Need a way to expand partial private keys.

RESOLVED FIXED in 3.12.9

Status

P1
enhancement
RESOLVED FIXED
8 years ago
8 years ago

People

(Reporter: rrelyea, Assigned: rrelyea)

Tracking

3.12.6
3.12.9

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

8 years ago
Some systems store private keys with only some of the components:
   Modulus, public exponent, private exponent.
   Modulus, public exponent, prime1,
   prime1, prime2, public exponent

etc.

In freebl, we know how to take prime1, prime2, and public exponent and generate all the rest of the parameters. That same code can easily work with the private exponent instead.

Calculating prime1 and prime2 from the appropriate fraction of known components is possible. It should be relatively easy to recreate a private key from

1) one of the exponents (public or private).
2) two more of the remaining non-crt components (prime1, prime2, modulus, private exponent, public exponent).
(Assignee)

Comment 1

8 years ago
Created attachment 462625 [details] [diff] [review]
Populate an RSA Key with only a few components.

Most of the description can be found in the comments in front of RSAPopulate and the function go get 2 primes from 2 exponents and a either a prime or a modulus
(Assignee)

Updated

8 years ago
Assignee: nobody → rrelyea
(Assignee)

Comment 2

8 years ago
Created attachment 465507 [details] [diff] [review]
Populate an RSA Key with only a few components. Patch 2 (with NSS level test case).

Wtc It's a bit of a long patch, but other than the test program, It has some long extensive comments. There's a lot of algebra going on here;).

One area to weigh in on particularly is whether or not we should restrict or disallow one particular case: pub exp, priv exp, and one prime. It turns out that this is not sufficient information to guarantee reconstruction of the original key. It's possible to construct a key that is valid, but not the same (that is the new key has the same public exp, private exp, and prime as the original, but the second prime and modulus are different). I see this empirically pretty often (1 out of 100 times for 1024 bit keys). In the second key the prime has usually switched places in the prime order (that is if the prime for the original key was prime2, it may be prime1 in the reconstructed key). So restricting primes to their "proper" order may fix the problem.

If I know that the primes are all strong primes (p-1)/2 and (q-1)/2 are primes, then I can guarantee I get the right key. We don't require strong primes for these RSA primes, however (or I would never be seeing these incorrrect keys).

bob
Attachment #462625 - Attachment is obsolete: true
Attachment #465507 - Flags: review?(wtc)
(Assignee)

Comment 3

8 years ago
BTW the case I needed immediately were:

generate the private key from: pub exponent, modulus, one prime.

The case I think would be useful as well is:

generate the private key from: pub exponent, priv exponent, and modulus

bob
Bob asked "whether or not we should restrict or disallow one particular case: 
pub exp, priv exp, and one prime."

IMO, we must disallow it.  I think this won't be a serious limitation in 
practice.  I think it's rare to not have the complete public key, which 
gives us the modulus.
(Assignee)

Comment 5

8 years ago
Nelson, good input.

I'm thinking it's probably best to do so. As I think about it more, two different moduluses with the same prime factor can be used to find that factor using a LCD algorithm. Probably best not to give the user that kind of rope.

Do you think it's OK to restrict it to keys with strong prime factors (we would fail if (p-1)/2 is not prime or we could not find a (q-1)/2 which was prime).

I believe we can't get false positives out of this. Obviously we can detect if the prime given to us is strong. If it happens to be strong, but it's pair isn't, then we will fail to find q such that (q-1)/2. This is because for our discovered (q-1), it has only 2 factors (q-1)/2 and 2. The only source of factors for (q-1) are phi (p-1)(q-1) and k (which is less than our public exponent). We already limit e to 20 bits in this case, which means for it to provide (q-1)/2, the key would have have an 80 bit modulus (much to small to be useful safe on it's own).

Of course I don't have a use case for this, so maybe it's better to just reject it. I just like the symmetry of having it if we can do it safely.

bob
Bob, 
You used the term "strong prime" but gave the definition of "safe prime".
I'll assume your definition states what you really wanted, a safe prime.

