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

learn more… | top users | synonyms (1)

4
votes
1answer
120 views

Why are collision attacks important when talking about MAC schemes?

I'm reading Ferguson, Schneier, and Kouno's Cryptography Engineering, and it has a section on MACs. It discusses different types of MACs, but it seems to claim that to acheive 128-bit level security, ...
4
votes
2answers
137 views

Is PBKDF2-HMAC-SHA1 really broken?

I just read through this article which demonstrates practical (and seemingly trivial) collisions in PBKDF2-HMAC-SHA1, and provides a few examples of collisions. Am I missing something here? Is ...
4
votes
1answer
135 views

I need a 64-bit cryptographic hash for 96 bits of data

I have a situation in which I need to combine a 32-bit datum, G, and a 64-bit datum, I, to produce a 64-bit datum. No two ...
2
votes
1answer
120 views

Is $H(x) = x^2 \bmod p$ pre-image resistant, second pre-image resistant and/or collision resistant

I have the function $H(x) = x^2\bmod p$ , where $p$ is a prime of length n bits and this function maps to the message $x$ to a n-bit hash value $H(x)$. I need to find out if it is pre-image ...
1
vote
1answer
77 views

Prove that two MACs with incremendal PRF application are not secure

How do I prove the following MACs are insecure?                                                        1                                                                                   2
3
votes
2answers
155 views

Hashing SHA-512 1000 times

