Structure and Interpretation of Computer Programmers

I make it easier and faster for you to write high-quality software.

Thursday, April 12, 2012

On the magic of key agreement

Imagine that you want to implement AirDrop, or something like it. Two computers that have (possibly) never communicated before are going to share a file. Now you know that you want to encrypt the file in transit so that only these two computers get to see the file, but how do you set up an encryption key? You can’t generate it on one of the computers and send it over, because that way lies the infinite stack of turtles: how do you keep the key secure in transit?

The solution (or at least, one solution known as the Diffie–Hellman protocol) turns out to be beautifully simple. First, arrange that everyone knows two numbers, which we’ll call the base or generator g and the modulus m. For example, in the SKIP protocol these two numbers are documented:

g = 0x cf ca d9 90 8d 98 c1 c4 4e 4e 88 20 69 e8 7b fb
d0 ca e1 ee 24 64 a9 6c 89 70 a0 8c 86 00 30 c6
c2 83 4a 0d 82 bd a5 ba 10 cf 80 af 61 96 11 4b
3b 87 a9 7e 59 98 c4 aa 0c bd b7 2b 23 18 33 64
f3 b6 2e 1a 4d e8 86 85 aa de 78 a1 5d ce 65 33
75 7a 9d 00 b9 9e 05 26 ed 79 62 15 97 c4 06 26
fa 51 e1 5e f5 1d cb d2 23 e2 73 e5 f2 c7 3c c4
de 58 cd 3b b6 15 3c aa 84 7c fa 5f cb 6b 8d 78

m = 0x dd c9 08 3e 8f ae ef 28 16 ad 50 a9 68 ac bd 04
8e 90 9e ab 5d 41 fc 0a 51 3f 86 0a c4 1b 22 b9
30 dc a3 0a 59 73 05 38 59 b7 85 66 df ff c6 5b
b9 1f fe 44 d9 d6 5e cb 9b 68 38 a1 fd 25 3f 01
51 88 9e 93 c3 22 24 f9 03 e6 9b 8b 07 34 9d 9f
9b 38 4b c0 97 03 dc e5 2e 92 47 4c 2c e1 59 26
14 82 49 dd 58 13 91 05 12 11 a1 45 06 ac 11 8f
b1 83 53 46 93 88 9a 46 b1 8a 01 50 cb 5e 82 55

The two computers each generate a random number, which we’ll call x_A and x_B. They keep these numbers secret, but can independently calculate:

r = g^(x_A) mod m

s = g^(x_B) mod m

and they send each other r and s. The first computer can use x_A and s to derive:

k_A = s^(x_A) mod m = g^(x_A.x_B) mod m

while the second uses x_B and r to derive:

k_B = r^(x_B) mod m = g^(x_A.x_B) mod m ≡ k_A

They got the same key! Because you can’t gain any of the secrets k, x_A or x_B knowing only r and/or s, the two systems can negotiate a secret key that’s only known to the two of them without having to first establish a secure channel. I just think that’s really cool.

If you want to use this stuff in an iOS app, OpenSSL contains an implementation of Diffie–Hellman. On Android javax.crypto.KeyAgreement can do it for you.

posted by Graham at 19:24  

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress