Is EKE attackable by a brute-force password search?

Question

So I'm trying to properly implement the EKE protocol and I'm using C# with the Windows CNG and ECDH key exchange. I need to use this because it's FIPS certified and all that jazz.

So what I'm understanding about EKE is the fact that it depends on the fact that the public keys are completely randomized, therefore not verifiable plaintext. Otherwise it would be easy to run a dictionary attack against the protocol because the public keys are encrypted using the pre-known password.

Here's my problem: I noticed that in the CNG algorithm, the public key is a large byte array and it is completely randomized except for the first 6 bytes are always the same. From there on its completely randomized. This leads me to believe that if I wanted to run a dictionary attack against that, all I would need to know is what the first 6 bytes were and I could validate that I was able to decrypt that public key or maybe even brute force it.

To protect against this, I could easily truncate off the first 6 bytes and encrypt the rest of the completely randomized byte array with the password and then just add those 6 bytes back on either endpoint to calculate the secret key.

I'm pretty sure that's right but I'm discovering that cryptographic systems are fiendishly tricky and I wanted to run it past you guys to make sure I'm thinking about this correctly.

Answer 1

Doing EKE over an EC group is a tricky (and is something that RFC6124 avoids). The problem, as you note, is preventing an attacker from being able to determine whether a possible decryption is impossible (and hence he can remove that potential password from the list); that turns about to be considerably more involved than you would expect.

Even if you skip the first six bytes, well, the EC X and Y coordinates are not actually randomized (even though they look random); these coordinates are actually integers (if you're doing even-characteristic EC, field elements, don't worry about the distinction) which are related by an equation (perhaps $y^2 + ax = x^3 + b \mod p$) that's easy to check; this would easily allow an attacker to do a dictionary attack.

Now, all this can be handled; you can just use the X coordinate (ECDH still works just fine; however, your ECDH package might not support that), and you can deal with the problem that about half of the bit patterns are not possible EC X coordinates (and that's also easy to check); you could modify the encryption algorithm to deal with that as well.

On the other hand, all this is rather tricky for someone who isn't used to working with Elliptic Curves. I would strongly recommend that you use either EKE using a MODP group (as RFC6124 has; don't forget you have you use the nonstandard generators that RFC6124 has), or go with SRP.

Answer 2

The "proper" way to do EKE on a generic group (be it an elliptic curve or any other group) is to do the encryption part by "adding" a group element which is a hash of the password (actually, a hash of a structure containing the password and the names of the two entities involved in the operation, so as to avoid issues with attackers trying to play with several authentication sessions by distinct entities).

So you need a function $H$ which takes as input the password and outputs a (deterministic) pseudo-random point. One way is the following: for a $n$-bit curve of prime order (e.g. the P-256 curve from NIST: coordinates are integers modulo a 256-bit prime $p$, and the whole curve has prime order, so you want a random point on the curve), use the password as seed of a PRNG, to produce pairs $(x,r)$ where $x$ is an integer modulo $p$, and $r$ is either 0 or 1. Then, using the curve equation, try to find a point $(x,y)$ on the curve, such that the least significant bit of $y$ is $r$ (the curve yields $y^2 = x^3 + ax + b$; you then choose the square root which matches $r$). If the putative $y^2$ is not a square, use the next $(x,r)$ pair from the PRNG, and so on.

Then the EKE goes thus:

• Alice choose here random $a$ modulo $q$ ($q$ is the curve order) and sends $A = aG+H(\pi)$ (for the password $\pi$).
• Bob chooses $b$ and sends $B = bG+H(\pi)$.
• Alice computes $K = a(B-H(\pi))$.
• Bob computes $K = b(A-H(\pi))$.

The main difficulty is to have a $H$ which is close enough to a "random oracle" (the EKE described above is provable in the random oracle model). In practice, you need to be able to compute square roots modulo $p$ (this is easy if $p = 3 \pmod 4$).