Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
128 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 Z1, ...
3
votes
0answers
92 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
3k 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
1k 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?
1
vote
1answer
164 views

does SHA* collide more or less than a random function?

There were several questions here regarding how surjective SHA-1/2 is, how many values don't have a pre-image from a fixed size input. I and others answered when modelling the relevant hash function ...
2
votes
1answer
207 views

Does Keccak have an eTCR mode?

On page 7 of NIST's views on SHA-3's security requirements and Evaluation of attacks, I see that, at least at this point, NIST planned on offering SHA-3 having eTCR security (defined on page 3): ...
0
votes
1answer
85 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$$
6
votes
1answer
244 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 ...
0
votes
1answer
254 views

Why is H(k || m || k) secure against birthday attack?

I don't know if my opinion is correct. I think that H(k || m || k) (I mean using Merkle and Damgard algorithm where k is a secret key shared by two parties and m is the message sent) is a good keyed ...
-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
150 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 ...
2
votes
1answer
385 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 ...
9
votes
2answers
467 views

How should I incrementally sign a large set of documents?

Say I have a large set (i.e. unordered collection of unique elements) of documents, each of which is around 4KB in size. I'd like to sign that set with a private key so that anyone can verify the ...
6
votes
1answer
847 views

Is there a way one can combine two correlated hash outputs to maximize the collision resistance?

While practically diving into collision resistance, I am trying to first write a non-cryptographic hash (to learn from it) which is limited to arithmetic operations on 32-bit integers only. It ...
5
votes
1answer
980 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 ...
2
votes
1answer
327 views

Merkle-like hash tree that mirrors existing tree structure

I'm wondering about the security of a hash-tree structure that mirrors the structure of another tree. In an ordinary Merkle tree the block hashes form the leaves of the tree, and all internal nodes ...
7
votes
2answers
2k 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
1answer
204 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
799 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 ...
105
votes
7answers
173k views

Are there two known strings which have the same MD5 hash value?

Is there an example of two known strings which have the same MD5 hash value (representing a so-called "MD5 collision")?
-1
votes
1answer
63 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
414 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 $...
2
votes
1answer
54 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
421 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 ...
4
votes
1answer
293 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\}^* ...
-4
votes
2answers
452 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
606 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
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 ...
31
votes
3answers
5k views

Are common cryptographic hashes bijective when hashing a single block of the same size as the output?

It's been said that CRC-64 is bijective for a 64-bit block. It the corresponding statement true for typical cryptographic hashes, like MD5, SHA-1, SHA-2 or SHA-3? For example, would SHA-512 be ...
1
vote
2answers
294 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 ...
0
votes
1answer
112 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 ...
5
votes
1answer
4k views

Pre-image attack on MD5 hash

I read somewhere MD5 is broken in terms of collision, but I am wondering if it is broken in terms of pre-image resistance? Given a hash of Md5, is it possible to find the original message of it? If ...
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 ...
58
votes
2answers
21k views

Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1?

I am from a web development background (I don't know an awful lot about cryptography or how the algorithms themselves work), so I am asking this question in simple terms. Consider a hash of the word '...
0
votes
1answer
294 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): ...
-1
votes
1answer
1k views

MD5 proving collision for the famous hexadecimal blocks

Below shows the hexadecimal pair which collides in MD5 (http://www.mscs.dal.ca/~selinger/md5collision/): d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 ...
0
votes
1answer
569 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
211 views

Bitmasks or seed along with public key in WOTS+ post-quantum signatures

The state of the art hash-based post-quantum signature schemes, like Sphincs and XMSS, are using variations of WOTS (Winternitz OTS), like WOTS+, that require extra random bitmasks along with the ...
1
vote
1answer
436 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 ...
4
votes
2answers
802 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, $...
11
votes
3answers
1k views

Can there be two hash functions without common collisions?

Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision? I mean, like provable in way that someone who took one cryptography class in ...
2
votes
2answers
99 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 ...
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 ...
4
votes
2answers
2k views

Breaking effort on both Weak and Strong collision resistance hash values

I know the fact that the effort of brute force attack to break weak collision resistance hash value takes $2^n$ while in the strong collision resistance takes $2^{n/2}$. Can someone explain why strong ...
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
341 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 ...
0
votes
1answer
307 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 ...
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 ...
1
vote
1answer
152 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
479 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)$ ...

1
3 4
5
6 7
12