Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
697
questions
1
vote
1
answer
168
views
Is the collision chance 2^(n/2) of an n-bit tag τ unchanged if reduced to (n/2)-bits using a reduction of τ to some 2^(n/2) order group element?
If $H(k, Μ) = τ$, in the context where $τ$ is an $n$-bit tag produced as a mac on a key, $k$, and a message, $M$, through a keyed-hash function, $H$, is there a function $F(τ) = T$ that transforms $τ$ ...
- 53
0
votes
1
answer
144
views
Homomorphic hash from prime order group $G$ to $Z_p$
Let $G$ be a cyclic group with the generator $g$ and of prime order $p$ such that the discrete-logarithm problem is hard in $G$.
A hash function is homomorphic if $H(a\ast b)=H(a)\cdot H(b)$ (where ...
- 335
0
votes
1
answer
1k
views
Using bcrypt to always produce the same hash like SHA, MD
I want to take advantage of the slow property of bcrypt to hash an input but also want to get the same hash value for the same input every time just like SHA, MD, etc.
So in order to do that, instead ...
- 143
-1
votes
1
answer
53
views
Is it possible to have collision resistance but not pre-image and 2nd pre-image resistance?
I have studied cryptographic hash functions quite a lot, but have not completely understood whether it is possible to have collision resistance but not pre-image and 2nd pre-image resistance at the ...
4
votes
2
answers
951
views
Many near collisions but no full collision
I read this question: Cracking $f(x) = Cx \oplus Dx$
Asking about finding collisions in a simple 64 bit hash, and I thought I will give it a go myself just for fun.
I quickly wrote code to find ...
- 11.5k
0
votes
2
answers
69
views
Using hash of data as proof of integrity and preventing collision
Rather than storing user data when interacting with an app, I am storing the SHA3-256 of the data. This is because data storage in this particular environment is very limited.
The data can be several ...
- 103
3
votes
0
answers
143
views
Cracking $f(x) = Cx \oplus Dx$
A program I reverse engineered is using $f(x) = Cx \oplus Dx$ where C = 0x20ef138e415 and D = 0xd3eafc3af14600 as a hash ...
- 31
1
vote
1
answer
83
views
Preimage attack on sum of two Hash functions modulo 2
If a hash function $H$ is defined as $H(x_1,x_2) = H_1(x_1) \oplus H_2(x_2)$
for two n bit good hash functions $H_1$ and $H_2$
then how can we construct a preimage attack on $H$ that is of $O(2^\frac{...
- 35
2
votes
1
answer
105
views
How does Authentication-Key Recovery for GCM work?
In his Paper "Authentication weaknesses in GCM" Ferguson describes, how some bits of the error polynomial can be set to zero, thereby increasing significantly the chance of a forgery.
Q: ...
- 1,477
0
votes
0
answers
39
views
If the source code of SHA256 hashing algorithm is available in public, why can't it be hacked? [duplicate]
If the SHA256 algorithm is public, why can't attackers use it to create more collisions rendering the algorithm useless?
- 1
0
votes
0
answers
166
views
Merkle-Damgård construction
Let $H^f$ be a hash function designed using Merkle-Damgård construction on $f:\{0,1\}^{2n}\to\{0,1\}^n$. Write an algorithm that makes approximately $2.2^{n/2}$ many queries to $f$ and find four ...
1
vote
1
answer
113
views
Is it possible to exploit MD5 weaknesses to create an artificial collision for a password?
If it is possible, could an attacker create a collision for an MD5 password in a database? Could they look at an MD5 hash output and figure out data that creates the same MD5 hash?
- 11
2
votes
1
answer
77
views
Security of Hash Functions
Given a Hash Function H, how are the properties such as collision resistance, target collision resistance, one wayness, and non-malleability proved? I have read about hash function and stating that it ...
0
votes
1
answer
96
views
Two Different Ciphers with Same MD5
I was wondering if someone could help explain md5 collision abit better. I found this resource: https://www.mscs.dal.ca/~selinger/md5collision/ where they provided an example of where two cipher texts ...
1
vote
2
answers
211
views
Can there be an injective function that maps a large set of integers to a smaller set while being "collision-aware"
Consider two sets:
The "big set" contains all integers between $0$ and $2^{160}$ exactly once.
The "small set" contains all integers between $0$ and $2^{32}$ exactly once.
Given ...
- 19
-2
votes
2
answers
118
views
What are the security flaws of SHA? [closed]
I have been researching SHA algorithms extensively, specifically SHA1, SHA2-256, SHA2-512, SHA3-256, and SHA3-512, and have found many instances of successful collision attacks as well as methods.
In ...
- 119
2
votes
2
answers
276
views
Does SHA-256 have (128-time + 128-space = 256-overall)-bit collision resistance?
First, we consider those hash functions that can actually provide 256-bit pre-image security, and not something like SHAKE128<l=256bits> where the sponge ...
- 8,005
1
vote
2
answers
1k
views
Can SHA512 and SHA3-512 Make Same Collisions?
Does combining those two different cryptographic hash functions in HMAC, when each hashes the same data separately, then saved together, guarantee zero possibily of a collision simultaneously or is ...
user91960
0
votes
0
answers
169
views
Why do the first two digits of the hash table not collide within CRC32?
In this Python CRC32 table look-up method, the polynomial is 0x104c11db7.
I can understand that the generated table does not collide. After all, as long as the ...
- 9
1
vote
1
answer
170
views
Breaking merkle damgård construction that uses bitwise and?
I'm preparing for a exam in crypto course, and i'm doing some practice problems.
I'm now playing with this problem:
...
0
votes
2
answers
326
views
Shake256 Infinity Collision
Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?
1
vote
1
answer
577
views
Example of a Hash function which is second pre-image resistant but not collision resistant [duplicate]
We know that a collision resistant hash function is also second pre-image resistant. But the converse is not necessarily true.
I am looking for the example of a hash function which is second pre-image ...
- 149
8
votes
3
answers
571
views
What is this AES SBOX triplet property?
While playing around with the AES SBOX, I found out that there are 85 unordered triplets (a, b, c) that have the following characteristics:
...
- 181
4
votes
2
answers
5k
views
Are SHA-256 and SHA-512 collision resistant?
Context: Designing a TinyUrl system. The user inputs a lengthy URL and the system computes the hash and encodes it binary64 and sends it back to the user.
From what I understood so far (from this ...
- 143
3
votes
2
answers
359
views
Use slow hashing to reduce digest size?
I have seen this question on MD5 replacement for 128 bit digests. It is said numerous times that having a 128 bit digest is impossible today because finding a collision would only require $2^{64}$ ...
- 231
1
vote
3
answers
511
views
Using date stamp down to milliseconds / ticks as a salt?
As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash.
The salt is often stored with the hash, either prepended or as a separate field.
As ...
- 113
1
vote
1
answer
90
views
Depth of the SHA-256 collision search knowing partial input and final hashes
So I have a partial input data (string) PART1+UNKNOWN+PART2, length of UNKNOWN is self-describing.
I have a bunch of valid ...
- 13
0
votes
1
answer
43
views
Finding multiple smaller collisions equal work as finding a bigger collision?
Problem A:
I receive two hash digests $H(x), H(y)$ and the corresponding preimages $(x, y)$.
$H$ is a 128-bit cryptographic hash function: $H: \{0,1\}^{*} \longrightarrow \{0, 1\}^{128}$
I need to ...
1
vote
3
answers
402
views
Is collision resistant hash enough for one-block counter mode?
Let $H:\{0,1\}^*\rightarrow \{0,1\}^\ell$ be a collision resistant hash function (CRH), and let $\Pi = (\mathsf{enc,dec})$ be an encryption scheme with the following properties:
$\Pi.\mathsf{enc}: \...
- 413
0
votes
0
answers
291
views
Hash Function that is Collision Resistant but not Puzzle Friendly
Is there any example of a Hash function that is collision-resistant but may not be puzzle-friendly, similarly example of a hash function that is puzzle-friendly but not collision-resistant?
Puzzle ...
1
vote
0
answers
59
views
Are the hash functions collosion resistant or not? [closed]
If H is collision resistant then the following are collision resistant or not?
H'(x) = H(x) || H(x)
H'(x) = 1 || H(x)
My thoughts:
I am confused in question 1. In case of different hash function(H'(...
3
votes
2
answers
311
views
How many different keys can be derived with HKDF before two outputs are identical?
How many different keys can be derived with HKDF before two outputs are identical?
This question is about collision resistance, not about generating different keys with different parameters (eg. ...
- 31
1
vote
1
answer
90
views
Authentication tag length and post-quantum security
The recommended hash length for post-quantum security seems to be either 384-bits or 512-bits. 512-bits gives 256-bit collision resistance, and 256-bit security is obviously ideal for post-quantum ...
- 11
1
vote
1
answer
256
views
HKDF Bit Security
I've always understood the bit security of hash functions to be related to their output size (eg. collision resistance). However, I recently came across a table from a Wickr blog post that lists HKDF-...
- 11
4
votes
2
answers
541
views
What are the differences between a UHF (as used in cryptography) and a cryptographic hash function?
After reading about UHFs from different sources (From Algorithm books to Crypto books), I am still thoroughly confused about them.
How is a UHF different from other cryptographically secure hashing ...
- 2,249
5
votes
1
answer
331
views
Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken?
As we know, MD5 and SHA1 (to some extent) are broken, and older algorithms like SHA0 or MD4 and MD2 are very broken.
Does this also imply that the corresponding HMACs are also broken?
Obviously nobody ...
- 1,387
1
vote
1
answer
359
views
Why this function isn't preimage resistant?
Prove that the function
$$
G(z) = \mathcal{H}(z) \, || \, \text{LSB}(z)
$$
(where $\mathcal{H}$ is a collision resistant hash function, $||$ is concatenation and $\text{LBS}$ is the least significant ...
- 79
0
votes
1
answer
241
views
is there any hash collision attack that is not defeated by adding a salt first?
In the references I've read, all the uses of "collision attacks", whether classical collision attack or chosen-prefix collision attack, goes like this: "Alice creates a 'good' document ...
- 145
5
votes
2
answers
930
views
Extending the size of input for SHA-2 function
In the question Does a hash function necessarily need to allow arbitrary length input? many answers talk about the theoretical limit of the SHA-2 functions being $2^{64} - 1$ bit due to padding. I was ...
- 161
0
votes
1
answer
98
views
Will repeatedly applying a hash function to the prior result visit all possible hashes? [duplicate]
If one were to take a message, say "Hello world!", and compute the MD5 hash:
86fb269d190d2c85f6e0468ceca42a20
Then, taking the MD5 hash of this, and repeating that procedure:
...
- 103
5
votes
0
answers
133
views
Challenging $O(2^{n/2})$ for hash collisions using quantum computers
In "Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound" the authors Akinori Hosoyamada and Yu Sasaki state that it may ...
- 89.1k
8
votes
2
answers
1k
views
What are other good attack examples that use the hash collision?
When we consider the security of a cryptographic hash function with $n$ bit output, we simply say that it must have at least $\mathcal{O}(2^{n/2})$-time security against the (generic) collision attack ...
- 45.7k
0
votes
2
answers
494
views
Bits of security vs collision resistance?
I have been doing some research on security, and I am confused on the bits of security vs collision resistance, and I was wondering if someone could clarify my understanding.
For instance, if you have ...
- 3
3
votes
2
answers
261
views
Application of cryptographic hash functions which do not require collision resistance property
I can not understand why collision resistance of a cryptographic hash function is not required for some applications. for example, if we store the trusted hash of a file or program, and later when we ...
- 43
2
votes
1
answer
298
views
What are the “costs” to find a pre-image, weak collision, or strong collision?
For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?
- 23
2
votes
1
answer
363
views
Is this modification in Merkle-Damgård collision-resistant?
We modify Merkle-Damgård construction by setting $z_0:=L$ (the length of the message), computing $z_i:=h(z_{i-1}||x_i)$ for $i=1,...,B$ and defining $H(x):=z_B.$ Is this construction collision-...
- 21
0
votes
1
answer
68
views
Time and Space complexity of MiniAES
I am currently doing my masters research on security of wireless sensor networks, the topic is "ENHANCING THE SECURITY OF WIRLESS SENSOR NETWORKS BY COMBINING GEOENCRYPTION AND LIGHT WEIGHT ...
-2
votes
1
answer
154
views
How much brute forcing efforts needed to find 2 or more inputs that generating same SHA256 outputs
Say I have SHA256 hash result that produced from 2000 bits inputs. For example, 0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef (64 bit hex representation) is the SHA256 output.
...
- 61
2
votes
2
answers
618
views
Examine whether a hash function is collision-resistant
Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$:
$$
h_1(...
- 79
0
votes
0
answers
94
views
How a collision for a function can be for another one
We have two bit strings $x\in\{0,1\}^q$ , $y\in\{0,1\}^w$ of length $q$ bits, and $w$ bits. The notation $x\mathbin\|y$ means $(q+w)$ bits long concatenation,
And the functions: $H∶\ \{0,1\}^* \to \{...
- 117