Hot answers tagged

81

In order to get a collision on a $n$ bit Random Oracle using the birthday paradox, one needs $\sqrt{\pi / 2} \cdot 2^{n/2}$ calls. In other words, in the case of the 160 output bits of SHA-1 the limit is in the order of $2^{160/2} = 2^{80}$. Previous Attacks SHA-1 (and the broken SHA-0) have been under the following attacks over the past few years: ...


61

As a general rule, you should not use SHA1; instead, go with one of the hash functions from the SHA-2 family. As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, SHA-512/256, and SHA-512/384, ...


53

Yes, SHA1-signed certificates are unsafe. The SHAttered paper is instructive. From the introduction: The MD-SHA family of hash functions is the most well-known hash function family, which includes MD5, SHA-1, and SHA-2 that have all found widespread use. This family originally started with MD4 in 1990, which was quickly replaced by MD5 in 1992 due to ...


47

Actually SHA-1 has been "officially insecure" for a longer time, since an attack method was published in 2011. The 2017 collisions was just the first known case of actually running the attack. But everybody was already quite convinced that the attack worked, and, indeed, the 2017 collision was produced with the expected computational cost. The important ...


45

We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks. Even when there were no known collisions in SHA-1, we still called collision resistance of SHA-1 broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$...


37

Would you use HMAC-SHA1 or HMAC-SHA256 for message authentication? Yes. That is a semi-serious answer; both are very good choices, assuming, of course, that a Message Authentication Code is the appropriate solution (that is, both sides share a secret key), and you don't need extreme speed. How much HMAC-SHA256 is slower than HMAC-SHA1? Those sorts of ...


35

The functions considered are binary functions of 3 bits to 1 bit (extended to bit vectors, that is bitwise functions). There are $2^{(2^3)}=256$ such functions. All the functions considered are balanced; that is, there is an equal number of input combinations for which the function outputs 0 and for which the function outputs 1. That reduces the number of ...


34

The answer is "not safe". But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice. Google found one collision based on some existing, publicly known collision attacks on SHA-1. Sees the introduction of Google's paper for a complete list of prior work. First, let me briefly explain how RSA-SHA1 ...


33

This answer is now out of date as on Feb 23 2017, a collision for SHA-1 was found. See What is the new attack on SHA-1 “SHAttered” and how does it work? In short, no. So, what is the current state of cryptanalysis with SHA-1 (for reference only as this question relates to SHA-2) and SHA-2? Bruce Schneier has declared SHA-1 broken. That is because ...


32

The existence of the SHAttered result is not, I think, in itself a surprise: everyone knows that in theory you can create two streams of bytes that hash to the same value. Google's achievements (which I don't wish to downplay) are (a) that they mustered enough resources to actually do this, and (b) they did so while keeping the colliding file a valid PDF (...


29

First up, the following table should provide a nice comparison of the SHA algorithms and their status back in 2013, when I fist posted this answer: [38] The theoretical attack on SHA-1 refers to “Freestart collision for full SHA-1” (PDF) by Marc Stevens and Pierre Karpman and Thomas Peyrin, first published 8 October 2015. Meanwhile – in 2017 – ...


29

a. No such double hashing doesn't do a bit of good. Anything which collides after a single hash will definetly collide after a double hash. It preserves all collisions and adds new ones. We might consider other constructions which may provide some strength e.g $H(H(m) || m)$ however: b. We have no need for any such double hashing of SHA1 as we have newer ...


28

MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992). The main structural differences are the following: SHA-1 has a larger state: 160 bits vs 128 bits. SHA-1 has more rounds: 80 vs 64. SHA-1 rounds have an ...


28

In the first section of this answer I'll assume that through better hardware or/and algorithmic improvements, it has become routinely feasible to exhibit a collision for SHA-1 by a method similar to that of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu's attack, or Marc Stevens's attack. This has been achieved publicly in early 2017, and had been clearly ...


26

I have 3 answers: We can't fix SHA-1, we shouldn't fix SHA-1 and we already did fix SHA-1. SHA-1 is a hash standard; many different people can and have implemented it and they all get the same results. SHA-1 is broken. We have to replace it and convince everybody to move on to a new standard. A fixed SHA-1 wouldn't be SHA-1. We shouldn't try a minimal fix; ...


25

For any one of the SHA hashes, the hash should be indistinguishable from pseudo-random. That means each and every bit flips with a chance of 50%. So on average half of the amount of bits gets flipped, as long as the input message doesn't repeat (because that will match 100% with the hash of the identical message, of course). It doesn't matter how many input ...


