334553 - NIST K- and B- curves don't work on HP-UX 11.11 PA-RISC

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Wan-Teh Chang]

On HP-UX 11.11 PA-RISC, NSS passes all the FIPS ECDSA
tests (Key Pair Generation, Public Key Validation,
Signature Generation, and Signature Verification) with
the NIST P- curves but fails all the FIPS ECDSA tests
with the NIST K- and B- curves.

Comment 1

[Wan-Teh Chang]

On HP-UX, mp_digit is defined as "unsigned long long".

If I add -DMP_USE_UINT_DIGIT to lib/freebl/Makefile to
cause mp_digit to be defined as "unsigned int" (this
requires that the assembly code files NOT be used),
the ECDSA tests pass.

If I only change lib/freebl/Makefile to not use the
assembly code files (which means mp_digit is still
defined as "unsigned long long"), the ECDSA tests
still fail with the NIST K- and B- curves.

It seems that we can conclude:
1. The assembly code files have nothing to do with this
bug.
2. If mp_digit is defined as unsigned long long, the
NIST K- and B- curves don't work.  If mp_digit is defined
as unsigned int, the NIST K- and B- curves work.

The failure is in EC_ValidatePublicKey.  It fails here
for a good public key:
lib/freebl/ecl/ec2_aff.c:ec_GF2m_validate_point

    /* 3: Verify that publicValue is on the curve. */
    ...
    /* check LHS - RHS == 0 */
    MP_CHECKOK( group->meth->field_add(&accl, &accr, &accr, group->meth) );
    if (mp_cmp_z(&accr) != 0) {
        res = MP_NO;
        goto CLEANUP;
    }

because accr is not zero.

Comment 2

[Wan-Teh Chang]

Attachment: Conservative patch for NSS_3_11_BRANCH

I was lucky enough to spot an unsigned long long constant
that doesn't have the ULL suffix in the 64-bit mp_digit code
in mpi/mp_gf2m.c, and that's indeed the problem.  I also found
that I could have caught this by examining the compiler warnings:

cc -o HP-UXB.11.11_OPT.OBJ/HP-UX_ABI32_FPU/mp_gf2m.o -c -O -DHPUX10 -Ae +Z -DHPU
X -Dhppa -D_HPUX_SOURCE -D_USE_BIG_FDS -Aa +e +DA2.0 +DS2.0 -DHPUX11 -DXP_UNIX -
DSHLIB_SUFFIX=\"sl\" -DSHLIB_PREFIX=\"lib\" -DSHLIB_VERSION=\"_3\" -DSOFTOKEN_SH
LIB_VERSION=\"3\" -DNSS_ENABLE_ECC -DRIJNDAEL_INCLUDE_TABLES -UDEBUG -DNDEBUG -D
NSS_ENABLE_ECC -DNSS_USE_ABI32_FPU -DMP_ASSEMBLY_MULTIPLY -DMP_ASSEMBLY_SQUARE -
DMP_API_COMPATIBLE -I../../../../dist/HP-UXB.11.11_OPT.OBJ/include  -I../../../.
./dist/public/nss -I../../../../dist/private/nss -Impi -Iecl  mpi/mp_gf2m.c
cc: "mpi/mp_gf2m.c", line 95: warning 602: Integer constant exceeds its storage.

The compiler pointed out a similar problem in ecl/ecp_256.c, although
this seems to affect corner cases only:

cc -o HP-UXB.11.11_OPT.OBJ/HP-UX_ABI32_FPU/ecp_256.o -c -O -DHPUX10 -Ae +Z -DHPU
X -Dhppa -D_HPUX_SOURCE -D_USE_BIG_FDS -Aa +e +DA2.0 +DS2.0 -DHPUX11 -DXP_UNIX -
DSHLIB_SUFFIX=\"sl\" -DSHLIB_PREFIX=\"lib\" -DSHLIB_VERSION=\"_3\" -DSOFTOKEN_SH
LIB_VERSION=\"3\" -DNSS_ENABLE_ECC -DRIJNDAEL_INCLUDE_TABLES -UDEBUG -DNDEBUG -D
NSS_ENABLE_ECC -DNSS_USE_ABI32_FPU -DMP_ASSEMBLY_MULTIPLY -DMP_ASSEMBLY_SQUARE -
DMP_API_COMPATIBLE -I../../../../dist/HP-UXB.11.11_OPT.OBJ/include  -I../../../.
./dist/public/nss -I../../../../dist/private/nss -Impi -Iecl  ecl/ecp_256.c
cc: "ecl/ecp_256.c", line 374: warning 602: Integer constant exceeds its storage
.

This patch is very conservative and is only suitable for the
NSS_3_11_BRANCH.  It is written to be clear that the patch
does not affect any other platform in order to avoid redoing
the FIPS ECDSA algorithm testing on other platforms. Note that
I duplicate the entire if statement in ecl/ecp_256.c because
I'm not sure if all compilers allow mixing of #if and if.

This experiment shows the HP C compiler truncates an unsigned
long long constant without the ULL suffix:

% cat foo.c
#include <stdio.h>

int main()
{
    unsigned long long ull = 0x1FFFFFFFFFFFFFFF;

    printf("0x%llx\n", ull);
    return 0;
}
% cc foo.c
cc: "foo.c", line 5: warning 602: Integer constant exceeds its storage.
/usr/ccs/bin/ld: (Warning) At least one PA 2.0 object file (foo.o) was detected.
 The linked output may not run on a PA 1.x system.
% ./a.out
0xffffffff

Comment 3

[Wan-Teh Chang]

Attachment: Proposed patch

Add the ULL suffix to the unsigned long long constants.

