Ogłoszono nową funkcję skrótu SHA-3

[KopalniaWiedzy.pl 357]

Amerykański NIST (Narodowy Instytut Standardów i Technologii) ogłosił wyniki konkursu na zestaw funkcji skrótu SHA-3. Konkurs ogłoszono w 2007 roku, gdy NIST zaczął podejrzewać, iż SHA-2 można złamać. Jego zwycięzcą został algorytm Keccak, stworzony przez Guido Bertoniego, Joan Daemen, Gillesa Van Assche i Michaela Peetersa.

Keccak został wybrany, gdyż współpracuje z wieloma różnymi urządzeniami, a testy przeprowadzone przez NIST i niezależnych badaczy wykazały, że jest najszybszym algorytmem spośród 64 zgłoszonych do konkursu.

Warto zauważyć, że w przeciwieństwie do poprzednich funkcji SHA oraz algorytmów MD4 i MD5 Keccak nie wykorzystuje struktury Merkle'a-Damgarda, ale używa techniki, którą jego twórcy nazwali "funkcją gąbki". To duża zaleta, gdyż dzięki temu jest mało prawdopodobne, by atak skuteczny przeciwko SHA-2 był równiez skuteczny w przypadku SHA-3.

Tim Polk, ekspert ds. bezpieczeństwa w NIST mówi, że Instytut nadal uznaje SHA-2 za bezpieczny, ale posiadanie innego algorytmu zapewnia specjalistom większą elastyczność. Ponadto wydajność SHA-3 czyni go bardzo interesującym rozwiązaniem dla producentow urządzeń przenośnych.

[Jarek Duda 139]

Przyglądnąłem się właśnie tej "funkcji gąbki": http://sponge.noekeon.org/

Bierzemy w miarę duży stan (r+c bitów), dzielimy wiadomość na fragmenty stałej długości (r bitów) - w każdym kroku XORujemy kolejny fragment z częścią stanu oraz używamy ustalonej permutacji (f) na wszystkich bitach stanu.

Brzmi prosto, elegancko ... ale z perspektywy kryptograficznej składając te permutacje dostajemy znowu permutację - każdy bit wiadomości wpływa tylko na pojedynczy bit stanu końcowego i to łatwo prześledzić który !?!

Czyli kompletny brak nawet podstawowej własności wymaganej od systemów kryptograficznych: mieszania - zmiana pojedynczego bitu wiadomości powinna zmieniać nie jeden bit stanu, tylko średnio połowę wszystkich - powinna powodować że stan jest zupełnie niezwiązany z poprzednim.

 

Ogólnie wiara w bezpieczeństwo kryptografii zbudowanej tylko na permutacjach i XORach (jak nawet AES) to jest taka heureza że tak skomplikowana łamigłówka no to już chyba nie powinna być łatwo rozwiązywalna ...

Zupełnie nie rozumiem dlaczego nie wychodzi się w mniej przewidywalne nielinowe funkcje ... np. Asymetryczne Systemy Liczbowe - szybkie i proste w użyciu, a niesłychanie nieliniowe i konkretną funkcję możemy sobie pseudolosowo wybrać ... stan automatu zawiera niecałkowitą ilość bitów, wypluwając całe bity gdy się skumuluje:

http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/

[peceed 127]

Zastanawia mnie dlaczego nie rozpatruje się skrótów typu sha2^sha3. Przy zupełnie nieskorelowanych funkcjach haszujących efektywna trudność złamania w prosty sposób powinna się zbliżać do przeglądu wszystkich możliwych rozwiązań, i nawet możliwość skutecznego ataku na każdą składową nie daje najmniejszej możliwości ataku na funkcję złożoną. W ten sposób sha2-256 ^ sha3-256 ze wszelkich praktycznych względów mogłoby być równie bezpieczne jak sha2-512, miałby taki sam koszt obliczniowy a dawało mniejszy skrót. Mało tego - można by przyjąć zasadę, że funkcję skrótu zawsze tworzymy przez połączenie dwóch niezależnych i mocnych algorytmów, i przy pojawieniu się skutecznego ataku na jedno ogniwo - możemy bez paniki je wymienić.

 

Co do braku zainteresowania ASL - jak w życiu, wiele rzeczy najlepiej zrobić samemu. Konkurs na SHA-4 powinien wystartować w ciągu następnej dekady

[Jarek Duda 139]

