Subject: [pkix] Off topic: Preimage attack on SHA-1

From: Stephen Wilson <[email-masked]>
Date: Fri, 10 Feb 2012 06:44:26 +1100

Colleagues,

Trying the PKIX list for its cryptographic expertise, I hope you don't 
mind:

Is anyone aware of a demonstrated preimage attack (or demonstrated 
feasibility of a practical preimage attack) on SHA-1?  Is it still the 
case, as it was when RFC4270 was published in 2005, that there is only 
the possibility of Collision attack?

Supplementary question: Does anyone think a preimage attack on the 
signature of a PKC, even if mounted, would be a practical problem?  I 
would have thought there would be so much interference with the rest of 
the data structures that the certificate would become unparseable.

Cheers,

Stephen Wilson
Lockstep

http://lockstep.com.au <http://www.lockstep.com.au>
Lockstep Consulting provides independent specialist advice and analysis
on digital identity and privacy.Lockstep Technologies develops unique
new smart ID solutions that enhance privacy and prevent identity theft.

---

From: Dan Brown <[email-masked]>
Date: Thu, 16 Feb 2012 21:16:32 +0000

Hi Stephen,

Regarding your supplementary question:

1)      You're right that the pre-image would need to meet the X.509 ToBeSigend format, so it would depend on the nature of the pre-image attack.  Any pre-image attack on SHA-1 would require about 160 bits of flexibility in the pre-image format (i.e. to have a large enough target pre-image space to ensure that pre-images of the hash value to be inverted exists).  I'm not sure how much flexibility there is in the X.509 format, but I think the serial number could support a sequence of freely chosen bits, which may be a simple enough formatting restriction to accommodate some pre-image attacks. (Although the resulting serial number may be larger than usual, so could be viewed as suspicious.)  The public exponent in an RSA key could support 160 bits, but the result would look suspicious.  The subject name has a large amount of flexibility, but it seems especially unlikely that an actual faster-than-generic pre-image attack have the needed control in the pre-image.

2)      The answer also depends the vulnerability of the signature algorithm to hash pre-image attacks.  The algorithms DSA and ECDSA admit existential forgery using a hash pre-image finder, and so does RSA-PSS as specified in PKCS#1 version 2.1 (but as far as I can tell not RSA-PSS as originally propose by Bellare and Rogaway).  I don't see how a hash pre-image finder suffices to forge an RSA-PKCS1-v1.5 signature.

3)      Under generic attacks, a hash functions's pre-image resistance has about the twice the security level of the collision resistance (exhaustive search vs. birthday).  Typically, the public key is chosen to have a security level half that of the pre-image resistance of hash.  So, normally hash pre-image attacks are not a concern for signatures, unless they are very drastic improvements over exhaustive search.

Best regards,

Daniel Brown

Research In Motion Limited

From: [email-masked] [mailto:[email-masked]] On Behalf Of Stephen Wilson
Sent: Thursday, February 09, 2012 2:44 PM
To: pkix
Subject: [pkix] Off topic: Preimage attack on SHA-1

Colleagues,

Trying the PKIX list for its cryptographic expertise, I hope you don't mind:

Is anyone aware of a demonstrated preimage attack (or demonstrated feasibility of a practical preimage attack) on SHA-1?  Is it still the case, as it was when RFC4270 was published in 2005, that there is only the possibility of Collision attack?

Supplementary question: Does anyone think a preimage attack on the signature of a PKC, even if mounted, would be a practical problem?  I would have thought there would be so much interference with the rest of the data structures that the certificate would become unparseable.

Cheers,

Stephen Wilson
Lockstep
http://lockstep.com.au<http://www.lockstep.com.au>
Lockstep Consulting provides independent specialist advice and analysis
on digital identity and privacy.  Lockstep Technologies develops unique
new smart ID solutions that enhance privacy and prevent identity theft.

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Dan Brown <[email-masked]>
Date: Thu, 16 Feb 2012 22:30:52 +0000

Hi,

Just to clarify myself [at others' advice] when I said "Under generic attacks", the adjective "generic" meant that to restrict consideration to attacks that apply to all hash functions (i.e. even a random oracle).  In particular, I definitely did ***not*** mean to say that if MD5 has only 23 bits of collision resistance, then it only has 46 bits of pre-image resistance.  As far as I know, MD5 has 128 bits of pre-image resistance.  The 2^23 cost MD5 collision attack is not a "generic" attack, but a specific attack, so it was meant to excluded from that statement.  

To worsen things, my choice of the word "twice" could have misleadingly implied a relation between the attacks.  I erred on the side of brevity, to avoid saying "twice", I should have re-stated the cost of generic attacks in terms of hash-function output length.  In particular, I do not know of a way to convert a collision attack into a pre-image attack.  (There are conversions the other way, that would be getting even more off-topic.)

Sorry if I've caused any confusion.

Daniel Brown

From: [email-masked] [mailto:[email-masked]] On Behalf Of Dan Brown
Sent: Thursday, February 16, 2012 4:17 PM
To: [email-masked]'; pkix
Subject: Re: [pkix] Off topic: Preimage attack on SHA-1

---

From: Stephen Wilson <[email-masked]>
Date: Fri, 17 Feb 2012 10:02:03 +1100

Many thanks Dan for this and the subsequent clarification.

Can I ask a silly question: I've assumed that in preimage attacks [where 
synthetic data A' is computed so that Hash(A') == Hash(A) original data 
A] it is not necessary for A and A' to have the same bit length.  I am 
guessing that computing A' is a whole lot easier if you can make it as 
long as you like.

