Crypto 2013: dzień czwarty

Czwarty dzień zaczął się od prezentacji dra Macieja Obremskiego na temat pracy członków zespołu CryptoUW pt. "Non-malleable codes from two-source extractors" (współautorami są: dr hab. Stefan Dziembowski oraz niżej podpisany). Ponieważ pewnie nie wypada skupiać się właśnie na tym, napiszę co mnie zainteresowało poza tą prezentacją.

Moją uwagę przykuł referat "Optimal Coding for Streaming Authentication and Interactive Communication". Autorzy wracają w nim do znanego problemu przesyłania wiadomości przez zaszumiony kanał. Istotą komunikacji w takim warunkach jest automatycznia korekcja błędu wysyłanych komunikatów. Istnieją już dobre rozwiązania tego problemu: polegają na przesyłaniu pewnej redundantnej informacji, która ułatwia odczytanie częściowo (być może złośliwie) zmienionej informacji.

To, co nowego, zrobili autorzy, to rozwiązali problem przy ogólniejszych założeniach. Dotychczas zakładano, że długość wiadomości $n$ jest z góry znana, a wysyłający od razu wie, jaką wiadomość chce wysłać. W referowanej pracy, te założenia osłabiono: pokazano protokół dla komunikacji strumieniowej, potencjalnie nieskończonej.

Aby zachęcić do sięgnięcia po wersję papierową wystąpienia, dodam, że rozwiązanie jest wysoce nietrywialne. Łatwo chociażby zauważyć, że blokowe wysyłanie kolejnych fragmentów wiadomości długości $n$ jakimś znanym wcześniej kodowaniem nie może działać - zgubienie jednego bloku jest niewielkim (a więc dopuszczalnym) zaszumieniem, a przecież uniemożliwia odtworzenie całej wiadomości.

Na sam koniec pozwolę sobie (jak to ja) na uwagę natury bardziej filozoficznej. Tendencja, aby robić wyniki już znane, ale przy słabszych założeniach, jest zauważalna na całej konferencji. To chyba dobry kierunek. Przykładem takiego myślenia jest cała gałąź kryptografii, którą zajmuje się CryptoUW, tzn. wycieki (ang. leakage).

Crypto 2013: dzień drugi

Najciekawszą prezentacją drugiego dnia, moim zdaniem, była "Key Homomorphic PRFs and Their Applications".  Autorami pracy są Dan Boneh, Kevin Lewi, Hart Montgomery(prezentujący) i Ananth Raghunathan, wszyscy z Uniwerytetu Stanforda. 

Z trzech powodów było to niezwykle mile spędzone 20 minut: po pierwsze praca porusza niezmiernie ciekawe problemy, po drugie prezentowane rozwiązania są wyjątkowo eleganckie, w końcu po trzecie sama prezentacja była dobrze przemyślana i zrozumiała dla chyba wszystkich niezależnie od tematyki jaką się zajmują.

Nie chcę wchodzić zbytnio w szczegóły techniczne i nie zaprezentuję samej konstrukcji zamiast tego skupię się na jednym dość ciekawym zastosowaniu.

Niech $f(k,x)$ będzie funkcją pseudolosową, to znaczy, że jeśli nie znamy klucza $k$ wartości $f(k, \, )$ będą dla nas nieodróżnialne od kompletnie losowych. Na przykład jeśli poznamy $f(k,1)$, $f(k,2)$, $f(k,3)$ to bez znajomości klucza nie mamy szans na zgadnięcie $f(k,4)$.

Załóżmy, że chcemy połączyć się z jakimś serwerem. Zarówno serwer jak i my jesteśmy w posiadaniu tajnego klucza (ciągu bitów) $k$. Pierwszą fazą w nawiązywaniu połączenia jest udowodnienie serwerowi, że my to my (tj. że jesteśmy w posiadaniu klucza $k$). 

Jak to zrobić?

Może wyślijmy do serwera nasz klucz i serwer sprawdzi czy wszystko się zgadza? Niestety, jeśli ktoś podsłucha transmisje to wejdzie w posiadanie tajnego klucza. Potrzebujemy zatem lepszego rozwiązania.

