Financial Crypto '14 - dzień trzeci

Dzisiaj dwie prezentacje wygłosił nasz rodak Lucjan Hanzlik z Politechniki Wrocławskiej. Obie prace dotyczą systemu zarządzania tożsamościami U-Prove. Pierwsza prezentacja ("Attack on a U-Prove Revocation Scheme from FC’13 - Exploiting the Weakness of the Underlying Accumulator Scheme (Short Paper)", Lucjan Hanzlik, Kamil Kluczniak i Mirosław Kutyłowski) wzbudziła wiele emocji, ponieważ przedstawia atak na modyfikację U-Prove przedstawioną rok temu właśnie na Financial Crypto. Atak pozwala na kompletne złamanie systemu i podszywanie się pod innych użytkowników. Druga praca ("A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates", Lucjan Hanzlik i Kamil Kluczniak) opisuje rozszerzenie protokołu U-Prove, które zapewnia większą anonimowość.

Bardzo ciekawa była również prezentacja Nicholasa Hoppera "Challenges in protecting Tor hidden services from botnet abuse". Okazuje się, że na przełomie sierpnia i września 2013 roku liczba węzłów w sieci Tor wzrosła w ciągu kilku dni z miliona do... 5 milionów! Odpowiedzialna za to była sieć botów (ang. botnet) Mevade. Tak duża liczba węzłów spowolniła kilkukrotnie korzystanie z Tora i prezentacja Nicholasa, który pracuje nad rozwojem Tora dotyczy właśnie metod ochrony sieci Tor przed botami. Celem botów najprawdopodobniej nie był atak na Tora, ale pytanie, czy Tor zapewnia jeszcze anonimowość w sytuacji kiedy 4/5 węzłów są kontrolowane przez jedną osobę pozostaje.

Financial Crypto '14 - dzień czwarty

Ostatni dzień konferencji w dużej mierze dotyczył jakże aktualnego tematu Bitcoina. Spore poruszenie na sali wywołała praca, która zatrząsła światem Bitcoina w listopadzie 2013, Majority is not Enough: Bitcoin Mining is Vulnerable. Wbrew tytułom prasowym, protokół Bitcoina nie został złamany. Praca zwraca jednak uwagę na ciekawy fakt, że minerom (użytkownikom inwestującym moc obliczeniową swoich komputerów w Bitcoina) opłaca się postępować inaczej niż to przewiduje oryginalna praca Satoshi Nakamoto z 2008. roku.

Kopanie Bitcoinów (ang. mining) polega na obliczaniu wartości znanej funkcji haszującej na kolejnych, dowolnie wybranych argumentach. Celem jest znalezienie takiego argumentu, dla którego wartość funkcji jest mniejsza od pewnej, z góry ustalonej granicy.

Zgodnie z oryginalnym protokołem Bitcoina, w momencie rozwiązania problemu (znalezienia argumentu, który haszuje się do odpowiednio małej wartości) miner ogłasza swój sukces, publikując tzw. blok i tym samym otrzymuje nagrodę w wysokości 25 bitcoinów. Oczekiwana wartość zarobionych w ten sposób bitcoinów jest proporcjonalna do mocy obliczeniowej minera w stosunku do mocy obliczeniowej całej sieci.

Zgodnie z pracą Satoshi Nakamoto, o ile moc obliczeniowa żadnego z minerów nie przekracza 50% mocy całej sieci, każdemu opłaca się postępować zgodnie z protokołem. Autorzy pracy dowiedli natomiast, że nie zawsze opłaca się od razu publikować wykopany blok. Pokazali oni mianowicie strategię, która nawet przy posiadaniu niewielkiej części całkowitej mocy obliczeniowej może dać wyższą wartość oczekiwaną zysku niż trzymanie się oryginalnego protokołu.

Financial Crypto '14 - dzień drugi

