Re: Exponent 3 damage spreads...

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

2006-09-28 Thread Ralf-Philipp Weinmann


On Sep 25, 2006, at 10:29 AM, Simon Josefsson wrote:


Leichter, Jerry [EMAIL PROTECTED] writes:


I agree that there are two issues, and they need to be treated
properly.  The first - including data after the ASN.1 blob in the
signature computation but then ignoring it in determining the
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...

2006-09-28 Thread Kuehn, Ulrich
 

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

2006-09-25 Thread Philipp Gühring
Hi,

We have been researching, which vendors were generating Exponent 3 keys, and 
we found the following until now:

* Cisco 3000 VPN Concentrator
* CSP11
* AN.ON / JAP (they told me they would change it on the next day)
(perhaps more to come)

My current estimate is that 0.26% of the 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...

2006-09-25 Thread Simon Josefsson
Leichter, Jerry [EMAIL PROTECTED] writes:

 I agree that there are two issues, and they need to be treated
 properly.  The first - including data after the ASN.1 blob in the
 signature computation but then ignoring it in determining the
 semantics - is, I'll argue, an implementation error.  You 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...

2006-09-23 Thread Peter Gutmann
Simon Josefsson [EMAIL PROTECTED] writes:

Not using e=3 when generating a key seems like an easy sell.

Almost no-one does this anyway, but I don't think that's much help.

A harder sell might be whether widely deployed implementations such as TLS
should start to reject signatures done with an 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...

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

2006-09-23 Thread Simon Josefsson
Leichter, Jerry [EMAIL PROTECTED] writes:

 Granted, one or more implementations got this wrong.  (Has anyone looked
 to see if all the incorrect code all descends from a common root, way
 back when?)

We have at least three independent widely used implementations that
got things wrong: OpenSSL, 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...

2006-09-23 Thread Peter Gutmann
Yet another e=3 attack, although this one is a bit special-case.  As Burt
Kaliski points out in his paper on hash function firewalls,
http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.pdf,
if you can control the 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...

2006-09-23 Thread Peter Gutmann
Leichter, Jerry [EMAIL PROTECTED] writes:

A several year old paper by Kaliski discussed using the ASN.1 OID to store
data in.

Damn, beat me to it :-).

It has slightly different properties, but the lesson in this context is that
implementations must properly check the ASN.1 OID field too.

The 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...

2006-09-23 Thread Leichter, Jerry
| | I don't think it's a problem, you just take the ASN.1 DigestInfo
| | value, since the trailing garbage isn't part of the DigestInfo, you
| | ignore it.  Specifically, the ASN.1 object is entirely
| | self-contained, so you can tell exactly where it ends and what it
| | contains.  Anything 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...

2006-09-23 Thread Leichter, Jerry
|  Granted, one or more implementations got this wrong.  (Has anyone
|  looked to see if all the incorrect code all descends from a common
|  root, way back when?)
| 
| We have at least three independent widely used implementations that
| got things wrong: OpenSSL, Mozilla NSS, and GnuTLS.
| 
| 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...

2006-09-23 Thread James A. Donald

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

2006-09-22 Thread Leichter, Jerry
| 
|10.2.3 Data decoding
| 
|The data D shall be BER-decoded to give an ASN.1 value of
|type DigestInfo, which shall be separated into a message
|digest MD and a message-digest algorithm identifier. The
|message-digest algorithm identifier shall determine 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...

2006-09-22 Thread Anton Stiglic
O.k., thanks to Hal Finney for pointing out to me in a private email that my
modulus wasn't in fact the right size.  I have had some problems with the
openssl key generation (doesn't always seem to generate the exact modulus
size I ask for).  

In attachment, the forged signature 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...

2006-09-21 Thread Hal Finney
Anton Stiglic writes:
 I tried coming up with my own forged signature that could be validated with
 OpenSSL (which I intended to use to test other libraries). ...

 Now let's look at s^3
 1FFF\
 \
 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...

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

2006-09-21 Thread Kuehn, Ulrich
Peter,

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

2006-09-21 Thread Peter Gutmann
Kuehn, Ulrich [EMAIL PROTECTED] writes:

But the PKCS#1 spec talks about building up the complete padded signature
input at the verifier, and then comparing it.

Uhh, did you actually read the rest of my post?  *One variant of the PKCS #1
spec, that didn't exist at the time the the affected other 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...

2006-09-21 Thread Kuehn, Ulrich
Peter, 

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

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

2006-09-21 Thread Simon Josefsson
[EMAIL PROTECTED] (Peter Gutmann) writes:

