CS 513 System Security -- Symmetric Cryptosystems and Authentication

Symmetric Cryptosystems and Authentication

Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett

Last time we discussed several primitive cryptosystems. We mentioned two properties, confusion and diffusion, that are desirable in any cryptosystem.

There are three classes of cryptographic functions that turn out to be useful:

secret key -- one key, referred to as the secret key; we saw examples of this last time,
public key -- two keys, referred to as private and public keys,
hash -- zero keys.

Secret Key Cryptography

Secret key cryptography involves two functions:

encryption: E(key, message) -> enciphered text
decryption: D(key, ciphertext) -> message.

These functions are inverses of each other, so that message = D(key, E(key, message)). The E and D notation is a bit verbose, so we will use the notation k{m} to say that message m was encrypted under key k.

Uses for secret key cryptography include: transmitting secret messages in the presence of passive eavesdroppers, storing information in encrypted form on insecure media, and authentication (determining who is involved in a given dialogue.) Note: if you are using encryption to store data on insecure media, most editors work on a decrypted form of data. Thus, they may store temporary unencrypted versions of your data.

Authentication, as we have seen it before, is often done with a password. However, that form of authentication involves revealing the 'secret' (password) in order to prove one's identity. We are interested in strong authentication--providing proof of identity without revealing the secret. In other words, strong authentication involves proving knowledge of a secret (key/password) without revealing the secret itself.

Suppose we would like user A to prove to user B that A is A without revealing the secret that is the essence of being A, and vice versa. Thus, we desire a protocol that allows A and B to authenticate themselves to each other. Assume that there is a shared, secret key: k. Knowing k is proof of being either A or B. The desired mutual authentication protocol works as outlined below. The arrows indicate sending a message.

There are many subtle errors that can arise when designing cryptographic protocols. We now illustrate some. First, note in the above protocol that B sends A two messages in a row. An obvious optimization might be to combine those messages into one, as well as having A announce itself and send a random bit string for B to encrypt at the same time.

This protocol, however, if flawed. In particular, it is susceptible to what is known as a reflection attack. It is possible for an eavesdropper, T, to convince B that T is A. T exploits the fact that B seems willing to encrypt challenges. Therefore, T can pretend to be A as follows:

After B sends R₁ to T, T needs to get it encrypted under k in order to convince B that T is A. T therefore starts another session, sending R₁ which B then returns encrypted. T now learns the encrypted version of R₁ and can convince B that B is communicating with A.

There are several possible approaches to repairing the protocol:

Use two different keys, one from A to B and another from B to A. This introduces additional keys to keep track of.
Insist that the challenge from the initiator look different from the challenge from the responder. If this holds, then T can never get B to encrypt the 'right thing.' For instance, suppose A generates random even numbers and B generates random odd numbers. Then B would never encrypt a random number that it had generated (as in the above example.)
Initiator must prove its identity first. This is based on the assumption that the initiator in a protocol is likely to be the attacker (if anyone is). In the above examples, B would respond with a challenge of its own before responding to A's (T's) challenge. The reflection attack in this type of protocol would not work.