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
3
votes
2answers
273 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
106 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
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
135 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
69 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
88 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
161 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
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-...
0
votes
0answers
128 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 ...
1
vote
1answer
149 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
48 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
969 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
68 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
63 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
639 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]$ ...
1
vote
1answer
90 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
49 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
95 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
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 ...
0
votes
1answer
120 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)}\...
3
votes
1answer
108 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
73 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
22 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
174 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
84 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
253 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
77 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
156 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
749 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
333 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
34 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
102 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
50 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
16 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
369 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
11k 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
169 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
258 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
226 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
287 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
131 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
64 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
441 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
237 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 ...
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 ...
8
votes
1answer
1k 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
333 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
86 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
167 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 ...

1
2
3 4 5
12