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
72 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
968 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
591 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
280 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
702 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
108 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
113 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
97 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
55 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
91 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
191 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
108 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
89 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
136 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
36k 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
289 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
157 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
32 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
144 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
97 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
113 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 ...
1
vote
1answer
234 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 ...
2
votes
1answer
78 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
36 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
40 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
79 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
37 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 ...
151
votes
6answers
97k views

Why can't we reverse hashes?

First off, I know hashes are 1 way. There are an infinite number of inputs that can result in the same hash output. Why can't we take a hash and convert it to an equivalent string that can be hashed ...
0
votes
1answer
205 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: ...
5
votes
2answers
301 views

How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?

Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that $$h(a)\oplus h(b)=h(c) \text?$$
0
votes
1answer
136 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&...
3
votes
1answer
177 views

Do hash functions for digital signatures need to be preimage resistant?

I understand that hash functions used for hashing a document or some data before signing it, needs to be collision resistant and 2nd pre-image resistance. Otherwise an adversary could "look" ...
3
votes
2answers
297 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 ...
0
votes
0answers
42 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{...
1
vote
1answer
108 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 ...
53
votes
11answers
20k views

How do hashes really ensure uniqueness?

This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup. So hashes are said ...
0
votes
1answer
52 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
vote
1answer
145 views

Avoiding collisions by combining MD5 and SHA-2

It is often suggested that hashing of long character columns can be used for indexing in databases, but the possibility of collisions is an issue for Unique indexes. Whilst I know that both MD5 and ...
1
vote
1answer
73 views

Using first, say, 50 letters from a public key as user identifier?

I am making a messaging system where users are identified by their public keys. It doesn't matter which friendly username they have, so I'm not going to prompt them to choose one. Each user will ...
1
vote
1answer
96 views

HMAC SHA256 - fixed vs dynamic key - security and collision impacts

Assume we should apply an hmac sha256 on different messages made of incremental numbers (Ex. 1 to 1 billion). Does it make sense in terms of security to apply a different fixed key for each message? ...
3
votes
1answer
116 views

With AES encryption and a known key and plaintext, can an attacker create a different key and plaintext resulting in the same ciphertext?

In short: with AES encryption can an attacker create a new key2 and plaintext2 so that AESkey1(plaintext1) = AESkey2(plaintext2) If so, can it be solved by just applying for instance a MAC like AES-...
6
votes
2answers
3k views

Why might SHA-384 throughput be lower than SHA-512 throughput in hashcat and more secure?

I found a hashcat benchmark results in the internet: hashcat results: SHA-384 is 17065.4 MH/s SHA-512 is 17280.3 MH/s Why does SHA-512 take less time? SHA-512 is longer and I thought it therefore ...
0
votes
0answers
131 views

Probability of collision when we use a particular part of sha 256 hashed value

So I was supposed to use hash some co-ordinates and I was supposed to use k 3-wise independent hash functions in order for the mathematical explanations behind that algorithm to be hold. But after ...
6
votes
2answers
15k views

Computational requirements for breaking SHA-256?

Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function): preimage attacks to get $m$ knowing $H(m)$ second-preimage ...
4
votes
1answer
654 views

Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant?

I'm trying to solve the following problem: Given two CRHF $H_1:2^{4n}\to2^{2n}$, $H_2:2^{2n}\to 2^n$, construct the following hash function $H^{*}=H_2(H_1(x))$ compressing from $2^{4n}\to 2^n$. We ...
5
votes
1answer
2k views

MD5 - Chosen Prefix Collision Attack

Given 2 messages $m_1$ and $m_2$, in a chosen prefix attack, we want to find $s_1$ and $s_2$ such that: $\text{MD5}(m_1 || s_1) = \text{MD5}(m_2 || s_2)$ Are $s_1$ and $s_2$ found by brute force ...
1
vote
1answer
172 views

Subset Sum Hashes

This link discusses something called a 'subset-sum hash function'. I'm having a little difficulty understanding the algorithm, and I can't seem to find any existing implementations to reference. Could ...
3
votes
1answer
51 views

How can a collision attack using MD5 be used to break WOTS

It is stated in Winternitz One time signature security that MD5 is not safe for Winternitz due to collision attack. Given that WOTS generates multiple, say 32 private keys then hashing them a number ...
8
votes
0answers
970 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 ...

1
2
3 4 5
12