Tag Info

Hot answers tagged

8

With the definitions that a function $F$ is collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$; first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with ...


8

It is neither pre-image resistant, second pre-image resistant nor collision resistant. It is easy to compute square-roots modulo a prime (assuming, of course, a square root exists, it will half the time). If $p = 3 \bmod 4$, then the simple formula $x^{(p+1)/4} \bmod p$ will work; for $p = 1 \bmod 4$, it's a tad more complicated but still sufficiently ...


5

Pre-image resistant but not 2nd pre-image resistant? describes the relationship between the three basic hash function security notions: Collision Resistance, Second Preimage Resistance and Preimage Resistance. In short, Collision Resistance implies Second Preimage Resistance (but not vice-versa) - there is a good diagram on page 4 of RogawayShrimpton04 that ...


5

Let me try to elaborate on their proof. Suppose you had a hash function $H$ that was second-preimage resistant but not first-preimage resistant. By showing that this leads to a contradiction, we will be showing that with second-preimage resistance, you must have first-preimage resistance. Namely, we will show that the lack of first-preimage resistance is ...


4

Preliminary: Almost the same article is available for free without breaking any law, nor downloading 5GB (formatting is shifted by at most one third of a page). It is also (as well as all other articles of IACR crypto conferences from 2000-2011) in the IACR Online Proceedings, specifically in the FSE 2008 section, but then you need to subtract about 223 from ...


4

Yes, it has happened. If you look at the SHA3 hash zoo, there are a number of hashes who has the best attack listed as "2nd preimage". One general place this can occur is if you have a hash function with a weak message compression step, but a fairly strong finalization step. Here, we might not be able to generate first preimages (because we don't know what ...


3

Given message $A$, you have to find message $B$, such that the first 64 bits (say, MSB) of their hashes collide: $$ MSB_{64}(H(A)) = MSB_{64}(H(B)) $$ This problem is called Second Preimage Search for the function $MSB_{64}(H)$, or Partial Second Preimage Search for the hash function $H$ alone. When $H$ is the full round SHA-1, there is no result, ...


3

While collision resistance can be defined for normal hash functions like SHA1, for target collision resistance you need a so called keyed hash function, that is a hash function that additionally to a message $m$ also takes a key $k$. The simplest way to construct a keyed hash function out of a regular one is to prepend the key in front of the message: ...


2

Take a function $H:\mathbb S\to\{0,1\}^k$ where $\mathbb S$ is a large finite subset of $\{0,1\}^*$, such that $H$ "compress data" [however this is defined], and $H$ is [conjectured] collision-resistant [thus second-preimage-resistant] and first-preimage-resistant; e.g., SHA-512, for $k=512$. Let $«0»$ and $«1»$ be two public distinct elements of $\mathbb ...


1

The current status as of the time I write this is: There are no known attacks on second pre-images for truncated SHA-256 that are faster than brute force.



Only top voted, non community-wiki answers of a minimum length are eligible