Może niech serwer wybierze dowolną wartość $x$ i poprosi byśmy odpowiedzieli wartością $f(k,x)$? Nawet jeśli nasza transmisja zostanie podsłuchana przeciwnik pozna jedynie poprawną odpowiedź na jedno, konkretne, pytanie, jest niezwykle mało prawdopodobne, że serwer następnym razem zapyta o tę samą liczbę. Takie rozwiązanie jest poprawne.

Autorzy pracy dostrzegają jednak istotny minus takiej konstrukcji. Jeśli jakiś haker złamie zabezpieczenia serwera to za jednym zamachem otrzyma cały nasz klucz $k$ składowany na serwerze i będzie się mógł pod nas podszywać. Odpowiedzią na ten problem jest następujący pomysł autorów pracy.

Skonstruujmy trochę lepszą funkcję pseudolosową: jeśli $k=k_1+k_2$ to niech $f(k,x)=f(k_1,x)+f(k_2,x)$. Pomysł jest więc taki, by nasz klucz $k$ podzielić na wiele części $k_1, k_2, k_3,…,k_n$ i każdą z nich składować na innym serwerze.

Uwierzytelnianie (dowodzenie, że ja to ja) będzie wtedy wyglądało następująco. Serwer prosi o wartość funkcji w $x$, my odpowiadamy $f(k,x)$ teraz serwer prosi o kolejne wartości $f(k_i,x)$ kolejne serwery (w żadnym momencie klucze nie opuszczają serwerów na których są składowane), teraz wystarczy że serwer sprawdzi czy przesłane przez nas $f(k,x)$ jest równe $f(k_1,x)+f(k_2,x)+ f(k_3,x)+…+f(k_n,x)$.

Przewagą tego rozwiązania nad poprzednim jest to, że teraz haker musi włamać się do wszystkich serwerów by móc podszywać się pod nas co jest niewątpliwie znacznie trudniejsze niż włamanie do pojedynczego serwera. 

Wszystko pięknie, tylko czy taka funkcja istnieje? Nie tylko istnieje. Dzięki "Key Homomorphic PRFs and Their Applications" znamy jej konstrukcję!

Autor: dr Maciej Obremski

Uwaga: artykuł ma charakter popularnonaukowy i zawiera pewne uproszenia

Crypto 2013: dzień trzeci

Dzisiaj swój wykład miał zwycięzca konkursu na najlepszą pracę konferencji. Wygrał Gologlu et al z pracą "One the Function Field Sieve and the Impact of Higher Splitting". Praca dotyczyła teorii liczb, ogólnie była chwalona. Nie jest to jednak moja działka, więc nie chcę wypowiadać się ekspercko na temat tego rezultatu.

Dla mnie największe wrażenie zrobiła sesja nr 13, czyli zagadnienia obliczeń wielopodmiotowych. Zaczął Yuval Ishai. To jedna z tych osób, które ma zawsze świetne przygotowane wystąpienia. Jednoczeście wykład był wyjątkowy interesujący dla mnie. Autor mówił jak zrobić gadżet podobny do obwodu Yao, ale bardziej skompresowany. To jest o tyle ciekawe, że obwody Yao wykorzystywałem osobiście w pracy "One-Time Programs with Limited Memory". Mogę więc teraz zastanowić się, czy nie da się zastąpić tej nowo zaproponowanej konstrukcji w swej starej pracy. Dzięki temu pewnie poprawią się parametry. Po takich wykładach dokładnie rozumie się, co to znaczy "środowisko naukowe". Badania to praca zespołowa!

Jako drugi w tej sesji swą pracę przedstawiał Ron Rothblum. Wynik znowu ciekawy. Idea jest taka: ile trzeba "przekupić" osób, żeby czegoś się dowiedzieć w jakimś obliczeniu wielopodmiotowym? Ogólne oszacowania są znane. Ale co, gdy ograniczymy np. głębokość drzewiastą funkcji, którą obliczamy? Wtedy da się zrobić to lepiej.

