 X Ŀ B
 O ͻ P
 R  .    .Ŀ .    *    Ŀ Ŀ   . Ŀ  .    *Ŀ   .     * X
ٺ               .۳                     Ŀ
ͼ   * Ŀ    .    ۳ .    Ŀ۳    .  ڿ۳.     .  ͻ
 . Ŀ ۳  Ŀ     Ŀ.. Ŀ ۳ Ŀ Ŀ.
  ۳۳  ۳* .۳*  ۳ ۳*   ۳. ۳ 
 ٳ ۳Ŀ ڿ   Ŀ  ۳  
*. ٳ ۳۳. Ŀ ۳  ڿ..  
 ۳   . ۳  ۳۳ٳ۳   ۳۳ ۳    
        ۳ ٳ۳ .   ڿ   
 Ŀ*       .  .    *  ۳ *      Ŀ     *  ۳* 
. ۳   .                 ۳       . ۳  .     ۳ 
              .              .              ..
members:       *    .       *  members: .            *     .       members:
 *    beanus   dulek      jaro   massh    mig-21 oxcart  zetx
arakus .  coxoc   hannibal  lobix * mauzer    neo  ._r00t_  
ٺ
ͻ   .        .           *     .         .           *   ĿĿĿĿ ͼ
Ŀ official URL: http://beanus.provider.pl/     .         ٳ۳۳۳ 
 E  *     on IRC: #crackpl or #cookiecrk  *          .       C
 X ͼ M
 P  P

=============================================================================

DES (Data Encryption Standart) algorytm ten zaliczamy do szyfrow kaskadowych

lub iloczynowych, iteeracynych.Dyscyplina zajmujaca sie analiza DES-a to kryptografia.

Jest to nauka z pogranicza matematyki i informatyki, zajmuje sie zapisywanim

informacji w postaci zaszyfrowanej.Natomiast kryptografia zajmuje sie probami

odcztania zaszyfrowanych inforamcji.      

============================== Kryptoanaliza ================================

Kryptoanaliza zajumje sie lamaniem szyfrow.Polega na znalezieniu klucza na

podstawie zaszyfrowanego textu lub na okresleniu klucza, jesli znany jest

text jawny i szyfrogram, polega rozniez na znalezieniu jawnego textu:)

Atak oparty jedynie na znajomosci textu zaszyfrowanego jest najtrudniejszy

do przeprowadzenia.Przy lamaniu algorytmu szyfrowania zaklada sie , ze jego

struktura(sposob dzialania) jest znana kryptoanalikowi.



============================ Metody kryptoanalizy ===========================

* brute force - atak brutalny - chodzi tutaj o sprawdzenie wsztystkich mozliwych

  kluczy

* matematyczne analizy algorytmu, celem jest znalezenie slabego punktu

  algorytmu szyfrowania

=============================================================================

                               Brute force

Mamy szyfr o n mozliwosciach, do jego zlamania mozemy uzyc 2 sposobow:

* szukanie wszystkich mozliwych kluczy - wymaga duzego nakladu czasu

* metoda sprawdzania tablicy(lookup table method) wymaga duzej ilosci pamieci



                               Metoda czasowa

                               --------------

Mamy szyfrogram C i odpowiadajacy mu text jawny M : zasada ? - sprawdzanie

wszystkich kluczy tzn. text M szyfrowany jest przy uzyciu kazdego mozliwego klucz

w celu otrzymania odpowiadajacego mu szyfrogramu C.Zuzycie czasu w tej metodzie wynosi

O(n), natomiast zajetosc pamieci O(1).

                                

                                 Przyklad

                                ----------

Mamy algorytm DES.Liczba wszystkich mozliwych kluczy dla tego algorytmu

wynosi 2^56 (56 bitowy klucz).Przy wykorzystaniu metod sprzetowych mozna

