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 (Matsumoto, Takashima, Imai)/BO 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}\). The \(a_{pub}\) value is created from Bob's public key, and \(b_{pub}\) value is created from Alice's public key. In this case we will use the inverse of Bob's and Alice's keys. For Alice's private key of \(a\), we determine \(a^{-1}\) for \(a \times a^{-1} \pmod {(p-1)}=1\). For two secret values of \(x\) and \(y\), the resultant shared key is \(g^{x+y} \pmod p\) [MTI/A0][MTI/A0 (EC)][MTI/B0][MTI/B0 (EC)][MTI/C0][MTI/C0 (EC)][MTI/C1].
Key exchange (MTI/B0) |
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/BO 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}\). The \(a_{pub}\) value is created from Bob's public key, and \(b_{pub}\) value is created from Alice's public key. In this case we will use the inverse of Bob's and Alice's keys. For Alice's private key of \(a\), we determine \(a^{-1}\) for \(a \times a^{-1} \pmod {(p-1)}\). For two secret values of \(x\) and \(y\), the resultant shared key is \(g^{x+y} \pmod p\). 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} = {z_b}^x \pmod p\)
Bob sends a public key value to Alice of:
\(b_{pub} = {z_a}^y \pmod p\)
Alice then generates a shared key of:
\(K_{alice} = {(b_{pub})}^{a^{-1}} g^x \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^{b^{-1}} g^y \pmod p\)
These will be the same as:
\(K_{alice} = {(b_{pub})}^{a^{-1}} g^x \pmod p = {(z_a^y)}^{a^{-1}} g^x \pmod p = g^{a y a^{-1}} g^x \pmod p = g^y g^x \pmod p = g^{x+y} \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^{b^{-1}} g^y \pmod p = {(z_b^x)}^{b^{-1}} g^y \pmod p = g^{b x b^{-1}} g^y \pmod p = g^x g^y \pmod p = g^{x+y} \pmod p\)
The value of \(a^{-1}\) is calculated with:
\(a \times a^{-1} \pmod {(p-1)}\)
In Python, this is achieved with:
a_inv = libnum.invmod(a,p-1)
Coding
The following is the code:
import random import libnum 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=0 b=0 while (libnum.gcd(a,p-1)!=1): a=random.randint(1,p-1) while (libnum.gcd(b,p-1)!=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"\bBob'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(z_b,x,p) b_pub = pow(z_a,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}") a_inv = libnum.invmod(a,p-1) b_inv = libnum.invmod(b,p-1) print (f"Inv a: {a_inv}, Inv_b: {b_inv}") K_a = (pow(b_pub,a_inv,p)*pow(g,x,p)) % p K_b = (pow(a_pub,b_inv,p)*pow(g,y,p)) % p print (f"\nAlice's Key: {K_a}") print (f"Bob's Key: {K_b}") print (f"\nChecking g^(x+y)= {pow(g,x+y,p)}")
And a sample run:
Alice's long term private key: 21529949, long term public key: 2200449372 Bob's long term private key: 2563900771 long term public key: 2056614523 Alice's session private key: 1344915156, session public key: 338317829 Bob's session private key: 1667204244, session public key: 1202372470 Inv a: 1206462049, Inv_b: 149779631 Alice's Key: 976729499 Bob's Key: 976729499 Checking g^(x+y)= 976729499
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.