Difficulty of finding two different inputs that hash to the same value

learn more… | top users | synonyms (1)

37
votes
1answer
3k views

What is a “freestart collision”?

In their work on SHA-1 collisions (cf. the currently unpublished paper “Freestart collision on full SHA-1” by Stevens, Karpman, and Peyrin) Stevens et al show that they are able to generate "freestart ...
0
votes
0answers
68 views

MD5 SSL Collision Attack

I want to create fake certificate for test purposes. I have read about the http://marc-stevens.nl/p/hashclash/index.php project but I am unable to understand the two files that I have to put as input ...
3
votes
0answers
126 views

Are there MD5 collisions for inputs of different length?

There are many examples of MD5 collisions (some of them can be found here Are there two known strings which have the same MD5 hash value?). But as far as I know two inputs should have the same length ...
1
vote
1answer
180 views

SHA-256 “almost unique”?

I have seen numerous references on the internet of people describing SHA-256 as generating an "almost unique" hash. Exhibit A. there are more. Is there some mathematical basis to the almost ...
0
votes
3answers
99 views

Perfect hash function

Is a perfect hash function always bijective ? In Wiki "In mathematical terms, it is a total injective function" but it does not mean, that it is bijective.
0
votes
2answers
72 views

hash functions preimage and second collision resistance [duplicate]

A hash function H is secure in terms of pre-image resis-tance. Does this imply that H has second pre-image (aka weak collision) resistance?
3
votes
0answers
62 views

Combining md5 collisions to create more collisions

Given X1 and X2 such that md5(X1) = md5(X2) and Y1 and Y2 such that md5(Y1) = md5(Y2), and knowing the following property of md5: if md5(a) = md5(b), md5(a|s) = md5(b|s) is there a way to find ...
0
votes
2answers
156 views

If I compute the SHA-1 of all possible 40 digits hexadecimal strings, will I get all possible sha1 hashes? [duplicate]

Wikipedia says sha1 produces a 160-bit (20-byte) hash value. So if I compute the SHA-1 of all possible SHA-1 values, which as far as I understand is at current time impossible both to calculate and ...
2
votes
0answers
137 views

Bobcat hash, trying to find a 48-bit hash collision for x

I am trying to find a collision with the Bobcat hash of the 48-bit hash. I am a beginner coder so please point out any flaws in my modification of the bobcat program. It does find a truncated 12-bit ...
7
votes
3answers
282 views

What was the first MD5 collision ever constructed?

We all know that MD5's collision resistance is severly broken. But when thinking of "random" strings with great cryptographic importance I've come up with NIST's curve seeds and MD5 collisions. But ...
2
votes
0answers
90 views

Is there a way to slow down collision attacks using iteration?

The simple way to iterate a hash function $H(H(m))$ only makes brute force preimage finding slower, but leaves collision attacks as fast since a collision in the inner hash function is a collision in ...
0
votes
1answer
142 views

1024 RSA Hash Signature attack. Forge a valid signature

I have an RSA signature of 1024 bit where i know the following: Public modulus N Public exponent (0x03) Cypher message Summary: An MD5 hash is calculated from a collection of byte and is used as ...
5
votes
1answer
250 views

Can iterated hashing be used to mitigate collision and preimage weaknesses?

How much security does double hashing add regarding collisions and preimages? Is it helpful to iterate a hash function even more times than two? For example, can MD5 be fixed (in practice) by ...
2
votes
1answer
143 views

Why the $IV$ used in Merkle-Damgard has to be fixed to a specific value?

I just can't figure out why on earth the $IV$ in Merkle-Damgard has to be fixed (that's what the Katz-Lindell book says)? Because even if you choose it randomly from say $\{{0,1}\}^n$ then the ...
0
votes
0answers
115 views

For each of the following modifications to the Merkle-Damgard transform, determine whether the result is collision resistant or not

$(a)$ Modify the construction so that the input length is not included at all (i.e., output $z_B$ and not $z_{B+1}=h^s(z_B||L)$). $(b)$ Modify the construction so that instead of outputting ...
1
vote
2answers
183 views

How to formally prove that a given hash construction is collision resistant or not?

