captcha image

A password will be e-mailed to you.

Jesteśmy geekami, ale nawet tacy jak my robią od czasu do czasu coś fajnego – i tak właśnie w naszej firmie zrodził się spontaniczny projekt pt. „Łamiemy kod Enigmy”. Wykorzystaliśmy naszą wiedzę, pasję i sztuczną inteligencję do pokonania Enigmy: najważniejszej maszyny wojennej hitlerowskich Niemiec.

Dziś łamy Crazy Nauki oddajemy Łukaszowi Kuncewiczowi, który wraz ze swoimi kolegami z firmy Enigma Pattern Inc. wpadł na pomysł, żeby złamać kod Enigmy przy pomocy algorytmów uczenia maszynowego i sztucznej inteligencji. Zobaczcie, co im z tego wyszło i oceńcie, czy dobrze zainwestowali swój czas i 7 dolarów.

Crazy Nauka

Enigma (zdjęcie: Bundesarchiv, Bild 183-2007-0705-502 / Walther / CC-BY-SA 3.0)

Być może niektórzy pamiętają ze szkoły, że podczas II Wojny Światowej, Niemcy oraz współpracujące z nimi kraje używały Enigmy do szyfrowania wiadomości. Były to urządzenia wielkości przenośnej maszyny do pisania, korzystające z ciągle zmieniającego się szyfru polialfabetycznego. Przemyślna konstrukcja tych maszyn powodowała, że były uważane za niemożliwe do złamania, i hitlerowcy używali ich jako podstawowego zabezpieczenia komunikacji, przesyłając zakodowane przez Enigmy rozkazy i raporty z wojny na terenach państw osi. Zanim opiszemy, jak z Enigmą poradziła sobie sztuczna inteligencja, musimy cofnąć się w czasie.

Czy trudno było złamać Enigmę osiemdziesiąt lat temu?

Cóż… przez długi czas było to uważane za niemożliwe. Praca Enigm polegała na wykorzystaniu oryginalnej wiadomości, i zamiany w bardzo skomplikowany sposób poszczególnych jej liter, przy wykorzystaniu pewnego uzgodnionego wcześniej, tajnego hasła. Ta podmiana liter była na tyle skomplikowana, że nawet jeśli wróg przechwyciłby samą maszynę oraz zakodowaną nią wiadomość, nie mógłby odtworzyć wiadomości oryginalnej bez znajomości wspomnianego wcześniej hasła. W latach trzydziestych niektóre państwa w Europie aktywnie nasłuchiwały niemieckich transmisji z zakodowanymi informacjami, próbując odczytać te wiadomości. Ponieważ Niemcy zmieniali hasła parę razy dziennie, działania te okazywały się bezskuteczne. Sytuacja wydawała się beznadziejna to tego stopnia, że wywiad francuski przekazał Polsce parę zdobytych Enigm, sądząc że są one i tak bezużyteczne dla francuskich lingwistów łamiących szyfry.

Francuzi mieli rację. Polski rząd zaproponował zupełnie inne podejście – zamiast lingwistów zatrudnił młodych, zdolnych matematyków. W 1932 roku Marian Rejewski, Jerzy Różycki i Henryk Zygalski wymyślili sposób na deszyfrowanie niemieckich komunikatów – stworzyli tzw. bomby kryptologiczne. Były to urządzenia swoją wielkością przypominające współczesne pralki, które naśladowały sposób działania samej Enigmy i wypróbowywały wszystkie możliwe kombinacje haseł. Niestety, wraz z coraz bardziej udoskonalaną konstrukcją niemieckich maszyn szyfrujących, bomby musiały być coraz większe, a znajdowanie haseł trwało coraz dłużej. Zbyt długo by to miało jakąś wartość.

Enigma 1941 (zdjęcie: Bundesarchiv, Bild 146-2006-0188 / Lücke / CC-BY-SA 3.0)

Polacy zmuszeni byli oddać projekt Brytyjczykom, którzy mieli większe zaplecze finansowe i techniczne, a dodatkowo mogli oddelegować do prac nad tym projektem więcej ludzi.
Po stronie brytyjskiej projekt prowadził Alan Turing. Rozszerzył on koncepcję Polaków, zbudował znacznie większe bomby oraz wprowadził genialne metody zmniejszenia liczby haseł, dzięki czemu bomby zaczęły znów zaczęły znajdować hasła w ciągu godzin, a nie tygodni. Ten mariaż ludzkiej intuicji i maszynowej szybkości pozwalał cały czas być o krok przed zmieniającymi Enigmy Niemcami. Szacuje się, że złamanie szyfru Enigmy ocaliło życie od 14 do 21 milionów ludzi, i skróciło wojnę o 2 lata.

Czy sztuczna inteligencja może być lepsza od geniuszy informatyki?

To pewnie nie jest dobre pytanie, bo dzisiejsza sztuczna inteligencja jest jeszcze bardzo daleko od bycia inteligentną – ale być może jest na tyle sprytna, że da się tę różnicę „zasypać” poprzez wykorzystanie aktualnych zdobyczy techniki? Przez te ponad osiemdziesiąt lat prędkość obliczeń niewyobrażalnie wzrosła – może więc da się to wykorzystać i, stosując nawet bardzo „nieinteligentną” sztuczną inteligencję, dorównać Rejewskiemu, Różyckiemu, Zygalskiemu i Turingowi?