Crypto 2013: dzień pierwszy

Za nami pierwszy dzień bodaj najlepszej konferencji kryptograficznej, CRYPTO. Jak zawsze w Santa Barbara, w Południowej Kalifornii.

Tutaj każdy kryptograf czuje się jak w raju: przez kilka dni w jednym miejscu obcować można z pięknym miejscem, na pięknym kampusie, wśród pięknej fauny i flory, słuchając pięknych referatów. Surferzy na deskach na wysokich falach, szyfry symetryczne, wyrafinowane własności twierdzenia min-max, pelikany, szopy, kody niekowalne, podział sekretu, pelikany, szopy... Wszystko to miesza się jak w kalejdoskopie, a dusza i ciało mają ucztę w każdym sensie. Wszystkie poziomy potrzeb w kryteriach Maslowa wydają się być jednocześnie zaspakajane.

Może piszę trochę rzewnie, ale przecież inaczej się nie da. Żeby poczuć CRYPTO, trzeba zrozumieć, że tutaj wszystko się przeplata: rano śniadanie na tarasie De La Guerra, potem pospiesznie na pierwszą sesję wykładów. A tam Fully Homomorphic Encryption, czyli coś bardzo świeżego i aktualnego. Mi podobał się wykład Micciancio na temat swoich wyników z SIS i LWE - poprawił trochę parametry i pokazał pewne związki z Lossy Function Families. Nie mniej ciekawy był Alwen opowiadający o Learning with Rounding. Świetne tempo i balans między jasnością opisu a jego głębokością. Kluczowa definicja jest następująca:

$x\in Z_q, \lfloor x \rfloor_p := \lfloor \frac{xp}{q} \rfloor$.

Czemu to służy? Zachęcam do sięgnięcia po pełną pracę.

A dalej? A dalej spacer klifem wzdłuż brzegu oceanu. Krótki, bo zaraz kolejne wykłady.

Duże zainteresowanie wzbudził pierwszy duży wykład zaproszonego gościa - Cindy Cohn. Tematyka ocierała się o politykę, a więc o powszechne podsłuchiwane wszystkiego przez tajne służby. Dużo by pisać, na sali czuło się czasem gęstą atmosferę sprzeciwu przeciw niektórym praktykom agencji NSA. Nie będę rozwodził się na temat szczegółów technicznych. Zwrócę tylko uwagę, że to, co mnie osobiście najbardziej uderzyło to fakt, że politycy zdają się nie rozumieć, o co "w tym wszystkim chodzi". A NSA trochę działa jak państwo w państwie. Jak powiedziała prelegentka: w NSA jest dużo geeków, a po stronie polityków - mało. Jej zdaniem potrzeba jest zaangażować więcej geeków także po "jasnej stronie mocy". Sądzę, że wielu słuchaczy CRYPTO z tym się zgodziło.

Rocznica przekazania przez Polaków materiałów dotyczących dekryptażu Enigmy zachodnim aliantom

Dziś przypada rocznica przekazania przez polskie Biuro Szyfrów materiałów dotyczących dekryptażu niemieckiej maszyny szyfrującej Enigma zachodnim aliantom. W obliczu nieuchronnego wybuchu wojny Polacy zdecydowali podzielić się jednym z najcenniejszych sekretów wywiadu jakim była metoda łamania Enigmy. Do spotkania z przedstawicielami francuskich i brytyjskich służb kryptologicznych doszło 25 lipca 1939 roku w siedzibie Biura Szyfrów zlokalizowanej w ośrodku w Lasach Kabackich pod Warszawą. Polacy przekazali zrekonstruowane przez siebie repliki Enigmy wraz z pełną dokumentacją metod jej łamania, w tym opis tzw. płacht Zygalskiego i bomby kryptologicznej. 

Marian Rejewski, Jerzy Różycki i Henryk Zygalski