I think you're asking if it's acceptable to implement the algorithm for
"pub exp, priv exp, and one prime" (Let's call them 'e', 'd' and 'P') inputs 
for the case where the following additional restrictions hold true:

a) the one given prime P is a "safe" prime (that is such that (P-1)/2 is prime)
and 

b) we can find a second prime Q, such that the two exponents (d and e) have the desired relationship when used with the modulus N formed as the product of the given P and the found prime Q, and

c) the found prime 'Q' is also a safe prime, and 
d) the found prime 'Q' has the same length as 'P'.

If we ignore conditions 'c' and 'd', I'm pretty sure that there's commonly  more than one prime Q that can be found that satisfies condition 'b'.  Stated probabilistically, I'm pretty sure that for any given e, d, and safe prime P,
there is a high probability that multiple primes Q1, Q2 ... can be found 
that satisfy condition b.  Adding conditions c and d reduces the probability considerably.  

But we're trying to re-create a second prime 'Q' that has been created before.
In general, do we have any reason to believe that the original prime Q was 
chosen to be "safe", or to be the same length as 'P'?  Being the same length 
as 'P' is perhaps quite likely, but being safe is not likely, IMO.  We don't 
require that P and Q be safe primes in our own RSA key gen code, for example,
so why would we imagine that others do that?  

If we know that two primes Q can be found that satisfy condition B, one of 
which is safe and one of which is not, have we any reason to believe that 
the original creator of the private key used one rather than the other?
(Assignee)

Comment 7

