PGP choice of e.
Mark E. Shoulson
Hi, out there.
I'm not a regular reader of these groups, but I have had some interest in
cryptography for years. I was poking around with PGP and some programs
that use it, and came up with a question about a possible slight weakness.
I was hoping someone out there could tell me why this isn't a weakness. I
don't read the groups, as I said, so please at least CC a private email
message to me (shou...@cs.columbia.edu).
I understand the RSA method, which PGP uses for its public keys. The PGP
public key record contains n (the modulus) and e (the exponent) of a given
public key, obviously. In general, this should not give anyone any
information about the prime factorization of n, or phi(n), upon which the
security of RSA rests, since all that you really know from the fact that n
and e are used as keys is that e is relatively prime to phi(n), which
doesn't really tell you much about phi(n).
I recently found a perl script on the Web that extracts n and e from public
PGP keys, which was amusing. So I started extracting on the few keys I had
on my keyring. I noticed that every single one had e=17. It was some time
before I found one or two keys with e=19. It seemed strange that e should
always be the same number, and I figured it probably happened that PGP
would just look for the lowest usable e (i.e. the lowest number relatively
prime to phi(n)) above some lower limit. And sure enough, that's what it
does. But I realized that gives away more information. If you find a
public key with e=19 (unless the person who generated it tweaked PGP), then
you *KNOW* that phi(n) is a multiple of 17, something you would not have
otherwise known. (In fact you'll know at least that it's a multiple of 68,
since phi(n)=(p-1)*(q-1) and p and q are both odd, so it has to be a
multiple of 4. But you knew that). OK, that may not be a big help in
searching... or is it?
This is a pretty obvious conclusion. I have to believe that people thought
of this already and it's known not to be a problem. At least I hope so.
I'm hoping someone out there can explain to me *why* it isn't a problem.
Sorry for what may be a trivial question, but I'd like to know.
Thanks in advance
~mark
o o o o o o o o o o o o
o o o o o o o
o o o o o o o o o o o N2KOT
Mark E. Shoulson: shou...@cs.columbia.edu
Bryce Wilcox
So is someone going to respond to this guy's idea? I've been keeping
this post active for a week waiting for someone to respond to it. Here is
a reprint.
John Hemming (Chief Executive MarketNet )
>
>
> So is someone going to respond to this guy's idea? I've been keeping
> this post active for a week waiting for someone to respond to it. Here is
> a reprint.
>
> Mark E. Shoulson <@news.cs.columbia.edu> wrote:
> >on my keyring. I noticed that every single one had e=17. It was some time
> >before I found one or two keys with e=19. It seemed strange that e should
> >always be the same number, and I figured it probably happened that PGP
> >would just look for the lowest usable e (i.e. the lowest number relatively
> >prime to phi(n)) above some lower limit. And sure enough, that's what it
> >does. But I realized that gives away more information. If you find a
> >public key with e=19 (unless the person who generated it tweaked PGP), then
> >you *KNOW* that phi(n) is a multiple of 17, something you would not have
> >otherwise known.
denominator of 1. ie that you know not that phi(n) is a multiple of 17
but that it is not.
(In fact you'll know at least that it's a multiple of 68,
> >since phi(n)=(p-1)*(q-1) and p and q are both odd, so it has to be a
> >multiple of 4. But you knew that). OK, that may not be a big help in
> >searching... or is it?
Generally the RSA routines use either 3 or 0x10001 (Fermat's
4th No. (Fermat numbers are 2^2^n +1 eg 3,5,17,257,65537=0x10001)
This makes the public key calculation a lot faster.
Generally given that the modulus is a constant the public key calculation
takes a time proportional to the number of bits in the exponent for the
public key. This means, of course, that the private key calculation
takes longer.
The basic question, therefore, is whether it is easier to factor
n into p and q knowing that de = 1 mod (p-1)(q-1)
and that e is 17, 3, 19 or whatever. That does not imply
(p-1)(q-1) is a multiple of 17 (19,3 etc).
I can't see how it does, but then again I would not claim
to be omniscient in this area.
Michael Paul Johnson
>So is someone going to respond to this guy's idea? I've been keeping
>this post active for a week waiting for someone to respond to it. Here is
>a reprint.
>Mark E. Shoulson <@news.cs.columbia.edu> wrote:
>>
>>Hi, out there.
>>
>>I'm not a regular reader of these groups, but I have had some interest in
>>cryptography for years. I was poking around with PGP and some programs
>>that use it, and came up with a question about a possible slight weakness.
>>I was hoping someone out there could tell me why this isn't a weakness. I
>>don't read the groups, as I said, so please at least CC a private email
>>message to me (shou...@cs.columbia.edu).
>>
>>I understand the RSA method, which PGP uses for its public keys. The PGP
>>public key record contains n (the modulus) and e (the exponent) of a given
>>public key, obviously. In general, this should not give anyone any
>>information about the prime factorization of n, or phi(n), upon which the
>>security of RSA rests, since all that you really know from the fact that n
>>and e are used as keys is that e is relatively prime to phi(n), which
>>doesn't really tell you much about phi(n).
>>
>>I recently found a perl script on the Web that extracts n and e from public
>>PGP keys, which was amusing. So I started extracting on the few keys I had
>>on my keyring. I noticed that every single one had e=17. It was some time
>>before I found one or two keys with e=19. It seemed strange that e should
>>always be the same number, and I figured it probably happened that PGP
>>would just look for the lowest usable e (i.e. the lowest number relatively
>>prime to phi(n)) above some lower limit. And sure enough, that's what it
>>does. But I realized that gives away more information. If you find a
>>public key with e=19 (unless the person who generated it tweaked PGP), then
>>you *KNOW* that phi(n) is a multiple of 17, something you would not have
>>otherwise known. (In fact you'll know at least that it's a multiple of 68,
>>since phi(n)=(p-1)*(q-1) and p and q are both odd, so it has to be a
>>multiple of 4. But you knew that). OK, that may not be a big help in
>>searching... or is it?
>>
>>This is a pretty obvious conclusion. I have to believe that people thought
>>of this already and it's known not to be a problem. At least I hope so.
>>I'm hoping someone out there can explain to me *why* it isn't a problem.
>>Sorry for what may be a trivial question, but I'd like to know.
>>
Knowing e doesn't help you find d unless (1) you can factor very big
numbers quickly (not likely for 1024-bit numbers), (2) you happened to
generated the same e for the same modulus (even less likely than the
factoring problem due to the large number of choices for m), (3) you
figure out a way faster than factoring of computing the Euler Totient
function, or (4) the same plain text is RSA encrypted to more than one
recipient (not done in PGP ever, due to random padding added to the IDEA
session key). If this still bothers you, you can always generate a key
with a bigger e (which probably is safer against unforseen attacks, but
is slower to encrypt with). The clinically paranoid may generate keys
with the command line
pgp -kg 2048 128
This topic gets discussed periodically in alt.security.pgp.
___________________________________________________________
| |
|\ /| | | Michael Paul Johnson Colorado Catacombs BBS 303-772-1062 |
| \/ |o| | PO Box 1151, Longmont CO 80502-1151 USA Jesus is alive! |
| | | / _ | m...@csn.org aka m...@netcom.com m.p.j...@ieee.org |
| |||/ /_\ | ftp://ftp.csn.net/mpj/README.MPJ CIS: 71331,2332 |
| |||\ ( | ftp://ftp.netcom.com/pub/mp/mpj/README -. --- ----- .... |
| ||| \ \_/ | PGPprint=F2 5E A1 C1 A6 CF EF 71 12 1F 91 92 6A ED AE A9 |
|___________________________________________________________|
William Lorimer
Wilcox) wrote:
> So is someone going to respond to this guy's idea? I've been keeping
> this post active for a week waiting for someone to respond to it. Here is
> a reprint.
>
>
> Mark E. Shoulson <@news.cs.columbia.edu> wrote:
> >
> >Hi, out there.
*snip*
> >does. But I realized that gives away more information. If you find a
> >public key with e=19 (unless the person who generated it tweaked PGP), then
> >you *KNOW* that phi(n) is a multiple of 17, something you would not have
> >otherwise known. (In fact you'll know at least that it's a multiple of 68,
Some authorities insist (others merely suggest) that both p and q should
be "strong primes", i.e. primes where both p-1 and q-1 have at least one
large factor. Many key generating algorithms start by generating, say, a
511-bit prime, doubling it, adding one, and seeing if the resulting
512-bit number is also prime. I don't know if PGP does this. Schneier
seems to think that "strong primes" are over-rated.
You may want to try the following experiment. Generate keys at random, PGP
will display the secret key information, until you get one where e=19.
Then test your hypothesis to see if either p-1 or q-1 is divisible by 17.
If not, then your observation would be a non-starter.
Does anyone know if PGP uses "strong primes"?
--
WR Lorimer
(I apologize if the above questions have already been addressed.)
"For lust of knowing what should not be known\We take the Golden Road to Samarkand." J. Elroy Flecker
Mark Henderson
>>cryptography for years. I was poking around with PGP and some programs
>>that use it, and came up with a question about a possible slight weakness.
>>I was hoping someone out there could tell me why this isn't a weakness. I
>>don't read the groups, as I said, so please at least CC a private email
>>message to me (shou...@cs.columbia.edu).
>>I recently found a perl script on the Web that extracts n and e from public
>>PGP keys, which was amusing. So I started extracting on the few keys I had
>>on my keyring. I noticed that every single one had e=17. It was some time
>>before I found one or two keys with e=19. It seemed strange that e should
>>always be the same number, and I figured it probably happened that PGP
>>would just look for the lowest usable e (i.e. the lowest number relatively
>>prime to phi(n)) above some lower limit.
By default, PGP uses to lowest usable e >= 17 (after choosing the primes,
remember that e and phi(n) must be relatively prime).
You can change this, by changing the initial value of ebits (the
default is ebits = 5) from the command line, when generating your
key.
e.g.
pgp -kg 1024 17
will generate keys which (almost always) have e = 65537.
There are some general problems with RSA with very small exponents
(e=3), that probably don't make much difference in the PGP case
anyway. I'd certainly recommend using ebits = 17 (i.e. e>=65537),
unless performance of the encryption operation is very important. I
think it is safe to dismiss me as paranoid :-)
Generally numbers with lots of zeros in their binary expansion are
faster for modular exponentiation and hence encryption. So, values of
e of the form 2^k + 1, are a good choice from a performance
persepective.
--
Mark Henderson -- m...@squirrel.com, ma...@wimsey.bc.ca, hend...@netcom.com
PGP 1024/C58015E3 fingerprint=21 F6 AF 2B 6A 8A 0B E1 A1 2A 2A 06 4A D5 92 46
RIPEM 2.1 MD5OfPublicKey: 089D04AC278EFE21F73C4C2B50A0A072
cryptography archive maintainer -- anon ftp to ftp.wimsey.bc.ca:/pub/crypto
D. Dale Gulledge
I understand the RSA method, which PGP uses for its public keys. The PGP
public key record contains n (the modulus) and e (the exponent) of a given
public key, obviously. In general, this should not give anyone any
information about the prime factorization of n, or phi(n), upon which the
security of RSA rests, since all that you really know from the fact that n
and e are used as keys is that e is relatively prime to phi(n), which
doesn't really tell you much about phi(n).
I recently found a perl script on the Web that extracts n and e from public
PGP keys, which was amusing. So I started extracting on the few keys I had
on my keyring. I noticed that every single one had e=17. It was some time
before I found one or two keys with e=19. It seemed strange that e should
always be the same number, and I figured it probably happened that PGP
would just look for the lowest usable e (i.e. the lowest number relatively
prime to phi(n)) above some lower limit. And sure enough, that's what it
does. But I realized that gives away more information. If you find a
public key with e=19 (unless the person who generated it tweaked PGP), then
you *KNOW* that phi(n) is a multiple of 17, something you would not have
otherwise known. (In fact you'll know at least that it's a multiple of 68,
since phi(n)=(p-1)*(q-1) and p and q are both odd, so it has to be a
multiple of 4. But you knew that). OK, that may not be a big help in
searching... or is it?
There are two possible other security holes caused by this. The first is not
currently a problem. Simply put, since the ciphertext is the plaintext raised
to the e power, and the ciphertext is of a known length (209 bits if I read
the source correctly: Session key, IV, checksum and ID byte (of which only the
low order bit is on)), we can calculate the minimum exponent for any given
modulus length that will guarantee that we exceed the modulus by a comfortable
margin.
Modulus size Smallest exponent to exceed it (not necessarily prime)
512 3
1024 5
2048 10
4096 20 (Note a security hole here if e is still 17)
8192 40
I spent several hours over the weekend investigating precisely this problem.
I read the source code because if only the session key (128 bits) were
encrypted with RSA, roughly 1 in every 200 messages would effectively be
transmitted in the clear because the session key taken to the 17th power would
be less than the modulus for session keys with the first 7-8 bits 0. Adding
the ID byte on the front, as well as the IV and a checksum at the end solves
that problem.
The other problem is still a problem regardless of the modulus size. When
everyone shares the same value for e, is it cost effective to start generating
all of the possible session key values, raising them to the e power and
storing them? Obviously the answer is no because of the size of the key
space. However, it is possible to generate a large number of them and match
some messages' session keys. Because of the widely shared value of e, there
may be a decent payoff in doing those calculations in bulk, I think.
- Dale
--
'95 bicycle commuting season: 25 days, 86 km (I hate this weather).
Accidents: 1 minor (bent rear rim). Max speed this season: 67.5 kph
--
d...@cci.com, D. Dale Gulledge, Software Engineer, Northern Telecom,
Directory & Operator Services, 97 Humboldt St., Rochester, NY 14609
Hal
of 2 is 16 and the first e tried is 17. It checks to see if GCD(e, phi)
is 1 which ensures that e has a multiplicative inverse mod phi. If not,
it adds 2 to e and tries again, continuing until it finds a good one.
Therefore, as suggested, an e of 19 can only be produced by an unmodified
PGP if phi is a multiple of 17. (And since 17 is prime this can only be
true if at least one of p-1 or q-1 is a multiple of 17.) Similarly an e
of 21 implies that phi is a multiple of 17*19, etc.
I believe there are some factoring algorithms which work if p-1 or q-1
have many small factors, but for random p and q they are not competitive
with the best known algorithms which search for solutions to x^2=y^2 mod
n and AFAIK can't benefit from knowledge of factors of phi.
It would be interesting for someone to scan the big key rings and find
what values of e are farthest above the next lower power of 2.
This is probably not a big deal for PGP, but for some other
applications it could be more important. For fun I once designed (but
never implemented) an electronic cash system similar to the "magic
money" that was done by Pr0duct Cypher based on the ideas of David
Chaum. Different denominations would be represented by different
exponents, all with the same modulus. You would want the exponents to
be small for efficiency, and there could be a couple of dozen of them.
If you just started with e=3 and worked your way up, skipping those
exponents for which gcd(e,phi)!=1, you could actually end up giving away
quite a bit of information about the factorization of phi by publishing
these exponents. So I was going to start with a larger number for the
initial e and use primes for e's, in which case the chances of phi being
a multiple of e would be very low. Another solution would be to use
strong primes for p and q so that essentially all odd e's would work.
Hal Finney
hfi...@shell.portal.com
Francis Litterio
> You may want to try the following experiment. Generate keys at random, PGP
> will display the secret key information, until you get one where e=19.
> Then test your hypothesis to see if either p-1 or q-1 is divisible by 17.
Actually, his hyposthesis was that (p-1)(q-1) was divisible by 17, not
that either p-1 or q-1 was divisible by 17.
If (p-1)(q-1) was divisible by 17, would that actually help anyone
factor pq?
And how do you get PGP to tell you the values of p and q? p and q
certainly don't exist in the secring.pgp file (even in encrypted
form). Can PGP be made to display them during key generation?
--
Francis Litterio fr...@centerline.com
02 37 DF 6C 66 43 CD 2C http://draco.centerline.com:8080/~franl/
10 C8 B5 8B 57 34 F3 21 PGP-encrypted email preferred
Mike Oliver
>Methinks this problem would have been easily circumvented by padding
>the plaintext with random garbage up to the length of the modulus
>before encrypting.
It *is* so padded, or maybe you knew that?
Doesn't *anybody* read the docs?
Harald Hanche-Olsen
| There are two possible other security holes caused by this. The
| first is not currently a problem. Simply put, since the
| ciphertext is the plaintext raised to the e power, and the
| ciphertext is of a known length (209 bits if I read the source
| correctly: Session key, IV, checksum and ID byte (of which only
| the low order bit is on)), we can calculate the minimum exponent
| for any given modulus length that will guarantee that we exceed
| the modulus by a comfortable margin.
|
| Modulus size Smallest exponent to exceed it (not necessarily prime)
|
| 512 3
| 1024 5
| 2048 10
| 4096 20 (Note a security hole here if e is still 17)
| 8192 40
Methinks this problem would have been easily circumvented by padding
the plaintext with random garbage up to the length of the modulus
before encrypting.
- Harald
Harald Hanche-Olsen
|
| In article <1995-05-03.1...@romberg.imf.unit.no> han...@imf.unit.no (Harald Hanche-Olsen) writes:
|
| >Methinks this problem would have been easily circumvented by padding
| >the plaintext with random garbage up to the length of the modulus
| >before encrypting.
|
| It *is* so padded, or maybe you knew that?
That is good to hear. No, I did not know that.
| Doesn't *anybody* read the docs?
Never looked at them. I read the original post to mean that there was
no padding. Indeed D. Dale Gulledge wrote
: Simply put, since the ciphertext is the plaintext raised to the e
: power, and the ciphertext is of a known length (209 bits if I read
: the source correctly: Session key, IV, checksum and ID byte (of
: which only the low order bit is on)) [...]
but maybe he did not read the the source correctly, or maybe I
misunderstood him.
- Harald
Kamil Kukura
: By default, PGP uses to lowest usable e >= 17 (after choosing the primes,
: remember that e and phi(n) must be relatively prime).
: You can change this, by changing the initial value of ebits (the
: default is ebits = 5) from the command line, when generating your
: key.
: e.g.
: pgp -kg 1024 17
: will generate keys which (almost always) have e = 65537.
: There are some general problems with RSA with very small exponents
: (e=3), that probably don't make much difference in the PGP case
: anyway. I'd certainly recommend using ebits = 17 (i.e. e>=65537),
: unless performance of the encryption operation is very important. I
: think it is safe to dismiss me as paranoid :-)
Bruce Schneier in his "Apllied cryptography" in section where he describes
possible attacks on RSA presents that someone has demonstrated how to reveal
"d" when "e" is as low as p*q/4. However, there's nothing about how does it
relate to fact whether or not p,q are strong primes.
(Q: if p and (p-1)/2 are both primes, does it mean p-1 has no small factors?)
: Generally numbers with lots of zeros in their binary expansion are
: faster for modular exponentiation and hence encryption. So, values of
: e of the form 2^k + 1, are a good choice from a performance
: persepective.
Well, in fact "e" just determines how many times the operation M^2 mod p*q
will be performed. The only operation it takes place in is e/2 that is 1
bit-rotation to right.
: --
: Mark Henderson -- m...@squirrel.com, ma...@wimsey.bc.ca, hend...@netcom.com
: PGP 1024/C58015E3 fingerprint=21 F6 AF 2B 6A 8A 0B E1 A1 2A 2A 06 4A D5 92 46
: RIPEM 2.1 MD5OfPublicKey: 089D04AC278EFE21F73C4C2B50A0A072
: cryptography archive maintainer -- anon ftp to ftp.wimsey.bc.ca:/pub/crypto
--
-- Kamil....@tuke.sk
-- --------------------
-- MIME, ISO-Latin-2
--