Image for post
Image for post
Photo by Paulius Dragunas on Unsplash

Password Authenticated Key Exchange (PAKE) is generating a good deal of interest, and a secret held only by Bob and Alice could be used to generate secret connections between them. One of the most convenient of these is a password, but it could as easily be a random nonce.

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:

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:

Image for post
Image for post

This is then encrypted with the P key:

Image for post
Image for post

Bob receives this and can recover:

Image for post
Image for post

Bob then create a random value b and then computes a new key of:

Image for post
Image for post

He encrypts with this P:

Image for post
Image for post

Bob then creates a new challenge (c1) and encrypted with the new key (K):

Image for post
Image for post

These two values are sent to Alice, and with the first part she computes the new shared key of:

Image for post
Image for post

She can use this to then decrypt EK(c1) to recover the challenge (c1). Alice then creates her own challenge (c2) and appends to c1 and encrypts with the new key:

Image for post
Image for post

The following shows an overview of the method:

Image for post
Image for post

Bob then decrypts and recovers both c1 and c2. The following is the code [here]:

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 [here]:

=== 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

And here is the shared code:

And here is it implemented in elliptic curves:

Reference

[1] Bellovin, S. M., & Merritt, M. (1992). Encrypted key exchange: Password-based protocols secure against dictionary attacks [here].

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store