Cryptography

Review of Shared Key Cryptography

Shared key cryptography (also known as symmetric key cryptography) involves functions E (encryption) and D (decryption):

• E: key x message -> cyphertext
• D: key x cyphertext -> message.

In these notes, we use the following notation:

• {m}k to denote E(k,m)
• A -> B : m to denote "A sends m to B"
• A -> B : r,s,t to denote sending a message comprising fields r,s,t

We assume a strong attacker so that our protocols will resist whatever might be encountered in the "real world". The Dolev-Yao threat model has become a standard for this and formalizes the following attacks.

• An attacker can intercept messages transmitted between hosts.
• An attacker can parse any message comprising separately encrypted fields, and the attacker can extract the separate fields.
• An attacker can decrypt a message or field if and only if that attacker has previously obtained the appropriate encryption key.
• An attacker can construct and send new messages using information intercepted from old messages.

The first three elements characterize passive attacks; the fourth element exemplifies an active attack.

Uses of Shared Key Cryptography

When cryptography is first mentioned, most people think about implementing confidentiality. If A and B share a key k, then one can send a message to the other, keeping the contents of that message secret from the adversary.

A -> B:  {m}k

This basic approach also works for storing confidential information on a device, like a disk. Think of the device as B; only encrypted information is written to B. Note, the fact that information stored on B is encrypted might not suffice for keeping that information confidential. A text editor, for example, will typically work by copying any files it opens from long term storage (i.e., disk B) into CPU main memory; manipulation of file contents are then done in the CPU main memory. The file in CPU main memory is unencrypted (possibly providing an attacker with one access point). Moreover, to ensure that file updates are not lost, an editor is likely to store the current state of the object being edited in a temporary file (i.e., on disk B), and that means confidential information might temporarily reside unencrypted on the disk too, despite our best intentions. In fact, file deletion often leaves the file contents on a disk, so the confidential information might remain available in unencrypted form on the disk long after the editing session has ended.

Authentication using Shared Key Cryptography

An authentication protocol allows a principal receiving a message to determine which principal sent that message. Any afficionado of spy movies is doubtless familiar with one means by which principals might authenticate each other: The first principal asks an innocuous question --- called the challenge --- of the second ("Its a bright sunny day in Dover."). And if the first principal knows the secret response to that challenge ("But the queen prefers rain.") then the first concludes that the second is a compatriot.

This authentication protocol has a significant weakness. Anyone overhearing the exchange is thereafter able to impersonate either side. The basic idea---using knowledge of a secret---is sound. The problem is that a principal must reveal the secret in order to prove knowledge of that secret. This is known as weak authentication, and it is subject to replay attacks whereby an adversary repeats fragments of a past protocol run, appearing to have knowledge of the secret, and thus passes the authentication test.

In a strong authentication protocol, knowledge of the secret is demonstrated without revealing the secret itself. If, for example, the secret is used in determining the answer for the challenge, then an adversary overhearing the challenge and response is not going to be able to feign knowledge of the secret when confronted with other, different challenges.

One way to implement strong authentication in a network starts from the assumption that principals share a secret key. Knowledge of that key is demonstrated by using the key to encrypt and decrypt challenges, but the key itself is never revealed. Here is a protocol that allows B to authenticate A. Assume that A and B are the only two principals with knowledge of secret key k.

1. B:  select and store a new random value r.
2. B --> A:  B,r
3. A --> B:  {r}k
4. B:  check whether D(k, {r}k) equals the stored value r from step 1.

Reflection Attacks. An attacker T (traditionally cryptographers use T, short for "Trudy" to denote an intruder) can compromise the previous protocol, because A and B are each unwittingly running an "encryption service". In particular, A assumes any challenge it receives (message 2) is from an honest principal, and A always encrypts such challenges to produce responses. With a reflection attack, an intruder sends information from an on-going protocol execution back to the originator of that information. For example, an intruder might exploit an "encryption service" being run by both A and B and fool one of the participants into generating responses for its own challenges. To fool a participant, the intruder runs one or more concurrent instances of the protocol and interleaves them with the original. Because participants in protocol instances execute each protocol instance independently (and therefore no protocol instance inspects the state of any other concurrent instances, since doing that correlation would be expensive), a participant won't realize that it is generating responses for its own challenges.