Drugiego dnia wykłady rozpoczęły się od prezentacji pracy Mehdi Tibouchi "Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings". Praca jest ciekawa, ponieważ porusza temat, który zazwyczaj jest pomijany przy konstrukcji kryptosystemów a mianowicie ukrycie samego faktu, że dane są szyfrowane. Dlaczego ktoś chciałby ukryć, że korzysta z szyfrowania? Rządy niektórych krajów, jak np. Chiny, czy Iran nie życzą sobie, żeby ich obywatele korzystali z anonimowości w internecie jaką daje technnologia Tor, ponieważ uniemożliwia to cenzurę. W tym celu filtrują połączenia internetowe wychodzące za granicę kraju i jeśli nabiorą podejrzeń, że dane połączenie jest połączeniem sieci Tor to zostaje ono przerwane. Z tego względu ważne jest, aby takie połączenia były możliwie trudne do odróżnienia od innych typów połączeń.

Połączenia Tor można odróżnić od innych połączeń, m.in. dzięki temu, że są one zaszyfrowane za pomocą szyfrów bazujących na krzywych eliptycznych. W szyfrach tych przesyłane wiadomości szyfrowane są jako ciągi punktów na takich krzywych, które są następnie kodowane jako ciągi bitów i przesyłane przez internet. Okazuje się, że opisy punktów na krzywych eliptycznych nie są do końca losowe i łatwo odróżnić je od innego typu danych. Z tego względu korzystne byłoby istnienie kodowania dla którego opis punktu na krzywej eliptycznej byłby zupełnie losowym ciągiem bitów (tzn. o rozkładzie jednostajnym). Dotychczas takie kodowania znane były tylko dla niektórych krzywych i to akurat takich, które do wykorzystania w kryptografii z pewnych względów często się nie nadają. Autor we wspomnianej pracy rozwiązuje ten problem i pokazuje algorytm kodowania punktów, który dla dowolnej krzywej generuje zupełnie losowe ciągi bitów.

Warto też wspomnieć o pracy "Scaling Private Set Intersection to Billion-Element Sets" (autorzy: Seny Kamara, Payman Mohassel, Mariana Raykova, Saeed Sadeghian). Postawiony w pracy problem jest następujący. Dwie osoby mają pewne zbiory danych, np. pacjentów szpitala lub klientów firmy i chcieliby policzyć przecięcie tych zbiorów. Nie ufają sobie jednak nawzajem i nie mogą po prostu przesłać sobie swoich zbiorów. Znane są rozwiązania dla tego problemu bazujące na tzw. Two Party Protocols, ale są one zbyt mało wydajne. Autorzy proponują inne rozwiązania przy założeniu, że możemy skorzystać z pomocy dodatkowego serwera, który może dokonywać obliczeń, ale nie powinien dowiedzieć się niczego o samych zbiorach.

Najprostsze rozwiązanie działa w następujący sposób. Strony ustalają między sobą klucz K i szyfrują za pomocą niego elementy swoich zbiorów a następnie przesyłają je do serwera. Serwer może wówczas policzyć przecięcie otrzymanych zaszyfrowanych zbiorów i przesłać je obu stronom, sam jednak nie dowiaduje się niczego o przetwarzanych zbiorach oprócz ich rozmiaru i rozmiaru przecięcia. Przy takim rozwiązaniu serwer może jednak oszukać i dodać lub odjąć jakiś element do przecięcia. Autorzy prezentują w pracy szereg algorytmów, które pozwalają uniknąć takiej sytuacji i wykryć modyfikacje dokonane przez serwer.

TCC 2014: sprawozdanie z konferencji

Za nami jedenasta już konferencja Theory in Cryptography Conference organizowana przez IACR.

Tym razem spotkanie najlepszych ekspertów od kryptografii teoretycznej odbyło się w San Diego. Klimat kalifornijski sprawiał, że trochę czuliśmy się jak podczas konferencji Crypto, która zawsze odbywa się niedaleko, bo w Santa Barbara. To spotkanie było jednak w trochę mniejszym gronie, a tematyka węższa. Pozwalało to na odbycie wielu ciekawych krótkich rozmów w trakcie przerw. Właśnie te spotkania często są najważniejsze. Ogólna fantastyczna atmosfera cakowicie zrekompensowała drobne potknięcia organizacyjne.

Przejdźmy jednak do soli konferencji. A więc do części merytorycznej!

Zwraca uwagę dużo odczytów na temat "obfuskacji", czyli "zaciemniania kodu". To o tyle interesujące, iż parę lat temu pojawił się rezultat negastywny w tej dziedzinie. Teraz kryptografowie próbują iść inną drogą: szukają wyników pozytywnych, ale przy silniejszych założeniach.

