People who code: we want your input. Take the Survey

# Questions tagged [collision-resistance]

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

581 questions
Filter by
Sorted by
Tagged with
405 views

### SNARK-friendly one-way compression functions

I'm looking for a one-way compression function that is secure and efficient within a zk-SNARK circuit. The motivation behind this comes from these considerations: SHA256-compression is highly ...
556 views

### Partial collisions of hashes, why is this important?

There's a lot of work finding "partial collisions" in hashes, and "Parallel Collision Search with Cryptanalytic Applications" seems to be the go-to paper for this work. I'm trying to understand why ...
642 views

### Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant?

I'm trying to solve the following problem: Given two CRHF $H_1:2^{4n}\to2^{2n}$, $H_2:2^{2n}\to 2^n$, construct the following hash function $H^{*}=H_2(H_1(x))$ compressing from $2^{4n}\to 2^n$. We ...
444 views

### AES_256_ENCRYPT_CTR(key, sha-1(plainText)+plainText) VS AES-GCM, which is more secure? [duplicate]

What if we encrypt sha-1 hash of the plain text, along with the plain text using AES-256 in CTR mode? How much future proof the above method would be in comparison to AES-GCM or any other method ...
6k views

### Hash Collision Probabilities

Please give help! how can I calculate the probability of collision? I need a mathematical equation for my studying. Assume, I am using SHA256 to hash 100-bits. Thus: SHA256 {100} = 256-bits (hash ...
291 views

### On a lower bound for the birthday problem

I'm now familiar with a lower bound for the birthday problem as exposed in the theorem A.16 of Katz and Lindell book (alternatively see this webpage). If one denotes by $C(q,N)$ the probability of ...
145 views

### Is there an information theoretic equivalent of a trap door collision free function?

Warning: Possibly ill-posed question. I'm using the following definition from a recent paper available here. I believe their terminology is slightly different but reproduce my understanding of it ...
108 views

### What is the smallest last value of sequence of integers from 1, where there is a collision in md5? [duplicate]

Question is just out of interest. If we take md5 hash from all integers from 1 to n, what is the first n, where its md5 collides with some previous md5? Has anyone ever calculated and proved the ...
601 views

77 views

### Why do m and m' both hash to H2?

I'm trying to understand the following text: I'm having trouble understanding why $m$ and $m'$ both hash to $H_2$. I tried doing truth tables for $m_1'$ and $m_2'$ given the equations but I don't ...
331 views

### What does Keccak being “efficiently invertible” mean?

Reading through Wikipedia, I saw this: It has been shown that the Merkle–Damgård construction, as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant, but for the sponge ...
2k views

### MD5 - Chosen Prefix Collision Attack

Given 2 messages $m_1$ and $m_2$, in a chosen prefix attack, we want to find $s_1$ and $s_2$ such that: $\text{MD5}(m_1 || s_1) = \text{MD5}(m_2 || s_2)$ Are $s_1$ and $s_2$ found by brute force ...
295 views

### Is there an $n$-bit hash function such that $n$ is equal to the length of input and the collision resistance is close/equal to $2^{n/2}$?

Let $B$ denote a non-empty bitstring of arbitrary length. Then let $n$ denote the length of $B$. The question: does there exist a cryptographic hash function $H$ that outputs a hash $h$ of $B$ such ...
779 views

Using a compression function $f : A × A → A$. A basic version given by: $W_0 = IV$ $W_1 = f(W_0, m_1)$ $W_2 = f(W_1, m_2)$ ... $W_n = f(W_{n-1}, m_n)$ $W_n$ is the output of the hash function, $... 5answers 3k views ### How many hex digits do I need to compare when manually checking hash functions? I sometimes run sha256sum on large files after transferring them from one place to another, and will just skim the hash output to verify it's correct. But, I usually just look at the first/last 5 or 6 ... 2answers 177 views ### Feasible to find two sets with the same RSA accumulator value if a prime representative hash function is used? Consider the RSA accumulator scheme with random oracle as proposed by Barić and Pfitzmann, with the random oracle replaced by a secure hash function$H$as follows. For a set$S$, the accumulator ... 1answer 151 views ### repeatedly hashing result and using reverse sequence as RNG secure? I want to have a source of randomness for which: no one but me can predict the next number in the sequence. I know the entire sequence in advance, but I have no way of manipulating it once the first ... 1answer 472 views ### Hashing based on the discrete logarithm problem At a first look, one could use the elliptic curve discrete logarithm problem to grant for the onewayness of$H(x)=x*G$(where$G$is the generator point of the cyclic subgroup). Additionally,$H(x)$... 2answers 196 views ### Can RFC 5649 be used to wrap multiple keys with the same KEK? I am unable to convince myself that RFC5649 is secure when storing multiple keys with the same KEK. My point is: RFC5649 uses AES-ECB, therefore the usual weakness of this method applies, namely an ... 5answers 351 views ### What is the mathematical property stating that it is hard to find a collision in the AES algorithm? Finding a collision in the AES algorithm is (apparently) hard. Why ? What is the mathematical property stating that there is a negligible probability to find a collision by taking two random ... 1answer 144 views ### Cryptanalysis of MD4 (Wang et al) — how did the authors come up with the collision differential? Edit: ok, after I re-read the paper a couple of times it is clear that Table 6 is easily derived from Table 5, which describes the collision differential. So the real question is: how did the ... 3answers 7k views ### Does “Shattered” actually show SHA-1-signed certificates are “unsafe”? Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of ... 3answers 11k views ### After Google's collision attack, is RSA-SHA1 signature still safe? Google succeeded to get a collision in SHA-1 last year in an attack called shattered. Does this fact make certificates based RSA-SHA1 Signature risky for creating fraud certificates? If RSA-SHA1 ... 1answer 97 views ### The Collision Differential for MD4 - a question on notation (Wang, et al) In the paper "Cryptanalysis of the Hash Functions MD4 and RIPEMD" the authors introduce the following notation (paragraph 4.1):$\Delta$$H_0 = 0 \xrightarrow{(M_,M')} \Delta$$H$= 0 What exactly ... 2answers 546 views ### MD5 hash functions to prove integrity of a download It doesn't take a lot of time on the crypto StackExchange to realise the sentiment around MD5 hash functions is poor. My questions are: If it's such a bad idea to make use of MD5 hash functions why ... 4answers 714 views ### Find some hash function with deliberate collisions I guess this should be well known (or trivially desperate), but I couldn't find any reference. I have a small number (say$k=15$) of messages$m_i$,$i=1\cdots k$(they are fixed length and short, ... 2answers 627 views ### Finding k collisions on hash function Let$n$be the size of the image-space of a hash function$H$. It is known that you can find a collision on$H$in$O(\sqrt{n})$time (by birthday paradox). How can I show that, in order to find$k$... 2answers 434 views ### Is it possible to generate an infinite number of collisions given an infinite amount of strings? Let us assume that we have a string$w$such that it belongs the set$C$, where every member of$C$is not null, and contains every string of characters that can be permuted (numbers, letters etc.). ... 1answer 236 views ### What are the implications of quantum collision search algorithms like Ambainis for collision-resistant hash functions? I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet): Post-quantum ... 2answers 3k views ### How many trials does it take to break HMAC-MD5? I know that you can find collision in MD5 with 2^64 trials using Birthday paradox. Now everyone is saying that HMAC-MD5 is significantly more secure. How can I ... 2answers 72 views ### Technical term for hash value being uncorrelated to input message? Is there a technical term for the desirable property of hash functions. That a small change to the input message will produce a massive unpredictable and seemingly uncorrelated change to the output ... 2answers 568 views ### collisions on hash functions Why do we say that collision-resistance is a "harder" property than second pre-image for hash functions whereas if you have an attack on the second pre-image then you find a collision ? Moreover, a ... 1answer 1k views ### Security of XORing hashes vs concatenating On this question https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes a couple of the answers say that xoring is a bad/insecure choice for combining hashes. However,... 2answers 2k views ### (strong) collision resistance Example I'm studying Cryptography & Network Security. It has the following example for collision resistance: "Suppose Bob writes an IOU message, sends it to Alice, and she signs it. Bob finds two ... 1answer 123 views ### For a random permutation$P$, what's the probability of the following event? For a random permutation$P$and$q$distinct inputs$x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among$\{P(x_1)\oplus x_1,\ldots,P(x_q)\...
1k views

I know this is usually frowned upon, but supposing you were to roll your own encryption cipher (completely on your own or with a small group of friends, with no peer review possible), what could you ...
49 views

### Hash Function SHA-3 [duplicate]

I would like to discuss the minimum input of hash function to consider strong (e.g Shack128 (SHA-3)). I have a mechanism based on SHA-3, but the input is just 40-bit, some friends told me 40-bit input ...