11
$\begingroup$

In the context of cryptographic hash function collisions, what exactly is a pseudo-collision attack?

E.g., pseudo-collisions are discussed here:

Also, is that term actually well-established and used consistently?

$\endgroup$
11
$\begingroup$

To understand what a pseudo-collision attack is, we first need to understand how a hash function internally works:

Most hash functions are basically composed out of four functions:

  • An initialization function that just sets a bunch of start values for the state: $I:\emptyset\rightarrow \{0,1\}^k$
  • An input pre-processing function that computes some values based on the message and possibly hidden context: $P:\{0,1\}^l\rightarrow \{0,1\}^q$
  • A state-update function, sometimes also called "compression function" that takes the current message block, the associated pre-processing and the current state and outputs a new state: $U:\{0,1\}^l\times\{0,1\}^q\times \{0,1\}^k\rightarrow \{0,1\}^k$
  • An output function that takes the state and outputs the hash digest: $O:\{0,1\}^k\rightarrow \{0,1\}^o$

Now a normal collision attack takes the standard composition of these functions and tries to find a collision.
A pseudo-collision attack on the other hand just tries to find a collision on the state-update function. So an attacker is interested in finding two triples $x=(m,p,h),x'=(m',p',h')$ such that $U(x)=U(x')$ with $x\neq x'$.

The application of this is more or less clear: To show weaknesses in the core update function and give insights into possible paths to full collision attacks.
For additional discussion also see these slides (PDF).


When I originally wrote this answer I screwed the concepts up, so here you have the definition and use of a "near-collision-attack" as well as a bonus:
The term "near-collision-attack" and the associated term "near-collision" aren't as "strictly" defined as "collision-attack" and "collision" however I'd define a nearcollision-attack as follows:

Given a hash function $H:\{0,1\}^*\rightarrow \{0,1\}^n$ find $x_1,x_2$ with $x_1\neq x_2$ such that $\Delta(H(x_1),H(x_2))$ is low but not zero. Here $\Delta(x,y)$ denotes the Hamming distance between the two input strings, i.e. the number of set bits of $x\oplus y$.

The application of these attacks is clear: Suppose you authenticate files by providing a hash for human verification over a secure channel. As humans are lazy they probably won't spot the difference (if it is small as it is here) between the computed hash and the transmitted hash in case of a pseudo-collision.
As a real-life example ask yourself: When you verify an MD5 / SHA1 hash of a file, do you actually look at all the hex digits or only at the first few and the last few?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.