www.hakin9.org

hakin9 Nr 6/2007

70

Narzędzia

T

a potęga ma niestety swoją cenę, co
nie przeszkodziło jednak w użyciu jej
do zabezpieczenia komunikacji mię-

dzy Kremlem i Białym Domem po kryzysie
kubańskim. Jak to zwykle bywa w kryptolo-
gii, nie bardzo wiadomo, kto tak naprawdę
jest autorem algorytmu One Time Pad. Al-
gorytm jest wariantem szyfru Gilberta Ver-
nama, który wzbogacił Joseph Mauborgne, a
jego własności udowodnił Claude Shannon.
Ale czy byli pierwsi? Nie wiemy. Kryptologia
rozwijała się nie tylko w kręgach akademic-
kich, publikujących wszystkie swoje wyniki,
ale także w agencjach wywiadu, które swoje
wyniki trzymały w najgłębszej tajemnicy.

Wiele technik, odkrywanych w ostatnich

kilkudziesięciu latach było od dawna znanych
w kręgach wywiadowczych. Na przykład kryp-
toanaliza różnicowa, którą odkryli na nowo
Shamir i Biham w 1980 roku. IBM twierdzi,
że już w 1974r. firma znała tę technikę pod
inną nazwą i tak projektowała swoje algoryt-
my, żeby były na nią odporne, a NSA znać ją
miała jeszcze wcześniej (nie wiadomo jednak
od kiedy). Należy więc z pewną ostrożnością
podchodzić do informacji historycznych doty-
czących rozwoju kryptologii.

Samo kodowanie w One Time Pad (OTP)

jest trywialne, tajemnica i potęga tego algoryt-
mu zawarta jest w kluczu. Wymagania wobec
klucza są następujące:

• klucz musi być sekwencją losową (nie my-

lić z pseudolosową!),

• klucz musi być co najmniej tak długi, jak

tekst jawny,

• klucz może być użyty tylko raz (stąd one

time).

One Time Pad

czyli jednorazowa

podkładka

Cezary Cerekwicki

stopień trudności

Algorytmów szyfrujących powstało już wiele, ale tylko jeden

z nich tworzy kryptogramy, które gwarantują bezpieczeństwo

nawet wtedy, gdy atakujący będzie dysponował nieskończenie

długim czasem i nieskończenie szybkim komputerem. I to

niezależnie od dalszego rozwoju matematyki i kryptoanalizy!

Z artykułu dowiesz się

• jak działa najbezpieczniejszy algorytm krypto-

graficzny,

• jak działają szyfry strumieniowe,
• czym różnią się liczby losowe od pseudoloso-

wych.

Powinieneś wiedzieć

• wskazane jest rozumienie podstaw terminologii

kryptologicznej.

Narzędzia

hakin9 Nr 6/2007

www.hakin9.org

71

Można powiedzieć, że w przypadku
tego algorytmu reguła druga zawie-
ra się niejako w trzeciej, jednak dla
jasności w literaturze zwykle wy-
mienia się je osobno. Chodzi o to,
że skoro klucza można użyć tylko
raz, a klucz ma taką naturę, że każ-
dy jego znak jest pewnego rodzaju
mikrokluczem dla jednego znaku
tekstu jawnego, to wymaganie nu-
mer 2 jest naturalną implikacją tych
dwóch faktów. Gdyby można było
używać kluczy krótszych niż tekst
jawny, co najmniej jednego znaku
klucza użylibyśmy więcej niż raz.

Klucza można użyć tylko raz,

ponieważ tylko w ten sposób
kryptogramu nie będzie można
odróżnić od ciągu całkowicie
losowego. Gdybyśmy tą samą
sekwencją losową szyfrowali wię-
cej tekstów, kryptogramy miałyby
pewną cechę stałą, którą dałoby
się wykorzystać do ich złamania.
Drastycznie zmalałaby wówczas
entropia kryptogramów. Można by
było sprowadzić problem do ataku
na szyfr polialfabetyczny, który już
daje się atakować metodą brutalną
w rozsądnym czasie.

Dlatego są to wymagania ab-

solutnie konieczne. Każde, choćby
niewielkie odstępstwo od nich,
powoduje automatyczną utratę
gwarancji, co do braku możliwości
odszyfrowania kryptogramu przez
osoby nie dysponujące kluczem.

