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

learn more… | top users | synonyms (1)

0
votes
1answer
47 views

Are these hash function compositions collision resistant?

If a hash function $H$ is collision resistant, are the following two hash functions collision resistant or not? ($||$ is concatenation) $H'(m) = H(H(m)) || H(m)$ $H''(m) = H(m) || H(m)$ My first ...
0
votes
1answer
23 views

Determining collision resistance of a function?

I am having trouble trying to understand if the function is collision resistant. As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the ...
1
vote
1answer
78 views

Why does a fixed key not make MACs like CBC-MAC or GMAC into secure hash functions? [duplicate]

Why does setting the secret key to a fixed, public value not make MACs like CBC-MAC or EMAC into secure unkeyed cryptographic hash functions? In other words, why is the resulting hash function not ...
3
votes
2answers
58 views

How to generate a random number so server cannot cheat?

Here is the protocol: Bunch of players connected to server. Server creates nonce and hashes it - send hash to clients as bit commitment. Clients make nonces and send hashes to server as their bit ...
2
votes
1answer
95 views

Block cipher not resistant to collisions

If we have the following block cipher, $E(k,m)$, which is a permutation, why is $f_2 (x,y)$ not collision resistant? $$f_2(x, y) = E(x, x \oplus y)$$
1
vote
2answers
60 views

Is there a standard for hashing a list of strings?

I'm working in Python, and my goal is to hash a list of strings with a cryptographic hash function such as sha256. It would need the property that a change in any string, or the order of the strings, ...
3
votes
2answers
74 views

Long passwords and Bcrypt

I need to store passwords for a web application, and was looking at Bcrypt for a possible solution. After some research, it appears only the first 72 bytes influence the final hash output. While it is ...
2
votes
0answers
31 views

Are collisions in AES-128 theoretically possible when the plaintext is the same? [duplicate]

Is it theoretically possible to find $P$, $K$, and $K^\prime$ such that $E_K(P) = E_{K^\prime}(P)$ where $E$ is AES-128 and $K \ne K^\prime$? I'd imagine this would be infeasible, but is it actually ...
0
votes
2answers
67 views

Discrete logarithm hash function Exercises

I have a problem with this exercise: Let $G$ be a group of order a prime $q$ and let $g, h$, be two randomly selected elements of $G$, with $g,h\ne 1$. Consider the following hash function on ...
4
votes
1answer
97 views

Could we share a secret key using the Birthday problem?

I stumbled upon this code on-line, it seems obvious to me that generating all 2^40 keys in trivial time can always be achieved as can hashing each and everyone of them, using the SHARED Salt that ...
3
votes
1answer
122 views

Is finding collisions in a part-hash not often enough a bad problem?

My situation: I've been working now for a couple of months on my own unique hash function, I've changed it many times and had two main versions but I won't bore anyone with the details of my work; at ...
2
votes
2answers
129 views

Collision free one way function

I was playing with a function that I think is collision free and uninvertible assuming the hardness of integer factorization. I am unfortunately not as skilled at math as I would like to be, and do ...
5
votes
1answer
46 views

Question about lower bound and upper bound key collision

I'm reading this article and I have a doubt in the page 7. First I going to describe the required definitions and next I formulate my question. Let be $$F(n)=\{f_k: \{0,1\}^n\rightarrow \{0,1\}^n| ...
2
votes
0answers
23 views

Why do we need Merkle–Damgård strengthening [duplicate]

Reading through some manuals, wikis and other documentation I'm learning about Merkle–Damgård construction. I understand why padding beginning with '1', followed by '0's is needed, but I can't ...
2
votes
1answer
94 views

Would SHA-1 be safe for certificates with short validity?

