RE: Why the exponent 3 error happened:

2006-11-10 Thread Kuehn, Ulrich
 

 From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 
 Sent: Sonntag, 17. September 2006 06:01
 
 For another example of just how badly this kind of thing can 
 be done, look at this code excerpt from Firefox version 
 1.5.0.7, which is the fixed version.  There are two PKCS-1 
 parsing functions, one which returns the hash and its prefix, 
 the other of which is given the hash and asked whether it 
 matches the RSA-signed value.  This is from the latter one:
 
 /*
  * 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;
 
 PORT_Free(buffer);
 return SECSuccess;
 
 Here, buffer holds the result of the RSA exponentiation, of 
 size modulus_len, and we are passed hash of size hash_len to compare.
 
 I don't think this code is used, fortunately.  It will accept 
 anything of the form 0, 1, 0, garbage, hash.  Just goes to 
 show how easy it is to get this kind of parsing wrong.
 

Unfortunately, this code _is_ used! It took me quite a while to understand 
under what circumstances, but here is the result. The problem is fixed as of 
version 1.5.0.8 (out now). Interestingly, the mozilla people fixed it by 
themselves in the 2.0 version (and any public beta I could find), but for the 
1.5 version it took my bug report...

So here is how the code is used and some hints (I am reluctant to give out the 
details right now, given that there are still many vulnerable systems out 
there. However, I am sure you can easily work out the details):

Whenever a SSL or TLS server send a ServerKeyExchange message, the key 
contained in there is signed with a fresh nonce. This signature is checked 
using RSA_CheckSign(). 

Faking a signature for a key with a small exponent like 3 is easy. This can be 
used to break the SSL/TLS authentication.

Better upgrade asap...

Regards,
Ulrich

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


Re: Why the exponent 3 error happened:

2006-10-06 Thread James A. Donald

--
Travis H. wrote:
 Actually, encoding lengths of other fields in a
 protocol is probably the easiest way to introduce a
 remotely-exploitable vulnerability (typically buffer
 overflow).  I'm going to have to side with the no
 redundancy means no inconsistencies possible argument
 here.  Oh, and you shouldn't process
 remotely-manipulable data in a language like C, unless
 you're doing all variable-length buffer management
 through a well-tested library, and even then you're
 playing with fire.

All fields that could be controlled by an adversary
should have reasonable maximum values specified in the
protocol definition.  Consider the language field in
HTTP.  It normally is blank, or contains the string
English.  A lot of implementations failed in ways
interesting to attackers when the language field
exceeded 20K, and wound up executing script contained in
the language field.  Why were language fields not given
a reasonable maximum length, and reasonable limits on
the characters permitted in the language field, and an
error response defined for the case that the language
field exceeded that limit, or contained improper
characters?

The only fields that should be permitted to have
unbounded length are those that can be pipelined, where
you repeated fill a fixed length buffer, and repeatedly
empty it.

 And fixed-length buffers are often broken too, because
 many a programmer has arbitrarily decided that's big
 enough without considering how an active adversary
 would be constrained, or without considering that the
 data may grow in size with the next revision of
 (whatever is feeding data to us).

All fixed length buffers are of course broken unless the
length is part of the protocol.  Since there is, in
practice, always going to a maximum length, if only the
length at which the computer starts to run out of
memory, maximum lengths should be defined as part of the
protocol The  field is bounded by the first
whitespace character, or a maximum of 128 unicode
characters, whichever comes first.

Recall all the implementations that gave interesting
results when the length count overflowed to negative.

--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 /qepotdogioqKl6zqKb1307bOmyXeRzSTpBPmWcw
 4WtThf8IVl9id73YCBhzL8jl5yJ7wd+oc/GuW4E7o

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


Re: Why the exponent 3 error happened:

2006-09-21 Thread Anton Stiglic
As other's have mentioned, I don't believe the small RSA exponent (e = 3)
is to blame in Bleichenbacher's attack.
Indeed, the mathematical problem of computing the cubic root of m modulo
an rsa modulus n, for a *fixed*, arbitrary m, is still considered to be
hard (no one has shown the opposite).
What Bleichenbacher demonstrated is that computing the cubic root of m' ||
G, where G can be any value, garbage, and is sufficiently large, is easy.

These are two different problems, and the vulnerability is due to the fact
that these libraries allow for the variant G part.

I don't see ASN.1 as being faulty either.  The ASN.1 simply acts as a
value that allows you to determine what hash algorithm to use.  If the
encrypted signature would be of the form:
  What-ever-padding, hash, header
and implementations would directly go to the least significant bits in
order to retrieve the header (which should be of fixed size), and then
retrieve the hash, we wouldn't have this problem.

I believe you should put the most sensitive information in the least
significant bytes, which are harder to manipulate (Bleichenbacher's attack
plays with the most significant bytes, the least significant bytes are
basically random in his calculations, he doesn't have control over them).

This reminds me of the RSA lsb hardness problem theorem
http://www.wisdom.weizmann.ac.il/~oded/annot/node17.html
I have notes explaining it right here, section 8.4.1:
http://crypto.cs.mcgill.ca/~stiglic/Papers/crypto2.ps
The theorem basically says that if you can predict the least significant
bit of the plaintext given the corresponding RSA ciphertext, than you can
compute the whole plaintext.
The theorem doesn't directly apply however (RSA signature verification
uses the encryption operation, not decryption), but may be of some
insight.

The problem is that we (crypto community) still don't have a good way of
writing specs.  This is in fact a hard problem.  And the problem doesn't
get easier with the increasing complexity of the specs.  We need simple
algorithms and protocols, which allow just enough flexibility, and we need
a good and precise way to write specs for these.

On one side you have theoretical cryptographers / mathematicians who work
in an abstract level, develop algorithms and protocols, but don’t have
much interest in implementing these other than possibly in a prototype
form.  On the other end, you have developers who excel in coding and
system integration but don’t necessarily understand the theoretical
background in all its details.  Specifications act as a bridge between
these two worlds, but this bridge is not very solid today.  We need to do
allot more effort into building stronger bridges.

--Anton


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


RE: [cryptography] Re: Why the exponent 3 error happened:

2006-09-20 Thread Kuehn, Ulrich
 
 From: Ralf-Philipp Weinmann 
 [mailto:[EMAIL PROTECTED] 
[...]
 Unfortunately we only found out that there has been prior art 
 by Yutaka Oiwa et al. *AFTER* we successfully forged a 
 certificate using this method (we being Andrei Pyshkin, Erik 
 Tews and myself).
 
 The certificate we forged however adheres to the padding 
 specifications unlike the one by Yutaka Oiwa that Simon 
 Josefsson forwarded to the list a couple of days ago:
 
 -BEGIN CERTIFICATE-
 MIICgzCCAWugAwIBAgIBFzANBgkqhkiG9w0BAQUFADBoMQswCQYDVQQGEwJVUzEl
 MCMGA1UEChMcU3RhcmZpZWxkIFRlY2hub2xvZ2llcywgSW5jLjEyMDAGA1UECxMp
 U3RhcmZpZWxkIENsYXNzIDIgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkwHhcNMDYw
 ODE5MTY1MTMwWhcNMDYxMDE4MTY1MTMwWjARMQ8wDQYDVQQDEwZIYWNrZXIwgZ8w
 DQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKSu6ChWttBsOpaBrYf4PzyCGNe6DuE7
 rmq4CMskdz8uiAJ3wVd8jGsjdeY4YzoXSVp+9mEF6XqNgyDf8Ub3kNgPYxvJ28lg
 QVpd5RdGWXHo14LWBTD1mtFkCiAhVlATsVNI/tjv2tv7Jp8EsylbDHe7hslA0rns
 Rr2cS9bvpM03AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJKoZIhvcNAQEF
 BQADggEB
 
 
 ADLL/Up63HkFWD15INcW
 Xd1nZGI+gO/whm58ICyJ1Js7ON6N4NyBTwe8513CvdOlOdG/Ctmy2gxEE47HhEed
 ST8AUooI0ey599t84P20gGRuOYIjr7c=
 -END CERTIFICATE-
 
 Broken implementations can successfully verify it using the 
 Starfield Class 2 Certification Authority:
 

I tried to parse and verify this certificate using openssl's asn1parse command. 
However, I get an error:

Error in encoding
7469:error:0D07207B:asn1 encoding routines:ASN1_get_object:header too 
long:asn1_lib.c:150:

I am using openssl version 0.9.8c as of Sep 05, 2006 (Linux/Debian system).

Any ideas what I am doing wrong?

Cheers,
Ulrich


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


Re: [cryptography] Re: Why the exponent 3 error happened:

2006-09-20 Thread Ralf-Philipp Weinmann


On Sep 20, 2006, at 3:10 PM, Kuehn, Ulrich wrote:


-BEGIN CERTIFICATE-
MIICgzCCAWugAwIBAgIBFzANBgkqhkiG9w0BAQUFADBoMQswCQYDVQQGEwJVUzEl
MCMGA1UEChMcU3RhcmZpZWxkIFRlY2hub2xvZ2llcywgSW5jLjEyMDAGA1UECxMp
U3RhcmZpZWxkIENsYXNzIDIgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkwHhcNMDYw
ODE5MTY1MTMwWhcNMDYxMDE4MTY1MTMwWjARMQ8wDQYDVQQDEwZIYWNrZXIwgZ8w
DQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKSu6ChWttBsOpaBrYf4PzyCGNe6DuE7
rmq4CMskdz8uiAJ3wVd8jGsjdeY4YzoXSVp+9mEF6XqNgyDf8Ub3kNgPYxvJ28lg
QVpd5RdGWXHo14LWBTD1mtFkCiAhVlATsVNI/tjv2tv7Jp8EsylbDHe7hslA0rns
Rr2cS9bvpM03AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJKoZIhvcNAQEF
BQADggEB


ADLL/Up63HkFWD15INcW
Xd1nZGI+gO/whm58ICyJ1Js7ON6N4NyBTwe8513CvdOlOdG/Ctmy2gxEE47HhEed
ST8AUooI0ey599t84P20gGRuOYIjr7c=
-END CERTIFICATE-

Broken implementations can successfully verify it using the
Starfield Class 2 Certification Authority:



I tried to parse and verify this certificate using openssl's  
asn1parse command. However, I get an error:


Error in encoding
7469:error:0D07207B:asn1 encoding routines:ASN1_get_object:header  
too long:asn1_lib.c:150:


I am using openssl version 0.9.8c as of Sep 05, 2006 (Linux/Debian  
system).


Hi Ulrich,

You're using a version that has already been fixed. However the main  
problem seems to be that you're trying to parse a certificate in PEM  
format using the option -inform DER instead of -inform PEM ;)


At least that's how I can reproduce your error...

Cheers,
Ralf



smime.p7s
Description: S/MIME cryptographic signature


Re: [cryptography] Re: Why the exponent 3 error happened:

2006-09-19 Thread Ralf-Philipp Weinmann


On Sep 16, 2006, at 11:31 PM, Eric Young wrote:

This is a question I would not mind having answered; while the  
exponent 3 attack works when there are low bits to 'modify', there  
has been talk of an attack where the ASN.1 is correctly right  
justified (hash is the least significant bytes), but incorrect ASN. 
1 encoding is used to add 'arbitrary' bytes before the hash.  So in  
this case some of the most significant bytes are fixed, the least  
significant bytes are fixed, but some in the middle can be  
modified.  Does the exponent 3 attack work in this case?  My  
personal feel is that his would be much harder, but is such an  
attack infeasible?


This issue about ASN.1 parameters being an evil concept goes away  
if the attack can only work when the least significant bytes need  
to be modifiable.


Hi Eric,

the attack indeed is not infeasible. Although if you do not want to  
violate the padding specifications (minimum of eight 0xFF bytes), you  
need moduli longer than 1024 bits. My colleague Andrei Pyshkin had  
the following idea:


In the following, we will assume to public exponent e=3. Let s be the  
signature of a message m. The message can be broken down into 3 parts:


m := f_1 || v || f_2

with f_1, f_2 being fixed and v variable. Note that f_2 denotes the  
lowermost bits of the message. Furthermore let d=bitlength(f_2).


In order to calculate a signature s such that m is a perfect cube, we  
carry out the following steps:


1. Calculate an x such that f_2 = x^3 mod 2^d with x  2^d. This will
succeed with probability  1/2.

2. Calculate s_0 = floor(cuberoot(m))

3. Calculate the signature s = s_0 + x - (s_0 mod 2^d)

Calculating the bounds for which moduli and fixed data structures  
this attack will succeed is left as an excercise to the inclined reader.


Unfortunately we only found out that there has been prior art by  
Yutaka Oiwa et al. *AFTER* we successfully forged a certificate using  
this method (we being Andrei Pyshkin, Erik Tews and myself).


The certificate we forged however adheres to the padding  
specifications unlike the one by Yutaka Oiwa that Simon Josefsson  
forwarded to the list a couple of days ago:


-BEGIN CERTIFICATE-
MIICgzCCAWugAwIBAgIBFzANBgkqhkiG9w0BAQUFADBoMQswCQYDVQQGEwJVUzEl
MCMGA1UEChMcU3RhcmZpZWxkIFRlY2hub2xvZ2llcywgSW5jLjEyMDAGA1UECxMp
U3RhcmZpZWxkIENsYXNzIDIgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkwHhcNMDYw
ODE5MTY1MTMwWhcNMDYxMDE4MTY1MTMwWjARMQ8wDQYDVQQDEwZIYWNrZXIwgZ8w
DQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKSu6ChWttBsOpaBrYf4PzyCGNe6DuE7
rmq4CMskdz8uiAJ3wVd8jGsjdeY4YzoXSVp+9mEF6XqNgyDf8Ub3kNgPYxvJ28lg
QVpd5RdGWXHo14LWBTD1mtFkCiAhVlATsVNI/tjv2tv7Jp8EsylbDHe7hslA0rns
Rr2cS9bvpM03AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJKoZIhvcNAQEF
BQADggEB


ADLL/Up63HkFWD15INcW
Xd1nZGI+gO/whm58ICyJ1Js7ON6N4NyBTwe8513CvdOlOdG/Ctmy2gxEE47HhEed
ST8AUooI0ey599t84P20gGRuOYIjr7c=
-END CERTIFICATE-

Broken implementations can successfully verify it using the Starfield  
Class 2 Certification Authority:


https://certificates.starfieldtech.com/repository/sf-class2-root.crt

Cheers,
Ralf

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


Re: Why the exponent 3 error happened:

2006-09-19 Thread James A. Donald

--
imon Josefsson wrote:
 Again, there is no problem in ASN.1 or PKCS#1 that is
 being exploited here, only an implementation flaw,
 even if it is an interesting one.

But why did several people independently implement the
same or similar flaws?

The answer is in Jack Lloyd's post:
 I wrote a decoder for PKCS#1 v1.5, realized it
 probably had bugs I wouldn't figure out until too
 late, [...] my PSS verification code is probably
 around twice the length of the PSS generation code,
 due to the need to check every stupid little thing.

--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 kcayKvWlPFXTPP9oNsxdS/f7Cu706I0sQMBSZJUj
 4578L9TLcVLPN7c++p1/Un4LFV6ugOy6Pb/SpWw2u




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


Re: Why the exponent 3 error happened:

2006-09-18 Thread Simon Josefsson
Whyte, William [EMAIL PROTECTED] writes:

 This is incorrect. The simple form of the attack
 is exactly as described above - implementations
 ignore extraneous data after the hash. This
 extraneous data is _not_ part of the ASN.1 data.
 
 James A. Donald wrote:
But it is only extraneous because ASN.1 *says* it is
extraneous.

 No. It's not the ASN.1 that says it's extraneous, it's the
 PKCS#1 standard. The problem is that the PKCS#1 standard
 didn't require that the implementation check for the
 correct number of ff bytes that precede the BER-encoded
 hash. The attack would still be possible if the hash
 wasn't preceded by the BER-encoded header.

That's not true -- PKCS#1 implicitly require that check.  PKCS#1 says
the verification algorithm should generating a new signature and then
compare them.  See RFC 3447 section 8.2.2.  That solves the problem.

Again, there is no problem in ASN.1 or PKCS#1 that is being exploited
here, only an implementation flaw, even if it is an interesting one.

After reading http://www.rsasecurity.com/rsalabs/node.asp?id=2020 it
occurred to me that section 4.2 of it describes a somewhat related
problem, where the hash OID is modified instead.  That attack require
changes in specifications and implementations, to have the
implementation support the new hash OID.  But it suggests a potential
new problem too: if implementation don't verify that the parsed hash
OID length is correct.  E.g., an implementation that uses

memcmp (parsed-hash-oid, sha1-hash-oid,
 MIN (length (parsed-hash-oid), length (sha1-hash-oid)))

to recognize the hash algorithm used in the ASN.1 structure, it may
also be vulnerable: the parsed-hash-oid may contain garbage, that
can be used to forge signatures against broken implementations,
similar to the two attacks discussed so far.  I don't know of any
implementations that do this, though.

/Simon

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


RE: Why the exponent 3 error happened:

2006-09-18 Thread Kuehn, Ulrich
I noticed the exact same code being present in the mozilla 1.7.13 source ... I 
wonder what the correct consequence would be? Have us crypto people proof-read 
all relevant source code? Better educate developers?

Interestingly the attacker's playground between the 0, 1, 0 and the hash gets 
bigger with larger key sizes, so I wonder if attacks get easier for longer 
keys...

Cheers,
Ulrich

 From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 
 
 For another example of just how badly this kind of thing can 
 be done, look at this code excerpt from Firefox version 
 1.5.0.7, which is the fixed version.  There are two PKCS-1 
 parsing functions, one which returns the hash and its prefix, 
 the other of which is given the hash and asked whether it 
 matches the RSA-signed value.  This is from the latter one:
 
 /*
  * 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;
 
 PORT_Free(buffer);
 return SECSuccess;
 
 Here, buffer holds the result of the RSA exponentiation, of 
 size modulus_len, and we are passed hash of size hash_len to compare.
 
 I don't think this code is used, fortunately.  It will accept 
 anything of the form 0, 1, 0, garbage, hash.  Just goes to 
 show how easy it is to get this kind of parsing wrong.
 
 (Note, this is from 
 mozilla/security/nss/lib/softoken/rsawrapr.c:RSA_CheckSign())
 

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


Re: [cryptography] Re: Why the exponent 3 error happened:

2006-09-17 Thread Eric Young

James A. Donald wrote:

--
James A. Donald wrote:
 Code is going wrong because ASN.1 can contain
 complicated malicious information to cause code to go
 wrong.  If we do not have that information, or simply
 ignore it, no problem.

Ben Laurie wrote:
 This is incorrect. The simple form of the attack is
 exactly as described above - implementations ignore
 extraneous data after the hash. This extraneous data
 is _not_ part of the ASN.1 data.

But it is only extraneous because ASN.1 *says* it is
extraneous.

If you ignore the ASN.1 stuff, treat it as just
arbitrary padding, you will not get this problem.  You
will look at the rightmost part of the data, the low
order part of the data, for the hash, and lo, the hash
will be wrong!
This is a question I would not mind having answered; while the exponent 
3 attack works when there are low bits to 'modify', there has been talk 
of an attack where the ASN.1 is correctly right justified (hash is the 
least significant bytes), but incorrect ASN.1 encoding is used to add 
'arbitrary' bytes before the hash.  So in this case some of the most 
significant bytes are fixed, the least significant bytes are fixed, but 
some in the middle can be modified.  Does the exponent 3 attack work in 
this case?  My personal feel is that his would be much harder, but is 
such an attack infeasible?


This issue about ASN.1 parameters being an evil concept goes away if the 
attack can only work when the least significant bytes need to be modifiable.


eric

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


RE: Why the exponent 3 error happened:

2006-09-17 Thread Whyte, William
 This is incorrect. The simple form of the attack
 is exactly as described above - implementations
 ignore extraneous data after the hash. This
 extraneous data is _not_ part of the ASN.1 data.
 
 James A. Donald wrote:
But it is only extraneous because ASN.1 *says* it is
extraneous.

No. It's not the ASN.1 that says it's extraneous, it's the
PKCS#1 standard. The problem is that the PKCS#1 standard
didn't require that the implementation check for the
correct number of ff bytes that precede the BER-encoded
hash. The attack would still be possible if the hash
wasn't preceded by the BER-encoded header.

William

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


Re: Why the exponent 3 error happened:

2006-09-17 Thread Hal Finney
For another example of just how badly this kind of thing can be done,
look at this code excerpt from Firefox version 1.5.0.7, which is the
fixed version.  There are two PKCS-1 parsing functions, one which returns
the hash and its prefix, the other of which is given the hash and asked
whether it matches the RSA-signed value.  This is from the latter one:

/*
 * 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;

PORT_Free(buffer);
return SECSuccess;

Here, buffer holds the result of the RSA exponentiation, of size
modulus_len, and we are passed hash of size hash_len to compare.

I don't think this code is used, fortunately.  It will accept anything
of the form 0, 1, 0, garbage, hash.  Just goes to show how easy it is
to get this kind of parsing wrong.

(Note, this is from 
mozilla/security/nss/lib/softoken/rsawrapr.c:RSA_CheckSign())

Hal Finney

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


Re: Why the exponent 3 error happened:

2006-09-16 Thread James A. Donald

--
James A. Donald wrote:
 Code is going wrong because ASN.1 can contain
 complicated malicious information to cause code to go
 wrong.  If we do not have that information, or simply
 ignore it, no problem.

Ben Laurie wrote:
 This is incorrect. The simple form of the attack is
 exactly as described above - implementations ignore
 extraneous data after the hash. This extraneous data
 is _not_ part of the ASN.1 data.

But it is only extraneous because ASN.1 *says* it is
extraneous.

If you ignore the ASN.1 stuff, treat it as just
arbitrary padding, you will not get this problem.  You
will look at the rightmost part of the data, the low
order part of the data, for the hash, and lo, the hash
will be wrong!


--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 UXewrm6/A/3rklAbGfwShB29YFqjqqWLa3AU+htK
 4Xf+hOFyYI4Pv0jWjzDC226z/LHorwYhZlhfNvl2z

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


Re: Why the exponent 3 error happened:

2006-09-16 Thread Ben Laurie
James A. Donald wrote:
 --
 James A. Donald wrote:
 Code is going wrong because ASN.1 can contain
 complicated malicious information to cause code to go
 wrong.  If we do not have that information, or simply
 ignore it, no problem.
 
 Ben Laurie wrote:
 This is incorrect. The simple form of the attack is
 exactly as described above - implementations ignore
 extraneous data after the hash. This extraneous data
 is _not_ part of the ASN.1 data.
 
 But it is only extraneous because ASN.1 *says* it is
 extraneous.
 
 If you ignore the ASN.1 stuff, treat it as just
 arbitrary padding, you will not get this problem.  You
 will look at the rightmost part of the data, the low
 order part of the data, for the hash, and lo, the hash
 will be wrong!

If you ignore the ASN.1 stuff then you won't know what hash to calculate.

-- 
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: Why the exponent 3 error happened:

2006-09-16 Thread James A. Donald

--
James A. Donald wrote:
Code is going wrong because ASN.1 can contain
complicated malicious information to cause code
to go wrong.  If we do not have that
information, or simply ignore it, no problem.

Ben Laurie wrote:
   This is incorrect. The simple form of the attack
   is exactly as described above - implementations
   ignore extraneous data after the hash. This
   extraneous data is _not_ part of the ASN.1 data.

James A. Donald wrote:
  But it is only extraneous because ASN.1 *says* it is
  extraneous.
 
  If you ignore the ASN.1 stuff, treat it as just
  arbitrary padding, you will not get this problem.
  You will look at the rightmost part of the data, the
  low order part of the data, for the hash, and lo,
  the hash will be wrong!

Ben Laurie wrote:
 If you ignore the ASN.1 stuff then you won't know what
 hash to calculate.

If true, irrelevant.  If true, it would merely imply
that they should not have used ASN.1 to represent the
hash type.

But in fact it is not true.  I suspect a lot of
implementations decide the hash type by looking for
particular byte values at particular fixed locations,
rather than by deciphering the data as ASN.1.

To repeat my argument:  A program can only correctly
handle a small number of fixed data layouts, but ASN.1
can express an infinite variety of layouts, giving great
scope for malicious data.

--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 bUm91GJmI9zp9B7QNyHcQVSy/PJPz6xQb/PIepFe
 47yymkER8iV/Dv/2S5EmJ4XMufQI8aDE8j3ZF80nl

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


Re: Why the exponent 3 error happened:

2006-09-15 Thread Peter Gutmann
Victor Duchovni [EMAIL PROTECTED] writes:

This, in my view, has little to do with ASN.1, XML, or other encoding
frameworks. Thorough input validation is not yet routinely and consistently
practiced by most software developers. Software is almost invariably written
to parse formats observed in practice correctly, and is then promptly
declared to work. 

It's not just this, sometimes the acceptance of not-quite-correct data is
necessary, because if you don't do it, your implementation breaks.  To take
one well-known example, Microsoft have consistently encoded the version info
in their SSL/TLS handshake wrong, which in theory allows rollback attacks.  So
as a developer you have the following options:

 1. Reject the encoding and be incompatible with 95(?)% of *all* deployed SSL
clients (that's *several hundred million* users).

 2. Turn a blind eye and interoperate with said several hundred million users,
at the expense of being vulnerable to rollback attacks.

I'm not aware of a single implementation that takes option 1, simply because
it would be pure marketplace suicide to do so.

The same goes for pretty much every other security protocol I know of.  SSH is
the most explicit since clients and servers exchange ASCII strings before they
do anything else, all SSH implementations have a built-in database of known
bugs that they adjust their behaviour for when they detect a certain client or
server.  Obviously no-one will implement this bug-compatibility for a security
hole, but it's not impossible that some of this extended flexibility may at
some point lead to a problem.

For other protocols, it works in reverse, you recognise the peer implemention
by the bugs, not the other way round.  Beyond straight implementation bugs
though are standards that require insecure or ambiguous behaviour, either by
accident (which eventually gets fixed), or because of design-by-committee
politics, about which enough has probably been said in the past
(cough*IPsec*cough :-).

Peter.

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


Re: Why the exponent 3 error happened:

2006-09-15 Thread Steven M. Bellovin
On Thu, 14 Sep 2006 17:21:28 -0400, Victor Duchovni
[EMAIL PROTECTED] wrote:

 
 If so, I fear we are learning the wrong lesson, which while valid in
 other contexts is not pertinent here. TLS must be flexible enough to
 accommodate new algorithms, this means that the data structures being
 exchanged are malleable, and that implementations must validate strict
 adherence to a specifically defined form for the agreed algorithm,
 but the ability to express other forms cannot be designed out.
 
 This, in my view, has little to do with ASN.1, XML, or other encoding
 frameworks. Thorough input validation is not yet routinely and
 consistently practiced by most software developers. Software is almost
 invariably written to parse formats observed in practice correctly, and is
 then promptly declared to work. The skepticism necessary to continually
 question the implicit assumption that the input is well-formed is perhaps
 not compatible with being a well-socialized human. The attackers who ask
 the right questions to break systems and the few developers who write
 truly defensive code are definitely well off the middle of the bell-curve.
 
 It is not just PKCS#1 or X.509v3 that presents opportunities for crafting
 interesting messages. MIME, HTTP, HTML, XML, ... all exhibit similar
 pitfalls. Loosely speaking, this looks like a variant of Goedel's theorem,
 if the protocol is expressive enough it can express problematic assertions.
 
 We can fine-tune some protocols to remove stupid needless complexity, but
 enough complexity will remain to make the required implementation disciple
 beyond the reach of most software developers (at least as trained today,
 but it is not likely possible to design a training program that will
 a preponderance all strong defensive programmers).

A software testing expert once asked me why even good test groups didn't
find more of the software holes.  I told her it was because the spec said
things like must accept input up to 4096 bytes rather than must accept
input up to 4096 bytes and must detect and reject longer input strings.
I think we're seeing the same thing here -- the spec didn't say must
reject, so people who coded to the spec fell victim.

As for the not compatible with a well-socialized human -- well, maybe --
I don't think normal people describe themselves as paranoid by
profession


--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

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


Re: Why the exponent 3 error happened:

2006-09-15 Thread Richard Salz
From http://www.w3.org/2001/tag/doc/leastPower.html :

When designing computer systems, one is often faced with a choice between 
using a more or less powerful language for publishing information, for 
expressing constraints, or for solving some problem. This finding explores 
tradeoffs relating the choice of language to reusability of information. 
The Rule of Least Power suggests choosing the least powerful language 
suitable for a given purpose

--
STSM, Senior Security Architect
SOA Appliances
Application Integration Middleware


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


Re: Why the exponent 3 error happened:

2006-09-15 Thread James A. Donald

--
Victor Duchovni wrote:
 If so, I fear we are learning the wrong lesson, which
 while valid in other contexts is not pertinent here.
 TLS must be flexible enough to accommodate new
 algorithms, this means that the data structures being
 exchanged are malleable, and that implementations must
 validate strict adherence to a specifically defined
 form for the agreed algorithm, but the ability to
 express other forms cannot be designed out.

There is no need, ever, for the RSA signature to encrypt
anything other than a hash, nor will their ever be such
a need.  In this case the use of ASN.1 serves absolutely
no purpose whatsoever, other than to create complexity,
bugs, and opportunities for attack.  It is sheer
pointless stupidity, complexity for the sake of
complexity, an indication that the standards process is
broken.

--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 mKNEZf/r5lZqyGpNhzkQ0zdt2uAdaxkSyyyxAW3W
 4BWO8prrBiE/VfMik8xpeS4TgD+5KsqGSGeRw2Dxr

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


Re: Why the exponent 3 error happened:

2006-09-15 Thread Peter Gutmann
Steven M. Bellovin [EMAIL PROTECTED] writes:

As for the not compatible with a well-socialized human -- well, maybe -- I
don't think normal people describe themselves as paranoid by profession

Might I refer the reader to http://www.cs.auckland.ac.nz/~pgut001/.  I've even
received mail from address-harvesting bots that begin Dear Paranoid, 

Peter.

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


Re: Why the exponent 3 error happened:

2006-09-15 Thread Hal Finney
James Donald writes:
 There is no need, ever, for the RSA signature to encrypt
 anything other than a hash, nor will their ever be such
 a need.  In this case the use of ASN.1 serves absolutely
 no purpose whatsoever, other than to create complexity,
 bugs, and opportunities for attack.  It is sheer
 pointless stupidity, complexity for the sake of
 complexity, an indication that the standards process is
 broken.

Actually there is something besides the hash there: an identifier for
which hash algorithm is used.  The ASN.1 OID was, I suppose, a handy and
already-existant mechanism for universal algorithm identification numbers.

Putting the hash identifier into the RSA signed data prevents hash
substitution attacks.  Otherwise the hash identifier has to be passed
unsigned, and an attacker could substitute a weak hash algorithm and find
a second preimage that matches your signed hash.  Maybe that is not part
of a threat model you are interested in but at least some signers don't
want their hash algorithms to be changed.

BTW I want to mention a correction to Peter Gutmann's post: as I
understand it, GnuPG was not vulnerable to this attack.  Neither was PGP.
The OpenPGP standard passes the hash number outside the RSA signed data
in addition to using PKCS-1 padding.  This simplifies the parsing as it
allows hard-coding the ASN-1 prefix as an opaque bit string, then doing
a simple comparison between the prefix+hash and what it should be.

Hal Finney

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


Re: Why the exponent 3 error happened:

2006-09-15 Thread Ben Laurie
James A. Donald wrote:
 --
 Greg Rose wrote:
 At 19:02  +1000 2006/09/14, James A. Donald wrote:
 Suppose the padding was simply

 010101010101010 ... 1010101010101 hash

 with all leading zeros in the hash omitted, and four
 zero bits showing where the actual hash begins.

 Then the error would never have been possible.
 
 James A. Donald:
 I beg to differ. A programmer who didn't understand
 the significance of crypto primitives would (as many
 did) just search for the end of the padding to locate
 the beginning of the hash, and check that the next set
 of bytes were identical to the hash, then return
 true. So
 
 The hash is known size, and occurs in known position.
 He does not search the padding for location, but
 examines it for correct format.
 

 01010101 ... 1010101010101 hash crappetycrap

 would still be considered valid. There's a lot of code
 out there that ignored the fact that after the FFs was
 specific ASN.1 stuff, and just treated it as a defined
 part of the padding.
 
 And that code is correct, and does not have the problem
 that we discuss.  Paying attention to ASN.1 stuff is
 what is causing this problem.

No, it is incorrect and does have the problem we discuss. The fact that
it ignores the crap that's after the hash makes it vulnerable.

 Code is going wrong because ASN.1 can contain
 complicated malicious information to cause code to go
 wrong.  If we do not have that information, or simply
 ignore it, no problem.

This is incorrect. The simple form of the attack is exactly as described
above - implementations ignore extraneous data after the hash. This
extraneous data is _not_ part of the ASN.1 data.

The more complex form of the attack does actually use the ASN.1, in the
form of the parameters field. However, I'm not sure why you'd single out
ASN.1 as the cause of this problem: once the designers of the protocol
decided you needed parameters, the door was opened to the attack.
Implementations can incorrectly ignore the extraneous parameters no
matter how you encode them.

Not that I'm a fan of ASN.1, but if we're going to blame it for
problems, we should do so only when it is actually to blame.

The fault in this case is a combination of overly flexible protocol
design and implementation flaws.

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: Why the exponent 3 error happened:

2006-09-15 Thread Whyte, William
   If so, I fear we are learning the wrong lesson, which
   while valid in other contexts is not pertinent here.
   TLS must be flexible enough to accommodate new
   algorithms, this means that the data structures being
   exchanged are malleable, and that implementations must
   validate strict adherence to a specifically defined
   form for the agreed algorithm, but the ability to
   express other forms cannot be designed out.
 
 There is no need, ever, for the RSA signature to encrypt
 anything other than a hash, nor will their ever be such
 a need.  In this case the use of ASN.1 serves absolutely
 no purpose whatsoever, other than to create complexity,
 bugs, and opportunities for attack.  It is sheer
 pointless stupidity, complexity for the sake of
 complexity, an indication that the standards process is
 broken.

I think this is a bit unfair.

PKCS#1 signatures were originally designed to include a hash 
identifier to address a specific concern, arising from the
fact that RSA signers can freely choose the hash algorithm
to use.

Say that Alice uses SHA-1 to generate her signature on m,
and SHA-1(m) = h.

Then the concern is that Bob can find a broken hash function
BASH such that BASH(m') = h. If he can do that and format a
message that claims to be signed with RSA and BASH, then he
can present Alice's signature as a valid signature on m'.

There are a number of different protections against this.
For example, Alice's cert could identify her key as only 
to be used with SHA-1 (this is effectively what happens with
DSA public keys). However, the convention has been to mark an
RSA key in an X.509 cert as rsaEncryption and not specify
in the AlgorithmIdentifier that it's only to be used with a
certain hash function (or signature scheme).

So PKCS#1 incorporated the hash identifier, which prevents
a signature generated with one hash algorithm from being
used with a different hash algorithm. (Since then, Burt
Kaliski's done some research on the use of hash firewalls
of this type: see
http://www.rsasecurity.com/rsalabs/node.asp?id=2020.
His conclusion is that by and large they aren't necessary,
but that isn't relevant to the discussion here).

At the time, ASN.1 was in widespread use, so it was an 
obvious decision (rather than pointless stupidity) to use 
it to encode the hash function identifier. In practice, 
the ASN.1 doesn't introduce complexity because most implementations 
(certainly ones I've worked on) simply treated it as a memcmp 
rather than wheeling out the heavy ASN.1 machinery.

The real problem isn't ASN.1; the problem is that an
encoding method was used for the rest of the signature
that didn't specify the length of the signature block
and it didn't occur to anyone to check it.

Cheers,

William


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


Why the exponent 3 error happened:

2006-09-14 Thread James A. Donald

Why the exponent 3 error happened:

The signature consists of a number that when cubed, is
equal modulo N to the padded hash of the quantity to be
signed.

Part of the padding is the ASN.1 encoding of the hash.

Now suppose we had not ASN.1 encoded the hash.

Suppose the padding was simply

010101010101010 ... 1010101010101 hash

with all leading zeros in the hash omitted, and four
zero bits showing where the actual hash begins.

Then the error would never have been possible.

ASN.1 provided additional redundant information, making
possible unexpected data layouts that should not
normally happen.  It had too much expressive power, too
much flexibility.  It could express cases that one does
not expect to deal with, could flex in more ways than
one's software is likely to be written for.

XML has even greater redundancy and flexibility, but has
the advantage that one can constrain it with a DTD that
guarantees that it will have the form, and only the
form, that one's software expects.

Still, usually the simplest way of dealing with data
that may be hostile and malicious is to use a data
format that is entirely free from redundancy, thus can
*only* have the expected form.  If there is no
redundancy in ones data, then one never has to deal with
cases where the data is inconsistent.

One is not always able to eliminate all redundancy, but
one always has to check that the data is of the expected
form, and the fewer forms it can has the easier that is.
ASN.1's crowning virtue is its flexibility, and we do
not want flexibility in possibly hostile data.

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


Re: Why the exponent 3 error happened:

2006-09-14 Thread Greg Rose

At 19:02  +1000 2006/09/14, James A. Donald wrote:

Suppose the padding was simply

010101010101010 ... 1010101010101 hash

with all leading zeros in the hash omitted, and four
zero bits showing where the actual hash begins.

Then the error would never have been possible.


I beg to differ. A programmer who didn't understand the significance 
of crypto primitives would (as many did) just search for the end of 
the padding to locate the beginning of the hash, and check that the 
next set of bytes were identical to the hash, then return true. So


01010101 ... 1010101010101 hash crappetycrap

would still be considered valid. There's a lot of code out there that 
ignored the fact that after the FFs was specific ASN.1 stuff, and 
just treated it as a defined part of the padding.


Greg.

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


Re: Why the exponent 3 error happened:

2006-09-14 Thread Victor Duchovni
On Thu, Sep 14, 2006 at 11:25:11AM -0400, [EMAIL PROTECTED] wrote:

 
 James A. Donald writes:
 -+---
  | snip
  |
  | ASN.1 provided additional redundant information, making
  | possible unexpected data layouts that should not
  | normally happen.  It had too much expressive power, too
  | much flexibility.  It could express cases that one does
  | not expect to deal with, could flex in more ways than
  | one's software is likely to be written for.
  |
  | snip
 
 Sir,  There is a lesson here as important as
 Fred Brook's Adding people to a late project
 makes it later and I urge you to put this in
 some form of print at your earliest capability.
 No, not urge but rather beg.

If so, I fear we are learning the wrong lesson, which while valid in
other contexts is not pertinent here. TLS must be flexible enough to
accommodate new algorithms, this means that the data structures being
exchanged are malleable, and that implementations must validate strict
adherence to a specifically defined form for the agreed algorithm,
but the ability to express other forms cannot be designed out.

This, in my view, has little to do with ASN.1, XML, or other encoding
frameworks. Thorough input validation is not yet routinely and
consistently practiced by most software developers. Software is almost
invariably written to parse formats observed in practice correctly, and is
then promptly declared to work. The skepticism necessary to continually
question the implicit assumption that the input is well-formed is perhaps
not compatible with being a well-socialized human. The attackers who ask
the right questions to break systems and the few developers who write
truly defensive code are definitely well off the middle of the bell-curve.

It is not just PKCS#1 or X.509v3 that presents opportunities for crafting
interesting messages. MIME, HTTP, HTML, XML, ... all exhibit similar
pitfalls. Loosely speaking, this looks like a variant of Goedel's theorem,
if the protocol is expressive enough it can express problematic assertions.

We can fine-tune some protocols to remove stupid needless complexity, but
enough complexity will remain to make the required implementation disciple
beyond the reach of most software developers (at least as trained today,
but it is not likely possible to design a training program that will
a preponderance all strong defensive programmers).

-- 

 /\ ASCII RIBBON  NOTICE: If received in error,
 \ / CAMPAIGN Victor Duchovni  please destroy and notify
  X AGAINST   IT Security, sender. Sender does not waive
 / \ HTML MAILMorgan Stanley   confidentiality or privilege,
   and use is prohibited.

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


Re: Why the exponent 3 error happened:

2006-09-14 Thread James A. Donald

--
Greg Rose wrote:
 At 19:02  +1000 2006/09/14, James A. Donald wrote:
 Suppose the padding was simply

 010101010101010 ... 1010101010101 hash

 with all leading zeros in the hash omitted, and four
 zero bits showing where the actual hash begins.

 Then the error would never have been possible.

James A. Donald:
 I beg to differ. A programmer who didn't understand
 the significance of crypto primitives would (as many
 did) just search for the end of the padding to locate
 the beginning of the hash, and check that the next set
 of bytes were identical to the hash, then return
 true. So

The hash is known size, and occurs in known position.
He does not search the padding for location, but
examines it for correct format.


 01010101 ... 1010101010101 hash crappetycrap

 would still be considered valid. There's a lot of code
 out there that ignored the fact that after the FFs was
 specific ASN.1 stuff, and just treated it as a defined
 part of the padding.

And that code is correct, and does not have the problem
that we discuss.  Paying attention to ASN.1 stuff is
what is causing this problem.

Code is going wrong because ASN.1 can contain
complicated malicious information to cause code to go
wrong.  If we do not have that information, or simply
ignore it, no problem.

--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 8Jickn3nr3AE+2RW3jUC7DaHw6yD1gLpSTISH0F6
 4Bjf3VmASP+HQ4q0CYdRKgWFZxd/QnFOiartuob5Q

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