Subject: [dnsop] Re: [dnssec-deployment] BIND and OpenSSL's RSA signature forging issue

From: Thierry Moreau <[email-masked]>
Date: Fri, 08 Sep 2006 08:05:54 -0400

Ben Laurie wrote:

> I've just noticed that BIND is vulnerable to:
> 
> http://www.openssl.org/news/secadv_20060905.txt
> 
> Executive summary:
> 
> RRSIGs can be forged if your RSA key has exponent 3, which is BIND's
> default. Note that the issue is in the resolver, not the server.
> 

See a more comprehensive report at

Hal Finney, "Bleichenbacher's RSA signature forgery based on 
implementation error" Wed, 30 Aug 2006
http://www.mail-archive.com/[email-masked]/msg06537.html

"based on implementation error" is somehow relevant to understand 
exactly where the vulnerability lies. I mean "somehow relevant" because 
the specific implementation error (a missing data validation check, 
where the check is useful *only* for preventing the Bleichenbacher's RSA 
signature forgery while the forgery was previously unknown) is very 
likely to be done by even dedicated implementation developers, and 
remain undetected in the SW testing phase because of its innocuous-ness.

> Fix:
> Upgrade OpenSSL.

Or use the proper command-line argument in the BIND-specific 
dnssec-keygen utility?

Or fix the BIND-specific dnssec-keygen utility to use the other allowed 
value (i.e 65537) as the default?

> Issue:
> 
> Since I've been told often that most of the world won't upgrade
> resolvers, presumably most of the world will be vulnerable to this
> problem for a long time.
> 
> Solution:
> 
> Don't use exponent 3 anymore. This can, of course, be done server-side,
> where the responsible citizens live, allegedly.
> 
> Side benefit:
> 
> You all get to test emergency key roll! Start your motors, gentlemen!
> 

Responsible citizens consult their family cryptographer before selecting 
an RSA public key exponent, and they stay away from public exponent=3 
for number-theoretic reasons known only to the family cryptographers (of 
which the Bleichenbacher's RSA signature forgery is an acutely practical 
consequence)!

> Cheers,

Cheers,

> Ben.

- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, Qc
Canada   H2M 2A1

Tel.: (514)385-5691
Fax:  (514)385-5900

web site: http://www.connotech.com
e-mail: [email-masked]

.
dnsop resources:_____________________________________________________
web user interface: http://darkwing.uoregon.edu/~llynch/dnsop.html
mhonarc archive: http://darkwing.uoregon.edu/~llynch/dnsop/index.html

---

From: Ben Laurie <[email-masked]>
Date: Fri, 08 Sep 2006 14:01:07 +0100

> value (i.e 65537) as the default?

Neither of these measures will fix existing keys, of course.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
.
dnsop resources:_____________________________________________________
web user interface: http://darkwing.uoregon.edu/~llynch/dnsop.html
mhonarc archive: http://darkwing.uoregon.edu/~llynch/dnsop/index.html

---

From: Thierry Moreau <[email-masked]>
Date: Fri, 08 Sep 2006 11:08:41 -0400

Roy Arends wrote:

> fyi
> 
> I noticed that SE uses e=65537 for their KSK and e=3 for their ZSKs.  
> This means that the keyroll (all zsk's need to be e<>3) should go  
> smoothly and no emergency trust anchor rollover is needed.
> 
> This is not the case for RIPE (194.in-addr.arpa). RIPE uses e=3 for  
> both ZSK and KSK. Hence an emergency trust anchor roll is needed.
> 

Perhaps you may check if BIND DNSSEC signature verification, which is 
different from SSL X.509 security certificate signature verification, 
actually does have the implementation flaw??

The protocol formats are different, and the X.509 format is more fertile 
ground for implementation error, because the message payload length is 
self-encoded in ASN.1 encoding, and duplicated in the message header 
length. In RFC3035 section 5.3.2 and RFC3110, it is possible that either 
1) BIND does not rely on OpenSSL for length checking concurrent with RSA 
validation, and/or 2) BIND software can in no circumstances pass 
erroneous length indications to OpenSSL (after all, DNSSEC spec tells 
implementers to *reconstruct* input to the RSA signature verification 
routine).

If it (BIND + deployed SEP KSKs) isn't broken, don't fix it as an 
emergency response to a false alarm.

