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

Filter by
Sorted by
Tagged with
7
votes
1answer
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 ...
6
votes
2answers
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 ...
4
votes
1answer
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 ...
-4
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
601 views

Is the hash function $h(x\|y) = AES_x( y)$ collision resistant?

If $x$ and $y$ are both 128-bit strings would the function $h(x||y) = AES_x(y)$, where $x\|y$ means concatenation, be considered collision resistant ? Is there an easy way to find $(x_1, y_1)$ and $(...
1
vote
0answers
79 views

Extendable hash collision resistance of multiplication

I have a hash function $HashSet(A) = H(a_1) *\cdots * H(a_n)$, where $A = \{a_1,\ldots,a_n\}$ and $H$ is a hash function which generates values of $b$ bits (and $H$ has no collision attack that ...
17
votes
1answer
4k views

What are the consequences of removing a single byte from a sha256 hash?

I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash. Sha256 would meet this ...
0
votes
1answer
280 views

Python hash code returns wrong result? [closed]

For a school project, I'm trying to demonstrate a hash collision using Python. This is the little piece of code that I'm trying to use (based on this answer): ...
0
votes
1answer
562 views

Show that if a fixed key MAC is not collision resistant then the MAC function is not computation resistant for every key K

I'm really having some trouble with this one. Let $H$ be a MAC function. For every key $K$ we can create an unkeyed hash function (i.e.an MDC) by using $H$ to hash messages with the fixed key $K$. ...
1
vote
1answer
425 views

How to find a collision with a given prefix and a known key in an AES ECB symmetric block cipher?

I should be able to find a collision for a vulnerable hash function which uses AES ECB given a prefix, but I am unable to find a reasonable solution (besides brute-force attack). The hash function is ...
8
votes
1answer
3k views

What is the probability to produce a collision under two different hash functions?

Given 2 (weak) hash functions, namely MD5 and SHA1 The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two ...
2
votes
2answers
98 views

Difficulty of finding collisions for two different CRHF

Suppose that $\mathcal{H}$ is a family of collision resistant hash functions. Given $h$, which was chosen uniformly at random from $\mathcal{H}$, it is infeasible for a polynomial-time adversary to ...
53
votes
11answers
19k views

How do hashes really ensure uniqueness?

This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup. So hashes are said ...
4
votes
1answer
288 views

How to derive a hash function from another hash function? [duplicate]

Problem: Hash functions derived from another hash function (4 marks) Suppose that $H:\{0,1\}^* \rightarrow \{0,1\}^n$ is a collision resistant hash function. Define a new hash function by $G:\{0,1\}^* ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
2answers
779 views

AES-128 as compression function in Merkle-Damgard construction

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, $...
18
votes
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 ...
4
votes
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 ...
1
vote
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 ...
2
votes
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)$ ...
5
votes
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 ...
3
votes
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 ...
4
votes
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 ...
36
votes
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 ...
17
votes
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 ...
2
votes
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 ...
-1
votes
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 ...
3
votes
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, ...
6
votes
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$ ...
3
votes
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.). ...
6
votes
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 ...
10
votes
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 ...
0
votes
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 ...
2
votes
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 ...
2
votes
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,...
-1
votes
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 ...
4
votes
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)\...
4
votes
2answers
1k views

Rolling your own crypto

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 ...
1
vote
0answers
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 ...
0
votes
1answer
172 views

Taking $n-1$ bits from hash function will also be hash function?

If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(...
2
votes
2answers
774 views

Attack MD5 with partial information?

If I generate an MD5 hash from 2 pieces of information – i.e. by concatenating two strings – how easy is it to guess what that hash is, assuming an attacker has knowledge of only 1 piece of those info?...
5
votes
1answer
226 views

What is the collision resistance of a 2048-bit hash based on SHA-3?

Let $M$ denote the message. Let $B_i$ denote eight different bitstrings (chosen arbitrarily or randomly) such that $$0 \le \text{length}(B_i) \le 12345678.$$ Consider the following function (it ...
5
votes
1answer
960 views

Is there are a metric based on collisions to compare bad hash functions?

Bad hash functions are not so perfect as in the "general collision probability" hypothesis... And a general concept of "collision resistence" not need the constraint of independence between the ...

1 2 3
4
5
12