sprawdzic jeden klucz(jednokrotnie wykonanie algorytmu) w ciagu 1ms.



       t=2^56ms=7 x 10^16ms=7 x 10^10s=810 000 dni=2200 lat



                             Metoda pamieciowa

                             -----------------

Dla danego textu jawnego M tworzymy jego szyfrogram przy uzyciu wszystkich

mozliwych kluczy.

                        Ci=Eki(M)   dla i=1,2..,n.

Klucze Ki ukladamy w tablice(liste) tak ze , Ci jest numerem pozycji(indexem)

klucza Ki w tej tablicy.Mozemy wiec znalezc klucz , przy uzyciu ktorego

kryptogram zostal utworzony.Czas znalezienia textu jawego jest staly O(1),

natomiast ilosc potrzebnej pamieci  wynosi O(n)



                                 Przyklad

                                ----------

Obliczmy w przyblizeniu ilosc potrzebnej pamieci, potrzebnej do zlamania

DES-a metoda pamieciowa (jeden alement tablicy miesci 56-biotwy klucz)

==============================================================================

S=56*2^56 bitow=56 * 7 * 10^16bitow=4 * 10^18bitow=5 * 10^17 bajtow=470 mln GB

==============================================================================



Przyklady te daja duzo do zyczenia - wymagaja duzego nakladu czasu lub sa

bardzo kosztowne.

Mozliwe jest sprawdzenie wszyskich kluczy przez jeden dzien za pomoca okolo

800 000 ukladow elektroniczych.Jezeli zalozymy ze koszt jednego wynosi od

1 do 10 USD to cena bedzie w przedziale od kilkuset do kilku mln USD.



                                Pamiec-Czas

                               -------------

Kosztem czasu uzyskuje sie oszczednosc pamieci.Podobnie jak w metodzie pamieciowej

nalezy wykonac najpierw obliczenia i przygotowac tablice.Tablica bedzie miala

wymiar O(n^2/3), czas jest rowny O(n^2/3).

Mamy wiec dany text M oraz oraz text zaszyfrowany C.Naszym celem jest znalezienie

klucza.

Niech f(K) bedzie funkcja okreslona na kluczu K w sposob :

                        f(K)=Ek(M)

gdzie E jest przeksztalceniem szyfrujacym, czyli f(K) jest wynikiem szyfrowania

textu M przy pomocy klucza K.Przed wykonaniem obliczen wstepnych wybiera sie

ze zbioru wszystkich mozliwych wartosci klucza , m losowych wartosci poczatkowych

l10,l20,...,lm0 Dla pewnej ustalonej liczby t obliczamy wartosci:



Xi0=li0

Xij+1=f(Xij)

dla i=1,2..,m oraz j=1,2,..,t

oto rysunek

        =======================================================

        I10 = X10 -> X11 -> X12 -> ... -> X1t-2 -> X1t-1 -> X1t

        .

        .

        Ii0 = Xi0 -> Xi1 -> Xi2 -> ... -> Xit-2 -> Xit-1 -> Xit

        .

        .

        Im0 = Xm0 -> Xm1 -> Xm2 -> ... -> Xmt-2 -> Xmt-1 -> Xmt

        =======================================================



Niech X oznacza tablice zawierajaca wszystkie wyniki obliczen, a wiec wartosci

przedstawione na powyzszym rysunku.W pamieci zachowuje sie jednak tylko

pierwsza i ostania kolumne tej tablicy, czyli pary(li0,Xit), i =1,2..,m

(bez wynikow posrednich).Wielkosc zapamietanych danych wynosi O(m) a czas ich

tworzenia O(mt).

Poszukiwania klucza rozoczynamy w kolumnie t-1 tablixy X.Sprawdzamy czy ktoras z

wartosci kolumny t tzn Xit, i=1,2..,m jest rowna C.Jezeli tak oznacza to iz

szyfrogram ktory jest rowny tej wartosci, powstal z zaszyfrowania M kluczem z

