Powstanie nowe SHA

Za 4 lata będziemy dysponować mocą obliczeniową komputerów kwantowych kilka o ile nie kilkanaście rzędów wielkości większą. W dniu opublikowania decyzji o wyborze algorytmu domowy komputer będzie mógł go złamać siłowo w parę dni.

Taki scenariusz jest możliwy.

Ok, skrytykowałeś, ale jaką widzisz alternatywę? Odpuścić sobie prace nad nowymi metodami szyfrowania? Rozumiem, co masz na myśli, ale sama krytyka niekoniecznie wnosi wiele do tematu.

Chciałem powiedzieć, że 4 lata w dziedzinie bezpieczeństwa IT to niejeden kamień milowy. Procedury wdrażania od momentu ogłoszenia konkursu nie powinny przekroczyć roku. Alternatywą byłoby tu nie tworzenie nowych algorytmów na potrzeby konkursu ale wykorzystanie co nowszych już istniejących i w praktyce skutecznych rozwiązań, ewentualnie rozwijanie starych sprawdzonych metod (wydłużanie kluczy, łączenie istniejących modeli itp).

Chcialbym stanowczo zaprotestowac przeciwko szacowaniu powstania komputerow kwantowych i to jeszcze w perspektywie 4 lat.

Prawdziwa idea komputerow kwantowych jest jeszcze baaardzo daleka od realizacji. Nie chodzi w niej bynajmniej o  zastapienie elektronu kwantami, ale o zupelnie inna koncepcja maszyny rozwiazujacej problemy. W zasadzie nie da sie porownywac mocy obliczeniowych aktualnych liniowych komputerow z komputerami ktore otrzymuja wynik na zasadzie ewolucji.

Komputery aktualne sa to bardzo sprawne maszyny ktore robia to, co czlowiek zaprogramuje.

Komputery kwantowe to sa maszyny, ktorym zadaje sie problem, i otrzymuje sie ewolucyjnie wygenerowany wynik, ktory spelnia warunki odpowiedzi. Czlowiek zatem bedzie jedynie kierowal ewolucja rozwiazan, nie bedzie musial znac matematycznego sposobu na znalezienie odpowiedzi.

Prawda jest, ze w momencie powstania komputera kwantowego wszystkie aktualne sposoby szyfrowania beda zlamane. Nie dlatego jednak, ze bedzie to "o kilka rzedow szybsza" maszyna. Przyspieszenie o kilka rzedow mozna juz dzisiaj uzyskac za pomoca laczenia komputerow w klastry i stosujac sprzetowe lamacze hasel.

Wystarczy szyfrowany tekst przemnożyć przez olbrzymią liczbę pierwszą, tak dużą aby była poza zakresem możliwości użycia przez powszachnie wystepujący sprzęt.

Chciałem powiedzieć, że 4 lata w dziedzinie bezpieczeństwa IT to niejeden kamień milowy.

Podaj może przykład. Z IT mam doczynienia od 1997 i mimo iż minęło już prawie 3 x 4 lata nie dostrzegam jakichś nieprawdopodobnych skoków technologicznych.

Szybkość powszechnie dostępnych procesorów w tym czasie wzrosła z 200 MHz do prawie 4 GHz. Wzrost 20 razy.

Dyski twarde- szybkość wzrosła kilka razy. Pojemność z 2,5 GB do 1000 GB czyli 400 razy.

I tak można mnożyć, ogólnie w ciągu 12 lat, wszystko rosło od kilku do tysiąca razy.

A teraz słowo o kluczach, nie wiem czy znasz system binarny ale wzrost długości klucza z 512 na 1024 to nie jest podwójny wzrost bezpieczeństwa w sensie mocy obliczeniowej. To jest wzrost idący w kilkanaście jak nie kilkadziesiąt rzędów wielkości.

Ile zaś rzędów wielkości zwiększono moc obliczeniową sprzętu w czasie 12 lat o których pisałem? 1000 razy to zaledwie 3 rzędy wielkości. A Ty piszesz o rewolucjach w ciągu 4 lat? Maksymalnie 1 rząd wielkości, taki jest przyrot mocy obliczeniowej w ciągu 4 lat.

Prawda jest, ze w momencie powstania komputera kwantowego wszystkie aktualne sposoby szyfrowania beda zlamane. Nie dlatego jednak, ze bedzie to "o kilka rzedow szybsza" maszyna.

