Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
697
questions
0
votes
0
answers
24
views
Do L-trees remove the need of collision resistance hashes in XMSS MT?
I read that the bitmasks in XMSS-MT lower the security requirements from a collision resistant undetectable hash to a 2nd preimage resistant undetectable hash (see LMS vs XMSS: Comparion of two Hash-...
- 25
1
vote
0
answers
37
views
What is an advantage of the Charles--Lauter--Goren hash function?
What is an advantage of the Charles--Lauter--Goren hash function (based on isogenies of elliptic curves) among other provably secure collision-resistance hash functions ? I heard that it is slower.
- 317
1
vote
1
answer
55
views
Hash of concatenated values (one public, one private)
Assume two end-points $A, B$. $A$ sends to $B$ a $Hash(pv||key)$, where $pv$ is a public value that can be intercepted by attackers. The $key$ is a common secure shared key in both end-points, and $||$...
- 675
0
votes
1
answer
74
views
Randomness and authentication on short value outputs (48 bits)
I want to implement a client that generates random 48-bit values and send them as broadcast messages. We assume also there is a legitimate receiver getting those values (so, there is some sort of pre-...
- 675
0
votes
1
answer
152
views
non-reversible additive cryptographic hash algorithm
I need a lightweight cryptographic hash function which is additive but not reversible, however I'm not sure such a function exists! (it would be better if it works in multisets as well)
By additive I ...
0
votes
0
answers
23
views
Why we need DSPR or Eq. 14 for the proof of SPHNICS+?
The paper says that
We show that preimage resistance (PRE) follows tightly from the conjunction
of second-preimage resistance (SPR) and decisional second-preimage resistance
(DSPR).
As I understand ...
- 113
0
votes
0
answers
38
views
Collision and pre-image resistances of a hash function based on SPRP
Assume we have a secure block cipher $E$ (strong pseudorandom permutation) and a fixed key $k$ which are publicly known. We construct our hash function $H(m)$ as
$$
H(m) = E_k(m_1) \oplus \dots \oplus ...
- 1
1
vote
1
answer
132
views
Clarification on nonce collision calculation
I've been working on a AES256-GCM implementation (in Java).
I'm a little bit stuck on the part where i need to decide how often i need to rotate my key.
I've got a lot of information from this posts:
...
- 13
0
votes
0
answers
83
views
1st Preimage, 2nd Preimage, Collision resistance of powers of 2 mod n
Let $n$ be a product of two odd, distinct large primes $p$ and $q$. Define the hash function as
$$
H_{F}(x)=2^{x} \bmod n
$$
Is this hash function resistant to 1st/2nd preimage and collision attacks? ...
- 1
0
votes
0
answers
58
views
Checking if a function is collision-resistant
Consider a prime order cyclic group $\Bbb G$ of order $q$ with generator $g$. Then consider the function$$f:\Bbb Z^n_q\to\Bbb G\\(\alpha_1,\alpha_2,...,\alpha_n)\mapsto g^{\alpha_1\cdot\alpha_2...\...
1
vote
1
answer
51
views
vary length hash collision on deterministic block cipher
I am trying to learn attack on hash collision. I guess for this scheme, it might be possible to use messages with different lengths to find a pair of same ciphertexts. An attempt is to use the same ...
- 13
0
votes
0
answers
34
views
How Davies–Meyer does work? [duplicate]
I am here so if I asked something wrong or in the wrong way please let me know.
How to hash compression large data into the fixed size of the string.
Edit:
How Davies–Meyer does work?
Take the example ...
- 101
1
vote
0
answers
70
views
Cryptographic hash function to map interval onto itself
Is there any existing approach to construct perfect hash function that map [0, M) to [0, M)? It should be one to one mapping and ...
- 111
0
votes
1
answer
351
views
Is a perfect hash function the same concept as a collision-resistant hash function?
About collision-resistant hash functions, in Katz's Introduction to Modern Cryptography,
6.1 Definitions
Hash functions are simply functions that take inputs of some length and
compress them into ...
- 151
0
votes
1
answer
800
views
can you generate an ID number quickly, with no collisions, and without IDs revealing information?
Is there a standard way to generate ID numbers one after the other such that:
You can guarantee, or almost guarantee, that you avoid collisions. (By "almost guarantee", I mean for example ...
- 145
1
vote
0
answers
80
views
Collision-resistant single-pass EdDSA?
Is there any reason why collision resistant variants of ed25519 that use a single-pass aren't used instead? For example:
$n = h(noncekey \| m)$
$h(R \| pub \| n)$ instead of $h(R \| pub \| m)$
or ...
- 77
1
vote
1
answer
97
views
Why do we need both bitmasks and keyed hash in SPHINCS+
I think one of them is related to multitarget attacks and the other is related to collision attacks. But I cannot find how hash based crypto related to hash collisions.
1-) Consider the following ...
- 113
2
votes
2
answers
139
views
Are SHA-1 hash collisions harder to find when files are big?
Was that just a coincidence, or did the 2 "shattered" pdf files whose SHA-1 hashes are identical had to be small in size (412KB) to make the collision attack easier?
- 57
1
vote
1
answer
115
views
Do proof of work hash function arguments have anything in common?
Some proof of work hashes have a lot of initial zeros. Do the arguments to the hash functions giving these zero containing hashes have anything in common, or are they stochastic?
What I am looking ...
- 123
3
votes
1
answer
166
views
Can a collision resistant hash return zero?
Recently, I have been reading the original proof of GCM.
It mentioned the properties of "almost universal" and "return zero" for hash function.
I wonder if there is a connection ...
- 125
3
votes
2
answers
320
views
Will Hashing Multiple Times Be More, Less, Or Similarly Secure As Hashing Once
Will Hashing Multiple Times Be More, Less, Or Similarly Secure As Hashing Once?
Flushing out this question:
I saw this claim:
List item: ...
- 31
2
votes
1
answer
783
views
Understanding Hash collisions - why bad?
I read few answers about the question: why are hash collisions so dangerous?
But did not get a really satisfying answer.
Assume we are the first people who found a SHA256-collision, like
sha256($§&...
- 23
3
votes
1
answer
442
views
Is there a quantum algorithm to find SHA256 collisions?
As I understand, the Bitcoin network can be seen as a supercomputer looking for SHA256 collisions. It hasn't found one yet (March 2022). Also, in the post-quantum cryptography era, you would be ...
- 133
0
votes
0
answers
54
views
Collision resistance analysis
I am learning about collision resistance security notion of hash functions. However, I got confused when collision resistance experiment started using "keyed" hash functions in the ...
- 63
2
votes
1
answer
53
views
Why randomness space must be significantly larger than the commitment space |R|>>|C| in order to generate a commitment string?
Why randomness space must be significantly larger than the commitment space |R|>|C|? the picture is from https://youtu.be/IkNZWJFcfcU?t=236
- 205
2
votes
1
answer
172
views
Deterministically produce an array of indexes based on input number
Please see the Reference section below for terms.
Is there a known one-way method to produce an array of indexes, based only on two input elements:
length of the resulting array
number, used as a key ...
- 143
1
vote
2
answers
825
views
Is the composition of collision resistant functions H' = h1(h2()) collision resistant?
Suppose there are two collision-resistant hash functions $h_1$ and $h_2$ with output sizes of $n_1$ and $n_2$ respectively.
Is $H'(x) = h_1(h_2(x))$ collision resistant for the different ...
- 11
0
votes
1
answer
143
views
Finding collisions of polynomial rolling hashes
A polynomial hash defines a hash as $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, all modulo $2^n$ (that is, in $GF(2^n)$).
For brevity, let $c$ be a $k$ dimensional vector (encapsulating all the ...
- 135
1
vote
2
answers
208
views
Does concept "Collision Resistance" and "Binding Commitment" in cryptography similar?
I found there are two perplexing and related concept "Collision Resistance" and "Computation Binding in Commitment" in cryptography.
I found the wikipedia's explanation is ...
- 205
1
vote
1
answer
70
views
Checking equivalence among distributed sets
I have elements from $\{0, 1\}^{n}$ (range of a hash function)
The master $A$ can have any subset of this range.
There are clients that each have a subset from the space, too.
I want to make sure that ...
- 581
2
votes
2
answers
1k
views
Is there collision in encryption like in hash functions?
In hash functions, $h(m) = h(m_1)$ is called collision and is very undesired that they are feasible to find as it undermines hash security. However, is there essentially analogous concern in ...
- 71
1
vote
0
answers
735
views
How to find the 6 main properties of cryptographic hash functions when implementing a hash function?
According to this there are at least 6 "properties" all cryptographically secure hash functions strive to attain:
Deterministic: the same message always results in the same hash;
Quick: it ...
- 171
1
vote
1
answer
199
views
Avoiding MD5 collision with secondary partial hashes
I am trying to design a VCS like program that determines if the files are the same by comparing their MD5 hashes.
Then I read about MD5 collisions here, and I wonder if I can work around that by doing ...
- 121
2
votes
0
answers
121
views
Why this function isn't second preimage resistant?
Why is $h(k,m)$ not second-preimage resistant? Let $E_k$ be a block cipher where the message space is the same as the key space.
$$h(k,m)=E_k(m\oplus k)\oplus k$$
I've been reading about second ...
- 21
1
vote
0
answers
55
views
One way function with fixed point
As part of an exercise in a cryptography course, I want to come up with a one way function for which it is "easy" to find a collision from a given OWF. To achieve this, I tried the following:...
- 21
3
votes
1
answer
280
views
Why a hash function in a manner similar to CBC-MAC is not collision-resistant?
I'm reading the book The Joy of Cryptography by Mike Rosulek.
When reading Chapter 11, on the hash function, I found a very interesting exercise. Does anyone have ideas on how to prove this?
Please ...
user99141
2
votes
3
answers
231
views
Reversing hash function makes possibilities increase exponentially, yet there is a finite number of inputs. How?
When trying to reverse a hash function, there is loss, e.g.
a+b=c
given c=5, try to go back to a,b (previous step)
(a,b)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)
but, ...
- 41
0
votes
1
answer
182
views
truncated sha3-512
Let's say I need performance on 64-bit machine, then SHA3-512 is the way to go.
SHA-512/256(x) is SHA-512(x) with output truncated to 256 bits, according to https://pycryptodome.readthedocs.io/en/...
- 199
3
votes
1
answer
268
views
Collision finding method
The "birthday paradox" places an upper bound on collision resistance: if a hash function produces $N$ bits of output, an attacker who computes only $2^{N/2}$ (...) hash operations on random ...
- 199
5
votes
3
answers
1k
views
Composition of cryptographic hash functions
I've stumbled upon many opinions, so I ask about them myself.
Let $H(x)$ and $F(x)$ be hash functions.
is $H(F(x))$ or $F(H(x))$ safer than $H(x)$ or $F(x)$
is $H(F(x))$ or $F(H(x))$ safe when $H(x)$ ...
- 199
2
votes
0
answers
39
views
Cyclical Redundancy Check and bijections [closed]
Let $F_M(n)=\operatorname{CRC32}(M|n)$, where $M$ is an arbitrary length prefix message, $n$ is a 32 bit integer (whether little or big-endian encoded is unimportant) and "|" is simply ...
- 21
0
votes
3
answers
267
views
Two Elliptic Curve Points having the Same X coordinate
Suppose in a elliptic curve (say the curve equation is: $y^2 = x^3 -17$) with prime order $q$, we have $(x,y_1) = nP$, where $P$ is a generator and $n<\lceil{q/2}\rceil$. Can we claim that there ...
- 3
1
vote
1
answer
104
views
Is $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ with $p$ prime (strongly) collision-free?
Let $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ for $g \in \mathbb{Z}_{p}^{*}$ where $p$ is prime. Is this function (strongly) collision-free meaning we cannot find ...
- 121
0
votes
0
answers
71
views
What happens when we hash already hashed values, concatenated together?
I read on the page 16 of On the Security of Hash Function Combiners that
the classical combiner for collision-resistance simply concatenates the outputs of
both hash functions $Comb_{\mathbin\|}(M) = ...
1
vote
1
answer
666
views
AES-CBC Hash Function Collision Resistance
I am using AES-CBC as a hash function which is encrypting a block of length n. The blocks, m = (m1, m2, ..., mn). The IV is one block long and the encryption key is length 128, 192 or 256 bits.
Will I ...
- 13
1
vote
3
answers
214
views
if i enter a password that's incorrect but that collides with one when hashed, will it let me in?
suppose no salt or pepper is used and passwords are hashed plain, will entering incorrect password that just hashes to the same let me in? i know that one use of salting/peppering techniques is to, ...
- 71
2
votes
3
answers
191
views
$2^{64}$ versions of the same message
I am reading a textbook and in there they explain the property of hash functions. In particular, they give an example of how unlikely it would be to find a second input value that would match the hash ...
- 123
0
votes
2
answers
789
views
Is it possible to get the SHA256 hash collision with partial known data
I have a text sentence that consists of 448 digits [0-9] [a-f] (in HEX format).
This text sentence is partially cut off, but I know the middle, and the beginning ...
1
vote
0
answers
47
views
Hash function producing cycles with expected max length
Is there a known hash function $H_k: X\to X$ such that:
$\forall{x\in{X}},\exists{n\in{\mathbb{N}}}, n<k \land H^n(x)=x$
=== EDIT ===
By hash function I mean ...
- 111
1
vote
3
answers
170
views
Hash function collision importance
Suppose a collision has been found in a certain hash function,
such that H(x1) = H(x2)
However, x1 and x2 are both a seemingly 'random' collection of bits which do not convey a coherent message, and ...
- 11