RE: [cryptography] Re: Why the exponent 3 error happened:
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:
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:
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: [cryptography] Re: Why the exponent 3 error happened:
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]
