Re: Exponent 3 damage spreads...

2006-09-28 Thread Erik Tews
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...

2006-09-28 Thread Ralf-Philipp Weinmann
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...

2006-09-28 Thread Kuehn, Ulrich
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...

2006-09-25 Thread 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) (perhaps more to come) My current estimate is that 0.26% of the

Re: Exponent 3 damage spreads...

2006-09-25 Thread Simon Josefsson
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...

2006-09-23 Thread Peter Gutmann
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...

2006-09-23 Thread Peter Gutmann
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...

2006-09-23 Thread Simon Josefsson
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...

2006-09-23 Thread Peter Gutmann
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...

2006-09-23 Thread Peter Gutmann
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...

2006-09-23 Thread Leichter, Jerry
| | 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...

2006-09-23 Thread Leichter, Jerry
| 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...

2006-09-23 Thread James A. Donald
-- : : 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...

2006-09-22 Thread Leichter, Jerry
| |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...

2006-09-22 Thread Anton Stiglic
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...

2006-09-21 Thread Hal Finney
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...

2006-09-21 Thread Tolga Acar
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...

2006-09-21 Thread Kuehn, Ulrich
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...

2006-09-21 Thread Peter Gutmann
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...

2006-09-21 Thread Kuehn, Ulrich
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...

2006-09-21 Thread Anton Stiglic
\ 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...

2006-09-21 Thread Simon Josefsson
[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...

2006-09-21 Thread Peter Gutmann
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...

2006-09-21 Thread Steven M. Bellovin
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...

2006-09-20 Thread Anton Stiglic
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...

2006-09-20 Thread Peter Gutmann
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...

2006-09-19 Thread Damien Miller
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...

2006-09-18 Thread James A. Donald
-- 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...

2006-09-16 Thread James A. Donald
-- 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...

2006-09-15 Thread Peter Gutmann
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...

2006-09-15 Thread Bill Frantz
[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...

2006-09-15 Thread Jostein Tveit
[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...

2006-09-15 Thread Peter Gutmann
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...

2006-09-14 Thread James A. Donald
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...

2006-09-14 Thread Peter Gutmann
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...

2006-09-14 Thread Simon Josefsson
[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...

2006-09-14 Thread Peter Gutmann
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...

2006-09-14 Thread Tim Dierks
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...

2006-09-14 Thread Hal Finney
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...

2006-09-14 Thread Greg Rose
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...

2006-09-14 Thread Greg Rose
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...

2006-09-13 Thread Simon Josefsson
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...

2006-09-13 Thread Thor Lancelot Simon
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...

2006-09-12 Thread Eric Young
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...

2006-09-11 Thread Peter Gutmann
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...

2006-09-11 Thread Ben Laurie
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...

2006-09-11 Thread Jostein Tveit
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...

2006-09-11 Thread Thierry Moreau
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...

2006-09-10 Thread James A. Donald
-- 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...

2006-09-10 Thread Ben Laurie
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...

2006-09-10 Thread bmanning
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