4
$\begingroup$

I'm doing an exam in computer security and I encountered this problem which I'm unsure of how to attack properly. Should I get down and dirty with the Hash function on paper or is there a more general approach to making these kinds of security judgments?

The question is as follows:

Let $M = B_1, ...,B_n$ be a message consisting of $n$ blocks of 512-bits. Let $H$ be the function $H(M)=(((B_1+B_2) \oplus B_3)+B_4 \oplus B_5)...B_n$, where $+$ is the addition modulo $2^{512}$ and $\oplus$ is bitwise XOR. Is $H$ a secure Hash Function?

For each requirement:

  1. preimage resistance (or one-wayness)
  2. second preimage resistance (or weak collision resistance)
  3. collision resistance (or strong collision resistance)

motivate if it holds or disprove it.

Let $D$ be the set of all possible messages with $n \leq 4$ (ie. all messages smaller than 2 Megabits). Does $H$ produce more collisions than SHA-256 for messages in $D$?

$\endgroup$
  • 1
    $\begingroup$ Suppose you have a target value for $H(M)$ and have preselected values for $B_1, B_2, ..., B_{n-1}$. How difficult would it be to find a value for $B_n$ that makes the message hash to the desired target value? $\endgroup$ – poncho Mar 29 '18 at 21:21
  • $\begingroup$ BTW: this constraint $n \le 4$ actually means "all messages smaller or equal to 2 Kilobits" $\endgroup$ – poncho Mar 29 '18 at 21:24
  • $\begingroup$ Thanks but I still have no idea how to determine this unfortunately :/ Any help appreciated! $\endgroup$ – Mountain_sheep Mar 29 '18 at 22:00
  • 1
    $\begingroup$ Consider the $n=2$ case... $\endgroup$ – poncho Mar 29 '18 at 22:01
  • 1
    $\begingroup$ No, imagine your hash is only $B_1 + B_2$, how do you manage to forge a hash matching your target by only playing on $B_2$? $\endgroup$ – Mariuslp Mar 29 '18 at 22:14
8
$\begingroup$

The best way to approach problems like this is to start by assuming that a simple solution exists. That assumption might be wrong, of course, but:

  1. since this is a textbook problem, it probably does have a relatively simple solution that you should be able to figure out based on what you've learned, and

  2. even if that wasn't the case, you should still at least try to look for simple solutions before spending time on anything more complicated.

Thus, you should assume that, on one hand, if your hash function doesn't satisfy one of the three security properties the question asks about, then there should be a fairly simple example where that property is violated. On the other hand, if it does satisfy them, then there should be some fairly straightforward way to prove that conclusively, or at least to reduce it to some widely held assumption (e.g. "if someone can break this hash, then they can also break SHA-256").


With that in mind, let's take a closer look at your hash function. It's specified as taking a sequence of $n$ input blocks, which are combined according to a particular expression involving addition (modulo $2^{512}$) and bitwise XOR:

$$H(B_1, \dots, B_n) = ((((B_1 + B_2) \oplus B_3) + B_4) \oplus B_5) + \dots$$

How do we simplify that? Well, the fewer blocks there are, the simpler the expression gets. So let's start by considering the simplest possible case, i.e. $n=1$. With just a single block of input, your hash function looks like this:

$$H(B_1) = B_1$$

Now, consider the three security properties you've been asked about, and see if you can come up with single-block counterexamples:

  1. preimage resistance: if given a value $X$, can you find a single-block message $M = B_1$ such that $H(M) = X$?

  2. second preimage resistance: if given a single-block message $M = B_1$, can you find another single-block message $M' = B_1' \ne B_1$ such that $H(M) = H(M')$?

  3. collision resistance: can you find any two single-block messages $M = B_1$ and $M' = B_1' \ne B_1$ such that $H(M) = H(M')$?


Hopefully, you should be able to answer "yes" to at least one of the three questions above. (I won't spoil which one.) In fact, with a little bit more thought, you should be able to figure out that, for single-block messages, the answer to the other two questions is definitely "no".

However, we're not done yet. What if we consider messages consisting of two blocks? Then the hash function will look like this:

$$H(B_1, B_2) = B_1 + B_2$$

where $+$, of course, denotes addition modulo $2^{512}$. With that in mind, let's consider the three questions again. (Of course, you don't need to reconsider the one for which you already found a single-block counterexample above.)

  1. preimage resistance: if given a 512-bit value $X$, can you find a two-block message $M = (B_1, B_2)$ such that $H(M) = X$?

  2. second preimage resistance: if given a two-block message $M = (B_1, B_2)$, can you find another two-block message $M' = (B_1', B_2') \ne M$ such that $H(M) = H(M')$?

  3. collision resistance: can you find any pair of two-block messages $M = (B_1, B_2)$ and $M' = (B_1', B_2') \ne M$ such that $H(M) = H(M')$?


If, after considering the two-block case, your answer to some of those three questions was still "no", then it might be time to start considering whether the way you arrived at the "no" answer for the one- and two-block cases could be generalized to any number of blocks. Or you could decide to spend some time considering the three block case, if you think that the answer might be "yes" in that case.

But in fact, in this case, that should not be necessary; just considering the one- and two-block cases should be enough to give a definitive answer to all three questions for this hash.


Ps. As for the extra question about the number of collisions at the end, first note that the question (or your transcription of it) clearly has some typos: four 512-bit blocks work out to 2048 bits or 2 kilobits, not 2 megabits!

In any case, we of course don't know exactly how many collisions SHA-256 has on that set of inputs, since the input space is too large to count them by brute force, and any method of determining the exact number significantly faster than by brute force would require breaking SHA-256, or at least come worryingly close to it.

However, you should be able to come up with a lower bound on the number of collisions SHA-256 or any other hash with a 256-bit output size can have for that input space, just using simple arithmetic. (The generalized pigeonhole principle may be useful here.) And your hash function $H$ is simple enough that you can count the exact number of collisions it will have on the input space $D$, and compare that with the lower bound.

In fact, just for a yes/no answer, you don't really even need to calculate the actual number of collisions. All you really need to do is consider how close to the theoretical lower bound for a 512-bit hash your function $H$ gets, and then consider how making the hash output longer / shorter affects the lower bound.

(Also, yes, the result you'll get may seem counterintuitive. What it really demonstrated is simply that the total number of collisions doesn't necessarily correlate with the difficulty of actually finding one.)

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