23

The initial values to a Merkle–Damgård type hash function are essentially the plaintext to a block cipher, with the input to the hash function becoming the key. The maximum length of the hash is determined by the amount of bits of initial value. Five 32-bit words gives SHA1 a state size and maximum output of 160 bits. In order for an MD type hash function to ...


23

We can fix SHA-1 but why? SHA-1 is broken. We cannot fix it without modifying result (so compability won't be preserved). We can make changes that will fix it... for now, and also will make it inefficient. What are gains? That perhaps implementation will be somewhat easier... That is not much for fixing something that has only 160bit security and something ...


23

TL;DR; Just give me the numbers; \begin{array} {|c|l|l|}\hline & \text{in a Day} & \text{in an Year} \\ \hline \text{Summit} & \approx 2^{63} \text{ SHA-1} & \approx 2^{72} \text{ SHA-1}\\ \hline \text{Titan} & \approx 2^{62} \operatorname{ SHA-1} & \approx 2^{71} \operatorname{ SHA-1}\\ \hline \text{Bitcoin Miners} & \approx ...


23

Hash random values until you get a hash with two leading zeroes. We would expect about 1 in 4 values to have a hash-value of that form. So let's try this: echo hello | sha1sum f572d396fae9206628714fb2ce00f72e94f2258f - Nope. echo hello1 | sha1sum 0ef562ff2d0c21358f9d289f1c908436714fc923 - There we are, 4 leading zeroes.


21

I would use HMAC-SHA256. While poncho's answer that both are secure is reasonable, there are several reasons I would prefer to use SHA-256 as the hash: Attacks only get better. SHA-1 collision resistance is already broken, so it's not impossible that other attacks will also be possible in the future. It allows you to depend on just one hash function, which ...


21

It is an approximately1 $2^{64}$ time identical-prefix collision attack on SHA-1 based on the same principles as Marc Stevens' earlier attacks on SHA-1. It is the first practical collision attack on the full SHA-1 function, so obviously notable and a great achievement, even though SHA-1 was known to be broken for years. The attack itself works in two parts, ...


20

Hardened SHA-1 detects collisions built of a certain form, If someone were to find a collision using brute-force birthday attack (currently not feasible) the detection would not work. The vectors are specific small differences which may help to convert a near collision into a full collision. The details are in the paper: https://marc-stevens.nl/research/...


20

Does hashing algorithms have an upper bound in the input space? They can, but they don't have to and it depends on their specification. All Merkle-Damgård based hash functions do have an upper limit, because appending the message length simplifies the security proof and the backdoor-resistance of the function and they usually use a fixed-length encoding of ...


19

No. The wikipedia article is in my honest opinion misrepresenting this article on a reduced round attack on the SHA-2 family of hashes. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family. In other words, no collisions have been found in any of the SHA-2 hashes. The ...


17

When people say HMAC-MD5 or HMAC-SHA1 are still secure, they mean that they're still secure as PRF and MAC. The key assumption here is that the key is unknown to the attacker. $$\mathrm{HMAC} = \mathrm{hash}(k_2 | \mathrm{hash}(k_1 | m)) $$ Potential attack 1: Find a universal collision, that's valid for many keys: Using HMAC the message doesn't get ...


17

There is a huge difference between $2^{-64}$ probability of failure, which is indeed very small, and having to run $2^{64}$ in order to carry out the attack. The latter is much too small to be considered reasonable. Of course, one could argue about protecting secrets that are not very significant and you only need weak protection. However, it is usually very ...


16

Why is it it’s so much harder to execute a successful collision on certificates than it is on text data? It's not. Actually, the attacker does have to worry about the sequence number that the CA will use, however as we seen from the successful MD5 attacks, that's a solvable problem. What's more difficult is coming up with a useful (to the attacker) ...


15

The echo command will include a newline at the end. So when you use echo 'Rosetta Code' | sha1sum you are actually hashing the string Rosetta Code\n. Do the test using echo -n, the -n flag prevents the trailing newline character. Doing echo -n 'Rosetta Code' | sha1sum gives the same 48c98f7e5a6e736d790ab740dfc3f51a61abe2b5 hash that you were seeing ...


15

Surprisingly enough, it would appear that generating a simultaneous collision wouldn't be that much more expensive than generating a single collision for SHA-1. The basic idea is to form a $2^{64}$ wide multicollision on SHA-1; that is, $2^{64}$ distinct messages that all SHA-1 hash to the same value. We can do this by using Joux's idea of forming finding ...


Only top voted, non community-wiki answers of a minimum length are eligible