fermat primes and dnssec-keygen bug?

[Paul Wouters]

See part of the dicsussion Miek and I had at the golang group:

http://code.google.com/p/go/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Status%20Stars%20Priority%20Owner%20Reporter%20Summary&groupby=&sort=&id=3161

The bug seems to be that dnssec-keygen upgraded the fermat prime that
is used per default from F0 to F4, but did not change that "-e" would
get you the next fermat number. The result is that people who upgrade
bind and don't notice this changed behaviour are not changing their
scripts that explicitely use "-e".

I would recommend that dnssec-keygen starts ignoring the "-e" parameter
that everyone has put in their scripts to prevent exponent 3 keys, who
are not getting keys with exponent 4294967296 + 1 (F5)

Alternatively, if this is done on purpose, I guess we should all
migrate the 64 bit machines :)

You can detect these starts, as they start with BQE

Paul

[Spain, Dr. Jeffry A.]

> I would recommend that dnssec-keygen starts ignoring the "-e" parameter that everyone has put in their scripts to prevent exponent 3 keys, who are not getting keys with exponent 4294967296 + 1 (F5)

> Alternatively, if this is done on purpose, I guess we should all migrate the 64 bit machines :)

As background, see the discussion of Fermat Numbers, e.g. F4 and F5, at http://en.wikipedia.org/wiki/Fermat_number. See also the role of the exponent in RSA public-key cryptography at http://en.wikipedia.org/wiki/RSA_(algorithm).

This is interesting, if I correctly understand your point, but it appears that dnssec-keygen computes F5 differently than you do in your example in http://code.google.com/p/go/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Status%20Stars%20Priority%20Owner%20Reporter%20Summary&groupby=&sort=&id=3161.

In your example:
pubkey := new(rsa.PublicKey)
pubkey.N = big.NewInt(0)
pubkey.E = 4294967296 + 1
which results in 32-bit integer overflow.

In bind-9.9.0/lib/dns/opensslrsa_link.c, starting at line 750:
if (exp == 0) {
/* RSA_F4 0x10001 */
BN_set_bit(e, 0);
BN_set_bit(e, 16);
} else {
/* F5 0x100000001 */
BN_set_bit(e, 0);
BN_set_bit(e, 32);
}
where exp is nonzero if option -e is set in the original call to dnssec-keygen and e is a BIGNUM pointer initialized as 'BIGNUM *e = BN_new();'. I would surmise that e is not subject to integer overflow in its representation of F5. The BIGNUM type is a component of OpenSSL. See http://www.openssl.org/docs/crypto/bn.html. According to this document it supports arbitrary precision integer arithmetic subject only to memory allocation limits with no indication of a dependency on 32-bit or 64-bit CPU architecture. If there is a problem, I think it would be with OpenSSL rather than dnssec-keygen.

Jeffry A. Spain
Network Administrator
Cincinnati Country Day School

[Miek Gieben]

[ Quoting <spa...@countryday.net> at 04:07 on Mar 7 in "RE: fermat primes an..." ]

> > I would recommend that dnssec-keygen starts ignoring the "-e" parameter that everyone has put in their scripts to prevent exponent 3 keys, who are not getting keys with exponent 4294967296 + 1 (F5)
>
> > Alternatively, if this is done on purpose, I guess we should all migrate the 64 bit machines :)
>

> This is interesting, if I correctly understand your point, but it appears that dnssec-keygen computes F5 differently than you do in your example in http://code.google.com/p/go/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Status%20Stars%20Priority%20Owner%20Reporter%20Summary&groupby=&sort=&id=3161.
>
> In your example:
> pubkey := new(rsa.PublicKey)
> pubkey.N = big.NewInt(0)
> pubkey.E = 4294967296 + 1
> which results in 32-bit integer overflow.
>
> In bind-9.9.0/lib/dns/opensslrsa_link.c, starting at line 750:
> if (exp == 0) {
> /* RSA_F4 0x10001 */
> BN_set_bit(e, 0);
> BN_set_bit(e, 16);
> } else {
> /* F5 0x100000001 */
> BN_set_bit(e, 0);
> BN_set_bit(e, 32);
> }