There are articles floating around the topic of SHA-1 deprecation. The gist of it is that in (mostly) developing countries, people are still using mobile/computing devices that are 5 years old (or ...
1
vote
1answer
32 views

bcrypt collision probabilities assuming same password and work factor?

What is the likelihood of 2 bcrypt hashes colliding if they use the same work-factor and input? Are bcrypt's salts large enough to prevent this from happening?
0
votes
1answer
137 views

Why Merkle Tree doesn't suffer Birthday attack?

I am trying to understand why Merkle Tree doesn't suffer the birthday attack? Can you help me? Thank you!
2
votes
2answers
67 views

Probability approximation of no collisions

I am comparing the actual probability of no collisions to the probability approximation formula of no collisions from the Understanding Cryptography text. The approximation is as follows: ...
1
vote
1answer
47 views

Finding collisions for the DES F-function

It's known that for a given subkey, the F-function of the DES is not injective (see Is the DES F-function injective for a given subkey?). I am interested in efficiently finding collisions for this ...
1
vote
1answer
46 views

Rogue CA Certificate MD5 Collision Control

Papers from Marc Stevens et al show that X509 certificates that rely on MD5 signatures can break the assumed security model, that is, it allows for a forged certificate to have the same signature as a ...
3
votes
1answer
54 views

Memory hardness of key derivation function through XOR-ring multiple matrix values

For theoretical purposes in order to enhance my own understanding, and NOT in order to create my own cryptography, I am asking a question about the memory-hardness of a key derivation function ...
1
vote
1answer
62 views

Taking half of a X bits hash key as secure as using a X/2 bit hash function?

This question comes from a (nitpicking) comment by me in this SO question. I said that using the half of the output from a 256 bit hash function is worse than using a 128 bit hash function. My ...
1
vote
1answer
93 views

Proving collision resistance of a hash function?

Let $f$, $g$, and $h$ be hash functions that each map binary strings of length $2n$ to binary strings of length $n$. Suppose that $h(x) = f(g(x)||g(x))$. Prove that if $f$ and $g$ are collision ...
1
vote
0answers
54 views

If a PRG is constructed by iterating a PRF, is it backtracking-resistant?

Say we construct a pseudo-random number generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back ...
2
votes
2answers
60 views

Easy hash function collision

I'm designing a cryptography-breaking assignment for a college-level introductory security course, and I'm looking for a hash function which is reasonably easy (but not too easy) to generate ...
3
votes
3answers
826 views

For any hash value, is there an infinite number of inputs that hash to it?

Bruce Schneier writes (back in 2005) in a post on cryptanalysis of SHA-1: SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an ...
0
votes
1answer
149 views

Testing hash functions for collision resistance

I was hoping to implement a software that allows testing a user-defined hash function for cryptographic properties (Meant to pique interest in cryptographic hash function for a school showcase), as ...
4
votes
1answer
99 views

Effect of message length on collision attacks

I know that message collisions are supposed to be hard to calculate for a good cryptographic hash. Given 1k worth of data, it's hard to find another 1k worth of data that collides with the same hash. ...
3
votes
1answer
66 views

What is the complexity of finding SHA-1 collisions?

Given the recent news about SHA-1 collisions, what is the complexity of finding a SHA-1 collision? Marc Steven's HashClash is still detailing about 260. Does the previous complexity still hold?
1
vote
2answers
94 views

How does perfect hash function works?

According to wikipedia, a perfect hash function is a hash function that uses algorithms that has a certain random aspect to their logic. It is suppose to be collision-free. However due to the pigeon ...
34
votes
1answer
3k views

What is a “freestart collision”?

In their work on SHA-1 collisions (cf. the currently unpublished paper “Freestart collision on full SHA-1” by Stevens, Karpman, and Peyrin) Stevens et al show that they are able to generate "freestart ...
0
votes
0answers
56 views

MD5 SSL Collision Attack

I want to create fake certificate for test purposes. I have read about the http://marc-stevens.nl/p/hashclash/index.php project but I am unable to understand the two files that I have to put as input ...
3
votes
0answers
112 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
117 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 ...
0
votes
3answers
74 views

Perfect hash function

Is a perfect hash function always bijective ? In Wiki "In mathematical terms, it is a total injective function" but it does not mean, that it is bijective.
0
votes
2answers
69 views

hash functions preimage and second collision resistance [duplicate]

A hash function H is secure in terms of pre-image resis-tance. Does this imply that H has second pre-image (aka weak collision) resistance?
3
votes
0answers
49 views

Combining md5 collisions to create more collisions

Given X1 and X2 such that md5(X1) = md5(X2) and Y1 and Y2 such that md5(Y1) = md5(Y2), and knowing the following property of md5: if md5(a) = md5(b), md5(a|s) = md5(b|s) is there a way to find ...
0
votes
2answers
118 views

If I compute the SHA-1 of all possible 40 digits hexadecimal strings, will I get all possible sha1 hashes? [duplicate]

Wikipedia says sha1 produces a 160-bit (20-byte) hash value. So if I compute the SHA-1 of all possible SHA-1 values, which as far as I understand is at current time impossible both to calculate and ...
2
votes
0answers
81 views

Bobcat hash, trying to find a 48-bit hash collision for x

I am trying to find a collision with the Bobcat hash of the 48-bit hash. I am a beginner coder so please point out any flaws in my modification of the bobcat program. It does find a truncated 12-bit ...
7
votes
3answers
271 views

What was the first MD5 collision ever constructed?

We all know that MD5's collision resistance is severly broken. But when thinking of "random" strings with great cryptographic importance I've come up with NIST's curve seeds and MD5 collisions. But ...
2
votes
0answers
88 views

Is there a way to slow down collision attacks using iteration?

The simple way to iterate a hash function $H(H(m))$ only makes brute force preimage finding slower, but leaves collision attacks as fast since a collision in the inner hash function is a collision in ...
0
votes
1answer
117 views

1024 RSA Hash Signature attack. Forge a valid signature

I have an RSA signature of 1024 bit where i know the following: Public modulus N Public exponent (0x03) Cypher message Summary: An MD5 hash is calculated from a collection of byte and is used as ...
5
votes
1answer
240 views

Can iterated hashing be used to mitigate collision and preimage weaknesses?

How much security does double hashing add regarding collisions and preimages? Is it helpful to iterate a hash function even more times than two? For example, can MD5 be fixed (in practice) by ...
2
votes
1answer
96 views

Why the $IV$ used in Merkle-Damgard has to be fixed to a specific value?

I just can't figure out why on earth the $IV$ in Merkle-Damgard has to be fixed (that's what the Katz-Lindell book says)? Because even if you choose it randomly from say $\{{0,1}\}^n$ then the ...
0
votes
0answers
69 views