8 years ago
Yes, I mean safe primes, (I was using Schneier's definition of strong prime, which includes the requirement that (p-1)/2 is also prime).

There are RSA algorithms that require the primes to be safe primes.

The current algorithm enforces b and d. I am suggesting adding a and c.

If q is a safe prime, then it's impossible to satisfy condition b and d simultaneously and not have the correct q. (That is if you find q such that q is a safe prime, you know that q is the only possible prime that can satisfy the required conditions):

Condition (b) is the equation d*e-1 = k*(q-1)(p-1). k is an integer less than the smaller of d or e (in our case smaller than e) [this follows directly from the requirement that e*d mod (q-1)(p-1) = 1].  The current algorithm is restricted to e < 20 bits (otherwise finding k becomes computationally difficult using the naive algorithm we are currently using). Our algorithm is to find a k that divides k*(q-1)*(p-1) evenly, the result is divisible by 4 (since both p-1 and q-1 must be even), is the right size in bits (2*length of p), and p-1 divides evenly into it. In order for this to give us a different value of q is for q-1 and k to swap integer factors. If q is a safe prime, then it q-1 has factors 2 an (q-1)/2. k is too small to swap (q-1)/2, and 2 can only swap with 3 (or our size will be wrong). If (q-1)/2 is prime, than if 2 and 3 swap, the result is no longer even (thus the *4 check will fail). k is too small to swap with (q-1)/2 (k is size of 20 bits, if q-1 were that size, the RSA key would be 40 bits long, which is way too weak).

Note 1: the above is true whether or not (p-1)/2 is prime. I would only do the former check to blow out of keys that clearly are not using safe primes. (This also means if I find any q that does not satisfy (q-1)/2 is prime, I know I won't find a q that does and I can end there as well).

So the question is, what definition of strong prime does ANSI X9.31 require. If it requires that (prime-1)/2 is also prime, then this may be reasonable. If not, then it's probably useless. If p and q are strong, but do not require (prime-1)/2 to be prime, then it is again possible for k and (q-1) to swap small factors.

Note 2: This whole discussion has made me realize that if we keep the single prime case, I can speed up the processing by dividing kphi by (p-1) immediately. This shrinks the size of big num operations by half, and eliminates the need to divide p-1 out later. Unfortunately it doesn't solve the problem of multiple possible values of q.
(Assignee)

Comment 8

8 years ago
OK, I have what I think is a better solution.

for the e, d, and prime case. I don't stop after I find the first prime(q), that satisfies the condition:

   (ed +1)/(p-1) = k * (q-1)  where e, e, and p are given, k is an integer and
                              q is prime and the same length as p.

But continue on looking for more primes that may also meet this condition. If I find a second prime, then I will return an error (rather than potentially returning the wrong key).

This means the function *could* fail, but if it succeeds you know you have the same key as the original.

bob
> if it succeeds you know you have the same key as the original.

Are you actually proposing to do an EXHAUSTIVE search through the possible 
space of primes of the same size?  Anything less than an exhaustive search
does NOT assure you that you "have the same same key as the original", IINM,
and an exhaustive search is clearly impractical.
(Assignee)

Comment 10

8 years ago
> Are you actually proposing to do an EXHAUSTIVE search through the possible 
> space of primes of the same size?  Anything less than an exhaustive search
> does NOT assure you that you "have the same same key as the original", IINM,
> and an exhaustive search is clearly impractical.

yes and no. I'm doing an EXHAUSTIVE search for all possible k which divides k*(q-1).  I know (ed+1)/(p-1) so I can calculate k*(q-1) exactly. k is guaranteed to be less then 20 bits, so k*(q-1) is going to be at most key_size/2+20 bits. On my machine I can find all k's which divide k*(q-1) on a 1024 bit key and check the resulting q for proper order and primality in less than second.

So I'm doing an exhaustive search for all the primes that could satisfy the equation, but not my cycling through those primes, only by checking every candidate value for primality. I can exhaustively check all the candidates (which is a must smaller space than the possible prime space). If only one matches, then I *MUST* have the correct key.

bob
(Assignee)

Comment 11

8 years ago
Created attachment 471583 [details] [diff] [review]
Populate an RSA Key with only a few components. Patch 3 (fail if more than one key meets the criteria).
Attachment #465507 - Attachment is obsolete: true
Attachment #471583 - Flags: review?(wtc)
Attachment #465507 - Flags: review?(wtc)
(Assignee)

Comment 12

8 years ago
Comment on attachment 471583 [details] [diff] [review]
Populate an RSA Key with only a few components. Patch 3 (fail if more than one key meets the criteria).

Adding Brian so he can find this bug.
Attachment #471583 - Flags: superreview?(bsmith)

Updated

8 years ago
Status: NEW → ASSIGNED
Priority: -- → P1
Target Milestone: --- → 3.12.9
(Assignee)

Updated

8 years ago
Attachment #471583 - Flags: superreview?(bsmith) → superreview?(emaldona)

Comment 13

8 years ago
Comment on attachment 471583 [details] [diff] [review]
Populate an RSA Key with only a few components. Patch 3 (fail if more than one key meets the criteria).

The patch does not apply cleanly with the current sources. A few files have changed since it was submitted. Since the target is 3.12.9, I tried to apply it in the NSS_3_12_BRANCH with the following results:
$ cd mozilla/security/nss/
$ patch -p0 < ../../../patch.tpm.2 
patching file cmd/bltest/blapitest.c
patching file cmd/rsapoptst/Makefile
patching file cmd/rsapoptst/manifest.mn
patching file cmd/rsapoptst/rsapoptst.c
patching file lib/freebl/blapi.h
patching file lib/freebl/ldvector.c
Hunk #1 FAILED at 257.
1 out of 1 hunk FAILED -- saving rejects to file lib/freebl/ldvector.c.rej
patching file lib/freebl/loader.c
Hunk #1 succeeded at 1688 with fuzz 2 (offset -9 lines).
Hunk #2 succeeded at 1699 with fuzz 2 (offset -18 lines).
patching file lib/freebl/loader.h
Hunk #1 FAILED at 551.
1 out of 1 hunk FAILED -- saving rejects to file lib/freebl/loader.h.rej
patching file lib/freebl/rsa.c
patching file lib/softoken/pkcs11.c
Hunk #1 succeeded at 969 (offset -2 lines).
Hunk #2 succeeded at 985 (offset -2 lines).
Hunk #3 succeeded at 1862 (offset -2 lines).
Attachment #471583 - Flags: superreview?(emaldona) → superreview-

Comment 14

8 years ago
Indeed, it's a large patch. But that not the big issue, the big one is plowing through rsa_get_primes_from_exponents(). The code seems to do what you state in the comments. Those comments indicate quite a few assumptions that I'm slowly getting my head around.

Updated

8 years ago
Attachment #471583 - Flags: superreview- → superreview?(emaldona)

Comment 15

8 years ago
In rsa_get_primes_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
+			      mp_int *n, PRBool hasModulus, 
+			      unsigned int keySizeInBits)
in line 1502, where you wrote
+	/* calculate sqrt(s*s-n) */
you probably meant
+	/* calculate sqrt(s/2*s/2-n) */

rsa_keygen_from_prime ther is a stray printf in
     CHECK_MPI_OK( mp_mul(p, q, &n) );
     /*     verify that the modulus has the desired number of bits */
     if ((unsigned)mpl_significant_bits(&n) != keySizeInBits) {
+	printf("failed keySizeInBits check =%d, actual=%d\n", keySizeInBits,
+		mpl_significant_bits(&n));
 	PORT_SetError(SEC_ERROR_NEED_RANDOM);
that you want to remove

In @@ -279,7 +305,8 @@ RSA_NewKey(int keySizeInBits, SECItem *p
Minor stylistic suggestion: changing
	rv = rsa_build_from_primes(&p, &q, &e, PR_FALSE, &d, PR_TRUE, 
				   key, keySizeInBits);
to
	rv = rsa_build_from_primes(&p, &q, 
				   &e, PR_FALSE,/* needPublicExponent=false */
				   &d, PR_TRUE, /* needPrivateteExponent=true*/
				   key, keySizeInBits);
does helps the reader.

From my code inspection I believe that rsa_build_from_primes behaves as the old one does given the normal usage. 

Now PK11_CreateGenericObject has acquired new features, not that anyone will notice unless they know about this to try it things out. PK11_CreateGenericObject is not documented and it doesn't even show in the table in http://www.mozilla.org/projects/security/pki/nss/ref/nssfunctions.html#crypto. I wonder why?

The new rsapopt test tool is not being built, shouldn't we build it.
(Assignee)

Comment 16

8 years ago
> in line 1502, where you wrote
> +    /* calculate sqrt(s*s-n) */
> you probably meant
> +    /* calculate sqrt(s/2*s/2-n) */

yeah, I tried to weazle it with something about substituting s/2 for s*s saves a some divides and multiplies, but the original is still wrong in that case it should either be sqrt(s/2*s/2-n) or sqrt(s*s-4*n)[/2] which, of course, are equivalent.

I'll make that change

> +    printf("failed keySizeInBits check =%d, actual=%d\n", keySizeInBits,
> +        mpl_significant_bits(&n));

good catch. you are right, I want to remove that printf.

> Minor stylistic suggestion: changing

I'll make that change.

> Now PK11_CreateGenericObject has acquired new features
Not so much as C_CreateObject now works with a reduced set of parameters for private keys.

> The new rsapopt test tool is not being built, shouldn't we build it.

I wasn't planning on it, but we could.

bob

Comment 17

8 years ago
spellings: s/combiations/combinations/, s/alocated/allocated/

Comment 18

8 years ago
Comment on attachment 471583 [details] [diff] [review]
Populate an RSA Key with only a few components. Patch 3 (fail if more than one key meets the criteria).

r+ from me.
Attachment #471583 - Flags: superreview?(emaldona) → superreview+
(Assignee)

Comment 19

8 years ago
NSS 3.12 Branch checkin...

Checking in cmd/bltest/blapitest.c;
/cvsroot/mozilla/security/nss/cmd/bltest/blapitest.c,v  <--  blapitest.c
new revision: 1.59.2.1; previous revision: 1.59
done
RCS file: /cvsroot/mozilla/security/nss/cmd/rsapoptst/Attic/Makefile,v
done
Checking in cmd/rsapoptst/Makefile;
/cvsroot/mozilla/security/nss/cmd/rsapoptst/Attic/Makefile,v  <--  Makefile
new revision: 1.1.2.1; previous revision: 1.1
done
RCS file: /cvsroot/mozilla/security/nss/cmd/rsapoptst/Attic/manifest.mn,v
done
Checking in cmd/rsapoptst/manifest.mn;
/cvsroot/mozilla/security/nss/cmd/rsapoptst/Attic/manifest.mn,v  <--  manifest.mn
new revision: 1.1.2.1; previous revision: 1.1
done
RCS file: /cvsroot/mozilla/security/nss/cmd/rsapoptst/Attic/rsapoptst.c,v
done
Checking in cmd/rsapoptst/rsapoptst.c;
/cvsroot/mozilla/security/nss/cmd/rsapoptst/Attic/rsapoptst.c,v  <--  rsapoptst.c
new revision: 1.1.2.1; previous revision: 1.1
done
Checking in lib/freebl/blapi.h;
/cvsroot/mozilla/security/nss/lib/freebl/blapi.h,v  <--  blapi.h
new revision: 1.33.22.1; previous revision: 1.33
done
Checking in lib/freebl/ldvector.c;
/cvsroot/mozilla/security/nss/lib/freebl/ldvector.c,v  <--  ldvector.c
new revision: 1.21.22.2; previous revision: 1.21.22.1
done
Checking in lib/freebl/loader.c;
/cvsroot/mozilla/security/nss/lib/freebl/loader.c,v  <--  loader.c
new revision: 1.44.22.1; previous revision: 1.44
done
Checking in lib/freebl/loader.h;
/cvsroot/mozilla/security/nss/lib/freebl/loader.h,v  <--  loader.h
new revision: 1.26.22.1; previous revision: 1.26
done
Checking in lib/freebl/rsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/rsa.c,v  <--  rsa.c
new revision: 1.39.22.1; previous revision: 1.39
done
Checking in lib/softoken/pkcs11.c;
/cvsroot/mozilla/security/nss/lib/softoken/pkcs11.c,v  <--  pkcs11.c
new revision: 1.167.6.2; previous revision: 1.167.6.1
done
bobs-laptop(146)
(Assignee)

Updated

8 years ago
Attachment #471583 - Flags: review?(wtc)
(Assignee)

Comment 20

8 years ago
Trunk/Tip checkin:

Checking in cmd/bltest/blapitest.c;
/cvsroot/mozilla/security/nss/cmd/bltest/blapitest.c,v  <--  blapitest.c
new revision: 1.61; previous revision: 1.60
done
Checking in cmd/rsapoptst/Makefile;
/cvsroot/mozilla/security/nss/cmd/rsapoptst/Makefile,v  <--  Makefile
new revision: 1.2; previous revision: 1.1
done
Checking in cmd/rsapoptst/manifest.mn;
/cvsroot/mozilla/security/nss/cmd/rsapoptst/manifest.mn,v  <--  manifest.mn
new revision: 1.2; previous revision: 1.1
done
Checking in cmd/rsapoptst/rsapoptst.c;
/cvsroot/mozilla/security/nss/cmd/rsapoptst/rsapoptst.c,v  <--  rsapoptst.c
new revision: 1.2; previous revision: 1.1
done
Checking in lib/freebl/blapi.h;
/cvsroot/mozilla/security/nss/lib/freebl/blapi.h,v  <--  blapi.h
new revision: 1.39; previous revision: 1.38
done
Checking in lib/freebl/ldvector.c;
/cvsroot/mozilla/security/nss/lib/freebl/ldvector.c,v  <--  ldvector.c
new revision: 1.26; previous revision: 1.25
done
Checking in lib/freebl/loader.c;
/cvsroot/mozilla/security/nss/lib/freebl/loader.c,v  <--  loader.c
new revision: 1.50; previous revision: 1.49
done
Checking in lib/freebl/loader.h;
/cvsroot/mozilla/security/nss/lib/freebl/loader.h,v  <--  loader.h
new revision: 1.31; previous revision: 1.30
done
Checking in lib/freebl/rsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/rsa.c,v  <--  rsa.c
new revision: 1.41; previous revision: 1.40
done
Checking in lib/softoken/pkcs11.c;
/cvsroot/mozilla/security/nss/lib/softoken/pkcs11.c,v  <--  pkcs11.c
new revision: 1.172; previous revision: 1.171
done
Status: ASSIGNED → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.