# Tag Info

## Hot answers tagged collision-resistance

223

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

83

The risk of collision is only theoretical; it will not happen in practice. Time spent worrying about such a risk of collision is time wasted. Consider that even if you have $2^{90}$ 1MB blocks (that's a billion of billions of billions of blocks -- stored on 1TB hard disks, the disks would make a pile as large of the USA and several kilometers high), risks of ...

58

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

51

how can for example SHA-256 be unique if there is only a limited number of them?! Where your issue occurs is that they're not unique. It's just very improbable that they'll reoccur. Unique in this context is not a mathematical definition, it's a humanist one. In terms of human numbers, $2^{256}$ = ...

48

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

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

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

44

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

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

36

Preimage resistance is about the most basic property of a hash function which can be thought. It means: For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$. (Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash ...

33

A new result shows how to generate single block MD5 collisions, including an example collision: Message 1 Message 2 > md5sum message1.bin message2.bin > 008ee33a9d58b51cfeb425b0959121c9 message1.bin > 008ee33a9d58b51cfeb425b0959121c9 message2.bin There is an earlier example of a single block collision but not technique for generating it was ...

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

33

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

33

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

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

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

30

MD5 was intended to be a cryptographic hash function, and one of the useful properties for such a function is its collision-resistance. Ideally, it should take work comparable to around $2^{64}$ tries (as the output size is $128$ bits, i.e. there are $2^{128}$ different possible values) to find a collision (two different inputs hashing to the same output). (...

30

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

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

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

28

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

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

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

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

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

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

24

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

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