[openssl-users] possible C bugs in ecp_nistp521

[Patrick Steuer]

Dear Bo-Yin Yang,

I looked into your felem_square counterexample:

There is an overflow in the result's least significant 128-bit limb such 
that the computed result is 2^128 smaller than the actual result.

The general problem is the following..

The function's comment says:
/*-
  * felem_square sets |out| = |in|^2
  * On entry:
  *   in[i] < 2^62
  * On exit:
  *   out[i] < 17 * max(in[i]) * max(in[i])
  */

If you look at the function's code youll notice that given the entry 
assumption, the exit assertion's "less than" should actually be a
"less than or equal to" for in the case of all in[i]s being equal to say 
x, max(in[i])=x and out[0]=17*x^2.

So out[0] is stored in 128-bits, but for e.g. x=2^62-1, out[0]>2^128.

If its a bug depends on the contexts from which felem_square is called. 
If for some reason its inputs are guaranteed to satisfy some stricter 
entry condition than stated in the above comment (such that there is no 
overflow) things might be alright.

I didnt look at your other examples but id expect something similar.

Best Regards,

Patrick Steuer