Dear all,
we found some counter-examples (examples where wrong answers were returned) for field element computations in the C routines for P-521 (that is, modulo 2^521-1). The counterexamples, a C test file, a Makefile, and a short README are attached. The routines in question are: felem_square, felem_mul, felem_diff_128_64. Can someone inform us whether these are in fact a couple of bugs that we found, or did we miss something. Best wishes, Bo-Yin Yang P.S. The counterexamples are: - for felem_square and felem_mul: felem in = { 0x3fd9049d07fdc0ad, 0x3ece5f4000000000, 0x39c5349d6a623811, 0x3bf48f8409415499, 0x3ffdac80c8300000, 0x3ff3f3de63be6baf, 0x3fa3eff5c6db1743, 0x3dde8d0ddc21079f, 0x3e068b5ec961f8fc }; - for felem_diff_128_64: largefelem out = { 0,0,0, 0,0,0, 0,0,0 }; felem in = { 0x4000000000012270, 0x1000000000000000, 0x0010000000000000, 0x0400000000000000, 0x0800000000000000, 0x0020000000000000, 0x0000000040000000, 0x0002000000000000, 0x0000000400000000 }; -- B.Y. -- openssl-users mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users Makefile (352 bytes) Download Attachment check.c (14K) Download Attachment README (1K) Download Attachment |
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 -- openssl-users mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users |
I would expect that correct results would be provided for all valid
inputs (including those inputs that are not otherwise constrained). As such, I would class this as a bug in OpenSSL. -Kyle H On Mon, Jan 7, 2019 at 7:44 PM Patrick Steuer <[hidden email]> wrote: > > 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 > -- > openssl-users mailing list > To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users openssl-users mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users |
> I would expect that correct results would be provided for all valid
> inputs (including those inputs that are not otherwise constrained). > As such, I would class this as a bug in OpenSSL. These functions are not part of the public OpenSSL API so that's just not how it works. There is a ton of internal code across the library that makes assumptions about the inputs, e.g. in this case the internal caller using some non-trivial representation that somehow bounds limbs. In this instance, I suspect Patrick's statement is valid -- hopefully it's just a documentation typo and the bounds are tighter. In any case, this (and any other might-be arithmetic bug) is potentially a security issue so it shouldn't be discussed on a public mailing list. BBB -- openssl-users mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users |
Free forum by Nabble | Edit this page |