Seminaria Sekcji Kryptologii i Ochrony Informacji

Uprzejmie informujemy, ze seminarium kryptologiczne w IMPAN 
odbywa sie w piatki, o godzinie 16 (z kwadransem) 
w sali 106 na I pietrze Instytutu Matematycznego PAN
przy ul Sniadeckich 8.  Program seminarium obejmie m. innymi:
zagadnienia zwiazane z kryptoanaliza funkcji skrotu, algebraicznymi metodami 
kryptoanalizy, zastosowaniem funkcji eliptycznych w kryptografii oraz 
konstrukcja szyfrow asymetrycznych.

Zbigniew Jelonek
Janusz Szmidt
Aleksander Wittlin

W referacie przedstawiona zostanie historia oraz działania komórki deszyfrażu należącej do Biura "A" MSW PRL. Przeanalizowane zostaną najważniejsze typy operacji, w których była wykorzystywana, oraz osiągnięte rezultaty w kryptoanalizie obcych kodów i szyfrów.

Przedstawię prostą charakteryzację skończonych algebr lokalnych nad ciałami (skończonymi) z zastosowaniem do sprawdzania lokalności pierścieni skończonych. Przedyskutuję wielomianowy, deterministyczny algorytm sprawdzania czy algebra, dana za pomocą tzw. reprezentacji bazowej, jest lokalna. Stosując znany algorytm deterministyczny dla testowania pierwszości, przedstawię również deterministyczny algorytm sprawdzający lokalność dowolnych pierścieni skończonych i przedyskutuję warianty randomizowane obu algorytmów.

GOST 28147-89 is is a well-known 256-bit block cipher which is a plausible alternative for AES-256 and triple DES, which however has a much lower implementation cost. GOST is implemented in standard crypto libraries such as OpenSSL and Crypto++ and is increasingly popular and used also outside its country of origin and on the Internet. In 2010 GOST was submitted to ISO, to become a worldwide industrial encryption standard. Until 2011 researchers unanimously agreed that GOST could or should be very secure, which was summarized in 2010 in these words: despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken". As of today ISO is still in the process of standardising GOST. and it seems that never in history of industrial standardisation ISO had such a strong submission in terms of implementation cost vs. the the very high security level claimed for GOST. Unhappily however it was recently discovered that GOST can be broken. One simple attack was already presented in February at FSE 2011. In this talk we are going to present another attack which requires much less memory, and doesn't even require the reflection property to hold, without which the recent attack from FSE 2011 wouldn't work. We will also make a few remarks about much better yet unpublished attacks on GOST.

Krzywe eliptyczne i jakobiany krzywych hipereliptycznych z małymi stopniami zanurzeniowymi stosujemy do implementacji protokołów opartych na iloczynach dwuliniowych. Podstawowym problemem jest skonstruowanie odpowiednich krzywych. Podczas referatu omówię uogólnienia metod konstruowania krzywych eliptycznych na krzywe hipereliptyczne genusu 2.

Wiadomo, że ogólne metody obliczania rzędu krzywych hipereliptycznych są zbyt wolne w praktyce. Efektywniejsze metody istnieją dla krzywych o rozkładalnych jakobianach. Na przykład, Satoh podał metodę obliczania rzędu krzywych y²=x⁵+ax³+bx. W kryptografii możemy stosować krzywe hipereliptyczne C/F_q takie, że Jac(C) jest prosty nad F_q, ale jest izogeniczny z produktem krzywych eliptycznych nad pewnym rozszerzeniem F_q. Podczas referatu omówię metodę obliczania rzędu jakobianu takich krzywych.

NFSR (Nonlinear Feedback Shift Registers) mają podstawowe zastosowania w konstrukcji szyfrów strumieniowych. Podstawowymi problemami w teorii NFSR jest określenie okresowości i złożoności liniowej NFSR. Zagadnienie oszacowania z dołu złożoności liniowej NFSR związane jest z istnieniem rozwiązań układów równań diofantycznych w ciałach skończonych.

Omówię następujące zagadnienia:

• Algorytm Euklidesa
• Algorytm Gaussa o redukcji bazy krat w R²
• Algorytm Lenstra-Lenstra-Lovasz o redukcji bazy krat w Rⁿ
• Kryptosystem wykorzystujący problem najbliższego wektora do kraty
• Szyfrowanie homomorficzne

Fizyczne implementacje systemów kryptograficznych podatne są na ataki typu side-channel. W ostatnich latach pojawiły się liczne teoretyczne metody zapobiegania takim atakom. W referacie dokonamy przeglądu tych metod.

GOST 28147-89 is is a well-known 256-bit block cipher which is a plausible alternative for AES-256 and triple DES, which however has a much lower implementation cost. GOST is implemented in standard crypto libraries such as OpenSSL and Crypto++ and is increasingly popular and used also outside its country of origin and on the Internet. In 2010 GOST was submitted to ISO, to become a worldwide industrial encryption standard. Until 2011 researchers unanimously agreed that GOST could or should be very secure, which was summarized in 2010 in these words: "despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken".
As of today ISO is still in the process of standardising GOST. and it seems that never in history of industrial standardisation ISO had such a strong submission in terms of implementation cost vs. the the very high security level claimed for GOST. Unhappily however it was recently discovered that GOST can be broken. One simple attack was already presented in February at FSE 2011. In this talk we are going to present another attack which requires much less memory, and doesn't even require the reflection property to hold, without which the recent attack from FSE 2011 wouldn't work. We will also make a few remarks about much better yet unpublished attacks on GOST.

