# Tag Info

228

Take a simple mathematical operation like addition. Addition takes 2 inputs and produces 1 output (the sum of the two inputs). If you know the 2 inputs, the output is easy to calculate - and there's only one answer. 321 + 607 = 928 But if you only know the output, how do you know what the two inputs are? 928 = 119 + 809 928 = 680 + 248 928 = 1 + 927 ... ...

131

The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always gives the same answer; random in the sense that the value of the hash is basically unpredictable without actually computing it. And sufficiently unpredictable that, ...

60

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

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

51

The difference is in the choice of $m_1$. In the first case (second preimage resistance), the attacker is handed a fixed $m_1$ to which he has to find a different $m_2$ with equal hash. In particular, he can't choose $m_1$. In the second case (collision resistance), the attacker can freely choose both messages $m_1$ and $m_2$, with the only requirement that ...

46

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

38

As you correctly observed, for any function $H\colon \{0,1\}^\ast\to\{0,1\}^n$ collisions must exist, simply because $\{0,1\}^\ast$ is an infinite set and $\{0,1\}^n$ is finite. One could define "hash function" to mean something else (e.g., taking only a bounded input length), but this is non-standard. However, the term "collision resistance" denotes ...

35

Just to show you how easy it is today to create collisions on MD5: One could create collisions using Marc Steven's HashClash on AWS and estimated the the cost of around $0.65 per collision. These 2 images have the same md5 hash: 253dd04e87492e4fc3471de5e776bc3d If you want to test it yourself and the images below do not give you the MD5 hash ... 35 Cryptographically secure hashes were specifically build to (among other things) make what you're asking hard! Now, you could try to create an appropriate dictionary of all hashes, hoping to find appropriate pairs... but it would take more storage space than the total storage space that's currently available on our planet and more computing power than you'll ... 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 ... 34 Define$H(x) = \operatorname{SHA-256}(x) \mathbin\| 1$; that is, append a single 1 bit to SHA-256. Can you find a collision under$H$? Does$H$have anything resembling uniform distribution? This counterexample is not merely pathological; designs like Rumba20 and VSH provide collision resistance but neither preimage resistance nor uniformity. That said, ... 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 Definition In the Damgard-Merkle construction for hash functions the compression function takes as input: a message block and a chaining value. For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given. A freestart collision is a collision where the attacker can choose the ... 31 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 (... 31 Firstly, some definitions; Pre-image resistant: given a hash value$h$find a message$m$such that$h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account. Second Pre-image resistant: given a message$m_1$is should be computationally infeasible to find another message$m_2$... 30 SHA-256 is based on a Davies–Meyer compression function. Easy to find fixed-points are a known property of this construction. A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute fixed points for the construction : for any$m$, one can find a value of$h$such that$...

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

You are right, hashes won't be all unique as you already have shown. The important part are practical collisions - how many SHA-512 hashes can the whole earth generate in its lifetime? Definitely much less than $2^{512}$, it's even less than $2^{128}$. Let's guess unrealistically high and say we generate these $2^{128}$ hashes from perfectly random input, ...

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

After spending more than two weeks reading well over 750 pages while checking the following (PDF) documents… Sponge Functions Cryptographic sponge functions Security Analysis of Extended Sponge Functions Cryptographic Hash Functions: Recent Design Trends and Security Notions On the Implementation Aspects of Sponge-based Authenticated Encryption for ...

28

$\text{SHA256}$ is designed to behave as a random function. Under that assumption, it is expected that for most 256-bit $v$, there is no positive integer $n$ with $\text{SHA256}^n(v)$ equal to $v$. Otherwise said, most $v$ do not belong to a cycle. To illustrate this visually, in the following picture showing iteration of a 7-bit hash, I drew the points ...

27

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

27

Birthday problem for cryptographic hashing, 101. Let $p_n$ be the probability of collision for a number $n$ of random distinct inputs hashed to $k$ possible values (that is, probability that at least two hashes are identical), on the assumption that the hash is perfect. That $p_n$ is also the minimum probability of collision with no hypothesis on the hash. ...

26

Collisions of RSA keys should never happen for realistic key sizes and good random number generators. Assume a 1024 bit RSA key; the primes from which it has been derived are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about $2^{500}$ or $10^{150}$ ...

26

Yes, for any secure cryptographic hash function, it is overwhelmingly likely that there exists a string which contains, or even begins with, its own hash value (in any given encoding, even). However, if the hash function is indeed secure, it is also exceeding unlikely that we could ever find such a string. First, let's look on the positive side. A good ...

26

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution? This is obviously someone who threw something together without knowing what they were doing. If they knew what they were doing, they wouldn't roll their own algorithm (“Dave, ...

24

Strictly speaking, you can, and it stands to reason that you can. A SHA-1 hash has $2^{160}$ possible values. If we just consider $100$ byte binary plaintexts, well, there are $2^{800}$ possible ones of those. So it stands to reason that for any SHA-1 hash, there are likely to be around $2^{640}$ $100$ byte binary plaintexts that would match it.* When two ...

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