Its not about integer overflow, it's about the fact that F5
does not add to the security, but does use up a lot of CPU cycles.

grtz Miek

[Chris Thompson]

On Mar 6 2012, Paul Wouters wrote:

>See part of the dicsussion Miek and I had at the golang group:
>
>http://code.google.com/p/go/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Status%20Stars%20Priority%20Owner%20Reporter%20Summary&groupby=&sort=&id=3161
>
>The bug seems to be that dnssec-keygen upgraded the fermat prime that
>is used per default from F0 to F4, but did not change that "-e" would
>get you the next fermat number.

This is wrong (although I have seen the same thing stated in a number
of other places). When the default public exponent was changed from
3 to 2^16+1 (change 2088) the one selected by -e was changed from
2^16+1 to 2^30+3 ... *not* 2^32+1. And so it remains today.

As it happens, 2^30+3 is prime while of course 2^32+1 is not, although
that isn't really an issue.

I believe that the DNSKEY records (e.g. in a few TLDs) that do use
2^32+1 as the public exponent come from HSMs, not from dnssec-keygen.

In any case, there is no "bug" involved in any of this, other than
in validating code that cannot cope with large exponents.

> The result is that people who upgrade
>bind and don't notice this changed behaviour are not changing their
>scripts that explicitely use "-e".
>

>I would recommend that dnssec-keygen starts ignoring the "-e" parameter
>that everyone has put in their scripts to prevent exponent 3 keys, who
>are not getting keys with exponent 4294967296 + 1 (F5)
>
>Alternatively, if this is done on purpose, I guess we should all
>migrate the 64 bit machines :)
>

>You can detect these starts, as they start with BQE

And you will find that the ones generated by "dnssec-keygen -e" start
BEAAAA...

My personal opinion is that we should stop worrying about people
using buggy pre-2006 versions of OpenSSL and go back to using RSA
public exponents of 3 again most of the time. I notice that this
is what VeriSign do for the DNSKEY records in "com", "net" & "edu".

--
Chris Thompson
Email: ce...@cam.ac.uk

[Bill Owens]

On Wed, Mar 07, 2012 at 12:13:35PM +0000, Chris Thompson wrote:
> This is wrong (although I have seen the same thing stated in a number
> of other places). When the default public exponent was changed from
> 3 to 2^16+1 (change 2088) the one selected by -e was changed from
> 2^16+1 to 2^30+3 ... *not* 2^32+1. And so it remains today.

...

> And you will find that the ones generated by "dnssec-keygen -e" start
> BEAAAA...

Umm, no:

[littledebian:~/dns] owens% dnssec-keygen -e example.com
Generating key pair....................................++++++ .............++++++
Kexample.com.+005+43304
[littledebian:~/dns] owens% cat Kexample.com.+005+43304.key
; This is a zone-signing key, keyid 43304, for example.com.
; Created: 20120307140855 (Wed Mar 7 09:08:55 2012)
; Publish: 20120307140855 (Wed Mar 7 09:08:55 2012)
; Activate: 20120307140855 (Wed Mar 7 09:08:55 2012)
example.com. IN DNSKEY 256 3 5 BQEAAAABw3A8Wji6BjyanbOXUtIH1UcroHZKh06qRKXASbxHAQHJogaw 6m2wYX77KvtzVSto/nbHXM/53Vbu/Ar8CAXC/+r/R5BOHw73qA12LqXr 7utMeLmBPjq4RUqluurlVTHt5/FD85tr0yr8mu7h39gVmMY0bnRpgx6p aj2zjpv3O3U=

The code definitely uses 2^32+1:

[littledebian:bind-9.9.0/lib/dns] owens% grep -A 3 -B 5 F5 opensslrsa_link.c