peceed, kluczowe tutaj są szybkość, prostota, złożoność pamięciowa ... zarówno dla softwarowych jak i hardwarowych implementacji - żeby np. taki węzeł przez który przechodzą setki GB/s był w stanie sprawdzać w czasie rzeczywistym sumy kontrolne ...

Kolejną sprawą jest że składanie metod wcale nie musi prowadzić do czegoś bezpieczniejszego - składanie permutacji czy XORów z wzorcem jest (nową ale) dalej permutacją czy XORem z wzorcem ... dla dłuższej kombinacji tych operacji pewnie tak łatwo tego nie widać, ale to nie znaczy że się nie da - w każdym razie jak chcemy zbudować coś bezpiecznego, trzeba zacząć od bezpiecznych cegiełek, czyli dla kryptografii: nieprzewidywalnych, chaotycznych, nieliniowych.

[peceed 127]

@Jarek

To jest raczej oczywiste, że wynikowy algorytm haszujący będzie miał koszty pomięciowe i czasowe praktycznie równe sumie kosztów swoich składowych ( w praktyce można zamortyzować koszty I/O).

Zapostulowałem, że złożenie dwóch rozsądnych funkcji mieszających operacją xor nie może dać w efekcie funkcji _słabszej_ od każdej składowej.

Można oczywiście łatwo celowo skonstruować taki przypadek celowo - 2 identyczne funkcje. Intuicja podpowiada jednak, że w przypadku zastosownia wystarczająco różnych i bezpiecznych składowych wynikowa funkcja jest znacznie trudniejsza do złamania niż składowe.

Jest masa rozmaitych zastosowań w których ważniejsze jest bezpieczeństwo od wydajności. Zastosowanie (i ustandaryzowanie) podwójnego haszowania dwoma algorytmami mogłoby być znacznie lepszą praktyką niż proste zwiększanie długości klucza.

[wilk 103]

Najlepiej na początek rozgraniczyć zastosowania, bowiem innych parametrów oczekujemy od funkcji do generowania sum kontrolnych - tu ważna jest wydajność, a innych od funkcji do uwierzytelniania - tutaj wprost przeciwnie.

[Jarek Duda 139]

peceed, "Intuicja podpowiada..." - brawo, świetnie scharakteryzowałeś "dowody" bezpieczeństwa: nawrzucać tyle XORów i permutacji żeby "intuicja podpowiadała" że już wygląda bezpiecznie ... ;D

A co jeśli jednak jest ukryta luka, np. pozwalająca wygenerować zmieniony plik o takiej samej wartości funkcji hashującej ... ? I ktoś sobie po cichu podmienia pliki a ludzie myślą że oryginalne bo zgadzają się z posiadaną przez nich sumą kontrolną ...

 

A może zamiast dodawać kolejne XORy i permutacje żeby "intuicja jeszcze silniej podpowiadała", użyć czegoś tak nieprzewidywalnego żeby po prostu nie dało się obejść ...

Na przykład wspomniane asymetryczne systemy liczbowe jako podstawowy bloczek - krok dla przetworzenia bajtu to użycie niewielkiej tablicy, a potem ściągnięcie (zmiennej!) ilości bitów tak żeby stan automatu wrócił do założonego przedziału (I), przy okazji wypluwając skumulowane bity.

