# Questions tagged [collision-resistance]

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

712 questions
Filter by
Sorted by
Tagged with
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
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-...
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
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): ...
167 views

1 vote
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. ...
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 ...
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 vote
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. ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
81 views

1 vote
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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
82 views

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 \... 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 ... 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 ... 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 ... 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 ... 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 ...
1 vote
96 views

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 ...
1 vote
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 ...
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 ...
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. ...
1 vote
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 ...
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 ...
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 ...
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" ...
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 ...
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 vote
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
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
### 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, ...