Referowana będzie praca A. Biryukov, A. Shamir, Structural cryptanalysis of SASAS (Journal of Cryptology 23 (2010), 505–518). Jest to atak, którego celem jest odzyskanie nieznanej struktury szyfru blokowego typu sieć podstawieniowo-przestawieniowa, np. dla zredukowanej wersji algorytmu AES.

Metoda mnożeń zespolonych jest stosowana do konstruowania krzywych eliptycznych nad ciałami skończonymi. Omówię matematyczne podstawy tej metody oraz zastosowania do rozwiązania następujacych dwóch problemów:

1. Konstruowania krzywych eliptycznych rzędu prawie pierwszego nad danym ciałem skończonym.
2. Konstruowania krzywych eliptycznych o danym rzędzie nad pewnym ciałem skończonym.

We will use the interpretation of Incidence geometries to create fast algorithms to measure the distance between vertices of distance regular graphs of Lie type and related to them Hemmeter and Ustimenko graphs, double Grassman graphs. Distance regular graphs of Coxeter and Lie type are important examples of graphs for which there is the algorithms to measure the distance between vertices which is much faster than the speed of well known Dijkstra method. We will also use the flag systems of Lie geometries for the generation of polynomial public keys protected by the complexity of group theoretical discrete logarithm problems as well as incidence graph based key-exchange protocols.

Będziemy zajmować się konstruowaniem krzywych, których jakobian zawiera podgrupę dużego rzędu pierwszego z małym stopniem zanurzeniowym. Takie jakobiany są wykorzystywane do implementacji protokołów opartych na iloczynach Weila lub Tate. Losowy wybór krzywej o takich własnościach jest bardzo mało prawdopodobny. Podczas referatu podam nową metodę generowania takich krzywych o genusie 2, która jest oparta na twierdzeniu Hondy-Tate o reprezentacji klas isogenii rozmaitości abelowych przez liczby q-Weila.

Krzywe eliptyczne z małym stopniem zanurzeniowym stosuje się do implementacji pewnych protokołów (np. krótkich podpisów cyfrowych). Takie krzywe muszą być specjalnie konstruowane, ponieważ występują bardzo rzadko. Szczególną uwagę zwraca się na to, aby rząd podgrupy używanej do kodowania był jak najbliższy rzędowi krzywej, co poprawia efektywność. Krzywe o takich własnościach na ogół łatwiej otrzymywać przy pomocy tzw. rodzin (tzn. wielomianów, których wartości przypuszczalnie na nieskończenie wielu liczbach całkowitych dają parametry krzywych, które następnie można efektywnie skonstruować). Ogólne metody konstruowania zostały rozwinięte tylko dla tzw. rodzin zupełnych. Nie zostały również podane ogólne metody konstruowania rodzin krzywych, których rząd jest prawie pierwszy.

Podczas referatu skupię się na problemach konstruowania:
(i) rodzin dowolnego typu,
(ii) rodzin krzywych, których rząd jest prawie pierwszy.

Przedstawię dwie metody konstruowania rodzin (i). Ponadto podam opis rodzin (ii) pozwalający otrzymać układy równań, których rozwiązania wymierne wyznaczają takie rodziny.

1. Omówienie rozwiązań zadań domowych sformułowanych na seminarium w dniu 22 stycznia.
2. Referat na temat analogii między grupami punktów wymiernych na krzywych eliptycznych nad ciałami skończonymi a grupami krytycznymi grafów kołowych.

G. Musiker z powodzeniem zbudował pewne grafy, które dają takie same grupy, jak grupy punktów wymiernych na krzywych eliptycznych określonych nad ciałami skończonymi, lecz nie odwoływał się do tych krzywych. Zamierzam omówić kilka spraw poruszanych w tych pracach.

Nawiązując do ostatniego referatu Prof. Jelonka zastosujemy podobne metody do liczb całkowitych zamiast do wielomianów nad ciałem skończonym. Badamy rozkładalność liczby n postepując analogicznie:

Wybieramy dowolnie liczbę a względnie pierwszą z n. Jeżeli a^n-1 nie przystaje do 1 modulo n, to liczba n jest złożona na mocy małego twierdzenia Fermata.

Niech więc a^n-1 daje resztę 1 modulo n. Podnosimy a do potęgi (n-1)/2 modulo n. Jeżeli otrzymamy 1 lub -1, to wybieramy inną liczbę a. Jeżeli otrzymamy liczbę b różną od 1 i -1, to obliczamy NWD(n,b-1) oraz NWD(n,b+1). Jedna z tych liczb jest właściwym dzielnikiem liczby n.

Omówię różne modyfikacje tego algorytmu. Szczegóły można znaleźć w  mojej pracy w Mathematics of Computation 73 (2004), 1031-1037, errata ibid. 74 (2005), p. 1573.

Krzywe eliptyczne odpowiednie dla zastosowań w "Pairing-based cryptography" są bardzo rzadkie, dlatego poszukuje się metod konstruowania ich. Takie metody dają albo pojedyncze krzywe, albo rodziny krzywych. Na ogół w drugim przypadku można otrzymać krzywe o lepszych własnościach.