Użycie tablicy zwiększa logarytm z wartości stanu o mniej więcej (dyfuzyjność) lg(1/q_s) - zwykle niewymierną liczbę (ergodyczność) i to q_s (prawdopodobieństwo symbolu) zmienia się (asymetria) dosłownie pseudolosowo od punktu do punktu, jak poniżej (z http://dl.dropbox.co...5967/ANSang.pdf ).

Wszystko jest zapisane w tej tablicy, która np. została na początku pseudolosowo wygenerowana (generujemy rozkład symboli o zadanym rozkładzie prawdopodobieństwa) - pomijając trzy własności poniżej, samo to powoduje że po prostu nie da się śledzić, szukać skrótów etc. dla pracy automatu ...

 

Oprócz/zamiast XORa i permutacji, tak nieprzewidywalnych podstawowych bloczków powinno się szukać dla kryptografii!

 

 

wilku, do sum kontrolnych ta gąbka rzeczywiście jest ok, ale dla uwierzytelniania to jest prosty xor z permutacji - trzeba sporo obudować żeby można było temu zaufać ...

[peceed 127]

@Jarek

Nie lubię być upierdliwy, ale czasami trzeba (oj, znalazł się mój miotacz ognia):

 

>/Przyglądnąłem się właśnie tej "funkcji gąbki "(...)

f nie musi być permutacją ani funkcją liniową, w sha3 - nie jest

 

>każdy bit wiadomości wpływa tylko na pojedynczy bit stanu końcowego i to łatwo prześledzić który !?!

nieprawda i nieprawda, http://en.wikipedia.org/wiki/Keccak, podrundy 8 i X

 

>Ogólnie wiara w bezpieczeństwo kryptografii zbudowanej tylko na permutacjach i XORach (jak nawet AES)

>to jest taka heureza że tak skomplikowana łamigłówka no to już chyba nie powinna być łatwo rozwiązywalna ...

>świetnie scharakteryzowałeś "dowody" bezpieczeństwa: nawrzucać tyle XORów

>i permutacji żeby "intuicja podpowiadała" że już wygląda bezpiecznie

Radziłbym się dokładnie przyjrzeć czego dotyczą dowody kryptoodporności tych algorymów, nie ma to nic wspólnego z intuicją.

Intuicja jest kluczowa do formułowania hipotez i przydatna do poszukiwania dowodów, ale same dowody są bardzo ścisłe.

 

>Zupełnie nie rozumiem dlaczego nie wychodzi się w mniej przewidywalne nielinowe funkcje ...

Z oczywistego powodu - brak narzędzi do kryptoanalizy i oceny bezpieczeństwa takich funkcji. Bez takich zbliżamy się niebezpiecznie do

"szyfrowania opartego na tajemnicy".

Trzeba rozróżnić dwie rzeczy - bezpiecznie i "wiadomo, że bezpiecznie z określonym powodem pewności". Bezpieczne rozwiązania o których nie wiemy jak bardzo są bezpieczne są niebezpieczne.

 

// w każdym razie jak chcemy zbudować coś bezpiecznego, trzeba zacząć od bezpiecznych cegiełek,

//czyli dla kryptografii: nieprzewidywalnych, chaotycznych, nieliniowych

Korekcja błedów oraz ogromna liczba skutecznych algorytmów szyfrujących i mieszających opartych na prostych operacjach wskazuje na coś przeciwnego.

Skomplikowane zachowania naprawdę nie wymagają skomplikowanych składowych, NKS Wolframa dobrze to wyjaśnia.

 

>Czyli kompletny brak nawet podstawowej własności wymaganej od systemów kryptograficznych: mieszania - zmiana pojedynczego

>bitu wiadomości powinna zmieniać nie jeden bit stanu, tylko średnio połowę wszystkich - powinna powodować że stan jest zupełnie niezwiązany z poprzednim.

>wilku, do sum kontrolnych ta gąbka rzeczywiście jest ok, ale dla uwierzytelniania to jest prosty xor z permutacji

>- trzeba sporo obudować żeby można było temu zaufać ...

 

Nieuznawanie autorytetów to przydatna cecha, ale bez przesady. Trochę więcej pokory - konkurs na SHA3 trwa 5 lat i uczestniczą w nim jedni z najlepszych ekspertów w dziedzinie (niezatrudnieni przez NSA ), patrzący sobie nawzajem na ręce. Na pewno w prezentowanych algorytmach nie ma szkolnych błędów (przynajmniej w 2 rundzie), a zwycięzca nie może być słaby.

 

 

Odnośnie XOR-owania niezależnych funkcji mieszających - może lepiej to zdefiniuję. Bardzo słaba i poddatna funkcja mieszająca - funkcja stała c - w żaden sposób nie upośledza siły

mieszającej funkcji c(x)^h(x) jeśli h(x) jest silne. Aby pewna funkcja niszczyła własności mieszające drugiej przez operację liniową, sama musiałaby być funkcją w ogromnym stopniu liniową z drugą funkcją. Przykład dla funkcji h(x): h(x)^const, etc. Fakt że 2 różne funkcje mieszające oparte na zupełnie innych procedurach wykazywałyby liniowa zależność pokazałby zaziwiający i nieprawdopodobny związek między zupełnie różnymi strukturami matematycznymi.

[Jarek Duda 139]

Rzeczywiście gąbka w Keccaku zawiera nieliniowość: http://keccak.noekeo...cs_summary.html

A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), forall (x,y) in (0…4,0…4)

