Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
619 views

Calculating probability of finding collisions in an invertible hash function

Assuming we have an invertible hash function H that takes inputs of size 2n and outputs hashes of size n, I use the following algorithm to find collisions: Choose a random M as input. Compute its ...
5
votes
1answer
2k views

Why has the sponge construction's generic collision finding attack a complexity of O(min(2^(-n/2) , 2^(-c/2)))?

I'm trying to learn about sponge function for creating hash functions and generic attacks on it. I'm looking for the collision finding attack scenario which leads to $O(\min(2^{-n/2} , 2^{-c/2}))$ ...
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 ...
-1
votes
2answers
2k views

What is the probability of any two users generating the same 128, 256, 2048 bit key?

There are some protocols that require the user to generate some random key locally (client-side) with no server authority to "approve" or "reject" their key and are based on the assumption that it's ...
9
votes
3answers
914 views

What is the reason to separate domains in the internal hash algorithm of a merkle tree hash?

From rfc 6962 It is stated that: Note that the hash calculations for leaves and nodes differ. This domain separation is required to give second preimage resistance. That means that ...
13
votes
0answers
192 views

Space complexity of quantum collision search?

Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
7
votes
0answers
204 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 ...
14
votes
1answer
800 views

Overview of relations between cryptographic primitives?

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives? More specifically, I am looking for ...
0
votes
0answers
35 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
1answer
110 views

collision resistance of a composed hash function

Given a collision-resistant hash function $H(x)$, say SHA256, and I devise another hash function by $H'(x)=\sum^{m}_{1}H(x||i) \mod p$. The summation is defined on finite field of prime order $p$. ...
4
votes
1answer
290 views

How can I verifiably announce a choice without revealing its content?

Here is the simplified problem: Alice chooses from a small set of possible values. Bob guesses which value Alice picked. Alice reveals what value she picked. Alice's choice must stay secret ...
1
vote
2answers
960 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 ...
3
votes
1answer
289 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 ...
6
votes
2answers
874 views

Are tags longer than 128 bit possible for AES-256-CCM and AES-256-GCM?

I have an existing application that uses AES-256-CBC for encrypting data blocks, and HMAC-SHA-256 on the plaintext for eliminating duplicate data blocks. For performance reasons, I would like to move ...
4
votes
1answer
236 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
vote
2answers
84 views

How many hash collision will exist where the digest is a pre-image?

This question follows on from the question Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a? The question was answered but the issue of the number of ...
16
votes
1answer
3k views

