Jednym z wielu zastosowań funkcji skrótu (ang. hash functions) jest identyfikacja i weryfikacja plików.

Pewnie każdemu zdarzyło się gorączkowo poszukiwać ważnego dokumentu, zapisanego „gdzieś na komputerze” i potrzebnego od zaraz. Korzystamy wtedy z wbudowanej funkcji wyszukiwania systemu operacyjnego, a w ostateczności po prostu przeglądamy pliki jeden za drugim, aż znajdziemy (lub nie) ten właściwy. Co jednak, gdy taki plik trzeba znaleźć wśród setek tysięcy innych?

Informacyjna klęska urodzaju

Przeciętny użytkownik zazwyczaj nie spotyka się z takim problemem, ale może on być udziałem na przykład operatorów oferujących usługę dysku chmurowego. Gdy wrzucamy plik „w chmurę”, dostawcy może zależeć na sprawdzeniu, czy nie przechowuje już identycznego pliku. Jeżeli dany plik już jest w chmurze (np. kilku użytkowników zapisało identyczny plik z daną piosenką), można zastosować tzw. deduplikację – odnotować, że dany plik ma być dostępny dla kolejnego użytkownika bez potrzeby jego ponownego przesyłania i zapisywania na serwerze. Pozwala to ograniczyć koszty transferu i przechowywania plików. Również serwisy społecznościowe muszą szybko weryfikować wiele plików, dbając o to, aby ich użytkownicy nie publikowali treści zakazanych, takich jak materiały promujące terroryzm czy nawołujące do przemocy lub ją przedstawiające. Wreszcie niekiedy w postępowaniu sądowym może pojawić się konieczność udowodnienia, że na danym nośniku cyfrowym (np. na dysku laptopa) wśród wielu innych znajdowały się także określone pliki istotne dla rozstrzygnięcia sprawy.

Trudno wyobrazić sobie sprawdzanie tak dużej liczby plików ręcznie – wymagałoby to ogromnego nakładu czasu i środków. Na szczęście można zautomatyzować ten proces dzięki funkcji skrótu (ang. hash function).

Czym są funkcja skrótu i hash?

Funkcja skrótu jest rodzajem funkcji matematycznej, która zastosowana do pliku (zapisu) cyfrowego pozwala przyporządkować mu określoną wartość, zwaną hashem. Hash jest ciągiem liter i cyfr o stałej długości, który można w uproszczeniu nazwać „cyfrowym odciskiem palca” pliku komputerowego. Przykłady hashów można obejrzeć poniżej (hashe ciągów tekstowych wygenerowane przy użyciu funkcji MD5).

 

Ala ma kota Mruczka.	149c190811c6c6cea4b51567d4314348
Ala ma kota Mruczka..	fb15a3daecaf2a71bcc58a513f3dc97d
Ala ma kota mruczka.	326df554146fee7088b02665e0bce31b

Aby znaleźć interesujący nas plik wśród wielu innych, należy najpierw dysponować jego hashem. Nie musimy go generować za każdym razem – można skorzystać z wcześniej zapisanego hasha. Hash można wygenerować dla dowolnego rodzaju pliku, a więc plików tekstowych, obrazków, dźwięków czy filmów. Następnie należy zastosować tę samą funkcję skrótu do obliczenia hashów przeszukiwanych plików. Gdy znajdziemy hash identyczny z wygenerowanym, oznacza to, że właśnie znaleźliśmy nasz plik – są one identyczne (można powiedzieć, że zgadza się „cyfrowy odcisk palca” tych plików). Wcale nie trzeba przy tym sprawdzać treści przeszukiwanych plików ani nawet dysponować kopią szukanego pliku.

Właściwości funkcji skrótu

Podany przykład ilustruje podstawową właściwość funkcji hashującej – dla tej samej wartości wejściowej (pliku) generowana jest zawsze ta sama wartość wyjściowa (hash). Kolejną ważną właściwością takiej funkcji jest jednokierunkowość – łatwo jest wygenerować hash dysponując plikiem, natomiast rekonstrukcja pliku na podstawie hasha jest bardzo trudna, niemalże niemożliwa (wymaga dużej mocy obliczeniowej).

Ta cecha pozwala ograniczyć podatność funkcji hashującej na ataki, mogące polegać np. na wygenerowaniu więcej niż jednego pliku pasującego do danego hasha (choć warto pamiętać, że w odniesieniu do niektórych funkcji udało się przeprowadzić takie ataki i wygenerować tzw. kolizje hashów). Teoretyczna możliwość przyporządkowania kilku plików do jednego hasha jest wpisana w naturę funkcji hashującej – zbiór plików jest potencjalnie nieskończony, w przeciwieństwie do skończonego zbioru hashów (ze względu na ich stałą długość)[1].

W praktyce takie ryzyko jest ograniczone ze względu na kolejną cechę funkcji hashującej, zwaną obrazowo efektem lawiny (ang. avalanche effect). Tak jak każda lawina rozpoczyna się od osunięcia drobnego kamyczka, tak w przypadku funkcji hashujących nawet drobna zmiana w wartości wejściowej (sprawdzanym pliku) powoduje znaczące zmiany w wartości wyjściowej (hashu). Efekt ten można zaobserwować na przykładach przytoczonych powyżej – niewielkie zmiany czy błędy, nie wpływające na rozumienie treści przez człowieka, powodują wygenerowanie całkowicie odmiennych skrótów.

