Hi,

Just one remark: As Dan mentioned, collision attacks (find 2 messages such
that their hashes coincide) are of higher concern than pre-image (having a
hash h find a message M / hash(M) = h) and second pre-image attacks (having
a message M find a second message M' / hash(M) = hash(M'), but the
algorithmic complexity of the former (collision attacks) is not half of the
latter, but much lower. Particularly, it is 2^(n/2), n being the length of
the hash, while for pre-image and second pre-image attacks is 2^n. There is
an exponential difference, not linear.

Having said that, there are theoretical attacks that reduce the complexity
needed to find a collision that are below brute force. I say theoretical
because though they are below 2^64 for SHA-1 they are still impractical. As
far as I now, in 2010 Marc Stevens implemented a differential path attack
against SHA-1 with a complexity of about 2^57. I am not very updated on
this topic, so maybe there have been some contributions to the field in the
last year that have gone even beyond that.

Best,

Jorge.

2012/2/17 Miller, Timothy J. <tmiller@mitre.org>

> 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" <swilson@lockstep.com.au> wrote:
>
> >
> >
> >
> >
> >    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:
> >
> >
> >
> >
> >
> >
> >        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:
> >                    pkix-bounces@ietf.org [mailto:pkix-bounces@ietf.org]
> >                    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.
> >
> >
> >
> >
> >_______________________________________________
> >pkix mailing list
> >pkix@ietf.org
> >https://www.ietf.org/mailman/listinfo/pkix
>
> _______________________________________________
> pkix mailing list
> pkix@ietf.org
> https://www.ietf.org/mailman/listinfo/pkix
>