On the other hand, we deprecate public exponent 3 in *any* operational 
use of RSA cryptosystem, so we spare ourselves a few emergency responses 
in a 10-year horizon.

-- 

- Thierry Moreau

Tel.: (514)385-5691
Fax:  (514)385-5900

.

---

From: Roy Arends <[email-masked]>
Date: Fri, 8 Sep 2006 16:05:28 +0200

fyi

Regards,

Roy
.

---

From: Paul Vixie <[email-masked]>
Date: 08 Sep 2006 17:32:37 +0000

> both ZSK and KSK. Hence an emergency trust anchor roll is needed.

i'd argue that if 194.in-addr.arpa is not registered a DLV registry and
if in-addr.arpa is not itself signed, then the community of beneficiaries
of 194's signedness is so small that this cannot be called an emergency.
-- 
ISC Training!  October 16-20, 2006, in the San Francisco Bay Area,
covering topics from DNS to DHCP.  Email [email-masked].
--
Paul Vixie
.
dnsop resources:_____________________________________________________
web user interface: http://darkwing.uoregon.edu/~llynch/dnsop.html
mhonarc archive: http://darkwing.uoregon.edu/~llynch/dnsop/index.html

---

From: Roy Arends <[email-masked]>
Date: Sat, 9 Sep 2006 00:14:09 +0200

> of 194's signedness is so small that this cannot be called an

I wouldn't use a dlv registry. All dlv.isc.org's DNSKEYs have e=3.

;)

Roy
.

---

From: Thierry Moreau <[email-masked]>
Date: Sat, 09 Sep 2006 12:16:24 -0400

Dear Roy:

Thanks for setting the record straight. See below for a suggestion as 
possible workaround in the BIND application for the OpenSSL weakeness 
for RSA signature verification with the public exponent=3.

Roy Arends wrote:

> 
> On Sep 8, 2006, at 5:08 PM, Thierry Moreau wrote:
> 
>>
>> The protocol formats are different, and the X.509 format is more  
>> fertile ground for implementation error, because the message  payload 
>> length is self-encoded in ASN.1 encoding, and duplicated in  the 
>> message header length. In RFC3035 section 5.3.2 and RFC3110, it  is 
>> possible that either 1) BIND does not rely on OpenSSL for length  
>> checking concurrent with RSA validation, and/or
> 
> 
> BIND uses openssl. There is a check during configure if the version  is 
> 0.9.5a or higher. I guess it should be either at least 0.9.7k or  0.9.8c 
> for upcoming releases.
> 
>> 2) BIND software can in no circumstances pass erroneous length  
>> indications to OpenSSL (after all, DNSSEC spec tells implementers  to 
>> *reconstruct* input to the RSA signature verification routine).
> 
> 
> The issue here is not passing the erroneous length indication to  
> openssl. The issue is that openssl did not check if the pkcs padding  
> was long enough so that len(00 01 FF*) is equal to len(modulus)-288  
> before removing the padding, thus allowing trailing garbage. There is  
> nothing that BIND or DNSSEC input reconstruction can do here in order  
> to circumvent the issue in openssl, since the padding itself will  only 
> be visible after the RRSIG signature payload is decrypted. The  padding 
> is then subsequently removed, and the hash is matched with  the hash 
> over message. All this is outside the scope of isc's named.

"the padding itself will only be visible after the RRSIG signature 
payload is decrypted"

   actually, to be more accurate, this should read:

"the padding itself will only be visible after the RRSIG signature 
payload is passed to the RSA encryptin function with the public 
signature key"

   and this leads to the suggestion below.

> it is broken.

I agree.

Here is a suggestion for a workaroud in BIND as an OpenSSL appication:

 From the RSA public signature key, make a temporary RSA public 
encryption key (I don't know the OpenSSL API details, but key usage 
integrity is typically enforced by a crypto library, so the {DNSKEY RR 
conversion to OpenSSL RSA public signature key object} can be followed 
by a {DNSKEY RR conversion to OpenSSL RSA public encryption key object} 
using the same RSA modulus and exponent from the DNSKEY RR contents).

Ask OpenSSL to encrypt the RRSIG signature payload with the temporary 
RSA public encryption key.

Check that the padding length is adequate.

