Pokazano względnie tanie generowanie kolizji klasy chosen prefix dla SHA-1

08 stycznia 2020, 13:16 | W biegu | komentarzy 6
: zin o bezpieczeństwie - pobierz w pdf/epub/mobi.

Kto chce miło spędzić całe popołudnie – zapraszam tutaj („SHA-1 is a Shambles. First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust”). Kto chce mieć esencję z cytowanego badania, niech czyta dalej ;) O kolizjach w SHA-1 pisaliśmy już w 2017 roku (dość mocne wyniki zaprezentował Google, choć wymagało to dość dużo mocy obliczeniowej – ponad 6500 lat pracy GPU). W tamtym przypadku było możliwe np. wygenerowanie dwóch różnych PDF-ów, posiadających tę samą sumę SHA-1. Bazowało to na na wyborze prefiksów dla kolizji:

Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two PDF documents with the same SHA-1 hash yet that display arbitrarily-chosen distinct visual contents

O co chodzi dokładniej z tymi prefiksami? Zadanie jest takie:

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 || M) = H(P1 || M’ ), where || denotes concatenation.

Najnowsze badanie pokazuje koszt takiej operacji na poziomie 45k USD:

45k US$ for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs.

Jaki wniosek? Jeśli nie jesteście pewni, że wasz przypadek użycia SHA-1 jest bezpieczny (są i takie) użyjcie innych algorytmów (np. SHA-256 czy SHA-512). W szczególności jakiekolwiek użycie SHA-1 związane z podpisem cyfrowym powinno być wykluczone. Dla przykładu, w cytowanej pracy, badacze w praktyce pokazali atak na mechanizm PGP Web of Trust.

–ms

Spodobał Ci się wpis? Podziel się nim ze znajomymi:



Komentarze

  1. kolizja

    Czy dodatkowe dopisanie hasha sha256 już coś lepiej zabezpieczy?
    https://ideone.com/1l18u1
    <?php
    $shift="123";
    echo "shift=$shift";
    echo "\n”;
    $sum=hash(„sha1”,$shift);
    echo „sha1=$sum”;
    echo „\n”;
    $sum=hash(„sha256”,$shift);
    echo „sha256=$sum”;
    echo „\n”;
    $shift=$shift.$sum;
    echo „shift+sha256=$shift”;
    echo „\n”;
    $sum=hash(„sha1”,$shift);
    echo „sha1(shift+sha256)=$sum”;
    echo „\n”;
    ?>

    Odpowiedz
    • Michał

      Nie sądzę, „chroni” cię nadal tylko SHA1, jedyne co uzyskałeś to rozszerzenie hasła.

      Odpowiedz
      • kolizja

        A jakby tak
        sha1(sha256(tekst+sha256(tekst)))?
        Wtedy mamy ten sam rozmiar danych do funkcji sha1.

        Odpowiedz
  2. Pjentestjer

    Tak.

    Odpowiedz
  3. łips

    Czy jest jakaś spójna lista funkcji skrótów, z podziałem na te z udowodnioną kolizją i _jeszcze_ bez kolizji?

    Odpowiedz

Odpowiedz