Encrypted Key Exchange (EKE) was created by Steven M. Bellovin and Michael Merritt [1] and uses a shared password to encrypt the Diffie-Hellman key exchange. In this method, an initial encryption key is generated from a shared password, and which is then used to generate a session key through an encrypted Diffie-Hellman handshaking process [Key exchange methods] [article]. In this case we will use discrete logarithm methods to pass the shared key [EKE (Discrete logs)] [EKE (Elliptic Curve)].
Encrypted Key Exchange (EKE) - Discrete Logs |
Theory
Initially, Bob and Alice agree on a password and then generate an encryption key from a hash of the password (\(P\)). Alice initially creates a secret value of \(a\) and then computes:
\(g^a \pmod p\)
This is then encrypted with the \(P\) key:
\(E_P(g^a \pmod p)\)
Bob receives this and can recover:
\(g^a \pmod p\)
Bob then create a random value \(b\) and then computes a new key of:
\(K=g^{ab} \pmod p\)
He encrypts with this \(P\) :
\(E_P(g^{b} \pmod p)\)
Bob then creates a new challenge (\(c_1\)) and encrypted with the new key (K):
\(E_K(c_1)\)
These two values are sent to Alice, and with the first part she computes the new shared key of:
\(K=g^{ab} \pmod p\)
She can use this to then decrypt \(E_K(c_1)\) to recover the challenge (\(c_1\)). Alice then creates her own challenge (\(c_2\)) and appends to \(c_1\) and encrypts with the new key:
\(E_K(c_1,c_2)\)
Bob then decrypts and recovers both \(c_1\) and \(c_2\).
Coding
The following is the code:
import sys import random import hashlib from aes import encrypt, decrypt from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes from Crypto.Hash import SHA256 from Crypto.Protocol.KDF import PBKDF2 import binascii primebits=64 secret="Hello" if (len(sys.argv)>1): primebits=int(sys.argv[1]) if (len(sys.argv)>2): secret=(sys.argv[2]) print ("=== Stage 1: Bob and Alice generate a key===") print (f"Shared password: {secret}") s=int(hashlib.md5(secret.encode()).hexdigest(),16) p = getPrime(primebits, randfunc=get_random_bytes) g=3 a = random.randint(0, p-1) b = random.randint(0, p-1) A = pow(g,a,p) B = pow(g,b,p) salt = get_random_bytes(16) key = PBKDF2(str(secret), salt, 32, count=1000, hmac_hash_module=SHA256) print (f"Key from password: {binascii.hexlify(key)}") A_cipher = encrypt(str(A),key) print ("\n=== Stage 2: Alice generates cipher and sends to Bob===") print ("\nBob now receives ...") B_receive = decrypt(A_cipher,key) B_receive = int(B_receive) print (f"Alice sends: A_cipher={binascii.hexlify(A_cipher)}\nBob receives={B_receive}") KeyBob = pow(B_receive,b,p) NewKey = PBKDF2(str(KeyBob), salt, 32, count=1000, hmac_hash_module=SHA256) print (f"Bob computes New Key as {binascii.hexlify(NewKey)}") B_cipher = encrypt(str(B),key) print ("\n=== Stage 3: Bob recovers shared key and sends back an encrypted challenge ===") c1 = "I am Bob" c1_cipher = encrypt(c1,NewKey) print (f"\nBob send B_cipher={binascii.hexlify(B_cipher)}, c1_cipher={binascii.hexlify(c1_cipher)}") A_receive = int(decrypt(B_cipher,key)) Key = pow(A_receive,a,p) newkey = PBKDF2(str(Key), salt, 32, count=1000, hmac_hash_module=SHA256) print (f"\nAlice computes New key as {binascii.hexlify(newkey)}") c1_recover = decrypt(c1_cipher,newkey) print ("\n=== Stage 4: Alice recovers the challenge with shared key and sends back an encrypted challenge ===") print (f"\nAlice recovers the challenge: '{c1_recover}' using New Key") print ("Now Alice sends to Bob ...") #### c2 = "I am Alice" c2_cipher = encrypt(c2,NewKey) print (f"\nAlice send c2_cipher={binascii.hexlify(c2_cipher)}") print ("\n=== Stage 6: Bob recovers the challenge with the new shared key ===") print ("Now Bob receives ...") c2_recover = decrypt(c2_cipher,newkey) print (f"\nBob recovers the challenge: '{c2_recover}' using New Key")
And a sample run:
=== Stage 1: Bob and Alice generate a key=== Shared password: Hello Key from password: b'2c4583bcc4be6e7088bfd6b1c60829a642bcbcea28a304211c365d2a2b3e77a7' === Stage 2: Alice generates cipher and sends to Bob=== Bob now receives ... Alice sends: A_cipher=b'dc0858ee18a7f21c64d43a700630ead4' Bob receives=1800915403 Bob computes New Key as b'6eb1c7225363b2d9ecbf9afa75293f7a64144b6b720663c8cfa791ba1232d493' === Stage 3: Bob recovers shared key and sends back an encrypted challenge === Bob send B_cipher=b'aa78b1f538e730278dc31ecb30042dba', c1_cipher=b'4d9198da995f8167dea5f27cd009a8f5' Alice computes New key as b'6eb1c7225363b2d9ecbf9afa75293f7a64144b6b720663c8cfa791ba1232d493' === Stage 4: Alice recovers the challenge with shared key and sends back an encrypted challenge === Alice recovers the challenge: 'I am Bob' using New Key Now Alice sends to Bob ... Alice send c2_cipher=b'6c3c41e60bfcfa288483e91af861d9e9' === Stage 6: Bob recovers the challenge with the new shared key === Now Bob receives ... Bob recovers the challenge: 'I am Alice' using New Key
Presentation
Reference
[1] Bellovin, S. M., & Merritt, M. (1992). Encrypted key exchange: Password-based protocols secure against dictionary attacks [here].