-15% na nową książkę sekuraka: Wprowadzenie do bezpieczeństwa IT. Przy zamówieniu podaj kod: 10000

Google pokazuje kolizję na SHA-1. Wielki zderzacz SHA-1 wykonał 9 trylionów obliczeń…

23 lutego 2017, 18:19 | Aktualności | komentarzy 12
TL;DR – zobaczcie dwa różne PDF-y – dające dokładnie tą samą sumę SHA-1. Jeden podpis cyfrowy jest poprawny na obu tych dokumentach…

Kolizje funkcji hashującej to zazwyczaj koszmar kryptografów – a  szczególnie dotknięty jest w tym przypadku podpis cyfrowy.

Podpis, jak pewnie wiecie, zazwyczaj jest dość krótki (nawet dużego, wielomegabajtowego dokumentu). Dlaczego? Bo robiony jest najczęściej nie z całego dokumentu, tylko np. tak:

signature = RSA_SIG(SHA-1(dokument)).

Co zatem jeśli znajdę dwa różne dokumenty o tym samym skrócie? Z równania powyżej wynika, że podpisy będą zgadzać się na obu dokumentach.

Kolizja. Zródło: Google.

Czyli podsuwam komuś dokument do podpisu, mając obok dokument o innej treści (ale dający taki sam SHA-1). Ktoś podpisuje, a podpis zgadza się na obu dokumentach…

Problem dotyka też choćby certyfikatów HTTPS – co jeśli SHA-1 jest takie samo na dwóch różnych certyfikatach…? Z tym przypadkiem obecnie przeglądarki radzą sobie różnie (np. Firefox ma wyrugować takie certyfikaty na początku 2017r.)

I to dlatego do podpisu trzeba używać funkcji skrótu odpornej na kolizje, co więcej – odpornej co najmniej kilka lat do przodu (nie chcemy żeby ktoś za 5 lat mógł sfałszować mój podpis cyfrowy wykonany dzisiaj…). Takie funkcje to obecnie SHA-256 czy SHA-512.

Google za 90 dni udostępni kod, który pozwoli na generowanie tego typu kolizji.

Wygenerowanie kolizji na realnym PDF-ie wymagało dość dużo obliczeń…:

  • Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total
  • 6,500 years of CPU computation to complete the attack first phase
  • 110 years of GPU computation to complete the second phase

ale patrząc na historię podobnych przypadków: a) zapewne pojawią się optymalizacje wykorzystanych do akcji algorytmów b) cały czas wzrasta dostępna moc obliczeniowa.

Można więc śmiało powiedzieć: SHA-1 is dead.

–Michał Sajdak

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



Komentarze

  1. Pitasato

    Niby ten sam wpis jest wszędzie, ale jak zawsze na sekuraku.pl napisane krótko zwięźle i na temat, niby nic a jednak wielka różnica :-)

    Odpowiedz
    • oszczędzamy czas czytelnikom :-) choć news pisany z lekkim zamuleniu przeziębieniem czy czymś podobnym :/

      Odpowiedz
      • Patryk

        To się ceni.

        Odpowiedz
      • Test penetracyjny by virus ;-D

        Odpowiedz
  2. Pankracy

    Wyrugowac – co to znaczy po polsku?

    Odpowiedz
  3. Te pdfy jeszcze nie zostały udostępnione? Testowałbym.

    Odpowiedz
    • Są są, nawet w poście są linki. To te oryginalne dokumeny PDF które wyprodukował Google w ramach kolizji.

      Odpowiedz
  4. Zakładając, że podpisywanie będzie nadal realizowane poprzez (przykładowo)
    signature = RSA_SIG(SHA-1(dokument))
    (a tak raczej na razie będzie ze względu na czas takiej operacji), to należy się liczyć z tym, że jakiej byśmy funkcji skrótu nie użyli, to i tak jakieś kolizje zawsze będą (bo taka jest „natura” funkcji skrótu).
    Czy nie poprawiło by takiej sytuacji (chodzi o próbę wyeliminowania „łatwego” znalezienia innego pliku o takim samym skrócie) użycie DWÓCH (lub więcej) funkcji skrótu, które byłyby dopiero podpisywane (jako scalone):
    signature = RSA_SIG(SHA-1(dokument)&SHA-2(dokument))
    albo (przy 3 skrótach)
    signature = RSA_SIG(SHA-1(dokument)&SHA-2(dokument)&SHA-3(dokument))
    Takie podejście jest proste, szybkie i wygodne a (według mnie) zwiększa złożoność problemu (znalezienia innego dokumentu mającego taki sam podpis) wykładniczo, przez co zabezpiecza to znacznie bardziej.

    Odpowiedz
    • Z definicji funkcji skrótu to powinna być właśnie odporna na kolizje ;)

      Odpowiedz
  5. krystian3w

    A kiedy pdf co kilka sum kontrolnych będzie takie samo np. na początek md5 i sha1 (na tych plikach md5 na razie różne, mimo że też już dead) albo sha1 i keccak.

    Odpowiedz

Odpowiedz na sekurak