Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
45 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 ...
0 votes
1 answer
69 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
129 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 ...
  • 115
1 vote
0 answers
38 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 ...
  • 115
2 votes
1 answer
89 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 ...
  • 143
1 vote
1 answer
33 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
62 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 \...
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 ...
  • 963
2 votes
1 answer
82 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
59 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 ...
  • 93
1 vote
0 answers
27 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
43 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
71 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 ...
  • 425
1 vote
1 answer
121 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
478 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 ...
2 votes
1 answer
56 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. ...
  • 183
1 vote
1 answer
200 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 ...
0 votes
1 answer
142 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
107 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
162 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" ...
0 votes
1 answer
35 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
214 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,365
1 vote
1 answer
99 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
78 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
81 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
108 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
104 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
70 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 ...
0 votes
0 answers
32 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, ...
  • 413
2 votes
1 answer
171 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
2 votes
1 answer
69 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 ...
0 votes
0 answers
132 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 ...
  • 113
1 vote
1 answer
139 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) =...
1 vote
1 answer
250 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-...
0 votes
1 answer
141 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
148 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 ...
  • 103
0 votes
1 answer
100 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 ...
  • 1,171
0 votes
0 answers
89 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 ...
1 vote
1 answer
64 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 ...
3 votes
1 answer
80 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 ...
1 vote
1 answer
65 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 \...
  • 321
0 votes
0 answers
38 views

Assumptions used for Designing Homomorphic CRHF

What are the possible assumptions that have been used or can be used for designing the homomorphic Collision Resistant Hash function (CRHF)? I know Short Integer Solution (SIS) is one of the ...
0 votes
1 answer
67 views

Double hashing scheme on not collision resistant hash

Given an hash H that is not collision resistant, for example 80-bit digest, if we use the following double hashing scheme: H(SHA2-256(x)). Does this scheme increase the collision resistance?
  • 1
1 vote
0 answers
28 views

Does a salt by a trusted party remove the need for collision resistance for a binding commitment?

Say a Human is operating their trusted computer, Alice, and Human wants to hand copy a collision resistant commitment, with a security factor of 128 from Bob on to paper. Naturally we want the ...
  • 488
1 vote
1 answer
143 views

Does RIPEMD-320 provides the same level of security as RIPEMD-160?

This article from Wikipedia claims that "256- and 320-bit versions of RIPEMD provide the same level of security as RIPEMD-128 and RIPEMD-160, respectively". Is that true or false ? And why ?
  • 57
0 votes
4 answers
612 views

Is 32 bytes enough for a hash and would anything else be 'overengineering'?

For data integrity, specifically for small blocks of data, rather than using a SHA-256 hash, or simply truncating a SHA-512 hash, I am playing with the following idea: ...
1 vote
0 answers
56 views

Compute a hash function given commitment to some secret element

Given a secret key x and a commitment to it comm(x) where comm(x) is both binding and hiding (it can be for example $g^x$ or some homomorphic encryption). Given public parameters $P_1,...,P_k$, comm(x)...
  • 79
0 votes
0 answers
106 views

Determine if a Hash function is pre-image resistant and collision free

I'm so confused by this kind of exercise. We have that $n = p * q$, where $p$ and $q$ are prime numbers. Let's examine this hash function: $h(x) = x^2 \mod n$. Determine if the hash function is pre-...
0 votes
0 answers
69 views

Can we combine two AES (with block size 128) to to a block cipher with a block size 192 which is collision-resistant?

Encrypting values with AES we only need about $2^{64}$ trials until we finding an already used value (some collision). This can be done these days with easy. To make this harder can we combine two AES ...
  • 505
0 votes
1 answer
67 views

Proof of computationally binding correct?

I have defined the following commitment scheme and would like to prove that it is statistically hiding and computationally binding, but I'm not sure if my proof is accurate: For $h$, a collision ...
  • 321

1
2 3 4 5
14