People who code: we want your input. Take the Survey

Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
0
votes
2answers
757 views

Can SHA512 and SHA3-512 Make Same Collisions?

Does combining those two different cryptographic hash functions in HMAC, when each hashes the same data separately, then saved together, guarantee zero possibily of a collision simultaneously or is ...
0
votes
1answer
80 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 ...
1
vote
1answer
33 views

Breaking merkle damgård construction that uses bitwise and?

I'm preparing for a exam in crypto course, and i'm doing some practice problems. I'm now playing with this problem: ...
0
votes
2answers
39 views

Shake256 Infinity Collision

Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?
1
vote
1answer
107 views

Example of a Hash function which is second pre-image resistant but not collision resistant [duplicate]

We know that a collision resistant hash function is also second pre-image resistant. But the converse is not necessarily true. I am looking for the example of a hash function which is second pre-image ...
8
votes
3answers
491 views

What is this AES SBOX triplet property?

While playing around with the AES SBOX, I found out that there are 85 unordered triplets (a, b, c) that have the following characteristics: ...
1
vote
1answer
106 views

Are SHA-256 and SHA-512 collision resistant?

This is my first post on this forum, apologies if this post is naive. I want to learn cryptography and I want to start with this question. Context: Designing a TinyUrl system. The user inputs a ...
3
votes
2answers
220 views

Use slow hashing to reduce digest size?

I have seen this question on MD5 replacement for 128 bit digests. It is said numerous times that having a 128 bit digest is impossible today because finding a collision would only require $2^{64}$ ...
1
vote
3answers
108 views

Using date stamp down to milliseconds / ticks as a salt?

As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash. The salt is often stored with the hash, either prepended or as a separate field. As ...
31
votes
2answers
19k views

How secure is SHA1? What are the chances of a real exploit?

I read that, in February 2017, a SHA1 collision was calculated for the first time. This, and earlier theoretical proof, means that SHA1 is officially cryptographicaly insecure. But, when using SHA1 in ...
1
vote
1answer
77 views

Depth of the SHA-256 collision search knowing partial input and final hashes

So I have a partial input data (string) PART1+UNKNOWN+PART2, length of UNKNOWN is self-describing. I have a bunch of valid ...
0
votes
1answer
37 views

Finding multiple smaller collisions equal work as finding a bigger collision?

Problem A: I receive two hash digests $H(x), H(y)$ and the corresponding preimages $(x, y)$. $H$ is a 128-bit cryptographic hash function: $H: \{0,1\}^{*} \longrightarrow \{0, 1\}^{128}$ I need to ...
1
vote
3answers
316 views

Is collision resistant hash enough for one-block counter mode?

Let $H:\{0,1\}^*\rightarrow \{0,1\}^\ell$ be a collision resistant hash function (CRH), and let $\Pi = (\mathsf{enc,dec})$ be an encryption scheme with the following properties: $\Pi.\mathsf{enc}: \...
15
votes
7answers
3k views

Is it theoretically possible to construct a string that contains its own hash value?

After saw the xkcd comic Self-Description, I wonder if it is theoretically possible to construct a self-descriptive string that contains its own hash value? Let's say the string's MD5 value is ...
1
vote
1answer
88 views

HKDF Bit Security

I've always understood the bit security of hash functions to be related to their output size (eg. collision resistance). However, I recently came across a table from a Wickr blog post that lists HKDF-...
6
votes
2answers
556 views

Partial collisions of hashes, why is this important?

There's a lot of work finding "partial collisions" in hashes, and "Parallel Collision Search with Cryptanalytic Applications" seems to be the go-to paper for this work. I'm trying to understand why ...
0
votes
0answers
74 views

Hash Function that is Collision Resistant but not Puzzle Friendly

Is there any example of a Hash function that is collision-resistant but may not be puzzle-friendly, similarly example of a hash function that is puzzle-friendly but not collision-resistant? Puzzle ...
3
votes
2answers
111 views

How many different keys can be derived with HKDF before two outputs are identical?