Te informacje umożliwiły aliantom regularne odczytywanie niemieckich depesz w ramach operacji o kryptonimie Ultra, która, w opinii Winstona Churchilla, walnie przyczyniła się do zwycięstwa w wojnie. Brytyjski kryptolog Gordon Welchman pisał: "Ultra nie mogłaby się w ogóle rozpocząć gdybyśmy w dosłownie ostatniej chwili nie poznali dzięki Polakom szczegółów działania wojskowej Enigmy (...)".

Autor: Konrad Durnoga

Referat "Deszyfraż w Polsce Ludowej: komórki deszyfrażu Służby Bezpieczeństwa MSW PRL oraz Sztabu Generalnego LWP"

Serdecznie zapraszamy na referat dr Jana Burego z Instytutu Prawa Międzynarodowego, Unii Europejskiej i Stosunków Międzynarodowych UKSW.

Tytuł: Deszyfraż w Polsce Ludowej: komórki deszyfrażu Służby Bezpieczeństwa MSW PRL oraz Sztabu Generalnego LWP

Streszczenie: W referacie przedstawiona zostanie historia komórek deszyfrażu należących do Biura "A" Ministerstwa Spraw Wewnętrznych PRL oraz Zarządu II Sztabu Generalnego Ludowego Wojska Polskiego w świetle odtajnionych dokumentów źródłowych. Przeanalizowane zostaną najistotniejsze typy operacji, w które zaangażowane były wspomniane instytucje oraz osiągnięte przez nie rezultaty w kryptoanalizie obcych kodów i szyfrów. W referacie uwzględnione zostaną także najbardziej powszechne metody deszyfrażu i dekryptażu stosowane przez służby specjalne Polski Ludowej.

Slajdy będą w języku polskim, natomiast jeśli na sali będą osoby które nie znają polskiego to sama prezentacja odbędzie się w języku angielskim.

Miejsce: Wydział MIM UW, sala 5070

Termin: wtorek, 9 lipca 2013, godz 16:00

Od paraboli do podziału sekretu

Niniejszy artykuł został opublikowany w miesięczniku Delta z lutego 2011.

Zaczniemy od przypomnienia kilku podstawowych własności wielomianów nad liczbami rzeczywistymi. Skupmy się najpierw na funkcji kwadratowej $f(x) = a x^2 + b x + c$. To, co będzie nas interesowało, to ile informacji potrzebujemy, żeby ustalić parametry $a$, $b$ i $c$. Na przykład jeśli znamy dwa punkty $P = (x_1, y_1), Q = (x_2, y_2)$, przez które przechodzi szukana parabola, to wiemy jeszcze za mało. Co to znaczy? Weźmy dla przykłady $P = (0,1)$ oraz $Q = (2,0)$. Łatwo sprawdzić, że zarówno funkcja $f_1(x) = -\frac{1}{4}x^2+ 1$ jak i $f_2(x) = x^2 - \frac{5}{2} x + 1$ spełnia nasze oczekiwania, tzn. w wykresiu obu funkcji leżą oba punkty. Okazuje się, że zawężenie kryteriów do trzech punktów, sprawia, że znajdziemy co najwyżej jedno rozwiązanie. Faktu tego nie będziemy ściśle dowodzić, intuicja powinna jednak podpowiadać, że właśnie trzy punkty są konieczne i wystarczające. Dlaczego? Jeden punkt przekłada się na jedno równanie liniowe z trzema niewiadomymi $a,b,c$. Trzy takie punkty, dają trzy równania.
Prezentowana wyżej własność funkcji kwadratowej uogólnia się dla wielomianów wyższych stopni. Sformułujemy ściśle odpowiednie twierdzenie.

Twierdzenie 1
Jeśli liczby rzeczywiste $x_1, x_2,\ldots,x_{n+1}$ są parami różne, to przez ustalone punkty $P_1 = (x_1, y_1), P_2=(x_2, y_2),\ldots, P_{n+1} = (x_{n+1},y_{n+1})$ przechodzi dokładnie jeden wielomian nad liczbami rzeczywistymi stopnia co najwyżej $n$.