Consequently, I think the focus on e=3 is misguided. 

 It's not at all misguided.  This whole debate about trying to hang on to e=3
 seems like the argument about epicycles, you modify the theory to handle
 anomalies, then you modify it again to handle 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...

2006-09-21 Thread Peter Gutmann
Kuehn, Ulrich [EMAIL PROTECTED] writes:

   10.2.3 Data decoding

   The data D shall be BER-decoded to give an ASN.1 value of
   type DigestInfo, which shall be separated into a message
   digest MD and a message-digest algorithm identifier. The
   message-digest algorithm 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...

2006-09-21 Thread Steven M. Bellovin
On Thu, 21 Sep 2006 07:00:03 -0400, Whyte, William [EMAIL PROTECTED]
wrote:

  Similarly, the thousands of words of nitpicking standards, bashing ASN.1, 
  and
  so on ad nauseum, can be eliminated entirely by following one simple rule:
  
Don't use e=3
 
 I'd extend it to don't use e = 17. 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...

2006-09-20 Thread Anton Stiglic

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

2006-09-20 Thread Peter Gutmann
David Wagner [EMAIL PROTECTED] writes:

(a) Any implementation that doesn't check whether there is extra junk left
over after the hash digest isn't implementing the PKCS#1.5 standard
correctly. That's a bug in the implementation.

No, it's a bug in the spec:

9.4 Encryption-block parsing

It is an 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...

