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
        o 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
        o The network is insecure: eavesdroppers can arbitrarily read,
          insert, delete, or modify messages in transit.
   * Authentication Server (aka Certification Authority)
        o 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.
        o 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
        o 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.
        o This is covered in more detail in another paper.
   * Nonces and Timestamps
        o 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.
        o 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
        o 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).
        o 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.
        o 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)
        o 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").
        o 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).