Omówię podstawowe własności krzywych, które są istotne dla "Pairing-based cryptography", oraz metody konstruowania rodzin takich krzywych.

Referat będzie dotyczył pracy Dinura i Shamira Cube attacks on tweakable black box polynomials. W szczególności przedstawiony będzie atak na szyfr strumieniowy Trivium.

Omówię protokoły implementowane na takich krzywych, np. uzgadniania klucza publicznego między trzema osobami w jednej rundzie, podpisu cyfrowego czy idee realizacji systemu, w którym autentyczność klucza sprawdza się przy pomocy tożsamości jego właściciela. Przedstawię również metody konstruowania takich krzywych, które są ważne choćby z takiego powodu, że losowo wybrana krzywa nie nadaje się do tego typu zastosowań.

Przedstawię prezentację Ronalda Rivesta z ostatniego Crypto na temat nowej funkcji skrótu MD6. Ponieważ był to wykład zaproszony (tzw. Invited Talk), dlatego nie ma go w materiałach z konferencji, co trochę utrudnia jego całkowite zrozumienie. Seminarium poprowadzę jedynie na podstawie slajdów Rivesta i tego, co usłyszałem na wykładzie na Crypto, wobec czego może to nie być do końca zrozumiałe (szczególnie, że sam nie wszystko z tych slajdów zrozumiałem).

Niech E będzie krzywą eliptyczną określoną nad ciałem skończonym F i niech m będzie rzędem grupy E(F) punktów na tej krzywej o współrzędnych w F. Z punktu widzenia kryptografii byłoby dobrze, gdyby ta grupa była cykliczna, jednak grupa abelowa rzędu m może cykliczna nie być.

Jak wiadomo, przy dowolnej izogenii E→E' rząd grupy się nie zmienia, a struktura grupy może ulec zmianie. Szukamy więc takiej izogenii, aby grupa E'(F) była cykliczna.

Zamierzam mówić dokładniej na ten temat. Dla poglądowego przedstawienia tych spraw wygodnie jest narysować odpowiedni wulkan, czego niestety w tym streszczeniu zrobić nie mogę.

Referat będzie poświęcony nowemu podejściu do zagadnień obliczalności na liczbach rzeczywistych. Wprowadzona zostanie nowa klasy rzeczywistych funkcji rekurencyjnych określona za pomocą definicji indukcyjnej wykorzystującej przejście graniczne oraz rekursję różniczkową. Podane zostaną dodatkowe warunki nałożone na klasę zapewniające poprawność definicji i użyteczność zdefiniowanej klasy funkcji.

Na bazie powyżej wspomnianej definicji przedstawione zostaną podstawowe własności rzeczywistych funkcji rekurencyjnych. Najpierw podane zostaną przykłady oraz alternatywne metody wprowadzenia tej klasy. Następnie wskazane zostaną ograniczenia związane z rozstrzygalnością oraz związki z klasyczną teorią złożoności obliczeniowej. Ponadto zostanie krótko omówiony aspekt fizycznej realizowalności wprowadzonego modelu obliczeń.

Jako główne zagadnienie referatu zostanie wyeksponowany związek rzeczywistych funkcji rekurencyjnych z hierarchią arytmetyczną oraz problem istnienia funkcji uniwersalnej w tym modelu. Na tej podstawie zostanie udowodniony nieskończonych charakter hierarchii rzeczywistych funkcji rekurencyjnych zbudowanej ze względu na operator przejścia granicznego. Dodane zostaną także informacje o iterowalności w obrębie modelu oraz związkach z funkcjonałami rekurencyjnymi. Na koniec wskazane zostaną dalsze kierunki badań.

Algorytm autorstwa Havarda Raduma i Igora Semaeva to jedna z najnowszych metod rozwiązywania nieliniowych układów równań nad ciałami skończonymi. Rozwiązywanie takich układów to kluczowa część ataków algebraicznych. Algorytm opiera się na zaskakująco prostym pomyśle - jego podstawowym krokiem jest eliminowanie rozwiązań niemożliwych. Warunkiem jego efektywości jest rzadkość układu w sensie małej liczby zmiennych występujących w jednym równaniu. Jest to jedyny ze znanych dotychczas algorytmów, którego złożoność nie zależy od stopnia równań. W referacie omówiona zostanie podstawowa wersja algorytmu oraz kilka pomysłów na jego usprawnienie.

Pokażę ogólny algorytm rozwiązujący układ wielomianowych równań (nad dowolnym ciałem). Moja metoda jest oparta na klasycznej metodzie eliminacji i jest różna od metod opartych na bazach Groebnera.

In 2001 Courtois and Pieprzyk have conjectured that though for dense systems the problem is NP-hard, many systems of sparse multivariate quadratic equations can be solved in practice. This allows to design algebraic attacks on block ciphers. In 2006 it was discovered that not only many systems of equations can be solved by Gröbner bases, which nobody have noticed before, but also sometimes by much simpler algorithms such as ElimLin. Moreover a new very fast method was proposed by Courtois and Bard: conversion and usage of SAT solvers.The possibility of efficiently solving sparse polynomial equations opens many avenues for future research. In 2007 Courtois and Bard broke KeeLoq, a block cipher used by millions of people worldwide to unlock their car doors and alarms. This is the first time in history that a full-size industrial block cipher was broken by an algebraic attack. When looking at limitations of algebraic attacks we realize that some are very strong (we hit the wall when the number of rounds increases) and some are spectacularly naive (such as the degree in Gröbner basis computation).