The only risk of this patch is that some compilers may not
support the unsigned long long type.  For example, older
versions of Microsoft Visual C++ use the unsigned __int64
type instead and the suffix is ui64 or UI64.  But all the
compilers for which we define mp_digit as a 64-bit unsigned
integer (either unsigned long or unsigned long long) have
the unsigned long long type and understand the ULL suffix.
So at least for now we don't need to go to the trouble of
defining macros to handle the suffix (UL, ULL, or UI64).

Comment 4

[Wan-Teh Chang]

Comment on attachment 219060 [details] [diff] [review]
Proposed patch

I forgot to mention that we should use this patch
on the NSS_3_11_BRANCH if we have to redo the FIPS
ECDSA algorithm testing for other reasons.

Comment 5

[Douglas Stebila]

Comment on attachment 219039 [details] [diff] [review]
Conservative patch for NSS_3_11_BRANCH

Not having an HP/UX machine, I can't test this patch to see if it works, I can only verify that it is valid C code and doesn't affect anything other than HP/UX.

Comment 6

[Douglas Stebila]

Comment on attachment 219060 [details] [diff] [review]
Proposed patch

Not having an HP/UX machine, I can't test this patch to see if it works, I can only verify that it is valid C code.  The ULL changes shouldn't affect other systems.

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

Let's see if the "proposed patch" builds on all platforms, and if so, use
it on the 3.11 branch also. 

Might this be one of the causes for bug 334057 ?

Comment 8

[Wan-Teh Chang]

I checked in the "proposed patch" on the NSS trunk (3.12).

Checking in ecl/ecp_256.c;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecp_256.c,v  <--  ecp_256.c
new revision: 1.2; previous revision: 1.1
done
Checking in mpi/mp_gf2m.c;
/cvsroot/mozilla/security/nss/lib/freebl/mpi/mp_gf2m.c,v  <--  mp_gf2m.c
new revision: 1.4; previous revision: 1.3
done

I checked in the "conservative patch" on the NSS_3_11_BRANCH (3.11.1).
Nelson, this patch avoids redoing the FIPS ECDSA algorithm testing on
other platforms.  I will check in the "proposed patch" on the
NSS_3_11_BRANCH if we have to redo the FIPS ECDSA algorithm testing on
other platforms for some other reason.

Checking in ecl/ecp_256.c;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecp_256.c,v  <--  ecp_256.c
new revision: 1.1.2.3; previous revision: 1.1.2.2
done
Checking in mpi/mp_gf2m.c;
/cvsroot/mozilla/security/nss/lib/freebl/mpi/mp_gf2m.c,v  <--  mp_gf2m.c
new revision: 1.3.30.1; previous revision: 1.3
done

Douglas, here is a better experiment to demonstrate the bug
in mpi/mp_gf2m.c on HP-UX:

% cat foo.c
#include <stdio.h>

int main()
{
    unsigned long long a1, a;

    a = 0xDEADBEEFDEADBEEFULL;
    a1 = a & (0x1FFFFFFFFFFFFFFF);

    printf("0x%llx\n", a1);
    return 0;
}
% cc foo.c
cc: "foo.c", line 8: warning 602: Integer constant exceeds its storage.
/usr/ccs/bin/ld: (Warning) At least one PA 2.0 object file (foo.o) was detected.
 The linked output may not run on a PA 1.x system.
% ./a.out
0xdeadbeef

The expected output is
0x1eadbeefdeadbeef

which is produced if I add ULL to the constant 0x1FFFFFFFFFFFFFFF.

GCC on Linux also warns about the constant 0x1FFFFFFFFFFFFFFF:
% gcc foo.c
foo.c: In function `main':
foo.c:8: warning: integer constant is too large for "long" type

but produces the correct output anyway:
% ./a.out
0x1eadbeefdeadbeef

Comment 9

[Wan-Teh Chang]

Attachment: Fix the comment in lib/freebl/Makefile

In 64-bit HP-UX PA-RISC "HP-UX_SINGLE_SHLIB" build,
mp_digit is "unsigned long" (64-bit).

In 32-bit HP-UX PA-RISC "HP-UX_ABI32_FPU" build,
mp_digit is "unsigned long long" (64-bit).

If the "digits" in the comments in lib/freebl/Makefile
means "mp_digits", then the comments should say
"64-bit digits" instead of "32-bit digits" for these
two HP-UX builds.

Note: in the 32-bit HP-UX PA-RISC "HP-UX_ABI32_INT32" build,
mp_digit is "unsigned int" (32-bit) because we compile with
-DMP_USE_UINT_DIGIT.

Comment 10

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 219080 [details] [diff] [review]
Fix the comment in lib/freebl/Makefile

r=nelson

Comment 11

[Wan-Teh Chang]

Comment on attachment 219080 [details] [diff] [review]
Fix the comment in lib/freebl/Makefile

I checked in this makefile comment patch on the
NSS trunk (3.12).

Checking in Makefile;
/cvsroot/mozilla/security/nss/lib/freebl/Makefile,v  <--  Makefile
new revision: 1.80; previous revision: 1.79
done

Comment 12

[Nelson Bolyard (seldom reads bugmail)]

Wan-Teh fixed this bug.

Comment 13

[Wan-Teh Chang]

Comment on attachment 219060 [details] [diff] [review]
Proposed patch

I checked in this better fix on the NSS_3_11_BRANCH
(NSS 3.11.2) since we already checked in ECC changes
to fix memory leaks (336335).

Checking in ecl/ecp_256.c;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecp_256.c,v  <--  ecp_256.c
new revision: 1.1.2.4; previous revision: 1.1.2.3
done
Checking in mpi/mp_gf2m.c;
/cvsroot/mozilla/security/nss/lib/freebl/mpi/mp_gf2m.c,v  <--  mp_gf2m.c
new revision: 1.3.30.2; previous revision: 1.3.30.1
done