2006-09-19 Thread Damien Miller
On Fri, 15 Sep 2006, Jostein Tveit wrote:

 [EMAIL PROTECTED] (Peter Gutmann) writes:
 
  What's more scary is that if anyone introduces a parameterised hash
  (it's quite possible that this has already happened in some fields,
  and with the current interest in randomised hashes it's only a
  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...

2006-09-18 Thread James A. Donald

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

 It seems to me that the problems can be attributed to
 two problems: (a) implementation 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...

2006-09-16 Thread James A. Donald

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

2006-09-15 Thread Peter Gutmann
Simon Josefsson [EMAIL PROTECTED] writes:

Deploying a hash widely isn't done easily, though.  GnuTLS only support MD2,
MD5, SHA-1 and RIPEMD (of which MD2/MD5 are by default not used to verify
signatures).

Right, but it's been pure luck that that particular implementation (and most
likely a 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...

2006-09-15 Thread Bill Frantz
[EMAIL PROTECTED] (James A. Donald) on Thursday, September 14, 2006 wrote:

Obviously we do need a standard for describing structured data, and we 
need a standard that leads to that structured data being expressed 
concisely and compactly, but seems to me that ASN.1 is causing a lot of 
grief.

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...

2006-09-15 Thread Jostein Tveit
[EMAIL PROTECTED] (Peter Gutmann) writes:

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

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...

2006-09-15 Thread Peter Gutmann
Simon Josefsson [EMAIL PROTECTED] writes:

Test vectors for this second problem are as below, created by Yutaka OIWA.

To make this easier to work with, I've combined them into a PKCS #7 cert chain
(attached).  Just load/click on the chain and see what your app says.

(As an aside, this chain is 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...

2006-09-14 Thread James A. Donald

Simon Josefsson wrote:

Jostein Tveit [EMAIL PROTECTED] writes:


Anyone got a test key with a real and a forged signature to test
other implementations than OpenSSL?


There are actually two problems to consider...

First, there is the situation by Bleichenbacher at Crypto 06 and
explained in:

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...

2006-09-14 Thread Peter Gutmann
Simon Josefsson [EMAIL PROTECTED] writes:

The second problem is that the parameters field can ALSO be used to store
data that may be used to manipulate the signature value into being a cube.
To my knowledge, this was discovered by Yutaka Oiwa, Kazukuni Kobara, Hajime
Watanabe.  I didn't attend 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...

2006-09-14 Thread Simon Josefsson
[EMAIL PROTECTED] (Peter Gutmann) writes:

 Simon Josefsson [EMAIL PROTECTED] writes:

The second problem is that the parameters field can ALSO be used to store
data that may be used to manipulate the signature value into being a cube.
To my knowledge, this was discovered by Yutaka Oiwa, Kazukuni 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.  Look at the certificates I
posted.

 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.
Checking that it is empty shouldn't be a problem.

Or do you know of real certificates with a non-NULL parameters field
in the signature?

It is important to keep in mind that this only applies to incorrect
implementations that handle keys with e=3.  Using Debian's
/etc/ssl/certs/ CA list, which on my system contains around 100 CAs, I
extracted the issuer name of the CAs with e=3:

Issuer: C=US,O=Digital Signature Trust Co.,OU=DSTCA E1
Issuer: C=US,O=Digital Signature Trust Co.,OU=DSTCA E2
Issuer: C=US,O=Entrust.net,OU=www.entrust.net/Client_CA_Info/CPS incorp. by 
ref. limits liab.,OU=(c) 1999 Entrust.net Limited,CN=Entrust.net Client 
Certification Authority
Issuer: C=US,O=Entrust.net,OU=www.entrust.net/CPS incorp. by ref. (limits 
liab.),OU=(c) 1999 Entrust.net Limited,CN=Entrust.net Secure Server 
Certification Authority

I'm not familiar with DST, so I wonder whether those two are widely
used.  https://secure.digsigtrust.com/ doesn't use it.

That leaves two Entrust certificates.  At least
https://www.entrust.com/ is protected by the second certificate above,
so it may be in wide use.

/Simon

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Exponent 3 damage spreads...

2006-09-14 Thread Peter Gutmann
Simon Josefsson [EMAIL PROTECTED] writes:
[EMAIL PROTECTED] (Peter Gutmann) writes:
Simon Josefsson [EMAIL PROTECTED] writes:
The second problem is that the parameters field can ALSO be used to store
data that may be used to manipulate the signature value into being a cube.
To my knowledge, this 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...

2006-09-14 Thread Tim Dierks

On 9/14/06, James A. Donald [EMAIL PROTECTED] wrote:

It seems to me that the evil here is ASN.1, or perhaps standards that
use ASN.1 carelessly and badly.

It is difficult to write code that conforms to ASN.1, easy to get it
wrong, and difficult to say what in fact constitutes conforming to 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...

2006-09-14 Thread Hal Finney
Peter Gutmann writes:
 But wait, there's more!  From what I understand of the attack, all you need
 for it to work is for the sig.value to be a perfect cube.  To do this, all you
 need to do is vary a few of the bytes of the hash value, which you can do via
 a simple brute-force search.  So even 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...

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


So the next question becomes, 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...

2006-09-14 Thread Greg Rose

At 23:40  +1200 2006/09/14, Peter Gutmann wrote:

But wait, there's more!  From what I understand of the attack, all you need
for it to work is for the sig.value to be a perfect cube.  To do this, all you
need to do is vary a few of the bytes of the hash value, which you can do via
a simple 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...

2006-09-13 Thread Simon Josefsson
Jostein Tveit [EMAIL PROTECTED] writes:

 Anyone got a test key with a real and a forged signature to test
 other implementations than OpenSSL?

There are actually two problems to consider...

First, there is the situation by Bleichenbacher at Crypto 06 and
explained in:

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...

2006-09-13 Thread Thor Lancelot Simon
On Mon, Sep 11, 2006 at 06:18:06AM +1000, James A. Donald wrote:
 
 3.  No one actually uses DNSSEC in the wild.

DNSSEC seems to be not-uncommonly used to secure dynamic updates,
which is not the most common DNS feature in the world but it is not
so uncommon either.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Exponent 3 damage spreads...

2006-09-12 Thread Eric Young

Jostein Tveit wrote:

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

2006-09-11 Thread Peter Gutmann
Ben Laurie [EMAIL PROTECTED] quotes:

Since I've been told often that most of the world won't upgrade resolvers,
presumably most of the world will be vulnerable to this problem for a long
time.

What you really meant to say was most of the vanishingly small proportion of
the world that bothers 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...

2006-09-11 Thread Ben Laurie
James A. Donald wrote:
 --
 James A. Donald wrote:
  What is the penetration of Secure DNS?
 
 Ben Laurie wrote:
 Anyone who is running any vaguely recent version of
 BIND is DNSSEC enabled, whether they are using it now
 or not.
 
 I am not well informed about DNSSEC, but I am under the
 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...

2006-09-11 Thread Jostein Tveit
Ben Laurie [EMAIL PROTECTED] writes:

 ...thought this might interest people here.

Anyone got a test key with a real and a forged signature to test
other implementations than OpenSSL?

Thanks in advance.

Regards,
-- 
Jostein Tveit [EMAIL PROTECTED]

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Exponent 3 damage spreads...

2006-09-11 Thread Thierry Moreau



Jostein Tveit wrote:


Ben Laurie [EMAIL PROTECTED] writes:



...thought this might interest people here.



Anyone got a test key with a real and a forged signature to test
other implementations than OpenSSL?



If I understand the attack mathematics correctly, the following 
algorithm should 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...

2006-09-10 Thread James A. Donald

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

 To:
 DNSEXT WG 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...

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

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