Powyższy fakt chcemy uogólnić jeszcze bardziej. Otóż twierdzenie jest wciąż prawdziwe, jeśli zmienimy zbiór, nad którym rozpatrywane są wielomiany. Przykładowo - to samo stwierdzenie w świecie liczb zespolonych również jest prawdziwe. Dla osób zaznajomionych z podstawami algebry będzie jasne, jeśli powiemy, że jest ono prawdziwe nad każdym ciałem. Dla naszych rozważań nie będzie potrzeba dokładna definicja tej struktury. Zajmiemy się jednym konkretnym przykładem. Otóż niech $p$ będzie liczbą pierwszą oraz $Z_p$ - zbiorem liczb od naturalnych od $0$ do $p-1$. Wraz z tym zbiorem skojarzymy działania dodawania i mnożenia. Przyjmiemy, że aby dodać dwie liczby z tego zbioru, dodajemy je w sposób tradycyjny, po czym jako wynik bierzemy resztę z dzielenia przez $p$. Dla mnożenia robimy analogicznie. Poniższy przykład ilustruje te definicje dla $p = 13$: $$ 3 + 11 = 1$$ $$ 4 \cdot 6 = 11 $$ $$ 9 \cdot 9 + 10 = 0 $$ Nad taką dziwaczną strukturą będziemy badać tradycyjne wielomiany. Ponownie przyjmijmy $p=13$ oraz $w_1(x)=x^3 + 2 x^2 + 6$, $w_2(x) = x^5 + 3$, $w_3(x) = x + 4$. Mamy wówczas przykładowo: $$ w_1(4) = 11$$ $$ w_2(4) = 0$$ $$ w_3(10) = 1$$ Jak uprzedziliśmy w tym świecie również zachodzi twierdzenie o wielomianach:

Twierdzenie 2
Jeśli elementy ciała $x_1, x_2,\ldots,x_{n+1} \in Z_p$ są parami różne, to przez ustalone punkty $P_1 = (x_1, y_1), P_2=(x_2, y_2),\ldots, P_{n+1} = (x_{n+1},y_{n+1})$ przechodzi dokładnie jeden wielomian nad $Z_p$ stopnia co najwyżej $n$, o ile $n<p$.

A gdzie w tym wszystkim podział sekretu? Jeszcze chwila cierpliwości i wszystko się wyjaśni. Mamy już potrzebny aparat matematyczny, czas więc na ogólne wprowadzenie w problematykę sekretów, spisków i wzajemnej nieufności. ("Kontrola jest najwyższą formą zaufania", Włodzimierz Iljicz Lenin, filozof)

Rozważmy uproszczoną sytuację, gdzie pewna grupa $k$ osób ma jakiś wspólny sekret $M$, który interpretujemy jako jedną liczbę z przedziału $0,\ldots,p-1$, czy raczej - mówiąc językiem algebry - jako element ciała $Z_p$. Chcemy jakoś rozdzielić informację o $M$ wśród grupy, aby uzyskać taki oto poziom bezpieczeństwa sekretu $M$:

Poziom bezpieczeństwa 1
(Opisany tutaj poziom bezpieczeństwa da się uzyskać znacznie prościej niż opisano to niżej. Wystarczy pierwszym $k-1$ osobom dać losowe liczby $\ell_i$, a ostatniej: $M - \sum_{i=1}^{k-1} \ell_i$. Przedstawione rozumowanie jest podane, ponieważ poźniej następują jego uogólnienia, których nie da już tak łatwo uzyskać.)
Dowolna podgrupa $k-1$ nic nie wie o $M$. Pełna grupa $k$ osób jest w stanie odtworzyć $M$.

