Re: [tahoe-dev] SHA-1 broken!
On Sat, May 2, 2009 at 12:33 PM, Perry E. Metzger wrote: As just one obvious example of a realistic threat, consider that there are CAs that will happily sell you certificates that use SHA-1. Various clever forgery attacks have been used against certs that use MD5, see: http://www.win.tue.nl/hashclash/rogue-ca/ Those attacks can now be extended to SHA-1 pretty easily. It might require a bit of compute infrastructure -- say a lot of FPGAs and a bunch of cleverness -- to turn out certs quickly, but it can be done. Given that there are lots of high value certs out there of this form, this is rather dangerous. Off-the-shelf FPGA-based device that breaks DES by brute force in about a week, costs 9,000 euros: http://www.copacobana.org/ These are commercially available and programmable. Setting a few of them up to break SHA-1 certainly would not be trivial, but it looks feasible. The design of DES facilitates this kind of throughput/cost gains on FPGAs. Remember that the MD4 family (incl. SHA-1) was designed to be efficient on 32-bit CPUs. For these hash functions, it is much harder to get a throughput/cost gain on FPGAs compared to off-the-shelf CPUs. At least, this was my conclusion when I quickly looked into this a few years ago. Best, Christian -- Christian Rechberger, Graz University of Technology, Austria - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
Quoting "Perry E. Metzger" : Ray Dillinger writes: I cannot derive a realistic threat model from the very general statements in the slides. (BTW, you mean threat, not threat *model*, in this instance.) As just one obvious example of a realistic threat, consider that there are CAs that will happily sell you certificates that use SHA-1. Various clever forgery attacks have been used against certs that use MD5, see: http://www.win.tue.nl/hashclash/rogue-ca/ Those attacks can now be extended to SHA-1 pretty easily. It might It is in my opinion way to early to jump to this kind of conclusions: Even if the new attack works are promised (and I have the feeling that people are too optimistic here), there is the following issue: * these advanced attacks against CAs do require a special type of collision attack (the name "chosen-prefix attack" was coined), not a "normal" collision attack we are talking about here for the case of SHA-1. A chosen-prefix attack can be expected to be significantly harder to perform than a "normal" attack. The link you provided should contain a more in-depth discussion on this for the case of MD5. Nevertheless, I agree that moving away from SHA-1 should be encouraged (since 2005). Best, Christian -- Christian Rechberger, Graz University of Technology, Austria. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Re: Re: Fwd: Potential SHA 1 Hack Using Distributed Computing - Near Miss(es) May be Good Enough
Quoting Paul Hoffman <[EMAIL PROTECTED]>: At 11:31 PM +0200 8/14/07, Christian Rechberger wrote: The mentioned article is indeed confusing, the information in there took apparently several hops. Welcome to the world of public cryptography! :-) At least I haven't seen anyone so far suggest that you will find pre-images. Stay tuned, you never know ;-) Something similar happened last year with our example for "meaningful collisions" for SHA-1 to reduced to 80% of its steps. We gave two meaningful but different ASCII texts followed by some random chunk as an example of our new technique back then. Suddenly someone invented HTML as an example of another application that ended up on a newsticker. To address your questions: Indeed, we have our own "path", but more importantly we developed a new method to speed-up generation and testing of candidate message pairs and apply it to SHA-1. The resulting work factor is still quite high, hence we ask for contributions via the BOINC framework. Is there any estimation of how high? Specifically, do you believe there is a good chance of having less work effort than the current Wang strategy? Seriously, if we wouldn't be convinced that the new method is more efficient than anything else we know of and hence interesting enough to explore further, we wouldn't have started such a project. So yes, this is much faster than Wang's published method, and based on all we know also faster than what is estimated for Wang's latest unpublished methods. Exact comparison is a complicated and delicate issue, and I have to put you of to our upcoming paper on that issue. Your contribution of CPU cycles is of course very welcome. More information on cryptanalytic details, type of collision, and resulting work factor will appear later this year. That's good to hear. It would also be interesting if you could keep a running meter of approximately how much work you are getting from the participants. This isn't nearly as "sexy" as finding ETs or even protein folding... We first plan to provide support for more platforms to increase the size of our potential user base, but next, some meaningful statistics are indeed on our todo-list. -Christian (only sporadic access to mail this week) - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Re: Fwd: Potential SHA 1 Hack Using Distributed Computing - Near Miss(es) May be Good Enough
Quoting Paul Hoffman <[EMAIL PROTECTED]>: At 11:00 PM -0700 8/13/07, Aram Perez wrote: Anyone know more about this? I have the same question. I could not find any description of *why* they think that finding near-misses is going to help the research. It's not clear if they are taking their own path, or trying to improve Wang's path, or what. The mentioned article is indeed confusing, the information in there took apparently several hops. To address your questions: Indeed, we have our own "path", but more importantly we developed a new method to speed-up generation and testing of candidate message pairs and apply it to SHA-1. The resulting work factor is still quite high, hence we ask for contributions via the BOINC framework. More information on cryptanalytic details, type of collision, and resulting work factor will appear later this year. -Christian - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: [Cfrg] Applications of target collisions: Pre or post-dating MD5-based RFC 3161 time-stamp tokens
Alfonso De Gregorio wrote: Hi Steven, hi Benne, Yes, this is a sweet and sour truth. We are not getting closer to preimage attacks. We are getting more far away from considering preimage and second-preimage resistance sufficient hash-function requirements for the real-world security of some protocols. Hi everyone, agreed to all you've said, still there are special examples where bridging this gap seems closer. Consider a special type of preimage resistance, CTFP (Chosen Target Forced Prefix), which was introduced by John Kelsey and Tadayoshi Kohno in their paper "Herding Hash Functions and the Nostradamus Attack" at Eurocrypt 2006. If new methods like the one developed by Marc Stevens for MD5 are sufficiently fast (just being faster than a birthday attack is not enough in this setting), then also herding attacks can be faster. Hence finding a preimage for MD5 in this special setting would be faster than for a good MD-style hash function with the given output size. Collision search for full SHA-1 (especially in this setting) does not seem to be fast enough to allow this speed-up of herding attacks. However, according to our experiments, with some new methods and reducing SHA-1 to e.g. 75% of its steps, this changes. Note that the effort for finding a preimage by looking for lots of collisions in this setting would still be prohibitive in practice. For MD5 and even more so for SHA-1. Note also that this does not allow to draw conclusions on the standard preimage or 2nd-preimage resistance of the mentioned algorithms. This seems a different and challenging problem. Best regards, Christian Rechberger -- Christian Rechberger <[EMAIL PROTECTED]> Krypto Group - IAIK - TU Graz, Inffeldgasse 16a, A-8010 Graz, Austria http://www.iaik.tugraz.at/research/krypto/ phone: +43 (0)316 873 5534 --- fax: +43 (0)316 873 5594 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
