# Establish more secure symmetric crypto system given A and B have small initial secret

Alice and Bob have a secret number X that is known only to them. However, the number is only 14 bits, and Trudy knows they share such a secret and can intercept messages between them. Instead of using X right of the bat for their symmetric key, Alice and Bob want a more secure system because Trudy can brute force X. How can Alice and Bob have establish a more secure system?

My textbook points at Diffe-Hellman as a hint.

Alice and Bob enact DH as normal. After Alice receives $g^b$ mod $p$ and Bob receives $g^a$ mod $p$ instead of just computing $g^{ab}$ mod $p$ as their shared key, they add X as well, for $g^{abX}$ mod $p$.

Since $p$ will be much larger than $X$ the whole key can't be brute forced easily. A MiM attack Trudy can try in normal DH is to establish $g^{at}$ mod $p$ with Alice and $g^{bt}$ mod $p$ with Bob. My understanding is $x$ or $g^{atx}$ mod or $g^{btx}$ mod $p$ would be expensive to find for Trudy, thus Alice and Bob retain confidentiality.

I'm not sure if I'm overthinking the problem or if what I came up with adds that much more security that couldn't be achieved in a simpler way. Is my method OK? What could a more secure system be?

• could this be related to password based key exchange? – Florian Bourse Feb 22 '18 at 9:25

My understanding is $x$ or $g^{atx} \bmod p$ or $g^{btx} \bmod p$ would be expensive to find for Trudy, thus Alice and Bob retain confidentiality.
Not really. Trudy knows $g^a$ (Alice sent that) and $t$ (Trudy picked that); let us assume that Alice uses the value $g^{atx} \bmod p$ for something, such as deriving symmetric keys, and then uses that to encrypt a message. What Trudy could do it compute $(g^a)^{tx} \bmod p$, for all possible values of $x$, and derive keys from all of them; that's 16384 possible keys. Trudy can then try to decrypt Alice's message using each key; the one that works will tell her the correct value of $x$ (and then she can either continue with a MITM attack, or impersonate Bob).
There are protocols that don't have this weakness, examples include EKE and SRP; these don't prevent Trudy from taking a random guess of $x$, attempting a MITM attack (and learning whether that was the $x$ that Alice and Bob shared); what they do is make sure that Trudy can't do any better; to test 1000 possible $x$ values, she'll need to perform the MITM attack 1000 times.
After class it seems a good answer would be for Alice and Bob to to normal DH, except encrypt $g^{a}$ mod p and $g^{b}$ mod p with their shared 14-bit symmetric key. The DH MiM is a real time attack and Trudy has a limited window. Also, $g^{a}$ mod p and $g^{b}$ mod p are not plain messages, so Trudy would not know if she found the right key trying to brute force all 16k possibilities.