609068 - Implement J-PAKE in FreeBL

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Mozilla needs a J-PAKE implementation for Sync in Firefox 4. A J-PAKE implementation in NSS will eliminate the need for Firefox to depend on FreeBL's MPI library (and avoiding issues with platform-dependent MPI digit representations), and it should be easier to review--especially, in comparison with the OpenSSL implementation.

Comment 1

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Extended DSA key generation logic used for J-PAKE

J-PAKE needs to be able to generate random nonces which are very much like DSA keys, except they are not limited to 160 bits. Here, I extended the DSA key generation code to work with subprimes larger than 160 bits. The code ensures that the pre-existing DSA functions continue to reject inputs that don't have a 160-bit subprimes.

The J-PAKE code will also use the new DSA_NewRandom function independently of DSA_NewKeyExtended in order to generate the random R value for Schnorr signatures. (See the next patch.)

Comment 2

[Robert Relyea]

Comment on attachment 492858 [details] [diff] [review]
Extended DSA key generation logic used for J-PAKE

This is the hdf patch;( I'd give it an r+, but I already have;).

bob

Comment 3

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Extended DSA key generation logic used for J-PAKE

Sorry, Bob. Here's the correct patch.

Comment 4

[Robert Relyea]

Comment on attachment 492875 [details] [diff] [review]
Extended DSA key generation logic used for J-PAKE

r- but only for two small issues...

1) in dsa_GenerateGlobalRandomBytes, now that the length of 'dest' is no longer the passed in length, we should probably pass in it's length in *destLen and check it. I know the length has to be at least the length of qItem->len, but that's a little more obscure to the caller. We should check to make sure *destLen is at least the size to hold  our expected dest value (if (*destLen < qLen) fail).

This is not a bug in the current patch. the requested change will cause a change to line 445. kSeedLen needs to be set to sizeof (kSeed). (the other usage will already have seed->len set properly).

2) There is a leak at 268 in DSA_NewRandom if the generateBytes fails, we leak the seed.

Everything else looks good.

bob

Comment 5

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Patch for all lib/freebl changes for J-PAKE

In order to avoid conflicts in loader/ldvector, I combined the DSA changes with the new J-PAKE specific code.

Comment 6

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Changes to bltest for testing J-PAKE

This patch for the J-PAKE tests needs some work and I would like some feedback about the general approach.

Comment 7

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: FreeBL J-PAKE tests in bltest

With this patch, bltest -J will run the J-PAKE tests. 

The test vectors were created by instrumenting the latest OpenSSL J-PAKE implementation so that the intermediate results were output, and then capturing the output of sample runs.

Comment 8

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

(In reply to comment #4)
> Comment on attachment 492875 [details] [diff] [review]
> Extended DSA key generation logic used for J-PAKE
> 
> r- but only for two small issues...
> 
> 1) in dsa_GenerateGlobalRandomBytes, now that the length of 'dest' is no longer
> the passed in length, we should probably pass in it's length in *destLen and
> check it. I know the length has to be at least the length of qItem->len, but
> that's a little more obscure to the caller. We should check to make sure
> *destLen is at least the size to hold  our expected dest value (if (*destLen <
> qLen) fail).
> 
> This is not a bug in the current patch. the requested change will cause a
> change to line 445. kSeedLen needs to be set to sizeof (kSeed). (the other
> usage will already have seed->len set properly).

This is addressed in the new version of dsa.c. I used the (output buffer, output length, max length) pattern for the parameters that is common in the rest of NSS.

> 2) There is a leak at 268 in DSA_NewRandom if the generateBytes fails, we leak
> the seed.

This is also addressed in the new patch.

Comment 9

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: J-PAKE FreeBL Patch v2 - add DSA_NewRandom to loader.c

This is the same as the previous patch except that it includes the DSA_NewRandom stub in loader.c that I accidentally omitted previously.

Comment 10

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

There should be a check that gx3 != gx4 and gx3 in round2 and also this check should be done in the OpenSSL implementation if it isn't already. I will add this check after I get Bob's review comments.

Comment 11

[Robert Relyea]

Comment on attachment 494310 [details] [diff] [review]
J-PAKE FreeBL Patch v2 - add DSA_NewRandom to loader.c

r-

The DSA Random stuff looks ok.

I have some questions that need to be answered before I r+, but the r- is primarily for a few bugs..

Bug: In JPAKE_Verify we check that R is < q, but we haven't set R to *r until later.

