3
$\begingroup$

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.

I am not sure how to go about this, this is something I came up with:

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?

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

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.

$\endgroup$
0
$\begingroup$

You're right, this method would work. And it will still be vulnerable to the MITM attack you mention without any authentication of the parties.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.