Funkcje Hashujące Kryptograficzne: Efekt Lawiny, Kolizje i Granica Urodzin

Co obiecuje kryptograficzny sumy bajterów

Funkcja haszująca kryptograficznie przyjmuje dowolnej długości wejście i generuje wyraz o stałej wielkości – 256 bitów dla SHA-256 – oraz musi spełniać trzy właściwości, aby była uważana za bezpieczną: odporność na odwracanie (dane haszowane nie można znaleźć takiego wejścia, które by je wygenerowało), drugorzędną odporność na odwracanie (dane wejściowe nie można znaleźć innego wejścia o tym samym haśle) i odporność na kolizje (nie można znaleźć dwóch wejść z tym samym hasłem, co zgodnie z twierdzeniem o urodzinach jest ściślej trudne niż drugorzędna odporność na odwracanie). Żadna z tych właściwości nie została matematycznie udowodniona jako niemożliwa do złamania – są to stwierdzenia empiryczne, które przetrwają tak długo, jak nikt nie opublikuje ataku szybszego niż siła bruta.

Efekt lawiny

Dobra funkcja haszująca wykazuje efekt lawiny: odwrócenie pojedynczego bitu wejściowego powinno zmienić w przybliżeniu połowę bitów wyjściowych, w sposób, który jest statystycznie niezauważalny, jakby rzucano monetą dla każdego bitu wyjściowego. Jest to to, co zaprojektowano do zagwarantowania w wewnętrznej konstrukcji SHA-256 – 64 rundach obrotów bitowych, operacji XOR, dodawania modulo i funkcji wyboru/większości na stanie o długości 256 bitów. Nie ma żadnego widoczego związku między wejściem a wyjściem; hasz słowa "hello" i hasz słowa "Hello" nie dzielą żadnej znaczącej struktury, pomimo różnicy w jednym bicie wejściowym.

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e... SHA-256("Hello") = 185f8db32271fe25f561a6fc938b2e26... // odwrócenie jednego bitu wejściowego -> ~50% bitów wyjściowych różni się, // bez jakiegokolwiek wyraźnego wzoru łączącego dwie sumy kontrolne Dlatego hasze są używane do sprawdzania integralności i dlatego są bardzo złe jako struktury zachowujące lokalność – nie można ich wykorzystać do znalezienia "podobnych" wejść w taki sposób, jak np. hasz percepcyjny obrazu, ponieważ efekt lawiny celowo niszczy jakąkolwiek korelację między podobieństwem wejściowym a podobieństwem wyjściowym.

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e...
SHA-256("Hello") = 185f8db32271fe25f561a6fc938b2e26...
// one bit flipped in the input -> ~50% of output bits differ,
// with no discernible pattern connecting the two digests

Granica urodzinowa: kolizje są bliżej niż intuicja sugeruje

Dla haszowania z n-bitowym wyjściem, próba znalezienia konkretnej przedmiotu wymaga średnio około 2ⁿ prób. Jednak znalezienie jakiejkolwiek kolizji między dwoma nieokreślonymi wejściami jest znacznie tańsze, dzięki paradoksowi Cezara: wśród zaledwie 23 osób istnieje ponad 50% szans, że dwie osoby urodziły się w tym samym dniu, ponieważ porównujesz wszystkie pary, a nie szukasz konkretnej daty. Ta sama matematyka oznacza, że kolizja w haszach o n bitach jest oczekiwana po około 2ⁿ/² losowych próbach, a nie 2ⁿ. Dla hasza 256-bitowego nadal to astronomiczne 2¹²⁸ operacji – bezpieczne według wszelkich praktycznych miar – ale dla hasha 128-bitowego to tylko 2⁶⁴, co jest osiągalne dzięki dedykowanemu sprzętowi, co jest jednym z powodów, dla których hasze o długości 128 bitów są uważane za zbyt krótkie do nowych zastosowań kryptograficznych.

expected tries for a collision  ≈ sqrt(2^n) = 2^(n/2)
n = 256 (SHA-256)  -> ~2^128 tries  (infeasible)
n = 128 (MD5-ish)  -> ~2^64  tries  (feasible with enough hardware)
n =  64             -> ~2^32  tries  (feasible on a laptop in hours)

Kiedy funkcje skrótu rzeczywiście się łamią

MD5 (128-bitowy) od 2004 roku ma praktyczne kolizje i obecnie uważa się go za złomowany kryptograficznie – ataki kolizyjne wykonywane w ciągu kilku sekund na zwykłym sprzęcie. SHA-1 (160-bitowy) został złamany w 2017 roku, kiedy Google i CWI Amsterdam opublikowali atak SHAttered, generujący dwa różne pliki PDF z identycznymi hashami SHA-1 po około 2⁶³ obliczeniach – znacznie mniej niż granica urodzinowa brute-force 2⁸⁰, ponieważ atak wykorzystał słabości strukturalne w funkcji kompresji SHA-1, a nie polegał na czystej sile bruta. SHA-2 (SHA-256/SHA-512) i SHA-3 (strukturalnie odmienny projekt oparty na spongi, zstandardyzowany w 2015 roku specjalnie w celu zabezpieczenia przed ewentualnymi przyszłymi słabościami strukturalnymi znalezionymi w rodzinie SHA-2) pozostają nienaruszone do dziś.

Haszowanie haseł stanowi odrębny problem

SHA-256 jest celowo szybki – to właśnie w tym tkwi sedno problemu, ponieważ szybkie haszowanie sprawia, że ataki typu brute force i deszczowe tablice przeciwko skradzionym bazom haseł są tanie. Haszowanie haseł wykorzystuje specjalnie zaprojektowane wolne funkcje – bcrypt, scrypt i Argon2 (obecny zalecany domyślny) – które dodają regulowany współczynnik pracy oraz, w przypadku scrypt i Argon2, celowo duże wymagania pamięciowe, aby przeciwdziałać równoległemu przetwarzaniu GPU i ASIC, tak że sprawdzenie jednego hasła trwa milisekundy dla prawidłowego logowania, a sprawdzenie miliardów potencjalnych haseł zajmuje odpowiednio więcej czasu atakującemu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Hash Functions i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.