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)/CO 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)}\). For two secret values of \(x\) and \(y\), the resultant shared key is \(xyG\). [MTI/A0][MTI/A0 (EC)][MTI/B0][MTI/B0 (EC)][MTI/C0][MTI/C0 (EC)][MTI/C1].
Key exchange (MTI/C0) |
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^{xy} \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}}) }^x \pmod p\)
and Bob generates:
\(K_{bob} = { ({(a_{pub}) }^{b^{-1}}) }^y \pmod p\)
These will be the same as:
\(K_{alice} = { ({(b_{pub}) }^{a^{-1}}) }^x \pmod p = { ({( {z_a}^y ) }^{a^{-1}}) }^x \pmod p g^{xy} \pmod p\)
and Bob generates:
\(K_{bob} = { ({(a_{pub}) }^{b^{-1}}) }^y \pmod p = { ({ {z_b}^x ) }^{b^{-1}}) }^y \pmod p = g^{xy} \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"\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(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"\nInv a: {a_inv}, Inv_b: {b_inv}") K_a = (pow(pow(b_pub,a_inv,p),x,p)) % p K_b = (pow(pow(a_pub,b_inv,p),y,p)) % p print (f"\nAlice's Key: {K_a}") print (f"Bob's Key: {K_b}") print (f"\nChecking g^(xy)= {pow(g,x*y,p)}")
And a sample run:
Alice's long term private key: 1969927861, long term public key: 625922490 Bob's long term private key: 791174417, long term public key: 1887567540 Alice's session private key: 2388371944, session public key: 83111415 Bob's session private key: 1724351632, session public key: 1508974340 Inv a: 1290691981, Inv_b: 1819053173 Alice's Key: 844610848 Bob's Key: 844610848 Checking g^(xy)= 844610848
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.