YAK - Authenticated Key ExchangeYAK uses public-key methods to implement authenticated key exchange. It was created by Feng Hao in 2010 [1]. [article][ECC implementation] |
Theory
If you’re into Cybersecurity, you should hopefully all know about the magic of the Diffie-Hellman (DH) method. Basically, Bob and Alice agree on a generator (\(g\)) and a large prime number (\(p\)), and then Bob creates a secret (b), and Alice creates her secret (a). Bob then calculates B= g^b (mod p), and Alice calculates \(A=g^a \pmod p\). They pass their values, and Bob computes \(A^b \pmod p\) and Alice computes \(B^a \pmod p\) and they should end up with the same shared secret, and derive a secret encryption key for that:
The first time I saw this in action, and when I tried the numbers, I fell in love with the magic of cryptography. But there’s a flaw! What if Eve is in-between:
Now, Eve sits in the middle between Bob and Alice ('a proxy''). Bob talks with Eve, and Alice also talks with Eve, and so we have an Eve-in-the-Middle. Bob has no way of knowing that he is talking to Eve instead of Alice, and the same goes for Alice. If Bob and Alice create a secure tunnel, Eve will decrypt things from Bob with \(K_1\), and then re-encrypt with \(K_2\) for Alice.
So how do we overcome this? Well, public key normally comes in somewhere, and where Alice and Bob can prove themselves using their public key. As a simple example we will take the YAK method, and which was defined by Feng Hao in 2010, and which focuses on authenticated key exchange (AKE) [here]:
Outline
With authenticated key exchange, Bob has a private key of \(b\) and a public key of:
\(Bpub=g^b \pmod p\)
Alice has a private key of \(a\) and a public key of:
\(Apub=g^a \pmod p\)
For the key exchange, Alice generates a secret \(x\) and sends Bob:
\(A=g^x \pmod p\)
For the key exchange, Bob generates a secret \(y\) and sends Alice:
\(B=g^y \pmod p\)
Alice computes:
\(K=(g^b g^y)^{x+a} \pmod p\)
Bob computes:
\(K=(g^a g^x)^{y+b} \pmod p\)
These values should be the same, as:
\(K=(g^b g^y)^{x+a} \pmod p= g^{(b+y)(x+a)}\)
Bob computes:
\(K=(g^a g^x)^{y+b} \pmod p = g^{(a+x)(y+b)}\)
Coding
The following is some example coding using a randomly generated prime number for a given bit size:
import random import Crypto.Util.number import sys g=2 a=random.randint(0,2e16) b=random.randint(0,2e16) x=random.randint(0,2e16) y=random.randint(0,2e16) bits=128 if (len(sys.argv)>1): bits=int(sys.argv[1]) p=Crypto.Util.number.getPrime(bits,randfunc=Crypto.Random.get_random_bytes) Apub=pow(g,a,p) Bpub=pow(g,b,p) A=pow(g,x,p) B=pow(g,y,p) KA=pow(B*Bpub,x+a,p) KB=pow(A*Apub,y+b,p) print ("Prime: ",p) print ("g ",g) print ("\nAlice public key: ",Apub) print ("Bob public key: ",Bpub) print ("\nAlice secret:\t",a) print ("Bob secret:\t",b) print ("\nAlice passes:\t",A) print ("Bob passes:\t",B) print ("\nAlice key:\t",KA) print ("Bob key:\t",KB)
The following is a sample run and have \(p\) and \(q\) have 256 bits and N has 512 bits. We can see the number of decimal digits in \(N\) is 154:
Prime: 215724695438718924354421417797563802497 g 2 Alice public key: 205412326610078321536315600196139515706 Bob public key: 179089747468154927852212148173309375757 Alice secret: 17040461508873207 Bob secret: 18678083293992335 Alice passes: 19126688461477256476923071702392802133 Bob passes: 91658868533302328032484343124318057321 Alice key: 16102372395080110318170505028128817551 Bob key: 16102372395080110318170505028128817551
References
Hao, F. (2010, January). On robust key agreement based on public key authentication. In International Conference on Financial Cryptography and Data Security (pp. 383-390). Springer, Berlin, Heidelberg. [here]