Rozwiązania oparte na funkcjach skrótu

Ze względu na efekt lawiny można łatwo uniknąć wykrycia pliku przez prostą funkcję skrótu, wprowadzając nieistotne zmiany w pliku, np. modyfikując formatowanie tekstu czy obcinając fragment zdjęcia niewidoczny dla ludzkiego oka. W pewnych sytuacjach, gdy bardziej istotna jest treść plików niż ich identyczność, może to być niepożądane (np. filtrowanie zabronionych treści w serwisach społecznościowych). Aby temu przeciwdziałać, na bazie funkcji hashujących opracowywane są bardziej złożone rozwiązania do identyfikacji plików.

Jednym z nich jest technologia PhotoDNA, stworzona przez Microsoft i udoskonalona przez Hany’ego Farida, wykładowcę informatyki z amerykańskiego Dartmouth College. Jak sama nazwa wskazuje, służy ona do identyfikowania plików graficznych, którym przydziela unikatowy identyfikator będący niejako odpowiednikiem kodu DNA pliku. Wyróżnia ją zastosowanie tzw. robust hashing – w celu wygenerowania hashu algorytm dzieli analizowane zdjęcie na kilka mniejszych fragmentów, dzięki czemu trudniej jest go oszukać, wprowadzając nieistotne zmiany w pliku.

Microsoft przekazał prawa do PhotoDNA amerykańskiej organizacji International Centre for Missing & Exploited Children, która korzystając z algorytmu stworzyła bazę hashów plików zidentyfikowanych jako zawierające pornografię dziecięcą. Baza jest wykorzystywana nie tylko przez organy ścigania, ale także przez wiele znanych firm internetowych, które zapobiegają w ten sposób pojawianiu się we własnych usługach treści zabronionych oraz zgłaszają takie przypadki odpowiednim organom. Jakiś czas temu branżowi giganci ogłosili plany wdrożenia podobnych mechanizmów filtrujących w odniesieniu do materiałów propagujących terroryzm (więcej można dowiedzieć się o tym tutaj i tutaj).

Na podobnej zasadzie działa system Content ID, wykorzystywany przez YouTube do wykrywania filmów i muzyki naruszających prawa autorskie. System ten sprawdza, czy filmik dodawany przez użytkownika nie zawiera utworów z bazy stworzonej na podstawie materiałów pochodzących od podmiotów praw autorskich. Już w 2010 roku Google podawało, że algorytm sprawdza „setki godzin filmów umieszczanych na YouTube każdej minuty”, z czym nigdy nie poradziłby sobie człowiek.

Jeżeli w dodawanym filmiku znajdują się cudze treści chronione prawem autorskim, właściciel praw jest o tym powiadamiany i może podjąć decyzję np. o usunięciu filmiku albo przekierowaniu na własną rzecz dochodów z jego wyświetlania. W praktyce system bywa krytykowany zarówno przez właścicieli treści (ich zdaniem często nie wykrywa treści naruszających ich prawa), jak i użytkowników serwisu (uważają oni, że systemowi zdarza się zablokować treści, których wykorzystywanie było zgodne z prawem). Ten ostatni problem w pewnej mierze wynika z samej zasady działania systemu, który jedynie sprawdza, czy w filmiku znajdują się treści występujące w bazie danych, pomijając przy tym kontekst, w jakim się one pojawiają.

Na algorytmach hashujących opiera się także działanie popularnej aplikacji Shazam, pozwalającej zidentyfikować piosenkę na podstawie jej krótkiego fragmentu. Jej twórcy stworzyli bazę danych zawierających cyfrowe sygnatury milionów utworów, które można szybko porównać z sygnaturą generowaną dla utworu „odsłuchiwanego” przez aplikację.

Krótko o innych zastosowaniach funkcji skrótu

Mając świadomość przydatności funkcji hashujących, warto pamiętać o ich wadach, takich jak np. konieczność przygotowania bazy hashów na podstawie plików przeanalizowanych przez człowieka czy łatwość „oszukania” funkcji przez prostą zmianę pliku. Dlatego opracowywane są także inne rozwiązania do identyfikacji plików. Interesującym przykładem są zwłaszcza systemy komputerowego rozpoznawania i przetwarzania obrazu – w istocie rodzaj sztucznej inteligencji, która uczy się samodzielnego „oglądania” zdjęć i potrafi opisać ich zawartość bez polegania na zewnętrznej bazie danych.

Jednak nawet jeśli funkcje hashujące zostaną zastąpione takim komputerowym „wzrokiem”, nadal będą zapewne wykorzystywane w wielu innych dziedzinach. Identyfikacja plików komputerowych to bowiem tylko jedno z wielu ich zastosowań. Poza tym funkcje hashujące są wykorzystywane np. w podpisach elektronicznych (podpisujemy nie plik, lecz właśnie jego hash), w kryptografii, do przechowywania haseł w serwisach internetowych, a także stanowią jeden z istotnych elementów technologii blockchain.

Rafał Kuchta