How many different keys can be derived with HKDF before two outputs are identical? This question is about collision resistance, not about generating different keys with different parameters (eg. ...
1
vote
0answers
46 views

Are the hash functions collosion resistant or not? [closed]

If H is collision resistant then the following are collision resistant or not? H'(x) = H(x) || H(x) H'(x) = 1 || H(x) My thoughts: I am confused in question 1. In case of different hash function(H'(...
5
votes
1answer
793 views

Is there a feasible preimage attack for any hash function (no matter how deprecated) today?

Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack? All hashes that are nowadays considered 'broken' (...
0
votes
0answers
19 views

Public Key Fingerprint: Preimage Resistance

In my system, “resources” are granted operational certificates signed by a particular CA. Each resource has a unique public/private key pair that it generates once. The operational cert granted by the ...
6
votes
2answers
560 views

Parallel Rho Hash Collisions

I've been having a hard time placing DJB's analysis of Oorschot & Wiener parallel rho collision search into context. There is plenty of discussion about the birthday bound and quantum computers ...
0
votes
0answers
36 views

Authentication tag length and post-quantum security

The recommended hash length for post-quantum security seems to be either 384-bits or 512-bits. 512-bits gives 256-bit collision resistance, and 256-bit security is obviously ideal for post-quantum ...
4
votes
2answers
339 views

What are the differences between a UHF (as used in cryptography) and a cryptographic hash function?

After reading about UHFs from different sources (From Algorithm books to Crypto books), I am still thoroughly confused about them. How is a UHF different from other cryptographically secure hashing ...
4
votes
1answer
103 views

Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken?

As we know, MD5 and SHA1 (to some extent) are broken, and older algorithms like SHA0 or MD4 and MD2 are very broken. Does this also imply that the corresponding HMACs are also broken? Obviously nobody ...
9
votes
3answers
2k views

Are there MD5 collisions for inputs of different length?

There are many examples of MD5 collisions (some of them can be found here Are there two known strings which have the same MD5 hash value?). But as far as I know two inputs should have the same length ...
1
vote
1answer
80 views

Why this function isn't preimage resistant?

Prove that the function $$ G(z) = \mathcal{H}(z) \, || \, \text{LSB}(z) $$ (where $\mathcal{H}$ is a collision resistant hash function, $||$ is concatenation and $\text{LBS}$ is the least significant ...
0
votes
1answer
82 views

is there any hash collision attack that is not defeated by adding a salt first?

In the references I've read, all the uses of "collision attacks", whether classical collision attack or chosen-prefix collision attack, goes like this: "Alice creates a 'good' document ...
5
votes
2answers
665 views

Extending the size of input for SHA-2 function

In the question Does a hash function necessarily need to allow arbitrary length input? many answers talk about the theoretical limit of the SHA-2 functions being $2^{64} - 1$ bit due to padding. I was ...
0
votes
0answers
232 views

Create a MD5 collision on two given files with an identical prefix

I'm stuck on an assignment of mine and maybe someone has some advice for me. I have the following task: I have to modify two files, which differ in exactly one byte, so that they have the same MD5 ...
0
votes
1answer
47 views

Will repeatedly applying a hash function to the prior result visit all possible hashes? [duplicate]

If one were to take a message, say "Hello world!", and compute the MD5 hash: 86fb269d190d2c85f6e0468ceca42a20 Then, taking the MD5 hash of this, and repeating that procedure: ...
4
votes
0answers
71 views

Challenging $O(2^{n/2})$ for hash collisions using quantum computers

In "Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound" the authors Akinori Hosoyamada and Yu Sasaki state that it may ...
11
votes
1answer
956 views

Collision resistance of hash function built on modular exponentiation

Consider the following hash function family for hashing integers: $Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$. $H_{(n,y)}(x) = y^x \...
6
votes
3answers
581 views

How to prove that finding a cycle in a cryptographic hash function is hard?

I want to show that finding cycles in a cryptographic hash function is hard. My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial ...
4
votes
1answer
277 views

What is perfect collision-resistence in probability terms?

update: removed lots of stupidity... sorry. I didn't know I can be this stupid but I achieved it. 1. Goal Let $\mathcal{D}$ be the universal space of our plain data. Our goal is to find a function $...
7
votes
2answers
684 views

What are other good attack examples that use the hash collision?

When we consider the security of a cryptographic hash function with $n$ bit output we simply say that it must have at least $\mathcal{O}(2^{n/2})$-time security against the (generic) collision attack ...
0
votes
2answers
94 views

Bits of security vs collision resistance?

I have been doing some research on security, and I am confused on the bits of security vs collision resistance, and I was wondering if someone could clarify my understanding. For instance, if you have ...
3
votes
2answers
112 views

Application of cryptographic hash functions which do not require collision resistance property

I can not understand why collision resistance of a cryptographic hash function is not required for some applications. for example, if we store the trusted hash of a file or program, and later when we ...
2
votes
1answer
65 views

What are the “costs” to find a pre-image, weak collision, or strong collision?

For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?
1
vote
0answers
96 views

Is this modification in Merkle-Damgård collision-resistant?

We modify Merkle-Damgård construction by setting $z_0:=L$ (the length of the message), computing $z_i:=h(z_{i-1}||x_i)$ for $i=1,...,B$ and defining $H(x):=z_B.$ Is this construction collision-...
0
votes
1answer
54 views

Time and Space complexity of MiniAES

I am currently doing my masters research on security of wireless sensor networks, the topic is "ENHANCING THE SECURITY OF WIRLESS SENSOR NETWORKS BY COMBINING GEOENCRYPTION AND LIGHT WEIGHT ...
-2
votes
1answer
90 views

How much brute forcing efforts needed to find 2 or more inputs that generating same SHA256 outputs

Say I have SHA256 hash result that produced from 2000 bits inputs. For example, 0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef (64 bit hex representation) is the SHA256 output. ...
3
votes
1answer
189 views

How secure is a hash based signature scheme after signing assuming quantum computers?

Consider a hash based signature scheme that requires taking the $k$-bit hash of an arbitrary length message to be signed (e.g. Lamport one-time signature scheme). My understanding is, assuming that ...
1
vote
1answer
104 views

Examine whether a hash function is collision-resistant

Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$: $$ h_1(...
0
votes
0answers
86 views

How a collision for a function can be for another one

We have two bit strings $x\in\{0,1\}^q$ , $y\in\{0,1\}^w$ of length $q$ bits, and $w$ bits. The notation $x\mathbin\|y$ means $(q+w)$ bits long concatenation, And the functions: $H∶\ \{0,1\}^* \to \{...
0
votes
0answers
134 views

Does this qualify as a one-way function?

First, we observe that the expression X*Y mod P (where X and Y are secret and P is a large public prime) reveals no useful information. Next we define an extending function E(U, M) which "somehow&...
23
votes
2answers
35k views

Is there a hash function which has no collisions?

Is there a hash function which has no collisions? To clarify: it would be some function which would produce variable-length output, and never produce the same output for differing input. It would ...
2
votes
1answer
288 views

Practicality of a certain hash function

Consider the following hash function: $$(V\cdot A + V\cdot B)^2 \bmod C$$ $A, B,$ and $C$ are large primes. $V$ is the value to be hashed and is guaranteed to contain at least as many bits as the ...
2
votes
1answer
142 views

Dan Boneh's explanation of why Davies-Meyer requires the final step of XOR with the previous Hash

This is from this video https://www.coursera.org/learn/crypto/lecture/XZt5V/constructing-compression-functions At 2:44, Dan Boneh explains why the XOR is required. This is his explanation m - message ...
0
votes
0answers
28 views

Extractability of random oracle in simulation-based proof

I am working on the simulation-based proof, where Random Oracle (RO) is used to extract malicious parties' input. In particular, the RO considered in the proof has a small range (whose size is ...

1
2 3 4 5
12