2014-04-01
Agenda
Bezpieczeństwo
" Podstawowe pojęcia
i ochrona danych
" Algorytmy synchroniczne i asynchroniczne
" Algorytmy z rejestrem przesuwnym
" Algorytm Berlekampa-Masseya
Algorytmy strumieniowe
" Atak korelacji
" Przykładowe algorytmy
Algorytmy strumieniowe Algorytmy strumieniowe
" Uogólnienie koncepcji szyfrowania z kluczem " Klucz szyfrowania jest wykorzystywany
jednorazowym - one-time pad (OTP) zgodnie z ideÄ… klucza jednorazowego
TJ xor Klucz = TT
" Możliwość szacowania bezpieczeństwa
i większa praktyczność niż OTP " Podstawą jest generator ciągów
pseudolosowych
" Algorytm jest inicjowany przy pomocy
krótkiej tajnej wartości stanowiącej klucz " Generowane są losowe pojedyncze bity lub
bajty
" Klucz jest rozciągany do długiego ciągu
stanowiÄ…cego klucz szyfrowania
Algorytmy strumieniowe
Algorytm strumieniowy
" Cechy bezpiecznego generatora ciągów
pseudolosowych:
1. Generowane wartości będą każdorazowo praktycznie
nieprzewidywalne dla osób postronnych
2. Nie będzie możliwe ustalenie ziarna lub stanu
wewnętrznego generatora na podstawie obserwacji
dowolnie długiego ciągu wygenerowanych bitów.
3. Znajomość dowolnej liczby wcześniej wygenerowanych
bitów nie będzie wystarczała, by odgadnąć dowolny
przyszły bit z prawdopodobieństwem istotnie wyższym od
1/2.
" Ogólny schemat algorytmu
4. Dla wszystkich możliwych wartości ziarna, zachowana
będzie pewna minimalna, dopasowana do zastosowania,
długość cyklu PRNG.
1
2014-04-01
Algorytm strumieniowy
" Wyróżnia się algorytmy
Synchroniczne
Asynchroniczne
Algorytmy synchroniczne
Algorytm synchroniczne Algorytmy synchroniczne
" Nie ma propagacji błędów
" Synchroniczne szyfry strumieniowe:
pojedynczy błąd nie ma wpływu na kolejne
strumień klucza jest generowany
porcje danych
nieżalenie od zawartości tekstu jawnego
nadaje sie do sytuacji o dużym
oraz szyfrogramu
prawdopodobieństwie błędu transmisji
jest potrzebna synchronizacja
" Podatny na ataki zmiany bitów
" nadawca i odbiorca musza być
zmiana bitu w szyfrogramie powoduje zmianÄ™
zsynchronizowani.
bitu w rozszyfrowanej wiadomości
" Podatność na ataki wstawiania i usuwania
bitów szyfrogramu
utrata synchronizacji
Algorytm synchroniczne Algorytmy synchroniczne
si+1= f(si,k)
zi=g(si,k)
ci=h(zi,mi)
2
2014-04-01
Algorytmy synchroniczne Algorytmy synchroniczne
" Jeśli transformacja h łącząca strumień
Deszyfrowanie
klucza wraz ze strumieniem tekstu
jawnego jest funkcja XOR, wówczas błędy
bitowe w pewnych pozycjach szyfrogramu,
ci`
będą miały wpływ tylko na odpowiednie
pozycje tekstu jawnego.
mi
-1
h
Algorytmy asynchroniczne
" Asynchroniczne szyfry strumieniowe, nazywane
także samo-synchronizujacymi szyframi
strumieniowymi
generowany strumień klucza jest zależny od:
" wartości klucza
Algorytmy asynchroniczne
" wartości szyfrogramów poprzednich.
" Liczba szyfrogramów wpływających na wartość
strumienia klucza, musi być stała w obszarze
działania całego szyfru.
Algorytmy asynchroniczne Algorytmy asynchroniczne
" Generator strumienia szyfrującego używa kilku " Asynchroniczne szyfry strumieniowe są szyframi
poprzednich bitów szyfrogramu przy z pamięcią.
generowaniu kolejnych elementów ciągu.
bufor dla szyfrogramów stanów poprzednich.
" Problem wygenerowania strumienia klucza w
" Pojedynczy błąd rozprzestrzenia sie na kilka
pierwszych t-chwilach.
kolejnych elementów szyfrogramu.
" Jedna z technik rozwiÄ…zania tego problemu
" Powrót do poprawnego deszyfrowania po
użycie dla pierwszych t-chwil wektora
wstawieniu lub usunięciu bitów (czyli po stracie
inicjalizujÄ…cego IV.
synchronizacji) jest automatyczny.
3
2014-04-01
Algorytmy asynchroniczne Algorytmy asynchroniczne
" Jedną z podstawowych własności tych szyfrów " Dobre własności statystyczne
jest samosynchronizacja.
każdy bit tekstu jawnego wpływa na wartość
szyfrogramu, statystyczne własności tekstu jawnego
ulegają rozrzuceniu w obrębie wszystkich
proces deszyfrowania zależny jest tylko od t stanów
szyfrogramów,
poprzednich, a nie jak w przypadku szyfrów
odporniejsze na ataki bazujÄ…ce na redundancji tekstu
synchronicznych od wszystkich stanów.
jawnego.
propagacja błędów jest ograniczona do t
szyfrogramów.
Rejestr przesuwny
" Tradycyjne algorytmy strumieniowe
wykorzystywały rejestry przesuwne
" Obecnie jest większa różnorodność podejść
projektowych
Algorytmy z rejestrem przesuwnym
" Rejestr przesuwny:
Generuje serię stanów (bitów)
Towarzyszy mu sprzężenie zwrotne
" Na przykład: rejestr z liniowym sprzężeniem
zwrotnym - linear feedback shift register (LFSR)
Rejestr przesuwny
LFSR
" Przykład (nieliniowej) funkcji sprzężenia
" Przykład rejestru LFSR
zwrotnego
f(xi, xi+1, xi+2) = 1 Åð xi Åð xi+2 Åð xi+1xi+2
" Przykład (nieliniowy) rejestru przesuwnego
" xi+5 = xi Åð xi+2 dla każdego i
" Jeżeli ziarno (x0,x1,x2,x3,x4) = 01110
wtedy (x0,x1,& ,x15,& ) = 0111010100001001&
" Pierwsze 3 bity sÄ… inicjowane losowÄ…
wartością (ziarno) - (x0, x1, x2)
4
2014-04-01
Algorytmy strumieniowe oparte na
LFSR
rejestrze przesuwnym
" Dwa podejścia do wykorzystania LFSR na
" Dla LFSR
potrzeby szyfrowania:
Jeden rejestr LFSR z nieliniowÄ… funkcjÄ…
połączeń
Kilka LFSR połączonych nieliniową funkcją
" Mamy xi+5 = xi Åð xi+2 dla każdego i
" Kluczem jest początkowe wypełnienie
" Funkcja sprzężenia zwrotnego jest zapisywana w
LFSR (ziarno)
postaci wielomianu: x5 + x2 + 1
" Ciąg szyfrujący stanowi wyjście rejestru
" Wielomian połączeniowy rejestru LFSR
(zestawu rejestrów)
Algorytmy strumieniowe oparte na
Algorytmy strumieniowe oparte na
rejestrze przesuwnym
rejestrze przesuwnym
" Wiele rejestrów LFSR z funkcją nieliniową
" Pojedynczy rejestr LFSR jest specjalnym
przypadkiem złożonych rejestrów
" W celu przejścia od przypadku pojedynczego
rejestru LFSR do przypadku wielokrotnego
użycia:
Niech LFSR0,& LFSRn-1 będą identyczne
Ziarno LFSR0 jest identyczne z ziarnem LFSR
Ziarno LFSR1 jest identyczne z zawartością LFSR z
kroku pierwszego
qðCiÄ…g wyjÅ›ciowy: k0,k1,k2,&
Itd.
Algorytm Berlekampa-Masseya
Algorytm Berlekampa-Masseya
" Sekwencja bitów: s = (s0,s1,s2,& ,sn-1)
" Dysponując częścią okresowego
" Liniowa złożoność L sekwencji s jest
strumienia, możemy znalezć najkrótszy
najmniejszym rozmiarem LFSR generujÄ…cym s
LFSR, który wygenerowałby taką
" Niech L będzie liniową złożonością s
sekwencjÄ™
" Wtedy C(x) jest wielomianem definiujÄ…cym
" Algorytm Berlekamp-Massey
połączenia rejestru o następującej postaci:
Wymiar problemu N2, gdzie N jest długością
C(x) = c0 + c1x + c2x2 + & + cLxL
LFSR
" Algorytm Berlekamp-Massey pozwala określić
Algorytm iteracyjny
L i C(x)
Potrzebuje jedynie 2N kolejnych bitów
5
2014-04-01
Algorytm Berlekampa-Masseya
Algorytm Berlekampa-Masseya
" Alglorytm Berlekamp-Massey jest efektywnÄ… metodÄ…
określenia minimalnego LFSR potrzebnego do
wygenerowania sekwencji
" Przy znanym tekście jawnym, wartości bitów generatora
są również dostępne
" Z wystarczająco długim ciągiem generatora, algorytm
Berlekamp-Massey może być użyty do odnalezienia
wszystkich bitów
" Wystarcza 2L bitów, gdzie L jest liniową złożonością
generatora
" Ciąg pseudolosowy musi mieć dużą złożoność liniową
Moc sekwencji
Moc algorytmu
" Aby ciąg był bezpieczny kryptograficznie
" Generowana sekwencja jest dobra jeżeli spełnia
generator musi posiadać dużą złożoność
kryteria generatora pseudolosowości
" Nie jest to warunek wystarczajÄ…cy!
" Dobry generator musi być nieprzewidywalny
Znany ciąg udostępnia informacje o generatorze " Np. s = (s0,s1,& ,sn-1) = 00& 01
Nie można uzyskać wiedzy na temat przyszłych
" Wtedy s ma złożoność n
elementów ciągu na podstawie znajomości
Najmniejszy rejestr przesuwny dla s wymaga n
wcześniejszych wartości
stopni
" Mała złożoność generatora = przewidywalność
Największy z możliwych okresów - n
Wniosek z algorytmu B-M
Lecz nie jest kryptograficznie bezpieczny
" Złożoność skoncentrowana na ostatnim
bicie
Profil liniowej złożoności Profil liniowej złożoności
" Profil liniowej złożoności jest lepszą miarą
" Dobry profil złożoności liniowej
mocy kryptograficznej
" Wykres liniowej złożoności jako funkcji od
liczby bitów w algorytmie Berlekamp-Massey
Powinien być zbliżony do linii n/2
" Wykres dla s = (s0,s1,& ,sn-1) = 00& 01 ma
wartości bliskie 0 aż do ostatniego bitu, kiedy to
skacze do n
Nie zbliża się do charakterystyki n/2
Nie stanowi mocnego kryptograficznie generatora (w
s
świetle tej definicji)
6
2014-04-01
k-błąd k-błąd
" k-błąd profilu liniowej złożoności
" Stanowi alternatywną miarę jakości dla
generatorów
k-błąd jako funkcja od k
" Jeszcze raz: s = (s0,s1,& ,sn-1) = 00& 01
" Przykład:
" SÅ‚aba sekwencja s
" s- duża złożoność, lecz tylko jeden bit poza
" Dobry profil powinien
minimalną złożonością
zbliżać się do przekątnej
" k-błąd jest równy minimalnej złożoności
liniowej algorytmu dającego sekwencję odległą
o k od sekwencji s
" k-błąd złożoności liniowej sekwencji s = 00& 01
wynosi 0
Liniowa złożoność tej sekwencji jest niestabilna
Kryptograficznie silne sekwencje Kryptograficznie silne sekwencje
" Testy jakości PRNG -16 testów statystycznych
" Liniowa złożoność musi być duża
(http://csrc.nist.gov/groups/ST/toolkit/rng)
" Profil liniowej złożoności musi być bliski
Frequency (Monobits) Test
Test for Frequency within a Block
do linii n/2
Test for the Longest Run of Ones in a Block
" k-błąd profilu liniowej złożoności musi być
Random Binary Matrix Rank Test
Discrete Fourier Transform (Spectral) Test
bliski przekÄ…tnej
Non-overlapping (Aperiodic) Template Matching Test
" Wszystkie ww warunki sÄ… konieczne lecz
Overlapping (Periodic) Template Matching Test
nie wystarczajÄ…ce. Maurer's Universal Statistical Test
Lempel-Ziv Complexity Test
Linear Complexity Test
&
Atak korelacji
" Intruz uzyskuje część ciągu wygenerowanego
przy pomocy LFSR
" Mamy do czynienia z generatorem złożonym z
wielu rejestrów
Jeżeli tak nie jest, można dokonać odpowiedniej
Atak korelacji
konwersji
" Zgodnie z zasadą Kerckhoffa zakładamy, że
rejestr i funkcje sÄ… znane.
" Jedynie nie jest znany klucz - ziarno
7
2014-04-01
Atak korelacji
Atak korelacji
" Przypuśćmy, że mamy do czynienia z
" Celem jest odtworzenie poczÄ…tkowego stanu
następującym generatorem:
rejestru LFSR
Znamy wszystkie połączenia dla wielomianu
generujÄ…cego i funkcji nieliniowej
Znamy ciąg N bitów, k0,k1,& ,kN-1
" Czasami jest możliwe określenie
początkowego ustawienia LFSR niezależnie
Poprzez korelację wyjścia LFSR z dostępnym
qðf(x,y,z) = xy Åð yz Åð z
ciągiem bitów
qðKlucz jest 12 b
Poprzez typowy atak dziel i rzÄ…dz
Atak korelacji
Atak korelacji
" Rozważmy tablicę prawdy dla funkcji:
" Przypuśćmy, że klucz (ziarno) ma
f(x,y,z) = xy Åð yz Åð z
postać:
" Aatwo pokazać, że:
X = 011, Y = 0101, Z = 11100
f(x,y,z) = x - z prawdopodobieństwem 3/4
bits i = 0,1,2,& 23
f(x,y,z) = z - z prawdopodobieństwem3/4
xi 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1
" Możemy to wykorzystać w celu
yi 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
odtworzenia klucza
zi 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1
ki 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1
Atak korelacji
Atak korelacji
" Mamy ciÄ…g generatora z tabeli
" Bierzemy X = 011
" Chcemy odtworzyć klucz
" Porównujemy 24 bitów X (i klucza)
" Zgadujemy X = 111, generujemy 24 bity
generowane przy zadanym X, porównujemy z
xi 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1
ki
xi 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 ki 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1
ki 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1
" Zgadza się 21 bitów z 24
" Spodziewane 3/4 trafień dla zadanego
" Znajdujemy 12 wartości z 24
przypadku
" Zgodnie z oczekiwaniami
" Znalezliśmy klucz dla X
8
2014-04-01
Atak korelacji
Atak korelacji
" W ogólnym przypadku&
" Jak kosztowny jest to atak?
X,Y,Z sÄ… odpowiednio 3,4,5 bitowe
" Mamy n rejestrów LFSR
" Musimy wypróbować około połowy możliwości zanim
O długościach N0,N1,& ,Nn-1
znajdziemy właściwe X
" Atak korelacji wymaga
" Następnie połowę możliwości zanim znajdziemy Y i
połowę zanim znajdziemy Z
" Z tego wynika, że musimy sprawdzić:
" Atak przeglądu zupełnego:
22 + 23 + 24 < 25
" Przegląd zupełny natomiast: 211
Wnioski
" Generator musi być silny kryptograficznie
Kluczowa własność: nieprzewidywalność
" Mamy do dyspozycji sporo teorii zwiÄ…zanych
z LFSR
Algorytm Berlekamp-Massey
Przykładowe algorytmy
oraz wiele innych teorii matematycznych
" LFSR mogą być wykorzystane przy
konstrukcji algorytmów strumieniowych
Musimy zapewnić odporność na atak korelacji
Zależy od własności funkcji f
Generator Blum-Micali Generator Blum-Blum-Shub BBS
" Znajdujemy dwie duże liczby pierwsze p i q,
" W generatorze tym wykorzystuje sie
takie, że p ºð3 (mod 4) oraz q ºð 3 (mod 4);
trudność w obliczaniu logarytmu
N = pq.
dyskretnego.
Wybieramy losowa liczbę x względnie pierwszą z N, a
" Wybieramy dwie liczby pierwsze a i p oraz
następnie obliczamy
liczbę x0 (zarodek), a następnie obliczamy
x0 = x2 (mod N)
x0 stanowi zarodek dla generatora.
xi+1 = axi (mod p) dla i = 1, 2, 3, . . .
Liczymy
xi+1 = xi2(mod N)
Generowanym bitem ki jest najmłodszy bit xi+1.
9
2014-04-01
Algorytmy oparte na LFSR A5/1
" Generatory Stop-and-Go :
" A5/1 składa się z 3 rejestrów przesuwnych
Jeden lub więcej LFSR wykorzystany jako zegar
X: 19 bit (x0,x1,x2, & ,x18)
3xLFSR
Y: 22 bit (y0,y1,y2, & ,y21)
Jeżeli x(1) == 0, LFSR2 jest przesuwany; w przeciwnym
Z: 23 bit (z0,z1,z2, & ,z22)
przypadku LFSR3. WyjÅ›cie = x(2) Åð x(3).
" A5 (GSM):
3x LFSRs; 64 bitów w sumie.
ZÅ‚amany przez Biryukov & Shamir, 1999
" E0 (Bluetooth)
4x LFSR; 128 bit w sumie.
A5/1
A5/1
" W każdym kroku: m = maj(x8, y10, z10)
X
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18
np.: maj(0,1,0) = 0 and maj(1,1,0) = 1
Åð
" If x8 = m then X
Y y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21
t = x13 Åð x16 Åð x17 Åð x18
Åð
xi = xi-ð1 for i = 18,17,& ,1 and x0 = t
Åð
" If y10 = m then Y
Z z0 z1 z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12 z13 z14 z15 z16 z17 z18 z19 z20 z21 z22
t = y20 Åð y21
yi = yi-ð1 for i = 21,20,& ,1 and y0 = t
Åð
" If z10 = m then Z
" Wartości wyjściowe pojedyncze bity
t = z7 Åð z20 Åð z21 Åð z22
" Klucz początkowe wypełnienie rejestrów
zi = zi-ð1 for i = 22,21,& ,1 and z0 = t
" Rejestry przesuwają się w zależności od (x8, y10, z10)
" CiÄ…g wyjÅ›ciowy: x18 Åð y21 Åð z22
" Wyjściem jest wartość XOR prawych bitów rejestrów
A5/1
X
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Åð
Y
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 Åð
Åð
Dziękuję za uwagę
Z
1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1
Åð
" np., m = maj(x8, y10, z10) = maj(1,0,1) = 1
" Rejestr X przesuwamy, Y nie i Z przesuwamy
" Wartość wyjÅ›cia: 0 Åð 1 Åð 0 = 1
10
Wyszukiwarka
Podobne podstrony:
analiza algorytmow2009 12 Metaprogramowanie algorytmy wykonywane w czasie kompilacji [Programowanie C C ]6 6 Zagadnienie transportowe algorytm transportowy przykład 2! Średniowiecze algoryzm sredniowiecznyAlgorytmy genetyczne a logika rozmytaLekcja algorytmy w geometriiAlgorytm Wstrzas anafilaktycznyTechnologie informatyczne 6 algorytmy 1Algorytmy grafowe, wykładAlgorytmy genetyczne i procesy ewolucyjne Wykład 2Algorytmy wyklad 1Algorytm obliczania parametrów termodynamicznych03 Implementacja komputerowa algorytmu genetycznegoAlgorytm genetyczny – przykład zastosowaniaalgorytmy ewolucyjneSTRUMIENICE OPISPLC mgr wyklad 11 algorytmywięcej podobnych podstron