Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [collision-resistance]

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

2
votes
0answers
47 views

Application of High-level Mathematics to Hashing [on hold]

Sorry if this post is a tad unconventional(it's also a reddit repost), but I was recently commissioned by a teacher to write a paper on the application of high-level math to a topic of our choice, and,...
0
votes
0answers
17 views

Summary of Klima's Tunneling Method of Finding Collisions

I was wondering if anyone could link to any summaries of Vlastimil Klima's method of locating hash collisions. I understood around 70% of his paper on the topic, but would like to supplement it with ...
2
votes
0answers
40 views

Impossible to construct collision resistant hash function from one way function

[Simon 98] showed that it is impossible to construct collision resistant hash function from one way functions in a black-box way. I read the paper but barely understood it. Is there any source, where ...
1
vote
2answers
168 views

What is a simple 8-bit cryptographic hash function that I can use in a quantum simulation of Grover's algorithm?

I'm taking a quantum computing course in which, for our final project, we must create a proof-of-concept implementation of Grover Search for finding hash collisions up to a difficulty (similar to ...
6
votes
2answers
629 views

Compression function is not collision resistant but Merkle-Damgard is collision resistant

Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?
0
votes
1answer
47 views

What does the minimal number of round of “nr” use Keccak to avoid “collision attack”?

What does the minimal number of round of "nr" use Keccak to avoid collision attack? $$nr = 12+2L$$
2
votes
1answer
67 views

Formal definition of collision resistance for hash function

In my cryptography class, the professor said that collision resistance for a fixed hash function is not a "precise" definition. The reason is since a fixed hash function is a single instance of a ...
2
votes
2answers
263 views

How to prove that finding a cycle in a cryptographic hash function is hard?

I want to show that finding cycles in a cryptographic hash function is hard. My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial ...
1
vote
0answers
94 views

Show that the CBC-MAC construction applied to a PRP is not collision resistant

I'm trying answer the following question. Yes, it is a homework question, so I'm not asking for the answer directly but would like to get some pointers on how to solve it. So far I have spent several ...
1
vote
1answer
74 views

Is a hashing algorithm considered broken if a collision happens under $2^{n/2}$?

If for example we would find a hash collision for SHA256 with $h(x) = h(x')$ for $x \ne x'$ and $x, \space x' < 128$ bit (meaning both $x$ and $x'$ are smaller than 128 bit), would SHA256 be ...
1
vote
2answers
62 views

Integrity check of a binary firmware file with hash function

I need to provide a mechanism that it is possible to verify the integrity of a firmware image flashed on an embedded system. The procedure should be, that if someone has doubt on the firmware’s ...
4
votes
1answer
480 views

Is there a feasible preimage attack for any hash function (no matter how deprecated) today?

Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack? All hashes that are nowadays considered 'broken' (...
-1
votes
1answer
47 views

Add string to create specific MD5?

I have a file that include a long string , I can calc the md5 of this file . Is there any way to know which string I need to add for this file so the md5 of this file will be specific md5 that I want?...
2
votes
1answer
63 views

What is the minimum message length to obtain the full potential of a hash?

Suppose I want to commit to a uniformly picked nonce of fixed length $n$ bits without revealing the nonce, so I use a secure hash function $H$ mapping messages to digests of length $d$ bits. Suppose $...
17
votes
2answers
4k views

What makes SHA256 secure?

For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem. What makes SHA256 and similar hash functions, of the same family, ...
1
vote
1answer
27 views

Number of preimages of hash function from bounded domain

Suppose we have an "ideal" cryptographic hash function $H: \{0,1\}^{n+k}\to \{0,1\}^{n}$ and a given bitstring $b\in \{0,1\}^{n}$, Can we estimate how many preimages $H^{-1}(b)$ there are? With ...
7
votes
1answer
117 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 ...
5
votes
1answer
113 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 ...
3
votes
1answer
116 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
259 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 ...
0
votes
1answer
245 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
96 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
61 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
64 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
82 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
59 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
3k 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
50 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
110 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
119 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 ...
5
votes
1answer
948 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
58 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 ...
4
votes
1answer
114 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
58 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
144 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 ...
3
votes
1answer
395 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
99 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 ...
3
votes
2answers
148 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, $...
-1
votes
1answer
112 views

finding encoding based collision

For example, If I enter as a sample "hello world" in English, how hashing protocol generates a hash of it? is in the first step, change it to ASCII or Unicode or Binary? What if I find a word in other ...
19
votes
5answers
2k 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
68 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
110 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 ...
1
vote
1answer
156 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
85 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 ...
2
votes
5answers
230 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
121 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 ...
27
votes
3answers
3k 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
7k 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
56 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 ...
0
votes
2answers
300 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 ...