Now, you ponder "how much flexibility there is in the X.509 format" and 
I it's fair to say there is a lot.  You can add totally custom fields to 
a certificate and in general, most X.509 parsers will skip over them.

So here's a thought.  If A' can be longer than A, then a preimage 
attacker could add a nonsense field to the SHA1+RSA profile of interest, 
and populate that extra field with whatever data is needed to 
'compensate' for tampering with data in the original body of the 
certificate (say the public key value). The nonsense field might be 
arbitrarily long and still escape the notice of the applications 
consuming the certificates.

Cheers,

Steve Wilson.

On 17/02/2012 8:16 AM, Dan Brown wrote:
> 1)You're right that the pre-image would need to meet the X.509 
> ToBeSigend format, so it would depend on the nature of the pre-image 
> attack.  Any pre-image attack on SHA-1 would require about 160 bits of 
> flexibility in the pre-image format (i.e. to have a large enough 
> target pre-image space to ensure that pre-images of the hash value to 
> be inverted exists).  I'm not sure how much flexibility there is in 
> the X.509 format, but I think the serial number could support a 
> sequence of freely chosen bits, which may be a simple enough 
> formatting restriction to accommodate some pre-image attacks. 
> (Although the resulting serial number may be larger than usual, so 
> could be viewed as suspicious.)  The public exponent in an RSA key 
> could support 160 bits, but the result would look suspicious.  The 
> subject name has a large amount of flexibility, but it seems 
> especially unlikely that an actual faster-than-generic pre-image 
> attack have the needed control in the pre-image.
>
> 2)The answer also depends the vulnerability of the signature algorithm 
> to hash pre-image attacks.  The algorithms DSA and ECDSA admit 
> existential forgery using a hash pre-image finder, and so does RSA-PSS 
> as specified in PKCS#1 version 2.1 (but as far as I can tell not 
> RSA-PSS as originally propose by Bellare and Rogaway).  I don't see 
> how a hash pre-image finder suffices to forge an RSA-PKCS1-v1.5 signature.
>
> 3)Under generic attacks, a hash functions's pre-image resistance has 
> about the twice the security level of the collision resistance 
> (exhaustive search vs. birthday).  Typically, the public key is chosen 
> to have a security level half that of the pre-image resistance of 
> hash.  So, normally hash pre-image attacks are not a concern for 
> signatures, unless they are very drastic improvements over exhaustive 
> search.
>
> Best regards,
>
> Daniel Brown
>
> *From:[email-masked] [mailto:[email-masked]] *On Behalf 
> Of *Stephen Wilson
> *Sent:* Thursday, February 09, 2012 2:44 PM
> *To:* pkix
> *Subject:* [pkix] Off topic: Preimage attack on SHA-1
>
>
> Colleagues,
>
> would have thought there would be so much interference with the rest 
> of the data structures that the certificate would become unparseable.
>
> Cheers,
>
>
> Stephen Wilson
> Lockstep
>
> This transmission (including any attachments) may contain confidential 
> information, privileged material (including material protected by the 
> solicitor-client or other applicable privileges), or constitute 
> non-public information. Any use of this information by anyone other 
> than the intended recipient is prohibited. If you have received this 
> transmission in error, please immediately reply to the sender and 
> delete this information from your system. Use, dissemination, 
> distribution, or reproduction of this transmission by unintended 
> recipients is not authorized and may be unlawful.

---

From: Dan Brown <[email-masked]>
Date: Fri, 17 Feb 2012 15:44:14 +0000

Hi Stephen and PKIX List,

One more clarification: in the case of DSA and ECDSA, if the group size is sufficiently larger than the hash size, then I don't know how a pre-image attack on the hash could be used to forge a signature (in a public-key only attack, i.e. no chosen message signature queries).   For example, consider, ECDSA with P-384 and SHA-1.  The conditional forgery attack (that I know of) has a step where it generates a special random-like 384-bit integer for which it needs find a SHA-1 pre-image.  The step of computing this integer would have to be iterated about 2^224 random values on average to get the 384-bit integer small enough to be a SHA-1 output (so with the parameters this attack is slower than finding the private key).  (... Of course, a pre-image attack could be also used to find collisions, and then a chosen-message signing query can be used to make a forgery, and one still needs to consider direct collision attacks.  So, I won't get into overall security levels ...)

