Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
5 votes
1 answer
87 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 ...
constantine's user avatar
2 votes
1 answer
71 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 ...
Lorenzo's user avatar
  • 139
1 vote
1 answer
79 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 ...
Rory's user avatar
  • 313
2 votes
1 answer
58 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 ...
Garret Wilson's user avatar
3 votes
0 answers
105 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 ...
Ryan B.'s user avatar
  • 153
2 votes
1 answer
68 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 ...
vimwitch's user avatar
  • 119
4 votes
1 answer
206 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 ...
Shivendra Mishra's user avatar
2 votes
1 answer
55 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{...
vimwitch's user avatar
  • 119
1 vote
1 answer
79 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 + ...
vimwitch's user avatar
  • 119
1 vote
1 answer
54 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 ...
DivideByZero's user avatar
0 votes
1 answer
126 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 ...
Entree's user avatar
  • 111
1 vote
1 answer
143 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 ...
alpominth's user avatar
  • 181
1 vote
0 answers
43 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 ...
alpominth's user avatar
  • 181
2 votes
1 answer
108 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 ...
foo's user avatar
  • 145
1 vote
1 answer
35 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 ...
Rafael Werlang's user avatar
1 vote
0 answers
71 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 \...
Jakab Martin's user avatar
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 ...
Eddie's user avatar
  • 983
2 votes
1 answer
87 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 ...
constantine's user avatar
3 votes
1 answer
85 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 ...
sbluff's user avatar
  • 103
1 vote
0 answers
33 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 ...
vimwitch's user avatar
  • 119
2 votes
0 answers
50 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 ...
Steven's user avatar
  • 131
1 vote
1 answer
76 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 ...
n-l-i's user avatar
  • 435
1 vote
1 answer
137 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 ...
gct's user avatar
  • 175
5 votes
2 answers
496 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 ...
Wacky Skiff's user avatar
2 votes
1 answer
70 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. ...
pioneer's user avatar
  • 305
1 vote
1 answer
232 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 ...
vimwitch's user avatar
  • 119
0 votes
1 answer
223 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 ...
new-to-crypto's user avatar
2 votes
1 answer
111 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 ...
Konrads's user avatar
  • 165
3 votes
1 answer
167 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" ...
Dniel BV's user avatar
0 votes
1 answer
48 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 ...
Duan's user avatar
  • 1
4 votes
3 answers
276 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 ...
Matteo Monti's user avatar
  • 1,365
1 vote
1 answer
129 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 ...
ONUR EREN ARPACI's user avatar
1 vote
0 answers
85 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 ...
hasin's user avatar
  • 77
1 vote
0 answers
89 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 ...
hasin's user avatar
  • 77
1 vote
0 answers
116 views

AES-CBC collision resistance of hash function [closed]

I'm very new to cryptography and am having some issues with the following question ...
George's user avatar
  • 11
3 votes
0 answers
109 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 ...
Kristi's user avatar
  • 31
1 vote
0 answers
72 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 ...
CryptoGuru's user avatar
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, ...
vxek's user avatar
  • 413
2 votes
1 answer
205 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 ...
Thanos's user avatar
  • 183
2 votes
1 answer
100 views

How does the SWIFFT algorithm relate finding hash collisions to a lattice problem?

I've been messing around with lattice based cryptography and came across the SWIFFT algorithm, a provably secure cryptographic hash function which has a security proof stating that finding collisions ...
August H's user avatar
0 votes
0 answers
209 views

What hashing algorithm is fast and good enough for checking if source data is changed?

Not sure if this falls into crypto from contextual point of view but it is about hashing algorithms. I have two directories -- assets/ and cache/. Anytime there is a file added, deleted, or changed in ...
Gasim's user avatar
  • 113
1 vote
1 answer
734 views

Why is $\operatorname{Hash}(x \oplus y)$ not a secure proof-of-work algorithm?

$x$ is challenging string, $y$ is proof string. $\operatorname{H}$ is the proof-of-work (pow) function, to find a $y$ such that $H(x,y)<2^{256}/D$ $x ,y = \{ 0, 1 \}^{512}$ $\operatorname{H}(x,y) =...
user2383960's user avatar
1 vote
1 answer
275 views

Which hash functions provide 128 bit resistance?

I was wondering out of the functions (MD5, SHA-1, SHA-256, and SHA-512), do all provide 128-bit pre-image resistance and 128-bit second-image resistance? Also, out of these hash functions, do only SHA-...
CryptoGuru's user avatar
0 votes
1 answer
147 views

How to prove that a hash function is collision resistant if it's equal to that of a collision resistant hash function? [closed]

Given that H is a collision-resistant hash function from 2n-bit strings to n-bit strings. How do I prove that Hash is collision-resistant if: $$\text{Hash}(X_1∥X_2∥X_3) := \text{H}(X_1∥H(X_2∥X_3))$$
user avatar
0 votes
1 answer
245 views

Is sha-256 better then sha-1 in aspects othen then the hash size?

Assume I create a hash using SHA-256 and then take only the first 160 bits of the hash, as the result. is the result more cryptographically secured than SHA-1? Or are the two algorithms equally secure ...
Aviv Aviv's user avatar
  • 103
0 votes
1 answer
116 views

Security of 128-bit hash function with salt

Modern hash function have to be at least 256-bit, due to birthday attack. But let's consider 128-bit hash function which takes as an input: plaintext $\oplus$ salt Salt may be know to attacker. Do ...
Tom's user avatar
  • 1,181
0 votes
0 answers
97 views

Is there a special limit in the range of the hash function?

Is there a special limit in the range of the hash function? More specifically, is it possible that there is a cryptographic hash function that outputs c-membered subsets of the n-membered set? In ...
ali alizade's user avatar
1 vote
1 answer
71 views

Can a cryptographic hash function that outputs a c-membered subset of the n-membered set?

Is it possible that there is a cryptographic hash function that outputs a c-membered subset of the n-membered set? In other words, can the set of the binary representation of c-membered subsets of the ...
ali alizade's user avatar
3 votes
1 answer
86 views

Avoid hash flooding without a secret key?

I'm currently building an implementation of the dynamo paper, yottastore. Imagine it as a huge, distributed, hash map. To find the node holding a key, I use rendezvous hashing (an improvement over ...
Mascarpone's user avatar
1 vote
1 answer
71 views

How to complete this proof of statistically indistinguishable distributions?

Given that: $$ SD\bigg( (r, \langle r, s \rangle),(r, b) \bigg) < \mathrm{negl}(n)$$ where $SD$ stands for statistical distance, $r$ is random uniform in $\{0,1\}^n$, $s$ is random uniform in $S \...
Anon's user avatar
  • 383

1
2 3 4 5
15