Odcisk palca w Twoich plikach

Trzech kryptografów ze Stanford University wymyśliło niedawno sprytne rozwiązanie uporczywego problemu kradzieży tożsamości w Internecie. Sprytni hakerzy z Rosji, Chin i innych krajów wysyłają stosy wiadomości e-mail, które wyglądają, jakby pochodziły z jakiejś instytucji finansowej, takiej jak Citibank lub Paypal. Miliony konsumentów otrzymują te wiadomości, które mają osadzone w nich łącza HTML, które przenoszą niczego niepodejrzewającego odbiorcę na podobne do siebie witryny działające w odległych miejscach. Zostaniesz poproszony o podanie nazwy użytkownika i hasła, a następnie haker ma klucze do twojego konta bankowego.

Ale dobre nazwy użytkownika i hasła wpisywane na złych stronach internetowych nie są jedynym zagrożeniem, z jakim borykają się konsumenci. Potencjalnie większym problemem jest to, że wiele osób używa tej samej kombinacji nazwy użytkownika i hasła w wielu witrynach. Ułatwia to zapamiętywanie, ale oznacza, że ​​pozbawiony skrupułów operator witryny może pobrać listę nazw użytkowników i haseł, powiedzmy, z witryny internetowej z loterią i użyć jej do włamania się na internetowe konta bankowe.

Tak więc kryptografowie ze Stanford, Blake Ross, Dan Boneh i John Mitchell, zaprojektowali sprytną wtyczkę do Internet Explorera, która rozwiązuje ten problem, mieszając to, co wpisujesz w polu hasła, aby każda witryna widziała inne hasło, które jest oparte na tym, co wpisujesz oraz w domenie samej witryny.

Teraz wiele osób używa jakiegoś wariantu tej strategii. Ich hasłem Hotmail może być nosmis-hotmail, podczas gdy ich Yahoo! Hasło towarzyskie to nosmis-Yahoo! Ale każda taka strategia jest dość łatwa do rozszyfrowania. Opracowana przez trio ze Stanford metoda szyfrowania haseł opiera się na funkcji matematycznej zwanej funkcją jednokierunkową typu hasha kryptograficznego, która przekształca to, co wpisuje użytkownik, w mieszaninę cyfr i liter w sposób, którego nie można odwrócić. Ponieważ system Stanford oblicza skrót kryptograficzny zarówno domeny strony internetowej, jak i hasła użytkownika, haker otrzymuje inne hasła niż te prawidłowe. (Kliknij tutaj aby znaleźć szczegółowe informacje na temat tego sprytnego rozwiązania.)

Jedną z firm, która używa skrótów kryptograficznych w sposób bardzo publiczny, jest Yahoo! W zeszłym roku Yahoo! przeprojektował proces logowania do swojej strony internetowej, aby był odporny na wąchanie. Standardowym sposobem na to jest użycie szyfrowania. Ale szyfrowanie może być powolne, zwłaszcza gdy korzystasz z jednej z najpopularniejszych witryn w Internecie.

Więc co z Yahoo! zamiast tego zmodyfikował swoją stronę logowania tak, aby korzystała z tak zwanego systemu wyzwań-odpowiedzi opartego na hashu kryptograficznym. Kiedy próbujesz się zalogować, serwer Yahoo!s pobiera do Twojej przeglądarki kryptograficzną funkcję skrótu napisaną w JavaScript. Wraz z tą funkcją wyzwaniem jest krótki ciąg liter i cyfr. Kiedy wpisujesz hasło na ekranie logowania, przeglądarka pobiera hasło, dołącza te znaki dostarczone przez Yahoo! i oblicza skrót kryptograficzny otrzymanego ciągu. Następnie przeglądarka wysyła wynikową wartość z powrotem do Yahoo!, bez konieczności szyfrowania. Nawet jeśli jesteś w kafejce internetowej, w której hakerzy z Belgii podsłuchują Twój ruch sieciowy, złoczyńcy nie mają możliwości przejęcia powstałej wartości skrótu i ​​uzyskania oryginalnego hasła.

Ten sprytny system odpowiedzi na wyzwanie jest również podstawą systemu Mobil Speedpass: to właśnie dlatego tag identyfikacji radiowej (RFID) Speedpass jest tak trudny do sklonowania. Inne systemy RFID nie wykorzystują odpowiedzi na wyzwanie, co sprawia, że ​​ich atakowanie jest stosunkowo łatwe.