Omówię pracę dyplomową T. Stegersa na temat algorytmu F5 zaproponowanego przez J. C. Faugère'a. Jest to algorytm mający usprawnić wyznaczanie bazy Groebnera ideału generowanego przez dane wielomiany. Niestety, nie zawsze działa on dobrze.

Będę zakładał znajomość algorytmu Buchbergera, którego nie omawiałem przy tablicy, lecz jest on opisany wraz z dowodem w moim tekście o bazach Groebnera.

W pierwszej części seminarium przedstawiona zostanie kryptoanaliza zaproponowanej na FSE'2006 dedykowanej funkcji skrótu FORK-256. Pokaże ona, jak wykorzystując pewną szczególną słabość pojedynczej rundy w funkcji kompresji można otrzymać interesujące charakterystyki różnicowe dla jednego kroku, a następnie rozszerzyć je do ścieżek różnicowych dla całej funkcji. Używając tej metody można znaleźć kolizje dla kompletnej funkcji kompresji ze złożonością obliczeniową 2^126.6 używając tylko małej pamięci roboczej. Zaprezentowana metoda ataku jest praktyczna i pozwala na znajdowanie blisko-kolizji o wadze poniżej 30 na pojedynczym komputerze PC. Na zakończenie omówione zostanie teoretyczna optymalizacja która pozwala na obniżenie złożoności obliczeniowej do ok. 2¹¹⁰ kosztem użycia pamięci o rozmiarze rzędu 2⁶⁷ słów. Ponadto pokazana zostanie metoda rozszerzenia ataku z funkcji kompresji na funkcję skrótu. W drugiej części seminarium przedstawione zostanie kilka uwag na temat obecnego stanu badań w dziedzinie kryptograficznych funkcji skrótu w świetle zapowiadanego konkursu NIST na nową funkcję skrótu.

Xoring the output of k permutations, k≥2, is a very simple way to construct pseudo-random functions from pseudo-random permutations. Moreover such constructions have many applications in cryptography. In this talk we will study the best known generic attacks on these constructions, and we will present the best security results obtained.

W ramach tematu postaram się omówić następujące zagadnienia:

1. Uwierzytelnianie (definicja, założenia, najpopularniejsze rozwiązania)
2. Idea i własności dowodów o wiedzy zerowej (definicja, cechy charakterystyczne, klasy problemów obliczeniowych)
3. Zastosowanie teorii grafów (definicje: graf, cykl, cykl Hamiltona, problem znajdowania cykli Hamiltona, izomorfizm grafów)
4. Algorytmy uwierzytelniające oparte o DWZ (podział, krótkie omówienie)

    Bazy Groebnera to są bazy ideałów pierścienia wielomianów wielu
zmiennych. Bazy te mają różne dobre własności, których nie mają inne
bazy. Zamierzam przedstawić nastepujace sprawy:
    1. Definicja bazy Groebnera.
    2. Algorytm dzielenia wielomianów wielu zmienych, w szczególności
       dzielenie przez bazę Groebnera.
    3. Warunek Buchbergera na to, aby baza była bazą Groebnera.
    4. Algorytm Buchbergera dla wyznaczania bazy Groebnera.
    5. Baza Groebnera zredukowana.
    6. Modyfikacje algorytmu Buchbergera.

    OMÓWIENIE KOLEJNYCH PUNKTÓW
Ad 1. Do zdefiniowania bazy Groebnera trzeba ustalić pewien dobry porządek 
w zbiorze jednomianów. Przedstawię więc takie porzadki, co pozwoli 
zdefiniować bazę Groebnera (zależną od porządku!) i udowodnić, że baza
Groebnera naprawdę jest bazą. Do tego celu będę też musiał podać 
podstawowe informacje o ideałach generowanych przez jednomiany.

Ad 2. Zwykły algorytm dzielenia wielomianu wielu zmiennych przez układ
wielomianów daje pewną resztę, ale ta reszta ma zupełnie przypadkowe 
własności. Na przykład zależy od kolejności wielomianów w tym układzie.
Natomiast dzielenie przez układ, który jest Bazą Groebnera, nie ma tych
wad, a ma szereg zalet.

Ad 3. Warunek Buchbergera pozwala rozstrzygnąć w skończonej liczbie 
kroków, czy dana baza ideału jest bazą Groebnera. Jest to bardzo pomysłowy 
warunek, który oprócz samych wielomianów z bazy wykorzystuje tzw. syzygie 
par tych wielomianów. Warunek Buchbergera mówi, że te syzygie mają dawać 
resztę 0 przy dzieleniu przez daną bazę.

Ad 4. Algorytm Buchbergera pozwala rozszerzyć dowolną bazę ideału do 
pewnej jego bazy Groebnera. Po prostu, gdy syzygia pewnej pary wielomianów 
nie daje reszty 0 przy dzieleniu przez tę bazę, to do bazy dołaczamy tę 
syzygię i tak aż do skutku.

Ad 5. Ideał ma na ogół wiele baz Groebnera, lecz jeśli nałożymy na nie 
odpowiednie warunki, to otrzymamy jednoznacznie określoną bazę Groebnera. 
Nazywa się ją bazą zredukowaną. Ta baza zredukowana jest najlepsza ze 
wszystkich.

