Skip Menu |
 
Ticket metadata
The Basics
Id: 1593
Status: resolved
Priority: 0/
Queue: OpenSSL-Bugs

Custom Fields
Milestone: (no value)
Subsystem: (no value)
Severity: (no value)
Broken in: (no value)

People
Owner: Andy Polyakov
Requestors: Harry Reimann
Cc:
AdminCc:

More about the requestors

Harry Reimann

Comments about this user: No comment entered about this user
Groups this user belongs to
  • Everyone
  • Unprivileged

New reminder:
Subject:
Owner:
Due:

Dates
Created: Thu Oct 18 14:58:47 2007
Starts: Not set
Started: Not set
Last Contact: Wed Apr 23 10:36:24 2008
Due: Not set
Closed: Fri Sep 12 19:13:59 2008
Updated: Fri Sep 12 19:14:00 2008 by Andy Polyakov



Subject: BN_nist_mod_384 gives wrong answers
Date: Thu, 18 Oct 2007 13:46:27 +0200
To: openssl-bugs@openssl.org
From: Harry.Reimann@rohde-schwarz.com
Download (untitled) / with headers
text/plain 4.6k
The function BN_nist_mod_384 (in crypto/bn/bn_nist.c) gives wrong results
for some inputs. For example, on input:
0xffffffff00000000ffffffffffffffffffffffff000000000000000000000000fffffffffffffffffffffffffffffffe00000002ffffffffffffffffffffffff00000000ffffffffffffffffffffffff
it yields
0x100000000ffffffffffffffff00000000
but the correct result is
0x200000001fffffffffffffffe00000001.

As a consequence the function EC_POINT_add gives sometimes wrong results
for the NIST standard curve P-384. For example, if it computes the sum of
the points
(0x56fce068ab4eacbcbdca2a8cf5608e74d89ad30925bedac917aee82799eab18cd22e09a64bdcc2e03fd6f51a7c23bce6,

0x259b376c88fc35a48e25dc20da307cf2ca30cda69f14584020a75061b0a300f04c6acd9c8890a9653625bdaed2d2e4ce)
and
(0xa9031f9754b153444235d5730a9f718b27652cf6da412536e85117d866154e722dd1f658b4233d1fc0290ae683dc431a,

0x9ac68504a9cb1565ea7b9ccf45d53bbbcc06c39cb102a3ef5d3b7f02111489e7dde3bb954e8a10bf4b9c6f852dd2c46a)
which lie on that curve the result is a point which does not lie on the
curve. To see this compile the following code:

---------------- BEGIN: demo.c ------------------------------------------

#include <stdio.h>
#include <openssl/ec.h>
#include <openssl/obj_mac.h>

int main() {
BN_ULONG ax[12] = {
0x7c23bce6, 0x3fd6f51a, 0x4bdcc2e0, 0xd22e09a6, 0x99eab18c,
0x17aee827,
0x25bedac9, 0xd89ad309, 0xf5608e74, 0xbdca2a8c, 0xab4eacbc, 0x56fce068
};
BN_ULONG ay[12] = {
0xd2d2e4ce, 0x3625bdae, 0x8890a965, 0x4c6acd9c, 0xb0a300f0,
0x20a75061,
0x9f145840, 0xca30cda6, 0xda307cf2, 0x8e25dc20, 0x88fc35a4, 0x259b376c
};
BN_ULONG bx[12] = {
0x83dc431a, 0xc0290ae6, 0xb4233d1f, 0x2dd1f658, 0x66154e72,
0xe85117d8,
0xda412536, 0x27652cf6, 0x0a9f718b, 0x4235d573, 0x54b15344, 0xa9031f97
};
BN_ULONG by[12] = {
0x2dd2c46a, 0x4b9c6f85, 0x4e8a10bf, 0xdde3bb95, 0x111489e7,
0x5d3b7f02,
0xb102a3ef, 0xcc06c39c, 0x45d53bbb, 0xea7b9ccf, 0xa9cb1565, 0x9ac68504
};
BIGNUM AX = { ax, 12, 12, 0, BN_FLG_STATIC_DATA };
BIGNUM AY = { ay, 12, 12, 0, BN_FLG_STATIC_DATA };
BIGNUM BX = { bx, 12, 12, 0, BN_FLG_STATIC_DATA };
BIGNUM BY = { by, 12, 12, 0, BN_FLG_STATIC_DATA };
BN_CTX *ctx;
EC_GROUP *group;
EC_POINT *A, *B, *C;
int i;

ctx = BN_CTX_new();
group = EC_GROUP_new_by_curve_name(NID_secp384r1);
A = EC_POINT_new(group);
B = EC_POINT_new(group);
C = EC_POINT_new(group);

printf("Setting affine coordinates of point A:\nX = 0x%lx", ax[i = 11]);
while(i)
printf("%08lx", ax[--i]);
printf("\nY = 0x%lx", ay[i = 11]);
while(i)
printf("%08lx", ay[--i]);
EC_POINT_set_affine_coordinates_GFp(group, A, &AX, &AY, ctx);

printf("\nChecking A ... %s on curve.\n\n",
EC_POINT_is_on_curve(group, A, ctx) ? "is" : "not");

printf("Setting affine coordinates of point B:\nX = 0x%lx", bx[i = 11]);
while(i)
printf("%08lx", bx[--i]);
printf("\nY = 0x%lx", by[i = 11]);
while(i)
printf("%08lx", by[--i]);
EC_POINT_set_affine_coordinates_GFp(group, B, &BX, &BY, ctx);

printf("\nChecking B ... %s on curve.\n\n",
EC_POINT_is_on_curve(group, B, ctx) ? "is" : "not");

puts("Calling 'EC_POINT_add' to compute C = A + B.");
EC_POINT_add(group, C, A, B, ctx);

printf("Checking C ... %s on curve.\n",
EC_POINT_is_on_curve(group, C, ctx) ? "is" : "not");

exit(0);
}