A to czemu?

Wystarczy szyfrowany tekst przemnożyć przez olbrzymią liczbę pierwszą, tak dużą aby była poza zakresem możliwości użycia przez powszachnie wystepujący sprzęt.

Ale to jest jednokierunkowa funkcja skrótu, nie szyfrowanie, a jak wiemy mnożenie można odwrócić. Poza tym istnieją dość wydajne biblioteki liczb bignum, gdzie można przeprowadzać działania na liczbach o niemal nieskończonej ilości cyfr (ograniczonej pojemnością pamięci, a nie rejestrów procesora), kwestią jest tylko wydajność systemu.

Chciałem powiedzieć, że 4 lata w dziedzinie bezpieczeństwa IT to niejeden kamień milowy. Procedury wdrażania od momentu ogłoszenia konkursu nie powinny przekroczyć roku. Alternatywą byłoby tu nie tworzenie nowych algorytmów na potrzeby konkursu ale wykorzystanie co nowszych już istniejących i w praktyce skutecznych rozwiązań, ewentualnie rozwijanie starych sprawdzonych metod (wydłużanie kluczy, łączenie istniejących modeli itp).

Po to jest tyle czasu, by matematycy, pasjonaci i inni mieli czas na przeanalizowanie konkursowych algorytmów pod kątem wszelkich podatności (dla fanów teorii spiskowych - także rząd [NSA]). To coś jak konkurs na AES, który wygrał algorytm Rijndael. Poza tym de facto SHA-1 (160 bitów) pozostanie używany jako bezpieczna funkcja skrótu do 2010 - czyli będą to tylko 2 lata, nie 4, zaś SHA-2 (224-512 bitów) dalej będą użyteczne (póki nie zostanie dowiedziona ich słabość, tak jak jakiś czas temu MD5). Natomiast wydłużanie kluczy nic nie da, jeśli struktura algorytmu jest skompromitowana. Zaś skuteczne rozwiązanie wcale nie musi znaczyć najbezpieczniejszego, a chodzi o wyznaczenie nowego standardu.

Poszukiwanie nowego algorytmu skrótu jest potrzebne i wcale nie chodzi o to czy można go złamać za pomocą domowego komputera czy też nie. Wszystko się da złamać metodą brute-force bez względu na to ile ma bitów. Wystarczy duży klaster lub choćby botnet (md5 szybko się łamie za pomocą tęczowych tablic).

Funkcje skrótu są używane do kontroli autentycznośći danych, zwykle stosowane są SHA1 lub MD5, obydwa nie są już 100% bezpiecznie gdyż udało się stworzyć w taki sposób zmodyfikowane dane że funkcja skrótu zwróciła tę samą wartość - czyli udowodnono że jest możliwe zmodyfikowanie podpisanych informacji w taki sposób że będą uznane za autentyczne.

Prawda, choć rainbow tables są bezużyteczne, gdy zastosuje się ziarno (salt), które obecnie niemal zawsze stosuje się ze wspomnianego powodu. SHA-1 nie tyle co zostało złamane, a wykazane zostało istnienie kolizji przy ilości prób radykalnie mniejszej od ataku brute-force (2^63 zamiast 2^80 iteracji). Jednakże spreparowanie czytelnego i sensownego dokumentu w przeciwieństwie do sum kontrolnych weryfikujących ściągane z netu pliki jest o niebo trudniejsze (stąd czasem stosuje się tandem SHA1 + np. MD5).

Ale to jest jednokierunkowa funkcja skrótu, nie szyfrowanie, a jak wiemy mnożenie można odwrócić

Najwyższe liczby pierwsze są największą tajemnicą systemów bankowych (takie większe niż 128 cyfr) . Każdy inny szyfr (złożenie kilku funkcji) można zastąpić uproszczoną funkcją wynikową przez aproksymację wielu wyników lub w przypadku tekstu przez analizę pewnych statystyk zasad występowania określonych kombinacji liter.

Oto jak ja rozumiem idee komputera kwantowego, w czesci wykreowane przez S.Lema:

Nie jest jak zwykle komputery zbudowany na bramkach logicznych zero jedynkowych, ale jest oparty na kwantach, zatem jego bramki maja stan nieokreslony w zakresie 0 .. 1.