Ad 6. Niestety algorytm Buchbergera omówiony w punkcie 4. jest zbyt 
skomplikowany algorytmicznie. Jest w nim trochę niepotrzebnych kroków.
Przedstawię kilka podstawowych modyfikacji oryginalnego algorytmu 
Buchbergera, które w wielu przypadkach mają zalety z algorytmicznego 
punktu widzenia.

    INNE INFORMACJE
    Nie zakładam u słuchaczy żadnych specjalnych wiadomości. Wystarczy 
wiedzieć, co to jest wielomian wielu zmiennych (o współczynnikach 
w jakimś ciele) i co to jest ideał pierścienia wielomianów.
    Nie podaję żadnych informacji na temat literatury przedmiotu. Jest 
bardzo dużo różnych opracowan tej tematyki i trudno wyróżnić jakiś 
podręcznik. Najlepiej szukać przez GOOGLE pod hasłem "Groebner basis"
i otrzyma się dziesiątki albo i setki pozycji.
    Postaram się mówić bez pośpiechu i zrozumiale. Tematyka wydaje się 
interesująca z matematycznego punktu widzenia i nie wymaga reklamy.

Referat będzie poświęcony zastosowaniu schematu podziału sekretu wg Shamira do tzw. cyfrowego podpisu pełnomocniczego (ang. threshold proxy signature scheme). Planuję dokładniej omówić schemat takiego podpisu, którego bezpieczeństwo opiera się na problemie logarytmu dyskretnego w grupie punktów wymiernych krzywej eliptycznej nad ciałem skończonym.

Osią wykładu będzie opracowany przez NSA, jako tajny, algorytm SKIPJACK. Na podstawie historii jego powstawania i wdrażania omówiony zostanie problem tzw. "kryptografii kontrolowanej". Następnie przedstawiona będzie jego specyfikacja. Na zakończenie po krótkim wprowadzeniu w zagadnienia kryptoanalizy różnicowej pokazane zostaną ataki na SKIPJACKA wykorzystujące różniczki niemożliwe, a w szczególności atak na 25-rundowy wariant.

Zostanie przedstawiona krótka analiza złożoności obliczeniowej działań na grupie punktów krzywej eliptycznej. Szczególna uwaga poświęcona będzie efektywnym metodom obliczania wielokrotności punktu. Omówione zostanie również wykorzystanie działania połowienia punktu, jako jednego ze sposobów na przyspieszenie obliczeń.

HAVAL jest kryptograficzną funkcją skrótu, której struktura jest podobna do innych powszechnie używanych funkcji, takich jak MD5 oraz SHA-1. Specyfikacja algorytmu HAVAL zawiera parametr bezpieczeństwa, liczbę rund, która może być wybrana między 3, 4 i 5. W świetle ostatnich doniesień o złamaniu SHA-1 i MD5 temat kryptoanalizy funkcji skrótu stał się bardzo popularny. Przedstawię praktyczny atak znajdowania kolizji dla 3-rundowej wersji funkcji skrótu HAVAL, który wykorzystuje podobne techniki jak ataki na inne funkcje z rodziny MD4.

We will look again at the method of Maurer/Wolf for showing equivalence between the DLP and DHP. We will concentrate on the case where the DHP is defined over an elliptic curve and show that a relatively tight security reduction can be found in all cases.

Protokół Prywatnego Pozyskiwania Danych (ang.: Private Information Retrieval, PIR) jest wykonywany przez dwóch uczestników: klienta i bazę danych. Protokół ten pozwala klientowi uzyskać dostęp do bazy w taki sposób, by baza nie uzyskała żadnej informacji na temat zapytania zadanego przez klienta. Protokoły takie istnieją, o ile spełnione są założenia o trudności pewnych problemów obliczeniowych. Teoria wiecznego bezpieczeństwa (ang.: everlasting security) zajmuje się konstrukcją protokołów kryptograficznych, które są bezpieczne ,,na zawsze'' (np. szyfrowanie RSA z kluczem o długości 2048 prawdopodobnie nie spełnia tego warunku, gdyż prędzej czy później powstaną metody jego złamania).

Tematem referatu będzie wprowadzenie do obydwu zagadnień oraz pokazanie niespodziewanego związku między teorią PIR a teorią wiecznego bezpieczeństwa.

Referat jest oparty na pracy:
Stefan Dziembowski i Ueli Maurer On Generating the Initial Key in the Bounded-Storage Model, EUROCRYPT'04

In this talk we present a very practical ciphertext-only cryptanalysis of GSM encrypted communication, and various active attacks on the GSM protocols. These attacks can even break into GSM networks that use ``unbreakable'' ciphers. We describe a ciphertext-only attack on A5/2 that requires a few dozen milliseconds of encrypted off-the-air cellular conversation and finds the correct key in less than a second on a personal computer. We then extend this attack to a (more complex) ciphertext-only attack on A5/1. We describe new attacks on the protocols of networks that use A5/1, A5/3, or even GPRS. These attacks are based on security flaws of the GSM protocols, and work whenever the mobile phone supports A5/2. We emphasize that these attacks are on the protocols, and are thus applicable whenever the cellular phone supports a weak cipher, for instance they are also applicable using the cryptanalysis of A5/1. Unlike previous attacks on GSM that require unrealistic information, like long known plaintext periods, our attacks are very practical and do not require any knowledge of the content of the conversation. These attacks allow attackers to tap conversations and decrypt them either in real-time, or at any later time. We also show active attacks, such as call hijacking, altering of data messages and call theft.

