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)/C1 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 \(g^{abxy} \pmod p\). [MTI/A0][MTI/A0 (EC)][MTI/B0][MTI/B0 (EC)][MTI/C0][MTI/C0 (EC)][MTI/C1].
Key exchange (MTI/C1) |
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^{abxy} \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}^{ax} \pmod p\)
Bob sends a public key value to Alice of:
\(b_{pub} = {z_a}^{by} \pmod p\)
Alice then generates a shared key of:
\(K_{alice} = { (b_{pub}) }^x \pmod p\)
and Bob generates:
\(K_{bob} = { (a_{pub}) }^y \pmod p\)
These will be the same as:
\(K_{alice} = { (b_{pub}) }^x \pmod p = { ({z_a}^{by}) }^x \pmod p = g^{abxy} \pmod p \)
and Bob generates:
\(K_{bob} = { (a_{pub}) }^y \pmod p = { ({z_b}^{ax}) }^y \pmod p = g^{abxy} \pmod p \)
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,a*x,p) b_pub = pow(z_a,b*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,x,p)) % p K_b = (pow(a_pub,y,p)) % p print (f"\nAlice's Key: {K_a}") print (f"Bob's Key: {K_b}") print (f"\nChecking g^(abxy)= {pow(g,a*b*x*y,p)}")
And a sample run:
Alice's long term private key: 11480431455049849093, long term public key: 13000716410397532378 Bob's long term private key: 9849536166080929371, long term public key: 3083486889214346829 Alice's session private key: 9729179376738345237, session public key: 6274525452848730879 Bob's session private key: 416154734152200862, session public key: 7102899671276618846 Alice's Key: 172223978027123239 Bob's Key: 172223978027123239 Checking g^(abxy)= 172223978027123239
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.