if (exp == 0) {
/* RSA_F4 0x10001 */
BN_set_bit(e, 0);
BN_set_bit(e, 16);
} else {
/* F5 0x100000001 */
BN_set_bit(e, 0);
BN_set_bit(e, 32);
}

Note - I have no opinion on whether this is good, bad, or merely ugly since I don't write crypto code and don't understand enough about RSA to be able to form an opinion. But that's what BIND does, as of the current version.

Bill.

[Spain, Dr. Jeffry A.]

> Its not about integer overflow, it's about the fact that F5 does not add to the security, but does use up a lot of CPU cycles.

I'd like to study this issue more. Would you please provide a reference that discusses your assertion that using an F5 public exponent does not add to the security of RSA encryption vs. F4 or perhaps F0.

With regard to CPU utilization, from the description of the modular exponentiation algorithm at http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method, it appears that the number of modular multiplications required for a modular exponentiation is the total number of bits in the exponent plus the number of one bits. This is 19 for an F4 exponent and 35 for F5. Given this, it's not obvious to me that the CPU utilization differences are significant. If you can point me to a reference that benchmarks this, that would be much appreciated.

Thanks. Jeff.

[Chris Thompson]

Oh, damn. I have to retract. Or indeed, grovel. It all depends on which
version of OpenSSL it is linked with, not on the code in dnssec-keygen
itself. Older versions do indeed generate 2^30+3, but newer ones 2^32+1.

You can see the BEAAAA (2^30+3) ones in the DNSKEYs for dlv.isc.org as
well as in a number of our own zones (which says either that the keys
are oldish or that the versions of OpenSSL used are not as up to date
as they probably ought to be).

[Miek Gieben]

[ Quoting <spa...@countryday.net> at 14:33 on Mar 7 in "RE: fermat primes an..." ]

> > Its not about integer overflow, it's about the fact that F5 does not add to the security, but does use up a lot of CPU cycles.
>
> I'd like to study this issue more. Would you please provide a reference that discusses your assertion that using an F5 public exponent does not add to the security of RSA encryption vs. F4 or perhaps F0.
>
> With regard to CPU utilization, from the description of the modular exponentiation algorithm at http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method, it appears that the number of modular multiplications required for a modular exponentiation is the total number of bits in the exponent plus the number of one bits. This is 19 for an F4 exponent and 35 for F5. Given this, it's not obvious to me that the CPU utilization differences are significant. If you can point me to a reference that benchmarks this, that would be much appreciated.

Well, go argue with Adam Langly in the bug report I submitted (and Paul quoted
in this thread).

grtz Miek

[Bill Owens]

On Wed, Mar 07, 2012 at 02:43:01PM +0000, Chris Thompson wrote:
> Oh, damn. I have to retract. Or indeed, grovel. It all depends on which
> version of OpenSSL it is linked with, not on the code in dnssec-keygen
> itself. Older versions do indeed generate 2^30+3, but newer ones 2^32+1.
>
> You can see the BEAAAA (2^30+3) ones in the DNSKEYs for dlv.isc.org as
> well as in a number of our own zones (which says either that the keys
> are oldish or that the versions of OpenSSL used are not as up to date
> as they probably ought to be).

Caveat - I am no kind of a programmer; I frequently get into trouble trying to read other peoples' code. However, I made an extremely naive patch to opensslrsa_link.c:

[littledebian:bind-9.9.0/lib/dns] owens% diff -c opensslrsa_link.c.orig opensslrsa_link.c
*** opensslrsa_link.c.orig 2012-03-07 09:48:48.000000000 -0500
--- opensslrsa_link.c 2012-03-07 09:50:46.000000000 -0500
***************
*** 752,760 ****

BN_set_bit(e, 0);
BN_set_bit(e, 16);
} else {

! /* F5 0x100000001 */
BN_set_bit(e, 0);
! BN_set_bit(e, 32);
}