---------------- END: demo.c --------------------------------------------

link it with the OpenSSL crypto library and run the resulting executable
with no arguments.

I did this with the following version of OpenSSL on a PC running Windows
XP sp2:
OpenSSL 0.9.8f 11 Oct 2007
built on: Thu Oct 18 07:59:19 2007
platform: Mingw32
options: bn(64,32) md2(int) rc4(idx,int) des(ptr,risc1,16,long) idea(int)
blowfish(idx)
compiler: gcc -DL_ENDIAN -DDSO_WIN32 -fomit-frame-pointer -O3 -march=i486
-Wall -DBN_ASM -DMD5_ASM -DSHA1_ASM -DOPENSSL_BN_ASM_PART_WORDS
-DOPENSSL_NO_CAMELLIA -DOPENSSL_NO_SEED -DOPENSSL_NO_RC5 -DOPENSSL_NO_MDC2
-DOPENSSL_NO_TLSEXT -DOPENSSL_NO_KRB5 -DOPENSSL_NO_DYNAMIC_ENGINE


************************************************************
ROHDE & SCHWARZ SIT GMBH

Dr. Harry Reimann
SIT-EC3
Am Studio 3
D-12489 Berlin
Germany

Phone: +49-30-65884-283
Fax: +49-30-65884-183

