Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
8
votes
0answers
959 views

Does there exist a hash function which has a fixed point? [duplicate]

Does there exist a hash function $h$ and an input $x$ such that $h(x) = x$? I believe this is a special case of collision-resistance. I imagine such a case is guaranteed not to be possible (otherwise ...
0
votes
0answers
52 views

Is it something wrong in proof of Preservation of Collision Resistance for Merkle-Damgard?

I wonder about this proof. Can someone help me? I try to prove for Presevation of Collision Resistance for Merkle-Damgard as guide in end of this paper (Security Reductions of the Second Round SHA-3 ...
4
votes
2answers
1k views

Are My Answers to This Hash Question Correct?

Question When determining the security of a hash system, the cryptanalyst tries the following attacks. (a) If the attacker is NOT allowed to modify the original message, determine the number of hash ...
2
votes
1answer
62 views

Difficulty to find the pre-images of a pair of hash result such that given $a,b$, $H(x_1)=aH(x_2)+b$?

Suppose given fix values $a,b$, how difficult to find a pair of sha256 pre-images $x_1,x_2$ such that $H(x_2)=aH(x_1)+b$? How difficult to find 4 hash pre-images $x_1,x_2,x_3,x_4$ such that $\dfrac{H(...
2
votes
2answers
462 views

Finding collisions for XOR of many hashes

There's a collision-resistant hash function $H$. Given $x$, how hard would it be to find a set $a[i]$ such that: $H(a[1]) \oplus H(a[1]) \oplus \cdots \oplus H(a[N]) = H(x)$ whereas none of $a[i]$ ...
0
votes
1answer
36 views

does using an HMAC protect against hash table DoS attacks?

For a hash set where the values are supplied by a third party, one concern is that an attacker can run a denial of service attack by creating many values that all fall into one bucket of the hash ...
0
votes
0answers
29 views

Is Joux's multicollision attack applicable for truncated SHA256?

Joux presents an elegant way to generate k-way multi-collisions with about as much effort as generating a single collision: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf ...
0
votes
1answer
49 views

Hash function without avalanche effect but with few collisions

I am searching for a hash function which has these attributes: low Avalanche Effect, similiar files should get similiar outputs low number of collisions (if I have 0*10000 in one file, and 0*99999 + ...
0
votes
1answer
36 views

How to prove truncated MD (or chop MD) hash function is collision resistant?

We have a collision resistant hash function (based MD construction) H with 2n bits hash value size. Call chop(H) is a chopping n-bits from H's hash output. How can I prove a chop(H) is collision ...
0
votes
1answer
63 views

How to determine if a hash is pre image resistant or collision free

Let $H : \{0,1\}^*\to \{1,\dots, 2^{256}\}$ be a hash function. Let $p > 2^{256}$ be a safe prime, and $\alpha$ a primitive root for $p$. Define: $$H'(m) = H(m || m),\quad H''(m) = \alpha^{H(m)}\...
2
votes
1answer
64 views

Is there an increased risk of nonce reuse when using GCM with a nonce more than 96 bits?

GCM is designed to use a 96-bit nonce, which can be generated either randomly or deterministically. If you use a nonce that isn't 96 bits then it is padded and hashed with GHASH to create a ...
1
vote
1answer
52 views

Could multicollisions be used to mine large amounts of cryptocurrency?

I'm reading about hash functions at the moment, and in the book I'm reading there's a section on multicollisions. Specifically, using a 2-collision to find $2^N$ collisions in $N2^N$ time. If, ...
2
votes
0answers
18 views

How to find k-way second preimages

For example: Assuming someone has found a second preimage for SHA-256. In other words, for SHA256(M1)=H, someone has found M2 which SHA256(M2)=H Now, is it possible to generate k-way second ...
2
votes
3answers
129 views

How to derive a passphrase from a hash?

I'd like to generate a passphrase derived from a hash fingerprint. The passphrase consists of short and human-pronounceable words from a phonetically-distinct wordlist. The derivation is a one-way ...
1
vote
1answer
60 views

Birthday-paradox for big numbers and more than one person: Computing the approximate probability of $k$ hash collisions for $n$ hashes

Given a cryptographic hashing function, with say a $256$ bit-length, I want to calculate the probability that out of $n$ hashes we have at least $k$ hashes that collide in the first $32$-bit (...
0
votes
1answer
65 views

concerning collision-resistant hash function

Let H, H' be collision-resistant hash functions. Which of the following functions H'' is NOT necessarily collision-resistant? 1) H''(x) = H(H'(x)) 2) H''(x) = H(x)||H'(x), where || denotes ...
0
votes
0answers
17 views

Does every 256 bit number have a distinct sha256 result? [duplicate]

If I were some how able to create a table of all 256 bit inputs and outputs of sha256, would each of the inputs have a distinct output?
0
votes
0answers
38 views

How to create two partly similar plaintexts with same MD5 hash value?

The problem I'd like to solve looks like this: There are two plaintexts which differ in length and letters, but contain a few common strings. The first few words and the last few words are the same, ...
1
vote
1answer
76 views

If I concatenate two colliding SHA-256 messages with the same prefix and suffix, will the resulting hash output still collide with each other?

So let's say that there are two messages, $x_1$ and $x_2$, which hash to the same output. In other words, these two messages collide with each other: $$\operatorname{SHA256}(x_1)=\operatorname{SHA256}...
2
votes
1answer
125 views

For SHA3-512, SHA512, and Whirlpool, which algorithm has least probability for collision and preimage collision?

For comparing these 3 hash functions SHA3-512, SHA512, and Whirlpool. Which one is strongest against collision and preimage attacks. Are they fundamentally the same because of the same size output? ...
1
vote
3answers
172 views

Identifying identical files without reading them completely

Imagine the following situation: there are many "big" files (100Gb+) lying on 2 different remote servers you have no direct access to these files you can only read a small amount of each file (e.g. ...
0
votes
0answers
31 views

Finding a hash function that calculates average of an item in a stream of tuples

So, I have a stream of tuples coming in for example [country, state, person], where state and person are unique items. Now I have to find : 1. for each country, I have to estimate average number of ...
2
votes
2answers
87 views

Do hash collisions persist if a file is modified?

Suppose I use a relatively insecure hash algorithm to digitally sign a contract. Suppose also that creating a fraudulent contract with the same hash, a collision, is practical. As I understand, in ...
0
votes
0answers
46 views

Collision resistance

I have function with input 128 bit and output 64 bit that hash the header and hash the payload then concatenating them after that hash the result so my question is does this pass the collision ...
0
votes
0answers
15 views

Scrypt cipher - known vulnerabilities and cryptanalysis? [duplicate]

there is a Scrypt cipher which is used for exmaple by some cryptos like LItecoin for their mining algorithm. I never heared of scrypt. I know eg SHA256 which is well analyzed and considered as secure ...
7
votes
4answers
317 views

Can I replace SHA-1 with SHA-512/160 to address Shambles?

The destination is software (within a remote trust boundary) that expects SHA-1 results. Would it be safer for the source (that's within my own trust boundary) to replace my SHA-1 computation at my ...
16
votes
1answer
8k views

In 2020, SHA-1 practically broken in chosen-prefix collision (CP-collision). Can double SHA-1 hashing prevent CP-collision?

In a recent study SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust by Gaëtan Leurent and Thomas Peyrin. 2020, they showed the first practical chosen-...
3
votes
1answer
111 views

Can the confusion/diffusion of a hash algorithm be quantified?

I am wondering whether the confusion and diffusion are quantified in any way when we examine hashing algorithms and, if so, how they are quantified and what units (if any) are used to represent them.
5
votes
2answers
216 views

“One-Wayness” of SHA 1

I recently started learning about Hash Functions for my first time, and I've gone through and have tried to understand the SHA1 process. Brilliant does an excellent job of explaining it step by step. ...
6
votes
1answer
133 views

Do a 160-bit SHA-1 hash and a 160-bit slice of a SHA-256 hash have the same strength in terms of collision-free?

Take OpenPGP fingerprint for example. If the 40-digit hex standard remains unchanged, would it be helpful to upgrade SHA-1 to SHA-256 (but only taking the last 160 bits), in terms of reducing the risk ...
2
votes
2answers
251 views

Does stronger cryptographic hashes also imply being better at verifying integrity?

What I know so far Fact 1) I know that all cryptographic hash functions have the following properties They are many-to-one in nature They produce fixed size outputs Given an output ...
0
votes
0answers
104 views

Is md5(x) xor md4(x) collision proof?

Suppose I have the following hash function: $\newcommand{\md}[1]{\text{md#1}} \newcommand{\H}{\text{H}}$ $$\H(x, y) = \md{5}(x) \oplus \md{4}(y)$$ How can I prove it's collision proof? I tried to ...
1
vote
1answer
61 views

Any known cases of lucky collisions resulting in security breaches?

This isn't a deep technical question, but I feel like this is a good place to ask. Modern cryptography generally rely on statistical chances of collisions according to current computing powers. Are ...
4
votes
1answer
303 views

Is length extension attack considered as collision?

I came across a few articles about length extension attacks on cryptographic hash functions. I was very surprised to read that SHA-256 and SHA-512 are prone to length extension attacks. This seems ...
2
votes
1answer
83 views

Merkle–Damgård transformation example

I m looking at this Example of Merkle–Damgård I have a similar question about this topic. I have hash function maps 256b blocks into 128b blocks, how many rounds are required for hashing a 140KB ...
0
votes
0answers
45 views

Probability of collision of two HMACs with two random keys

Assume $k_1$ and $k_2$ are two $\lambda$ bit random number ($|k_1|=|k_2|=\lambda$), and HMAC generates $f(\lambda)$ bit tag. How much is the probability of their collision for an input message $m$? $...
8
votes
1answer
716 views

Security levels in NIST Post-quantum project: e.g. AES-128 vs SHA-256

In an article about NIST Post-quantum Standardization project I read about the security criteria of the proposed schemes and there was this table (Level I lowest security, level V highest): Level I: ...
0
votes
1answer
174 views

If multiple hashing algorithms are chained together, is the compound hash function more collision resistant? [duplicate]

The DASH cryptocurrency uses X11, which is a Proof of Work hashing algorithm composed of 11 separate hash functions which are run as a sequence. Example: $Digest = H_{11}...(H_3(H_2(H_1(Input))))$ ...
1
vote
1answer
68 views

Swapping a single bit inside a 40 bytes inputs fed to keccak256. Is it safe to assume no change in the first 20 bytes can result in the same hash?

I have the following data (represented as hex from binary below) where the lower bytes is controlled by attacker in the second case : ...
1
vote
2answers
95 views

For data shorter than 32 bytes, is it sure that no collision exists?

I’m not talking about if a collision can be found but even simply exists. The point is since it’s shorter than the length of the hash (since I’m talking about keccak256), normally there’s a hash ...
2
votes
2answers
83 views

Collision resistant functions - definition

Let $f$ be a collision resistant function i.e. it is computationally impossible to find $x_0, x_1$ such that $f(x_0) = f(x_1)$. If a computationally bounded adversary demonstrates that he knows some $...
12
votes
3answers
2k views

SHA3-255, one bit less

I need a SHA3-255 or 511. What if I simply truncate a standard SHA3-256 or 512? Apart from the doubled probability of hash collision, are there any other things I should be aware of? I could also ...
5
votes
0answers
93 views

Parameters for high density SIS

I am considering the SIS problem of finding $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}_q^{n\times m}$, $Ax=0$ and $\lVert x\rVert < \beta$ for some $p$-norm and bound $\beta < q$. ...
7
votes
0answers
144 views

Are there two known ASCII-only strings which have the same MD5 hash value?

Up to now, the pairs of strings that create an MD5 collision that have been discovered all contain non-ASCII (binary) characters. Are there two known ASCII-only strings which have the same MD5 hash ...
0
votes
0answers
33 views

Help, Feedback and Solutions to a problem on a PoC CSPRNG

Background I do not recommend trying to roll your own crypto. This is just a for-fun PoC, which won't be used in any public or private scenario. I am creating a PoC nearly-true random number ...
4
votes
2answers
2k views

Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3?

The traditional brute force collision attack is generate $2^{N/2}$ (unique) random strings, hash them and this results in ~50% chance for collision. The attack talked in the question's title is ...
1
vote
2answers
379 views

How to prove if a Hash Function is collision resistant

Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that ...
1
vote
1answer
122 views

What is the possibility of collision of trailing 160 bits of Keccak_256, for any two differing public-keys as pre-images?

Earlier today I was answering a question on the ethereum SE site that analyzed the potential for more than one private key on curve secp256k1 (which maps to a distinct public key) to control the same ...
5
votes
1answer
155 views

Hash multiset to point on elliptic curve where $A = 0$

I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that ...
3
votes
1answer
112 views

Is it feasible to find n hashes that sum up to a given hash?

Consider two sets $A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$; We can calculate the hash sum of those sets: $$HASHSUM(𝐴)=(ℎ𝑎𝑠ℎ(a_1)+ ℎ𝑎𝑠ℎ(𝑎_2)+\cdots +ℎ𝑎𝑠ℎ(𝑎_𝑛))$$ and $$HASHSUM(𝐵...

1
2 3 4 5
11