SageMathCloud security (http://goo.gl/dCujW1) is as follows: Only the hash of your password is stored by the server, which uses 1000 iterations of the sha-512 hash function, with a salt length of ...
1
vote
1answer
101 views

Hash functions with or without secret key

The classical definition of hash functions (found in books) are OK, but when studying a little more there is a lot of notions that seem ambiguous (contradictory) to me : Sometimes we have hash ...
1
vote
2answers
102 views

Current standard for hash function security parameter?

When designing a hash function, what should be the secure input and output lengths? In particular, what lengths do I need for collision resistance?
5
votes
1answer
119 views

Is MD5 second-preimage resistant when used only on FIXED length messages?

I fully realize that MD5 should not be used in any new project, but in my particular situation I have severe CPU performance issues, so MD5 is convenient. I have read a lot about MD5 security for this ...
4
votes
1answer
63 views

Why has the sponge construction's generic collision finding attack a complexity of O(min(2^(-n/2) , 2^(-c/2)))?

I'm trying to learn about sponge function for creating hash functions and generic attacks on it. I'm looking for the collision finding attack scenario which leads to $O(\min(2^{-n/2} , 2^{-c/2}))$ ...
1
vote
1answer
72 views

Would this prevent FNV1a 32 bit hash collision?

I am considering the FNV1a 32 bit hash as part of a simple software security and authentication system. I am aware that FNV1a is NOT ideal but it may suit my needs. I am aware that FNV1a has rather ...
0
votes
2answers
83 views

Is the composition of collision resistant hash with non collision resistant hash a collision resistant hash?

Suppose $h_1$ is collision resistant, and $h_2$ isn't. Will $h(x)=h_2(h_1(x))$ always be collision resistant? [Edited:] the output of h2 must be uniformly distributed
1
vote
0answers
157 views

What is the chance of a collision when using SHA-3?

I currently am writing a web app and am using two random hashes that are before and after the string and are both 50 char long (alphabet, numbers, and special chars). ...
5
votes
2answers
256 views

Can the XOR of two non-collision-resistant hashes be collision resistant?

Suppose I have two hash functions, of which neither (or only one) is collision resistant, and I want to create a new hash function by taking the bitwise exclusive or (XOR) of the results of those two ...
1
vote
0answers
35 views

TCR hash functions from MD5

I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical (pag. 10 and 11) and here say The most direct way to construct a TCR hash function is to key a function like MD5 or SHA-1. ...
1
vote
1answer
67 views

Adversary to Any Collision Resistance Hash Function

I'm reading a notion Any Collision Resistance for Hash Functions. In the lecture define a collision finder CF. CF is said to $(t,\epsilon)$-break the family of hash functions $F_K$ if the ...
0
votes
1answer
44 views

Asymptotic Hash Function and Concrete Hash Function

I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical, and they say that its formalization is non-asymptotic. Why is the formalization non-asymptotic? What is an example of hash ...
0
votes
0answers
40 views

Merkle-Damgard transform: necessity of the Length block [duplicate]

The Merkel-Damgard transform append the message length (in blocks) to the message itself and then computing the 'chained hash' algorithm. Does the last block (which contains the length of the ...
2
votes
1answer
151 views

Brute force attack expected running time

I am a bit confused about the expected running times of brute force attacks on different cryptosystems. So let's assume a key size of $2^n$ bits. Symmetric key cryptography: $E(brute)$ = ...
1
vote
0answers
36 views

MD Construction Doesn't Propagate TCR

I'm reading a proof of the proposition of CollisionResistant Hashing Towards Making UOWHFs Practical Suppose there exists a compression function $F: \Sigma^k\times\Sigma^{c+m'} \rightarrow ...
2
votes
2answers
81 views

MD5 theoretical question

Ok, so this is a very possible stupid question, but one of those things that has sat at the back of my mind for a while. We all know that MD5 has issues, and these have been known for about a decade. ...
0
votes
1answer
88 views

SHA-1 Keyed Hash Function

I know that SHA-1 is an unkeyed cryptographic hash function when used in practice. But, in the theory, all hash function are defined with keys. My question is: How I will be able to formalize the ...
0
votes
1answer
90 views

Explicit Key SHA-1

I'm reading “Collision-Resistant Hashing? Towards Making UOWHFs Practical” and in the Section 2 it says: Hash functions like MD5 or SHA-1 have no explicit key. But no notion of ...
0
votes
1answer
101 views

No Birthday Attack to TCR

I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” , which compared TCR (Target Collision Resistant) and ACR (Any collision Resistant). It says we wish to stress ...
2
votes
1answer
52 views

Weaker Notion of Target Collision Resistance

I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states: While it might be easy to find a collision $M,M'$ in $F_K$ by making both $M,M'$ depend on $K$ ...
2
votes
1answer
65 views

Dependence on Keyed Hash Function

I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states: With an ACR hash function $F$ the key $K$ is announced and the adversary wins if she manages to ...
2
votes
2answers
191 views

Difference between collision resistance and target collision resistance

For a hash function, what's the difference between Collision Resistance and Target Collision Resistance?. I understand the definition of hash function collision resistance, but I don't know about ...
1
vote
2answers
147 views

Are there attacks that break collision resistance but not preimage resistance?

Are there any examples of attacks on hash functions which: break collision resistance and second preimage resistant, or break collision resistance and preimage resistant? I have looked at ...
2
votes
0answers
163 views

Question about modifying the MD5 plain text to cause a collision

I was trying to understand MD5 and got stuck with this question, its from Michael sipser's book on Information security Principles and Practice, 2nd edition The MD5 collision in Problem 25 is said ...
6
votes
1answer
382 views

Three-way hash collision

According to the birthday paradox we need approximately $O(|T|^{1/2})$ samples from the tag-space to find a collision for a hash function $h:K\times M \to T$. But how many samples are needed to find a ...
1
vote
0answers
56 views

Can you help me understand this “Message Modification by Meet-in-the-Middle” related to Tiger Hash?

I found this paper that explains how to attack a reduced round tiger hash, but I'm having a hard time understanding some of the mathematical notation. Could someone explain the section "Message ...
3
votes
1answer
98 views

md5sum collision question

I've been reading the wikipedia page, trying to get a better understanding of how to produce a collision. http://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities The wikipedia page above states: ...
0
votes
1answer
309 views

probability of N hash digits colliding

What is the probability of the first N hash digits colliding? for example i made a script that appends the first 5 digits of the file's sha1 hash to the name of the file. So will the probability of ...
4
votes
1answer
373 views

Will rehashing an SHA256 hash continually, eventually produce every possible value?

So let's say you had infinite time and energy. You have a hashed string of some sort. Because you have infinite time and energy, you can produce a collision(or the original value) easily enough. But, ...
4
votes
5answers
385 views

Is it theoretically possible to construct a string that contain its own hash value?

After saw the xkcd comic self-description, I wonder is it theoretically possible to construct a self-descriptive string that contains its own hash value? Let's say the string's md5 value is ...
12
votes
1answer
1k 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
58 views

Applications of 3-collisions

I recently read Improved Generic Algorithms for 3-Collisions by Joux and Lucks (Asiacrypt 2009), available as http://eprint.iacr.org/2009/305.pdf. I was wondering about applications of this technique ...
4
votes
4answers
350 views

Compare two hashes with different salt

I'm storing the salted hash of a credit card number in a database. What I'd like to be able to do is determine if two different entries in the same database correspond to the same credit card. ...
2
votes
1answer
114 views

Probability for collisions of a one-way compression function

Given a one-way compression function $h:\{0,1\}^n \rightarrow \{0,1\}^m$ and an attacker that picks $x_1 \ldots x_t \in \{0,1\}^n$ (uniformly distributed), I have to show that the probability to find ...
2
votes
1answer
111 views

The probability of finding a limited set of collisions for HMACSHA256

I need some input on the use of HMAC-SHA256 in an open source project, any help appreciated. The problem I'm solving is session fixation. We have a username, for that username we'd like to generate a ...
7
votes
1answer
350 views

Is it possible to actually verify a “sponge function” security claim?

When using a “sponge function” to create a cryptographic hash, we can look at the flat sponge claim, which flattens the claimed success probabilities of all attacks using a single parameter: the ...
1
vote
2answers
129 views

Digital Signature Scheme Count

My question is How I will be able to count digital signature Scheme that can sign many documents with one private key. There are signature scheme as long as exists private keys in the keys spaces? or ...
5
votes
1answer
538 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 ...
4
votes
1answer
153 views

How hard is it to generate a partial RSA fingerprint collision?

When I use SSH to log into a new system, I get asked to verify that the fingerprint (a 32 hex digits string) of the hosts's RSA key is correct. How much if it must I actually compare (by hand/eye) to ...
1
vote
2answers
115 views

Does collision resistance stay when extending a hash function to a set domain?

Given a Cryptographic hash function $h$ for element $x$, let's extend it to sets via $H(S)=\prod_{x\in{S}}{h(x)}$. I am asking if the new hash $H$ (in domain of set) is still collision resistant? To ...
2
votes
1answer
111 views

How does the birthday attack work in AUTH and UF-CMA games?

In the AUTH and UF-CMA games, an adversary is required to forge a ciphertext or message/tag pair to win the game. Given an encryption scheme $E$ and a PRF $F$, let $\hat{E} = C || F_k(C)$ and $C = ...
11
votes
1answer
575 views

Is Wikipedia's table about SHA-2 collisions correct?

I was looking a Wikipedia article on SHA-2, and the "Comparison of SHA functions" table seems to indicate that SHA-2 is less secure than SHA-1. Is this true, or is the table wrong / misleading? ...
6
votes
1answer
620 views

Using an MD5 hash as a password

Suppose Alice is using a password prompt that only accepts up to 32 characters for any particular password. Memorization of long strings of random characters is not one of Alice's strengths, so she ...
7
votes
2answers
263 views

Finding hash almost-collisions

A few months ago, XKCD posted a challenge to find a plaintext which hashed (using Skein 1024 1024) to a specified value. Inputs were scored based on the hamming distance between the hash of the ...
3
votes
4answers
613 views

Increased CRC collision probability when adding bits to input message

The Scenario I have a message string I need to transport over a wireless network that may be unreliable. This message string is about 100 bits long, and is packaged with an 8-bit CRC. When the ...