Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
95 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
476 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
68 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
209 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
92 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 ...
1
vote
1answer
72 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
35 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
306 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}: \...
0
votes
0answers
62 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 ...
1
vote
0answers
42 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'(...
3
votes
2answers
103 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. ...
0
votes
0answers
16 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 ...
0
votes
0answers
34 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 ...
1
vote
1answer
81 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-...
4
votes
2answers
332 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
88 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 ...
1
vote
1answer
73 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
79 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 ...
0
votes
0answers
214 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 ...
5
votes
2answers
653 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
1answer
45 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
68 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 ...
7
votes
2answers
652 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
82 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
104 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
62 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
91 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
50 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
88 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. ...
1
vote
1answer
97 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
84 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
131 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&...
2
votes
1answer
286 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 ...
0
votes
0answers
26 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
vote
1answer
114 views

Example of a universal one-way hash function that is not collision resistant hash function

In collision-resistant hash function, first, a hash function is sampled and the adversary is allowed to pick a collision $(x, x')$ s.t. $H(x) = H(x')$ and $x \neq x'$. In a universal one-way hash ...
0
votes
0answers
90 views

Is truncated hash collision resistant if original hash is collision resistant?

Let's say I have a collision resistant hash function $H: \{0,1\}^* \rightarrow \{0,1\}^n$ and I want to create another collision resistant hash function $H': \{0,1\}^* \rightarrow \{0,1\}^n$ using $H$ ...
2
votes
1answer
129 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 ...
2
votes
1answer
49 views

PBKDF2-HMAC Collisions

Trying to understand the well known property of these collisions when used with SHA1, SHA256, etc. where a given key is larger than the block size of the digest function. In these cases the smaller of ...
0
votes
0answers
33 views

finding hash collisions for set of hashes

I am searching info on dependencies between different hash functions. Let's say that we have a set of x hashes H1, H2 ... Hn (using different hashing functions) of the same string S. For every hash we ...
1
vote
0answers
39 views

Changing a bit in IV of MD5

It is obvious that changing even one bit in data or IV (initialization vector) will change the hash value a lot. I want to know if, for example, changing a single bit within the $IV$ in MD5 can be ...
2
votes
1answer
76 views

How does randomized hashing defeat collision attack?

SEC#1 recommends randomized hashing when using SHA-1 with ECDSA; SPHINCS+ uses randomized hashing in WOTS+ to defeat collision attack so as to reduce signature size. How does a randomized hashing ...
1
vote
0answers
33 views

Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
2
votes
1answer
101 views

Is an HMAC based on a second-preimage resistant hash function always unforgeable?

If hash function is collision-resistant, then its associated HMAC is always unforgeable. But suppose that a hash function is only second-preimage resistant, not necessarily collision-resistant. Then ...
0
votes
1answer
161 views

A hash function that returns a value interpreted as integer

I am new in cryptography. I need to compute a hash of a string value represented as follows: $name||i$ where $i$ is an integer. I use the following pseudocode: ...
1
vote
1answer
179 views

Collision resistance of hash functions with short, fixed-length inputs?

Regular hash functions like SHA-256 have a variable length input and measure security against collision attacks in bits. For SHA-256 this is 128 bits. When I limit the input length of SHA-256 to for ...
0
votes
1answer
131 views

Hash function construction

I recently studied a Hash function and its security requirement. I have studied that simple hash construction from XOR is weak. My question is, based on Xor property the following Hash based on RSA Mi&...
0
votes
0answers
40 views

(key) Target Collision Resistance (kTCR)?

The enhanced Target Collision Resistance (eTCR) game implies that an adversary is allowed to choose a target message $M$. Upon choosing this target message, the attacker learns the function $\mathcal{...
3
votes
2answers
255 views

Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem

Problem statement: "Bob is a paranoid cryptographer who does not trust dedicated hash functions such as SHA1 and SHA-2. Bob decided to build his own hash function based on some ideas from number ...
1
vote
1answer
103 views

Is this SHA-256 modification still valid?

We typically model a hash function (in particular $\mathrm{SHA}$-$256$) as a function $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ with some special properties that makes them useful in practice. In this ...
0
votes
1answer
51 views

collision resistance with added permutation

Suppose we have an $n$ bit ciphertext $c$ protected by a $k$ bit $MAC$, with $k < n$. Generally, we expect collisions after $O(2^{k/2})$ ciphertext/MAC pairs are seen. Consider the following ...

1
2 3 4 5
12