In this talk we present new techniques for finding collisions of variants of SHA-0 and SHA-1. These techniques allow to find collisions of (the full 80 rounds of) SHA-0 with a 2^56 complexity, and to find near-collisions of the full compression function of SHA-0 on a home PC. The strength of SHA-0 is shown not to be montoneous with the number of rounds. We use the very surprising fact that the messages have many neutral bits, some of which do not affect the differences for about 15-20 rounds. A method to use near-collisions as a tool in order to find collisions, which is especially useful in cases where the original technique cannot find collisions (such as 50-round SHA-0), will also be shown. These techniques were improved by Antoine Joux, who used them to find a collision of the full SHA-0. We then discuss the application of these techniques to SHA-1, and present collisions of reduced variants of SHA-1 (our current record is 36 rounds), along with near-collisions of longer variants.

Dokonamy wprowadzenia do obliczeń wielopodmiotowych (ang.: multiparty computations, MPC). Dziedzina ta została zapoczątkowana pracami [1,2] i była intensywnie rozwijana przez ostatnie dwie dekady. Nieformalnie, protokoły obliczeń wielopodmiotowych umożliwiają grupie użytkowników wykonanie wspólnego zadania bez wzajemnego ujawniania swoich sekretów. (Przykładem może być wspólne obliczenie publicznie znanej funkcji z zachowaniem tajności jej argumentów).

Przedstawione zostaną najważniejsze definicje, wyniki i kierunki badań. Nie jest wymagana żadna wcześniejsza znajomość tych zagadnień. Znajomość podstaw kryptografii może być przydatna.

1. Goldreich, Micali and Wigderson. How to play any mental game, STOC 1987
2. A. C. Yao. Protocols for secure computations, FOFS 1982.

Na seminarium przedstawione będą znane metody ataków (na podstawie między innymi monografii Barta Preneela Analysis and Design of Cryptographic Hash Functions) na funkcje skrótu, wraz z przykładami.

Zaprezentowano bardzo praktyczny atak z samym szyfrogramem na komunikację szyfrowaną w systemie GSM i różne aktywne ataki na protokoły GSM. Atak te mogą nawet włamywać się do sieci GSM, która używa szyfrów "nie do złamania". Opisano atak z samym szyfrogramem na A5/2, który wymaga tylko kilkunastu milisekund szyfrowanej off-the-air rozmowy i znajduje poprawny klucz w mniej niż sekundę na PC. Rozszerzono ten atak (do bardziej złożonego) na A5/1. Opisano nowe ataki na protokoły sieciowe, które wykorzystują A5/1, A5/3, czy nawet GPRS. Ataki te opierają się na błędach w bezpieczeństwie protokołów GSM i działają zawsze, gdy tylko telefon komórkowy obsługuje A5/2. Podkreślono, że są to ataki na protokoły i mogą być stosowane zawsze, gdy telefon komórkowy używa słabego szyfru, zadziałają także z zastosowaniem kryptoanalizy A5/1. W przeciwieństwie do wcześniejszych ataków na GSM, które wymagały nierealnych ilości informacji, takich jak długi znany strumień tekstu jawnego, te ataki są bardzo praktyczne i nie wymagają żadnej wiedzy o zawartości rozmowy. Ataki te pozwalają atakującym na przechwycenie rozmowy i rozszyfrowanie jej w czasie rzeczywistym lub kiedykolwiek później. Pokazano także ataki aktywne takie jak: przechwytywanie rozmowy, zmianę danych wiadomości i kradzież wywołania (rozmowa na koszt innego użytkownika).

Referat jest fragmentem pracy pt. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication E. Barkana, E. Bihama i N. Kellera opublikowanym na CRYPTO 2003.

Plan referatu:

1. Wstęp
2. Opis A5/2 i bezpieczeństwo GSM
   1. Bezpieczeństwo GSM: A3/A8 i GPRS
3. Atak ze znanym tekstem jawnym na A5/2
   1. Optymalizacja ataku ze znanym tekstem jawnym na A5/2
4. Błyskawiczny atak z samym szyfrogramem na A5/2
5. Przełożenie ataków na wszystkie sieci GSM
6. Możliwe scenariusze ataków
   1. Podsłuch rozmowy
   2. Przechwycenie rozmowy
   3. Zamiana danych wiadomości (sms)
   4. Kradzież rozmowy - dynamiczne klonowanie
7. Podsumowanie

Zaprezentowana zostanie odkryta przez Bartosza Żółtaka i zaprezentowana na międzynarodowej konferencji FSE'04 w Delhi, Indie, funkcja jednokierunkowa VMPC (Variably Modified Permutation Composition). Jest to najprawdopodobniej najprostsza znana funkcja jednokierunkowa. Podstawowy wariant funkcji wykorzystuje trzy elementarne operacje na permutacjach, podczas gdy proces odwracania tego przekształcenia wymaga średnio ok. 2²⁶⁰operacji. Zaprezentowany zostanie najbardziej efektywny znany autorowi algorytm odwracania funkcji VMPC.