Without that R will be zero (which is less than q), so the test will always pass.
(NOTE, unlike GX, R of zero (and thus R=Nq) is not a problem (where GX= (n)*p-1 is a problem). Still the code should be correct.

Potential Bug: I can't see how you are using JPAKE_Round2, but I think you still need to raise your calculated base to the x2*s power at some point to get 'A' (I was just expecting it to be in JPAKE_Round2 rather than somewhere else).

General comment. I would have liked to see less 'name swapping' in the mp calls. Particularly confusing is the change of base from mpint to SECItem in two different, bug closely related functions, so that I originally thought we had a type mismatch. I also found the swapping of modulus and exponent a bit much. I would have rather just had p and q mp_int's (and x2s get's converted to mp_int twice, which sort of cries out for it's own mp_int).

Finally the question:

In JPAKE_sign, you take x and return gx. My question is is this how you are generating gx? I would have though you would use DSA_KeyGen to get both x and gx, then pass both to sign.

I don't see anything else that makes me sqirm;).

bob

Comment 12

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

(In reply to comment #11)
> Bug: In JPAKE_Verify we check that R is < q, but we haven't set R to *r until
> later.

> Without that R will be zero (which is less than q), so the test will always
> pass. (NOTE, unlike GX, R of zero (and thus R=Nq) is not a problem
> (where GX= (n)*p-1 is a problem). Still the code should be correct.

Yes, I added this check at the very end so that we only interoperate with implementations that follow the "spec" exactly to reduce the potential for any problems with R=Nq+x for N>0. I will move the initialization of R up.

> Potential Bug: I can't see how you are using JPAKE_Round2, but I think you
> still need to raise your calculated base to the x2*s power at some point to 
> get 'A' (I was just expecting it to be in JPAKE_Round2 rather than
> somewhere else).

JPAKE_Round2 is used two different ways:

1. It is used to generate A. In this case, the x2s parameter will be non-NULL and JPAKE_Round2 will return base and x2s. The caller then passes these to JPAKE_Sign to generate A=base^x2s, base^v, and R. (JPAKE_Sign isn't the best name because it doesn't account for the fact that it calculates base^exponent. Maybe JPAKE_RaiseAndSign would be a better name.)

2. It is used to calculate the base of B (where B=base^x4s) for the final round. In this case, x2s will be NULL and JPAKE-Round2 returns just the base.

> General comment. I would have liked to see less 'name swapping' in the mp
> calls. Particularly confusing is the change of base from mpint to SECItem in
> two different, bug closely related functions, so that I originally thought we
> had a type mismatch. I also found the swapping of modulus and exponent a bit
> much. I would have rather just had p and q mp_int's (and x2s get's converted > to mp_int twice, which sort of cries out for it's own mp_int).

I will make these clarifications.

> Finally the question:
> 
> In JPAKE_sign, you take x and return gx. My question is is this how you are
> generating gx? I would have though you would use DSA_KeyGen to get both x and
> gx, then pass both to sign.

In round 2, x isn't random; it is x2*s. I do the exponentiation g^x inside JPAKE_Sign to show and exploit the symmetry between the round 1 calculations and the round 2 calculations. In round1, we have (base=g, x=x1) and (base=g, x=x2); in round2, we have (base=g^(x1+x3+x4), x=x2*s) but otherwise the calculations are the same.

Thus, before Round1, I just call the new DSA_NewRandom directly to generate x1 and x2, since JPAKE_Sign does the exponentiation.

Comment 13

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Everything except jpake.c

This patch addresses your review comments and adds a PLArenaPool parameter to DSA_NewRandom. By allowing the random value to be allocated in the arena, it will get zeroized in J-PAKE/softoken when the arena is freed.

Comment 14

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Patch to add jpake.c

Patch to add jpake.c. Besides addressing the review comments, I also added checks for s < q and gx3 != gx4 and more general parameter validation.

Comment 15

[Robert Relyea]

Comment on attachment 495064 [details] [diff] [review]
Everything except jpake.c

r+ rrelyea, but this patch needs jpake.c to land at the same time or before this patch.

Comment 16

[Robert Relyea]

> In round 2, x isn't random; it is x2*s. I do the exponentiation g^x inside
> JPAKE_Sign to show and exploit the symmetry between the round 1 calculations
> and the round 2 calculations. In round1, we have (base=g, x=x1) and (base=g,
> x=x2); in round2, we have (base=g^(x1+x3+x4), x=x2*s) but otherwise the
> calculations are the same.

OK, so the rounds are SNORR signed as well. I would prefer and optional parameter GX which could pass GX in and not have to calculate it. You may not need it for JPAKE_Sign, but I can use if for other SNORR-like operations.

Comment 17

[Robert Relyea]

Comment on attachment 495065 [details] [diff] [review]
Patch to add jpake.c

r+

I'm going to R+ this, but I would like an optional gxin (SECITEM *) parameter in JPAKE_SIGN.

if gxin == NULL, then you generate GX = g^x mod p, other wise GX = gxin.
You could optionally use the existing gx parameter. If gx->len == 0, then calculate it, otherwise, just use it.

bob

Comment 18

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Tests for J-PAKE FreeBL in bltest (bltest -J)

Bob, JPAKE_Sign is the only place that calculates g^x so gxin would always be NULL. This test program + the upcoming jpakesftk.c patch should make this clear.

Comment 19

[Robert Relyea]

I think you missed my point.

I want a check so that someone else can use JPAKE_Sign by passing in gxin even if JPAKE doesn't do it. (I'm trying to save myself some future work here. If you add this, JPAKE_Sign can be used by other protocols for part of their work).

It's OK of you implement it as

gx->len = 0 rather than adding a new parameter.

bob

Comment 20

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: J-PAKE FreeBL (v4) - now JPAKE_Sign has gxIn/gxOut parameters

Comment 21

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Tests for J-PAKE FreeBL in bltest (bltest -J) (v2)

Comment 22

[Robert Relyea]

Comment on attachment 495173 [details] [diff] [review]
J-PAKE FreeBL (v4) - now JPAKE_Sign has gxIn/gxOut parameters

r+ pending the equivalent change in pjake.c

Comment 23

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

jpake.c is already rolled into that patch. (I had only split the patch into two parts previously because I wasn't expecting the interface to change.)

Comment 24

[Robert Relyea]

Hmm, I see no pjake.c, did you cvs diff -Nup?

bob

Comment 25

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

jpake.c is a new file and cvs -Nup doesn't work. I guess I should use cvsdo.pl to create patches for new files, but AFAICT the site from which I am supposed to download cvsdo.pl is down. So, I did a normal diff -Nup /dev/null lib/freebl/jpake.c, appended it to the patch, and edited the filename in the patch.

I guess that isn't enough to satisfy the bugzilla patch UI but if you look at the raw patch it is at the bottom of the patch.

Comment 26

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: cvs -N10p patch for jpake.c

Here is the standalone version of the jpake.c patch if it helps.

Comment 27

[Robert Relyea]

Comment on attachment 495192 [details] [diff] [review]
cvs -N10p patch for jpake.c

r+

I don't know what -10 was, but this patch seemed to not like the tools.
I reviewed the relevant changes, I presume that's all that changed.

bob

Comment 28

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Patch for the stable branch that resolves the conflicts in ldvector.c, loader.h, loader.c

Comment 29

[Robert Relyea]

Tip/Trunk checkin

Checking in lib/freebl/blapi.h;
/cvsroot/mozilla/security/nss/lib/freebl/blapi.h,v  <--  blapi.h
new revision: 1.40; previous revision: 1.39
done
Checking in lib/freebl/dsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/dsa.c,v  <--  dsa.c
new revision: 1.21; previous revision: 1.20
done
RCS file: /cvsroot/mozilla/security/nss/lib/freebl/jpake.c,v
done
Checking in lib/freebl/jpake.c;
/cvsroot/mozilla/security/nss/lib/freebl/jpake.c,v  <--  jpake.c
initial revision: 1.1
done
Checking in lib/freebl/ldvector.c;
/cvsroot/mozilla/security/nss/lib/freebl/ldvector.c,v  <--  ldvector.c
new revision: 1.27; previous revision: 1.26
done
Checking in lib/freebl/loader.c;
/cvsroot/mozilla/security/nss/lib/freebl/loader.c,v  <--  loader.c
new revision: 1.51; previous revision: 1.50
done
Checking in lib/freebl/loader.h;
/cvsroot/mozilla/security/nss/lib/freebl/loader.h,v  <--  loader.h
new revision: 1.32; previous revision: 1.31
done
Checking in lib/freebl/manifest.mn;
/cvsroot/mozilla/security/nss/lib/freebl/manifest.mn,v  <--  manifest.mn
new revision: 1.60; previous revision: 1.59
done
Checking in lib/freebl/stubs.c;
/cvsroot/mozilla/security/nss/lib/freebl/stubs.c,v  <--  stubs.c
new revision: 1.10; previous revision: 1.9
done
Checking in lib/freebl/stubs.h;
/cvsroot/mozilla/security/nss/lib/freebl/stubs.h,v  <--  stubs.h
new revision: 1.7; previous revision: 1.6
done

Comment 30

[Robert Relyea]

Branch checkin

hecking in lib/freebl/blapi.h;
/cvsroot/mozilla/security/nss/lib/freebl/blapi.h,v  <--  blapi.h
new revision: 1.33.22.2; previous revision: 1.33.22.1
done
Checking in lib/freebl/dsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/dsa.c,v  <--  dsa.c
new revision: 1.20.22.1; previous revision: 1.20
done
Checking in lib/freebl/jpake.c;
/cvsroot/mozilla/security/nss/lib/freebl/jpake.c,v  <--  jpake.c
new revision: 1.1.2.2; previous revision: 1.1.2.1
done
Checking in lib/freebl/ldvector.c;
/cvsroot/mozilla/security/nss/lib/freebl/ldvector.c,v  <--  ldvector.c
new revision: 1.21.22.3; previous revision: 1.21.22.2
done
Checking in lib/freebl/loader.c;
/cvsroot/mozilla/security/nss/lib/freebl/loader.c,v  <--  loader.c
new revision: 1.44.22.2; previous revision: 1.44.22.1
done
Checking in lib/freebl/loader.h;
/cvsroot/mozilla/security/nss/lib/freebl/loader.h,v  <--  loader.h
new revision: 1.26.22.2; previous revision: 1.26.22.1
done
Checking in lib/freebl/manifest.mn;
/cvsroot/mozilla/security/nss/lib/freebl/manifest.mn,v  <--  manifest.mn
new revision: 1.58.2.1; previous revision: 1.58
done
Checking in lib/freebl/stubs.c;
/cvsroot/mozilla/security/nss/lib/freebl/stubs.c,v  <--  stubs.c
new revision: 1.8.2.1; previous revision: 1.8
done
Checking in lib/freebl/stubs.h;
/cvsroot/mozilla/security/nss/lib/freebl/stubs.h,v  <--  stubs.h
new revision: 1.5.2.1; previous revision: 1.5
done

Comment 31

[Robert Relyea]

Attachment: Branch patch as checked in

Tweaks from Brian's patch before checkin:
   DOS ^M's were removed.
   stubs.c/h were updated to include NSS_SecureMemcmp
   stubs.h was added to jpake.c

Comment 32

[Robert Relyea]

Attachment: Tip/Trunk patch as checked in

Tweaks from Brian's patch before checkin:
   DOS ^M's were removed.
   stubs.c/h were updated to include NSS_SecureMemcmp
   stubs.h was added to jpake.c

Comment 33

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Attachment: Patch on top of checked-in code to check shared key s != 0 [checked in]

Mozilla will never call this with a zero s but it should still be guarded against.

I did not add checks for the range of x1 and x2 because they are generated by DSA_NewRandom in Softoken and DSA_NewRandom guarantees its output to be in the desired range.

Comment 34

[Robert Relyea]

Comment on attachment 495213 [details] [diff] [review]
Patch for the stable branch that resolves the conflicts in ldvector.c, loader.h, loader.c

this patch is already in the branch.

Comment 35

[Robert Relyea]

Comment on attachment 496110 [details] [diff] [review]
Patch on top of checked-in code to check shared key s != 0 [checked in]

r+ rrelyea

Comment 36

[Robert Relyea]

Comment on attachment 495175 [details] [diff] [review]
Tests for J-PAKE FreeBL in bltest (bltest -J) (v2)

This isn't a full review, but there are a few things that would be good to change:

1) It would be good politic to remove variable names like openssl_generated. (even better politic to actually generate them with NSS (there should be functions to generate pqg parameters for you.

2) bltest has a very nice facility to read base64 encoded data from files.It would be good to recast this test so you can read the input from files. (you could also expand the test cases in the future easily. (see mozilla/security/nss/cmd/bltest/tests).

Doing that would allow you to just add an entry into mozilla/security/nss/tests/cipher/cipher.txt to add the tests to all.sh.

bob

Comment 37

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Comment on attachment 496110 [details] [diff] [review]
Patch on top of checked-in code to check shared key s != 0 [checked in]

attachment 496110 [details] [diff] [review] was checked into the trunk and NSS_3_12_BRANCH with commit meessage "Bug 609068: Implement J-PAKE in FreeBL, additional check that s != 0, r=rrelyea"

All 4.0-blocking patches for this bug have been checked in. The bug is open because I need to rewrite the tests but that part isn't going to block 4.0. I recommend removing the blocking flag.

Comment 38

[Philipp von Weitershausen [:philikon]]

Alternatively, this bug can be left as it is and RESOLVED FIXED and we make a new bug that depends on this bug?

Comment 39

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Taking Philipp's advice. The bug for the tests is bug 625456.