fermat primes and dnssec-keygen bug?
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 ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
RE: fermat primes and dnssec-keygen bug?
> 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 0x10001 */
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
___
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe
from this list
bind-users mailing list
bind-users@lists.isc.org
https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
[ Quoting 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 0x10001 */
> 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
signature.asc
Description: Digital signature
___
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe
from this list
bind-users mailing list
bind-users@lists.isc.org
https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
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 BE... 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: c...@cam.ac.uk ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
On Wed, Mar 07, 2012 at 12:13:35PM +, 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
> BE...
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
BQEBw3A8Wji6BjyanbOXUtIH1UcroHZKh06qRKXASbxHAQHJogaw
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 0x10001 */
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.
___
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe
from this list
bind-users mailing list
bind-users@lists.isc.org
https://lists.isc.org/mailman/listinfo/bind-users
RE: fermat primes and dnssec-keygen bug?
> 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. ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
On Mar 7 2012, Bill Owens wrote:
On Wed, Mar 07, 2012 at 12:13:35PM +, 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
BE...
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
BQEBw3A8Wji6BjyanbOXUtIH1UcroHZKh06qRKXASbxHAQHJogaw
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 0x10001 */
BN_set_bit(e, 0);
BN_set_bit(e, 32);
}
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 BE (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).
--
Chris Thompson
Email: c...@cam.ac.uk
___
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe
from this list
bind-users mailing list
bind-users@lists.isc.org
https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
[ Quoting 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 signature.asc Description: Digital signature ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
On Wed, Mar 07, 2012 at 02:43:01PM +, 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 BE (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.0 -0500
--- opensslrsa_link.c 2012-03-07 09:50:46.0 -0500
***
*** 752,760
BN_set_bit(e, 0);
BN_set_bit(e, 16);
} else {
! /* F5 0x10001 */
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 0x4003 */
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
BEO+k2eTlU4PS0U16bt6AVTZLqoaYKJKHXZYG+0yWZiiADqTd61W
yuBHqrVgPJMLMKEGJRQpNJJRuVrOw3VZTC255gt+L5XLVzrmQwR2jG+0
QFPx+Dqriq9lqmhvxtUXDMTwrCMyhv5fdDjPJ1KxknimH0htOivrHBEE EIV/6gwPkQ==
As you pointed out, BEO is 2^30+3
[littledebian:~] owens% echo 'BEO+' | base64 -d | xxd -l 12 -b
000: 0100 0100 0011 1010 .@
This certainly looks (to my inexpert eyes) like an explicit choice on the part
of the BIND authors.
Bill.
___
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe
from this list
bind-users mailing list
bind-users@lists.isc.org
https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
On Wed, Mar 07, 2012 at 02:43:01PM +, Chris Thompson wrote: > You can see the BE (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. ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
RE: fermat primes and dnssec-keygen bug?
> 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 ev idence you may have that would further the discussion. Thanks. Jeff. ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
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 -- Chris Thompson Email: c...@cam.ac.uk ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
Re: fermat primes and dnssec-keygen bug?
On Wed, Mar 07, 2012 at 03:35:25PM +, 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. ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
RE: fermat primes and dnssec-keygen bug?
> 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. ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
RE: fermat primes and dnssec-keygen bug?
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 root602 Aug 23 2007 ssh_host_dsa_key.pub.broken -rw--- 1 root root668 Aug 23 2007 ssh_host_dsa_key.broken -rw-r--r-- 1 root root602 May 14 2008 ssh_host_dsa_key.pub -rw--- 1 root root668 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. ___ Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list bind-users mailing list bind-users@lists.isc.org https://lists.isc.org/mailman/listinfo/bind-users