Druga część referatu poświęcona będzie praktycznemu wykorzystaniu funkcji VMPC do budowy bardzo prostego, szybkiego i - zgodnie z dotychczasowymi analizami - w pełni bezpiecznego szyfru strumieniowego, wraz z algorytmem zarządzania kluczem i wektorem inicjującym. Omówione zostaną aspekty implementacji i bezpieczeństwa algorytmu, ze szczególnym naciskiem na szereg przewag w bezpieczeństwie VMPC nad popularnym szyfrem strumieniowym RC4.

Na zakończenie przedstawiona zostanie koncepcja - Tail-MAC - bardzo prostego algorytmu obliczania sum kontrolnych (tzw. Message Authentication Codes) dla szyfrów strumieniowych - na przykładzie systemu opartego na algorytmie VMPC.

Omawiam metodę implikującą efektywny algorytm faktoryzacji liczb Carmichaela. Uogólnia ona metodę Pollarda i w szczególności implikuje test Millera Rabina. Opisuję uproszczoną wersję tego ostatniego - test Lehmanna - oraz test Fermata, deterministyczny na podzbiorze N dużej gęstości.

Od 1979 r., kiedy Adi Shamir i niezależnie George Blakley wprowadzili koncepcje podziału tajemnicy, powstało mnóstwo pomysłów praktycznego wykorzystania i realizacji tego typu schematów. W swoim referacie przedstawię pomysły, które towarzyszyły rozwojowi Progowych Schematów Podpisu oraz kilka ich współczesnych implementacji.

Funkcje bent to funkcje maksymalnie nieliniowe względem wielu kryteriów nieliniowosci, jednak nie spełniające wszystkich kryteriów niezbędnych, aby znalazły zastosowanie do konstrukcji systemów kryptograficznych. Referat zawierać będzie omówienie podstawowych własności funkcji bent, ze szczególnym uwzględnieniem ich przydatności do stosowania w szyfrach blokowych typu DES. Przedstawione będą również przykłady konstrukcji omawianych funkcji.

Tematem prezentacji będzie system mikropłatności MINX: Micropayments with Secure Network Exchange. System ten posiada wszystkie własności wymagane od mikropłatności: operacje są efektywne obliczeniowo, a zapewniany poziom bezpieczeństwa stosunkowo wysoki. Poza tym ma on unikatowe własności karty pre-paid oraz zapewnia użytkownikowi pewną anonimowość. Umożliwia on również utajnienie wymiany danych między operatorem a użytkownikiem. Inną zaletą jest brak jakiejkolwiek zaufanej trzeciej strony i systemu klucza publicznego. Przed omówieniem systemu przedstawione zostaną ogólnie płatności elektroniczne i systemy mikropłatności.

Addressing new challenges by building security protocols around graphs
We discuss the use of graphs as basic objects in security/cryptographic protocols. While having all the functionality of their number based counterparts; such protocols can have extended capabilities, especially useful in the field of verification and analysis. The scalability and transitivity for graph related properties allow for addressing protocols of increasing complexity. These features also cater for new challenges in the future, which will be briefly discussed. Some examples of graph based protocols will be presented.

Na początku przewidywany jest krótki wstęp o grafach i ich kolorowaniu.
Następnie zaprezentowane zostanie twierdzenie określające górne ograniczenie liczby grafów o zadanej ilości wierzchołków, takich, że mogą zostać pokolorowane n kolorami. Rezultat ten jest następnie wykorzystywany do konstrukcji metody kodowania liczb z wykorzystaniem kolorowania grafów. Efektywność proponowanej metody rośnie wraz z długością sprawdzanych liczb i prawdopodobieństwem wystąpienia błędów.

W referacie będzie udowodniona pewna hipoteza dotycząca liczb pseudopierwszych. Pozwoli to łatwo rozkładać na czynniki pewne liczby pseudopierwsze Lucasa. Wykład ten jest głosem w dyskusji nad poprzednim referatem.

Wiele jest twierdzeń następującej postaci:

Jeżeli liczba naturalna n jest pierwsza, to spełnia warunek W.

Liczbę naturalną złożoną n nazywamy pseudopierwszą w sensie W, jeżeli spełnia warunek W.

Gdyby warunek W był łatwy do sprawdzenia i liczb pseudopierwszych w sensie W było "mało", to mielibyśmy dogodny sposób sprawdzania, czy dana liczba naturalna n jest pierwsza. Sprawdzalibyśmy po prostu, czy spełnia warunek W i czy należy do krótkiej listy liczb pseudopierwszych w sensie W.

W referacie zamierzam omówić pewien nowy rodzaj liczb pseudopierwszych określonych przez J. Granthama w 2000 r. zwanych liczbami pseudopierwszymi Frobeniusa.

W trakcie referatu chciałbym przedstawić nowy protokół mikropłatności czyli dokonywania transakcji elektronicznymi pieniędzmi o wartości nie przekraczającej 1 EURO. Będzie on zapewniał także anonimowość, jaką dają pieniądze nieelektroniczne, mimo minimalnego użycia silnej kryptografii (tzn. kryptografii klucza publicznego). Proponowany system jest, jak większość protokołów mikropłatności, systemem off-line, co w połączeniu z jego kredytowym charakterem wymusza kontrolę nad wydawaniem tych samych elektronicznych banknotów w kilku miejscach (ang. overspending). Umożliwia to pewna własność protokołu uwierzytelniania Schnorra, którego zmodyfikowaną wersję zastosowałem także do tworzenia i weryfikacji podpisów cyfrowych. Bezpieczeństwo protokołu opiera się między innymi na częściowo ślepych podpisach, umożliwiających tworzenie integralnych podpisów cyfrowych zawierających jednocześnie dane podpisywane "na ślepo" (nieznane autorowi podpisu) i dane jawne, z góry ustalone przez autora podpisu i osobę go zadającą. W miarę możliwosci czasowych postaram się opisać jeden z takich protokołów częściowo ślepych podpisów cyfrowych oparty na protokole Nyberga-Rueppela.