Ale czym właściwie jest ta kryptograficzna funkcja skrótu?

Niezwykle użyteczny hasz

Funkcje skrótu kryptograficznego są jednym z podstawowych elementów budulcowych dzisiejszej gospodarki cyfrowej. Niemniej jednak pod wieloma względami pozostają tajemnicą zarówno dla kryptografów, którzy je tworzą, jak i dla ogółu społeczeństwa, który ich używa na co dzień.

Funkcje skrótu są czasami nazywane funkcjami odcisku palca, ponieważ mogą być używane do tworzenia unikalnego odcisku palca pliku cyfrowego. Odciski palców to zazwyczaj liczby 128-bitowe lub 160-bitowe, które są wyświetlane jako sekwencja cyfr szesnastkowych. Na przykład odcisk palca mojego nazwiska w systemie MD5 to c55bbe0f3ba258f5b1cb6d5b62b0b360. Funkcje skrótu są zaprojektowane tak, aby przynajmniej teoretycznie żadne dwa pliki nigdy nie miały tej samej wartości.

Abyś mógł zorientować się, jak działają te funkcje odcisków palców, umieściliśmy poniżej kalkulator MD5 oparty na JavaScript. Wystarczy wpisać jakiś tekst i zobaczysz skrót MD5. Zwróć uwagę, jak zmienia się on całkowicie za każdym razem, gdy dodajesz, usuwasz lub zmieniasz literę. Sposób, w jaki zmiany odcisków palców są nieprzewidywalne, rzeczywiście, gdybyśmy mogli przewidzieć, jak się zmienią, odciski palców nie byłyby zbyt przydatne.

Wpisz swój tekst poniżej:

MD5 to:

Większość używanych obecnie funkcji skrótu opiera się na technice opracowanej przez profesora MIT Rona Rivesta w latach 80. XX wieku. (Rivest jest prawdopodobnie najbardziej znany jako R w algorytmie szyfrowania RSA, algorytmie szyfrowania klucza publicznego, który jest wbudowany praktycznie w każdą przeglądarkę internetową.) W tamtym czasie Rivest i inni matematycy opracowywali szczegóły podstawowych operacji kryptograficznych, które teraz bierz za pewnik. Funkcje skrótu zostały wymyślone jako rodzaj kryptograficznego systemu kompresji, który umożliwia rozdrobnienie dużego pliku do krótkiego ciągu liter i cyfr.

Pomysł polegał na wykorzystaniu tych odcisków palców jako swego rodzaju substytutu samych plików. Zamiast podpisywać cyfrowo cały plik, rozumowali Rivest i inni, można cyfrowo podpisać skrót. Ponieważ kryptografia z kluczem publicznym wiąże się z dużą ilością skomplikowanej matematyki, funkcje skrótu sprawiają, że podpisanie bardzo długiego pliku jest prawie tak samo szybkie, jak podpisanie krótkiego pliku.

Jedną z najbardziej podstawowych rzeczy, które można zrobić za pomocą funkcji skrótu, jest sprawdzenie, czy plik się zmienił: po prostu oblicz skrót pliku i zapisz go. Później ponownie obliczasz hash. Jeśli hash się nie zmienił, to szanse są przytłaczające, że plik również się nie zmienił.

Załóżmy na przykład, że utrzymujesz finanse swojej małej firmy za pomocą QuickBooks i chcesz wyjechać na wakacje na kilka dni: ludzie muszą korzystać z twojego komputera, ale chcesz mieć pewność, że nikt nie zmodyfikuje danych QuickBooks. Jedną prostą rzeczą, którą możesz zrobić, jest obliczenie skrótu kryptograficznego pliku przed wyjściem i zapisanie numeru na karcie indeksu. Kiedy wrócisz z wakacji, po prostu ponownie oblicz hash. Jeśli te dwie wartości nie pasują, wiesz, że plik został naruszony.

