Using Encryption for Authentication in Large Networks of Computers
--- Needham and Schroeder, 1978.


- authentication: verifying the identity of the communicating principals to 
  one another;

- three functions are discussed:

	- establishment of authenticated interactive communication;
	- authenticated one-way communication, such as email;
	- signed communication, where origin and integrity can be
	  authenticated to a third party.

1) Protocols for Establishing Interactive Connections:
-----------------------------------------------------

With conventional algorithms:
----------------------------

- each principal has a secret key that is known only to itself and to
  its authentication server;

- if A wants to communicate with B:

	- the message must be comprehensible only to B, so B can use
	  its contents to identify itself to A;
	- it must be evident to B that it originated with A;

Handshake:

A->AS:	A, B, IA

AS->A:	KA{IA, B, CK, KB{CK, A}}

A->B:	KB{CK, A}

In order to know if CK is fresh, B uses a challenge:

B->A:	CK{IB}

A->B:	CK{IB - 1}

At this point, the freshness of the key is guaranteed and secure
communication is achieved by using CK.


With public-key algorithms:
--------------------------

A->AS:	A, B

AS->A:	SKAS{PKB, B}		signature provides integrity;

A->B:	PKB{IA, A}

B->AS:	B, A

AS->B:	SKAS{PKA, A}

B->A:	PKA{IA, IB}

A->B:	PKB{IB}


Multiple Authentication Servers:
-------------------------------

- only ASa can produce items encrypted with KA while only ASb can
  generate items encrypted with KB;

- they suppose that separate measures have been taken to ensure secure
  communication between the servers;

- the authentication server for a host can be discovered by the host's
  name;

- the communication between servers provide the data for A:

	ASa->ASb:	CK, B, A, IA
	ASb->ASa:	KB{CK, A}, IA, A

- in the public-key case, A can approach ASb directly if A knows the
  server's public key;

- the servers maintain no state about ongoing transactions;


2) One-way communication:
------------------------

- even though they may not be available at the same time,
  authentication of sender and receiver is desirable for email;


With conventional algorithms:
----------------------------

A->B:	KB{CK, A}, CK{MESSAGE}

- each recipient maintains a register in which an entry of the form
  {source, timestamp} is stored for each mail item received.  A mail
  item is rejected if its {source, timestamp} is on the register or its
  timestamp predates the current time by more than a constant T;


With public-key algorithms:
--------------------------

A->B:	PKB{A, I, SKA{B}}

- I is a nonce identifier that is used to connect the header with the
  ensuing message text sent under the protection of PKB;


3) Digital Signatures:
---------------------

With conventionan encryption and a little help:
----------------------------------------------

- one method uses a characteristic function of the cleartext message
  that is to be signed;

- the characteristic function must have the property that, given the
  cleartext message, the function, and the resulting characteristic 
  value, it is hard to find another sensible cleartext message that
  produces the same characteristic value;

* characteristic function looks like hash functions;

- while sending the text, A computes the characteristic value CS and
  requests a signature block from the AS:

A->AS:	A, KA{CS}

AS->A:	KAS{A, CS}

- the last message is encrypted with AS's key and therefore is
  accessible only to AS;

- Note that A cannot validate the message, but if it has been
  interfered with, then B will be unable to validate the signature;

B->AS:	B, KAS{A, CS}

AS->B:	KB{A, CS}

- if the returned CS matches the one computed by B, the principal
  named in the last messageis the sender of the signed text;


With public-key encryption:
--------------------------

A->B:	PKB{SKA{textblock}}


Conclusions:

- protocols using conventional or public-key cryptosystems are
  similar;

- caching is important to reduce transactions with lookup servers;