# Tag Info

18

A cryptographic hash function $f : \{0,1\}^{*} \to \{0,1\}^n$ has three properties: (1) preimage resistance, (2) second-preimage resistance, and (3) collision resistance. Even further, these properties form a hierarchy where each property implies the one before it, i.e., a collision-resistant function is also second-preimage resistant, and a second-preimage ...

10

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

9

The difference is in the choice of $m_1$. In the first case (second preimage resistance), the attacker is handed a fixed $m_1$ to which he has to find a different $m_2$ with equal hash. In particular, he can't choose $m_1$. In the second case (collision resistance), the attacker can freely choose both messages $m_1$ and $m_2$, with the only requirement ...

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

7

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

7

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

6

As far as I am aware, there are no practical known second pre-image attacks on MD5, under the conditions you listed. However: if the attacker can control any part of the original, I would worry about using MD5 in this setting. Its security in this setting may be fragile and there may well be cleverer attacks than anything currently in the literature. I ...

6

Consider the function $H$ transforming a message $m$ to the SHA-512 hash of the first 1024 bits of $m$ (right-padded with $1024-n$ zero bits if the bit length $n$ of $m$ is less than 1024). $H$ is first-preimage resistant, but not second-preimage resistant: once you have a first preimage $m_1$, it is trivial to get another $m_2$ with the same hash (e.g. ...

6

In their paper Second Preimages on $n$-Bit Hash Functions for Much Less than $2^n$ Work, Kelsey and Schneier provide: a second preimage attack on all $n$-bit iterated hash functions with Damgard-Merkle strengthening and $n$-bit intermediate states, allowing a second preimage to be found for a $2^k$-message-block message with about $k\times2^{n/2+1}+ ... 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 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 ... 5 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 ... 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 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 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

You are not asking for a collision but for a preimage. Collision attack: the attacker computes two messages m and m', distinct from each other, such that m and m' hash to the same value. Preimage: the attacker is given a goal (a hash value h) and finds a message m which hashes to h. MD5 is weak for collisions, but not for preimages: no attack method is ...

4

I really like this question, and have two things to say. First note that CBC-MAC is no good since given the key it's easy to find a collision. Let $t$ be a tag for a message $m=m_1,m_2$ of length $\ell$ bits. Then, in CBC-MAC the input to AES first is $\ell$ and then the output is XORed with $m_1$ and input to AES, and so on. Let $t_1$ be the intermediate ...

4

Actually, to the best of our knowledge, it's computationally infeasible. By the terminology what we use when we discuss cryptographical hash functions, you're not asking for a hash collision (which is "find two different messages that hash to the same value"), but instead you're asking for a hash preimage (which is "for this hash value, find a message that ...

3

I have ask as part of my answer, "What problem are you trying to solve?" Do you want a secure unkeyed hash function? If you do, then there are plenty of them around. Even some of the ones that are broken for some uses might be okay for yours (SHA-1 springs to mind -- note the discussion above on HMAC and how broken a hash function has to be). But really, ...

3

We know no practically feasible way to do what you ask for, except if the hash X=acf3602b5eb9a2db3e365d3043682faf or the content of the file wczasp.rb was prepared specially to make that possible. Assuming that the content of file wczasp.rb is arbitrary, what is asked would be a preimage attack. This is further sub-classified as first preimage if only the ...

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

SipHash is a MAC (aka Pseudo Random Function Family) with 64-bit output and 128-bit key, rather than a hash (aka random public member of a Pseudo Random Function Family). It is explicitly designed to be used with a secret random key. Quoting Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash: a fast short-input PRF (in proceedings of Indocrypt 2012): ...

3

Can we exhibit collisions, or second-preimages (with implies the former), for the ChaCha core? No, likely not. The Salsa20 and ChaCha cores both consist of a large number of "quarter-rounds" each of which is invertible and bijective. The only reason neither core is a bijection (and thus can have collisions) is the final addition of the input elements ...

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

2

Well, if you construct what you described you basically create a function $f: \{0,1\}^{2m} \rightarrow \{0,1\}^m$. As you correctly pointed out these two strings give the same when xor'ed. So the messages $10101111$ and $00000101$ will result in the same xor and hence will get mapped to the same hash, resulting in a second preimage as you found two $x,x'$ ...

1

Consider this hash: $$H(m) = m$$ Where we define it's domain to be messages of some arbitrary fixed-length. It is completely second pre-image resistant. It is not at all first pre-image resistant. Therefore: Second pre-image resistance does not imply first pre-image resistance.

1

The easiest, zero thought, way to get an answer to this question is to ask the computer. Using Dylan's cryptol implementation it is straight-forward to ask a question: m1 != m2 ==> ChaChaCore m1 != ChaChaCore m2 That is, if inputs m1 and m2 are not equal then the ChaCha core function will not be equal either. Cryptol doesn't (well, didn't) have an ...

1

Yes. ​ I believe this is the standard conversion. (That link is to the paper "Universal One-Way Hash Functions via Inaccessible Entropy".)

1

I think I understand what you're asking now. ChaCha is essentially a block cipher with no key schedule. This has an advantage, less SRAM required for constrained devices, and even for desktops, less cache calls ( https://stackoverflow.com/questions/10274355/cycles-cost-for-l1-cache-hit-vs-register-on-x86 ). Part of the reason why ChaCha manages to be as ...

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