EC benchmarks randomly fail. about mbedtls HOT 11 CLOSED

These are the errors I get on a WIN64 system:

  ECDSA-secp224k1       :  FAILED: ECP - Generation of random value, such as (ephemeral) key, failed
  ECDSA-secp224k1       :  FAILED: ECP - Bad input parameters to function : ASN1 - ASN1 tag was of an unexpected value

from mbedtls.

Hey,

We are looking into it.. The fact that the errors are as such, I suspect a memory overwrite somewhere..

Are you able to do a git bisect to find out the 'bad commit'?
(git bisect start polarssl-1.3.4 polarssl-1.3.3)

from mbedtls.

I was able to reproduce the problem on Linux 64 (GCC 4.8): I got one FAIL out of three runs (with ecdh + ecdsa). Obviously this will be hard to bisect. If FAILs are more frequent on Windows, it will probably be easier to do the bisection on Windows.

Concerning memory, neither valgrind's memcheck nor ASan detected anything so far.

from mbedtls.

By the way, the "random failed" error for secp224k1 could perfectly be legitimate. Since the order of this curve is 2^225 + 2^113 + smaller things, the probability that a uniformly chosen string of 226 bits is an acceptable key is roughly very close to 1/2. But then we try only 10 times before we give up on key generation, so it should fail one time in 1048 tries.

This hypothesis is consistent with the fact that I get more failures when compiling with -O2 (ECDSA signature failing consistently with secp224k1). Also, this portion of the code was changed when implementing deterministic ECDSA, to match its procedure (and also remove a slight bias in our old procedure). Finally, I just upped the limit in ecp_gen_keypair() and got no failure for the last 30 runs (-O2, restricted to secp224k1), so I'm pretty confident this part of the problem is solved.

Now looking into the other failures.

from mbedtls.

Ok, so I checked the order of the other curves (what matters is that there are enough bits set to 1 close enough to the MSB) and it appears that brainpoolP384r1 is the second curve with the highest probability of failure for key generation (slightly above 45% for each iteration in ecp_gen_keypair(), so about 0.03% for 10 tries, which means one failure every roughly 3000 signatures). Then the two other brainpool curves with a theoretical failure rate of about one in 55000 signatures with 10 iterations. For the other curves (NIST and "Koblitz" curves except 224k1), the theoretical failure rate is completely negligible.

So if secp244k1 and brainpoolP384r1 are the only curves which got failures (as the above quotes suggest), then the insufficient number of iterations (with the new key selection algorithm) would explain the failures for ECDSA signatures and ECDHE handshakes.

Then, since ECDSA verification (resp. fixed ECDH handshake) in the benchmark app just reuse the signature (resp. ServerKeyExhange) from the last run of ECDSA signing (resp. ECDHE), all the FAILs there that directly follow a FAIL on the previous line could be explained by the previous FAIL.

Anyway, I'm going to do more runs to be sure. If you want to try too, the fix is to change 10 to 20 on line 1799 of library/ecp.c.

from mbedtls.

I can confirm, it seems to have fixed it. I cannot produce any FAILS anymore.

from mbedtls.

So just so I understand this correctly: All above mentioned issues are solved with the change in ecp.c?

from mbedtls.

Yes. I wrote a test program that does the same thing as the benchmark, but in a different order and with an infinite loop, it's been running for 1.5 hour now without any error (23k operations on each curve so far). I intend to have it running all night long just to be extra sure.

So, literally a one character fix :)

from mbedtls.

Maybe there could be some explanatory lines of comments to that line, where that value 20 is coming from (why it is 20 and not to 15 or 30 or anything else).

I think some of the odds calculations that Manuel did a few comments ago would make things in the code much clearer.

from mbedtls.

Yes, sure, the value will be commented! It already is in my private branch :)

from mbedtls.

Fixed for next release

from mbedtls.