jednego "and"a - cała reszta to xory i permutacje.

Nie mówię że wiem jak to zrobić, tylko że nie jestem przekonany że tym razem już nie istnieje skrótowy sposób na rozwiązanie takiej łamigłówki logicznej.

Piszesz że są "dowody kryptoodporności" - proszę przybliż jak chciałbyś dowodzić nieistnienie takich algorytmów? Podpowiem że jest to bardzo zbliżony problem do dowodzenia że P!=NP.

Chyba jedyny prawdziwy dowód bezpieczeństwa o jakim słyszałem to dla "one-time pad": xorujesz z jednorazowym kluczem - cała reszta to raczej zbiór heurez i wiary w autorytety ... jasne (znanych!) "szkolnych błędów" pewnie nie ma, ale skąd mamy wiedzieć że np. nie jest tak że jeden z autorytetów już znalazł bardzo subtelne obejście i właśnie dlatego tak forsuje?

W żadnym razie nie chodzi mi o to żeby snuć teorie spiskowe, tylko zwrócić uwagę że jednak istnieją nawet bardziej nieprzewidywalne-bezpieczne podstawowe bloczki których moglibyśmy użyć niż nawet wspaniały pojedynczy "bitand" ...

 

Wspomniałeś składanie w korekcji błędów - rzeczywiście w początkach telekomunikacji konkatenacji używało się dla dużych szumów ( http://en.wikipedia....orrection_codes ), ale podczas gdy jednym kodem bardzo trudno podejść do granicy Shannona, po złożeniu dwóch odlatujesz od niej w kosmos ... konkatenacja szybko odeszła do lamusa gdy tylko pojawiły się porządne "jednofazowe" metody: Turbo Codes, Low Density Parity Check (a teraz właśnie dołącza do nich Correction Trees: http://arxiv.org/pdf/1204.5317 ).

[peceed 127]

Ale dowody kryptoodporności nie polegają na udowadnianiu że nie istnieją algorytmy pozwalające znacznie zredukować czas łamania funkcji w porównaniu do naiwnego przeszukiwania przestrzeni rozwiązań, tylko pokazuje się że dana metoda nie ma gorszych własności od pewnych wyidealizowanych rozwiązań wzorcowych.

Tak naprawdę brak istnienia takich algorytmów nie jest konieczny aby uzyskać praktyczne bezpieczeństwo, bo osobną sprawą jest znalezienie tych algorytmów. Z praktycznego punktu widzenia istotne jest to aby samo znlezienie efektywnych algorytmów łamiących było porównywalnie trudne z atakiem brute-force.

Moja propozycja xorowania niezależnych algorytmów zwiększa bezpieczeństwo właśnie na tym poziomie - jest to w pewnym sensie mieszanie przestrzeni algorytmów atakujących. Nie upieram się, że pełny przegląd przestrzeni możliwych skrótów (czyli w praktyce szukamy wszystkich ciągów instrukcji krótszych od 2^256*<ilość instrukcji potrzebnych na wymieszanie wiadomości> które zmniejszają średni czas ataku dla każdej praktycznej wiadomości (np. < 2^64) wykaże, że taka opercja zawsze zwiększa bezpieczeństwo, bo tak nie będzie(to doświadczenie myślowe).Ale na pewno zwiększy praktyczne bezpieczeństwo.

 

Nie wspominałem o składaniu w korekcji błędów, to nadinterpretacja. Odnosiłem do ogólnikowego twierdznia "... jak chcemy zbudować coś bezpiecznego, trzeba zacząć od bezpiecznych cegiełek ..." , które może być prawdziwe w przypadku budowania fizycznych budowli, ale nie algorytmów. Przykładem jest korekcja błędów, która pozwala dowolnie zwiększać pewność kanału transmisji.

 

Chyba powinieneś stworzyć _wydajną_ implementację skrótu która wykorzystuje ASL. Jeśli będzie wolniejsza w większym stopniu niż (1-4)xSHA2, to ze wszelkich praktycznych względów można o niej zapomnieć. Jeśli zmieści się w limicie, to można rozpocząć pracę nad analizą jej bezpieczeństwa. Jeśli okaże się istotnie szybsza, to można zacząć rozważać ją jako heurystyczne wzmocnienie dowolnej funkcji skrótu h według schematu h(x)^aslh(x).