Czym różni się sekwencja loso-

wa od pseudolosowej? Sekwencja

pseudolosowa jest deterministycz-
na. Oznacza to, że jeśli znamy
algorytm, który został użyty do jej
wygenerowania i odgadniemy war-
tość inicjalną (zwaną zalążkiem),
to będziemy w stanie przewidzieć
wszystkie przyszłe wartości tej
sekwencji.

Oznacza to, że bezpieczeń-

stwo każdego systemu opartego
na nieprzewidywalności sekwencji
pseudolosowej jest potencjalnie
zagrożone, ponieważ istnieje w niej
zależność, którą atakujący może
odnaleźć i wykorzystać.

Sekwencja losowa jest niedeter-

ministyczna. Nie podlega żadnym
prawom, dającym się przewidzieć
i wykorzystać do skutecznego pro-
gnozowania jej dalszych wartości.
Między jej wartościami nie ma żad-
nych zależności, które dałoby się
odkryć i wykorzystać. Dzięki temu
jej przyszłe wartości są całkowicie
nieprzewidywalne. Nawet znając
część klucza, nie jesteśmy w stanie
wyprowadzić innych części. Można
powiedzieć, że sekwencja losowa
to czysty przypadkowy szum, bez
żadnych trwałych statystycznych
anomalii.

Uzyskanie takiej sekwencji

w zwykłym komputerze jest dość
trudne, o ile nie dysponuje się spe-
cjalnym sprzętowym generatorem
liczb losowych albo dużą ilością
nieprzewidywalnych danych, takich
jak ruchy myszki czy liczby milise-
kund między wywołaniami prze-

rwań klawiatury. Właśnie dlatego,
wiele programów kryptograficznych
wymaga poruszania myszki pod-
czas generowania klucza szyfru-
jącego.

Mając do dyspozycji klucz o tak

ciekawej charakterystyce, możemy
już przystąpić do kodowania. Sama
technika kodowania nie jest tak bar-
dzo istotna, może to być XOR, może
to być dodawanie i odejmowanie,
lub dowolna inna bezstratnie odwra-
calna operacja. Najczęściej używa
się następującej operacji:

znak kryptogramu = znak tekstu jawnego

XOR znak klucza

Na wszelki wypadek przypominam,
że XOR (ang. eXlusive OR) to
dwuargumentowa bitowa alterna-
tywa wykluczająca, zwracająca 1
dla pary różnych bitów i 0 dla pary
bitów o tej samej wartości. Można
to przedstawić w tabelce. Operator
XOR ma ciekawą własność:

a = (a XOR b) XOR b.

Oznacza to, że jeśli szyfrujemy
poprzez znak tekstu jawnego XOR
znak klucza, to odszyfrowanie bę-
dzie przebiegało analogicznie: znak
kryptogramu XOR znak klucza.

W Tabeli 2. przedstawiamy przy-

kładowe szyfrowanie litery T (o kodzie
ASCII 84) kluczem o wartości 105.

Kryptoanaliza

One Time Pad

W przypadku One Time Pad, dla
każdego kryptogramu istnieją różne
klucze, które pozwolą odszyfrować
go do wielu sensownych tekstów
jawnych. Zatem atak brutalny
zwróci nam wszystkie możliwe sen-
sowne teksty o takiej długości, jaką
miał kryptogram. Odróżnienie tego
właściwego od pozostałych jest
niemożliwe.

Tabela 1.

Działanie operatora XOR

A

B

A XOR B

0

0

0

0

1

1

1

0

1

1

1

0

Tabela 2.

Przykład szyfrowania OTP

Tekst jawny

1

0

1

0

1

0

0

Klucz

1

1

0

1

0

0

1

Kryptogram

0

1

1

1

1

0

1

hakin9 Nr 6/2007

www.hakin9.org

Narzędzia

72

Analiza częstości

Rozkład częstości znaków w kryp-
togramie jest równomierny, zatem
nie niesie jakiejkolwiek przydatnej
informacji dla atakującego.

Atak ze znajomością

części klucza