Oczywiście nie musisz poprzestać na jednym pliku. Możesz obliczyć skrót kryptograficzny każdego pliku na komputerze i umieścić je wszystkie w nowym wywołaniu pliku hashes.txt. Następnie możesz obliczyć hash pliku hashes.txt i zapisać ten odcisk palca na swojej karcie notatek. Powtórz ten proces, gdy wrócisz z wakacji, a będziesz miał szybki sposób sprawdzenia, czy jakiś plik na całym komputerze uległ zmianie. (Nie będziesz wiedział, który plik się zmienił, ale to inny problem.)

Pomysł obliczania skrótu skrótu jest podstawą systemu wykrywania włamań o nazwie Tripwire, który został wynaleziony na początku lat 90. przez profesora informatyki z Purdue University Gene Spafforda i jego doktoranta Gene Kima. (Spafford i ja jesteśmy współautorami pięciu książek na temat informatyki.) Obecnie wiele różnych programów wykorzystuje podejście Tripwire, aby zapewnić integralność plików komputerowych i baz danych.

Obliczanie skrótów haszów jest również podstawą bezpiecznej usługi znaczników czasu, wymyślonej przez Stuarta Habera i Scotta Stornettę, gdy obaj byli w Bellcore w 1990 roku. Usługa o nazwie Surety umożliwia wygenerowanie bezpiecznego kryptograficznie i niepodrabialnego dowodu, że dany dokument , zdjęcie lub inny plik istniał w określonym czasie w określonym dniu i od tego czasu nie został zmieniony.

Technika Surety polega na obliczeniu drzewa skrótu na podstawie kodów skrótu każdego dokumentu oznaczonego znacznikiem czasu. Korzeń drzewa jest następnie publikowany w dobrze znanej lokalizacji, może być na przykład wydrukowany w ogłoszeniu New York Times . Możesz udowodnić, że Twój dokument istniał w danym dniu, pokazując, że odcisk Twojego dokumentu był potrzebny do wygenerowania odcisków palców, które pojawiły się w gazecie.

Inne firmy, a nawet US Postal Service, od tego czasu stworzyły własną usługę elektronicznego znacznika czasu. Ale wszystkie te systemy opierają się na organizacji, która działa jako zaufana strona trzecia, która w efekcie podpisuje dokument przy użyciu swojego klucza prywatnego. Problem z tym podejściem polega na tym, że strona trzecia musi być całkowicie godna zaufania: jeśli ta strona trzecia zdecyduje się utworzyć podpis z niewłaściwą datą lub jakiś haker zdoła ukraść klucz prywatny strony trzeciej, nie ma możliwości, aby odróżnić fałszywy podpis od prawidłowego. Oczywiście możliwe jest również tworzenie fałszywych podpisów Poręczyciela, ale musisz albo cofnąć się w czasie i zmienić to, co zostało wydrukowane w New York Times lub podróżować po całym świecie, znaleźć każdą wydrukowaną kopię i zmienić stare odciski palców na nowe.

Jak działają funkcje skrótu

Dlatego właśnie funkcje skrótu są pomocne. Zobaczmy teraz, jak faktycznie wyglądają.