Poza tym pojawiły się dwa odczyty na o kodach niekowalnych. To istotne dla prac grupy warszawskiej, gdyż my również badamy ten temat. (Wstępne wyniki prezentowalimy na zeszłorocznym Crypto; nowe - niedługo powinny się pojawić.)

Mnie osobiście najbardziej zaciekawiło specjalne wystąpienie Silvio Micalego. Zeszłoroczny laureat nagrody Turinga opowiadał o swojej - jak sam to ujął - drugiej miłości. Pierwszą była kryptografia, ale została porzucona dla teorii mechanizmów. Nie znałem wcześniej tej dziedziny nauki. Przykładowy wynik: w przetagu otwartym najlepiej sprawdza się zasady "druga oferta wygrywa" (tę metodę stosuje Google przy sprzedaży miejsca reklamowego!), przy założeniu, iż każdy z graczy maksymalizuje swój własny zysk. Ta ostatnia uwaga jest bardzo istotna! Profesor Micali pokazywał, że to założenie nie musi być wcale praktyczne. Problemem może być zmowa kilku graczy. Przy takiej zmowie, może się okazać, że strategia żadnego z pojedynczych graczy (traktowanych niezależnie od reszty) nie jest optymalna, ale jako grupa zyskuje łącznie więcej! Wykład dotyczył właśnie tego typu problemów oraz (jakże by inaczej!) ich związku z kryptografią.

Na koniec ważne przypomnienie: za rok TCC odbędzie się w Warszawie. Zapraszamy i obiecujemy zarówno świetne wystąpienia, jak i znakomitą atmosferę. Za pogodę ręczyć niestety nie możemy... :)

Financial Crypto '14 - dzień pierwszy

Po dłuższej przerwie reaktywujemy nasz blog. Zaczynamy poniższą relacją z pierwszego dnia konferencji Financial Crypto. Ciąg dalszy niebawem.

Konferencja Financial Crypto, a w zasadzie Financial Cryptography and Data Security dla wielu kojarzy się głównie z Karaibami, gdyż właśnie tam jest przeważnie organizowana. Rok 2014 nie jest pod tym względem wyjątkowy - tym razem wybór padł na Barbados.

Tematyka prac jest bardzo różna - znajdziemy tu zarówno prace o atakach przeprowadzonych na działające systemy informatyczne, sporo prac przeglądowych i statystycznych (np. praca o tym, co się aktualnie dzieje z witrynami zamkniętych banków), ale również teoretyczne prace opisujące nowe protokoły kryptograficzne. W każdym wypadku, zgodnie z nazwą konferencji, prace są zawsze związane z przynajmniej jednym spośród słów: finanse, kryptografia, bezpieczeństwo.

Przy okazji konferencji zorganizowano dwa workshopy: 2nd Workshop on Applied Homomorphic Cryptography (WAHC '14) i 1st Workshop on Bitcoin Research (BITCOIN '14). To właśnie workshop o Bitcoinie i nasza praca na niego przyjęta jest powodem naszej wizyty na Barbadosie.

Pierwszy dzień konferencji rozpoczął Nicolas Christin z uniwersytetu Carnegie Mellon przedstawiając liczne wykresy i statystyki dotyczące zarówno bieżącej edycji, jak i całej osiemnastoletniej historii tej konferencji. Na zakończenie swojego wystąpienia zażartował, że najprostszą drogą do dostania się na konferencję jest... posiadanie polskiego paszportu! Jak się okazało, w tym roku Polacy jako jedyni osiągneli stuprocentowy wskaźnik przyjętych prac - oprócz naszej pracy na workshopie o Bitcoinie, na Financial Crypto przyjęto dwie krótkie prace (ang. short paper) autorstwa Lucjana Hanzlika, Kamila Kluczniaka i Mirosława Kutyłowskiego z Politechniki Wrocławskiej. Prace te opisują atak i poprawkę do protokołu U-Prove Revocation Scheme zaprezentowanego na tej samej konferencji w zeszłym roku.