Powiedzmy, że w jakiś sposób
pozyskaliśmy część klucza. Dzięki
temu jesteśmy w stanie odszyfro-
wać fragment kryptogramu, który
powstał przy użyciu tej właśnie
części klucza. Co możemy zro-
bić z taką informacją? Niewiele.
Znajomość części klucza nie daje
się w żaden sposób przełożyć na
znajomość całości. Nie uzyskuje-
my żadnej wiedzy na temat choćby
charakterystyki statystycznej resz-
ty klucza.

Ataki w innych scenariuszach

niż atak na kryptogram

One Time Pad jest algorytmem
symetrycznym, a więc zarówno do
szyfrowania, jak i deszyfrowania uży-
wany jest ten sam klucz. W związku
z tym, użycie tego algorytmu wiąże
się z takimi samymi ograniczeniami,
jak w przypadku wszystkich innych
szyfrów symetrycznych: konieczne
jest utworzenie bezpiecznego ka-
nału wymiany klucza przed nawią-
zaniem komunikacji zabezpieczanej
One Time Pad, a następnie trzeba
chronić klucz przed niepowołanym
dostępem.

Oczywiście możemy skonstru-

ować protokół kryptograficzny,
który zabezpieczy zdalną wymianę
kluczy rozwiązaniem z zakresu
kryptografii klucza publicznego (co
częściowo rozwiąże problem po-
tencjalnie długotrwałego przecho-
wywania klucza), ale jednocześnie
zredukuje bezpieczeństwo całej
komunikacji do bezpieczeństwa
algorytmu użytego do realizacji wy-
miany kluczy. Co więcej, długość
klucza dla OTP może być bardzo
duża (dodatkowo jego charakte-
rystyka statystyczna praktycznie
wyklucza sensowność kompresji),
a jak wiadomo algorytmy krypto-
grafii klucza publicznego do naj-
szybszych się nie zaliczają.

Szyfry strumieniowe

One Time Pad jest wariantem algo-
rytmu Vernama. Jeśli zamiast liczb
losowych posłużymy się sekwencją
wygenerowaną przez kryptogra-
ficznie bezpieczny generator liczb
pseudolosowych, otrzymamy tzw.
szyfr strumieniowy.

Klasyczny algorytm Vernama

używał zwykłych sekwencji pseudo-
losowych, nie dających żadnych do-
datkowych gwarancji (jakie zapewnia
użycie kryptograficznie bezpiecznego
generatora liczb pseudolosowych).

Claude Shannon podczas dru-

giej wojny światowej udowodnił, że
One Time Pad jest niemożliwy do
złamania w scenariuszu ataku na
kryptogram (a więc ma cechę bez-
pieczeństwa absolutnego) oraz, że
każdy algorytm, który będzie mieć
taką cechę, jest równoważny One
Time Pad.

To bardzo silny wynik, jak na

kryptografię, ponieważ niewiele algo-
rytmów dorobiło się bezwarunkowych
dowodów swojego bezpieczeństwa.
Wiele z nich teoretycznie może z dnia
na dzień okazać się bezużytecznymi,
bo np. uda się znaleźć metodę szyb-
kiej faktoryzacji dużych liczb (m.in.
RSA) albo efektywną metodę liczenia
logarytmów dyskretnych (m.in. Diffie-
Hellmann). Bezpieczeństwo więk-
szości algorytmów kryptograficznych
zależy od szybkości komputerów - im
szybciej wzrasta ich moc obliczenio-
wa, tym szybciej te algorytmy stają
się przestarzałe.

Tymczasem One Time Pad jest

niemożliwy do złamania nawet przy
posiadaniu nieskończenie szybkiego
komputera i nieskończenie długiego
czasu. Niegroźny jest mu też rozwój
matematyki (w przeciwieństwie do
kryptografii klucza publicznego, której
los zależy od tego, którymi ścieżkami
matematyka się rozwinie). Niestrasz-
ne mu nowe metody kryptoanalitycz-
ne (przynajmniej w scenariuszu ataku
na kryptogram, kryptoanaliza gumo-
wej pałki i analogiczne jak najbardziej
dają się zastosować).

Żaden inny algorytm nie ma tak

silnych podstaw matematycznych
gwarantujących jego bezpieczeń-
stwo.

Skoro ten algorytm jest taki po-