Na chwilę wróćmy do świata wielomianów. Niech $W$ będzie losowym wielomianem nad $Z_p$ stopnia $k-1$, takim że $W(0) = M$. Tylko ten wielomian będzie nam potrzebny, aby rozdzielić sekret. Pierwszej osobie zdradzimy wartość $W(1)$, drugiej -- $W(2)$, $\ldots$ itd. Ostatnia k-ta osoba pozna $W(k)$. Teraz z Twierdzenia 2 dostajemy, że informacje posiadane przez te osoby pozwalają odtworzyć wielomian, a więc i obliczyć $W(0)$, to znaczy poznać sekret $M$. Gdy zabraknie choć jednej osoby, to wielomian nie jest wyznaczony jednoznacznie i wiadomość pozostaje tajna.

Co tu jest jeszcze do dowiedzenia?

Powyższe rozumowanie jest poprawne, zawiera jednak oczywiście pewne uproszczenia i luki w dowodzie. Nie będziemy wszystkiego uzupełniać. Chcemy jednak dokładnie określić, co należałoby ściśle dowieść, aby móc stwierdzić, że opisany schemat jest bezpieczny.

Przede wszystkim nie zdefiniowaliśmy precyzyjnie, co rozumiemy przez sformułowanie, że wiadomość jest tajna. Nie wystarczy powiedzieć, że posiadana wiedza nie wystarcza do jednoznacznego odtworzenia sekretu $M$. Mogłoby się przecież tak zdarzyć, że - w skrajnym przypadku - zostaną tylko dwie możliwości. Pierwsze przybliżenie definicji mogłoby więc iść w tę właśnie stronę. Tzn chcielibyśmy, aby posiadana wiedza nie mogła wykluczyć żadnego kandydata na $M$. Jednak również i taka definicja jest za słaba. Nie wyklucza bowiem przypadku, gdy posiadana wiedza pozwala stwierdzić, że na przykład $M$ wynosi $23821$ z prawdopodobieństwem $0.9$. (a nie $\frac{1}{p}$ jak pewnie byśmy oczekiwali). Najsilniejsza definicja jest właśnie tak sformułowana, tzn w języku probabilistyki: Dana wiadomość jest tajna, jeśli posiadana wiedza nie pozwala na ustalenie innego rozkładu prawdopodobieństw tajnego sekretu niż rozkład jednostajny.

Okazuje się, że dzielenie sekretu za pomocą wielomianu spełnia tę najsilniejszą definicją. Zachęcamy do udowodnienia tego faktu, a przynajmniej dokładnego sformułowania, co tak naprawdę trzeba udowodnić.

Dalsze zastosowania

Wielomiany dają nam jeszcze inne ciekawe możliwości (ponownie $k$ oznacza liczbę osób):

Poziom bezpieczeństwa 2
Dowolna podgrupa $k-4$ nic nie wie o $M$. Każda podgrupa $k-3$ osób jest w stanie odtworzyć $M$.

Powyższe bezpieczeństwo uzysujemy następująco: losujemy wielomian stopnia $k-4$ o wartości $M$ w zerze. Osobom dajemy kolejne wartości $W(1), W(2), \ldots$. Ponownie Twierdzenie 2 dowodzi tezy. Lczba $4$ została tu wybrana przykładowo, można wybrać dowolną inną. Oczywiście, żeby zachować pełną ścisłość należy udowodnić trudniejszy fakt dotyczący prawdopodobieństw rozkładu.
To jednak nie koniec. Jako ostatnią rzecz, proponujemy ćwiczenie. Prosimy czytelnika o pokazanie jak użyć techniki wielomianów do takiego poziomu bezpieczeństwa:

Poziom bezpieczeństwa 3
Nie k oznacza liczbę pięcioosobowych rozłącznych grup osób. Chcemy, aby do poznania sekretu konieczne była większość (a więc co najmniej trzy osoby) z co najmniej $\frac{k}{2}$ grup.

Wskazówka: Początkowo rozwiązujemy problem w starym modelu dla $k$ osób wszystkich i $\frac{k}{2}$ potrzebnych do odzyskania sekretu. Następnie uzyskane punkty traktujemy jako kelejne sekrety, które w obrębie grupy ponownie szyfrujemy za pomocą tej samej techniki, ale - tym razem - dla pięciu osób łącznie i trzech potrzebnych do odszyfrowania.