6 ms·

Do sha1, sha2 have similar weakness?

by srcmap 12y ago

kingnothing 12y ago
There aren't any known collisions for either of those algorithms.
ygra 12y ago
SHA-1 can be considered near-broken at this point¹, as far as I remember. No actual successful attack like with MD5, but close enough to be theoretically possible in the foreseeable future. There was fear that the attacks could be extended to SHA-2, thus we now have SHA-3 too. However, SHA-2 remains secure for now. _____ ¹ Wikipedia: »As of 2012, the most efficient attack against SHA-1 is considered to be the one by Marc Stevens[34] with an estimated cost of $2.77M to break a single hash value by renting CPU power from cloud servers.« I.e. it's quite expensive, but can be done in a reasonable time, especially by adversaries with interest and funds to do so.
- 13 12y ago
  It would be a lot cheaper to approach industries which already have very large FPGA clusters (weather forecasting do, for example) and rent some compute time on them with your own bitsteam. Problems like this are embarrassingly parallel and very suited to hardware based attacks, given sufficient financial motivation. Time for a kickstarter, maybe?
- tptacek 12y ago
  There is no indication that SHA-2 is threatened in any practical way. SHA-1 and SHA-2 are similar at an architectural level, in some of the same ways that two mid-1990s Feistel ciphers might be similar, and share building blocks, but they aren't the same hash function. They are much more different than, say, DES and 3DES. SHA-2 remains the best practical choice for most systems today. The truncated variants (like SHA2-512/256) even break length extension exploits.
gojomo 12y ago
No one has yet shown that SHA-1 collisions are possible, as with this MD5 technique, but it's known that SHA-1 isn't as strong against potential attacks as it was designed-to-be. That knowledge has driven adoption of SHA-2, and was partial motivation for the (completed in 2012) competition to design SHA-3. I don't believe any weaker-than-designed problems have yet been found with the SHA-2 family. In 2012, Bruce Schneier reported on an analysis by Jesse Walker of Intel about when SHA-1 collisions might be practical to create: https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_... That analysis suggests: "A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021." But it also notes non-commodity approaches (GPUs, custom chips, etc) could achieve SHA-1 collisions sooner/cheaper.
- deleted 12y ago
  [deleted]
kapitalx 12y ago
Every time you map a large set to a smaller set, you are bound to have collisions[1]. In other words, all hashing algorithms which map input data to a bounded string will have collisions. Depending on what you're using the hashing function for, it just becomes a matter of how feasible it is to either find a collision or find the data which yielded the hash. [1] http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle Edit: source
- baddox 12y ago
  While that's true, I wouldn't call the pigeonhole principle a remotely similar weakness to the chosen prefix collision attack vulnerability in MD5. The feasibility of finding a collision in MD5 has little to do with the number of pigeonholes in MD5.
  - kapitalx 12y ago
    Not at all. Not to completely repeat myself, I'm merely saying that all such hash functions will have collisions. So the fact you have collisions doesn't imply weakness as it's a fact of life. So all you're left with is to look at the feasibility of finding a collision. We're both saying the same thing IMO.
miahi 12y ago
This is not new at all, I remember playing with MD5 collisions in 2006, but it's good to be discussed from time to time so that we know we cannot trust such things. We're getting there with reduced SHA-1[1] (that is, less than 80 rounds, that means less than 2^80 theoretical operations[2]). But the cost of finding a collision decreases over time[3], and this is why everybody says SHA-1 is obsolete. [1] http://eprint.iacr.org/2010/413.pdf http://eprint.iacr.org/2010/413.pdf [2] https://www.schneier.com/blog/archives/2005/02/sha1_broken.html https://www.schneier.com/blog/archives/2005/02/sha1_broken.h... [3] https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_...

Do sha1, sha2 have similar weakness?

by srcmap 12y ago

Do sha1, sha2 have similar weakness?

kingnothing 12y ago

There aren't any known collisions for either of those algorithms.

ygra 12y ago

SHA-1 can be considered near-broken at this point¹, as far as I remember. No actual successful attack like with MD5, but close enough to be theoretically possible in the foreseeable future. There was fear that the attacks could be extended to SHA-2, thus we now have SHA-3 too. However, SHA-2 remains secure for now. _____ ¹ Wikipedia: »As of 2012, the most efficient attack against SHA-1 is considered to be the one by Marc Stevens[34] with an estimated cost of $2.77M to break a single hash value by renting CPU power from cloud servers.« I.e. it's quite expensive, but can be done in a reasonable time, especially by adversaries with interest and funds to do so.

13 12y ago
It would be a lot cheaper to approach industries which already have very large FPGA clusters (weather forecasting do, for example) and rent some compute time on them with your own bitsteam. Problems like this are embarrassingly parallel and very suited to hardware based attacks, given sufficient financial motivation. Time for a kickstarter, maybe?
tptacek 12y ago
There is no indication that SHA-2 is threatened in any practical way. SHA-1 and SHA-2 are similar at an architectural level, in some of the same ways that two mid-1990s Feistel ciphers might be similar, and share building blocks, but they aren't the same hash function. They are much more different than, say, DES and 3DES. SHA-2 remains the best practical choice for most systems today. The truncated variants (like SHA2-512/256) even break length extension exploits.

gojomo 12y ago

No one has yet shown that SHA-1 collisions are possible, as with this MD5 technique, but it's known that SHA-1 isn't as strong against potential attacks as it was designed-to-be. That knowledge has driven adoption of SHA-2, and was partial motivation for the (completed in 2012) competition to design SHA-3. I don't believe any weaker-than-designed problems have yet been found with the SHA-2 family. In 2012, Bruce Schneier reported on an analysis by Jesse Walker of Intel about when SHA-1 collisions might be practical to create: https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_... That analysis suggests: "A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021." But it also notes non-commodity approaches (GPUs, custom chips, etc) could achieve SHA-1 collisions sooner/cheaper.

deleted 12y ago
[deleted]

kapitalx 12y ago

Every time you map a large set to a smaller set, you are bound to have collisions[1]. In other words, all hashing algorithms which map input data to a bounded string will have collisions. Depending on what you're using the hashing function for, it just becomes a matter of how feasible it is to either find a collision or find the data which yielded the hash. [1] http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle Edit: source

baddox 12y ago
While that's true, I wouldn't call the pigeonhole principle a remotely similar weakness to the chosen prefix collision attack vulnerability in MD5. The feasibility of finding a collision in MD5 has little to do with the number of pigeonholes in MD5.
- kapitalx 12y ago
  Not at all. Not to completely repeat myself, I'm merely saying that all such hash functions will have collisions. So the fact you have collisions doesn't imply weakness as it's a fact of life. So all you're left with is to look at the feasibility of finding a collision. We're both saying the same thing IMO.

miahi 12y ago

This is not new at all, I remember playing with MD5 collisions in 2006, but it's good to be discussed from time to time so that we know we cannot trust such things. We're getting there with reduced SHA-1[1] (that is, less than 80 rounds, that means less than 2^80 theoretical operations[2]). But the cost of finding a collision decreases over time[3], and this is why everybody says SHA-1 is obsolete. [1] http://eprint.iacr.org/2010/413.pdf http://eprint.iacr.org/2010/413.pdf [2] https://www.schneier.com/blog/archives/2005/02/sha1_broken.html https://www.schneier.com/blog/archives/2005/02/sha1_broken.h... [3] https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_...