W referacie przedstawione zostaną podstawowe kryteria oceny funkcji boolowskich pod kątem wykorzystania ich w systemach kryptograficznych. Przedstawione zostaną metody wyznaczania nieliniowości, rzędu algebraicznego i odporności korelacyjnej funkcji boolowskiej. Pokazany zostanie sposób wykorzystania algorytmów genetycznych do wyszukiwania funkcji o odpowiedniej nieliniowości.

Kolektywne generowanie klucza sesyjnego przez grupę użytkowników jest uogólnieniem idei algorytmu Diffie-Hellmana wymiany klucza między dwoma użytkownikami nie dysponującymi tajnym kanałem łączności. Powstanie algorytmów pozwalających grupie wypracować wspólny, tajny klucz zostało wymuszone rozwojem wszelkiego rodzaju systemów konferencyjnych. Przyjmuje się, że tak wygenerowany klucz powinien być w równym stopniu wypadkową pewnych tajnych wartości wniesionych do algorytmu przez wszystkich uczestników. Obiektem naszego zainteresowania będzie potencjalna słabość niektórych z tych algorytmów, polegająca na możliwości wpływania przez część użytkowników na ostateczną wartość klucza w większym zakresie, niż to winno mieć miejsce.

Plan referatu

• pożądane cechy algorytmów kolektywnego generowania klucza
• rodzaje kontroli klucza
• algorytm Diffie - Hellmana wymiany klucza i jego niedoskonałości
• algorytm Just'a - Vaudenay'a wymiany klucza z poświadczeniem użytkowników
• kontrola klucza w algorytmie Burmaster'a - Desmedt'a
• algorytm GDH.2. (Giuseppe Ateniese, Michael Steiner, Gene Tsudik)

Szyfr blokowy Q to nowy algorytm zgłoszony w 2000 r. do projektu NESSIE, oparty na szyfrach Rijndael i Serpent. W referacie przedstawiony zostanie krótki opis algorytmu i wyniki kryptoanalizy autora. Zaproponowano połączenie wielu charakterystyk różnicowych jako różniczek (differentials), co pozwala na skonstruowanie ataku na pełny algorytm, lepszego od pełnego przeszukiwania. Przedstawiony zostanie opis tego ataku i jego wyniki. Praca ta, której współautorami są E. Biham, V. Furman i  V. Rijmen, była zaprezentowana na FSE 2001 w Jokohamie.

Stinson podaje algorytmy dla wyznaczenia takiego logarytmu dyskretnego, jak w tytule, i znajduje oszacowania ich (średniej) złożoności obliczeniowej. Zamierzam omówić też związane z tym problemy kombinatoryczne.

It is well known in cryptography that it is easy to construct an unbreakable secret-key cipher system if a plaintext source generates letters which are independent and equiprobable even if the length of a key sequence is much less than the length of the message. In this paper, we suggest a new secret-key cipher system in which a message generated is transformed into two parts in such a way that the biggest part consists of independent and equiprobable bits and only this part is encrypted. The complexity of the method is exponentially less than that for other known methods.

W trakcie seminarium zamierzam przedstawić stosunkowo nowy kryptosystem NTRU (1996, J. Hoffstein, J. Pipher, J.H. Silverman). W szczególności omówię wykorzystywane struktury algebraiczne, podam definicje kryptosystemu oraz podstawy jego bezpieczeństwa. Ponadto przedstawie kilka atakow na ten kryptosystem:

• bardzo efektowny atak na wielokrotną transmisję (1998, J. Hoffstein, J.H. Silverman).
• atak kratowy - a właściwie całą klasę ataków (1997, D. Coppersmith, A. Shamir)
• atak na NTRU ze złożonym parametrem N (2001, C. Gentry)

Kryptografia kwantowa zajmuje sie problemem bezpiecznej dystrybucji klucza,
tzn. proponuje sposob przesylania informacji w taki sosob aby po zakonczeniu
transmisji nadawca i odbiorca dysponowali ta sama informacja a jednoczesnie
mieli pewnosc, ze informacja ta pozostaje nieznana innym. W celu zapewnienia
bez jej bezpowrotnego zniszczczenia.

W czasie wykladu zamierzam przedstawic;
1. najwazniejsze protokoly kryptografii kwantowej tzn.
  a. protokol Benneta-Brassarda (BB84) wykorzystujacy dwie rozne reprezentacje
     ukladu kwantowego o dwu stanach ("dwa alfabety"),
  b. protokol Benneta (B92), rowniez wykorzystujacy kwantowe uklady dwustanowe,
     jednak przy uzyciu jednego alfabetu,
  c. protokol Ekerta wykorzystujacy lamanie nierownosci tzw. Bella przez uklady
     kwantowe
2. najwazniejsze i najnowsze realizacje doswiadczalne kwantowych dystrybucji
     klucza - osiagniecia i trudnosci.