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 elliptic curve methods with the secp256k1 curve [EKE (Discrete logs)] [EKE (Elliptic Curve)].
Encrypted Key Exchange (EKE) - Elliptic Curves |
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:
\(aG\)
This is then encrypted with the \(P\) key:
\(E_P(aG)\)
Bob receives this and can recover:
\(aG\)
Bob then create a random value \(b\) and then computes a new key of:
\(K=abG\)
He encrypts with this \(P\) :
\(E_P(bG)\)
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=abG\)
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.Random import get_random_bytes from Crypto.Hash import SHA256 from Crypto.Protocol.KDF import PBKDF2 import binascii from secp256k1 import curve,scalar_mult,topoint secret="Hello" if (len(sys.argv)>1): secret=(sys.argv[1]) print ("=== Stage 1: Bob and Alice generate a key===") print (f"Shared password: {secret}") s=int(hashlib.md5(secret.encode()).hexdigest(),16) a = random.randint(0, curve.n-1) b = random.randint(0, curve.n-1) A= scalar_mult(a,curve.g) B= scalar_mult(b,curve.g) 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 = topoint(decrypt(A_cipher,key)) print (f"Alice sends: A_cipher={binascii.hexlify(A_cipher)}\nBob receives={B_receive}") # KeyBob = pow(B_receive,b,p) KeyBob = scalar_mult(b,B_receive) 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 = topoint(decrypt(B_cipher,key)) # Key = pow(A_receive,a,p) Key = scalar_mult(a,A_receive) 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'1789e0ae6f4135c7b4209a6278783002add6fce562b01ec939f1f2ce054237a5' === Stage 1: Bob and Alice generate a key=== Shared password: Hello Key from password: b'0d09cc3dbed55cdf0666bbbf753b4eb624b50555210d2def15b67f4e8f0f801b' === Stage 2: Alice generates cipher and sends to Bob=== Bob now receives ... Alice sends: A_cipher=b'5d605e1cd2d1011da0ddaad7e3aa4638ee311261f3eaa8ffa5176743bce7fd4689334595bbfc58ac6fa9e47f28de9cf7a3dca42608d54aa00e38a06d11dcb8f1b4a6daa93f2890285916e464588ae3facf5e1522d7ea35127140a6233317d31cb0770b8b07532d7ea55abfb1c9b8202996fa1c08ce7eb06530df5ce19935ed750d944751b55d69a1feef22007d97c9906c201ffa533154106df4dec29c11913b' Bob receives=(26498355478756615066570462773136595753620376875047274864147723539083047295133, 57234790719840716503354676248137421491923825264783115232290933986290705367125) Bob computes New Key as b'd732e45c04864785deb30f72c9023f1864c648650a19087161befa4f4b1e4ddb' === Stage 3: Bob recovers shared key and sends back an encrypted challenge === Bob send B_cipher=b'3e386e9720c6e64926164a85f00875c890e361240648a30f66a297d06d16c6afec539ee8f46bef9d8e017a920074e1545525e263dc689386758f4dddf502f0d9165c09bf26bfdf1a9f75b3aebc6b8c697844dc3af09d09e848686a8e63a686adb17b79f64f62a7f7543b3986968248049aa2a4a9facca63a18522383b3e5c969fb880a3281f7022373c45fbfb0ce1158e626175e8229fd4776807fa984e930b5', c1_cipher=b'f1b456d191e96ade6a6566e901add018' Alice computes New key as b'd732e45c04864785deb30f72c9023f1864c648650a19087161befa4f4b1e4ddb' === 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'3170d9c32400df709430c7b180391ffa' === 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].