This workaround in the BIND application is obviously neither a 
substitute for OpenSSL upgrade nor an endorsement of any public exponent 
3 in any operational use of RSA cryptosystem. But it might assist the 
reduction of vulnerable portion of DNSSEC deployed technology (BIND 
version and OpenSSL version at the resolver side, DNSSEC RR public 
exponent values=3 anywhere along the chain of trust).

This workaround idea is available to any application using OpenSSL. Feel 
free to circulate it in any other application forum.

Regards,

-- 

- Thierry Moreau

Tel.: (514)385-5691
Fax:  (514)385-5900

.

---

From: Paul Wouters <[email-masked]>
Date: Sun, 10 Sep 2006 05:24:13 +0200 (CEST)

> of 194's signedness is so small that this cannot be called an emergency.

More and more people will setup their own trusted keys. We don't neeed DLV
for that.

I'd rather see RIPE test their emergency key rollover procedure now, then
have them wait for a 'real' threat when people actually depend on its
secure status.

Paul
.

---

From: Ben Laurie <[email-masked]>
Date: Sun, 10 Sep 2006 07:12:52 +0100

Thierry Moreau wrote:
>>> Perhaps you may check if BIND DNSSEC signature verification, which 
>>> is different from SSL X.509 security certificate signature 
>>> verification, actually does have the implementation flaw??
>>>
>> BIND uses openssl. There is a check during configure if the version 
>> is 0.9.5a or higher. I guess it should be either at least 0.9.7k or 
>> 0.9.8c for upcoming releases.
>>
>> to circumvent the issue in openssl, since the padding itself will 
>> only be visible after the RRSIG signature payload is decrypted. The 
>> padding is then subsequently removed, and the hash is matched with 
>> the hash over message. All this is outside the scope of isc's named.
> 

You don't need to work around it, since OpenSSL has been fixed for
nearly a week now.

---

From: Thierry Moreau <[email-masked]>
Date: Sun, 10 Sep 2006 06:23:12 -0400

Ben Laurie wrote:

>>[...]

Yes, but what if it is not convenient to upgrade OpenSSL in a given 
run-time environment and it is possible to install or upgrade to an 
application that uses OpenSSL. I do not argue that it is good practice 
to rely on an application workaround for a cryptographic library 
weakness, but in some circumstances, it could be unavoidable or very 
effort-efficient.

Regards,

-- 

- Thierry Moreau

Tel.: (514)385-5691
Fax:  (514)385-5900

.

---

From: Paul Vixie <[email-masked]>
Date: Sun, 10 Sep 2006 04:37:59 +0000

> More and more people will setup their own trusted keys. We don't neeed DLV

i'm not sure we're transmissing on the same frequency.  can we try that again?
if more and more people set up their own trusted keys, then when more and more
of those trusted keys roll over, then more and more of the people who have set
up trusted keys will have to input replacement trust anchors, usually using
"cut and paste" and eventually depending on unsecure e-mail on mailing lists
as their cue to do so.

draft-ietf-dnsext-trustupdate-timers-04.txt is the IETF's current best guess as
to how this might be automated, and nobody (anywhere) thinks anymore than the
root zone will be signed (ever), and so it'll be "every TLD for itself".  in
the context of the current discussion, in-addr.arpa is "like the root".

> have them wait for a 'real' threat when people actually depend on its

i actually do love the way you're thinking, even though it's completely wrong.

what we're likely to learn from a 194 key rollover event is (a) pretty much
nobody had the trust anchor installed, (b) pretty much nobody who installed
it will remember that they'd installed it, (c) pretty much no applications will
break when the key rolls and the trust anchors don't, since nothing depends
on it working, and (d) dnssec is still a solution in search of a problem (and
a deployment plan).

http://ietcom.oxfordjournals.org/cgi/content/abstract/E88-B/4/1326 has a full
PDF available of the paper on DLV i published in IEICE last year.  i've also
given a presentation on DLV several times including USENIX LISA last year where
they MP3'd it (http://www.usenix.org/event/lisa05/tech/mp3/vixie.mp3) and wrote
about it in ;login: (volume 32 number 2 page 94).  if dnssec needed to scale
in its current form, we'd (http://www.isc.org/ops/dlv/) have heard about it.
.
dnsop resources:_____________________________________________________
web user interface: http://darkwing.uoregon.edu/~llynch/dnsop.html
mhonarc archive: http://darkwing.uoregon.edu/~llynch/dnsop/index.html