### Re: Exponent 3 damage spreads...

Am Montag, den 25.09.2006, 01:28 +0200 schrieb Philipp Gühring: Hi, We have been researching, which vendors were generating Exponent 3 keys, and we found the following until now: * Cisco 3000 VPN Concentrator * CSP11 * AN.ON / JAP (they told me they would change it on the next day)

### Re: Exponent 3 damage spreads...

On Sep 25, 2006, at 10:29 AM, Simon Josefsson wrote: Leichter, Jerry [EMAIL PROTECTED] writes: I agree that there are two issues, and they need to be treated properly. The first - including data after the ASN.1 blob in the signature computation but then ignoring it in determining the

### RE: Exponent 3 damage spreads...

From: Ralf-Philipp Weinmann [...] Relevant files to this problem that were patched turned out to be security/nss/lib/cryptohi/secvfy.c and nss/lib/util/secdig.c. Have a look at the function DecryptSigBlock() in secdig.c, lines 92-95 /* make sure the parameters are not too

### Re: Exponent 3 damage spreads...

Hi, We have been researching, which vendors were generating Exponent 3 keys, and we found the following until now: * Cisco 3000 VPN Concentrator * CSP11 * AN.ON / JAP (they told me they would change it on the next day) (perhaps more to come) My current estimate is that 0.26% of the

### Re: Exponent 3 damage spreads...

Leichter, Jerry [EMAIL PROTECTED] writes: I agree that there are two issues, and they need to be treated properly. The first - including data after the ASN.1 blob in the signature computation but then ignoring it in determining the semantics - is, I'll argue, an implementation error. You

### Re: Exponent 3 damage spreads...

Simon Josefsson [EMAIL PROTECTED] writes: Not using e=3 when generating a key seems like an easy sell. Almost no-one does this anyway, but I don't think that's much help. A harder sell might be whether widely deployed implementations such as TLS should start to reject signatures done with an

### RE: Exponent 3 damage spreads...

Leichter, Jerry [EMAIL PROTECTED] writes: | I don't think it's a problem, you just take the ASN.1 DigestInfo | value, since the trailing garbage isn't part of the DigestInfo, you | ignore it. Specifically, the ASN.1 object is entirely self-contained, | so you can tell exactly where it ends and

### Re: Exponent 3 damage spreads...

Leichter, Jerry [EMAIL PROTECTED] writes: Granted, one or more implementations got this wrong. (Has anyone looked to see if all the incorrect code all descends from a common root, way back when?) We have at least three independent widely used implementations that got things wrong: OpenSSL,

### Re: Exponent 3 damage spreads...

Yet another e=3 attack, although this one is a bit special-case. As Burt Kaliski points out in his paper on hash function firewalls, http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.pdf, if you can control the

### Re: Exponent 3 damage spreads...

Leichter, Jerry [EMAIL PROTECTED] writes: A several year old paper by Kaliski discussed using the ASN.1 OID to store data in. Damn, beat me to it :-). It has slightly different properties, but the lesson in this context is that implementations must properly check the ASN.1 OID field too. The

### RE: Exponent 3 damage spreads...

| | I don't think it's a problem, you just take the ASN.1 DigestInfo | | value, since the trailing garbage isn't part of the DigestInfo, you | | ignore it. Specifically, the ASN.1 object is entirely | | self-contained, so you can tell exactly where it ends and what it | | contains. Anything

### Re: Exponent 3 damage spreads...

| Granted, one or more implementations got this wrong. (Has anyone | looked to see if all the incorrect code all descends from a common | root, way back when?) | | We have at least three independent widely used implementations that | got things wrong: OpenSSL, Mozilla NSS, and GnuTLS. | |

### Re: Exponent 3 damage spreads...

-- : : 10.2.3 Data decoding : : The data D shall be BER-decoded to give an ASN.1 : : value of type DigestInfo, which shall be separated : : into a message digest MD and a message-digest : : algorithm identifier. The message-digest algorithm : : identifier shall determine the selected : :

### RE: Exponent 3 damage spreads...

| |10.2.3 Data decoding | |The data D shall be BER-decoded to give an ASN.1 value of |type DigestInfo, which shall be separated into a message |digest MD and a message-digest algorithm identifier. The |message-digest algorithm identifier shall determine

### RE: Exponent 3 damage spreads...

O.k., thanks to Hal Finney for pointing out to me in a private email that my modulus wasn't in fact the right size. I have had some problems with the openssl key generation (doesn't always seem to generate the exact modulus size I ask for). In attachment, the forged signature

### RE: Exponent 3 damage spreads...

Anton Stiglic writes: I tried coming up with my own forged signature that could be validated with OpenSSL (which I intended to use to test other libraries). ... Now let's look at s^3 1FFF\

### RE: Exponent 3 damage spreads...

PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Anton Stiglic Sent: Tuesday, September 19, 2006 8:56 PM To: cryptography@metzdowd.com Cc: 'Anton Stiglic' Subject: RE: Exponent 3 damage spreads... I tried coming up with my own forged signature that could be validated with OpenSSL

### RE: Exponent 3 damage spreads...

Peter, From: Peter Gutmann [mailto:[EMAIL PROTECTED] David Wagner [EMAIL PROTECTED] writes: (a) Any implementation that doesn't check whether there is extra junk left over after the hash digest isn't implementing the PKCS#1.5 standard correctly. That's a bug in the implementation.

### RE: Exponent 3 damage spreads...

Kuehn, Ulrich [EMAIL PROTECTED] writes: But the PKCS#1 spec talks about building up the complete padded signature input at the verifier, and then comparing it. Uhh, did you actually read the rest of my post? *One variant of the PKCS #1 spec, that didn't exist at the time the the affected other

### RE: Exponent 3 damage spreads...

Peter, From: Peter Gutmann [mailto:[EMAIL PROTECTED] Kuehn, Ulrich [EMAIL PROTECTED] writes: But the PKCS#1 spec talks about building up the complete padded signature input at the verifier, and then comparing it. Uhh, did you actually read the rest of my post? *One variant of the

### RE: Exponent 3 damage spreads...

\ 85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\ 81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E5324000\ 000 -Original Message- From: Hal Finney [mailto:[EMAIL PROTECTED] Sent: September 20, 2006 6:21 PM To: [EMAIL PROTECTED]; cryptography@metzdowd.com Subject: RE: Exponent 3 damage

### Re: Exponent 3 damage spreads...

[EMAIL PROTECTED] (Peter Gutmann) writes: Consequently, I think the focus on e=3 is misguided. It's not at all misguided. This whole debate about trying to hang on to e=3 seems like the argument about epicycles, you modify the theory to handle anomalies, then you modify it again to handle

### RE: Exponent 3 damage spreads...

Kuehn, Ulrich [EMAIL PROTECTED] writes: 10.2.3 Data decoding The data D shall be BER-decoded to give an ASN.1 value of type DigestInfo, which shall be separated into a message digest MD and a message-digest algorithm identifier. The message-digest algorithm

### Re: Exponent 3 damage spreads...

On Thu, 21 Sep 2006 07:00:03 -0400, Whyte, William [EMAIL PROTECTED] wrote: Similarly, the thousands of words of nitpicking standards, bashing ASN.1, and so on ad nauseum, can be eliminated entirely by following one simple rule: Don't use e=3 I'd extend it to don't use e = 17.

### RE: Exponent 3 damage spreads...

I tried coming up with my own forged signature that could be validated with OpenSSL (which I intended to use to test other libraries). I haven't succeeded, either because in the particular example I came up with OpenSSL does something that catches the invalid signature, or I messed up somewhere

### Re: Exponent 3 damage spreads...

David Wagner [EMAIL PROTECTED] writes: (a) Any implementation that doesn't check whether there is extra junk left over after the hash digest isn't implementing the PKCS#1.5 standard correctly. That's a bug in the implementation. No, it's a bug in the spec: 9.4 Encryption-block parsing It is an

### Re: Exponent 3 damage spreads...

On Fri, 15 Sep 2006, Jostein Tveit wrote: [EMAIL PROTECTED] (Peter Gutmann) writes: What's more scary is that if anyone introduces a parameterised hash (it's quite possible that this has already happened in some fields, and with the current interest in randomised hashes it's only a

### Re: Exponent 3 damage spreads...

-- David Wagner wrote: It seems to me that e=3 is a distraction. I think that these security holes have revealed some more fundamental issues here that are independent of the value of e you use. It seems to me that the problems can be attributed to two problems: (a) implementation

### Re: Exponent 3 damage spreads...

-- Peter Gutmann wrote: Right, but it's been pure luck that that particular implementation (and most likely a number of others) happen to have implemented only a small number of hash algorithms that allow only absent or NULL parameters. Anything out there that implements a wider range of

### Re: Exponent 3 damage spreads...

Simon Josefsson [EMAIL PROTECTED] writes: Deploying a hash widely isn't done easily, though. GnuTLS only support MD2, MD5, SHA-1 and RIPEMD (of which MD2/MD5 are by default not used to verify signatures). Right, but it's been pure luck that that particular implementation (and most likely a

### Re: Exponent 3 damage spreads...

[EMAIL PROTECTED] (James A. Donald) on Thursday, September 14, 2006 wrote: Obviously we do need a standard for describing structured data, and we need a standard that leads to that structured data being expressed concisely and compactly, but seems to me that ASN.1 is causing a lot of grief.

### Re: Exponent 3 damage spreads...

[EMAIL PROTECTED] (Peter Gutmann) writes: What's more scary is that if anyone introduces a parameterised hash (it's quite possible that this has already happened in some fields, and with the current interest in randomised hashes it's only a matter of time before we see these anyway) [...]

### Re: Exponent 3 damage spreads...

Simon Josefsson [EMAIL PROTECTED] writes: Test vectors for this second problem are as below, created by Yutaka OIWA. To make this easier to work with, I've combined them into a PKCS #7 cert chain (attached). Just load/click on the chain and see what your app says. (As an aside, this chain is

### Re: Exponent 3 damage spreads...

Simon Josefsson wrote: Jostein Tveit [EMAIL PROTECTED] writes: Anyone got a test key with a real and a forged signature to test other implementations than OpenSSL? There are actually two problems to consider... First, there is the situation by Bleichenbacher at Crypto 06 and explained in:

### Re: Exponent 3 damage spreads...

Simon Josefsson [EMAIL PROTECTED] writes: The second problem is that the parameters field can ALSO be used to store data that may be used to manipulate the signature value into being a cube. To my knowledge, this was discovered by Yutaka Oiwa, Kazukuni Kobara, Hajime Watanabe. I didn't attend

### Re: Exponent 3 damage spreads...

[EMAIL PROTECTED] (Peter Gutmann) writes: Simon Josefsson [EMAIL PROTECTED] writes: The second problem is that the parameters field can ALSO be used to store data that may be used to manipulate the signature value into being a cube. To my knowledge, this was discovered by Yutaka Oiwa, Kazukuni

### Re: Exponent 3 damage spreads...

Simon Josefsson [EMAIL PROTECTED] writes: [EMAIL PROTECTED] (Peter Gutmann) writes: Simon Josefsson [EMAIL PROTECTED] writes: The second problem is that the parameters field can ALSO be used to store data that may be used to manipulate the signature value into being a cube. To my knowledge, this

### Re: Exponent 3 damage spreads...

On 9/14/06, James A. Donald [EMAIL PROTECTED] wrote: It seems to me that the evil here is ASN.1, or perhaps standards that use ASN.1 carelessly and badly. It is difficult to write code that conforms to ASN.1, easy to get it wrong, and difficult to say what in fact constitutes conforming to

### Re: Exponent 3 damage spreads...

Peter Gutmann writes: But wait, there's more! From what I understand of the attack, all you need for it to work is for the sig.value to be a perfect cube. To do this, all you need to do is vary a few of the bytes of the hash value, which you can do via a simple brute-force search. So even

### Re: Exponent 3 damage spreads...

So, there is at least one top-level CA installed in some common browsers (I checked Firefox) that uses exponent-3. It is Starfield Technologies Inc. Starfield Class 2 CA. There may well be others... I only looked far enough to determine that that was a problem. So the next question becomes,

### Re: Exponent 3 damage spreads...

At 23:40 +1200 2006/09/14, Peter Gutmann wrote: But wait, there's more! From what I understand of the attack, all you need for it to work is for the sig.value to be a perfect cube. To do this, all you need to do is vary a few of the bytes of the hash value, which you can do via a simple

### Re: Exponent 3 damage spreads...

Jostein Tveit [EMAIL PROTECTED] writes: Anyone got a test key with a real and a forged signature to test other implementations than OpenSSL? There are actually two problems to consider... First, there is the situation by Bleichenbacher at Crypto 06 and explained in:

### Re: Exponent 3 damage spreads...

On Mon, Sep 11, 2006 at 06:18:06AM +1000, James A. Donald wrote: 3. No one actually uses DNSSEC in the wild. DNSSEC seems to be not-uncommonly used to secure dynamic updates, which is not the most common DNS feature in the world but it is not so uncommon either.

### Re: Exponent 3 damage spreads...

Jostein Tveit wrote: Anyone got a test key with a real and a forged signature to test other implementations than OpenSSL? Well, since this in not really an issue about forging signatures, rather invalid verification, I've appended 2 self-signed certs (resigned apps/server.pem), one with a

### Re: Exponent 3 damage spreads...

Ben Laurie [EMAIL PROTECTED] quotes: 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. What you really meant to say was most of the vanishingly small proportion of the world that bothers

### Re: Exponent 3 damage spreads...

James A. Donald wrote: -- James A. Donald wrote: What is the penetration of Secure DNS? Ben Laurie wrote: Anyone who is running any vaguely recent version of BIND is DNSSEC enabled, whether they are using it now or not. I am not well informed about DNSSEC, but I am under the

### Re: Exponent 3 damage spreads...

Ben Laurie [EMAIL PROTECTED] writes: ...thought this might interest people here. Anyone got a test key with a real and a forged signature to test other implementations than OpenSSL? Thanks in advance. Regards, -- Jostein Tveit [EMAIL PROTECTED]

### Re: Exponent 3 damage spreads...

Jostein Tveit wrote: Ben Laurie [EMAIL PROTECTED] writes: ...thought this might interest people here. Anyone got a test key with a real and a forged signature to test other implementations than OpenSSL? If I understand the attack mathematics correctly, the following algorithm should

### Re: Exponent 3 damage spreads...

-- Ben Laurie wrote: Subject: [dnsop] BIND and OpenSSL's RSA signature forging issue From: Ben Laurie [EMAIL PROTECTED] Date: Fri, 08 Sep 2006 11:40:44 +0100 To: DNSEXT WG namedroppers@ops.ietf.org, (DNSSEC deployment) [EMAIL PROTECTED], dnsop@lists.uoregon.edu To: DNSEXT WG

### Re: Exponent 3 damage spreads...

James A. Donald wrote: -- Ben Laurie wrote: Subject: [dnsop] BIND and OpenSSL's RSA signature forging issue From: Ben Laurie [EMAIL PROTECTED] Date: Fri, 08 Sep 2006 11:40:44 +0100 To: DNSEXT WG namedroppers@ops.ietf.org, (DNSSEC deployment) [EMAIL PROTECTED],

### Re: Exponent 3 damage spreads...

On Sun, Sep 10, 2006 at 08:30:53AM +1000, James A. Donald wrote: -- Ben Laurie wrote: Subject: [dnsop] BIND and OpenSSL's RSA signature forging issue From: Ben Laurie [EMAIL PROTECTED] Date: Fri, 08 Sep 2006 11:40:44 +0100 To: DNSEXT WG namedroppers@ops.ietf.org, (DNSSEC