2014-04-01

1

Bezpieczeństwo

i ochrona danych

Algorytmy strumieniowe

Agenda

• Podstawowe pojęcia
• Algorytmy synchroniczne i asynchroniczne
• Algorytmy z rejestrem przesuwnym
• Algorytm Berlekampa-Masseya
• Atak korelacji
• Przykładowe algorytmy

Algorytmy strumieniowe

• Uogólnienie koncepcji szyfrowania z kluczem

jednorazowym -

one-time pad (OTP)

• Możliwość szacowania bezpieczeństwa

i większa praktyczność niż OTP

• Algorytm jest inicjowany przy pomocy

krótkiej tajnej wartości stanowiącej

klucz

• Klucz jest ‘rozciągany’ do długiego ciągu

stanowiącego

klucz szyfrowania

Algorytmy strumieniowe

• Klucz szyfrowania jest wykorzystywany

zgodnie z ideą klucza jednorazowego

TJ xor Klucz = TT

• Podstawą jest generator ciągów

pseudolosowych

• Generowane są ‘losowe’ pojedyncze bity lub

bajty

Algorytmy strumieniowe

• 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.

4. Dla wszystkich możliwych wartości ziarna, zachowana

będzie pewna minimalna, dopasowana do zastosowania,
długość cyklu PRNG.

Algorytm strumieniowy

• Ogólny schemat algorytmu

2014-04-01

2

Algorytm strumieniowy

• Wyróżnia się algorytmy

– Synchroniczne
– Asynchroniczne

Algorytmy synchroniczne

Algorytm synchroniczne

• Synchroniczne szyfry strumieniowe:

– strumień klucza jest generowany

nieżalenie od zawartości tekstu jawnego
oraz szyfrogramu

– jest potrzebna synchronizacja

• nadawca i odbiorca musza być

zsynchronizowani.

Algorytmy synchroniczne

• Nie ma propagacji błędów

– pojedynczy błąd nie ma wpływu na kolejne

porcje danych

– nadaje sie do sytuacji o dużym

prawdopodobieństwie błędu transmisji

• Podatny na ataki zmiany bitów

– zmiana bitu w szyfrogramie powoduje zmianę

bitu w rozszyfrowanej wiadomości

• Podatność na ataki wstawiania i usuwania

bitów szyfrogramu

– utrata synchronizacji

Algorytm synchroniczne

s

i

+1

=

f(

s

i

,k)

z

i

=g(

s

i

,k)

c

i

=h(z

i

,m

i

)

Algorytmy synchroniczne

2014-04-01

3

Algorytmy synchroniczne

Deszyfrowanie

c

