Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
729
questions
6
votes
2
answers
1k
views
Purpose of hashing last block in Merkle-Damgård?
Is hashing the last block in the Merkle-Damgård necessary in preventing collisions? i.e. What if I just outputted $z_B || L$, where $z_i$ is the hash of the last block of the message, L is the length ...
- 17.9k
0
votes
1
answer
108
views
Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant?
I recently got a question that I’ld like to share here, since answers might be useful (or at least interesting) for people diving into Merkle-Damgård hash constructions for the first time.
We know ...
- 27.8k
0
votes
1
answer
519
views
Is triple-CRC-32 a bad (or not) idea for generating a uniform distribution hash? [closed]
I have an input of 288 bits (comprising 4 × 32-bit and 10 × 16-bit integers). I need to hash this to 96 bits with as few collisions as possible.
I'm aware that CRC is a bijective hash, thus ensuring ...
- 4,913
3
votes
3
answers
889
views
What do we gain from hashing the length in Merkle–Damgård?
Assuming our fixed compression function $h$ works for inputs of length $i(n)$ and output strings of length $o(n)$, if $2o(n) < i(n)$, why do we need to calculate $h(z_B||L)$ where L is the input's ...
- 17.9k
5
votes
3
answers
844
views
Can I use M1 straight away and get rid of IV in Merkle–Damgård?
In Merkle–Damgård is there any reason why we use a fixed $IV$ at the beginning? Can we use the first block ($M_1$) right away instead of $IV$ and feed it through the compression function with $M_2$.
1
vote
3
answers
584
views
Would this hash functionality fall under pre-image resistance or collision resistance?
I understand that there are three main security requirements for hash functions, pre-image resistance, second pre-image resistance and collision resistance.
I need to write about a hash function that ...
- 92.6k
1
vote
2
answers
148
views
Merkle–Damgård padded block concatenated outside the compression function hash?
I learned that the output of hash function from Merkle Damgard is
H(x) = ZB+1 = h(ZB || L) = h(ZB - 1 || XB || L) where XB = block of padded x and L = XB+1
and ...
- 17.9k
3
votes
1
answer
1k
views
Winternitz One time signature security
There are two versions of Winternitz-One time signature scheme, $W-OTS$ and $W-OTS^+$
Security of both is as following
$W-OTS$ is strongly unforgeable under chosen message attacks if $F$ is a ...
- 147k
1
vote
1
answer
120
views
Minimum difference collision metric
Take a hash function $H$.
There will be pairs of messages of the same length $M,M'$ for which $M\ne M',H(M)=H(M')$.
Let $P(x)$ be a function counts the number of $1$s in $x$. $d=P(M\oplus M')$, or ...
- 147k
4
votes
2
answers
994
views
Collision resistance in a hash function
I'm confused about whether the following hash function is collision resistant.
$x \sqsubseteq y $ denotes that x is equal to y or x precedes y.
$ H:\{0, 1\}^* \rightarrow \{0, 1\}^n$
If $x \...
- 5,188
1
vote
1
answer
206
views
Figuring out seed/internal state from HMAC-MD5 output
Here is the scenario i'm imagining, I use the python random library to generate x-bit key that I use to generate a HMAC-MD5 output. Every HMAC-MD5 has uses a different random number as its key.
My ...
- 48.4k
1
vote
1
answer
2k
views
Getting the key used for HMAC given the hash and the plaintext?
I'm working on a little exercise to understand the drawbacks of poor library choices and I've been presented with the following scenario.
The HMAC function in python is being used (md5). I know the ...
- 147k
7
votes
1
answer
2k
views
Collision Resistant Hashing from One-Way Functions?
In general, can we construct a collision resistant hash function from a one-way function?
- 5,188
7
votes
1
answer
3k
views
What is the best and fastest algorithm to generate a hash collision?
I want to find any two strings with same hash in any hash algorithm ( at least try to find depends on its collision resistance). What kind of algorithm should I follow? Should I constantly produce two ...
- 46k
3
votes
1
answer
3k
views
Testing hash functions for collision resistance
I was hoping to implement a software that allows testing a user-defined hash function for cryptographic properties (Meant to pique interest in cryptographic hash function for a school showcase), as ...
- 17.9k
-1
votes
1
answer
195
views
How many hash functions must Bob compute to find a solution?
Alice proposes the following puzzle to be completed.
Let m be the body of the email message,
let a be the recipient’s email address,
let H( )be the hash function SHA3-256, ...
- 3,842
9
votes
1
answer
3k
views
I need a 64-bit cryptographic hash for 96 bits of data
I have a situation in which I need to combine a 32-bit datum, G, and a 64-bit datum, I, to produce a 64-bit datum. No two ...
- 141k
2
votes
1
answer
507
views
Security of a given hash function
We have a message denoted $M$. Let us suppose that we have a collision-resistant hash function $h_0$ with output length $n$. We then consider two other independent (different) hash functions $h_1$ and ...
- 46k
0
votes
1
answer
1k
views
How much work is required to find multiple collisions for a hash function?
Assume an ideal hash function of output size n bits, finding one collision requires approximately 2^(n/2) evaluations of the ...
- 38.6k
2
votes
1
answer
133
views
How much would an unexpected hash collision undermine the security of a hash function?
Say some random person manages to, by sheer luck, find 2 messages with the same hash. There is no systematic way of creating more such pairs of messages that produce collisions.
How much would this ...
- 11.8k
7
votes
2
answers
811
views
Does a practical collision attack on a cryptographic hash function also mean it fails “indistinguishable from random data”?
It is knowns that SHA-1 has been broken in practice using collision attacks. Related to SHA-1 this mainly had a negative impact on the security of
Digital Certificate signatures
Email PGP/GPG ...
- 14.5k
15
votes
2
answers
3k
views
Mixing algorithms for password hashing good or bad?
So I've come across the following algorithm for hashing passwords
...
- 189
4
votes
3
answers
2k
views
For any hash value, is there an infinite number of inputs that hash to it?
Bruce Schneier writes (back in 2005) in a post on cryptanalysis of SHA-1:
SHA-1 produces a 160-bit hash. That is, every message hashes down
to a 160-bit number. Given that there are an ...
CommunityBot
- 1
8
votes
1
answer
1k
views
Collision on self made hashing function [closed]
I am currently designing a hashing function based on a mathematical formular to calculate the size of an arc on a circle with the radius 1.
From that I made a small hashing function which works kind ...
- 147k
4
votes
1
answer
4k
views
Understanding calculation of collisions in hash-functions
I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is:
How many collisions would you expect to find ...
CommunityBot
- 1
8
votes
1
answer
1k
views
Free Start Collision In SHA-3
Given that the five sub-functions that comprise SHA-3 are reversible an individual can produce specific outputs of their choosing. The following is to my knowledge an example of a free start collision ...
- 1
5
votes
2
answers
2k
views
Impact of the hash algorithm on a PRNG
Pseudorandom number generators often use hash functions for the generation. Some applications allow the users to choose this hash function, for example OpenVPN.
From the OpenVPN manual:
--prng alg ...
- 141k
0
votes
1
answer
571
views
In search of platform independent 128-bit hash function [closed]
We are currently using murmur3 as our hash function for small strings (up to 128 chars). We plan to replace it with a better non-crypto hash function which is fast and produces unique 128-bit hash for ...
- 15.4k
3
votes
1
answer
2k
views
Difficulty of collision vs preimage vs second-preimage attacks
It seems at first glance that brute-forcing a collision would be exactly as difficult for all of them. They all (I would expect) work like this: select a hash value, and then try messages to get an ...
- 141k
42
votes
2
answers
34k
views
Are there any known collisions for the SHA (1 & 2) family of hash functions?
Are there any known collisions for the hash functions SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512?
By that, I mean are there known values of $a$ and $b$ where $F(a) = F(b)$ and $a ≠ b$?
- 17.9k
1
vote
1
answer
731
views
Using variable length CBC-MAC, can some block cipher with a fixed k be used as a cryptographic hash function?
If a variable length CBC-MAC is used with a block cipher (a.k.a. pseudorandom permutation), does there exist a block cipher such that implementation of this CBC-MAC may be used as a cryptographic hash ...
- 147k
2
votes
1
answer
235
views
Would the Intel SHA extensions help in creating SHA1 collisions?
Would the Intel SHA extensions help in creating SHA1 collisions? AMD Ryzen and EPYC supports them.
- 131
2
votes
1
answer
4k
views
SHA256 Collisions
If we take every possible hash ($16^{64}$) and rehash it, the amount of possible outcomes for any given rehash is 1 out of $16^{64}$. So, all possible rehashes is equal to all possible unique hashes.
...
- 393
31
votes
2
answers
9k
views
Fixed point of the SHA-256 compression function
SHA256 Free Start Self Collision (Full 64 rounds)
IVec:
72BF9EF1 27B82DFB F298F3B7 22B6C32C 18A54860 4C032D91 ADD7B85B 7ED1A4AC
Block:
...
CommunityBot
- 1
3
votes
1
answer
820
views
Birthday attack for combination of hashes
I have to answer the following question for a homework assignment:
You have a hash algorithm that converts a $2\cdot n$ bit number to an n bit
number. How many hash values do you have to ...
- 141k
1
vote
0
answers
198
views
How many times does a hash function have to be evaluated?
I have the following homework assignment:
$n$ is an even number, $1^n$ and $0^n$ are $n$-bit strings and $x$, $y$ and $z$ are arbitrary strings of length $n$.
How many evaluations of hash ...
- 17.9k
1
vote
2
answers
237
views
Hash then Sign approaches
I am learning about digital signature. For performance, we normally do hash then sign.
One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but under chosen message attack, this ...
- 4,913
3
votes
1
answer
4k
views
What makes a hash like SHA1 resistant to collisions?
I have been reading about SHA1 and SHA256 and how they actually hash a string of text to a unique hashed message. But what I dont understand is what makes them resistant to collisions.
Whats the ...
- 19.6k
3
votes
1
answer
546
views
Birthday attack to find near collision
Follow up on this question: How efficient are the generic attacks regarding near-collision-resistance?
Let $H:\{0,1\}^∗→\{0,1\}^n$ be a cryptographically secure hash function. Let $k\in \mathbb{N}$ ...
- 92.6k
2
votes
0
answers
407
views
Hash function for sets with efficient membership testing
Is it possible to construct a collision-resistant function that hashes a set of values but also allows membership testing?
Essentially, I'm looking for a pair of functions, $\text{H} : \{0,1\}^{**} \...
- 2,834
0
votes
1
answer
110
views
Second Preimages on n-bit Hash Functions by John Kelsey and Bruce Schneier
I read your https://www.schneier.com/academic/paperfiles/paper-preimages.pdf
And found there:
«3.2 A Generic Technique: Multicollisions of Different Lengths»
<...
- 11
1
vote
1
answer
198
views
Is the subset of hash digest collision-resistant if hash function is collision-resistant?
Let $H(\cdot)$ be a collision resistant hash function,
$H:\{0,1\}^{\mathsf{poly(n)}} \rightarrow \{0,1\}^n$,
We define a new $H':\{0,1\}^{\mathsf{poly(n)}} \rightarrow \{0,1\}^k$, where we randomly ...
- 403
4
votes
2
answers
376
views
Why is a hash of blocks - with index - weaker than hashing the entire thing?
Let's say we want to sign message $M$ with RSA using a safe hash function.
However, instead of signing $\operatorname{hash}(M)$,
We split the message into 64-bit blocks (...
CommunityBot
- 1
0
votes
2
answers
2k
views
Hash length vs Data length
I'm very (!) new to the world of cryptography, so pardon me if this question is very basic.
Related to hashing, something that hasn't become clear to me is the relation between data length and hash ...
- 46k
5
votes
1
answer
832
views
Does Lamport's authentication scheme still work if the hash function is not collision-resistant?
Geology professor Peter McMenteur gets interested in Lamport’s authentication
scheme. After a brief study, he claims that the scheme works even if the hash
function is substituted by a function ...
- 46.1k
1
vote
2
answers
998
views
Concatenation of multiple shorter hashes vs a single long hash
I permanently need to hash lots of data quickly, but the result only needs to be collision resistant.
Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest ...
- 2,297
0
votes
1
answer
2k
views
Concatenating a hash function for generating one hash for multiple files
Assuming we use SHA256 as hash function. In practice you see that a Merkle tree is used to concatenating multiple hashes together to one single root hash.
A Merkle tree is a binary tree which always ...
- 5,664
3
votes
1
answer
174
views
Is there any hash function for which a preimage of a fixed element is always known?
I'm wondering if there is any collision-resistant hash function $h^s(\cdot)$ satisfying that there is a fixed value $c$ such that, for each $s$, a value $x_s$ satisfying $h^s(x_s) = c$ is known. This ...
- 17.9k
4
votes
1
answer
433
views
Is HMAC-MD5 collision-resistant if the key is unknown?
I'm in a situation where I need to use HMAC-MD5 (for a learning, non-production application) and it needs to be collision-resistant.
So my question: Is HMAC-MD5 collision-resistant if the key is ...
- 17.9k
2
votes
1
answer
1k
views
Why the $IV$ used in Merkle–Damgård has to be fixed to a specific value?
I just can't figure out why on earth the $IV$ in Merkle–Damgård 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 ...
- 92.6k