For each of the following modifications to the Merkle-Damgard transform, determine whether the result is collision resistant or not

$(a)$ Modify the construction so that the input length is not included at all (i.e., output $z_B$ and not $z_{B+1}=h^s(z_B||L)$). $(b)$ Modify the construction so that instead of outputting ...
1
vote
2answers
115 views

How to formally prove that a given hash construction is collision resistant or not?

Is there a precise procedure or strategy to follow in order to prove in a formal way the (not) collision-resistance of a certain given hash construction? I.e. let $H_1$ and $H_2$ be two hash ...
0
votes
0answers
63 views

How can I calculate the probability of collisions of a hashing algorithm?

I'm pulling a “Dave” and I'm designing my own hashing algorithm. Not that I intend to use it, I'm not certifiable or anything, I just want the challenge of creating something. I'm not going to get ...
4
votes
1answer
217 views

Formula for the number of expected collisions

Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision. Say instead that ...
5
votes
1answer
105 views

Keys in HMAC and NMAC

I'm quite new to this topic and have several questions concerning HMAC and NMAC: Why does NMAC need two keys? How can it be attacked if we just used some sort of initialization vector instead of the ...
1
vote
2answers
71 views

Collision probability of MD5 over different attacks

I am researching the collision probability of MD5 and various attacks against it. Can someone help me how to learn the least probability that there will be a collision in a specific attack on MD5? ...