Nasz plan składał się z dwóch kroków. Po pierwsze, nauczyliśmy sztuczną inteligencję rozpoznawać język niemiecki. Karmiliśmy ją bajkami braci Grimm i po kilkugodzinnym trawieniu tych historii, zaczęła ona być coraz pewniejsza w swoich klasyfikacjach.

Tak wyglądają wiadomości zdekodowane przy użyciu różnych haseł. Zaznaczyliśmy prawidłową wiadomość (zdanie po niemiecku).

Po drugie, wybraliśmy najbardziej skomplikowany model Enigmy (czterodyskowy model używany na U-botach, z jedną parą wtyczek, co dało nam potężny zbiór 15 354 393 600 różnych haseł do przetestowania), i napisaliśmy jej symulator. Tak jak w przypadku oryginalnych bomb, symulator testował każde z możliwych haseł – u nas różnica polegała na tym, że nie próbowaliśmy zmniejszać ich ilości (brakuje nam sporo do matematycznych talentów Rejewskiego czy Turinga), zamiast tego postawiliśmy na wykorzystanie prędkości aktualnych komputerów.

O ile w 1932 roku w rozszyfrowaniu niemieckiej maszyny pomógł geniusz człowieka i bardzo powolne maszyny, to 85 lat później stało się to zasługą superszybkich maszyn i prostej sztucznej inteligencji, która była w stanie odróżnić język niemiecki od przypadkowych liter. Wystarczyło nauczyć AI, jak wyglądają niemieckie słowa, by ta na wyjściu bomby kryptologicznej potrafiła odróżnić bełkot (złe hasło) od języka Goethego (hasło poprawne).

Ciągle pamiętam ten moment, gdy włączyliśmy naszą bombę po raz pierwszy… Po paru minutach dwie rzeczy stały się jasne. Dobra wiadomość była taka, że projekt działał: symulator Enigmy testował hasła po kolei, a sztuczna inteligencja wyłapywała wiadomości wyglądające na język niemiecki. Zła wiadomość była taka, że bomba działa zbyt wolno: szukanie hasła miało potrwać dwa tygodnie.

Jak skrócić dwa tygodnie do 19 minut

Enigma to tak naprawdę dosyć skomplikowana maszyna i chociaż dzięki temu bardzo dobrze szyfruje wiadomości, to jednak kodowywanie (i odkodowywanie) wiadomości chwilę trwa. Sprawdzanie, czy dany tekst jest po niemiecku, też trochę zajmuje. Normalnie jest to niewyczuwalne, ale jeśli buduje się bombę kryptologiczną testującą miliardy haseł, to cała procedura testowania zaczyna trwać tygodnie.

Ostateczne sprawdzenie wiadomości przez sztuczną inteligencję – widać rozszyfrowane wiadomości oraz prawdopodobieństwo, że dana wiadomość jest po niemiecku.

Musieliśmy znaleźć metodę, jak skrócić czas pracy bomby przynajmniej tysiąckrotnie. Mieliśmy szczęście – jeszcze parę lat temu nie byłoby to takie proste, ale obecnie można wynajmować komputery nie tylko na miesiące, ale także na godziny, minuty czy nawet sekundy… Jeśli naszemu komputerowi znalezienie hasła zajęłoby dwa tygodnie, to gdybyśmy rozłożyli tę pracę na tysiąc maszyn, całość powinna zakończyć się w… mniej niż godzinę!

Skontaktowaliśmy się z DigitalOcean i poprosiliśmy o udostępnienie ich tysiąca wirtualnych serwerów. Dali nam zielone światło, a my przygotowaliśmy naszą bombę do równoległego przetwarzania danych. Rozesłaliśmy paczki haseł dla każdego z serwerów, i… udało się! Całość zakończyła się po 19 minutach, rozpędzając się do całkiem okazałej prędkości 13 milionów sprawdzeń haseł na sekundę.

Czyli… każdy szyfr można tak złamać

Tak naprawdę pewnie niektórzy z nas myślą teraz o szyfrach bankowych i o tym, czy ich pieniądze są bezpieczne. Pomijając sprawdzone i niesprawdzone historie o możliwościach takich amerykańskich agencji jak National Security Agency, nasza odpowiedź na pytanie o złamanie szyfru bankowego jest taka: Testowana przez nas wersja Enigmy posiadała 15 354 393 600 możliwych haseł, które zapisane w systemie dwójkowym wymagały do ich policzenia tylko 34 cyfry. Dzisiejsze systemy bankowe używają kluczy (haseł) przynajmniej 128-cyfrowych – więc nawet jeśli łamalibyśmy trylion (1 000 000 000 000 000 000) haseł na sekundę, to wciąż zajęłoby to więcej niż bilion (1 000 000 000 000) lat. Myślę, że wszyscy możemy nadal spać spokojnie.

Ile kosztuje wypożyczenie tysiąca serwerów na godzinę?

$7. Tak. Dosłownie 7 dolarów amerykańskich, czyli jakieś 30 zł. Dla porównania wypada napisać, że brytyjska bomba kosztowała ponad pół miliona dzisiejszych funtów (2,4 mln zł). A zatem niech żyje przetwarzanie równoległe!

Jeśli interesuje Was, jakich technologii użyliśmy i jak teraz, już po projekcie, zrobilibyśmy go lepiej, zapraszamy tutaj: https://github.com/EnigmaPatternInc/EnigmaCode

Zdjęcie otwierające: TedColes; domena publiczna

Nie ma więcej wpisów