The Diffie-Hellman key exchange method is weak from a security point-of-view, as Eve can perform an Eve-in-the-middle attack, and Alice does not authenticate the value received from Bob, and vice-versa. One way to overcome this is MTI (Matsumoto, Takashima, Imai)/AO key agreement [1,2], and where Bob and Alice perform a trusted key exchange for a one-time setup. This passes \(z_a\) and \(z_b\), and then each session passes public keys of \(a_{pub}\) and \(b_{pub}\). [MTI/A0][MTI/A0 (EC)][MTI/B0][MTI/B0 (EC)][MTI/C0][MTI/C0 (EC)][MTI/C1].
Key exchange (MTI/A0) |
Theory
The Diffie-Hellman key method is weak from a security point-of-view, as Eve can perform an Eve-in-the-middle attack, and Alice does not authenticate the value received from Bob, and vice-versa. One way to overcome this is MTI/AO key agreement, and where Bob and Alice perform a trusted key exchange for a one-time setup. This passes \(z_a\) and \(z_b\), and then each session passes public keys of \(a_{pub}\) and \(b_{pub}\). An outline is:
The first phase is a one-time setup, and where Alice and Bob agree on a generator value (\(g\)) and a prime number (\(p\)). Next Alice generates a private key of \(a\) and Bob generates a private key of \(b\). Alice then passes her public key of:
\(z_a = g^a \pmod p\)
Bob passes his public key of:
\(z_b = g^b \pmod p\)
When Bob and Alice want to generate a new key, Alice generates a random value \(x\) and Bob generates a random value \(y\). Alice sends a public key value to Bob of:
\(a_{pub} = g^x \pmod p\)
Bob sends a public key value to Alice of:
\(b_{pub} = g^y \pmod p\)
Alice then generates a shared key of:
\(K_{alice} = {(b_{pub})}^x {(z_b)}^a \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^y {(z_a)}^b \pmod p\)
These will be the same as:
\(K_{alice} = {(b_{pub})}^x {(z_b)}^a \pmod p = {(g^b)}^x {(g^y)}^a \pmod p = g^{ba} g^{yx} \pmod p = g^{ab+xy} \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^y {(z_a)}^b \pmod p = {(g^a)}^y {(g^x)}^b \pmod p = g^{ab} g^{xy} \pmod p = g^{ab+xy} \pmod p \)
Coding
The following is the code:
import random from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes import sys primebits=32 if (len(sys.argv)>1): primebits=int(sys.argv[1]) g=3 p = getPrime(primebits, randfunc=get_random_bytes) a=random.randint(1,p-1) b=random.randint(1,p-1) z_a = pow(g,a,p) z_b = pow(g,b,p) print(f"\nAlice's long term private key: {a}, long term public key: {z_a}") print(f"\nBob's long term private key: {b} long term public key: {z_b}") x=random.randint(1,p-1) y=random.randint(1,p-1) a_pub = pow(g,x,p) b_pub = pow(g,y,p) print(f"\nAlice's session private key: {x}, session public key: {a_pub}") print(f"\nBob's session private key: {y}, session public key: {b_pub}") K_a = (pow(b_pub,a,p)*pow(z_b,x,p)) % p K_b = (pow(a_pub,b,p)*pow(z_a,y,p)) % p print (f"\nAlice's Key:\t{K_a}") print (f"Bob's Key:\t{K_b}")
And a sample run:
Alice's long term private key: 234922934927051736061407466859781671926, long term public key: 9553865896294691998820050822736010357 Bob's long term private key: 192684820488235721913538610637243476533 long term public key: 87629409173798051182302592765578727177 Alice's session private key: 176470342325955300772757080054933405845, session public key: 250928909289796421603126984483101721083 Bob's session private key: 217073041510159575168982756664701598050, session public key: 61705912907138968438256620254966595320 Alice's Key: 267734767508402112601722397616524910297 Bob's Key: 267734767508402112601722397616524910297
Presentation
Reference
[1] Matsumoto, Tsutomu, Youichi Takashima, and Hideki Imai. "On seeking smart public-key-distribution systems." IEICE TRANSACTIONS (1976-1990) 69.2 (1986): 99-106.
[2] Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (2018), Handbook of applied cryptography. CRC press, Page 517-518.