2
$\begingroup$

The first block $M_0$ is one of 64 possible values, whereas the next six blocks $M_1...M_6$ are chosen randomly. The idea is to publish the SHA-1 hash of $M_0...M_6$, wait for the value of $M_0$ to be announced, and then release the original message $M_0...M_6$ - so as to prove that we can predict $M_0$ beforehand.

But now we want to fake our prediction: that is, publish a certain hash $H$, and then once $M_0$ is revealed, we publish $M_0...M_6$ such that $M_0$ is correct and it hashes to $H$.

I'm not sure if my attack should leverage properties that are specific to SHA-1: it seems unlikely that it should. But I'm lost as to how I can choose 64 different sets of 6 random blocks that hash to the same value (when concatenated with one of $M_0$'s 64 values).

Edit: I forgot to mention that the algorithm used can be probabilistic, and it should work with at least $50\%$ probability.

Improve this question
$\endgroup$
5
  • $\begingroup$ I currently don't get the question. If this is some kind of assignment you may want to make sure you communicate the entire meaning of the assignment. $\endgroup$
    – Maarten Bodewes ♦
    Dec 23, 2015 at 11:47
  • $\begingroup$ @MaartenBodewes This is an assignment. What part isn't clear? $\endgroup$
    – Matt
    Dec 23, 2015 at 11:49
  • $\begingroup$ I don't see any difference between the output as discussed in the first paragraph and that of the second one. I can of course guess but you know what they say about assumptions... $\endgroup$
    – Maarten Bodewes ♦
    Dec 23, 2015 at 11:54
  • $\begingroup$ @MaartenBodewes In the second paragraph, we aren't able to predict $M_0$. So we publish a hash without knowing $M_0$, and then once we know $M_0$ we choose a message that contains $M_0$ and that matches to the hash. In the first paragraph we know $M_0$ beforehand. $\endgroup$
    – Matt
    Dec 23, 2015 at 12:00
  • $\begingroup$ Eh, SHA-1 isn't probabilistic, right? $\endgroup$
    – Maarten Bodewes ♦
    Dec 24, 2015 at 11:15

2 Answers 2

Reset to default
2
$\begingroup$

Assuming a naive birthday attack, you can do this by generating 63 collisions.

The idea is to create 32 colliding message pairs (64 messages total). Then take the hashes from two adjacent pairs and use those as the IV's for another row of 16 collisions. Keep doing that until you converge a single hash.

Building a collision tree that looks like this, where m and m' are colliding messages:

m0,m'0  m1,m'1  m2,m'2  m3,m`3  ...  m28,m'28  m29,m'29  m30,m'30  m31,m'31
\         /      \       /             \         /          \         /
 \       /        \     /               \       /            \       /
  m0,m'0          m1,m'1                 m14,m'14             m15,m'15             
    \               /                          \               /
     \             /                            \             /
      \           /                              \           /
         m0,m'0                                     m7,m'7


                     ..........................


                      m0,m'0,     m1,m'1
                          \        /
                            m0,m'0

Your $M_0$ would be any message from the first row, your $M_1$ would be the next message in the graph from the 2nd row, and so on.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Solved it myself and came here to post the answer for future reference but you beat me to it (: Thanks! $\endgroup$
    – Matt
    Dec 23, 2015 at 21:08
2
$\begingroup$

As far as I understand, you are trying to find $M_1...M_6$ so that $H(M_0||M_1||...||M_6) = h$ for any of 64 preset values of $M_0$. This implies a collision attack on $H$, which in the case of SHA-1 has not yet been accomplished in practice (though it is probably close).

Specifically, you would need a chosen prefix collision. We have such attacks for MD5 (see e.g. the links from this answer), assuming you have enough freedom in the size/choice of $M_i$. However, there is still a ways to go before it could be accomplished for SHA-1.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Fortunately SE dates answers :) Dear reader, if this attack is now feasible, please amend asnwer. $\endgroup$
    – Maarten Bodewes ♦
    Dec 23, 2015 at 11:59
  • $\begingroup$ Hi, I guess I forgot a crucial detail: see my edit. I don't think they'd give us an impossible homework assignment $\endgroup$
    – Matt
    Dec 23, 2015 at 12:02
  • $\begingroup$ @Matt, no I don't see how that would make it possible. You would not need quite so many collisions, but you would still need some. My guess is that you need to detail how you would do it if you had a collision attack (with arbitrary IV). $64 = 2^6$. $\endgroup$
    – otus
    Dec 23, 2015 at 12:06
  • $\begingroup$ @otus We're supposed to detail an attack with a time complexity much lower than finding a preimage, there's nothing about assuming a collision attack. ): The only leverage I can think of in an attack is that the possibilities for $M_0$ are very limited: 64 out of $2^{512}$. But I haven't been able to make use of this $\endgroup$
    – Matt
    Dec 23, 2015 at 12:10
  • $\begingroup$ @Matt, a brute force collision attack has a complexity much lower than finding a preimage (~$2^{80}$ vs. ~$2^{160}$). So you need to detail how to chain collision attacks to get them all into 1-2 hash values. I don't really want to just give you the solution here... $\endgroup$
    – otus
    Dec 23, 2015 at 14:20

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.