E-Mail: Harry <dot> Reimann <at> rohde-schwarz <dot> com
Internet: http://www.sit.rohde-schwarz.com
************************************************************
Geschäftsführer / President: Henning Krieghoff, Sitz der Gesellschaft /
Company's Place of Business: Berlin, Registereintrag / Commercial
Register No.: HRB 61 207, Umsatzsteuer-Identifikationsnummer (USt-IdNr.)
/ VAT Identification No.: DE 121 963 283, Elektro-Altgeräte Register
(EAR) / WEEE Register No.: DE 877 727 67
Subject: Re: [openssl.org #1593] BN_nist_mod_384 gives wrong answers
Date: Tue, 01 Apr 2008 11:45:35 +0200
To: rt@openssl.org
From: Andy Polyakov <appro@fy.chalmers.se>
Download (untitled) / with headers
text/plain 1.2k
Show quoted text
> The function BN_nist_mod_384 (in crypto/bn/bn_nist.c)

Other fast reduction functions are apparently affected too.

Show quoted text
> gives wrong results
> for some inputs. For example, on input:
> 0xffffffff00000000ffffffffffffffffffffffff000000000000000000000000fffffffffffffffffffffffffffffffe00000002ffffffffffffffffffffffff00000000ffffffffffffffffffffffff
> it yields
> 0x100000000ffffffffffffffff00000000
> but the correct result is
> 0x200000001fffffffffffffffe00000001.
>
> As a consequence the function EC_POINT_add gives sometimes wrong results
> for the NIST standard curve P-384. For example, if it computes the sum of
> the points
> (0x56fce068ab4eacbcbdca2a8cf5608e74d89ad30925bedac917aee82799eab18cd22e09a64bdcc2e03fd6f51a7c23bce6,
>
> 0x259b376c88fc35a48e25dc20da307cf2ca30cda69f14584020a75061b0a300f04c6acd9c8890a9653625bdaed2d2e4ce)
> and
> (0xa9031f9754b153444235d5730a9f718b27652cf6da412536e85117d866154e722dd1f658b4233d1fc0290ae683dc431a,
>
> 0x9ac68504a9cb1565ea7b9ccf45d53bbbcc06c39cb102a3ef5d3b7f02111489e7dde3bb954e8a10bf4b9c6f852dd2c46a)
> which lie on that curve the result is a point which does not lie on the
> curve. To see this compile the following code:

Please verify http://cvs.openssl.org/chngview?cn=16985. A.
Subject: Re: [openssl.org #1593] BN_nist_mod_384 gives wrong answers
Date: Tue, 8 Apr 2008 13:18:00 +0200
To: rt@openssl.org
From: Harry.Reimann@rohde-schwarz.com
Download (untitled) / with headers
text/plain 653b
Show quoted text
> Please verify http://cvs.openssl.org/chngview?cn=16985. A.

Unfortunately this is still incorrect. Consider for example a =
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000ffffffffffffffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000.
Then BN_nist_mod_384 yields
0xffffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000.
But the correct value (e.g. obtained by BN_mod) is
0xffffffffffffffff00000000000000000000000000000000000000000000000100000000ffffffffffffffff00000001.
I was not able to understand the treatment of the carry.

Harry Reimann
Subject: [Fwd: Re: [openssl.org #1593] BN_nist_mod_384 gives wrong answers]
Date: Wed, 09 Apr 2008 14:55:36 +0200
To: rt@openssl.org
From: Andy Polyakov <appro@fy.chalmers.se>
Download (untitled) / with headers
text/plain 1.7k
oops! should have replied to RT. sorry about noise on list. a.

Show quoted text
-------- Original Message --------
Subject: Re: [openssl.org #1593] BN_nist_mod_384 gives wrong answers
Date: Wed, 09 Apr 2008 14:51:17 +0200
From: Andy Polyakov <appro@fy.chalmers.se>
Reply-To: openssl-dev@openssl.org
To: openssl-dev@openssl.org
References: <RT-Ticket-1593@openssl.org>
<rt-3.4.5-13650-1207039972-898.1593-6-0@openssl.org>
<OF4DF61F9D.6E740B14-ONC1257425.003C4D7E-C1257425.003DFBDA@rohde-schwarz.com>
<rt-3.4.5-70811-1207650944-1288.1593-6-0@openssl.org>

>> Please verify http://cvs.openssl.org/chngview?cn=16985. A.
>
> Unfortunately this is still incorrect. Consider for example a =
> 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000ffffffffffffffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000.
> Then BN_nist_mod_384 yields
> 0xffffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000.
> But the correct value (e.g. obtained by BN_mod) is
> 0xffffffffffffffff00000000000000000000000000000000000000000000000100000000ffffffffffffffff00000001.

http://cvs.openssl.org/chngview?cn=17029 should do it. Note that this
commit addresses BN_nist_mod_384 only. Other functions will eventually
be fixed too. Presumably 64-bit implementation is also of interest...

> I was not able to understand the treatment of the carry.

They tried to "cheat" by simply accumulating carry bits and subtract
pre-computed carry*modulus value. But carry alone does not qualify for
if (intermediate_result >= modulus) for all inputs, therefore trouble.
Now it's done "by the book," i.e. modulo reduction is dutifully
performed after each operation. It's either that or full blown modulo
division. A.
Subject: Re: [openssl.org #1593] BN_nist_mod_384 gives wrong answers
Date: Wed, 23 Apr 2008 11:39:57 +0200
To: rt@openssl.org
From: Andy Polyakov <appro@fy.chalmers.se>
Download (untitled) / with headers
text/plain 1.4k
Show quoted text
>>> Please verify http://cvs.openssl.org/chngview?cn=16985. A.
>>
>> Unfortunately this is still incorrect. Consider for example a =
>> 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000ffffffffffffffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000.
>>
>> Then BN_nist_mod_384 yields
>> 0xffffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000.
>>
>> But the correct value (e.g. obtained by BN_mod) is
>> 0xffffffffffffffff00000000000000000000000000000000000000000000000100000000ffffffffffffffff00000001.
>>
>
> http://cvs.openssl.org/chngview?cn=17029 should do it.

And so would http://cvs.openssl.org/chngview?cn=17081. Please test and
confirm. It's probably easier to download the
http://cvs.openssl.org/getfile/openssl/crypto/bn/bn_nist.c?v=1.20 as
file instead of patching...

Show quoted text
>> I was not able to understand the treatment of the carry.
>
> They tried to "cheat" by simply accumulating carry bits and subtract
> pre-computed carry*modulus value. But carry alone does not qualify for
> if (intermediate_result >= modulus) for all inputs, therefore trouble.
> Now it's done "by the book," i.e. modulo reduction is dutifully
> performed after each operation. It's either that or full blown modulo
> division.

It was shown by Takanori Yanagisawa that "cheating" is perfectly
possible, if carry/borrow from final bn_[sub|add]_words is treated
appropriately. A.
Subject: Re: [openssl.org #1593] BN_nist_mod_384 gives wrong answers
Date: Wed, 23 Apr 2008 14:04:47 +0200
To: rt@openssl.org
From: Harry.Reimann@rohde-schwarz.com
Download (untitled) / with headers
text/plain 279b
Show quoted text
> And so would http://cvs.openssl.org/chngview?cn=17081. Please test and
> confirm. It's probably easier to download the
> http://cvs.openssl.org/getfile/openssl/crypto/bn/bn_nist.c?v=1.20 as
> file instead of patching...
>

This time it seems to be correct.

Harry Reimann