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

learn more… | top users | synonyms (1)

1
vote
0answers
25 views

Combining secure hashes with insecure hashes?

Assuming I'm a bank which seeks for secure hash functions to use in the process of signing on digital contents. I'd like to explain / prove why using each one of the following hash functions might ...
19
votes
2answers
10k views

Are there any known collisions for the SHA (1 & 2) family of hash functions?

Are there any known collisions for the hash functions SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512? By that, I mean are there known values of $a$ and $b$ where $F(a) = F(b)$ and $a ≠ b$?
5
votes
3answers
1k views

Is the number of creatable torrents limited?

Currently, a magnet link containing a 40-digits long SHA-hash value, is assigned to every torrent which is created. Therefore, this hash should be unique to identify a torrent and send the right bytes ...
17
votes
7answers
4k views

Is calculating a hash code for a large file in parallel less secure than doing it sequentially?

I would like to improve the performance of hashing large files, say for example in the tens of gigabytes in size. Normally, you sequentially hash the bytes of the files using a hash function (say, ...
9
votes
1answer
1k views

Change in probability of collision when removing digits from MD5 hexadecimal hash values

I am aware that MD5 has a known collision vulnerability and should not be relied upon when uniqueness is required, but in the environment I am working on I only have access to MD5 hash function. ...
3
votes
0answers
41 views

Can the attack in https://eprint.iacr.org/2008/469.pdf be parallelized?

Can this attack be parallelized? It is a $2^{57}$ complexity collision attack on SHA-1 based on disturbance vectors. If it is practical it is easy on a GPU ($\approx1.1$ GPU-days). If it is ...
40
votes
1answer
4k views

What is a “freestart collision”?

In their work on SHA-1 collisions (cf. the EUROCRYPT-2016 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
1answer
86 views

Is it possible to brute-force a hash algorithm of 32 bits

I have a 30000 user passwords and usernames stored in a table on a database in which the passwords are stored as hash where ,I need to guess the passwords for all users and I have the hash function ...
38
votes
7answers
35k views

Are there two known strings which have the same MD5 hash value?

Is there an example of two known strings which have the same MD5 hash value (representing a so-called "MD5 collision")?
-1
votes
0answers
6 views

Effective ways to find partial sha1 collision [migrated]

I need to find 2 different string and compare their hash value. Both string must contain "abc". I looking for the first eight character that are the same and stop. I have been running for more than 24 ...
1
vote
1answer
55 views

Safe MD5 digest

So I've heard that MD5 is broken because it's possible to engineer collisions. So instead we should use, say, SHA256. The problem which SHA256 digests is that they are long. So I've come up with this: ...
2
votes
1answer
54 views

How to find collisions in a hash function knowing its coefficent?

Say I have a simple hash function where $x$ is a sequence of integers: $$h(x)=(a_1\cdot x_1+...+ a_n\cdot x_n) \bmod N=\sum_i a_i\cdot x_i \bmod N$$ where $a_1,a_2,a_3,...,a_n$ is the coefficient ...
2
votes
1answer
58 views

SipHash's (non-)collision resistance

I'm very new to cryptography, and I need help understanding the security claims made in Aumasson and Bernstein's paper on the SipHash. In particular, I'm trying to understand the following statement ...
1
vote
1answer
39 views

Is it safe to use fast/small hash for key identity?

I have to roll database access keys often, but it's important to know which key each system is using in order to avoid unavailability. I want the systems to report that without exposing the key ...
0
votes
0answers
69 views

Why are hash functions like SpookyHash and MurmurHash so highly collision resistant?

Why are hash functions like SpookyHash and MurmurHash so highly collision resistant? I tried to test these hash functions using a few billion input messages and I found that there is no hash value ...
3
votes
1answer
149 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 ...
-1
votes
1answer
44 views

Collision-Resistance Hash Function PRF

I am trying to solve the following question with an example/proof. The question is from Introduction to Modern Cryptography by Katz and Lindell. Any help would be appreciated.
4
votes
4answers
126 views

How to construct a collision resistant hash function that is not a one-way function?

How to construct a CRHF (collision resistant hash function) that is not a OWF (one-way function)? Not sure but I think it probably needs another CRHF?
0
votes
0answers
116 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 ...
7
votes
3answers
290 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 ...
3
votes
1answer
106 views

Is there any function that does not suffers birthday problem?

I am eager to know that if there is any function that does not suffer birthday problem and how to prove it formally that the function is not suffering the birthday problem.
3
votes
1answer
72 views

What are the time considerations with regard to security against birthday attack?

When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the ...
7
votes
0answers
214 views

Are there any practical attacks that create a printable chosen prefix MD5 collision?

I would like to create two ASCII text messages with the same MD5. Is this possible? If not, is there a similar but less strict attack that could work? Or to rephrase my last question: what are the ...
0
votes
1answer
45 views

Are collision-resistant hash functions even possible? [see description] [duplicate]

Surely there can be no real collision resistant Hash function since hash values are of finite size which means there are finitely many of them, but there are an infinite number of messages we could ...
15
votes
3answers
9k views

What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

What is "preimage resistance", and how can the lack thereof be exploited? How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?
9
votes
1answer
267 views

Non-iterative cryptographic hash functions

Consider the following cryptographic hash function $H$ which maps a message $m$ of variable size to $b$ bits: $$H:\{0,1\}^{*} \mapsto \{0,1\}^b$$ $$y = H(m) = SPRP(IV||m||padding)\mid_{b}$$ , where: ...
3
votes
1answer
48 views

What are fixed points and length extension attack in hash functions?

I was recently reading about hash functions, and I came across fixed points (one or more fixed points, interested in both) and length extensions, but I didn't exactly understand how these work. If ...
1
vote
1answer
249 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 ...
2
votes
0answers
49 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 ...
1
vote
2answers
78 views

Weak and Strong Collision Resistance, again

Weak collision resistance (CR), or second-preimage resistance, is the property that given $x$ and $h(x)$ ($h$ a hash function) it's difficult to find $x' \neq x$ such that $h(x') = h(x)$. Strong CR, ...
1
vote
1answer
80 views

“Security” of SHA functions (Wikipedia), what does it mean?

Wikepedia's table Comparison of SHA functions mentions "Security(bits)" for some SHA functions. From the ratio (Output size (bits): Security(bits)), I feel it is something like "collision resistance". ...
4
votes
2answers
5k views

Why is HMAC-SHA1 still considered secure?

This Q & A http://security.stackexchange.com/questions/33123/hotp-with-as-hmac-hashing-algoritme-a-hash-from-the-sha-2-family says that the security of HMAC-SHA1 does not depend on resistance to ...
1
vote
0answers
56 views

Why is the compression function in Miyaguchi-Preneel scheme secure?

I was reading about the Miyaguchi-Preneel scheme and had difficulty in understanding why the compression function, $h(H,m)=E(H, H \oplus M) \oplus M \oplus H$ can be called secure. The only resource I ...
25
votes
1answer
5k views

Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1?

I am from a web development background (I don't know an awful lot about cryptography or how the algorithms themselves work), so I am asking this question in simple terms. Consider a hash of the word ...
3
votes
1answer
110 views

Differential Cryptanalysis for Hash functions

How is differential cryptanalysis used to attack hash functions? I've been struggling through a couple academic papers and thesis's on the subject but they all sound like greek to me. Does anyone know ...
7
votes
1answer
60 views

Difficulty to find any preimages $a$ and $b$ for given $V$ so that $H(a) \oplus H(b) = V$?

Suppose I have the values $a$, $b$, and $V = H(a) \oplus H(b)$ with inputs $a \neq b$ and $H$ being SHA-224. None of these values are a secret. How secure is it to assume that no other possible values ...
1
vote
1answer
86 views

Finding collisions in SHA1

I am trying to find two collisions in SHA1 for the 50 least significant bits. I was wondering if there was a way to efficiently do this without having to brute force all of the possible hash outputs? ...
0
votes
1answer
45 views

Does absence of second pre-image resistance infer absence of pre-image resistance?

Talking about hash functions, I know the hierarchy is as follows: Pre-image resistance Second pre-image resistance Collision resistance Where each property implies the one before it so 2nd ...
0
votes
1answer
73 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
32 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
96 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 ...
2
votes
1answer
116 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)$$
3
votes
2answers
68 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 ...
10
votes
2answers
3k views

How many RSA keys before a collision?

I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a ...
3
votes
2answers
94 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 ...
1
vote
2answers
68 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, ...
2
votes
0answers
32 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 ...
3
votes
2answers
143 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 ...
0
votes
2answers
97 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
104 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 ...