Is there a precise procedure or strategy to follow in order to prove in a formal way the (not) collision-resistance of a certain given hash construction? I.e. let $H_1$ and $H_2$ be two hash ...
0
votes
0answers
65 views

How can I calculate the probability of collisions of a hashing algorithm?

I'm pulling a “Dave” and I'm designing my own hashing algorithm. Not that I intend to use it, I'm not certifiable or anything, I just want the challenge of creating something. I'm not going to get ...
4
votes
1answer
278 views

Formula for the number of expected collisions

Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision. Say instead that ...
5
votes
1answer
140 views

Keys in HMAC and NMAC

I'm quite new to this topic and have several questions concerning HMAC and NMAC: Why does NMAC need two keys? How can it be attacked if we just used some sort of initialization vector instead of the ...
1
vote
2answers
78 views

Collision probability of MD5 over different attacks

I am researching the collision probability of MD5 and various attacks against it. Can someone help me how to learn the least probability that there will be a collision in a specific attack on MD5? ...
0
votes
1answer
41 views

What is the run-time on finding collisions with MACs,…?

I've recently read the claim that finding collisions on block cipher may be not a difficult task, if an attacker can control the key and the message. So, given a pseudo-random function $f:\{0,1\}^m ...
7
votes
0answers
209 views

Are there any practical attacks that create a printable chosen prefix MD5 collision?

I would like to create two ASCII text messages with the same MD5. Is this possible? If not, is there a similar but less strict attack that could work? Or to rephrase my last question: what are the ...
2
votes
1answer
86 views

Ideas for non duplicate cryptographically secure numbers

My Boss asked me this today. I am not a math major. He needs to generate 50 billion non-sequential non-duplicate (no collisions) cryptographically secure random numbers. I work in GO. Any ideas?
3
votes
3answers
244 views

Establishing encryption key using shared secret

I need to establish some security on a network of 8 bit microcontrollers. very limited RAM, CPU and packet sizes. I have zeroed in on a shared secret based scheme. Setting up shared secret is out of ...
4
votes
2answers
4k views

Why is HMAC-SHA1 still considered secure?

This Q & A http://security.stackexchange.com/questions/33123/hotp-with-as-hmac-hashing-algoritme-a-hash-from-the-sha-2-family says that the security of HMAC-SHA1 does not depend on resistance to ...
2
votes
0answers
44 views

Determine safety of exercise hash functions

There have been several attacks against hash functions such as $h_{sha1}$ and $h_{md5}$. Professor A suggests a new function $h_{666}$ with an output length of 666 bits. Professor B suggests ...
10
votes
3answers
301 views

Collision or second preimage for the ChaCha core?

Daniel J. Bernstein's ChaCha core is an evolution of the Salsa20 core. Both are functions over the set of 512-bit bitstrings, partitioned as sixteen 32-bit words. Can we exhibit collisions, or ...
5
votes
1answer
1k views

What are the differences between collision attack and birthday attack?

From my understanding both types of attack, collision and birthday, are based on the principle of two randomly/pseudo-randomly chosen plaintext to hash to the same value. I don't want to launch any ...
0
votes
1answer
104 views

What's wrong with an iterative (with counter) hashed salted KDF?

It seems like the brain-dead simplest KDF would have a key-stretching structure that is not substantially different from $\text{hash}(S | P | S | P |\dots|S|P)$, where $S$ is a salt and $P$ is a ...
0
votes
1answer
132 views

Has a collision ever been found for SHA-1/2/3 when truncated to 128 bits?

I'm aware that MD5 is broken, and collisions have been found for it. I'm interested in other hashes (SHA-1, SHA-2, SHA-3) when truncated to the same digest size, i.e. 128 bits. The time complexity of ...
0
votes
3answers
118 views

Is the hash function defined in this exercise collision-resistant?

I have this problem: "Let ${\rm Enc}_k(m)$ a safe block encryption system. We define a hash function $H(m)$ as follows: $m$ will be concatenated with $0$ until $|m|$ is a multiple of ...
0
votes
1answer
171 views

Which of the following hash functions is collision resistant?

Let $H: M \to T\ $ be a collision resistant hash function. Which of the following is collision resistant: $ 1.H'(m) = H(m \big\| m)$ $2.H'(m) = H(m) \big\| H(0)$ $3.H'(m) = H(m) \oplus H(m)$ ...
7
votes
2answers
557 views