if (callback == NULL) {
--- 752,761 ----

BN_set_bit(e, 0);
BN_set_bit(e, 16);
} else {

! /* 2^30+3 0x40000003 */
BN_set_bit(e, 0);
! BN_set_bit(e, 1);
! BN_set_bit(e, 30);
}

if (callback == NULL) {

. . . recompiled, and tried the new dnssec-keygen:

[littledebian:~] owens% /home/owens/src/bind-9.9.0/bin/dnssec/dnssec-keygen -e example.net
Generating key pair...++++++ .++++++
Kexample.net.+005+19281
[littledebian:~] owens% cat Kexample.net.+005+19281.key
; This is a zone-signing key, keyid 19281, for example.net.
; Created: 20120307145213 (Wed Mar 7 09:52:13 2012)
; Publish: 20120307145213 (Wed Mar 7 09:52:13 2012)
; Activate: 20120307145213 (Wed Mar 7 09:52:13 2012)
example.net. IN DNSKEY 256 3 5 BEAAAAO+k2eTlU4PS0U16bt6AVTZLqoaYKJKHXZYG+0yWZiiADqTd61W yuBHqrVgPJMLMKEGJRQpNJJRuVrOw3VZTC255gt+L5XLVzrmQwR2jG+0 QFPx+Dqriq9lqmhvxtUXDMTwrCMyhv5fdDjPJ1KxknimH0htOivrHBEE EIV/6gwPkQ==

As you pointed out, BEAAAAO is 2^30+3

[littledebian:~] owens% echo 'BEAAAAO+' | base64 -d | xxd -l 12 -b
0000000: 00000100 01000000 00000000 00000000 00000011 10111110 .@....

This certainly looks (to my inexpert eyes) like an explicit choice on the part of the BIND authors.

Bill.

[Bill Owens]

On Wed, Mar 07, 2012 at 02:43:01PM +0000, Chris Thompson wrote:
> You can see the BEAAAA (2^30+3) ones in the DNSKEYs for dlv.isc.org as
> well as in a number of our own zones (which says either that the keys
> are oldish or that the versions of OpenSSL used are not as up to date
> as they probably ought to be).

Incidentally, I surveyed a number of domains for exponent choices a couple of weeks ago, just for fun. These have 2^30+3:

bolagsverket.se
isc.org
sba.gov
skatteverket.se
verksamt.se

And these have 2^32+1:

america.gov
applicationmanager.gov
berkeley.edu
bredbandskollen.se
com.de
com.my
edu.my
epages.com
eu.com
fbi.gov
fueleconomy.gov
gov.my
iis.se
lsu.edu
mimiaukce.cz
mimishop.cz
net.my
nic.cz
opm.gov
ornl.gov
stockholm.se
uk.com
usajobs.gov
us.com
usconsulate.gov
usembassy.gov
uspto.gov
webtrh.cz

Reading Michael Sinatra's account of how he set up berkeley.edu was what led me to look at the zkt tool, which hardcodes the -e flag.

As Miek discovered, the hard way, .us also uses 2^32+1; my list didn't include TLDs so there may be others. I'll do another run over lunch today. . .

Bill.

[Spain, Dr. Jeffry A.]

> Well, go argue with Adam Langly in the bug report I submitted (and Paul quoted in this thread).

You're making an argumentum ad verecundiam, which I can't reasonably pursue. In the bug report (http://code.google.com/p/go/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Status%20Stars%20Priority%20Owner%20Reporter%20Summary&groupby=&sort=&id=3161), Adam Langly (assuming that is who "agl" is) refers to the article "Ron was wrong, Whit is right" (http://eprint.iacr.org/2012/064.pdf). That article discusses RSA public exponents in section 3, and states that the exponent 2^127+3 is used in a small percentage public keys, a fact to which agl alludes in his post. It doesn't address the security implications of any particular public key exponent, other than a few cases of what appear to be RSA implementation errors. The article focuses mainly on problems with the RSA modulus, rather than the exponent. Based on the facts presented so far in this thread, I can't find support for your assertion that keys created with 'dnssec-keygen -e' are insecure. Please post any additional evidence you may have that would further the discussion. Thanks. Jeff.

[Chris Thompson]

On Mar 7 2012, Bill Owens wrote:

[...]

>As Miek discovered, the hard way, .us also uses 2^32+1; my list didn't
>include TLDs so there may be others. I'll do another run over lunch today. . .

Based on a scan I did yesterday:

All DNSKEYs in all TLDs use an RSA public exponent of 2^16+1 except for
the following:

com, net & edu use 3 for all DNSKEYs
gov uses 3 for its KSK and active ZSKs, 2"32+1 for an idle ZSK
cz uses 2^16+1 for its KSK, 2^32+1 for its ZSK
la my & us use 2^32+1 for all DNSKEYs

[Bill Owens]

On Wed, Mar 07, 2012 at 03:35:25PM +0000, Spain, Dr. Jeffry A. wrote:
> Please post any additional evidence you may have that would further the discussion. Thanks. Jeff.

There's quite a bit about choosing e in this presentation:
http://www.esiea-recherche.eu/Slides09/slides_iAWACS09_Erra-Grenier_How-to-compute-RSA-keys.pdf

However, I don't understand the math, so I can't say whether any of the advice is reasonable :(

Bill.

[Spain, Dr. Jeffry A.]

> There's quite a bit about choosing e in this presentation:
> http://www.esiea-recherche.eu/Slides09/slides_iAWACS09_Erra-Grenier_How-to-compute-RSA-keys.pdf

> However, I don't understand the math, so I can't say whether any of the advice is reasonable :(

Interesting document, although I'm not a mathematician either. Slide 15 is the key, I think, saying in essence that there's no way to be certain that any given RSA key is secure. To be less uncertain about one's RSA keys, it suggests among other things reviewing recommendations from various national agencies. On slide 21 are some recommendations for the public key exponent: an odd integer not less than 65537 (Fermat number 4) and less than 2^256 (Fermat number 8 minus 1). Slide 23 describes a minor flaw when the exponent is greater than F4, but indicates that it is not a serious threat. Based on this document I don't see any reason to believe that exponent F4 (dnssec-keygen default) is any more or less secure than F5 (dnssec-keygen -e). Signature verification with exponent F5 would take more CPU time, but we don't have any benchmarking data to indicate whether or not this is significant.

Other posts have alluded to the Debian openssl flaw reported in May 2008 (http://www.debian.org/security/2008/dsa-1571). This led to predictable random primes being used to generate RSA moduli, and was not related to any specific public key exponent. It affected openssl version 0.9.8c-1, but only the Debian version.

Regards, Jeff.

[G.W. Haywood]

Hi there,

On Thu, 8 Mar 2012, Spain, Dr. Jeffry A. wrote:

> Other posts have alluded to the Debian openssl flaw reported in May
> 2008 (http://www.debian.org/security/2008/dsa-1571). This led to

> predictable random primes being used to generate RSA moduli ...

Just in case anyone thinks that this is a purely academic discussion,
in May 2008 when I received the Debian security advisory I did some
searching on the Internet for private keys. Several of my own hosts'
key pairs had been published widely in hackers' forums within less
than a day of the publication of the advisory. Here's one such pair:

-rw-r--r-- 1 root root 602 Aug 23 2007 ssh_host_dsa_key.pub.broken
-rw------- 1 root root 668 Aug 23 2007 ssh_host_dsa_key.broken
-rw-r--r-- 1 root root 602 May 14 2008 ssh_host_dsa_key.pub
-rw------- 1 root root 668 May 14 2008 ssh_host_dsa_key

It was rather worrying to find that this flaw had been available for
exploitation for nine months in the case of this particular host, very
satisfying that a policy of 'defence in depth' dropped all connection
attempts from unknown IPs, and little more than good fortune that the
affected servers were never exposed to the Internet.

--

73,
Ged.