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) (perhaps more to come) My current estimate is that 0.26% of the certificates in the wild have Exponents =17 I did a little survey one month ago for my bsc. thesis. I found out, that round about 1.19% of all https-server-certs use an exponent = 17. I did choose round about 32,000 random webservers for this survey. What is intresting is what happens when it comes to imap-ssl. Here, only 0.1% of all servers use a server-cert with exponent = 17. Imap-ssl users seem to be the better ssl-users, tls 1.0 is more widespread there, small rsa-modulus-sizes are more seldom, and ssl 2.0 is not so common there too. I will publish some more details later. signature.asc Description: Dies ist ein digital signierter Nachrichtenteil
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
semantics - is, I'll argue, an implementation error. You list only
OpenSSL as definitely vulnerable, NSS as ?, so it sounds like
only one definitive example.
Yes. I'm only familiar with NSS as a user, not as a developer. For
some reason, the Mozilla bug tracker hides information about this
problem from us, so it is difficult to track the code down.
I believe I identified the patch that solved the problem in NSS,
search for 350640 in:
http://bonsai.mozilla.org/cvsquery.cgi?branch=HEADfile=mozilla/
security/nss/date=month
The bug discussion is not public:
https://bugzilla.mozilla.org/show_bug.cgi?id=350640
Possibly also bug reports 351079 and 351848 are related to the same
problem, but these bugs are also hidden.
The actual patch for 350640 is:
http://bonsai.mozilla.org/cvsview2.cgi?
diff_mode=contextwhitespace_mode=showsubdir=mozilla/security/nss/
lib/
utilcommand=DIFF_FRAMESETfile=secdig.crev1=1.6rev2=1.7root=/
cvsroot
If some NSS developer could chime in, that would help.
Even if NSS has the same problem, one has to look at code
provenance.
Sure.
Hi Simon,
I'm not a NSS developer, but we did have a look at the code here to
figure out what EXACTLY those guys patched. The relevant portion can
quite easily be found by diff'ing the tags FIREFOX_1_5_0_6_RELEASE
vs. FIREFOX_1_5_0_7_RELEASE on their CVS tree for example. Insofar I
don't think that leaving the bug reports private after actually
shoving out the release does not really help things in this
situation; quite the opposite.
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 bogus. */
if (di-digestAlgorithm.parameters.len 2) {
goto sigloser;
}
Quite amused, we also noted the following:
/* XXX Check that tag is an appropriate algorithm? */
---
/* Check that tag is an appropriate algorithm */
if (tag == SEC_OID_UNKNOWN) {
goto sigloser;
}
This means, that before the patch was applied, NSS indeed was
vulnerable to Kaliski's OID attack.
At least some versions of PKCS#1 does NOT say that, e.g., RFC 3447.
RFC 3447 essentially says to generate a new token and use memcmp().
Such implementations would not be vulnerable to any of the current
attacks, except the Kaliski ASN.1 OID attack (an attack that doesn't
work on existing implementations).
See above.
Cheers,
Ralf
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 bogus. */
if (di-digestAlgorithm.parameters.len 2) {
goto sigloser;
}
Quite amused, we also noted the following:
/* XXX Check that tag is an appropriate algorithm? */
---
/* Check that tag is an appropriate algorithm */
if (tag == SEC_OID_UNKNOWN) {
goto sigloser;
}
This means, that before the patch was applied, NSS indeed was
vulnerable to Kaliski's OID attack.
While the patch for Firefox obviously fixed the bugs in
security/nss/lib/cryptohi/whatever,
There is another pkcs#1-padding check in security/nss/lib/softtoken/rsawrapr.c,
see function
RSA_CheckSign() and RSA_CheckSignRecover(). Does anybody know what these
functions are used for?
I tried to find that out, but did not get very far...
(Hal Finney also noted these functions some days ago).
It seems to be another creative bug:
/*
* check the padding that was used
*/
if (buffer[0] != 0 || buffer[1] != 1)
goto loser;
for (i = 2; i modulus_len - hash_len - 1; i++) {
if (buffer[i] == 0)
break;
if (buffer[i] != 0xff)
goto loser;
}
/*
* make sure we get the same results
*/
if (PORT_Memcmp(buffer + modulus_len - hash_len, hash, hash_len) != 0)
goto loser;
So it would accept a padding ( 00 || 01 || 00 || garbage || hash ), which is
not exactly what pkcs#1 says :)
The same loop is used in RSA_CheckSignRecover(), but I did not succeed in
finding out what it is exactly used for and if that is a safe application of
the rather wrong code.
Cheers,
Ulrich
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 certificates in the wild have Exponents =17 Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 list only OpenSSL as definitely vulnerable, NSS as ?, so it sounds like only one definitive example. Yes. I'm only familiar with NSS as a user, not as a developer. For some reason, the Mozilla bug tracker hides information about this problem from us, so it is difficult to track the code down. I believe I identified the patch that solved the problem in NSS, search for 350640 in: http://bonsai.mozilla.org/cvsquery.cgi?branch=HEADfile=mozilla/security/nss/date=month The bug discussion is not public: https://bugzilla.mozilla.org/show_bug.cgi?id=350640 Possibly also bug reports 351079 and 351848 are related to the same problem, but these bugs are also hidden. The actual patch for 350640 is: http://bonsai.mozilla.org/cvsview2.cgi?diff_mode=contextwhitespace_mode=showsubdir=mozilla/security/nss/lib/utilcommand=DIFF_FRAMESETfile=secdig.crev1=1.6rev2=1.7root=/cvsroot If some NSS developer could chime in, that would help. Even if NSS has the same problem, one has to look at code provenance. Sure. OSS efforts regularly share code, and code to pick apart data fields is hardly kind of thing that is going to inspire someone to go out and do it better - just share. I think you want to read up on free software license compatibilities, and in particular OpenSSL vs GPL. But this is a very different topic, that we shouldn't pursue here... The second - embedded parameter fields - is a much deeper issue. That's a protocol and cryptographic error. The implementations appear to be correctly implementing the semantics implied by the spec - ignore parameters you don't care about. At least some versions of PKCS#1 does NOT say that, e.g., RFC 3447. RFC 3447 essentially says to generate a new token and use memcmp(). Such implementations would not be vulnerable to any of the current attacks, except the Kaliski ASN.1 OID attack (an attack that doesn't work on existing implementations). This is common practice, and a fine idea in *most* situations, since it allows for extensions without breaking existing implementations. I believe the principle of Be conservative in what you do; be liberal in which you accept from others is generally a bad advice. The principle hides problems that should be fixed. Hiding a problem instead of fixing it typically enables bad things to happen. We've seen that lead to security problems for many years, this is just one example. /Simon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 e=3 RSA key. What do people think, is there sufficient grounds for actually _rejecting_ e= 3 signatures? I can't think of any other way to get people to move away from e=3. The problem isn't major implementations who use e=F4 and check signatures properly (at least as of a week or so back :-), it's the hundreds (or thousands?) of random obscure implementations and deployments that'll never even hear about this and will never be fixed, and so will remain vulnerable in perpetuity without even knowing it. Unless things break obviously, there's no incentive (or even apparent need) to fix it. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 what it contains. Anything | outside it is beyond the scope of this specification :-). This is a rather peculiar interpretation of the spec. If I look at a C specification and it tells me that an integer is a string of digits, when I write a C compiler, am I permitted to say that [EMAIL PROTECTED]% can be parsed as an entirely contained integer, with the @#% beyond the scope of the specification? No, because the compiler doesn't use a TLV encoding as ASN.1 does. Take something like an MPEG, JPEG, MP3, or some other piece of data that uses a TLV encoding with a clearly defined (by the data) end. Cat some extra garbage onto the end of it, and try and view/play it. If it's a proper TLV encoding (rather than a TV encoding, i.e. no explicit length info included) then the decoder/player will ignore the extra garbage at the end*. That's the whole point of TLV encodings, you know a priori when to stop, and stop exactly at that point. Peter. * There are some that might keep reading in the hope that something else crops up, I don't know, but the ones I've looked at don't care if there's extra junk at the end. This goes back at least as far as CP/M, where you could have extra ^Z's and other junk at the end of files that apps had to avoid ploughing into. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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, Mozilla NSS, and GnuTLS. However, note that this isn't a single problem; we are talking about at least two related problems. Some implementations are vulnerable to only one of them. The first problem was ignoring data _after_ the ASN.1 blob. Vulnerable: OpenSSL, NSS? The second problem was ignoring data _in_ the ASN.1 blob, in particular, in the parameters field. Vulnerable: OpenSSL, GnuTLS, NSS? A several year old paper by Kaliski discussed using the ASN.1 OID to store data in. It has slightly different properties, but the lesson in this context is that implementations must properly check the ASN.1 OID field too. Until we know whether this is *one* mistake that was copied from implementation to implementation, or the same mistake made by multiple developers, it's really premature to draw any conclusions. I hope that I convinced you that this isn't an open question. /Simon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 AlgorithmIdentifier (specifically the object identifier or OID), you can also inject arbitrary bits into the signature. This works as follows: 1. Create your forged e=3 signature using extra chosen garbage data. 2. Register an object identifier for the hash algorithm that contains the extra data, thus allowing you to retro-create the forged signature using legitimate data. 3. Profit! The use of multiple OIDs to identify a single algorithm is relatively common (see the OID table for dumpasn1, there are something like a dozen overlapping OIDs for DSA alone), all you need to do is get one registered and adopted. Sure, it's a bit of work, but if implemented no amount of checking will catch it, since it's a perfectly valid, legitimate OID and encoding. (I know of at least one registered OID that was back-engineered to contain an particular interesting bit pattern, and I've seen it used in several implementations, so this isn't that far-fetched an attack). Oh yes, and before the ASN.1-bashing starts again, this affects any encoding scheme, it's not some ASN.1 problem. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 problem is that no amount of checking can catch this. If you register the OID or otherwise get it into some standard somewhere, then it's kosher as far as anyone's concerned. There's no check that can catch it if you're required (by a standard, by a client, by bilateral agreement, etc) to accept that OID. (There's been at least one case where random OIDs have been used in the past. Since it's a pain to register them, a large vendor generated them randomly beneath an arc registered to them. Although this is kind of weird and I'm sure was never meant to be done this way, there's nothing inherently invalid about this). Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 outside it is beyond the scope of this | | specification :-). | | This is a rather peculiar interpretation of the spec. If I look at a | C specification and it tells me that an integer is a string of | digits, when I write a C compiler, am I permitted to say that | [EMAIL PROTECTED]% can be parsed as an entirely contained integer, with the | @#% beyond the scope of the specification? | | No, because the compiler doesn't use a TLV encoding as ASN.1 does. | Take something like an MPEG, JPEG, MP3, or some other piece of data | that uses a TLV encoding with a clearly defined (by the data) end. | Cat some extra garbage onto the end of it, and try and view/play it. | If it's a proper TLV encoding (rather than a TV encoding, i.e. no | explicit length info included) then the decoder/player will ignore the | extra garbage at the end*. That's the whole point of TLV encodings, | you know a priori when to stop, and stop exactly at that point. I have to disagree. The spec describes an entire certificate, not one field inside of it. The issue isn't the TLV encoding of the DigestInfo - fine, that subfield ended. It's the next level in the hierarchy, the D data field I think it was called. TLV-encoded or not, it exists as a called-out entity, since it is what the signature is run over. And we are told that D consists of DigestInfo and a digest value. That's it; no extra bytes at the end. If this were at the end of the certificate, and the code *completely ignored* the random trailing junk - that is, it did *not* include it in the signature - then you might have an argument. | Peter. | | * There are some that might keep reading in the hope that something | else crops up, I don't know, but the ones I've looked at don't care | if there's extra junk at the end. This goes back at least as far as | CP/M, where you could have extra ^Z's and other junk at the end of | files that apps had to avoid ploughing into. I would expect a file *player* that pretty much linearly scans a file, that's designed to be user-friendly, that runs in the standards-free zone of Windows software, and that doesn't deal with anything particularly critical, to have a greedy algorithm that just decodes as it goes along. Compare to Web browsers and their casual acceptance of all kinds of broken HTML. In both cases, I would expect a validator to be much stricter - and I would certainly expect a security-relevant piece of software, or even something like a compiler, to be strict. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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. | | However, note that this isn't a single problem; we are talking about | at least two related problems. Some implementations are vulnerable to | only one of them. | | The first problem was ignoring data _after_ the ASN.1 blob. | Vulnerable: OpenSSL, NSS? | | The second problem was ignoring data _in_ the ASN.1 blob, in | particular, in the parameters field. Vulnerable: OpenSSL, GnuTLS, | NSS? | | A several year old paper by Kaliski discussed using the ASN.1 OID to | store data in. It has slightly different properties, but the lesson | in this context is that implementations must properly check the ASN.1 | OID field too. | | Until we know whether this is *one* mistake that was copied from | implementation to implementation, or the same mistake made by | multiple developers, it's really premature to draw any conclusions. | | I hope that I convinced you that this isn't an open question. 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 list only OpenSSL as definitely vulnerable, NSS as ?, so it sounds like only one definitive example. Even if NSS has the same problem, one has to look at code provenance. OSS efforts regularly share code, and code to pick apart data fields is hardly kind of thing that is going to inspire someone to go out and do it better - just share. The second - embedded parameter fields - is a much deeper issue. That's a protocol and cryptographic error. The implementations appear to be correctly implementing the semantics implied by the spec - ignore parameters you don't care about. This is common practice, and a fine idea in *most* situations, since it allows for extensions without breaking existing implementations. As we've seen, it's a really bad idea for signed fields with small exponent, since they have an unexpected malleability. The advice to avoid small exponents is fine, but in fact I think this is a special case of another principle: Don't act as a signing oracle. That was known to be a bad idea quite some time ago, and it's one reason we sign cryptographic hashes, not raw data. The curiosity of this bit of misdesign is that it hashes the raw data, but then, on the way to signing it, turns the field back into (mainly) raw data! -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 : : message-digest algorithm for the next step. Leichter, Jerry wrote: The only reasonable reading of the text quoted above is that the D must consist of, and *only* of, an ASN.1 value of the given type. That is not what it says. It says shall be decoded to give, not shall be decoded to give and only give Further, similar text appears in lots of places where the correct behavior, to allow for future extension, is to allow for more stuff. A major design consideration in ASN.1 was *to* allow for more stuff, in order that multiple versions of the specification can peacefully coexist. Therefore, in the context of ASN.1, the correct interpretation of the specification is to allow for arbitrary expansion - which is a bad spec. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG uTSBsEVoGqap3qSR80twUH+gg5Q8MDBgQhB2Wyxw 4AjRA5gK1azQkXrhC7CakjCPKw7vvSVL7qWID8o/o - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 message-digest algorithm for the next step. | | Here, any trailing garbage would be included in data D. But does an | ASN.1 value allow such a thing? I am asking this independently of our | discussion here. | | 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 | outside it is beyond the scope of this specification :-). This is a rather peculiar interpretation of the spec. If I look at a C specification and it tells me that an integer is a string of digits, when I write a C compiler, am I permitted to say that [EMAIL PROTECTED]% can be parsed as an entirely contained integer, with the @#% beyond the scope of the specification? The only reasonable reading of the text quoted above is that the D must consist of, and *only* of, an ASN.1 value of the given type. 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?) Those implementations are as wrong as a C compiler that skips irrelevant junk at the end of an integer constant. I wouldn't blame either the spec or the use of ASN.1. The implementations are just plain wrong. There isn't even any plausible interpretation that would make them right. (On the one hand, they use all the data, including the junk, in computing the signature. On the other hand, they ignore some of the data when extracting the digest. It's clearly one piece of data!) Granted, this particular design, e=3 and all, *may* be particularly vulnerable to mistakes. Until we know whether this is *one* mistake that was copied from implementation to implementation, or the same mistake made by multiple developers, it's really premature to draw any conclusions. But assume that's so. Then indeed it's prudent to avoid e=3 - more because of the likely number of broken implementations out there that will take forever to move out of active use than for any other reason. But let's not draw the wrong conclusion. Bad code is bad code. The error in reasoning here is not all that different from what happens in various kinds of attacks, where for example the length of a contained record is marked as larger than the length of the containing record, is not checked separately - and produces a buffer overflow. This is also related to an error in the C library design. When comparing *for equality*, strcmp(s,t) - ignoring issues about possible missing trailing NUL's - has a very simple semantics: It compares two *strings*. The corresponding memcmp(s,t,n) is usually thought of as similarly comparing two memory regions - but that's *not* what it does. To really compare two memory regions, it would have to have accept two memory regions as inputs - that is, have separate pointers and a lengths to give memcmp(s,m,t,n). As it stands, the programmer given two memory regions is left with the task of coming up with the right value for n. In fact, what he *should* do is first compare the two lengths and decide not equal if they differ. In practice, programmers often use the minimum of the two lengths for n, which actually tests one region and one leading substring of another. Not what they had in mind - and indeed earlier in this thread we saw exactly this produce buggy code. (BTW, strncmp(), the fix for unterminated strings, has the same problem: Since it has a single maximum length, it no longer has a simple semantics as a C string comparison function.) | (When the spec was written, I think the thought that someone would append | trailing garbage never cropped up, so it's never explicitly addressed). I think you'd be hard pressed to find any spec that addresses such a thing. When a spec says X is an A followed by a B, the and nothing else is implied. | Anyway, I think we agree on the point that the spec (even version 2.1) is in | some point unprecise which should be considered a bug, as it can lead to | implementation flaws. And yes, given what we know, e=3 is a good candidate | for elimination :) | | Yup :-). I think you're putting the blame in the wrong place. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 opensslB-fake-bin.sig on messageBunicode.txt which can be validated using the new key I generated bellow. I took the same s that I computed beforehand, without reducing it this time. The value s is independent of the value of the modulus of the public key (only dependency is the size) So here are the instructions, once again (but I bit simplified): I followed the instructions of Hal Finney's excellent post: http://www.mail-archive.com/cryptography@metzdowd.com/msg06537.html I started out by generating 3072 RSA key pair, with public exponent e = 3. openssl genrsa -des3 -3 -out my.key 3072 (make sure that the modulus is really 3072 bits, no less no more). the resulting key can be found at the end of this post, the passwords is test if you ever want to use it. I also included the public key certificate by itself. All in PEM format. I created a plaintext message messageBunicode.txt on which I want to forge a signature. The file can be found in attachment, it is in Unicode because I wanted to also try this out with a VBscript implementing a signature function using CAPICOM, in which all plaintext is transformed into UNICODE (pretty annoying!). The hash of this file is openssl dgst -sha1 messageBunicode.txt SHA1(messageBunicode.txt)= 5d89b46034e0f41a920b2fa964e230ebb2d040b0 Now, let's create a valid signature over messageBunicode.txt using the private key, just to see what the output looks like: openssl dgst -hex -sha1 -sign my.key messageBunicode.txt Enter pass phrase for my.key: SHA1(..\messageBunicode.txt)= bb029c611d34e98188eb23bd1a836ec7305e94fc726577a59c8dab927fb6c5b3fce549be389f 6b15d8608c15a256f4209c7e76ed1186d8382242d53ee36e47b2d8ccb09be0440dcdcb373e37 967cfbe9d38b12a16dc9aa78e20e1303f8033f27b4c679dc215ac56b4bf33edc2c50f73d3da9 424bc072de81674b1905020546a9e57e3f96ceef7932751b94883f0409577ed7c0aa8cbed272 8dabf2a6df334357df2cabf7f5282107b6ec99e2bf0f65cd992a97f2f3e004e35739a368823c 4c0cebe4fdff53a9f039c2d85e57feff81284c7db97823359d9982da23707c8a48923e16e09e 13803cb5da3d87b94d32b5241198d91d490a3d1b343448b528e853d2add80679054e39e2e21c 1096ba66100ea73559c283c4f281fbf82fa292e6bc1dc5df5773affc3ea2425ce95ac779e7d7 90f59d11e3527d5645d9580bbf68909c2a1c4672204859cf46caa247186d917241a79224c9b6 95499644aeea43daefdc5438e9b96952771f1fbc809655ef5a5a5a148ffd47197369f4a85498 3220596a Now, let's do some bignumber math. I wanted to look at the value obtained when you verify a signature (RSA encrypt the signature with exponent 3). I use BC, a bignumber calculator I like allot: http://www.gnu.org/software/bc/ A version that can be installed on Windows: http://gnuwin32.sourceforge.net/packages/bc.htm I use a fast modexp function I implemented for BC, available at http://crypto.cs.mcgill.ca/~stiglic/Programming/modgroup.bc You can load it by simply calling bc like this: bc modgroup.bc I did all the calculations in hex, so typed the following in bc obase=16 ibase=16 Now, denote by sp the signature given above, e = 3 and m is the modulus in the public key certificate I generated. When pasting the values into BC, the hex digits need to be in capital letters. You can get the value of the modulus by using an ASN.1 interpreter, such as ASN.1 Editor or Peter Gutmann's dumpASN1 program. Here are the BC calculations: sp BB029C611D34E98188EB23BD1A836EC7305E94FC726577A59C8DAB927FB6C5B3FCE5\ 49BE389F6B15D8608C15A256F4209C7E76ED1186D8382242D53EE36E47B2D8CCB09B\ E0440DCDCB373E37967CFBE9D38B12A16DC9AA78E20E1303F8033F27B4C679DC215A\ C56B4BF33EDC2C50F73D3DA9424BC072DE81674B1905020546A9E57E3F96CEEF7932\ 751B94883F0409577ED7C0AA8CBED2728DABF2A6DF334357DF2CABF7F5282107B6EC\ 99E2BF0F65CD992A97F2F3E004E35739A368823C4C0CEBE4FDFF53A9F039C2D85E57\ FEFF81284C7DB97823359D9982DA23707C8A48923E16E09E13803CB5DA3D87B94D32\ B5241198D91D490A3D1B343448B528E853D2ADD80679054E39E2E21C1096BA66100E\ A73559C283C4F281FBF82FA292E6BC1DC5DF5773AFFC3EA2425CE95AC779E7D790F5\ 9D11E3527D5645D9580BBF68909C2A1C4672204859CF46CAA247186D917241A79224\ C9B695499644AEEA43DAEFDC5438E9B96952771F1FBC809655EF5A5A5A148FFD4719\ 7369F4A854983220596A m C68C6FEA9A08822C1DA79D4D975F95BF9EB56A906A66F7B63AF7CFC5B7A43012DDB4\ 2779002AFE4109922FA7B98CECDED22CADDBF1B1F116C79E9068D62A3B371318EA1C\ 56CA2106F196D0E6E8DE2D95D300935F5942638220073E311EB59FE9E2D7F84E\ F753A415E47E42604175F4B7F1AF52838B0BBA5769120B8DAFA1FFB5C96D961BA1E5\ 20717202DE09379F34960F03FE196F0A97704BFE32A5DF0D81445E8DDBAF750B5213\ 3EBF07D4859032AE392F161544BE5860579ABA6A6F34395D44754DC24C5C37D90F7F\ 017F7225F4EA20D4EADD7BEAFA9025D6D58B49DB151FB6C5C5F2CF6BE9175DCFE96D\ 5B752C00D71F032C6E89DEE85514816C50AC70D53A6417B30E93EA640E0E274BE926\ 4E94C9D1BE835EE252EB9550AFB7E26DCD3E42407F0797332562C2CA202A5A7C200A\
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\ \ FFF003021300906052B0E03021A05000\ 4145D89B46034E0F41A920B2FA964E230EBB2D040B00\ \ 02A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\ 1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\ 743B52BBFA7B9697DA285694CD9347AB7528\ D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\ 85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\ 81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E5324000\ 0 This has the form we are looking for, the 01 FF FF ... FF header that ends with 00, and then we have 03021300906052B0E03021A050004145D89B46034E0F41A920B2FA964E230EBB2D040B0 which is the d we started out with, and the rest is the GARBAGE part. Only one problem, s^3 is larger than m, so if we computed modexp(s, 3, m) the result would be rounded out modulo m and we would loose the above structure. This is not correct. I counted, and the number shown above has 762 hex digits. It is 3057 bits long, compared to m which is 3072 bits. It is not bigger than m, and does not need to be adjusted. 3057 is precisely the correct number of bits for a PKCS-1 padded value for a 3072 bit exponent. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Exponent 3 damage spreads...
Anton, Here is what I compute in Maple. I wonder if you are running into an old BC bug. I don't remember the details, but bc had a bug some 10 years or so ago with big numbers. with(numtheory): s:=convert(`00D3CDA91B578B6DF29AEB140272BD9198759F79FA10DC410B5D10362048AC7A BE5DF7FE0D94A6646E791C5B95B29F2C6384A570769DC888ED0B7AD510CCD3C758CEBEB64851 1620490E0FD54162BADB1ED05411ACC853509B62A4C1B242E1E2F737A1E7E4340F5A79B05EC3 475D7BA6FC7B3302F1258ABAC1079F11E8DFB9FC09D42716BA4054ADD460BB12FC1B0B8D5D32 DB50395374AEB3C215C2BC566328D2F03BF043068C5C9ABC649BA1767E97DF32B6AA734594EE 22FFFE7FB06EA3B77030E79BD6FE7683AB7FFCE462ABFBA5777B3914DE4665B86C1EC203FEB6 FCCB3DADB8BA51FD87A7457C62385418E65D17809C4256E3D27DC2017D7A093C8BD193A09168 F34D522DD7D3AFB95FC61C9F4339091CF25D78BF461B4EA5620EED722AB7D3EFF99CEA4A4F54 6BFF6CE338D7763AFF20A9B61452DA07179590D3316BBCE63B06B43D996D775D6843F46633FF 107A3C866E3B0A8AAAEA31F4A2048C9FCB448958287F8E961C9F3393E18FC9A05460D51A2867 37AEC14A1A7B27A51`,decimal,hex): m:=convert(`01D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796 918C3DC7A5951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D61A5 474491BF0D68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3DC298F9E584F FF3C7DBB8F703A0EAD97167F88C7229BBFA55B449CDE4C91B409D5B9ACF0134CB61352E9CE6C B3D847C7F3D9AFA74E8E19DD1ED7923270E310A5D91E97EF198694465950715AA066ACB06FAE C0BA64FCCCA155104852EFD41346F75D1ACB8574BBE3C7C8D6D1B501C1163AD2058506DF1B64 059A6932C0672FB9D094364EA4D7FA04442B8E643B74B8746B594866C7CBDAB8FEA954FDEE7C 44B9C5D6B9E19B49082D65B517EA7DBFEF5CA1EEA39AB2283CDB854C8B246F2B8EFE51895349 640248A3248EC65F64A89CA5AB194B444DF676B015AFBCACE13697CEEB5268F5E9AA674A83DD 1B0CE4DC83603CFFB801DB669216FC647CD7A6A84831E421D9676C7AAC44411B2AB3E901A713 9B3519B58EBAEEC20B`,decimal,hex): c:=s^3 mod m: convert(c,hex); 1B5FD52F9033ADD581101429F83B600AB9280AF9F448FCAF1F8F3D1375D526A390\ B949DE72773778D4C4C1A517730A90BA1DDC5DAEACE248534B1ECBF53B8957\ E595A8097D6828E1D05E9B7207EAA8425CC54365D78AEC13A53713AA6B44E5\ E63860824D0748184208398611253CC08E2AACE1ED62FDEB85403507512F90\ 296CEC26A05194C1332792468AC83D8411F4A1609799F7AAE9E60C84B33EDB\ E4CD590D58A5483A9A94B52853E7CF81DBFEECCD922AB1D954F9FEA40C22BB\ 575A094730F9F2AE5ECDD023AB37740984F5289F2C3900512974BE878D1A8D\ D880A871BEF9FE3C18A28DA9A40ABFF0B1288DFC9BA6971883E7263500BACC\ 458E3F9D1847BE6D542948363E8544BC2E7890580063D322DA203172FADA62\ B8D42A7959DA60CB6DC5CB90DB9E3F046F2AE816524FF5D112EB2CAC0E7D96\ 365550E68EAEA1EB2C17E63EC51719F4299A7FF68DD544FD2A6639F9B991F7\ 9F4497EAF86EA7E8964B28125772414BDA2369EA39994D972B863C2E46072D\ 56CEFF7E54A5774F1 c2:=m^3 mod s: convert(c2,hex); 89DB60414C5FE1762638AE4C61C0B485812C50E711FD7EAFA34544208E4E110F2A\ 04EDCF5CD2A71F13EC1640606DB7A49F6FD15E91269D5FF325FD6ECA6E\ 80FFDD9DC196E199DA55D69259E6022910598A886A4AFDC196C641B5BFF9C6\ 18D5EC1429C669D37C6A9B64EFDDF146C1774261B7CC9D53D360AC0B072546\ 568699A354E85BACA05119C09C5EE92A05B8AFE4BDBD725171A19F687AFE8B\ B28000181201CD7534C7D2A62B53796173BCA080630212CDD60D92A4E00E14\ 446748873F05AF14DBDECD5B5143F01C26A91A510623926DAADEADA8E16D6F\ 52C4184035767A2109197147D2279CDA312897CD346B5C8D0C7BFAE33CE33C\ C7C94E7C2CD66B212D99ADC15373E9815893F44B9510140395DB5EAC436E09\ 71E9D05EF760E477B58713B770A3FE61E37B2456543D8865D3272CC89F7390\ 03770446F4FD6CACA14BDCD7C5050774516C77456958BAF794ADE9A8BDB8A4\ 9092631DD467B0158BFBA416164D81DC8DE5C9D75118DA5BDB0CB121DC0C11\ 5271451781B4D0F -Original Message- From: [EMAIL 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 (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 (the likelihood of which is far from negligible). Unfortunately, I don't have much more time to play with this. I decided to share the methodology I used with those of you who are interested in case the info is helpful to anyone, or someone can tell me why the signature I produced doesn't get validated by OpenSSL. I followed the instructions of Hal Finney's excellent post: http://www.mail-archive.com/cryptography@metzdowd.com/msg06537.html I started out by generating 3072 RSA key pair, with public exponent e = 3. openssl genrsa -des3 -3 -out my.key 3072 the resulting key can be found bellow, the passwords is test if you ever want to use it. Then I created the corresponding public key certificate: openssl req -new -x509 -days 1001 -key my.key -out my.cer The public key certificate can be found bellow as well. You can import
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. No, it's a bug in the spec: 9.4 Encryption-block parsing [...] Nothing in there about trailing garbage. Actually, this part is about _encryption_, we are talking here about signature padding. But the PKCS#1 spec talks about building up the complete padded signature input at the verifier, and then comparing it. However, there is a note saying that alternatively one could parse the padding without saying how this would be done. The reason to use such a thing is given as saving intermediate memory. Oh well! So in fact what a lot of implementors do, parsing the padding, is not specified in sufficient detail to get it right. I would consider this buggy implementation resulting from buggy specification. Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 standards were created*, talks about ..., not the PKCS #1 spec as a whole. I even quoted the original text of the spec in my message. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 PKCS #1 spec, that didn't exist at the time the the affected other standards were created*, talks about ..., not the PKCS #1 spec as a whole. I even quoted the original text of the spec in my message. It might have helped if you indicated that the citation was from the PKCS#1 standard version 1.5 (?). Interestingly, I find there (version 1.5) also 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 message-digest algorithm for the next step. It is an error if the message-digest algorithm identifier does not identify the MD2, MD4 or MD5 message-digest algorithm. Here, any trailing garbage would be included in data D. But does an ASN.1 value allow such a thing? I am asking this independently of our discussion here. Anyway, I think we agree on the point that the spec (even version 2.1) is in some point unprecise which should be considered a bug, as it can lead to implementation flaws. And yes, given what we know, e=3 is a good candidate for elimination :) Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Exponent 3 damage spreads...
Thanks for taking the time to look at this. But I recounted, and I count 765 hex (with the formatting I get in my mail, 11 lines of 68 hex + 17 hex at the end), which gives 3060 bits. Considering that the first hex is 1 and can be represented in 1 bit, not for, that would give 3060 - 3 = 3057 bits. The modulus is the same size, but starts with 1D instead of 1F (the beginning of s^3), so s^3 is bigger. My bc library has a function called bits which returns the number of bits, I get 3057 in both cases, see bellow (also look at the value of m - s, which is negative, and modexp(s, 3, m) which doesn't have the form we want, but modexp(s/100, 3, m) does). But I seem to remember now that in openssl, mod(x, y) doesn't always return a value which is between 0 and y, maybe it would accept my s. Will try it. --Anton m 1D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796918C3\ DC7A5951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D6\ 1A5474491BF0D68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3D\ C298F9E584FFF3C7DBB8F703A0EAD97167F88C7229BBFA55B449CDE4C91B409D5B9A\ CF0134CB61352E9CE6CB3D847C7F3D9AFA74E8E19DD1ED7923270E310A5D91E97EF1\ 98694465950715AA066ACB06FAEC0BA64FCCCA155104852EFD41346F75D1ACB8574B\ BE3C7C8D6D1B501C1163AD2058506DF1B64059A6932C0672FB9D094364EA4D7FA044\ 42B8E643B74B8746B594866C7CBDAB8FEA954FDEE7C44B9C5D6B9E19B49082D65B51\ 7EA7DBFEF5CA1EEA39AB2283CDB854C8B246F2B8EFE51895349640248A3248EC65F6\ 4A89CA5AB194B444DF676B015AFBCACE13697CEEB5268F5E9AA674A83DD1B0CE4DC8\ 3603CFFB801DB669216FC647CD7A6A84831E421D9676C7AAC44411B2AB3E901A7139\ B3519B58EBAEEC20B s 7FFF\ \ FFEAAEAD6EAB6B2B18EBD595822B1555\ AC5D20CF08046814578C2B994E1DBD8413A43C05640 bits(m) BF1 bits(s^3) BF1 m - s^3 -27AE2AEB7CBA9F90A796CA2DD832A3080FB076F53AFDBE8745A0B117A288696E73C\ 2385A6AE367AAC634DBF1D745B53C5041F0914CEAE5F245029793DCB5CF2F82A6F29\ E5AB8BB6E40F2971E53806B3236763E63D1DA4DDB1E7E900E10140D0269B4003F3C2\ 7EACDEB5C1035A4765F029AF59AB74B1A6C2A091E14405AA4BB6321B36E4BF62A465\ 30FECB349ECAD1631934C27B8380C265058B171E622E1286DCD8F1CEF5A26E16810E\ 6796BB9A6DA29467C54B41AC61C95E3785A9F85D4578F21C056D03ECF9128580717D\ 563B5F437FEB9CDCAAE7E01D6C84F908AF5336EC3D710D6DF1F282A270E150F32438\ 31826C7843300F514A6B799383425470156AB021183BB4637CBCB87B1902C4D519D7\ 52B7C10EC94263DF2E26A5466F17150A2E4E2745BD967E5CC8352D58EE7A5237E637\ 3B36C59357EE1C3BCBBAE5A3EBFA812347B2D71FF03ECAD84A80E22419EA004D6C73\ 4BD35CE67B61094E6292B8E8BA5005F3D0F436A6C0EE1F47EDAFD37F94C16FE58EC6\ 4CAE64A7145113DF5 modexp(s, 3, m) 27AE2AEB7CBA9F90A796CA2DD832A3080FB076F53AFDBE8745A0B117A288696E73C2\ 385A6AE367AAC634DBF1D745B53C5041F0914CEAE5F245029793DCB5CF2F82A6F29E\ 5AB8BB6E40F2971E53806B3236763E63D1DA4DDB1E7E900E10140D0269B4003F3C27\ EACDEB5C1035A4765F029AF59AB74B1A6C2A091E14405AA4BB6321B36E4BF62A4653\ 0FECB349ECAD1631934C27B8380C265058B171E622E1286DCD8F1CEF5A26E16810E6\ 796BB9A6DA29467C54B41AC61C95E3785A9F85D4578F21C056D03ECF9128580717D5\ 63B5F437FEB9CDCAAE7E01D6C84F908AF5336EC3D710D6DF1F282A270E150F324383\ 1826C7843300F514A6B799383425470156AB021183BB4637CBCB87B1902C4D519D75\ 2B7C10EC94263DF2E26A5466F17150A2E4E2745BD967E5CC8352D58EE7A5237E6373\ B36C59357EE1C3BCBBAE5A3EBFA812347B2D71FF03ECAD84A80E22419EA004D6C734\ BD35CE67B61094E6292B8E8BA5005F3D0F436A6C0EE1F47EDAFD37F94C16FE58EC64\ CAE64A7145113DF5 modexp(s/100, 3, m) 1FFF\ \ FFF003021300906052B0E03021A05000\ 4145D89B46034E0F41A920B2FA964E230EBB2D040B00\ \ 02A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\ 1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\ 743B52BBFA7B9697DA285694CD9347AB7528\ D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\ 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 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\ \ FFF003021300906052B0E03021A05000\ 4145D89B46034E0F41A920B2FA964E230EBB2D040B00
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 further anomalies, then you modify it again, and again, ... Alternatively, you say that the earth revolves around the sun, and all of the kludges upon kludges go away. 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 This is never going to be reliably fixed if the fix is to assume that every implementor and implementation everywhere can get every miniscule detail right every time. The fix is to stop using e=3 and be done with it. Not using e=3 when generating a key seems like an easy sell. A harder sell might be whether widely deployed implementations such as TLS should start to reject signatures done with an e=3 RSA key. What do people think, is there sufficient grounds for actually _rejecting_ e=3 signatures? One alternative would be to produce a warning, similar to what is sometimes done for MD2 and MD5 today. Btw, by default, OpenSSH's ssh-keygen appear to use e=35 (0x23..), GnuPG (libgcrypt), GnuTLS and OpenSSL appear to all use e=65537, BIND dnssec-keygen appear to use e=3. /Simon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 identifier shall determine the selected message-digest algorithm for the next step. Here, any trailing garbage would be included in data D. But does an ASN.1 value allow such a thing? I am asking this independently of our discussion here. 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 outside it is beyond the scope of this specification :-). (When the spec was written, I think the thought that someone would append trailing garbage never cropped up, so it's never explicitly addressed). Anyway, I think we agree on the point that the spec (even version 2.1) is in some point unprecise which should be considered a bug, as it can lead to implementation flaws. And yes, given what we know, e=3 is a good candidate for elimination :) Yup :-). Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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. The PKCS#1 attack will work with e = 17, SHA-512 and RSA-15360, and someone's bound to implement RSA-15360 somewhere to claim 256-bit security. NIST's draft revision of FIPS 186-3 says (b) The exponent e shall be an odd positive integer such that 65,537 = e 2**(nlen - 2*security_strength) where nlen is the length of the modulus n in bits. The security_strength is the work factor for brute force attack on the corresponding symmetric cipher or hash function, i.e., 128 for SHA-256. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 (the likelihood of which is far from negligible). Unfortunately, I don't have much more time to play with this. I decided to share the methodology I used with those of you who are interested in case the info is helpful to anyone, or someone can tell me why the signature I produced doesn't get validated by OpenSSL. I followed the instructions of Hal Finney's excellent post: http://www.mail-archive.com/cryptography@metzdowd.com/msg06537.html I started out by generating 3072 RSA key pair, with public exponent e = 3. openssl genrsa -des3 -3 -out my.key 3072 the resulting key can be found bellow, the passwords is test if you ever want to use it. Then I created the corresponding public key certificate: openssl req -new -x509 -days 1001 -key my.key -out my.cer The public key certificate can be found bellow as well. You can import this in Windows key store, for example. I then created a plaintext file, messageAunicode.txt, for which I computed a signature on (a valid signature). The idea was then to forge a signature on an alternate messageBunicode.txt, without using the private key of course. The two files can be found in attachment, they are in Unicode because I wanted to also try this out with a VBscript implementing a signature function using CAPICOM. (you can get a file in Unicode by opening it with a simple text editor that allows you to save as Unicode, such as notepad, and erase any extra bytes (header) with a hex editor such as XVI32). The hashes of these files are openssl dgst -sha1 messageAunicode.txt SHA1(messageAunicode.txt)= eb8302606217ae549fe6ab1345f0b4c804195367 openssl dgst -sha1 messageBunicode.txt SHA1(messageBunicode.txt)= 5d89b46034e0f41a920b2fa964e230ebb2d040b0 Now, create the valid signature over messageAunicode.txt to see what the output looks like: openssl dgst -hex -sha1 -sign my.key messageAunicode.txt Enter pass phrase for my.key: SHA1(messageAunicode.txt)=00d3cda91b578b6df29aeb140272bd9198759f79fa10dc410b 5d10362048ac7abe5df7fe0d94a6646e791c5b95b29f2c6384a570769dc888ed0b7ad510ccd3 c758cebeb648511620490e0fd54162badb1ed05411acc853509b62a4c1b242e1e2f737a1e7e4 340f5a79b05ec3475d7ba6fc73b3302f1258abac1079f11e8dfb9fc09d42716ba4054add460b b12fc1b0b8d5d32db50395374aeb3c215c2bc566328d2f03bf043068c5c9abc649ba1767e97d f32b6aa734594ee22fffe7fb06ea3b77030e79bd6fe7683ab7ffce462abfba5777b3914de466 5b86c1ec203feb6fccb3dadb8ba51fd87a7457c62385418e65d17809c4256e3d27dc2017d7a0 93c8bd193a09168f34d522dd7d3afb95fc61c9f4339091cf25d78bf461b4ea5620eed722ab7d 3eff99cea4a4f546bff6ce338d7763aff20a9b61452da07179590d3316bbce63b06b43d996d7 75d6843f46633ff107a3c866e3b0a8aaaea31f4a2048c9fcb448958287f8e961c9f3393e18fc 9a05460d51a286737aec14a1a7b27a51 Now, let's do some bignumber math. I wanted to look at the value obtained when you verify a signature (RSA encrypt the signature with exponent 3). I use BC, a bignumber calculator I like allot: http://www.gnu.org/software/bc/ A version that can be installed on Windows: http://gnuwin32.sourceforge.net/packages/bc.htm I use a fast modexp function I implemented for BC, available at http://crypto.cs.mcgill.ca/~stiglic/Programming/modgroup.bc You can load it by simply calling bc like this: bc modgroup.bc I did the calculations all in hex, so typed the following in bc obase=16 ibase=16 Now, denote by s the signature given above, e = 3 and m is the modulus in the public key certificate I generated. When pasting the values into BC, the hex digits need to be in capital letters. You can get the value of the modulus by using a ASN.1 viewer, such as ASN.1 Editor or Peter Gutmann's ASN1dump. Here are the BC calculations: s=00D3CDA91B578B6DF29AEB140272BD9198759F79FA10DC410B5D10362048AC7ABE5DF7FE0D 94A6646E791C5B95B29F2C6384A570769DC888ED0B7AD510CCD3C758CEBEB648511620490E0F D54162BADB1ED05411ACC853509B62A4C1B242E1E2F737A1E7E4340F5A79B05EC3475D7BA6FC 7B3302F1258ABAC1079F11E8DFB9FC09D42716BA4054ADD460BB12FC1B0B8D5D32DB50395374 AEB3C215C2BC566328D2F03BF043068C5C9ABC649BA1767E97DF32B6AA734594EE22FFFE7FB0 6EA3B77030E79BD6FE7683AB7FFCE462ABFBA5777B3914DE4665B86C1EC203FEB6FCCB3DADB8 BA51FD87A7457C62385418E65D17809C4256E3D27DC2017D7A093C8BD193A09168F34D522DD7 D3AFB95FC61C9F4339091CF25D78BF461B4EA5620EED722AB7D3EFF99CEA4A4F546BFF6CE338 D7763AFF20A9B61452DA07179590D3316BBCE63B06B43D996D775D6843F46633FF107A3C866E 3B0A8AAAEA31F4A2048C9FCB448958287F8E961C9F3393E18FC9A05460D51A286737AEC14A1A 7B27A51 m=01D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796918C3DC7A5 951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D61A5474491BF0D 68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3DC298F9E584FFF3C7DBB8F
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 error if any of the following conditions occurs: oThe encryption block EB cannot be parsed unambiguously (see notes to Section 8.1). oThe padding string PS consists of fewer than eight octets, or is inconsistent with the block type BT. oThe decryption process is a public-key operation and the block type BT is not 00 or 01, or the decryption process is a private-key operation and the block type is not 02. Nothing in there about trailing garbage. Someone else said that the spec requires creating an encoded form of the ASN.1 data and then comparing the encoded form. Let's look at the spec again: 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 message-digest algorithm for the next step. Again, there's nothing in there that requires comparing the encoded form. You may be wondering why this differs somewhat from RFC 3447. That's because this is the original gold standard PKCS #1 spec, the one that everyone was using when PGP, PKCS #7/S/MIME, SSL, and possibly DNSSEC were created. True, since then other variants of the spec have imposed slightly different requirements, but the gold standard version that's contemporaneous with the security protocols in which it's caused problems doesn't require the measures that people have been claiming. (And I really, *really* don't want to get into some pointless debate over whose bits are more standards-compliant. All I'm pointing out is that a blanket assertion that doing/not doing X is a violation of the spec is an invalid claim. At best you can say doing X is a violation of one variant of the spec that didn't actually exist when the affected protocols were created). If your implementation supports appending additional parameter fields of some general structure, then you have not implemented conventional PKCS#1.5 signatures as they are usually understood; instead, you have implemented some extension. No, you've implemented PKCS #1 exactly as the specification says. Look up the definition of AlgorithmIdentifier. Why are people still deploying cryptographic schemes that haven't been properly validated? Because everyone else on the planet is doing it, and (with a few caveats) it's worked so far. If you're quite happy to not be able to talk to anything else in existence, you're welcome to use PSS or whatever's in fashion at the moment. Since my users expect to be able to, you know, talk to one another, I'll stick with PKCS #1. 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 further anomalies, then you modify it again, and again, ... Alternatively, you say that the earth revolves around the sun, and all of the kludges upon kludges go away. 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 This is never going to be reliably fixed if the fix is to assume that every implementor and implementation everywhere can get every miniscule detail right every time. The fix is to stop using e=3 and be done with it. Even Microsoft finally got this message after 14 years of getting RC4 wrong, they simply banned its use because they realised that they'd never get it fixed even if, in theory, it's easy to get right on paper. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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
matter of time before we see these anyway) [...]
Both Rivest and Shamir said that they want a parameterised hash
according to Paul Hoffman's Notes from the Hash Futures Panel.
URL: http://www.proper.com/lookit/hash-futures-panel-notes.html
Having a standard parametised hash function does not necessitate that
ASN.1 instances of their output have to be parametised too. IMO it
would make more sense to pick a progression of sizes similar to
SHA{1,256,...}
-d
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 bugs (failures to implement the spec faithfully); and (b) ad hoc signatures schemes that have never been adequately validated. In more detail: (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. Of course, as we know, if you use buggy implementations that fail to implement the specification faithfully, all bets are off (b) The discussion of parameter fields in PKCS#1.5 signatures illustrates a second, orthogonal problem. If your implementation supports appending additional parameter fields of some general structure, then you have not implemented conventional PKCS#1.5 signatures as they are usually understood; instead, you have implemented some extension. That raises a natural question: Why should we think that the extended scheme is still secure? When a protocol is successful, pretty soon it comes in a large number of variants, all of which have to coexist - the original version, several upgraded versions, different interpretations of the spec, buggy interpretations of the spec and Microsoft style embrace and extend interpretations of the spec designed to deliberately hamstring interoperability. Therefore one generally makes provisions for future expansion - for additional fields in a record, additional types of records. ASN.1, S-expressions, and XML permit essentially limitless future fields. That is dangerously great flexibility. On the other hand, TCP format turned out to permit too little flexibility. GPG's concept of records seems to me are reasonable way of providing future expansion, without requiring the programmer to handle potentially limitless future expansion of every possible bit of organized data, a task at which the programmer is likely to fail. In general, a communication should tell what program and version the communication is coming from, so that future programs can say oh, I am talking to someone old fashioned, so must talk in the old fashioned dialect. (Though for conciseness, this probably should not be in human readable form, but in some cryptic set of bytes that are agreed to stand for some particular program.) It should also be able to specify that it is like some other program, some program that became a de facto standard that everyone has to be able to interoperate with, saying If you don't recognize me, assume I am this other program, and it will work well enough. The communication should also identify that it is in accord with some particular standards document (again, probably with a cryptic set of bytes rather than a verbose url), so that the recipient knows that this communication version 1.0 format, or version 1.1, or the emergency fixed version of version 1.1, though if the standards document was good enough, which it seldom is, it would not be necessary for the program to identify itself, or to reference particular concrete implementations. But still, we likely need programs that only understand 1.0 format to have some success when they receive 1.1 format, and this is where the expandability of ASN.1 and the rest is useful - and dangerous. I would suggest that communication occurs in records that correspond to database records and to C++ objects, and that some records be defined with provision for future expansion, and other records not so defined, according to the judgment of the people defining the original protocol. With ASN.1, XML, and S-expressions, *everything* has provision for future expansion, which I suggest is dangerously excessive. If the 1.0 protocol contains an error, they find that the 1.1 protocol needs some more fields in the record, and no provision has been made for future expansion, then they either define a new type of record replacing the old, (thereby guaranteeing that 1.0 programs will fail to interoperate when this new record is used) or define an additional record supplementing the old, which the 1.0 programs will ignore, handling only the records they recognize. Coming back to the case at hand, we should have had a signature record that only allowed a one particular kind of hash, and nothing but the hash, and no future expansion, then when people realized that was a problem, that unforeseen new hashes would need to be introduced over time, they should have then introduced an incompatible signature record that defined the hash type, and the hash, and allowed for no future expansion. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG /zedskWwjM7YJCe3zo2C7y0GDwUQjP+BN9ayEeww
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 algorithms, including any that allow parameters, is most likely toast. Parameters should not be expressed in the relevant part of the signature. The only data that should be encrypted with the RSA private key and decrypted with the public key is the hash result itself, and the padding. If the standard specifies that additional material should be encrypted, the standard is in error and no one should follow it. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG sVNWfKHHWrogEro6rkjKzE2XEHGqyk1tXLiayWU7 4joW/r8h3DIfdlwaI5up/06PSaWuhEtwMmF9TsuGR - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 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 algorithms, including any that allow parameters, is most likely toast. 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), then changing a simple AlgoID definition in one part of the code is going to suddently break signatures 23 code modules away in a different directory. Will whoever's responsible for maintaining the hash AlgoID table in some far-removed code module in several years' time know that any change they make could cause a security breach via a non-obvious mechanism in a far-distant piece of code? This is just going to keep coming back and biting us again and again unless we default to deny-all. The e=3 issue is like the old war movies where someone steps on a mine and hears the click, but isn't quite sure yet how long it'll be before they spread themselves decoratively around the countryside. We've heard the click, it's time to get out of the minefield. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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. What is wrong with it, what alternatives are there to it, or how can it be fixed? In SPKI we used S-Expressions. They have the advantage of being simple, perhaps even too simple. In describing interfaces in the KeyKOS design document http://www.cis.upenn.edu/~KeyKOS/agorics/KeyKos/Gnosis/keywelcome.html we used a notation similar to S-Expressions which was: (length, data) These could be combined into a structure: e.g. (4, len), (len, data) for data proceeded by a four byte length field. If you standardize that the data is always right justified in a field of length len, and that binary data is encoded with a standard encoding (hexadecimal, 6-bit/character, decimal etc.), most of the problems I have seen described in this thread should just go away. Some might object that having a specific number of bits for the length field limits future expansion of this approach. Indeed, ASN.1 avoids this issue by allowing the encoding of infinite length integers, and XML does the same. The cost of that flexibility is much more difficult encoding and decoding. If a length field length of 4 to 8 bytes (32 to 64 bits) is chosen, as a practical matter, any length data that is transmittable in an exchange can be represented. (A terabit/second is 10**12 bits/second. 32 bits can represent a million seconds at that data rate. 64 bits can represent much longer data items.) Cheers - Bill --- Bill Frantz| gets() remains as a monument | Periwinkle (408)356-8506 | to C's continuing support of | 16345 Englewood Ave www.pwpconsult.com | buffer overruns. | Los Gatos, CA 95032 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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) [...] Both Rivest and Shamir said that they want a parameterised hash according to Paul Hoffman's Notes from the Hash Futures Panel. URL: http://www.proper.com/lookit/hash-futures-panel-notes.html Maybe thats not so good after all. Or maybe the not so good thing here is exponent equal to 3... -- Jostein Tveit [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 invalid for an entirely unrelated reason, so no standards-compliant PKI application should validate this chain even if the signature did check out. I wonder how many current apps will detect this? See, you don't even need PKCS #1 padding tricks to fool a PKI app... :-). Peter. [2. application/octet-stream; bad_chain.der]... - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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: http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html That uses the fact that implementation doesn't check for data beyond the end of the ASN.1 structure. OpenSSL was vulnerable to this, GnuTLS was not, see my analysis for GnuTLS on this at: http://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001202.html Eric already posted test vectors that trigger this problem. 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 Crypto 06, but as far as I understand from Hal's post, this aspect was not discussed. Their analysis isn't public yet, as far as I know. 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 ASN.1 or at least difficult to say what in fact constitutes conforming to standard written in ASN.1 ASN.1 does the same job as XML, but whereas XML is painfully verbose and redundant, ASN.1 is crypticly concise. People do not seem to get XML wrong all that often, while they endlessly get ASN.1 wrong, and endlessly disagree over what constitutes being right. 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. What is wrong with it, what alternatives are there to it, or how can it be fixed? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 Crypto 06, but as far as I understand from Hal's post, this aspect was not discussed. Their analysis isn't public yet, as far as I know. Can you make a guess at what it is? Is it the fact that you can have NULL parameters for algorithms or optionally non-NULL parameters? Changing this could be tricky because there are all sorts of inconsistencies both in standards and implementations, the standard practice has been to skip the parameters field because if you don't, things break. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 was discovered by Yutaka Oiwa, Kazukuni Kobara, Hajime Watanabe. I didn't attend Crypto 06, but as far as I understand from Hal's post, this aspect was not discussed. Their analysis isn't public yet, as far as I know. Can you make a guess at what it is? Is it the fact that you can have NULL parameters for algorithms or optionally non-NULL parameters? Yes. Implementations that didn't validate the parameters field are potentially vulnerable; the attacker can put garbage in the parameters field to make the signature value a cube. In that case (and because of something else I thought of after I posted, I was just heading out for dinner at the time) I think it's game over for RSA e=3 (see below). Changing this could be tricky because there are all sorts of inconsistencies both in standards and implementations, the standard practice has been to skip the parameters field because if you don't, things break. I don't think so. The contents of the parameters field depends on the hash algorithm. As far as I know (but I didn't read the scriptures), for normal hashes like SHA-1 the parameters field should not be used. It may or may not be used, depending on which standard you follow. First of all, even for the simple case of SHA-1, the parameters can be present or not. See the note in RFC 3274: There are two possible encodings for the [...] parameters field which arise from the fact that when the 1988 syntax for AlgorithmIdentifier was translated into the 1997 syntax, the OPTIONAL associated with the AlgorithmIdentifier parameters got lost. Later it was recovered via a defect report, but by then, everyone thought that algorithm parameters were mandatory. Because of this, some implementations will encode null parameters as an ASN.1 NULL element and some will omit them entirely (see for example section 12 of CMS [RFC2630]). So for both standards and implementations it's pretty much a coin-toss (crap- shoot if you're in the US) as to what you'll find there. Because of this, standard practice in implementations has been to skip any parameters. But wait, there's more! Some AlgorithmIdentifiers have parameters that you can set to either a large range of fixed values or even arbitrary values. For example the Ascom Tech IDEA AlgoID (which admittedly isn't a hash algorithm, but bear with me) has three optional parameters for CFB mode which can take various values and may or may not be present (AES almost took this path as well, luckily NIST decided against it at the last minute and went with simple, streamlined parameters). OK, so you don't sign IDEA values so this isn't a problem. However, a related AlgoID is the DES one, which for CBC mode has as parameter an IV, which is 64- bits of arbitrary user-chosen data. I've seen a banking security system from either Belgium or the Netherlands that signs CBC-MACs (I'm using a borrowed machine to send this so I can't provide names and numbers at the moment, it's from memory), and knowing the organisation that produced it it wouldn't surprise me if they also used keys with e=3. So lets extend this further. There have been a pile of designs for hash algorithms with user-definable parameters. If these ever get used in standards then no doubt there'll be AlgoIDs defined that allow an attacker to set arbitrary values in the AlgoID through them. So the arms-race of trying to track invalid data now becomes a problem of proving a negative, i.e. proving that there isn't some AlgoID out there somewhere that allows you to set one or two parameter bytes to arbitrary values. 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 with a perfect implementation that does a memcmp() of a fixed binary string for all the data present but the hash, the attack still works. In either of these cases, RSA e=3 is dead. Obesa cantavit. So the fix isn't an ongoing penetrate-and-patch arms race to try and filter out more and more hard-to-find possibilities, it's to immediately deprecate e= 3. Grab a pile of IETF boilerplate, add a single sentence Don't use RSA with e = 3 (I'd actually say = 17 since there's no good reason not to), and apply it as a BCP by reference to SSL/TLS, IPsec, S/MIME, PGP, DNSSEC, and so on. There'll always be broken standards out there that require e=3 (I know of at least one that uses e=2, and another that uses raw, unpadded RSA, and another that... well you get the idea), but the only quick, sure fix is to kill e=3, not to try and
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 ASN.1 or at least difficult to say what in fact constitutes conforming to standard written in ASN.1 ASN.1 does the same job as XML, but whereas XML is painfully verbose and redundant, ASN.1 is crypticly concise. People do not seem to get XML wrong all that often, while they endlessly get ASN.1 wrong, and endlessly disagree over what constitutes being right. This problem is just as likely or more likely if we were using XML to encode the hash inside the RSA-encrypted blob (signature). The equivalents would be: Appended garbage: signed-hashValid-looking-hash/signed-hashGarbage here Or signed-hashValid-looking-hash/signed-hash[null byte]Garbage here Interior garbage: signed-hash legal-but-unparsed-attribute=Garbage hereValid-looking-hash/signed-hash or similar attacks. The problem is not XML or ASN.1: the problem is that it's very demanding and tricky to write parsers that are invulnerable to all the different kinds of malicious attack that are out there. If anything, I think XML is more vulnerable to such attacks because its less-structured format makes it harder to write very strict parsers. The actual way to design a system that was less vulnerable to this attack would have been to use a much simpler data structure: e.g., one could have said that the hashing algorithm must already be known, so the size of the hash is known to be n bytes, and that the data block should be a byte of value 0, followed by bytes of value FF, with the last n bytes equal to the hash. Then it would have been a no-brainer for anyone to write a precisely accurate parser and validator, and we'd be less vulnerable to such oversights. - Tim - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 with a perfect implementation that does a memcmp() of a fixed binary string for all the data present but the hash, the attack still works. I don't think this works. I tried with a 1024 bit key. We want a cube root of something between: 0x1003021300906052B0E03021A05000414 and 0x1003021300906052B0E03021A05000414 But actually the nearest cube root is: 0x1428A2F98D728AE223DDAB715BE250D0C288F10291631FBC061800CC36FA2DD3A60B7D03DA26F0840F25C Cubing this gives: 0x1FFFC66E7388AFD22947A600FB19230A3162AB4A53B003B80F979B8E97D7DB74891A5769312C88639E645DD3DB79E32561BD7FF661977573AF888EF025ED0608245DE7048210C94AC32731DD6B19B2F25722E951F41C0 and cubing the next higher value gives: 0x200012A06F78681CDECFB70DC81AEE9F1B2FF7CBB6140D9A07D97209E81A4A2D957560CB04CF8F504EF90797FEBD799E9A64841F1168C13EC938E0D109610B8CC43EF3FDA8B374E3AD57AF2A0E084B15E8BB328384C05 So no variation on the hash value will produce something that is a perfect cube. Now, this is specific to 1024 bit keys, but larger keys should be even more unfavorable. As a general rule we can only force the top 1/3 of the bits to be 1s as required, and the chances of getting lucky will be worse for larger keys. We could start adding in multiples of the modulus and look for perfect cubes again, but basically the odds against are 1 in N^(2/3) so there is no point. Hal Finney PGP Corporation - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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, what browsers used OpenSSL and/or their own broken code, and need to be patched? I have no idea. Thanks to Alex Gantman for asking the question... Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 brute-force search. So even with a perfect implementation that does a memcmp() of a fixed binary string for all the data present but the hash, the attack still works. I thought this for a while, but no, it isn't true. Take a number k, which is of the order of 2^1008 (which is what a properly padded 1024-bit RSA signature will look like numerically). So the cube root of K is a real number of the order of 2^336... call this k'. Now on average it will be within +/- 0.25 of the nearest integer, so for sake of argument let i = k' + 0.25 be an integer. i^3 - k = (k' + 0.25)^3 - k = k + 0.25*k'^2 +0.0625*k' + 1/64 - k which is of order 0.25*k^2/3, ie, 2^670. Unless you are using very large hashes indeed, the chance of a properly padded RSA signature being a perfect cube is vanishingly small. In either of these cases, RSA e=3 is dead. Obesa cantavit. I don't yet agree with this conclusion. There'll always be broken standards out there that require e=3 (I know of at least one that uses e=2, and another that uses raw, unpadded RSA, and another that... well you get the idea), but the only quick, sure fix is to kill e=3, not to try and anticipate every potential way of trying to use it, because you'll never be secure that way. I just have to mention that e=2 is Rabin signatures, and they have different and very stringent requirements for signatures. Maybe the same problem exists, maybe it doesn't, I don't know. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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:
http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html
That uses the fact that implementation doesn't check for data beyond
the end of the ASN.1 structure. OpenSSL was vulnerable to this,
GnuTLS was not, see my analysis for GnuTLS on this at:
http://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001202.html
Eric already posted test vectors that trigger this problem.
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 Crypto 06, but as
far as I understand from Hal's post, this aspect was not discussed.
Their analysis isn't public yet, as far as I know.
Both OpenSSL and GnuTLS were vulnerable to the second problem. My
discussion of this for GnuTLS is in:
http://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001205.html
When I read the OpenSSL advisory, I get the impression that it doesn't
quite spell out the second problem clearly, but if you look at the
patch to correct this:
+ /* Excess data can be used to create forgeries */
+ if(p != s+i)
+ {
+ RSAerr(RSA_F_RSA_VERIFY,RSA_R_BAD_SIGNATURE);
+ goto err;
+ }
+
+ /* Parameters to the signature algorithm can also be used to
+ create forgeries */
+ if(sig-algor-parameter
+ sig-algor-parameter-type != V_ASN1_NULL)
+ {
+ RSAerr(RSA_F_RSA_VERIFY,RSA_R_BAD_SIGNATURE);
+ goto err;
+ }
+
You'll notice that there are two added checks, one check per problem.
Test vectors for this second problem are as below, created by Yutaka
OIWA.
[EMAIL PROTECTED]:~/src/gnutls/tests$ cat pkcs1-pad-ok.pem
-BEGIN CERTIFICATE-
MIICzTCCAjagAwIBAgIJAOSnzE4Qx2H/MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTY0MDM3WhcNMDcwOTA3MTY0MDM3WjBPMQswCQYDVQQGEwJK
UDEOMAwGA1UECBMFVG9reW8xFjAUBgNVBAoTDVRFU1QgMiBDTElFTlQxGDAWBgNV
BAMTD3d3dzIuZXhhbXBsZS5qcDCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEA
vSpZ6ig9DpeKB60h7ii1RitNuvkn4INOfEXjCjPSFwmIbGJqnyWvKTiMKzguEYkG
6CZAbsx44t3kvsVDeUd5WZBRgMoeQd1tNJBU4BXxOA8bVzdwstzaPeeufQtZDvKf
M4ej+fo/j9lYH9udCug1huaNybcCtijzGonkddX4JEUCAwEAAaOBxjCBwzAJBgNV
HRMEAjAAMCwGCWCGSAGG+EIBDQQfFh1PcGVuU1NMIEdlbmVyYXRlZCBDZXJ0aWZp
Y2F0ZTAdBgNVHQ4EFgQUK0DZtd8K1P2ij9gVKUNcHlx7uCIwaQYDVR0jBGIwYIAU
340JbeYcg6V9zi8aozy48aIhtfihPaQ7MDkxCzAJBgNVBAYTAkpQMRQwEgYDVQQK
EwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAxLTSCCQDkp8xOEMdh/jAN
BgkqhkiG9w0BAQUFAAOBgQCkGhwCDLRwWbDnDFReXkIZ1/9OhfiR8yL1idP9iYVU
cSoWxSHPBWkv6LORFS03APcXCSzDPJ9pxTjFjGGFSI91fNrzkKdHU/+0WCF2uTh7
Dz2blqtcmnJqMSn1xHxxfM/9e6M3XwFUMf7SGiKRAbDfsauPafEPTn83vSeKj1lg
Dw==
-END CERTIFICATE-
-BEGIN CERTIFICATE-
MIICijCCAfOgAwIBAgIJAOSnzE4Qx2H+MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTYzMzE4WhcNMDYxMDA3MTYzMzE4WjA5MQswCQYDVQQGEwJK
UDEUMBIGA1UEChMLQ0EgVEVTVCAxLTQxFDASBgNVBAMTC0NBIFRFU1QgMS00MIGd
MA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQDZfFjkPDZeorxWqk7/DKM2d/9Nao28
dM6T5sb5L41hD5C1kXV6MJev5ALASSxtI6OVOmZO4gfubnsvcj0NTZO4SeF1yL1r
VDPdx7juQI1cbDiG/EwIMW29UIdj9h052JTmEbpT0RuP/4JWmAWrdO5UE40xua7S
z2/6+DB2ZklFoQIBA6OBmzCBmDAdBgNVHQ4EFgQU340JbeYcg6V9zi8aozy48aIh
tfgwaQYDVR0jBGIwYIAU340JbeYcg6V9zi8aozy48aIhtfihPaQ7MDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTSCCQDkp8xOEMdh/jAMBgNVHRMEBTADAQH/MA0GCSqGSIb3DQEBBQUAA4GBABsH
aJ/c/3cGHssi8IvVRci/aavqj607y7l22nKDtG1p4KAjnfNhBMOhRhFv00nJnokK
y0uc4DIegAW1bxQjqcMNNEmGbzAeixH/cRCot8C1LobEQmxNWCY2DJLWoI3wwqr8
uUSnI1CDZ5402etkCiNXsDy/eYDrF+2KonkIWRrr
-END CERTIFICATE-
[EMAIL PROTECTED]:~/src/gnutls/tests$ ../src/certtool -e pkcs1-pad-ok.pem
Certificate[0]: C=JP,ST=Tokyo,O=TEST 2 CLIENT,CN=www2.example.jp
Issued by: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
Verifying against certificate[1].
Verification output: Verified.
Certificate[1]: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
Issued by: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
Verification output: Verified.
[EMAIL PROTECTED]:~/src/gnutls/tests$ cat pkcs1-pad-broken.pem
-BEGIN CERTIFICATE-
MIICzTCCAjagAwIBAgIJAOSnzE4Qx2H/MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTY0MDM3WhcNMDcwOTA3MTY0MDM3WjBPMQswCQYDVQQGEwJK
UDEOMAwGA1UECBMFVG9reW8xFjAUBgNVBAoTDVRFU1QgMiBDTElFTlQxGDAWBgNV
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. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 valid signature, and one with a signature block with an extra byte appended after the ASN.1 (but before signing). For openssl 0.9.8a [EMAIL PROTECTED] ~/workopenssl verify -CAfile cert-ok.pem cert-ok.pem cert-ok.pem: OK [EMAIL PROTECTED] ~/workopenssl verify -CAfile cert-bad.pem cert-bad.pem cert-bad.pem: OK For openssl 0.9.8c [EMAIL PROTECTED] ~/workopenssl-0.9.8c/apps/openssl verify -CAfile cert-ok.pem cert-ok.pem cert-ok.pem: OK [EMAIL PROTECTED] ~/workopenssl-0.9.8c/apps/openssl verify -CAfile cert-bad.pem cert-bad.pem cert-bad.pem: /C=AU/ST=Queensland/O=CryptSoft Pty Ltd/CN=Server test cert (512 bit) error 7 at 0 depth lookup:certificate signature failure 28900:error:04077068:rsa routines:RSA_verify:bad signature:rsa_sign.c:192: 28900:error:0D0C5006:asn1 encoding routines:ASN1_item_verify:EVP lib:a_verify.c:168: so this appears to trigger the relevant condition. For my own recent pkcs#1 implementations, they do not ASN.1 decode the signature block, rather then generate a signature block and do a memcmp with the output from the RSA decrypt. I did this since it is easy to generate small amounts of ASN.1 relative to parsing and checking all the boundary cases. In this case this 'simpler' approach seems to have paid off :-). eric [EMAIL PROTECTED] ~/workcat cert-ok.pem -BEGIN CERTIFICATE- MIIBsDCCAVoCAQYwDQYJKoZIhvcNAQEFBQAwYzELMAkGA1UEBhMCQVUxEzARBgNV BAgTClF1ZWVuc2xhbmQxGjAYBgNVBAoTEUNyeXB0U29mdCBQdHkgTHRkMSMwIQYD VQQDExpTZXJ2ZXIgdGVzdCBjZXJ0ICg1MTIgYml0KTAeFw0wNjA5MTEyMzU5MDJa Fw0wNjEwMTEyMzU5MDJaMGMxCzAJBgNVBAYTAkFVMRMwEQYDVQQIEwpRdWVlbnNs YW5kMRowGAYDVQQKExFDcnlwdFNvZnQgUHR5IEx0ZDEjMCEGA1UEAxMaU2VydmVy IHRlc3QgY2VydCAoNTEyIGJpdCkwXDANBgkqhkiG9w0BAQEFAANLADBIAkEAn7PD hCeV/xIxUg8V70YRxK2A5jZbD92A12GN4PxyRQk0/lVmRUNMaJdq/qigpd9feP/u 12S4PwTLb/8q/v657QIDAQABMA0GCSqGSIb3DQEBBQUAA0EAc+fnj0rB2CYautG2 4itiMOU4SN6JFTFDCTU/Gb5aR/Fiu7HJkuE5yGEnTdnwcId/T9sTW251yzCc1e2z rHX/kw== -END CERTIFICATE- [EMAIL PROTECTED] ~/workcat cert-bad.pem -BEGIN CERTIFICATE- MIIBsDCCAVoCAQYwDQYJKoZIhvcNAQEFBQAwYzELMAkGA1UEBhMCQVUxEzARBgNV BAgTClF1ZWVuc2xhbmQxGjAYBgNVBAoTEUNyeXB0U29mdCBQdHkgTHRkMSMwIQYD VQQDExpTZXJ2ZXIgdGVzdCBjZXJ0ICg1MTIgYml0KTAeFw0wNjA5MTEyMzU4NTVa Fw0wNjEwMTEyMzU4NTVaMGMxCzAJBgNVBAYTAkFVMRMwEQYDVQQIEwpRdWVlbnNs YW5kMRowGAYDVQQKExFDcnlwdFNvZnQgUHR5IEx0ZDEjMCEGA1UEAxMaU2VydmVy IHRlc3QgY2VydCAoNTEyIGJpdCkwXDANBgkqhkiG9w0BAQEFAANLADBIAkEAn7PD hCeV/xIxUg8V70YRxK2A5jZbD92A12GN4PxyRQk0/lVmRUNMaJdq/qigpd9feP/u 12S4PwTLb/8q/v657QIDAQABMA0GCSqGSIb3DQEBBQUAA0EAbynCRIlUQgaqyNgU DF6P14yRKUtX8akOP2TwStaSiVf/akYqfLFm3UGka5XbPj4rifrZ0/sOoZEEBvHQ e20sRA== -END CERTIFICATE- - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 with DNSSEC, right? So the real vulnerability level is down somewhere lost in the noise level. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 impression that: 1. Actually using DNSSEC is a major performance hit. No more than using SSL. Well, not much more :-) 2. Actually using DNSSEC requires manual secure master public key distribution, which people are disinclined to do, and which may not scale very well, unless unspecified institutions and arrangements are put in place. Key distribution is, indeed, an open question. Certainly manual key distribution is not a solution. 3. No one actually uses DNSSEC in the wild. I don't know whether this is true or not. Finding out what people do and don't do with DNS is hard. Please advice me if these impressions are wrong, or have become outdated. I realize that I sound like a cold wet sponge with a non stop stream of unpleasantly negative posts, but one of the reasons that cryptography is not widely used is that the various standards, processes, and tools are not in fact very usable. Doesn't bother me any, its just that I happen to have done work on DNSSEC, so I figured I should alert those who care to the problem. Implementing protocols requires widespread consensus, but when too many people show at a meeting then either nothing gets done, or the outcome is extremely stupid, or both, and anyone who points to big problems in what is being done is dismissed as out of order or off topic in order to create the semblance of progress, with the result that what little progress occurs is usually in the wrong direction. That seems a rather harsh judgement of a working group you say you're not informed about. Not that I totally disagree: the work I did on DNSSEC was initially dismissed as out of order and off topic, and it took a lot of effort to get people to accept that the problem was genuine. :-) Cheers, Ben. -- 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 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [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 give you an alleged signature value that would be mistakenly accepted by a flawed RSA implementation. I didn't implement the algorithm, and I will not make suggestions as a convenient big number arithmetic tool to implement it. Note: The algorithm output value is NOT A FORGED SIGNATURE, since a non-flawed RSA signature verification implementation will correctly reject it. Nonetheless, using public exponent 3 with any use of RSA should be deprecated. For the record, I am referring to Hal Finney, Bleichenbacher's RSA signature forgery based on implementation error Wed, 30 Aug 2006 http://www.mail-archive.com/cryptography@metzdowd.com/msg06537.html Input: N, large public modulus (of unknown factorization) h, hash value Constant: p: hex 01 FF 00 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14 A random binary source (e.g. large enough PRNG output) Algorithm: (A) find the largest value of r such that b=(p*2^20+h)*2^(8r) such that b+2^(8r)-1N (B) select random a, 0aN^2, then set c=a*N^2+b+2^(8r)-1 (C) using a simple binary search, find the d = integer cubic root of c (D) if d^3a*N^2+b, go back to step (B) -- if it occurs with a high probability, that's a failure of the approach proposed here, intuition suggests that the probability is either very close to zero, or very close to one (E) set alleged signature s=d mod N (indeed, dN, so s=d) and validate (merely as a software self-check) that (s^3 mod N) div 2^(8r) equals (p*2^20+h) (F) output alleged signature s Regards, -- - 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 PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 namedroppers@ops.ietf.org, (DNSSEC deployment) [EMAIL PROTECTED], dnsop@lists.uoregon.edu 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. Fix: Upgrade OpenSSL. 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! This seems to presuppose that Secure DNS is actually in use. I was unaware that this is the case. What is the penetration of Secure DNS? --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG fLselD6l8fdbF1p4sjg3RQ2GXi+NnQ//1CymnfKs 4+JAX1zwW3fSIStp6glgbAygK1zCuoMeiTigr4qmd - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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], dnsop@lists.uoregon.edu To: DNSEXT WG namedroppers@ops.ietf.org, (DNSSEC deployment) [EMAIL PROTECTED], dnsop@lists.uoregon.edu 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. Fix: Upgrade OpenSSL. 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! This seems to presuppose that Secure DNS is actually in use. I was unaware that this is the case. Does it? All it presupposes, I thought, was that secure DNS was being tested. Which it is. What is the penetration of Secure DNS? Anyone who is running any vaguely recent version of BIND is DNSSEC enabled, whether they are using it now or not. Unless they upgrade, they will be vulnerable when they start to use it. So, the question of whether to use exponent 3 is unrelated to the penetration of DNSSEC use now, it is related to the penetration of broken implementations of DNSSEC now. Cheers, Ben. -- 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 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [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 deployment) [EMAIL PROTECTED], dnsop@lists.uoregon.edu To: DNSEXT WG namedroppers@ops.ietf.org, (DNSSEC deployment) [EMAIL PROTECTED], dnsop@lists.uoregon.edu 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. Fix: Upgrade OpenSSL. 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! This seems to presuppose that Secure DNS is actually in use. I was unaware that this is the case. What is the penetration of Secure DNS? hard to tell... how many delegations are there? that said, RIPE has signed all their delegations and the SE delegation is signed. privately, i am aware of perhaps a dozen or so other delegations which are signed. one might also look to the ISC DLV registry to see which of those delegations are signed. --bill --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG fLselD6l8fdbF1p4sjg3RQ2GXi+NnQ//1CymnfKs 4+JAX1zwW3fSIStp6glgbAygK1zCuoMeiTigr4qmd - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