Here's an example of a reflection attack. Indentation (and roman-numeral steps) indicate the concurrent instance of the protocol that T is running.

1. B:  select and store a new random value r.
2. B --> T:  B,r
       i.  T --> B:  A,r
      ii.  B --> T:  {r}k
3. T --> B: {r}k
4. B:  check whether D(k, {r}k) equals the stored value r from step 1.

Reflection attacks can often be prevented by breaking protocol symmetry and having messages somehow distinguish the different roles participants play. In the attack given above, B serves in the first protocol instance as the initiator and in the second instance as the responder. Here are some alternatives for breaking the symmetry:

• Have A and B share two keys: k_AB and k_BA. Key k_AB is used by B when A is the initiator; key k_BA is used by A when B is the initiator. A will never send a message encrypted under k_AB, and B will never send a message encrypted under k_BA; thus a message encrypted under k_AB must have been sent by B. Let's revisit the attack.

  1. B:  select and store a new random value r.
  2. B --> T:  B,r
         i   T --> B:  A,r
        ii.  B --> T:  {r}k_AB
  3. T --> B: ????  T sending {r}k_AB doesn't suffice, since {r}k_BA is awaited by B
     ...
  

• Insist that each response includes the identity of the responder, so the authentication protocol becomes:

  1. B:  select and store a new random value r.
  2. B --> A:  B,r
  3. A --> B:  {A,r}k
  4. B:  check whether D(k, {A,r}k) equals "A,v" where v is the stored value r from step 1.
  

  And the reflection attack is again foiled:

  1. B:  select and store a new random value r.
  2. B --> T:  B,r
         i   T --> B:  A,r
        ii.  B --> T:  {B,r}k
  3. T --> B: ????? Sending {B,r}k doesn't suffice, since {A,r}k is awaited by B.
     ...
  

Man-in-the-Middle Attacks. Nothing restricts an attacker T to using the "encryption service" that is provided by only a single protocol participant. Indeed, even with the defenses just outlined, an attacker T could run two instances of the protocol: one with A and the other with B, engaging as needed whichever of these principals would produce the value being needed by T to perpetuate its deception.

The general form of this attack is simple to understand. Each protocol step i of the form

i. X --> Y: m

i. X --> T: m
i' T --> Y: m

We cannot eliminate man-in-the middle attacks, but we can blunt their effectiveness. If all traffic is encrypted using a key shared only by the endpoints, then an intruder in the middle cannot read or alter messages. There is now little to be gained from the attack. We now have two compelling reasons for principals to share keys. First, shared keys can be used to implement string authentication. Second, shared keys help in defending against man-in-the-middle attacks. The obvious question, then, is how do hosts come to share those keys.

Key Distribution Protocols

With N hosts, O(N**2) shared keys are needed for each pair of hosts to have a distinct shared key. This is a large number of keys if N is large. Moreover, relatively few of those shared keys would ever actually be used, since any given host is likely to communicate only with a small subset of the hosts. So, instead, a mediated key exchange protocol is often used. Each host shares a key with some trusted host KDC (for Key Distribution Center), and KDC generates keys, on demand, for pairs of hosts that must communicate. Thus, starting from a relatively small number of shared keys we generate all the rest.

Assume each principal P shares key K_P with KDC. An obvious protocol for principal A to obtain a fresh secret key K_AB for communication with a principal B is:

1.  A --> KDC: A,B
2.  KDC --> A: A,B, {K_AB}K_A
3.  KDC --> B: A,B, {K_AB}K_B

The engineering flaw is addressed by having A be responsible for forwarding K_AB to B rather than having KDC do this.

1.  A --> KDC: A,B
2.  KDC --> A: A,B, {K_AB}K_A, {K_AB}K_B
3.  A --> B: A,B, {K_AB}K_B

We now turn to vulnerabilities in the protocol. An intruder T that can impersonate B, could obtain a key and position itself to read all traffic between A and B. This key is obtained by T using a man-in-the-middle attack at step 1 and starting a second, independent instance of the authentication after step 2.

