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.

RC4 wyłączony w Windows 8.1

Firma Microsoft ogłosiła wyłączenie szyfru RC4 w protokole TLS w systemie Windows 8.1.  Jest to najprawdopodobniej reakcja na niedawny atak na RC4 dokonany przez Nadhema AlFardana, Dana Bernsteina, Kenny'ego Patersona, Bertrama Poetteringa and Jacoba Schuldta.

Atak ten działa przy dość optymistycznych założeniach odnośnie mocy przeciwnika.  Konkretnie, wymaga on użycia tego samego tekstu jawnego w $2^{30}$ sesjach TLS.  Atak pozwala na odtworzenie 220 bajtów tekstu jawnego.

Choć w praktyce może być trudno "namówić" serwer na takie $2^{30}$ sesji, to rozsądnym zachowaniem jest dmuchanie na zimne, zwłaszcza, że nie wiemy do jakiego stopnia ten atak może być ulepszany.  Stąd decyzja firmy Microsoft.

Coraz częściej słyszy się opinie, że TLS powinien zostać zastąpiony innym protokołem, zaprojektowanym od początku przez kryptologów i ekspertów od bezpieczeństwa.

Kto wymyślił transfer utajniony?

Wczorajszy wpis dotyczył uczuć i emocji (w końcu to blog). Jednak uważny czytelnik dostrzegł, że kluczowym składnikiem opisanej konstrukcji był obiekt bardzo matematyczny - chodzi o transfer utajniony (oblivious transfer). Pryncypał grupy CryptoUW zwrócił mi uwagę, że bardzo ciekawa jest osoba, która ten obiekt wymyśliła. Chodzi o Michaela Rabina urodzonego we Wrocławiu (wówczas Breslau). Zachęcam do zapoznania się z historią tej postaci:

Kocha, lubi, szyfruje...

Niniejszy artykuł został opublikowany w miesięczniku Delta z maja 2012.

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są postaci Alicji i Boba, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.

Tym razem jednak zadanie stojące przed Alicją i Bobem jest wyjątkowo trudne. Chcą sprawdzić, czy się nawzajem kochają, jednak bez ujawniania swoich uczuć. Co przez to rozumiemy? Otóż chcemy opracować następujący protokół komunikacyjny.

Alicja posiada bit $a$, który oznacza, czy kocha Boba, czy nie (to oznacza, że $a=1$ jeśli Alicja jest zakochana w Bobie, jeśli zaś nie jest, to $a=0$). Analogicznie, Bob posiada bit $b$ opisujący jego uczucia względem Alicji. Oczywiście teraz ich wzajemna miłość może być opisana w tej notacji przez wyrażenie $m := a \wedge b$, które jest równe $1$ tylko wtedy, gdy $a=b=1$. Naszym celem jest opracowanie takiego protokołu, w wyniku którego Alicja na końcu będzie znała $a$ oraz $m$ (i nic więcej!), natomiast Bob $b$ oraz $m$. Intuicja stojąca za takimi założeniami jest następująca: chcemy uniknąć krępującej sytuacji, gdy na przykład Alicja kocha Boba, ale Bob nie odwzajemnia tych uczuć, a dowiaduje się o uczuciu Alicji. Innymi słowy: jeśli Bob wie, że $b = 0$ oraz $m = 0$, to nie powinien umieć wyznaczyć $a$.

Powyższe założenia łatwo uzyskać, gdy dopuścimy trzecią zaufaną stronę, która, gdy pozna $a$ i $b$, obliczy $m$ oraz przekaże tę informację obu zainteresowanym osobom. Nasze zadanie jest jednak bardziej ambitne, ponieważ pożądany efekt chcemy uzyskać za pomocą protokołu, w którym jedynymi stronami są Alicja i Bob. Zadanie samo w sobie wydaje się trudne, a wręcz można by przypuszczać, że tak określony protokół nie jest możliwy do zrealizowania. Pokażemy jednak, że jest to możliwe, ale przy pewnych założeniach obliczeniowych. Mamy tu na myśli klasyczne założenia dotyczące szyfrowania algorytmem RSA: a więc, że strona posiadająca jakąś wiadomość zaszyfrowaną oraz klucz publiczny, bez znajomości klucza prywatnego nie jest w stanie odtworzyć wiadomości jawnej. Należy tu poczynić uwagę, że bez założeń tego typu (tj. bez ograniczeń obliczeniowych, inaczej mówiąc: bezpiecznie teorio-informacyjnie) żądanego protokołu nie da się skonstruować.

Wróćmy teraz do naszej Alicji i naszego Boba, którzy już za chwilę zaczną ze sobą rozmawiać.

Szukany protokół opiera się na idei tak zwanego transferu utajnionego (ang. oblivious transfer). Jest to bardzo ciekawy i użyteczny protokół, niejednokrotnie wykorzystywany jako cegiełka do budowy innych protokołów. Założenia są następujące: Alicja posiada parę liczb $(x_0, x_1)$, a Bob bit $s$. Po zakończeniu protokołu Alicja nie dowie się nic nowego, natomiast Bob pozna liczbę $x_s$. Taki protokół istnieje, pokażemy go później. Natomiast korzystając z transferu utajnionego, możemy już łatwo wykonać nasz docelowy protokół.