kolumny t-1 tego samego wiersza, w ktorym znaleziona wartosc.

Jezeli nie znalezlismy klucza w kolumnie t-1 , rozpoczynamy jego poszukiwanie

w kolumnie t-2. W tym celu obliczamy Y1=f(C) i sprawdzamy czy ktoras z wartosci Xit

gdzie i=1,2,..,m jest rowna Y1.Jezeli tak to znaczy ze Y1 powstalo w dwoch

literacjach funkci f, rozpoczetych na wartosci z kolumny t-2 wiersza ,w ktorym

znaleziono wartosc Xit rowna Y1.W razie potrzeby kontynuujemy poszukiwania klucza w kolumnach

t-3 , t-4 ..,1

Przypominamy ze poniewaz nie przechowujemy wartosci posrednich macierzy X

w razie znaleznienie klucza nalezy jego wartosc wyliczyc wykonujac odpowiednia

liczbe literacji funkcji f.

Jezeli wszystkie wartosci funkcji X sa rozne i wybrane losowo to prawdopodobienstwo

znalezienia w tablicy klucza wynosi mt/n(Hellman udowodnil ze jesli nawet sa

powrotzenia w tablicy X ale mt^2=n to prawdopodobienstwo to jest niewiele mniejsze

a mianowicie ograniczone od dolu wartoscia 0,8mt/n).Jezeli wiec wybierzemy

mt=n to mamy rowne jednosci(lub troche mniejsze - dla tablicy z powtorzeniami

i mt^2=n) prawdopodobienstwo znaleznienia klucza w tablicy X.

Niech m=t=1/3 .Wowczas prawdopodobienstwo powodzenia wynosi (n^-1/3) co

w praktyce moze nie byc zbyt duzo liczba.

Hellman przeprowadzil analize dla DES-a.Dla n = 2^56=7810^16.Rozwazane

prawdopodobienstwo (rowne n^-1/3) nieznacznie przekracza 10^-6, a wiec

nie jest zbyt duze.

Aby zwiekszyc prawdopodobienstwo , Hellman zaproponowal przygotowanie t=n^1/3

tablic, ktore beda pozniej przeszukiwane - wowczas prawdopodobienstwo bedzie

duze(jezeli zalozymy ze wartosci w tablicach nie beda sie powtarzac to razem bedzie

tmt=n wartosci , czyli wszystkie bede wycerpanei znalezienie wsrod nich klucza

bedzie rowne jednosci).Przy rozwiazaniu takim zajetosc pamieci wyniesie

O(tm)=O(n^2/3) czas obliczen wstepnych wyniesie O(tmt)=O(n)

(rowny czasowi przeszukiwania wszystkich kluczy), a cza poszukiwan O(tt)=O(n^2/3)

POniewaz czas obliczen poczatkowych jest bardzo duzy , Hellman proponuje zastosowanie obliczen

rownoleglych.Nalezy pamietac ze wyniki raz wykonanych obliczen wstepnych moga byc pozniej wielokrotnie wykorzystywane.

Hellman zaproponowal sprzetowa implementacje urzadzenia do lamania DES-a.

Przyjal m=10^5 t=10^6 oraz zalozyl uzycie 10^6 tablic.Poniewaz  jeden

element tablicy zajmuje 112 bitow , zajetosc pamieci wyniesie

112 * 11^11 =1300GB , natomiast czas poszukiwan 10612 operacji =11dni(zakladajac ze jedno szyfrowanie trwa 1ms)

Jezeli uzyjemy 250 ukladow ktore wykonuja jedno szyfrowanie w ciagu 1ms to czas spadnie

do  mniej wiecej 1 godziny.

Oszacujmy koszty:Przy cenach z lat 90 . 250 ukladow szyfrujacaych po 1-10 USD

bedzie kosztowalo kilkaset do kilku tys.USD , koszt 1300GB przestrzeni

dyskowej ok.100tys.USD



literaturka:

net forum
