Devil's Night

In my previous post, there is a high level overview about how OTR works. It mentions about AKE system. Today I am gonna show you how AKE works

Assume that Alice and Bob are going to implement AKE, The general idea is that Alice and Bob do an unauthenticated Diffie-Hellman (D-H) key exchange to set up an encrypted channel, and then do mutual authentication insidethat channel.

All exponentiations are done modulo a particular 1536-bit prime, and g is a generator of that group, as indicated in the detailed description below. Alice and Bob’s long-term authentication public keys are pub_A and pub_B, respectively.

Bob will be initiating AKE with Alice

• Bob:
  1. Picks a random value r (128 bits)
  2. Picks a random value x (at least 320 bits)
  3. Sends Alice AES_r(g^x), HASH(g^x)
• Alice:
  1. Picks a random value y (at least 320 bits)
  2. Sends Bob g^y
• Bob:
  1. Verifies that Alice’s g^y is a legal value (2 <= g^y <= modulus-2)
  2. Computes s = (g^y)^x
  3. Computes two AES keys c, c’ and four MAC keys m1, m1′, m2, m2′ by hashing s in various ways
  4. Picks keyid_B, a serial number for his D-H key g^x
  5. Computes M_B = MAC_m1(g^x, g^y, pub_B, keyid_B)
  6. Computes X_B = pub_B, keyid_B, sig_B(M_B)
  7. Sends Alice r, AES_c(X_B), MAC_m2(AES_c(X_B))
• Alice:
  1. Uses r to decrypt the value of g^x sent earlier
  2. Verifies that HASH(g^x) matches the value sent earlier
  3. Verifies that Bob’s g^x is a legal value (2 <= g^x <= modulus-2)
  4. Computes s = (g^x)^y (note that this will be the same as the value of s Bob calculated)
  5. Computes two AES keys c, c’ and four MAC keys m1, m1′, m2, m2′ by hashing s in various ways (the same as Bob)
  6. Uses m2 to verify MAC_m2(AES_c(X_B))
  7. Uses c to decrypt AES_c(X_B) to obtain X_B = pub_B, keyid_B, sig_B(M_B)
  8. Computes M_B = MAC_m1(g^x, g^y, pub_B, keyid_B)
  9. Uses pub_B to verify sig_B(M_B)
  10. Picks keyid_A, a serial number for her D-H key g^y
  11. Computes M_A = MAC_m1′(g^y, g^x, pub_A, keyid_A)
  12. Computes X_A = pub_A, keyid_A, sig_A(M_A)
  13. Sends Bob AES_c’(X_A), MAC_m2′(AES_c’(X_A))
• Bob:
  1. Uses m2′ to verify MAC_m2′(AES_c’(X_A))
  2. Uses c’ to decrypt AES_c’(X_A) to obtain X_A = pub_A, keyid_A, sig_A(M_A)
  3. Computes M_A = MAC_m1′(g^y, g^x, pub_A, keyid_A)
  4. Uses pub_A to verify sig_A(M_A)
• If all of the verifications succeeded, Alice and Bob now know each other’s Diffie-Hellman public keys, and share the value s. Alice is assured that s is known by someone with access to the private key corresponding to pub_B, and similarly for Bob.