Using Encryption for Authentication in Large Networks of Computers

Needham and Schroeder

Goals

• authenticated online communication (interactive protocols)
• authenticated offline communication (prove identity to party to which you send a message)
• signed communication (author and content provable to third parties)

I won't go into details about the specific protocols; the important things here are the concepts used. I urge you to know where you can find a copy of a good reference such as Applied Cryptography (2nd ed.); my personal copy tends to hang around 445 Soda.

• Assumptions
  • Users' personal computing environments are secure: when a user encrypts a message, for example, the operation performs as expected, and does not leak the key or the message to third parties
  • The network is insecure: eavesdroppers can arbitrarily read, insert, delete, or modify messages in transit.
• Authentication Server (aka Certification Authority)
  • Each user trusts an authentication server. For symmetric-key crypto, this server keeps a copy of the user's key, and so it has to be kept very secure from attack. For public-key crypto, the server keeps a public list of mappings from user names to the users' public keys, with each mapping signed by the server. In this case, only the mechanism to add new users to the list needs to be secured, but that can even happen offline.
  • There can be more than one authentication server (not counting duplicates; here, different servers store info about different users). These servers should all be able to talk to each other, either by each knowing each other's symmetric or public keys (Kerberos model), or by there being a "tree" wherein each node trusts its parent and children with its symmetric key, or to sign its public key (Certification Authority model).
• End-to-end encryption
  • Put encryption at the application level, not the network level; you may receive a message for which you do not yet know the key, for example.
  • This is covered in more detail in another paper.
• Nonces and Timestamps
  • These act as unique identifiers for a message, in order to prevent a "replay attack" in which an eavesdropper retransmits a properly-encrypted message she intercepted earlier.
  • In an interactive protocol, these can just be random numbers, sent and verified by each party. In a non-interactive protocol, a value tends to be used that is somehow based on the time. Users keep track of the timestamps they receive, and ignore duplicates. Sufficiently old timestamps are thrown away.
• Tickets and Certificates
  • In symmetric-key crypto, the authentication server will provide information of the form {B, CK, {CK, A}KB}KA. This information allows A to send {CK, A}KB to B and to subsequently communicate using the session key CK (nonces must be used to avoid replays).
  • In public-key crypto, the certification authority CA only needs to provide certificates of the form {B, PKB}SKCA, which A can verify and then then use PKB to communicate with B.
  • When more than one authentication server is involved, they can talk to each other (either directly or up and down a tree) to transparently (to the user) provide the same functionality.
• Characteristic Functions (aka Cryptographic Hash Functions)
  • These functions should have a number of properties:
    • Given M, h(M) is relatively easy to compute.
    • Given h(M), it is hard to find M ("inversion property").
    • It is hard to find different M1 and M2 with h(M1)=h(M2) ("collision property").
  • These functions are useful for proving that a message has not changed; it is infeasible for an adversary to change a message, but to end up with the same hash value: transmit the message, and a signed copy of the hash of the message (signed by the sender's secret key for public-key crypto, or encrypted (along with the name of the sender) with the authentication server's key, for symmetric-key crypto).