%^ef$g73$5r(@&#!! - Kilka słów o szyfrowaniu i algorytmach

%^ef$g73$5r(@&#!! - Kilka słów o szyfrowaniu i algorytmach

Maciej Ziarek
Analityk zagrożeń, Kaspersky Lab Polska

Czym jest szyfrowanie? Definicji tego terminu jest wiele, jedne są bardziej szczegółowe i skomplikowane inne prostsze, jednak wystarczające jest stwierdzenie, że szyfrowanie to po prostu metoda zapisu tekstu jawnego w taki sposób, by stał się on nieczytelny dla osób trzecich i jednocześnie z powrotem jawny po właściwej weryfikacji. Kryptografia nie została zapoczątkowana wraz z erą komputeryzacji. Co prawda to dzięki coraz większej mocy obliczeniowej komputerów powstają lepsze i skuteczniejsze szyfry i obecnie jest to z pewnością domena informatyki, jednak kryptografia istniała już tysiące lat temu. Zanim przejdziemy do opisu współczesnej kryptografii zapoznamy się z kilkoma dawnymi metodami szyfrowania.

Szyfry dawniej

Szyfr Cezara

Jest to jeden z najstarszych znanych szyfrów, który jak nazwa wskazuje był stosowany przez rzymskiego wodza, Juliusza Cezara. Stosował on tę metodę zabezpieczania przed wysłaniem ważnych wiadomości, np. poprzez gońca. Miało to uniemożliwić lokalizację wojsk w przypadku przechwycenia informacji. Jego działanie polega na zastępowaniu litery właściwej, znakiem znajdującym się 3 miejsca dalej w alfabecie. Szyfry, których działanie polega na podstawianiu jednej litery w miejsce drugiej, nazywamy szyframi podstawieniowymi. Jedną z ich wariacji są szyfry monoalfabetyczne (do nich zalicza się szyfr Cezara) czyli takie, w których każda litera tekstu przed kodowaniem ma swój odpowiednik w literze tekstu zakodowanego.

ROT13

Jest to szyfrowanie polegające na przesuwaniu liter o 13 znaków w prawo w alfabecie, począwszy od szyfrowanej litery. Działanie szyfru było zatem bardzo proste i nie zapewniał on należytej ochrony. Obecnie stosuje się go raczej jako ciekawostkę lub do zakodowania mało ważnych informacji. Małe i duże litery nie są rozróżniane. Na poniższym przykładzie widać, że mechanizm jest bardzo podobny do szyfru Cezara i różni się jedynie wartością przesunięcia.

ADFGVX

Ten szyfr o dziwnie brzmiącej nazwie został użyty przez Niemcy w czasie I Wojny Światowej do szyfrowania rozkazów i wytycznych. Jest to udoskonalona wersja szyfru ADFGX. Zasada jego działania opiera się na nadaniu każdej literze tekstu szyfrowanego pary liter A, D, F, G, V lub X. Następnie tworzone jest słowo kluczowe, aby dodatkowo utrudnić kryptoanalizę. Całość zbudowana jest z tabelki, z literami i cyframi w środku. Osoba, do której wysyłano wiadomość musiała znać zarówno słowo kluczowe jak i rozmieszczenie liter w tabeli. Obrazuje to lepiej poniższy przykład.

Zaszyfrujmy słowo Kaspersky. W tym celu łączymy litery w pary:

K - FV
A - GX
S - AG
P - AV
E - VA
R - VD
S - AG
K - FV
Y - XF

Kolejnym krokiem jest wybranie hasła - my wybierzemy słowo SZYFR. Następnie przepisujemy w jednym ciągu do nowej tabelki, pary liter z tabeli znaków ADFGVX. Każda kolumna musi mieć tyle samo liter, zatem jeżeli będzie ich brakowało, należy je dopisać. Tak też i w tym wypadku, zatem dwa ostatnie znaki w tabeli to cyfra 0.

Ostatnim krokiem jest ułożenie kolumn z literami hasła w kolejności alfabetycznej.

Teraz możemy już przepisać zaszyfrowane słowo z ostatniej tabelki, w tym celu przepisujemy litery po w kolejności od lewej do prawej. Powstały ciąg znaków dla dodatkowego utrudnienia dzielimy po 6 pozycji (ADFGVX).

One Time Pad

Jest to szyfr idealnie bezpieczny, nie istnieje metoda złamania go (wliczając w to metodę brute force czyli podstawiania każdego znaku w celu ustalenia poprawnej kolejności). Został stworzony w roku 1917 przez Gilberta Vernama. Obecnie istnieją dwie wersje szyfru - binarna oraz zwykła, znakowa. Różnią się one metodą szyfrowania tekstu - w jednej wykorzystuje się algorytm XOR, a w drugim Vigenere'a. To co sprawia, że hasło jest niespotykanie skuteczne to jego długość (taka sama, jak długość wiadomości), losowość oraz fakt, że może być użyte tylko jeden raz. Odpowiedź dla nadawcy jest generowana przy użyciu nowego klucza. Zarówno algorytm XOR jak i Vigenere'a są szyframi podstawieniowymi, jednak spełnienie trzech wcześniejszych warunków zapewnia całej metodzie szyfrowania bezwarunkowe bezpieczeństwo. W przykładzie użyję metody binarnej, a więc z zastosowaniem operatora logicznego XOR.

XOR to inaczej kontrawalencja lub alternatywa wykluczająca. Jeżeli p lub q jest prawdziwe (posiada wartość 1) to całe wyrażenie jest również prawdziwe.

Zatem w celu zaszyfrowania wiadomości Kaspersky na początku musimy zapisać ją w systemie binarnym. Oczywiście w praktyce wiadomość (np. treść listu) byłaby dłuższa, a co za tym idzie bezpieczniejsza, biorąc po uwagę fakt, że klucz będzie miał taką samą długość jak wiadomość.

Mając już wiadomość w systemie dwójkowym, należy jeszcze wygenerować hasło. Musi ono jednak zostać stworzone w sposób całkowicie losowy, a wbrew pozorom nie jest to zadanie łatwe. Istnieją wprawdzie generatory liczb pseudolosowych, jednak - jak wskazuje nazwa - ich użycie nie daje całkowitej losowości i pozwala na wykrycie pewnych regularności, okresowości. Najlepszym rozwiązaniem jest użycie generatora bazującego np. na przypadkowości i zmienności temperatury podzespołów komputerowych (takich jak procesor). Dla naszego przykładu wygenerowane zostały liczby:

Teraz należy wykonać operację XOR:

Nasza wiadomość jest teraz zaszyfrowana w następującej postaci:

Biorąc po uwagę fakt, że wygenerowane hasło byłoby użyte tylko raz, liczby są losowe a długość hasła odpowiada długości wiadomości szyfrowanej, mamy znamiona szyfrowania OTP (ang. One Time Password - hasło wykorzystywane jest tylko raz i traci ważność po wykorzystaniu). Próby łamania tego hasła zakończą się niepowodzeniem, ponieważ bez znajomości klucza nie da się odtworzyć wiadomości pierwotnej. Wynika to z faktu, że kryptogram jest tak samo losowy jak klucz. Znając wynik działania operacji XOR możemy jedynie przypuszczać i podstawiać kolejne znaki a z nich wyliczać hasło, jednak bez wiedzy, czy podstawiony znak jest prawdziwy nie zdołamy odgadnąć hasła, tym bardziej, że zostanie użyte tylko raz. Nie będzie więc można przeprowadzić kryptoanalizy na podstawie częstotliwości występowania pewnych symboli lub układów symboli (jak robi się to w przypadku szyfrów podstawieniowych). Będą się one zmieniały z każdą kolejną wiadomością.

Algorytmy współczesne

Przejdźmy teraz do algorytmów wykorzystywanych w dzisiejszych czasach. Na początku zapoznamy się z różnicą pomiędzy szyfrowaniem symetrycznym a asymetrycznym. Później przejdziemy do krótkiego opisu algorytmu AES oraz RSA, przy czym ten drugi pokażę bardziej szczegółowo, włączając w to przykład.

Kryptografia symetryczna

Swoją nazwę zawdzięcza temu, że większość szyfrów opartych o kryptografię symetryczną zawiera jeden klucz do kodowania i odkodowywania wiadomości. Możemy tu wprowadzić dodatkowy podział na szyfry blokowe i strumieniowe, gdzie blokowe dzielą wiadomość na bloki danych i dopiero wtedy przechodzą do właściwego szyfrowania, a szyfry strumieniowe przekształcają każdy bit wiadomości tak, jak dyktuje to algorytm. Problematyczna czasami staje się dystrybucja klucza, bowiem aby dać możliwość odszyfrowania wiadomości, musimy danej osobie przekazać klucz. Zatem siła kryptografii symetrycznej leży głównie w kluczu.

Kryptografia asymetryczna

Jest dzisiaj szeroko stosowana chociażby do składania podpisów cyfrowych. Polega ona na tworzeniu w procesie szyfrowania tekstu pary kluczy, prywatnego i publicznego. Klucz prywatny jest przeznaczony tylko dla nas. Możemy nim podpisywać wiadomość i tym samym uwierzytelniać ją. Klucz publiczny jest ogólnie dostępny i każdy adresat może dzięki niemu sprawdzić, między innymi, czy wiadomość jaką otrzymał nie była w międzyczasie modyfikowana. Kluczem publicznym można też szyfrować wiadomości i w takim wypadku do deszyfrowania posłuży już klucz prywatny.

Przedstawicielem szyfrów symetrycznych jest AES. Jest finalistą konkursu, który został ogłoszony, by zastąpić przestarzały już i zapewniający zbyt małe bezpieczeństwo standard DES. AES używa kluczy o długości 128, 196 i 256 bitów. Jest algorytmem operującym na blokach o zmiennej długości, a biorąc pod uwagę fakt, że i same klucze są różnej długości, zapewnia bardzo wysoki poziom bezpieczeństwa.

Działanie współczesnego algorytmu szyfrującego przedstawię na przykładzie RSA. Nie opisywałem go wcześniej, ponieważ chcę go pokazać trochę bardziej szczegółowo niż pozostałe algorytmy, dodając do tego przykład szyfrowania nim tekstu.

RSA jest czasami nazywany algorytmem Rivest, Shamir, Adleman - od nazwisk twórców. Jest to pierwszy algorytm bazujący na kryptografii asymetrycznej, o której pisałem wcześniej. Ten fakt sprawił, że RSA jest chętnie używany do podpisów cyfrowych. Trzej wymienieni twórcy, starali się znaleźć praktyczne rozwiązanie zaproponowanej przez Diffiego i Hellmana koncepcji używania kluczy publicznych i prywatnych do szyfrowania. Po zastosowaniu pewnych modyfikacji, udało się zrealizować dotąd nieosiągalną ideę udostępniania wszystkim użytkownikom jednego klucza, a szyfrowania drugim, indywidualnym.

Zanim przejdę do przykładu obrazującego szyfrowanie tekstu algorytmem RSA w praktyce, zapoznajmy się z symbolami używanymi we wzorach oraz z metodami ich wyliczania.

p - 1 duża liczba pierwsza
q - 2 duża liczba pierwsza
(liczby pierwsze mają jako dzielnik liczbę 1 oraz samą siebie)

n - iloczyn dużych liczb pierwszych
(w 256 bitowym szyfrowaniu otrzymujemy liczbę cyfr dla n powyżej 300)

m - wiadomość zapisana jako liczba

e - klucz szyfrujący będący liczbą względnie pierwszą dla iloczynu (p-1)(q-1), a także e < n
(liczby względnie pierwsze mają jako wspólny dzielnik liczbę 1)

Klucz prywatny (klucz deszyfrujący) - stanowią go liczby d oraz n, gdzie d wyliczamy według wzoru:

Klucz publiczny - stanowią go liczby n oraz e

Szyfrowanie:

Deszyfrowanie:

Oto jak przebiega proces szyfrowania. Wiadomo już, że potrzebujemy dużych liczb pierwszych. Dla celu przykładu użyję liczb pierwszych, które pozbawiają algorytm bezpieczeństwa, ponieważ są zbyt niskie, jednak pozwoli to łatwiej wykonać przykładowe obliczenia.

Przyjmijmy, że chcemy zaszyfrować literę Y (słowa i całe zdania zajęłyby zbyt dużo miejsca na obliczanie, dlatego ograniczę się do jednej litery). W systemie dziesiętnym litera Y to cyfra 89. Mamy więc już wiadomość zapisaną w postaci liczby czyli nasze m. Teraz należy odszukać p oraz q, które będą liczbami pierwszymi. Liczby 19 i 29 posiadają jako dzielnik samą siebie i 1, a więc spełniają kryteria liczb pierwszych (pamiętajmy jednak, że w "prawdziwym" szyfrowaniu powinny one być znacznie większe). Teraz przejdźmy do wyliczeń:

Mamy już wszystkie dane potrzebne do rozpoczęcia szyfrowania. Przy deszyfrowaniu będzie trzeba jeszcze wyliczyć d.

Zatem nasza wiadomość "Y" po zaszyfrowaniu ma wartość 90. Aby odszyfrować wiadomość należy użyć klucza prywatnego. Najpierw jednak musimy obliczyć wspomniane wcześniej d.

Deszyfrowanie wiadomości odbywa się według następujących wyliczeń:

89 to liczba reprezentująca symbol Y, zatem poprawnie zaszyfrowaliśmy i odszyfrowaliśmy naszą wiadomość. Operacje tego typu wykonywane są na dużo większych wartościach, dzięki czemu stosowanie obecnie tego algorytmu daje większe poczucie bezpieczeństwa. Piszę o poczuciu bezpieczeństwa, ponieważ w stu procentach bezpieczni nie będziemy nigdy. Każdy algorytm ma słabości i każdy zostanie kiedyś złamany. Jest to jedynie kwestia czasu, ponieważ moc obliczeniowa komputerów stale rośnie. Słabością RSA jest faktoryzacja (na szczęście obecnie faktoryzacja RSA trwałaby zbyt długo z powodu złożoności, by uzyskać sensowny wynik).

Faktoryzacja to rozkład dużej liczby całkowitej na czynniki pierwsze przebiegający w taki sposób, by iloczyn tych czynników był równy rozkładanej liczbie całkowitej. Aby troszeczkę to rozjaśnić posłużę się przykładem. Naszą dużą liczbą całkowitą jest x, natomiast po jej rozłożeniu otrzymujemy czynniki y1, y2, y3, yn. Zatem x=y1 y2 y3 yn.

Aby uzyskać klucz prywatny, należałoby dokonać faktoryzacji liczby użytej do stworzenia klucza publicznego, a więc uzyskać liczby pierwsze p oraz q. Wtedy odszyfrowanie wiadomości, a tym samym jej skompromitowanie, nie byłoby już problemem. Na szczęście jednak dla bezpieczeństwa RSA, faktoryzacja tak dużych liczb jakie są używane współcześnie jest bardzo trudna i długotrwała. Co prawda powstają algorytmy, które mają za zadanie przyspieszyć faktoryzację, jednak nadal czas łamania jest niesłychanie długi. Współcześnie używa się kluczy powyżej 1024 bitów, a największy złamany klucz RSA ma długość 576 bitów. Prawdziwym zagrożeniem, a nawet końcem RSA będą komputery kwantowe. Jak sama nazwa wskazuje, ich działanie opiera się na mechanice kwantowej. Moc obliczeniowa przewyższy znacznie tradycyjne komputery, przez co okres oczekiwania na faktoryzację dużej liczby pierwszej będzie bardziej racjonalny niż współcześnie. Odpowiedzią będzie zatem kryptografia kwantowa... Warto pamiętać, że algorytmy szyfrowania działają na zasadzie tarczy i miecza. Każdy nowy algorytm zapewnia ochronę jednak nie wiadomo na jak długo, bowiem prędzej czy później znajdzie się sposób na jego kompromitację...

Szyfrować, czy nie szyfrować...

Wiele osób niestety nie zdaje sobie sprawy jak cenne są dane gromadzone na komputerach czy pamięciach przenośnych i nie mam tu na myśli plików z muzyką czy zdjęć (aczkolwiek takie informacje mogą posłużyć cyberprzestępcy do np. szantażu). Chodzi o informacje zapisywane w przeglądarkach, pocztę zgromadzoną na dysku, aplikacje takie jak komunikatory z zapisanymi hasłami, prace, artykuły i wiele innych danych, których lepiej byłoby nikomu nie ujawniać. Sprzedając komputer czy sam dysk twardy nie wystarczy jedynie go sformatować. Wszystkie informacje będą cały czas możliwe do odzyskania i to nawet za pomocą darmowych programów. Nie trzeba wcale wymyślać scenariuszy do tego w jaki sposób można użyć zebrane dane. Wystarczy wyobrazić sobie przechwycenie przez osoby trzecie treści listu, zawierającego informacje dotyczące firmy lub zdobycie numeru karty kredytowej. Istnieje także możliwość wygenerowania fałszywej tożsamości, jeżeli zebrana zostanie dostateczna ilość danych osobowych.

Bywały już przypadki kupowania przez szantażystów używanych dysków twardych na aukcjach internetowych tylko i wyłącznie po to, by wydobyć skasowane dane i wykorzystać to do wyłudzenia pieniędzy od byłego właściciela. Niestety niektórzy ulegają i wolą zapłacić niż ryzykować wypłynięcie na światło dzienne danych związanych nimi/firmą.

Zapobiec temu może szyfrowanie dysków. Szyfrować można pojedyncze pliki, partycje i całe dyski twarde. Niektóre programy oferują tworzenie własnych szyfrowanych partycji, które są dostępne jedynie po ich podłączeniu. Dzięki takiemu rozwiązaniu przenoszenie ważnych dokumentów między komputerami staje się bezpieczniejsze. Wystarczy na komputerze A przenieść pliki na partycję, następnie całą partycję umieścić na pamięci przenośnej i podłączyć ją do komputera B. Ewentualne zgubienie lub kradzież nośnika danych nie spowoduje (w zależności od zastosowanego algorytmu szyfrującego) większych strat, a na pewno da więcej czasu na reakcję i zabezpieczenie się przed ewentualnymi stratami.

Na dowód tego, że zaszyfrowanie swoich danych nie jest trudne i każdy może sobie z tym poradzić, przedstawiam trzy krótkie filmy. Można na nich obejrzeć proces szyfrowania danych przy użyciu bezpłatnego programu TrueCrypt:

Tego typu rozwiązania w szczególności przydałyby się niektórym instytucjom przechowującym dane osobowe. Coraz częściej niestety słyszy się o kradzieży lub zaginięciu płyt i dysków z danymi personalnymi. Takie sytuacje z pewnością nie byłby tak szokujące gdyby nośniki były odpowiednio zabezpieczone mocnymi algorytmami.

  • W 2007 roku w Wielkiej Brytanii zaginęły dane osobowe 25 milionów obywateli. Były one przechowywane na niezabezpieczonych płytach CD. Znajdowały się tam takie informacje jak numery rachunków bankowych, daty urodzenia, adresy i nazwiska czy nr ubezpieczeniowe.
  • Miesiąc po powyższym zdarzeniu doszło do kolejnego incydentu, również z Wielką Brytanią w tle. W stanie Iowa w USA, zaginął dysk twardy z danymi 3 milionów kandydatów na prawo jazdy. Brytyjska agencja organizująca egzaminy, wydała zlecenie przechowywania danych osobowych przez amerykańską firmę. Nośnik jednak nie dotarł i dane te nie zostały odzyskane do teraz.

Niestety coraz częściej mają miejsce podobne sytuacje. Szyfrowanie tak ważnych informacji z pewnością bardzo by pomogło. O tym jak bardzo złudne jest poczucie bezpieczeństwa opartego na opinii "A co ktoś może zrobić z tymi danymi?" przekonał się Jeremy Clarkson. Ten brytyjski prezenter programu motoryzacyjnego Top Gear stwierdził podczas jednej z emisji, że takie dane nikomu się nie przydadzą i postanowił upublicznić numer rozliczeniowy swojego banku oraz dane potrzebne do przelewu. Bardzo szybko z jego konta zniknęło 500 funtów. Oto co powiedział po zajściu:

"Bank nie był w stanie stwierdzić, kto to zrobił i nie mógłby go powstrzymać przed zrobieniem tego ponownie. Myliłem się i zostałem ukarany za swój błąd."

Dowodzi to jak ważne jest szyfrowanie celem zabezpieczania danych osobowych. O ile nie mamy wpływu na dane przechowywane przez instytucje czy państwo, o tyle tylko i wyłącznie w naszej gestii leży bezpieczeństwo własnych komputerów.

Czasami szyfrowanie może być niestety wykorzystane w zupełnie innym celu niż pisaliśmy do tej pory. To co miało chronić nasze dane przed niepowołanym dostępem, może nas całkowicie od plików odciąć. W 2006 roku pojawił się w Sieci wirus o nazwie Gpcode, który szyfrował ponad 80 rodzajów plików na komputerze ofiary, po czym żądał zapłaty ich odszyfrowanie.

Wirus rozprzestrzeniał się poprzez pocztę elektroniczną. Użytkownicy sieci otrzymywali maile o następującej treści:

Witam!

Piszę odnośnie CV, które umieściłeś na stronie job.ru. Mogę zaoferować Ci posadę. ADC Marketing LTD (UK) otwiera filię w Moskwie, w związku z tym poszukuję odpowiednich kandydatów. Wkrótce zaproszę Cię na rozmowę kwalifikacyjną w dogodnym dla obu stron terminie. Jeżeli jesteś zainteresowany ofertą, wypełnij załączony formularz dotyczący oczekiwanego wynagrodzenia i prześlij go do mnie za pośrednictwem poczty elektronicznej.

Z poważaniem
Viktor Pavlov
Dyrektor działu HR

Jak nietrudno się domyśleć, w załączniku znajdował się trojan, który pobierał właściwego wirusa. Gpcode szyfrował między innymi pliki PDF, DOC, HTML, RAR i inne. Na koniec wszelkie szkodliwe programy pobrane i zainstalowane od momentu otworzenia wiadomości ulegały zniszczeniu, pozostawiając po sobie jedynie następujący komunikat:

Some files are coded by RSA method.
To buy decoder mail: k47674@mail.ru
with subject: REPLY

Tłumaczenie:

Niektóre pliki zostały zakodowane algorytmem RSA.
Aby zakupić dekoder wyślij maila na k47674@mail.ru o temacie ODPOWIEDŹ.

Początkowo algorytmy szyfrujące były dalekie od doskonałości i bardzo słabe (56-bitowe), z czasem jednak autor wirusa udoskonalał swoje "dzieło" kończąc z 660-bitowym kluczem RSA. Mimo, że jest to bardzo mocne zabezpieczenie, a największy ze złamanych kluczy RSA miał długość 640 bitów, pracownikom Kaspersky Lab udało się wypracować odpowiednie metody deszyfracji jeszcze tego samego dnia, w którym nastąpiło wykrycie wirusa.

Należy pamiętać, że szyfrowanie to miecz obosieczny. W zależności od tego przez kogo i w jaki sposób zostanie wykorzystane, może wyrządzić dużo szkód, jak i zapewnić bezpieczeństwo. Zapewnia swobodę słowa, bo zaszyfrowanej wiadomości bez odpowiedniego hasła nikt nie odczyta, zmniejszając jednocześnie bezpieczeństwo w państwie - skoro każdy może użyć szyfrowania to także organizacje przestępcze mogą stosować kryptografię do zatajania niewygodnych informacji. Nie można jednak popadać w paranoję, ponieważ wszystko jest dla ludzi. Ważne jest to, abyśmy sami zadbali o bezpieczeństwo naszych danych - tego nikt nie zrobi za nas.

Kaspersky Lab
Viruslist
Czytaj także
Polecane galerie