18
$\begingroup$

In a recent study SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust by Gaëtan Leurent and Thomas Peyrin. 2020, they showed the first practical chosen-prefix collision attack that required two months of computations using 900 Nvidia GTX 1060 GPUs.

Chosen-prefix collision (CP- collision)1: two message prefixes $P$ and $P'$ are first given as challenge to the adversary, and his goal is to compute two messages $M$ and $M'$ such that $H(P \mathbin\| M) = H(P' \mathbin\| M')$ where $\mathbin\|$ denotes concatenation.

They worked for two kinds of attacks;

  • They reduced the use of neutral bits BCJ+05 and boomerangs JP07 from $2^{64.7}$ to $2^{61.2}$
  • Also, they improved graph-based technique (LP19) to compute CP-collision from $2^{67.1}$ to $2^{63.4}$.

Actually, the CP-collision attack enables attackers to create some meaningful messages; however, classical collisions are not.

To demonstrate the attack they achieved a PGP/GnuPG impersonation (CVE-2019-14855).

The list of attacks on SHA-1

Questions:

  • Can a double hashing $h= \operatorname{SHA-1}(\operatorname{SHA-1}(m))$ mitigate the CP-collision?* It seems so, since the meaningful part will not exist for attackers as longs as they are not able to break double $\operatorname{SHA-1}$. This seems not feasible, yet.
  • An immediate follow-up question; if the answer is yes, should we design the new protocols based on double hashing?

*There can be many variants of double hashing.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 1) This doesn't mitigate the collision. 2) Anything that can be changed from SHA-1(m) to SHA-1(SHA-1(m)) could be just as easily changed to SHA-3(m). $\endgroup$
    – Paul Smith
    Jan 9, 2020 at 0:01

1 Answer 1

Reset to default
30
$\begingroup$

a. No such double hashing doesn't do a bit of good. Anything which collides after a single hash will definetly collide after a double hash. It preserves all collisions and adds new ones.

We might consider other constructions which may provide some strength e.g $H(H(m) || m)$ however:

b. We have no need for any such double hashing of SHA1 as we have newer better hash functions. Most notably we have SHA3 which is by all accounts far from being broken

Improve this answer
$\endgroup$
8
  • 6
    $\begingroup$ In almost all places where we can replace SHA1 with the modified construction we could also replace with SHA3. We even have hardened SHA1 which gives some backwards comparability if required. $\endgroup$
    – Meir Maor
    Jan 7, 2020 at 18:08
  • 1
    $\begingroup$ @kelalaka: A possible more useful double-hash might be $H(m) || H("hello world" || m))$ or something, or combine those two hashes somehow other than concat, maybe XOR. They can both be computed with only a single pass over the data so it's still usable as a stream hash where you only have access to the data once on the fly. (No extra memory bandwidth required either, and interleaving computation on 2 hashes in parallel is probably good for throughput.) But even if you need a short 160-bit hash, that might not be better than truncating a SHA-256 or SHA-512. $\endgroup$
    – Peter Cordes
    Jan 8, 2020 at 3:34
  • 17
    $\begingroup$ I don't think constructing a new 160-bit hash function with SHA-1 as a building block makes a lot of sense for any use-case except maybe new firmware for existing embedded hardware that has a high-performance SHA-1 accelerator and can't run any other hashes acceptably fast. Otherwise if you can change the hash function, you can replace it entirely. $\endgroup$
    – Peter Cordes
    Jan 8, 2020 at 3:37
  • 2
    $\begingroup$ @PeterCordes Actually, NIST removed SHA-1 from the recommendation in 2011. The $2^{80}$ classical collision with 50% probability is not negligible, we should consider the lower probabilities, and there are already collective computing powers that can reach $\approx 2^{63}$ in a day, like Summit. Maybe the more interesting of this work is the use case. Truncating has one good side that prevents the extension attack that built-in SHA3. $\endgroup$
    – kelalaka
    Jan 8, 2020 at 8:52
  • 15
    $\begingroup$ "When you discover you’re riding a dead horse, the best strategy is to dismount." $\endgroup$
    – tylo
    Jan 8, 2020 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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