If a hash function $H$ is collision resistant, is it true that $H(x)\neq H(x')$ for all messages $x, x'$ with $x \neq x'$?

I am puzzled with a question that seems to be based on theory. If there is a collision resistant hash function (since it is not possible for a hash function to be collision free, this is a ...
0
votes
1answer
1k views

Strongest collision resistance test?

An administrator is testing the collision resistance of different hashing algorithms. Which of the following is the strongest collision resistance test? A. Find two identical messages with different ...
0
votes
1answer
236 views

How does concatenating diverse hash functions affect collision resistance?

Let's suppose I take 3 different types of hash functions and concatenate them for future safety so that: digest = Hash3( Hash2( Hash1( text ))) Does the birthday attack mean in this case that I must ...
1
vote
2answers
610 views

Hash functions with variable and fixed length inputs

I was told that a hash function (mostly looking at the SHA-* family) should have input strings of variant length provided first, and those of fixed length after (ie salt), in order to avoid some kind ...
2
votes
1answer
345 views

Simple commitment scheme using secure hash function

Can I create a simple commitment scheme using a secure hash function? If so, is concatenation with a random secret enough to preserve hiding? (i.e. $C = H( random\_string || message)$) Thank you
1
vote
1answer
151 views

Is it possible to truncate AES output and keep uniqueness (no decryption needed)? [duplicate]

I would like to hash numbers less than 1000000000, so generally they could be stored on 30 bits. The aim is to obtain numbers that are not reversible, so my initial plan was to use SHA256 (with some ...
3
votes
1answer
133 views

Please explain me why we require $2^m$ & $2^{\frac{m}{2}}$ random messages

Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would ...
36
votes
3answers
7k views

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?

Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of ...
12
votes
2answers
19k views

SHA-256 “almost unique”?

I have seen numerous references on the internet of people describing SHA-256 as generating an "almost unique" hash. Exhibit A. there are more. Is there some mathematical basis to the almost ...
3
votes
1answer
992 views

Collision resistant hash function implies one-way function

I'm struggling to give a formal proof that $CRH \implies OWF$ using the definition below. Intuitively, I see why a $CRH$ would be "hard to predict" and might be used as a $PRF$, but I'm unable to ...
3
votes
1answer
93 views

Security issues with computing parallel hashes?

One issue with most hash algorithms like SHA-256 is that it is inherently serial. You can't effectively use SIMD to parallelize a single SHA-256 calculation. However, you can calculate multiple SHA-...
6
votes
2answers
346 views

Collision resistance of partial SHA-256 hashes XOR'ed

My hashing algorithm computes the SHA-256 for each of 12 input strings and XORs them to get the final hash. Is there a risk of an attacker being able to forge 2 sets of inputs that yield the same ...
1
vote
1answer
165 views

Is it safe to use fast/small hash for key identity?

I have to roll database access keys often, but it's important to know which key each system is using in order to avoid unavailability. I want the systems to report that without exposing the key itself,...
2
votes
0answers
62 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
17
votes
3answers
4k views

Can we assume that a hash function with high collision resistance also means a highly uniform distribution?

I want to use a hash function to generate a random sequence from number 0-n. And so I would like to find a good function that results in values that are seemingly random (does not need to be secure), ...
1
vote
1answer
99 views

Are Merkle Dags really Dags in most cases?

Let $H$ a cryptographic hash function of image length $n+1$ and $s_0$, $s_1$, ... , $s_k$ a finite sequence of bitstrings (length $>n+1$), such that $s_j$ contains a hash of $s_{j-1}$ for all $1\...
3
votes
1answer
895 views

Create a CR hash function where truncating one bit leads to collisions

I was reading Boneh and Shoups's A Graduate Course in Applied Cryptography, when I stumbled upon the following exercise (I have changed the array indices to start at 1 instead of 0): 8.1 (...
1
vote
1answer
176 views

Key-Bijective Secure Symmetric Encryption Methods

In AES, an N-bit message is mapped 1-to-1 message-to-output (for a fixed key). If we use a key with N bits, however, the key is not mapped 1-to-1 key-to-output (for a fixed message). So, is there any ...
2
votes
1answer
67 views

1 round Feistel with birthday attack

This is a reprise of an earlier question of mine, and I'm sorry if it's repetitious; I'm going at it with a different strategy. In an exercise I was given a 1-round Feistel network which uses $H(k \...
0
votes
0answers
75 views

Function F is not resistant to collisions

If we have the following block cipher, E(k,m), why is f(x,y) not collision resistant? $$f(x,y) = E(y,x) \oplus y$$
0
votes
1answer
104 views

Hashing functions - How to define them?

Let $\mathcal{G}$ be a cyclic additive group for an elliptic curve $E\, / \ \,\mathbb{F}_p$, and let $p, n$ be two large prime numbers (e.g., we can consider $\texttt{secp160r1}$ with $p = 160$ bit ...
2
votes
1answer
122 views

Cryptographic hash function based on logistic map?

Is there any secure cryptographic hash function based on the logistic map?
7
votes
1answer
414 views

Which TLS features are vulnerable to chosen-prefixes collision on SHA-1?

Gaëtan Leurent and Thomas Peyrin's preprint From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1 (in volume 1 of proceedings of the forthcoming Eurocrypt 2019) shows a feasible ...
2
votes
2answers
653 views

How can a hash function that implements random oracle model have collision resistance?

ROM is considered to be collision resistant. Does ROM assume there is an infinite set of outputs, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM ...
2
votes
2answers
397 views

Why do the non-leaf Nodes of Merkle tree need to be hashed?

Given the standard Merkle Tree as shown Wikipedia. I am having a hard time understanding why Hash(Hash(Leaf A)|| Hash(Leaf B)) at the parent of A and B is ...
0
votes
0answers
53 views

Collision resistance of a function which chooses the hash from a large table of hashes

Let's say you know a (possibly) large table of ids and some corresponsing hashes $h_{ID_j} = H(ID_j | secret_j)$. The resulting table looks like $$ ID_1 | h_{ID_1} $$ $$ ID_2 | h_{ID_2} $$ $$ ... $$ $...
0
votes
1answer
961 views

What is a fast good-uniformity hash function that if it's seed and it's hash values are unknown, can be strong as cryptographic hash functions?

The hash function is for an application that the input to the hash function is from a user's, hence the user can control the collisions, but the question is that if the collisions, the hash function's ...
1
vote
1answer
272 views

deterministic uuidv4 -> uuidv4

I need to copy a graph of elements with uuidv4s each, and separately stored relations containing element uuidv4s. On copy, I ...
1
vote
0answers
40 views

Round counts and permutation usage for hashing for a Merkle tree

Are there any current recommendations for performant hashing in a Merkle tree? It appears the hash based signatures in Sphincs use Blake2 everywhere (see Table 1 on page 22 of https://sphincs.cr.yp....
1
vote
1answer
354 views

hash collision chance using a 5 chars hash made of a-z A-Z and 0-9 (62 chars total)

What is the chance for collision or resistance of a hash made out of 5 chars randomly picked from this sets a-z A-Z and 0-9 (62 ...
2
votes
0answers
67 views

Application of High-level Mathematics to Hashing [closed]

Sorry if this post is a tad unconventional(it's also a reddit repost), but I was recently commissioned by a teacher to write a paper on the application of high-level math to a topic of our choice, and,...
1
vote
1answer
85 views

What are best known attacks for finding partial target pre-image?

Just a follow up on this question since I don't have enough point to comment: Does a partial preimage attack imply a preimage attack? Partial target preimage attack: Given $M$ and t-bit partial ...
1
vote
1answer
127 views

What does the〈 〉notation mean in this situation?

I was looking at solutions for a problem but I noticed it said $\langle2\rangle$ and was unsure of what that meant. From Homework 5 (PDF)

1 2 3
4
5
12