i`

mi

h

-1

Algorytmy synchroniczne

• Jeśli transformacja h łącząca strumień

klucza wraz ze strumieniem tekstu
jawnego jest funkcja XOR, wówczas błędy
bitowe w pewnych pozycjach szyfrogramu,
będą miały wpływ tylko na odpowiednie
pozycje tekstu jawnego.

Algorytmy asynchroniczne

Algorytmy asynchroniczne

• Asynchroniczne szyfry strumieniowe, nazywane

także samo-synchronizujacymi szyframi
strumieniowymi

– generowany strumień klucza jest zależny od:

• wartości klucza
• 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

• Generator strumienia szyfrującego używa kilku

poprzednich bitów szyfrogramu przy
generowaniu kolejnych elementów ciągu.

• Pojedynczy błąd rozprzestrzenia sie na kilka

kolejnych elementów szyfrogramu.

• Powrót do poprawnego deszyfrowania po

wstawieniu lub usunięciu bitów (czyli po stracie
synchronizacji) jest automatyczny.

Algorytmy asynchroniczne

• Asynchroniczne szyfry strumieniowe są szyframi

z pamięcią.

– bufor dla szyfrogramów stanów poprzednich.

• Problem wygenerowania strumienia klucza w

pierwszych t-chwilach.

• Jedna z technik rozwiązania tego problemu

– użycie dla pierwszych t-chwil wektora

inicjalizującego IV.

2014-04-01

4

Algorytmy asynchroniczne

• Jedną z podstawowych własności tych szyfrów

jest samosynchronizacja.

– proces deszyfrowania zależny jest tylko od t stanów

poprzednich, a nie jak w przypadku szyfrów
synchronicznych od wszystkich stanów.

– propagacja błędów jest ograniczona do t

szyfrogramów.

Algorytmy asynchroniczne

• Dobre własności statystyczne

– każdy bit tekstu jawnego wpływa na wartość

szyfrogramu, statystyczne własności tekstu jawnego
ulegają rozrzuceniu w obrębie wszystkich
szyfrogramów,

– odporniejsze na ataki bazujące na redundancji tekstu

jawnego.

Algorytmy z rejestrem przesuwnym

Rejestr przesuwny

• Tradycyjne algorytmy strumieniowe

wykorzystywały rejestry przesuwne

• Obecnie jest większa różnorodność podejść

projektowych

• 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

)

• Przykład (nieliniowej) funkcji sprzężenia

zwrotnego

f(x

i

, x

i+1

, x

i+2

) = 1



x

i



x

i+2



x

i+1

x

i+2

• Przykład (nieliniowy) rejestru przesuwnego

• Pierwsze 3 bity są inicjowane losową

wartością (

ziarno) -

(x

0

, x

1

, x

2

)

Rejestr przesuwny

LFSR

• Przykład rejestru LFSR

• x

i+5

= x

i



x

i+2

dla każdego i

• Jeżeli ziarno (x

0

,x

1

,x

2

,x

3

,x

4

) = 01110

wtedy (x

0

,x

1

,…,x

15

,…) = 0111010100001001…

2014-04-01

5

LFSR

• Dla LFSR

• Mamy x

i+5

= x

i



x

i+2

dla każdego i

• Funkcja sprzężenia zwrotnego jest zapisywana w

postaci wielomianu: x

5

+ x

2

+ 1

• Wielomian połączeniowy

rejestru LFSR

Algorytmy strumieniowe oparte na
rejestrze przesuwnym

• Dwa podejścia do wykorzystania LFSR na

potrzeby szyfrowania:

– Jeden rejestr LFSR z nieliniową funkcją

połączeń

– Kilka LFSR połączonych nieliniową funkcją

• Kluczem jest początkowe wypełnienie

LFSR (ziarno)

• Ciąg szyfrujący stanowi wyjście rejestru

(zestawu rejestrów)

Algorytmy strumieniowe oparte na
rejestrze przesuwnym

• Wiele rejestrów LFSR z funkcją nieliniową



Ciąg wyjściowy: k

0

,k

1

,k

2

,…

Algorytmy strumieniowe oparte na
rejestrze przesuwnym

• 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 LFSR

0

,…LFSR

n-1

będą identyczne

– Ziarno LFSR

0

jest identyczne z ziarnem LFSR

– Ziarno LFSR

1

jest identyczne z zawartością LFSR z

kroku pierwszego

– Itd.

Algorytm Berlekampa-Masseya

• Dysponując częścią okresowego

strumienia, możemy znaleźć najkrótszy
LFSR, który wygenerowałby taką
sekwencję

• Algorytm Berlekamp-Massey

– Wymiar problemu N

2

, gdzie N jest długością

LFSR

– Algorytm iteracyjny
– Potrzebuje jedynie 2N kolejnych bitów

Algorytm Berlekampa-Masseya

• Sekwencja bitów: s = (s

0

,s

1

,s

2

,…,s

n-1

)

• Liniowa złożoność L sekwencji s

jest

najmniejszym rozmiarem LFSR generującym s

• Niech L będzie liniową złożonością s
• Wtedy C(x) jest wielomianem definiującym

połączenia rejestru o następującej postaci:

C(x) = c

0

+ c

1

x + c

2

x

2

+ … + c

L

x

L

• Algorytm Berlekamp-Massey pozwala określić

L i C(x)

2014-04-01

6

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 algorytmu

• Generowana sekwencja jest dobra jeżeli spełnia

kryteria

generatora pseudolosowości

• Dobry generator musi być ‘

nieprzewidywalny’

– Znany ciąg udostępnia informacje o generatorze
– Nie można uzyskać wiedzy na temat przyszłych

elementów ciągu na podstawie znajomości
wcześniejszych wartości

• Mała złożoność generatora = przewidywalność

– Wniosek z algorytmu B-M

Moc sekwencji

• Aby ciąg był

bezpieczny kryptograficznie

–

generator musi posiadać dużą złożoność

• Nie jest to warunek wystarczający!
• Np. s = (s

0

,s

1

,…,s

n-1

) = 00…01

• Wtedy s ma złożoność n

– Najmniejszy rejestr przesuwny dla s wymaga n

stopni

– Największy z możliwych okresów - n
– Lecz nie jest kryptograficznie bezpieczny

• Złożoność “skoncentrowana” na ostatnim

bicie

Profil liniowej złożoności

• Profil liniowej złożoności

jest lepszą miarą

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 = (s

0

,s

1

,…,s

n-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

świetle tej definicji)

Profil liniowej złożoności

• Dobry profil złożoności liniowej

s

2014-04-01

7

k-błąd

• Stanowi alternatywną miarę jakości dla

generatorów

• Jeszcze raz: s = (s

0

,s

1

,…,s

n-1

) = 00…01

• s- duża złożoność, lecz tylko jeden bit poza

minimalną złożonością

• 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”

k-błąd

• k-błąd profilu liniowej złożoności

– k-błąd jako funkcja od k

•

Przykład:

•

Słaba sekwencja s

•

Dobry profil powinien

zbliżać się do przekątnej

Kryptograficznie silne sekwencje

• Liniowa złożoność musi być ‘duża’
• Profil liniowej złożoności musi być bliski

do ‘linii n/2’

• k-błąd profilu liniowej złożoności musi być

‘bliski’ przekątnej

• Wszystkie ww warunki są konieczne lecz

nie wystarczające.

Kryptograficznie silne sekwencje

• Testy jakości PRNG -16 testów statystycznych

(http://csrc.nist.gov/groups/ST/toolkit/rng)

– Frequency (Monobits) Test
– Test for Frequency within a Block
– Test for the Longest Run of Ones in a Block
– Random Binary Matrix Rank Test
– Discrete Fourier Transform (Spectral) Test
– Non-overlapping (Aperiodic) Template Matching Test
– Overlapping (Periodic) Template Matching Test
– Maurer's Universal Statistical Test
– Lempel-Ziv Complexity Test
– Linear Complexity Test
– …

Atak korelacji

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

konwersji

• Zgodnie z zasadą

Kerckhoffa zakładamy, że

rejestr i funkcje są znane.

• Jedynie nie jest znany klucz - ziarno

2014-04-01

8

Atak korelacji

• Celem jest odtworzenie początkowego stanu

rejestru LFSR

– Znamy wszystkie połączenia dla wielomianu

generującego i funkcji nieliniowej

– Znamy ciąg N bitów, k

0

,k

1

,…,k

N-1

• Czasami jest możliwe określenie

początkowego ustawienia LFSR niezależnie

– Poprzez korelację wyjścia LFSR z dostępnym

ciągiem bitów

– Poprzez typowy atak

dziel i rządź

Atak korelacji

• Przypuśćmy, że mamy do czynienia z

następującym generatorem:



f(x,y,z) = xy



yz



z



Klucz jest 12 b

Atak korelacji

• Przypuśćmy, że klucz (ziarno) ma

postać:

– X = 011, Y = 0101, Z = 11100

x

i

0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1

y

i

0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0

z

i

1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1

k

i

1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1

bits

i = 0,1,2,…23

Atak korelacji

• Rozważmy tablicę prawdy dla funkcji:

f(x,y,z) = xy



yz



z

• Łatwo pokazać, że:

f(x,y,z) = x - z prawdopodobieństwem 3/4

f(x,y,z) = z - z prawdopodobieństwem3/4

• Możemy to wykorzystać w celu

odtworzenia klucza

Atak korelacji

•

Mamy ciąg generatora z tabeli

•

Chcemy odtworzyć klucz

•

Zgadujemy X = 111, generujemy 24 bity
generowane przy zadanym X,

porównujemy z

k

i

k

i

1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1

x

i

1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1

•

Znajdujemy 12

wartości z 24

•

Zgodnie z oczekiwaniami

Atak korelacji

•

Bierzemy X = 011

•

Porównujemy 24 bitów X (i klucza)

k

i

1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1

x

i

0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1

•

Zgadza się 21 bitów z 24

•

Spodziewane 3/4

trafień dla zadanego

przypadku

•

Znaleźliśmy klucz dla X

2014-04-01

9

Atak korelacji

• Jak kosztowny jest to atak?

– X,Y,Z są odpowiednio 3,4,5 bitowe

• Musimy wypróbować około połowy możliwości zanim

znajdziemy właściwe X

• Następnie połowę możliwości zanim znajdziemy Y i

połowę zanim znajdziemy Z

• Z tego wynika, że musimy sprawdzić:

2

2

+ 2

3

+ 2

4

< 2

5

• Przegląd zupełny natomiast: 2

11

Atak korelacji

• W ogólnym przypadku…
• Mamy n rejestrów LFSR

– O długościach N

0

,N

1

,…,N

n-1

• Atak korelacji wymaga

• Atak przeglądu zupełnego:

Wnioski

• Generator musi być

silny kryptograficznie

– Kluczowa własność: nieprzewidywalność

• Mamy do dyspozycji sporo teorii związanych

z LFSR

– Algorytm Berlekamp-Massey
– 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

Przykładowe algorytmy

Generator Blum-Micali

• W generatorze tym wykorzystuje sie

trudność w obliczaniu logarytmu
dyskretnego.

• Wybieramy dwie liczby pierwsze

a

i

p

oraz

liczbę

x

0

(zarodek), a następnie obliczamy

x

i+1

= a

x

i

(mod p) dla i = 1, 2, 3, . . .

Generator Blum-Blum-Shub — BBS

• Znajdujemy dwie duże liczby pierwsze

p

i

q

,

takie, że p



3 (mod 4) oraz q



3 (mod 4);

N = pq

.

– Wybieramy losowa liczbę

x

względnie pierwszą z

N

, a

następnie obliczamy

x

0

= x

2

(mod N)

– x

0

stanowi zarodek dla generatora.

– Liczymy

x

i+1

= x

i

2

(mod N)

– Generowanym bitem

k

i

jest najmłodszy bit

x

i+1

.

2014-04-01

10

Algorytmy oparte na LFSR

• Generatory Stop-and-Go :

– Jeden lub więcej LFSR wykorzystany jako zegar
– 3xLFSR
– Jeżeli x

(1)

== 0, LFSR

2

jest przesuwany; w przeciwnym

przypadku LFSR

3

. 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 składa się z 3 rejestrów przesuwnych

– X: 19 bit (x

0

,x

1

,x

2

,

…,x

18

)

– Y: 22 bit (y

0

,y

1

,y

2

,

…,y

21

)

– Z: 23 bit (z

0

,z

1

,z

2

,

…,z

22

)

A5/1

• W każdym kroku: m = maj(x

8

, y

10

, z

10

)

– np.: maj(0,1,0) = 0 and maj(1,1,0) = 1

• If x

8

= m then X

– t = x

13



x

16



x

17



x

18

– x

i

= x

i



1

for i = 18,17,…,1 and x

0

= t

• If y

10

= m then Y

– t = y

20



y

21

– y

i

= y

i



1

for i = 21,20,…,1 and y

0

= t

• If z

10

= m then Z

– t = z

7



z

20



z

21



z

22

– z

i

= z

i



1

for i = 22,21,…,1 and z

0

= t

• Ciąg wyjściowy: x

18



y

21



z

22

A5/1

• Wartości wyjściowe – pojedyncze bity
• Klucz – początkowe wypełnienie rejestrów
• Rejestry przesuwają się w zależności od

(x

8

, y

10

, z

10

)

• Wyjściem jest wartość XOR prawych bitów rejestrów

y

0

y

1

y

2

y

3

y

4

y

5

y

6

y

7

y

8

y

9

y

10

y

11

y

12

y

13

y

14

y

15

y

16

y

17

y

18

y

19

y

20

y

21

z

0

z

1

z

2

z

3

z

4

z

5

z

6

z

7

z

8

z

9

z

10

z

11

z

12

z

13

z

14

z

15

z

16

z

17

z

18

z

19

z

20

z

21

z

22

X

Y

Z









x

0

x

1

x

2

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

10

x

11

x

12

x

13

x

14

x

15

x

16

x

17

x

18

A5/1

• np., m = maj(x

8

, y

10

, z

10

) = maj(

1

,

0

,

1

) =

1

• Rejestr X przesuwamy, Y nie i Z przesuwamy
• Wartość wyjścia: 0



1



0 = 1

1 1 0 0 1 1 0 0 1 1

0

0 1 1 0 0 1 1 0 0 0 1

1 1 1 0 0 0 0 1 1 1

1

0 0 0 0 1 1 1 1 0 0 0 1

X

Y

Z









1 0 1 0 1 0 1 0

1

0 1 0 1 0 1 0 1 0 1

Dziękuję za uwagę