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

[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
BQADggEBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADLL/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 majordomo at metzdowd.com