Zbior kwantowych bitow przez swoja nieokreslonosc moze reprezentowac wiele ciagow zero-jedynkowych naraz.

Wykonywanie operacji na takim zbiorze jest równoznaczne z wykonaniem tej operacji na wszystkich takich ciagach naraz.

Wynikiem tez sa kwantowe bity, zatem aby wyłuskać z nich potrzebne nam dane, potrzebujemy algorytmów kwantowych.

Komputer dochodzi do rozwiazania wykonujac cale serie wynikow ktorych wartosc jest niepewna. Dopiero usredniona ich wartosc jest zblizona z pewna dokladnoscia do prawidlowego wyniku. Im dokladniejsza chcesz otrzymac wartosc, tym wiecej robisz serii.

Co do kryptografii :

Wszystkie artykuly opiewajace komputery kwantowe wspominaja, ze algorytm faktoryzacji Shora, służący do rozbijania liczb na czynniki pierwsze bedzie dzialal znacznie szybciej.

Znalazlem na sieci szacowany czas zlamania klucza 512-bitowego, cytuje:

"Ocenia się, że złamanie klucza 512-bitowego wymagałoby kilku tysięcy lat pracy klasycznego komputera, podczas gdy nawet prosty komputer kwantowy pracujący z algorytmem Shora potrzebowałby zaledwie kilku godzin. "

Komputer dochodzi do rozwiazania wykonujac cale serie wynikow ktorych wartosc jest niepewna.

Troche to podobne do nauki ludzkiej świadomości (coś jak uśredniony wynik z GPS choć jednostkowo błędny to uśrednienie miliona pomiarów daje wynik w metrach na powierzchnię kuli ziemskiej).

Najwyższe liczby pierwsze są największą tajemnicą systemów bankowych (takie większe niż 128 cyfr) .

Ty tu mówisz o RSA a to nie jest funkcja skrótu tylko szyfrowanie asymetryczne.

Najwyższe liczby pierwsze są największą tajemnicą systemów bankowych (takie większe niż 128 cyfr) . Każdy inny szyfr (złożenie kilku funkcji) można zastąpić uproszczoną funkcją wynikową przez aproksymację wielu wyników lub w przypadku tekstu przez analizę pewnych statystyk zasad występowania określonych kombinacji liter.

128 cyfr? Przecież najdłuższa obecnie znana liczba pierwsza ma niemal 13 milionów cyfr.

Wszystkie artykuly opiewajace komputery kwantowe wspominaja, ze algorytm faktoryzacji Shora, służący do rozbijania liczb na czynniki pierwsze bedzie dzialal znacznie szybciej.

Wspominają algorytm Shora, bo jest to jeden z niewielu znanych, naprawdę efektywnych kwantowych algorytmów.

Nie znamy natomiast kwantowego algorytmu umożliwiającego efektywne (tzn. inaczej niż metodą brute force) wyszukiwanie kolizji dla funkcji haszujących.

128 cyfr? Przecież najdłuższa obecnie znana liczba pierwsza ma niemal 13 milionów cyfr.

Generowanie takich dużych liczb trwa zbyt długo, by miały one jakiekolwiek praktyczne znaczenie. Natomiast bzdurną jest oczywiście idea, że jakiekolwiek liczby pierwsze, duże czy nie, są "największą tajemnicą systemów bankowych". To tak jakby ktoś powiedział, że liczby wytworzone przez generator liczb losowych są tajemnicą.

Natomiast bzdurną jest oczywiście idea, że jakiekolwiek liczby pierwsze, duże czy nie, są "największą tajemnicą systemów bankowych". To tak jakby ktoś powiedział, że liczby wytworzone przez generator liczb losowych są tajemnicą.

To może podasz mi z jakiej kombinacji liczb pierwszych korzysta Visa ??

To może podasz mi z jakiej kombinacji liczb pierwszych korzysta Visa ??

Nie korzysta z żadnej 'kombinacji' liczb pierwszych, bo w każdym protokole asymetrycznym klucze są generowane losowo.

Skein to rodzina algorytmów o długości od 256 do 1024 bitów.

Rozumiem, że jest to pewien skrót myślowy i pewnie się czepiam, ale gwoli ścisłości - to nie algorytm (czy też rodzina) ma długość od 256 do 1024 bitów, ale wygenerowany przez niego ciąg.