tężny, to czemu jego powstanie nie
rozwiązało wszystkich problemów
kryptografii? Głównym powodem
jest jego zachłanność na liczby
losowe. One Time Pad zużywa ich
bardzo dużo, a jest to bardzo cen-
ny zasób, który trudno wytworzyć.
Dodatkowo te olbrzymie ilości da-
nych losowych trzeba bezpiecznie
dostarczyć wszystkim legalnym
stronom komunikacji, co powoduje
poważne osłabienie praktycznego
bezpieczeństwa całego protokołu.
Ponadto jest to algorytm symetrycz-
ny, a owe, już ze swej natury, nie
rozwiązują wszystkich problemów,
którymi zajmuje się kryptologia.
Jednak nawet w obrębie algoryt-
mów symetrycznych OTP jest mało
praktyczny, głównie ze względu
na swoje klucze, które są duże,
a więc i kłopotliwe w wytworzeniu,
przechowaniu i bezpiecznym trans-
porcie. Wiele innych algorytmów
symetrycznych potrafi zapewnić
rozsądny poziom bezpieczeństwa
dużo niższym kosztem.

Dotykamy tu dwóch istotnych

zagadnień: relacji poziomu bezpie-
czeństwa do jego kosztu oraz relacji
między teoretyczną kryptografią,
a praktyką bezpieczeństwa informa-
cyjnego. Dla praktyków One Time
Pad jest mało przydatny w większo-
ści zastosowań, w przeciwieństwie
do bardzo do niego podobnych szy-
frów strumieniowych.

Szyfry strumieniowe są próbą

znalezienia złotego środka między
idealnym bezpieczeństwem OTP

O autorze

Cezary Cerekwicki jest z wykształ-
cenia informatykiem i politologiem.
Pracował jako programista, admini-
strator, konsultant, tłumacz, koordy-
nator międzynarodowych projektów,
dziennikarz i publicysta. Pisał pro-
gramy w dziesięciu językach progra-
mowania (od asemblerów po języki
skryptowe) w czterech systemach
operacyjnych, na dwóch platformach
sprzętowych.
Kontakt z autorem: [e-mail]

Narzędzia

hakin9 Nr 6/2007

www.hakin9.org

73

i praktyką. Tu wymianie podlega
jedynie zalążek kryptograficznie
bezpiecznego generatora liczb
pseudolosowych, który ma skoń-
czoną i rozsądną długość. Można
go zatem bez problemu i efektywnie
wymienić technikami kryptografii
klucza publicznego. Tekst jawny
może mieć dowolną długość, nie-
znaną w momencie rozpoczęcia
szyfrowania (to ogólna cecha
wszystkich szyfrów strumieniowych,
stąd zresztą ich nazwa).

Kiedy obie strony dysponują za-

lążkiem, mogą generować kolejne,
takie same liczby pseudolosowe,
które będą kluczami dla poszcze-
gólnych znaków tekstu jawnego.

Taki protokół jest już podatny

na ataki brutalne próbujące od-
gadnąć wartość zalążka (dlatego
jest on na tyle długi, żeby taki
atak nie był praktyczny), na me-
todę wymienienia się nim przez
strony konwersacji oraz na próby
odnalezienia słabości użytego
kryptograficznego generatora liczb
pseudolosowych. Tak więc bezpie-
czeństwo szyfrów strumieniowych
jest znacznie słabsze od One Time
Pad (ale do praktycznych zastoso-
wań wystarcza), natomiast są one
dużo bardziej ekonomiczne, jeśli
chodzi o zapotrzebowanie na liczby
losowe (zalążek musi być nieprze-
widywalny).

Podsumowanie

Mimo swoich praktycznych niedo-
skonałości algorytm One Time Pad
był używany do zabezpieczania
bardzo ważnych kanałów komuni-
kacyjnych. Najbardziej znanym za-
stosowaniem było zabezpieczanie
gorącej linii między Waszyngtonem
i Moskwą po kryzysie kubańskim.
OTP używano także w Republice
Weimarskiej na początku XX wieku,
używali go alianci podczas drugiej
wojny światowej oraz Rosjanie pod-
czas Zimnej Wojny.

Dodatkowo OTM ma taką zaletę,

że do dziś można się nim posłużyć
przy pomocy jedynie ołówka i kartki
papieru, podczas gdy cała współ-
czesna kryptografia jest całkowicie
uzależniona od komputerów. l