# Tag Info

82

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: ...

53

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 ...

52

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 ...

40

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 ...

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 (...

30

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 ...

29

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 ...

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 ...

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; ...

26

TL;DR; Just give me the numbers; \begin{array} {|l|c|c|c|c|}\hline & \text{in a second} & \text{in an hour} & \text{in a day} & \text{in a year} \\ \hline \text{Summit on SHA-1} & \approx 2^{49.7} & \approx 2^{61.5} & \approx 2^{66.1} & \approx 2^{74.6} \\ \hline \text{Titan on SHA-1} & \approx 2^{49.1}& \approx ...

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 ...

25

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.

23

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, ...

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 ...

22

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

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

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 ...

18

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 ...

16

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 ...

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

Password hashes need first pre-image resistance and should not cause many collisions among typical passwords (preserve the entropy). This collision "attack" violates neither requirement and causes no practical security issues. While this issue can find trivial collisions, they're not between commonly chosen passwords. A SHA-1 hash (and thus the shorter of ...

14

They are all hash functions. Apart from that, they are structurally quite different. The SHA family (SHA-0, SHA-1, and the SHA-2 functions such as SHA-256 and SHA-512) use the Merkle-Damgård construction, around an internal permutation which happens to be an extended Feistel network. Low-level primitives include boolean bitwise operations, and addition over ...

13

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509. I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised that ...

13

The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like ...

12

Short answer: don't. Use a password hash like PBKDF2, scrypt or bcrypt. Also, if at all possible, use a library that takes care of the low level stuff like password database for you. E.g. passlib might work if you use Python. I'm sorry if that sounds blunt, but that's how it is. To answer your actual questions: There is just only one thing which bothers ...

12

Because the RFC says so. Signing and verifying using this key format is done according to the Digital Signature Standard [FIPS-186-2] using the SHA-1 hash [FIPS-180-2]. It says the same for RSA half a page down. Apparently the signature algorithm is a defined part of the public key method's specification, rather than being negotiated separately like the ...

12

Expanding then shrinking in SHA-1 refers to the process, performed for each round (each 512-bit block of padded message), of message expansion from 512 bits to 2560 bits; keeping only 160 bits of state for the next round. The later directly follows from the construction of SHA-1 as a Merkle-Damgård hash of 160 bit. The former occurs because SHA-1's ...

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