Niech mianowicie Alicja przyjmie: $$ x_0 = 0,\quad x_1 = a,$$ a Bob: $$s = b.$$ W pierwszej fazie testu na miłość wykonujemy klasyczny transfer utajniony dla podanych parametrów. W jego wyniku Bob otrzymuje wartość $y = x_s$. Wówczas wysyła ją Alicji i jest to wynik naszego protokołu.

Łatwo sprawdzamy poprawność: jeśli $b=0$, to wynikiem protokołu jest $x_0=0$, co jest zgodne z oczekiwaniami, gdyż $$m = b \wedge a = 0 \wedge a = 0,$$ niezależnie od wartości $a$. W drugim przypadku ($b=1$) wynikiem jest $x_1 = a$, co również jest poprawną odpowiedzią, gdyż: $$ m = (b\wedge a) = (1 \wedge a) = a .$$

Transfer utajniony

W tej części pokażemy, jak zrealizować transfer utajniony. Jako narzędzia potrzebujemy szyfrowania z kluczem publicznym i prywatnym -- dobrym przykładem jest tu wspomniany już algorytm RSA.
(Przypomnijmy tutaj potrzebne założenia na temat algorytmu RSA. Alicja wybiera dwie duże liczby pierwsze $p, q$ i oblicza $n=pq$. Następnie wyznacza liczbę $e$ względnie pierwszą z $\phi(n)$ oraz jej odwrotność $d$ modulo $\phi(n)$. Jej kluczem publicznym jest para $(n,e)$, zaś kluczem publicznym para $(n,d)$. Szyfrowanie wiadomości $m$ odbywa się według wzoru $c = m^e \bmod n$, zaś odszyfrowywanie według wzoru $m = c^d \bmod n$.)
Przypomnijmy założenia: Alicja posiada parę liczb $x_0$ oraz $x_1$, natomiast Bob ustala bit $s$. Teraz:

• Alicja inicjalizuje algorytm RSA, tzn. wybiera liczbę $n$ oraz klucze $d$ i $e$. Zakładamy, że $0 \leq x_0, x_1 < n$. Swój klucz publiczny, czyli parę $(n,e)$, wysyła do Boba.
• Alicja losuje niezależnie dwie różne liczby $0 \leq y_0, y_1 < n$ oraz wysyła je Bobowi.
• Bob losuje liczbę $0 \leq k < n$ i oblicza $v = (y_s + k^e) \bmod n$. Bob wysyła wartość $v$ do Alicji.
• Alicja oblicza kolejno: $k_0 = (v-y_0)^d \bmod n$ oraz $k_1 = (v-y_1)^d \bmod n$, $x_0' = (x_0 + k_0) \bmod n$, $x_1' = (x_1 + k_1) \bmod n$ oraz wysyła Bobowi $x_0'$ i $x_1'$.
• Bob potrafi obliczyć $(x_s' - k) \bmod n$

Sprawdźmy, że obliczona przez Boba wartość to rzeczywiście $x_s$: \begin{equation*} \begin{split} x_s' - k &\equiv x_s + k_s - k \equiv x_s + (v-y_s)^d - k \equiv x_s + (y_s + k^e - y_s)^d - k \equiv{}\\ &{}\equiv x_s + k^{ed} - k \equiv x_s \pmod n. \end{split} \end{equation*}

Aby opisany protokół był użyteczny potrzebujemy dwóch własności:

(*) Alicja nie poznaje bitu $s$. Ten fakt jest prosty - wynika z symetrii. To znaczy: z punktu widzenia Alicji nie ma w protokole żadnego rozróżnienia pomiędzy $s=0$ a $s=1$, gdyż jedyny komunikat otrzymany od Boba (wartość $v$) jest - z punktu widzenia Alicji -- losowy i niezależny od wartości $s$.

(**) Bob nie poznaje liczby $x_{1-s}$.

Pełny dowód (**) pominiemy i pozostawimy Czytelnikowi: wskazówka jest taka, że należy pokazać (metodą nie wprost), że gdyby można było złamać nasz protokół (a więc Bob dowiedziałby się czegoś na temat $x_{1-s}$), to złamać potrafilibyśmy również RSA. Rozumowania tego typu są bardzo częste w dowodach w kryptografii, czasem nazywamy je symulacją jednego protokołu przez drugi.

Na sam koniec warto dodać, że opisany tutaj problem jest tylko drobnym przykładem na to, co potrafimy robić. Otóż okazuje się, że funkcja $a\wedge b$ została wybrana zupełnie arbitralnie: tak naprawdę można podać protokół obliczający wartość dowolnej funkcji opisanej za pomocą obwodu logicznego. Wówczas ilość potrzebnej informacji, którą wymienią między sobą Alicja i Bob, jest proporcjonalna do liczby węzłów wspomnianego obwodu. Zainteresowanego Czytelnika zachęcamy do dalszych poszukiwań.