Chyba największe emocje w trakcie pierwszego dnia konferencji wzbudził wykład inauguracyjny prof. Rossa Andersona z Cambridge na podstawie pracy Security Protocols and Evidence: Where Many Payment Systems Fail. W swojej publikacji autorzy opisują wiele luk w systemie EMV stosowanym obecnie w większości kart płatniczych używanych na całym świecie. W ramach jednego z eksperymentów skonstruowali oni mieszczące się w plecaku urządzenie pozwalające na przeprowadzenie tzw. ataku No-PIN, który pozwala na dokonanie płatności skradzioną kartą bez znajomości kodu PIN.

W innym eksperymencie kryptolodzy z Cambridge odkryli, że w co drugim używanym obecnie bankomacie generator unikalnych liczb losowych stosowanych w zapytaniach bankomatu do karty jest bardzo słaby, np. jest zwykłym licznikiem resetowanym co 3 minuty. Dzięki temu, mając dostęp do karty, można zasymulować zapytania bankomatu, wygenerować odpowiedzi karty i użyć ich w odpowiednim momencie w przyszłości. Pewien hiszpański marynarz stracił w ten sposób 6 razy po 3300 euro, po tym jak zapłacił w barze 33 euro za drinka...

Co wspólnego ma telegram Zimmermanna z Edwardem Snowdenem?

Poza sprawą Enigmy z czasów II wojny światowej polskie media rzadko piszą o historii kryptologii. Tym bardziej szkoda, że jak już to robią to mylą podstawowe fakty i to na dodatek po to żeby w pokrętny sposób bronić Amerykanów w aferze podsłuchowej NSA. W dzisiejszej Gazecie Wyborczej redaktor Paweł Wroński podaje taki o to przykład na poparcie swej tezy, że "przyjaciół też się podsłuchuje":

W 1917 r. dzięki podłączeniu się do podmorskiego kabla biegnącego po dnie Atlantyku Stany Zjednoczone przechwyciły depeszę niemieckiego dyplomaty Artura Zimmermanna do ambasadora Niemiec w Meksyku. [...] Stany Zjednoczone nie były wówczas w stanie wojny z Niemcami.

Jak można sprawdzić chociażby w Wikipedii telegram Zimmermanna przechwycili Brytyjczycy, jak najbardziej będący w stanie wojny z Niemcami. Na dodatek musieli włożyć całkiem sporo wysiłku aby przekonać Amerykanów, że telegram jest prawdziwy. 

No i wydawać by się mogło, że "nie być w stanie wojny" to nie to samo co "być przyjacielem"...

Dlaczego prof. Shamir nie dotarł na konferencję Crypto'13

prof. Adi Shamir

Wracamy do blogowania po chwilowej przerwie, spowodowanej nawałem obowiązków związanym z upływającym dziś terminem zgłaszania prac na konferencję Eurocrypt. W najbliższych dniach mamy nadzieję blogować trochę więcej, w szczególności niebawem napiszemy o dalszych reperkusjach sprawy Snowdena. 

Dziś podajemy tylko krótką informację, która spowodowała spore poruszenie w świecie kryptologicznym: prof. Adi Shamir, znana gwiazda kryptologii (od jego nazwiska pochodzi litera "S" w nazwie szyfru RSA), nie otrzymał na czas wizy amerykańskiej i w związku z tym nie mógł uczestniczyć w konferencjach Crypto oraz History of Cryptology. Stało się to pomimo tego, że prof. Shamir wystąpił o tę wizę z dużym wyprzedzeniem, w USA bywał już wielokrotnie, a ponadto jest członkiem Amerykańskiej Akademii Nauk. Szczegóły tej historii opisał sam prof. Shamir w mailu, który został udostępniony na tej stronie.

Dodajmy, że podobny przypadek miał miejsce w 2005 roku kiedy amerykańskie władze odmówiły wizy obywatelce chińskiej Xiaoyun Wang, która nie mogła ona w związku z tym uczestniczyć w konferencji Crypto, mimo, że przyznano jej nagrodę za najlepszą pracę na tej konferencji (dotyczyła ona łamania funkcji haszujących). Więcej o tej sprawie można przeczytać tu.

Wiele osób uważa, że długofalowo najbardziej na takim zachowaniu swoich urzędników straci sama Ameryka, gdyż już teraz daje się usłyszeć głosy, że społeczność naukowa powinna zrezygnować z organizowania konferencji w USA na rzecz krajów o bardziej rozsądnej polityce wizowej.