2014-04-29 Agenda BezpieczeÅ„stwo " Ataki na funkcje skrótu i ochrona danych paradoks urodzinowy atak Nostradamusa " Ataki na implementacje RSA podstawy Ataki na jednokierunkowe teoretyczne funkcje skrótu oraz modularne potÄ™gowanie ^2 implementacjÄ™ algorytmu RSA mnożenie i redukcja Mongomerego mnożenie Karatsuba Problem urodzinowy Problem przed-urodzinowy " Jak wiele osób musi być w tym samym pokoju " Przypuśćmy, że jest N osób w pokoju aby prawdopodobieÅ„stwo znalezienia dwóch " Jak duże musi być N aby osób obchodzÄ…cych urodziny w tym samym dniu byÅ‚o wiÄ™ksze od ½ ? prawdopodobieÅ„stwo, że znajdziemy 1 -ð 365/365 ×ð 364/365 ×ð ×ð ×ð(365-ðN+1)/365 kogoÅ›, kto siÄ™ urodziÅ‚ w tym samym dniu Przyrównujemy do ½ i rozwiÄ…zujemy: co my sami bÄ™dzie Å‚ð ½? N = 23 RozwiÄ…zanie: ½ = 1 -ð (364/365)N dla N " Dziwne? Paradoksalne? Czyli N = 253 " Nie. Powinno być okoÅ‚o sqrt(365) ponieważ poszukujemy par x i y Urodziny i funkcje skrótu Atak urodzinowy na podpis " Jeżeli h(x) ma N bitów, ma 2N różnych wartoÅ›ci " Przypuśćmy, że mamy n-bitowÄ… funkcjÄ™ skrótu " Zauważmy, że sqrt(2N) = 2N/2 " Malkolm generuje dokument (MZ), w którym " StÄ…d przy 2N/2 różnych wejÅ›ciach możemy liczyć na Alicja przyznaje siÄ™ do napadu na bank wystÄ…pienie kolizji. Chce dostać podpis Alicji pod wiadomoÅ›ciÄ… (MZ) atak urodzinowy przeszukiwanie kompletne Malkolm generuje petycjÄ™ dotyczÄ…cÄ… zwolnienia z " N-bitowy symetryczny algorytm wymaga okoÅ‚o 2N-ð1 egzaminu wszystkich osób, których imiÄ™ zaczyna siÄ™ sprawdzeÅ„ aby znalezć klucz na A (MD) " Dla N-bitowej funkcji skrótu: wystarczy 2N/2 tylko Alicja chÄ™tnie podpisuje wiadomość (MD) Jak Intruz może wykorzystać paradoks urodzinowy aby uzyskać podpis pod wiadomoÅ›ciÄ… (MZ)? 1 2014-04-29 Atak urodzinowy na podpis Atak urodzinowy na podpis " Intruz generuje 2n/2 wariantów (MD) " Alicja podpisaÅ‚a niewinnÄ… petycjÄ™ MD,j Wszystkie majÄ… takie same znaczenie jak P " Intruz ma [h(MD,j)]Alicja Generuje wartoÅ›ci f-cji skrótu: h(MD,0),h(MD,1),& " Ale " Intruz generuje 2n/2 wariantów Mz [h( MD,j)]Alicja = [h(MZ,k)]Alicja Wszystkie majÄ… takie same znaczenie jak MZ Obliczamy wartoÅ›ci skrótów: h(MZ,0),h(MZ,0),& " Alicja nieroztropnie podpisaÅ‚a " Paradoks urodzin mówi nam, że dla pewnego j szkodliwy donos MZ,0 oraz k otrzymamy h(MD,j)= h(MZ,k) " Atak wykorzystuje tylko paradoks urodzin Aukcje online Aukcje online " Niech Ala, Bolek, Czarek uczestniczÄ… w aukcji " Protokół nie jest bezpieczny! " Ala obstawia A, Bolek B i Czarek C " Jest możliwy atak poszukiwania ChcÄ… zachować tajność stawek wstecznego " RozwiÄ…zanie Ala, Bolek i Czarek zgÅ‚aszajÄ… skróty h(A),h(B),h(C) Bolek oblicza h(A) dla domniemanego A Skróty sÄ… zgÅ‚aszane elektronicznie online " Jak zapobiec? NastÄ™pnie można ujawnić wartoÅ›ci A, B, C " Ala oblicza h(A,R), R jest losowe " Skróty nie ujawniajÄ… wartoÅ›ci Alicja musi ujawnić A oraz R " Nie można zmienić stawki po wysÅ‚aniu (brak Intruz nie jest w stanie sprawdzić wszystkich kolizji) A i R Aukcje online Aukcje online " SÅ‚aba odporność na kolizje " Niech B = $1000 oraz Bolek zgÅ‚asza dla każdego danego bloku x, znalezienie h(B,R) takiego y różnego od x, dla którego H(y)=H(x) " Ujawniamy: A = $1 oraz C = $2 nie jest wykonywalne na drodze obliczeÅ„ " Bolek chce zmienić swojÄ… propozycjÄ™ na: Bóð = $3 " Odporność na kolizje znalezienie pary (x,y), że H(y)=H(x) nie jest " Bolek oblicza h(Bóð,Róð) dla różnych Róð aż wykonywalne na drodze obliczeÅ„ znajdzie h(Bóð,Róð) = h(B,R) Jak wiele możliwoÅ›ci musi sprawdzić? OkoÅ‚o 2n skrótów 2 2014-04-29 Atak sÅ‚abych kolizji Przewidywanie przyszÅ‚oÅ›ci " Atak na kolizje dla zadanego skrótu wymaga " Intruz twierdzi, że potrafi przewidzieć przyszÅ‚ość nakÅ‚adu okoÅ‚o 2n operacji " 1 stycznia 2014, ogÅ‚asza y, twierdzÄ…c, że y = h(x) Gdzie x jest kursem PLN/EUR w dniu 30.05.2014 " Atak na dowolnÄ… kolizjÄ™ wymaga jedynie " 1 czerwca 2014, Intruz ujawnia x takie, że y = h(x) okoÅ‚o 2n/2 I wszystko siÄ™ zgadza & (x jest kursem PLN/EUR w dniu " Atak Nostradamusa rozwiÄ…zuje problem 30.05.2014) kolizji przy tylko 2n/2 skrótach " Czy to dowodzi nadprzyrodzonych zdolnoÅ›ci Intruza? np. w przypadku naszej aukcji online można wykorzystać np. dla skrótu Merkle- Damgard Przewidywanie przyszÅ‚oÅ›ci Atak Nostradamusa " Intruz podaje wartość y " Nostradamus (1503-1566) Niektórzy twierdzÄ…, że potrafiÅ‚ przewidzieć " Niech P bÄ™dzie kursem PLN/EUR w dniu przyszÅ‚ość 30.05.2014 Lecz można to sprawdzić jedynie w formie " Jeżeli Intruz nie potrafi przewidywać retrospektywy przyszÅ‚oÅ›ci, to musi znalezć takie S, że " Atak Nostradamusa y = h(P,S) Intruz może przewidzieć przyszÅ‚ość " Intruz może próbować 2n różnych skrótów S Zamienia rzÄ…d problemu przepowiedni z 2n na 2n/2 Lecz jest to pracochÅ‚onne Ma zastosowanie dla dowolnej funkcji skrótu Może da siÄ™ szybciej? Merkle-Damgard Struktura diamentu Atak Nostradamusa " Wybieramy " Obliczanie kolizji: praca rzÄ™du 2×ð2n/2 losowo M0 Porównanie jednego zbioru z drugim " Obliczamy " Przygotować kolizjÄ™ w inteligentny sposób d00 = f(IV,M0) " Tak aby zdeterminować y wartość skrótu " oraz M1,& ,M7 " Jeżeli zdefiniujemy P, możemy wymóc qðZnajdujemy M00,M01 dajÄ…ce kolizjÄ™: wartość skrótu y d10 = f(d00,M00) = f(d01,M01) Potrzeba nam okreÅ›lonego S qðKontynuujemy: y = d30 jest poszukiwanym skrótem 3 2014-04-29 Atak Nostradamusa Atak Nostradamusa " Skoro tylko znajdzie Sóð " Obliczenia wstÄ™pne Przechodzi Å›cieżkÄ… od d0j do dk0 Oblicz wartoÅ›ci struktury diamentowej o " W przypadku prezentowanej struktury diamentu, wysokoÅ›ci 2k jeżeli Intruz odkryÅ‚, że f(IV,P,Sóð) = d02 Wybierz y = dk0 jako przepowiadany skrót " Wtedy h(P,Sóð,M02,M11,M20) = d30 = y " Kiedy skrót przepowiedni jest znany, Przypominamy, że y jest skrótem przepowiedni Intruz: " Niech x = (P,Sóð,M02,M11,M20) Niech P bÄ™dzie przepowiedniÄ… " Oraz x jest wartoÅ›ciÄ… przepowiedni: P jest kursem PLN/EUR w dniu 30.05.2014, Wybiera losowo Sóð, gdzie (P,Sóð) jeden blok Sóð,M02,M11,M20 wartoÅ›ciÄ… losowÄ… uniemożliwiajÄ…cÄ… atak Aż do znalezienia takiego f(IV,P,Sóð)=d0j dla przeszukania wstecz na przepowiedniÄ™ pewnego j Atak Nostradamusa Atak Nostradamusa " Jak kosztowny? " W celu zminimalizowania kosztu " ZakÅ‚adajÄ…c, że struktura diamentu ma wysokość przyrównajmy dwie wartoÅ›ci z 2k i funkcja skrótu ma wyjÅ›cie n bitowe poprzedniego slajdu w celu znalezienia k - Z jednej stron mamy: 2×ð2n/2(2k -ð 1) H" 2n/2+k+1 " Mamy n/2 + k/2 + 1 = n -ð k co daje Można zredukować do 2n/2+k/2+1 k = (n -ð 4)/3 - Z drugiej chcemy osiÄ…gnąć zysk wymiaru: 2n-ðk " Dla MD4 lub MD5, n = 128, wiÄ™c k = 41 " Struktura diamentu o wysokoÅ›ci 241 " Ostateczny koszt ataku to 287 Nostradamus RSA " Atak wymierzony przeciw algorytmom " RSA opartym na idei Merkle-Damgard Klucz publiczny: (e,N) " Nie jest praktyczny dla funkcji 128-bit Klucz prywatny: d " Szyfrowanie M " Ostatecznie korzystanie ze skrótu w C = Me (mod N) celu przekonania kogoÅ› o czymÅ› nie jest " Deszyfrowanie C tak bezpieczne jak siÄ™ wydawać może & M = Cd (mod N) 4 2014-04-29 PotÄ™gowanie modularne Ataki na implementacje RSA " Ataki zwiÄ…zane ze specyfikÄ… potÄ™gowania " Ataki na implementacje RSA modulo Nie ma ataków w sensie Å›cisÅ‚ym na algorytm RSA " Dla zwiÄ™kszenia wydajnoÅ›ci implementacja " ZależnoÅ›ci czasowe potÄ™gowania modulo korzysta z pewnej PotÄ™gowanie jest kosztowe obliczeniowo kombinacji: Wykorzystanie różnic w czasie obliczeÅ„ pojawiajÄ…cych Powtarzania operacji podnoszenia do potÄ™gi 2 siÄ™ dla różnych wykÅ‚adników (kluczy prywatnych) ChiÅ„skiego twierdzenia o resztach (Chinese " Ataki na bÅ‚Ä™dy Remainder Theorem - CRT) Wstrzykiwanie bÅ‚Ä™dów może spowodować ujawnienie Mnożenia Montgomery informacji o kluczu prywatnym Okna przesuwnego (Sliding window) Mnożenia Karatsuba Powtarzanie ^2 Powtarzanie ^2 " PrzykÅ‚ad potÄ™gi modulo " Algorytm 520 = 95367431640625 = 25 mod 35 // oblicz y = xd (mod N) // gdzie binarnie d = (d0,d1,d2,& ,dn) with d0 = 1 " Lepiej: powtarzanie ^2 o 20 = 10100 (binarnie) s = x o (1, 10, 101, 1010, 10100) = (1, 2, 5, 10, 20) for i = 1 to n o Czyli 2 = 1×ð 2, 5 = 2 ×ð 2 + 1, 10 = 2 ×ð 5, 20 = 2 ×ð 10 s = s2 (mod N) o 51= 5 mod 35 if di == 1 then o 52= (51)2 = 52 = 25 mod 35 s = s ×ð x (mod N) o 55= (52)2 ×ð 51 = 252 ×ð 5 = 3125 = 10 mod 35 o 510 = (55)2 = 102 = 100 = 30 mod 35 end if o 520 = (510)2 = 302 = 900 = 25 mod 35 next i " Brak wielkich liczb + wzrost wydajnoÅ›ci return s W tym przypadku, 5 kroków vs 20 Okno przesuwne ChiÅ„skie Twierdzenie o resztach " Jedno z zasadniczych twierdzeÅ„, wiążące " Problem czas vs pamięć dla algorytmu ^2 wÅ‚asnoÅ›ci liczby caÅ‚kowitej n z wÅ‚asnoÅ›ciami jej " Zamiast przetwarzać bit po bicie& czynników w rozkÅ‚adzie na iloczyn potÄ™g liczb " & przetwarzane jest n bitów w jednym pierwszych, jest twierdzenie noszÄ…ce nazwÄ™ kroku chiÅ„skiego twierdzenia o resztach. Wykorzystanie wczeÅ›niej obliczonych wartoÅ›ci przechowywanych w pamiÄ™ci Zazwyczaj n = 5 5 2014-04-29 ChiÅ„skie Twierdzenie o resztach ChiÅ„skie Twierdzenie o resztach " JeÅ›li liczby caÅ‚kowite dodatnie: " Chinese Remainder Theorem (CRT) n1, n2, n3, ... , nk " Chcemy obliczyć: sÄ… parami wzglÄ™dnie pierwsze, zaÅ› Cd (mod N) gdzie N = pq a1, a2, a3, ... , ak " DziÄ™ki CRT, możemy obliczyć Cd mod p oraz q, a sÄ… dowolnymi liczbami caÅ‚kowitymi, to istnieje potem skleić wynik taka liczba caÅ‚kowita a, że: " Dwa dzielenia modulo rozmiaru N1/2 a a" a1(mod n1), Zamiast pojedynczego o rozmiarze N a a" a2(mod n2), " CRT daje możliwość znacznego przyspieszenia ........................... obliczeÅ„ a a" ak(mod nk), Algorytm CRT Algorytm CRT " KorzystajÄ…c z wczeÅ›niej obliczonych wartoÅ›ci " Dane: " C, d, N, p,q " Obliczamy: oraz " Szukane: Cd (mod N) gdzie N = pq " nastÄ™pnie: " Oblicz oraz dp = d (mod (p -ð 1)) oraz dq = d (mod (q -ð 1)) " Wynik: " A nastÄ™pnie a oraz b takie, że a = 1 (mod p) oraz a = 0 (mod q) b = 0 (mod p) oraz b = 1 (mod q) PrzykÅ‚ad CRT CRT " Niech N = 33, p = 11, q = 3 oraz d = 7 " Sprawia wrażenie dużej pracochÅ‚onnoÅ›ci Wtedy e = 3 (lecz jest zbÄ™dne w tym przykÅ‚adzie) " Lecz jest wrÄ™cz przeciwnie dużym " Oblicz zyskiem dp = 7 (mod 10) = 7 oraz dq = 7 (mod 2) = 1 Daje możliwość 4-krotnego przyspieszenia " Oraz , a = 12, b = 22 speÅ‚niajÄ… warunki obliczeÅ„ " Niech C = 5 Chcemy obliczyć Cd = 57 (mod 33) " Problemy? Znajdz Cp = 5 (mod 11) = 5 oraz Cq = 5 (mod 3) = 2 Czynniki p oraz q liczby N muszÄ… być znane NastÄ™pnie xp = 57 = 3 (mod 11), xq = 21 = 2 (mod 3) Czynniki te powinny być znane jedynie " Sprawdz: 57 = 3 ×ð 12 + 22 ×ð 2 = 14 (mod 33) wÅ‚aÅ›cicielowi klucza prywatnego! 6 2014-04-29 CiÄ…g dalszy (zastosowania) Na nastÄ™pnym wykÅ‚adzie 7