Wśród najczęściej używanych obecnie funkcji skrótu znajduje się tak zwany MD5 (od Message Digest #5). MD5 tworzy skrót o długości 128 bitów, który jest zwykle zapisywany jako sekwencja 32 cyfr szesnastkowych (o podstawie 16). Gdybyś wziął moje imię i przetworzył je za pomocą MD5, otrzymałbyś ten pozornie losowy ciąg:

c55bbe0f3ba258f5b1cb6d5b62b0b360

Lub, mówiąc bardziej matematycznie:

MD5 (Simson Garfinkel)= c55bbe0f3ba258f5b1cb6d5b62b0b360

Każdy z tych znaków szesnastkowych reprezentuje 4 bity; wartość MD5 mojego imienia to w rzeczywistości:

1100010101011011101111100000111100111011101
00010010110001111010110110001110001011011011
010101101101100010101100001011001101100000

Większość ludzi pracuje z reprezentacją szesnastkową, ponieważ dość łatwo jest spojrzeć na dwa skróty i stwierdzić, czy są one takie same, czy różne.

MD5 działa, dzieląc plik na wiele małych części, a następnie biorąc każdy z tych fragmentów i wykonując setki operacji matematycznych, które tasują, odwracają, transponują i w inny sposób przetwarzają bity w nierozpoznawalny bałagan. Słowo „nierozpoznawalny” w tym opisie jest kluczowe. Podstawowym wymogiem dobrej funkcji mieszającej jest to, że nie powinno być możliwe przewidzenie odcisku palca pliku bez faktycznego wysiłku polegającego na obliczeniu, że odcisk palca nie może być skrótów. Gdyby tak było, mógłbyś być w stanie uruchomić funkcję skrótu wstecz i utworzyć plik, który miał określony skrót, na przykład skrót innego pliku. Rzeczywiście, całe bezpieczeństwo funkcji skrótu całkowicie się rozpada, jeśli możliwe jest wygenerowanie dwóch plików, które mają ten sam skrót.

Piękno funkcji mieszającej polega na tym, że nawet niewielka modyfikacja danych wejściowych powoduje dramatyczną zmianę danych wyjściowych. Matematycznie funkcje są zaprojektowane tak, aby każdy bit na wyjściu miał 50 procent szans na zmianę dla każdego bitu zmienionego na wejściu.

Spójrzmy na inny skrót MD5, ten z nieco innej reprezentacji mojego imienia:

MD5 (Simson L. Garfinkel)= df876e8e6f548d5be698fab7f06dd278

Samo dodanie L. daje zupełnie inny hasz. Jeśli porównasz te dwa skróty bit po bicie, zobaczysz, że 63 ze 128 pozycji zmieniło się z 0 na 1 lub z 1 na 0, a pozostałe 65 pozostały niezmienione.

Niestety cała teoria kryptograficznych funkcji skrótu ma ogromny problem. Korzystanie z tych funkcji wymaga, aby nie było tak zwanych kolizji. Przypadkowo lub celowo nie powinno być dwóch plików, które mają ten sam kryptograficzny odcisk palca. I jak się okazuje, jest to warunek niemożliwy.

Powód jest dość prosty. Odciski palców pliku mają stały rozmiar, co oznacza, że ​​istnieje skończona liczba możliwych odcisków palców. Z drugiej strony pliki mogą mieć dowolny rozmiar. W związku z tym istnieje więcej możliwych plików niż odcisków palców, a zatem musi istnieć co najmniej jeden odcisk palca, który jest odciskiem palca wielu plików. Terminem matematycznym na to jest zasada szufladki. Rzeczywiście, nawet jeśli ograniczysz się do plików, które mają zaledwie dziewięć znaków, nadal liczba możliwych plików jest 256 razy większa niż liczba możliwych odcisków palców.

Powodem, dla którego zasada szufladkowania nie czyni funkcji haszujących całkowicie bezsensownymi, jest fakt, że istnieje zdumiewająca liczba możliwych odcisków palców, w rzeczywistości znacznie większa niż liczba plików na planecie. (W przypadku MD5 istnieje 2128 możliwych odcisków palców. Teraz całkowita liczba dysków twardych do komputerów, które kiedykolwiek wyprodukowano, wynosi tylko około 229. Gdyby każdy dysk twardy miał milion unikalnych plików, co jest rażącym przeszacowaniem, nadal byłoby tylko 249 pojedynczych plików. To dużo. , dużo, dużo mniej niż 2128.)

Kontrowersje SHA-1

Do celów samouczka użyłem funkcji skrótu MD5. Ale w dzisiejszych czasach rozważa się MD5 podawać zamiast tego większość świata przechodzi na bezpieczny algorytm haszowania rządów USA, znany jako SHA-1, standard przyjęty przez National Institutes of Standards and Technology (NIST) na początku lat dziewięćdziesiątych.

Dziś SHA-1 jest powszechnie szanowanym algorytmem, ale ma burzliwą historię. W 1993 roku rząd USA próbował nakłonić przemysł do przyjęcia tak zwanego tajnego systemu szyfrowania Clipper Chipa zaprojektowanego przez Narodową Agencję Bezpieczeństwa. Podczas tak zwanych wojen kryptograficznych, które szalały wokół Clippera, NIST zaproponował rządowi USA przyjęcie własnego algorytmu Secure Hash jako części Federalnych Standardów Przetwarzania Informacji. Ze względów technicznych funkcje skrótu powinny mieć dwa razy więcej bitów niż algorytmy szyfrowania, z którymi pracują. Clipper był 80-bitowym algorytmem szyfrowania, więc standard został zaprojektowany do tworzenia 160-bitowego odcisku palca.

Można by pomyśleć, że rządowy standard ze swoim 160-bitowym odciskiem palca byłby bezpieczniejszy niż 128-bitowy MD5. Ale podobnie jak sam Clipper, SHA został zaprojektowany przez Narodową Agencję Bezpieczeństwa i zarówno NIST, jak i NSA odmówiły wyjaśnienia zasad, które zostały użyte w jego projekcie. Niektórzy zastanawiali się, czy NSA mogła ukryć jakieś tylne drzwi wewnątrz algorytmu, aby agencja mogła generować kolizje na żądanie. Takie tylne drzwi można wykorzystać na przykład do tworzenia sfałszowanych podpisów cyfrowych, co może się przydać CIA. Fałszywy podpis cyfrowy może zostać wykorzystany na przykład do podpisania elektronicznego zamówienia, które daje szpiegowi amerykańskiemu dostęp do bazy danych w obcym kraju.

Wielu kryptografów i innych naukowców przeanalizowało algorytm SHA i nie mogło znaleźć w nim niczego złego. 11 maja 1993 r. NIST ogłosił SHA jako narody Secure Hash Algorithm. Ale atrament ledwo wysechł na tym dekrecie, kiedy NIST ogłosił, że popełnił błąd. Z powodów, które nie zostały wówczas ujawnione, NIST opublikował zmodyfikowaną wersję algorytmu Secure Hash Algorithm, który teraz nazywamy SHA-1.

Teoretycy spiskowi w społeczności kryptograficznej (a jest ich wielu) mieli dzień w terenie. Czy SHA była tak potężna, że ​​NSA zdecydowała, że ​​trzeba ją uprościć? A może NSA umieściła tylne drzwi w SHA i ktoś z NIST się dowiedział? Czy oba algorytmy były równie bezpieczne, a kryptografowie z NSA po prostu mieszali w umysłach ludzi?

W sierpniu 1998 roku świat mniej więcej poznał odpowiedź na zagadkę SHA vs. SHA-1. Florent Chabaud i Antoine Joux, dwaj francuscy kryptografowie, opracowali teoretyczny atak na pierwszą wersję ataku SHAan, przed którym SHA-1 akurat była zabezpieczona. Prawie na pewno ludzie z NSA wiedzieli o tym ataku i zaproponowali SHA-1 jako środek zaradczy. Co ciekawe, kryptografowie NSA prawdopodobnie nie wiedzieli o ataku, kiedy SHA został po raz pierwszy zaproponowany w 1993 roku, co oznacza, że ​​najlepsza na świecie agencja kryptograficzna wyprzedziła kryptografów w środowisku akademickim tylko o pięć lat.

Obecnie funkcje skrótu są również powszechnie używane do generowania powtarzalnych, ale nieprzewidywalnych liczb losowych, do konwersji wpisanych haseł na wartości odpowiednie do wykorzystania jako klucze szyfrowania. Zamiast przechowywać hasła bezpośrednio, wiele systemów komputerowych przechowuje skrót hasła. Uniemożliwia to osobie, która włamuje się do komputera, poznanie hasła każdego użytkownika.

Funkcje skrótu zostały zaproponowane jako sposób na walkę ze spamem i jako podstawa cyfrowych systemów gotówkowych. Matematyk Peter Wayner opublikował książkę pt Przezroczyste bazy danych kilka lat temu, w którym pokazał, w jaki sposób można wykorzystać funkcje skrótu do przechowywania informacji w bazie danych w sposób chroniony przez organizację prowadzącą bazę danych. Na przykład wydział przyjęć na uczelnię mógłby przechowywać numery ubezpieczenia społecznego studentów w bazie danych, tak aby numery te nadal mogły być używane jako identyfikatory we wnioskach, ale aby nikt w biurze przyjęć nie mógł usiąść przy terminalu i uzyskać listy studentów i ich liczba. Jak dotąd jednak żadne z tych podejść nie wyszło tak naprawdę na dobre.

Podsumowując, skróty kryptograficzne są jedną z najciekawszych i najbardziej użytecznych technik matematycznych, jakie kryptografowie wymyślili w ciągu ostatnich 20 lat i wciąż znajdują dla nich nowe zastosowania.

ukryć