EKE! It’s PAKE!

EKE! It’s PAKE!

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:

This is then encrypted with the P key:

Bob receives this and can recover:

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

He encrypts with this P:

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

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

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:

The following shows an overview of the method:

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].