Best regards,

Daniel Brown

Context:

---

From: "Miller, Timothy J." <[email-masked]>
Date: Fri, 17 Feb 2012 20:27:58 +0000

Arjen Lenstra and Benne de Weger's work with MD5 may be of interest to
you.  Not a preimage attack, but the method of integrating a collision
into X.509 may be relevant.

http://www.win.tue.nl/~bdeweger/CollidingCertificates/

-- T

On 2/16/12 5:02 PM, "Stephen Wilson" <[email-masked]> wrote:

>    Can I ask a silly question: I've assumed that in preimage attacks
>    [where synthetic data A' is computed so that Hash(A') == Hash(A)
>    original data A] it is not necessary for A and A' to have the same
>    bit length.  I am guessing that computing A' is a whole lot easier
>    if you can make it as long as you like.
>    
>    Now, you ponder "how much flexibility there is in the X.509 format"
>    and I it's fair to say there is a lot.  You can add totally custom
>    fields to a certificate and in general, most X.509 parsers will skip
>    over them.  
>    
>    attacker could add a nonsense field to the SHA1+RSA profile of
>    interest, and populate that extra field with whatever data is needed
>    to 'compensate' for tampering with data in the original body of the
>        Hi
>            Stephen,
>        1)     
>              You¹re
>            right that the pre-image would need to meet the X.509
>            ToBeSigend format, so it would depend on the nature of the
>            pre-image attack.  Any pre-image attack on SHA-1 would
>            require about 160 bits of flexibility in the pre-image
>            format (i.e. to have a large enough target pre-image space
>            to ensure that pre-images of the hash value to be inverted
>            exists).  I¹m not sure how much flexibility there is in the
>            X.509 format, but I think the serial number could support a
>            formatting restriction to accommodate some pre-image
>            attacks. (Although the resulting serial number may be larger
>            than usual, so could be viewed as suspicious.)  The public
>            exponent in an RSA key could support 160 bits, but the
>            result would look suspicious.  The subject name has a large
>            amount of flexibility, but it seems especially unlikely that
>            an actual faster-than-generic pre-image attack have the
>            needed control in the pre-image.
>         
>        2)     
>              The
>            answer also depends the vulnerability of the signature
>            algorithm to hash pre-image attacks.  The algorithms DSA and
>            ECDSA admit existential forgery using a hash pre-image
>            finder, and so does RSA-PSS as specified in PKCS#1 version
>            2.1 (but as far as I can tell not RSA-PSS as originally
>            propose by Bellare and Rogaway).  I don¹t see how a hash
>            pre-image finder suffices to forge an RSA-PKCS1-v1.5
>            signature.
>         
>        3)     
>              Under
>            generic attacks, a hash functions¹s pre-image resistance has
>            about the twice the security level of the collision
>            resistance (exhaustive search vs. birthday).  Typically, the
>            public key is chosen to have a security level half that of
>            the pre-image resistance of hash.  So, normally hash
>            pre-image attacks are not a concern for signatures, unless
>            they are very drastic improvements over exhaustive search.
>            
>         
>        Best
>            regards,
>         
>        
>          
>            
>              
>                
>                  Daniel
>                      Brown
>                
>              
>              
>                
>                  Research
>                      In Motion Limited
>                
>              
>            
>          
>           
>          
>            
>              
>                
>                
>              
>            
>          
>           
>          
>            
>              
>                
>                  
>                
>              
>              
>                
>                
>              
>            
>          
>           
>          
>            
>              
>                From:
>                    [email-masked] [mailto:[email-masked]]
>                    On Behalf Of Stephen Wilson
>              Trying the PKIX
>                  list for its cryptographic expertise, I hope you don't
>                  mind:
>                
>                
>              Is anyone aware
>                  of a demonstrated preimage attack (or demonstrated
>                  feasibility of a practical preimage attack) on SHA-1?
>                  Is it still the case, as it was when RFC4270 was
>                  published in 2005, that there is only the possibility
>                  of Collision attack?
>                
>              Supplementary
>                  question: Does anyone think a preimage attack on the
>                  signature of a PKC, even if mounted, would be a
>                  practical problem?  I would have thought there would
>                  be so much interference with the rest of the data
>                  structures that the certificate would become
>                  unparseable.
>                
>              Cheers,
>                
>                
>              
>            Stephen Wilson
>                Lockstep
>      This transmission (including any attachments) may contain
>      confidential information, privileged material (including material
>      protected by the solicitor-client or other applicable privileges),
>      or constitute non-public information. Any use of this information
>      by anyone other than the intended recipient is prohibited. If you
>      have received this transmission in error, please immediately reply
>      to the sender and delete this information from your system. Use,
>      dissemination, distribution, or reproduction of this transmission
>      by unintended recipients is not authorized and may be unlawful.
>    
>
>  
>
>_______________________________________________
>pkix mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/pkix