1.  A --> T: A,B
1'  T --> KDC: A,T
2.  KDC --> T: A,T, {K_AT}K_A, {K_AT}K_T
        T --> KDC:  T,B
        KDC --> T:  T,B {K_TB}K_T, {K_TB}K_B
2'  T --> A: A,B, {K_AT}K_A, {K_TB}K_B
3.  A --> B: A,B, {K_TB}K_B

1.  A --> KDC: A,B
2.  KDC --> A: {A,B, K_AB, {K_AB}K_B}K_A
3.  A --> B: A,B, {K_AB}K_B

1.  T --> KDC: T,B
2.  KDC --> T: {T,B, K_TB, {K_TB}K_B}K_T
3.  T --> B: A,B, {K_TB}K_B

1.  A --> KDC: A,B
2.  KDC --> A: {A,B, K_AB, {A,B,K_AB}K_B}K_A
3.  A --> B: A,B,{A,B,K_AB}K_B

The next vulnerability to note is that message 2 can be replayed by an attacker having intercepted message 1, forcing A and B to use an old key K_AB. Any attacker that had learned an old value of K_AB has the incentive to make this happen. We defend against A being fooled into using an old message 2 by including a nonce in message 1, which must be returned in message 2.

1.  A --> KDC: A,B,r    where r is a new random value
2.  KDC --> A: {A,B,r, K_AB, {A,B,K_AB}K_B}K_A
3.  A --> B: A,B, {A,B,K_AB}K_B

Needham-Schroeder Protocol:

  1.  A --> KDC: A,B,r    where r is a new random value
  2.  KDC --> A: {A,B,r, K_AB, {A,B,K_AB}K_B}K_A
  3.  A --> B: A,B, {A,B,K_AB}K_B
  4.  B --> A: {r'}K_AB   where r' is a new random value
  5.  A --> B: {r' + 1 }K_AB

3.  A --> B: A,B, {A,B,K_AB}K_B

1. A --> B:  n,A,B, {r1,n,A,B}K_A 
2. B --> KDC: n,A,B, {r1,n,A,B}K_A, {r2,n,A,B}K_B
3. KDC --> B: n,{r1,K_AB}K_A, {r2,K_AB}K_B, 
4. B --> A:  n,{r1,K_AB}K_A

Presumably the compromise of K_A is eventually detected and A adopts a new value, expecting everyone to live happily ever after. Unfortunately, an attacker T can still foist a bad key on an unsuspecting principal B with which A is attempting to establish a shared key. Here's how that attack works. (You will find it helpful to refer back to the final version above for Needham-Schroeder.)

1. Suppose T has intercepted message 2 from an earlier run of Needham-Schroeder where intercepted key K_A was in use. This means that T can extract the value of shared key K_AB being proposed in that message and also can extract "{A,B,K_AB}K_B".
2. T now waits for A to start a new execution of Needham-Schroeder to establish a shared key with B. T replaces message 3 in that execution with a message it constructs using "{A,B,K_AB}K_B" that T extracted in step i and that includes old key K_AB.
3. Because T knows this old value of K_AB (from step i), T can respond correctly to the challenge that B then sends in Needham-Schroeder message 4. So B will be convinced that this old value of K_AB is the new key it shares with A.

The vulnerability actually permits a less passive attack: T need not have intercepted a previous message 2, instead forging a message 1 to receive a message 2 for every principal P). This leaves T free to then initiate a connection to any principal P, impersonating A, until such time that every other principal's key has been changed. So a single compromised key ultimately would require changing all KDC keys!

The defense against this attack is to have B create a nonce r" so that the step ii replay of the old Needham-Schroeder message 3 can be detected by B. This is achieved by prepending to Needham-Schroeder step 1 a protocol (labeled steps a and b) whereby B selects r" and sends it to A for forwarding to KDC, where it is used in forming message 2 (the contents of which are later used in building message 3).

a.  A --> B: A,B
b.  B --> A: A,B,r"
1.  A --> KDC: A,B,r,r"
2.  KDC --> A: {A,B,r, K_AB, {A,B,K_AB,r"}K_B}K_A
3.  A --> B: A,B, {A,B,K_AB,r"}K_B
4.  B --> A: {r'}K_AB   where r' is a new random value
5.  A --> B: {r' + 1 }K_AB