Is HMAC-MD5 still secure for commitment or other common uses?

MD5 collisions have been out for some time. In spite of this, HMAC-MD5 is still secure for authenticating data1. This illustrates a strength of the HMAC construction, it does not require that the hash ...
0
votes
1answer
58 views

Why rogued certificate from hash collision is harmful

I cannot understand why rogued certificate is thought harmful though It can be used to impersonate some website. The attacker can craft a rogued certificate with different identities and public key ...
1
vote
1answer
106 views

Will there always be 256 collisions for the output of the MD5 hashsum function for 17-byte inputs?

By my math, if you are inputting all possible 17 byte values, and the output is 16 bytes long, then there must always be 256 possible inputs that will result in each output hashsum. However, looking ...
2
votes
1answer
2k views

Probability of SHA256 Collisions for Certain Amount of Hashed Values

I wonder if you can help me figure out that question: Is there a known probability function f: N -> [0,1], that computes the probability of a sha256 collision for a certain amount of values to be ...
2
votes
3answers
190 views

Cycles in SHA256

In the recommendations, it seems cycles is used usually as in "CPU Cycles", but, that's not what I mean here. What I mean, is this: Let's say I start with a particular 256 bit value. Call this v. I ...
2
votes
1answer
277 views

Concatenation of two strong hashes may have striking weakness

For any hash functions $H_0$ and $H_1$, it is easily proved that their concatenation $H_0\|H_1$, defined by $(H_0\|H_1)(X)=H_0(X)\|H_1(X)$, is at least as resistant as the strongest of $H_0$ and $H_1$ ...
3
votes
2answers
113 views

What practical uses can random hash collisions be put to?

Using magic, I've built a machine that instantly generates hash collisions. To try it out, I set the dial to SHA256 and typed in "e7cf3ef4f17c3999a94f2c6f612e8a888e5b1026878e4e19398b23bd38ec221a". I ...
1
vote
1answer
206 views

Problem with testing MD5 collisions

I am trying to test MD5 collisions presented in “Collisions for Hash Functions MD4, MD5, HAVA” (PDF) by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu; 2004. I wrote a PHP script to test it, but ...
0
votes
1answer
186 views

Reducing size of hash function

If I have some data I hash with SHA256 as hash=SHA256(data) and then copy only the first 8 bytes of the hash instead of the whole 32 bytes. How easy is it to find a ...
2
votes
1answer
102 views

Hash “Preimage by product” resistance

Let H() be a hash function that achieves collision resistance as well as first and second preimage resistance. Let's equip the output set of H of a multiplicative group structure, more precisely a ...
1
vote
1answer
104 views

Hashing - Digital Signing and Trivial Stretching

Two very basic questions: 1. Digital Signing Why is it not possible to just simply replace the hash value from the request? Examples: ...
4
votes
1answer
239 views

How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?

Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that $$h(a)\oplus h(b)=h(c) \text?$$
0
votes
1answer
172 views

How much work is required to detect multiple collisions for a hash function?

Assume an ideal hash function of output size n bits, detecting one collision requires approximately 2^(n/2) evaluations of the ...
7
votes
1answer
455 views

Why is EdDSA collision-resilient with SHA-512?

In the Bernstein et al. paper about EdDSA, the authors claim EdDSA is resilient against collisions (i.e. it can still be secure even if the hash function used isn't collision-resistant), drawing on a ...
1
vote
2answers
245 views

Are there cryptographic hash functions which do not have any collisions?

I've been studying digital signatures and hash functions recently, and I was wondering: Do hash functions exist which will never produce collisions?
3
votes
2answers
137 views

Security concern about reducing hash value using modulo operation

As stated in the title, what I am looking for is information about a "technique" that I would like to use in some of my algorithms. Sometimes I need to map a hash function's result into a range of ...
5
votes
1answer
3k views

Second pre-image resistance vs Collision resistance

From Wikipedia: Second pre-image resistance Given an input $m_1$ it should be difficult to find another input $m_2$ such that $m_1$ ≠ $m_2$ and $\operatorname{hash}(m_1) = ...
1
vote
1answer
155 views

N way collision of hashes

For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = ...