Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
712
questions
0
votes
0
answers
116
views
Do "superfast" keyed hash functions exist?
A common family of requirements for (cryptographic) keyed hash functions is that the function $h(k,-)$ should have good collision resistance for all keys $k$, even if the key $k$ is known to the ...
1
vote
1
answer
94
views
Hash-Then-Encrypt or Encrypt-Then-Hash on Keyed Hash Functions
I have seen other answers here on Stack Exchange regarding MAC-Then-Encrypt vs. Encrypt-Then-MAC (and this article regarding MAC-Then-Encrypt padding oracle attacks on SSL) as well as generic Hash-...
- 11
0
votes
0
answers
65
views
Having trouble providing a distinguisher proving this hash function is not collision-resistant
As suggested by the title, I'm working on an exercise where I'm given a hash function $H$ that takes in an input string $x$. I'm supposed to construct a distinguisher that proves $H$ isn't collision-...
1
vote
1
answer
88
views
Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]
I came upon the following hash function (pseudo-code):
...
- 33
2
votes
2
answers
167
views
A question about "attacks on MAC key space"
At page 336 in "Handbook of Applied Cryptography - Menezes", I see the sentence
For $n$-bit MAC with $t$-bit key space this requires $2^t$ MAC operations, after which one expects $1+2^{(t-n)...
- 21
1
vote
1
answer
39
views
Collision ISIS Problem
I'm trying to understand the inhomogeneous SIS problem and I'm came across to a scenario that I don't know how to evaluate.
Let $A,B \in \mathbb{Z}_q^{n\times m}$ be two random matrixes and $u,v \in \...
1
vote
0
answers
63
views
Is it possible to get the negative point with −x in that version of the Pedersen hash over the BaybyJubJub curve?
The Pedersen hash is a low constraints friendly hash for Zk-Snarks.
Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
- 153
2
votes
0
answers
101
views
Security of Even-Mansour based Merkle-Damgård
Assuming I have single-key Even-Mansour with single $2n$-bit permutation in wide-pipe Merkle-Damgård specifically with Matyas-Meyer-Oseas mode outputting $n$-bit hash.
What security can I expect ...
- 1,649
2
votes
1
answer
110
views
Recommended output filter for Rumba20 [closed]
Rumba20 is a compression function that maps a 192-byte (1536-bit) string to a 64-byte (512-bit) string. It's designed to provide collision resistance by using Salsa20 (or ChaCha20) with the ...
- 1,587
1
vote
1
answer
240
views
Pedersen Hash : when truncating the hash to keep only the X coordinate, is it possible to compute a collision when the Babyjubjub curve is used?
The Pedersen hash is a low constraints friendly hash for Zk-Snarks.
Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
- 153
0
votes
1
answer
107
views
If we supply a random uuid4 hashed salt to Hashid, will it be considered secure?
Ideally, Hashids -: https://pypi.org/project/hashID/ are considered insecure and it is recommended that we should not use them for any sensitive functions. Though, is a HashId considered secure if we ...
5
votes
1
answer
105
views
The rigorous proof in the commitment based on CRHF
I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
- 147
2
votes
1
answer
152
views
Implementing a Merkle tree using a 128 bit hash function?
I need to implement a Merkle tree using a 128 bit hash function. In general, any hash function that guarantees pre-image, second pre-image and collission resistance should be fine to implement a ...
- 139
1
vote
1
answer
618
views
What does the 256 in SHA3-256 and SHAKE256 refer to?
I am simply wondering what the bit-length in the algorithm variant in the table below refers to? For the hash functions I assume that this refers to the ouput length in bits. For instance for SHA3-256 ...
- 335
2
votes
1
answer
108
views
theoretical hash collisions vs random number collisions
I have a theoretical question about the probability of collisions of hashes versus random numbers. I'm not interested in the exact probabilities. The exact hash function is not relevant (we can assume ...
- 123
3
votes
0
answers
110
views
Are there "light" versions of cryptographic hash functions?
After tinkering with cryptographic hash functions, I started wondering if they do have counterpart functions that would imitate their cryptographic properties but with a lower level of strength in ...
- 153
3
votes
1
answer
81
views
Analyzing the security of hash approaches
Say that I have a random oracle function $H$. This function outputs a value in $\mathbb{F}_{p}$ where $p \approx 2^{256}$. $H$ can accept either one or two inputs (outputting a single value in both ...
- 139
4
votes
1
answer
238
views
very smooth hash (VSH) Stepwise examples
Can someone please point me to or give me stepwise example of VSH hash function. I couldn't find an example or a reference implementation. I tried to go through original publication but it seems way ...
- 141
2
votes
1
answer
81
views
Merkle tree alternating hash and polynomial
I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $H$. Assume $H$ outputs a value in $\mathbb{...
- 139
1
vote
1
answer
84
views
Hardening a polynomial checksum scheme
I have a checksum scheme that uses a simple polynomial summation as described here.
Basically I'll take a random value $R$ and a set of inputs $[v_0, v_1, v_2]$ and checksum it like $v_0*R + v_1*R^2 + ...
- 139
1
vote
1
answer
69
views
Hash Flooding a Randomized Modular Hash Table
Assume we have a hash table using the function h(x) = x mod 32. h(x) = x mod 33. Also assume it dynamically resizes by doubling the amount of buckets and rehashing. If I was able to provide inputs for ...
- 113
0
votes
1
answer
318
views
Checking encoded strings for a hash collision in Python [closed]
There is a common term used in cryptography called a hash collision. If I am reading the definition correctly on Wikipedia, this can occur if two different data values give rise to the same hash ...
- 111
1
vote
1
answer
161
views
Does an increase of message size increase the number of guesses to find a collision?
If I hash a 256-bit message and generate an output digest of the same size with a cryptographic hash function then the number of guesses to find a collision is expected to be 2^128.
Does increasing ...
- 391
1
vote
0
answers
64
views
How to estimate the collision resistance of a hash function if a secondary key is used (keyed hash function)?
According to the documentation of HighwayHash, for finding a collision are expected $m \over 2$ guesses, being $m$ the message.
By contrast, 'strong' hashes such as SipHash or HighwayHash require ...
- 391
2
votes
1
answer
178
views
Confusion+Diffusion comparison table? (e.g. with Avalanche Criterion / SAC)
I'm looking for a general comparison of encryption algorithms in regard to Confusion and Diffusion (as defined by Claude Shannon),
and if possible, specifically for their SAC and BIC quality.
For ...
- 144
1
vote
1
answer
41
views
Is a single 256 bits hash table in which the digests are from mixed cryptographic hashing algorithms still considered collision resistant?
Consider a single hash table containing digests from about 10 different 256 bits cryptographic hashing functions, like SHA256, SHA3, KECCACK256, BLAKE2, BLAKE3, etc...
Is such table still considered ...
1
vote
0
answers
82
views
What is the proof that the RSA is collision-free?
We have the RSA function:
$c = m^e (mod n)$.
I would like to know the proof that there is not an $m_1$ and an $m_2$ message that produce the same $c$.
My thoughts:
We know that $m \le n$, so $m_1 \...
- 11
2
votes
2
answers
1k
views
Wouldn't concatenating the result of two different hashing algorithms defeat all collisions? [duplicate]
Let's say I have three messages: A B C
And I run each of these through two different ...
- 983
2
votes
1
answer
112
views
Is there a CRHF based on integer factorization problem or RSA assumption
We know that in the black-box sense, we cannot use one-way functions to construct Collision Resistant Hash Functions.I feel that in my impression, I have never seen CRHF based on integer factorization ...
- 147
3
votes
1
answer
156
views
UOWHF vs CRHF / Relevance of UOWHF
What's the difference between UOWHF and CRHF and why are UOWHF useful?
As far as I understand, Universal One-Way Hash Functions are an alternative to CRHF. While for CRHF it is hard, given randomly ...
- 103
1
vote
0
answers
38
views
Checksum algorithm using system of multivariate polynomials
I'm working on a protocol that uses zero-knowledge proofs. I'm looking at systems of polynomial equations as cheap solutions for checksumming data. Note, I'm not looking for trapdoor functionality ...
- 139
2
votes
0
answers
66
views
Is there any standard extension of the Merkle-Damgård transform that handles arbitrary-length inputs?
I have seen multiple sources claim that the Merkle-Damgård transform is able to build a collision-resistant Hash-function $H$ for arbitrary-length inputs from a compression function $h : \{0,1\}^n \to ...
- 131
1
vote
1
answer
96
views
Does a salted password hash reveal info about the password?
Assume a password is hashed with a secure salt, e.g. hash = sha256(password+salt). If the hash and the salt are made public, an attacker can perform an attack by ...
- 435
1
vote
1
answer
162
views
Probability of a collision in the sum of hashed 64-bit values
I'm working on a problem where I need to track some state that's 64-bit integers. It turns out this state can tracked by simply accumulating a sum of differences, which in my case turns out to ...
- 175
5
votes
2
answers
592
views
Does using multiple hashes (to check if a file has been spoofed) reduce collisions?
I'm trying to create a script that will take a snapshot of the contents of a directory. For each file, all possible metadata will be recorded and written to the database. The point is that with some ...
- 51
2
votes
1
answer
103
views
Free-start collision vs Semi-free-start collision
Recently, I am very interested in the hash function attack paper, so I am reading it closely.
I found out that there are Free-start and Semi-free-start settings among the attacks on the hash function.
...
- 315
1
vote
1
answer
251
views
Data fingerprint using polynomial and Schwartz-Zippel Lemma
I'm working on a protocol and am looking for a way to fingerprint a set of elements. All elements are evenly distributed across a finite field that is integers modulus $2^{256}$.
Assume I have a set ...
- 139
0
votes
1
answer
450
views
Is it possible that two different messages have same hash code? [duplicate]
As I know a very common hash code has 256 bits.
From a message, it outputs a hash code that's 256 bits. That hash code should be unique to that message. That message can be something like email.
But a ...
2
votes
1
answer
148
views
Can I use last N blocks of AES-CBC +IV as hash?
Suppose I want to take advantage of hardware accelerated symmetric encryption like AES and use it to compute a “hash”. How collision resistant would it be if I’d take the IV + last N blocks of an AES ...
- 165
3
votes
1
answer
179
views
Will XORing two bad hashes lead to a collision resistant hash?
I'm reading the fourth edition of "Cryptography: Theory and Practice" by D.R. Stinson and M.B. Paterson.
In the book, they have mentioned the concept of "collision-resistant hash" ...
- 31
0
votes
1
answer
66
views
How to understand the argument “if the adversary outputs x then it queries (a, x) to oracle”？
When I read the work of Dodis et al. ref1, it looks as if I have encountered a simple logical bug. (I'm not concerned with the details of secure proof techniques, but with the logic of reasoning.)
In ...
- 1
4
votes
3
answers
410
views
Is the sum of hashes a suitable hash for sets?
Let $H: X \rightarrow \{0, 1\}^b$ denote a cryptographically secure, $b$-bits hash function on a set $X$. Let $H^*: \mathbb{P}(X) \rightarrow \{0, 1\}^b$ be a function on the power set of $X$ defined ...
- 1,375
1
vote
1
answer
209
views
Can I use a cryptographic hash function such as sha256 for Randomness Extraction [duplicate]
I want to transform a semi random input to a shorter, uniformly random bit string. Assuming there is enough entropy in the semi random input, can I use a collision resistant hash function to extract ...
1
vote
0
answers
120
views
Hash function collision resistance
I have a course work for university, and am not sure on my answer so if anyone could please take the time out to read the question and my answer to let me know if I'm going in the right direction that ...
- 77
1
vote
0
answers
127
views
Probability of getting a collision using chosen plaintext attacks
For university I am doing a piece of coursework right now. This question is focusing on CPA and collisions using CPA.
Question:
I have attempted to answer part 3, but am not very confident in the ...
- 77
1
vote
0
answers
159
views
AES-CBC collision resistance of hash function [closed]
I'm very new to cryptography and am having some issues with the following question
...
- 11
3
votes
0
answers
134
views
Is WPA2 collision-proof?
I was experimenting with hashcat and aircrack to test WiFi security.
The WiFi AP is a WPA2 encrypted network. The tool I used to ...
- 31
1
vote
0
answers
84
views
How many hashes to recover a salted password? [closed]
If a password p is selected from a space of 2^64 passwords, and the server stores this as a hash, h = SHA-256(p||s) where s is a random 128-bit salt. How many maximum hashes would an attacker need to ...
- 161
0
votes
0
answers
34
views
How to factor $n = p.q$, where $p,q$ are primes, knowing a multiple of $\mathrm{lcm}(p-1, q-1)$? [duplicate]
I was reading this post https://senderek.com/SDLH/ about Shamir's hash function, which is defined as follows:
Let $p,q$ be positive prime integers and let $n=p\times q$. Let $\ell = \mathrm{lcm}(p-1, ...
- 445
2
votes
1
answer
274
views
How do Pre-image, Second pre-image and collision resistance actually work? How does this affect data integrity?
I'm working on this past exam paper and found this question about pre-image resistance and its relation to data integrity:
Displaying the hash of a file on a website in order to provide data integrity ...
- 183