Tag Info

Hot answers tagged

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 ...


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 ...


4

A long message is a message that, when padded, is longer than the block size of the hash function. That means that the hash function has to process the message in parts and keep track of state somehow, which may allow for attacks. Such attacks would not apply to messages shorter than the block size, and may additionally require a large number of blocks to ...


4

Without the specific reference I can't be sure this is what you are talking about, but generally a "long message" attack is a way to defeat second preimage resistance with less complexity than expected. It uses a time-space tradeoff to find a second preimage with complexity $2^{n/2}$ for a $n$-bit hash function (normally you would expect $2^n$). In the ...


4

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 ...


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 ...


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 ...


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: ...


3

I prefer using definitions that explicitly specify who does what. Weak collision resistance: After Bob creates some message x1, it is "computationally infeasible" for an attacker Mallory to compute some other message x2 such that h(x1) == h(x2). Strong collision resistance: It is "computationally infeasible" for an attacker Mallory to find any two messages ...


2

First, I must warn you that any definition that uses "feasible" will not be a rigorous one. The only way I know to rigorously define collision and preimage resistances is using function families, i.e. keyed hash functions. That said, if you believe the negations are equivalent, the definitions you are using are themselves equivalent (you correctly negated ...


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