Powszechnie używane algorytmy haszujące hasła działają dzisiaj tak: Zasol hasło i wprowadź je do KDF. Na przykład przy użyciu PBKDF2-HMAC-SHA1 proces mieszania hasła toDK = PBKDF2(HMAC, Password, Salt, ...) . Ponieważ HMAC jest 2-okrągłym skrótem z wyściełanymi klawiszami, a SHA1 szereg permutacji, przesunięć, rotacji i operacji bitowych, zasadniczo cały proces jest pewnymi podstawowymi operacjami zorganizowanymi w określony sposób. Zasadniczo nie jest oczywiste, jak trudne są obliczenia. Prawdopodobnie dlatego funkcje jednokierunkowe są nadal przekonaniem i widzieliśmy, że niektóre historycznie ważne kryptograficzne funkcje skrótu stały się niepewne i przestarzałe.

Zastanawiałem się, czy da się wykorzystać NP całkowite problemy z hashowaniem haseł w zupełnie nowy sposób, mając nadzieję, że da to solidniejsze podstawy teoretyczne. Kluczową ideą jest założenie, że P! = NP (jeśli P == NP, to nie ma MFW, więc obecne schematy również się psują), ponieważ problem NPC oznacza, że ​​odpowiedź jest łatwa do zweryfikowania, ale trudna do obliczenia. Ta właściwość dobrze pasuje do wymagań mieszania hasła. Jeśli postrzegamy hasło jako odpowiedź na problem NPC, możemy zapisać problem NPC jako skrót hasła do przeciwdziałania atakom offline: łatwo jest zweryfikować hasło, ale trudno je złamać.

Zastrzeżenie polega na tym, że to samo hasło może być mapowane na wiele wystąpień problemu NPC, prawdopodobnie nie wszystkie z nich są trudne do rozwiązania. Jako pierwszy krok w tych badaniach próbowałem zinterpretować ciąg binarny jako odpowiedź na problem 3-SAT i skonstruować instancję problemu 3-SAT, dla którego ciąg binarny jest rozwiązaniem. W najprostszej postaci łańcuch binarny ma 3 bity: x_0, x_1, x_2. Następnie są 2 ^ 3 == 8 klauzul:

000 (    (x_0) v    (x_1) v    (x_2) )
--------------------------------------
001 (    (x_0) v    (x_1) v NOT(x_2) )
010 (    (x_0) v NOT(x_1) v    (x_2) )
011 (    (x_0) v NOT(x_1) v NOT(x_2) )
100 ( NOT(x_0) v    (x_1) v    (x_2) )
101 ( NOT(x_0) v    (x_1) v NOT(x_2) )
110 ( NOT(x_0) v NOT(x_1) v    (x_2) )
111 ( NOT(x_0) v NOT(x_1) v NOT(x_2) )

Załóżmy, że ciąg binarny ma wartość 000. Wtedy tylko 1 z 8 klauzul jest fałszywych (pierwszy). Jeśli odrzucimy pierwszą klauzulę i ORAZ pozostałe 7 klauzul, wówczas 000 jest rozwiązaniem wynikowej formuły. Więc jeśli przechowamy formułę, możemy zweryfikować 000.

Problem polega na tym, że dla 3-bitowego ciągu, jeśli zobaczysz tam 7 różnych klauzul, natychmiast wiesz, którego brakuje, a to ujawniłoby bity.

Później postanowiłem odrzucić 3 z nich, pozostawiając tylko 4 oznaczone jako 001, 010, 100 i 111. To czasami wprowadza kolizje, ale sprawia, że ​​rozwiązanie problemu jest mniej proste. Kolizje nie zawsze się zdarzają, ale nie wiadomo, czy na pewno znikną, gdy na wejściu będzie więcej bitów.

Edytować. W ogólnym przypadku, gdy ciąg binarny może być dowolnym z (000, 001, ..., 111), nadal istnieje 8 klauzul, gdzie 7 jest prawdą, a 1 jest fałszem. Wybierz 4 zdania, które dają wartość prawdy (001, 010, 100, 111). Odzwierciedla to poniższe wdrożenie prototypu.

Edytować. Jak pokazuje odpowiedź @DW poniżej, ta metoda wybierania klauzul może nadal skutkować zbyt wieloma klauzulami na danym zbiorze zmiennych, co umożliwia szybkie zawężenie ich wartości. Istnieją alternatywne metody wybierania klauzul spośród wszystkich klauzul 7 * C (n, 3). Na przykład: Wybierz inną liczbę klauzul z danego zestawu zmiennych i zrób to tylko dla sąsiednich zmiennych ((x_0, x_1, x_2), (x_1, x_2, x_3), (x_2, x_3, x_4), .. .) i tym samym tworzą cykl zamiast kliki. Ta metoda prawdopodobnie również nie działa, ponieważ intuicyjnie możesz wypróbować przypisania za pomocą indukcji, aby sprawdzić, czy wszystkie klauzule mogą być spełnione. Aby uprościć ogólną strukturę, zastosujmy po prostu bieżącą metodę.

Liczba klauzul dla ciągu n-bitowego wynosi 4 * C (n, 3) = 4 * n * (n - 1) * (n - 2) / 6 = O (n ^ 3), co oznacza rozmiar hash jest wielomianem wielkości hasła.

Jest to realizacja prototypu w Pythonie tutaj . Generuje wystąpienie problemu 3-SAT z wejściowego ciągu binarnego wprowadzonego przez użytkownika.

Po tym długim wprowadzeniu w końcu moje pytania:

1. Czy powyższa konstrukcja (zaimplementowana w prototypie) działa jako bezpieczne haszowanie hasła, a przynajmniej wygląda obiecująco, może zostać zmieniona itp.? Jeśli nie, gdzie się nie udaje?

2. Ponieważ mamy do wyboru 7 klauzul C (n, 3), czy można znaleźć inny sposób na zbudowanie bezpiecznej instancji 3-SAT odpowiedniej do użycia jako skrótu hasła, być może przy pomocy randomizacji?

3. Czy istnieją podobne prace mające na celu wykorzystanie kompletności NP do zaprojektowania sprawdzonych bezpiecznych schematów mieszania haseł i już przyniosły pewne wyniki (pozytywne lub negatywne)? Niektóre informacje i linki byłyby bardzo mile widziane.

Edytować. Przyjmuję odpowiedź poniżej przez @DW, który jako pierwszy odpowiedział i dał świetny wgląd w strukturę problemu, a także przydatne zasoby. Przedstawiony tutaj naiwny schemat wyboru klauzul (zaimplementowany w prototypie Pythona) nie działał, ponieważ możliwe jest szybkie zawężanie przypisań zmiennych w małych grupach. Jednak problem pozostaje otwarty, ponieważ nie widziałem formalnego dowodu, że takie redukcje NPC do hasła nie działają wcale. Nawet w przypadku tego konkretnego problemu redukcji 3-SAT mogą istnieć różne sposoby wybierania klauzul, których nie chcę tutaj wymieniać. Wszelkie aktualizacje i dyskusje są nadal mile widziane.

Niestety wydaje się, że to nie działa (szczegóły poniżej) i wydaje się, że trudno znaleźć sposób, aby ten pomysł przyniósł pewnie bezpieczny schemat.

Problem z Twoim ogólnym pomysłem

Nie jesteś pierwszym, który myśli o próbie oparcia kryptografii na problemach z NP. Problem polega na tym, że twardość NP zapewnia tylko najgorszą twardość, ale kryptografia wymaga średniej twardości. Podjęto wiele prób oparcia kryptografii na problemach z NP-zupełnymi (np. Kryptosystemami plecakowymi), ale nie radziły sobie dobrze. Zazwyczaj dzieje się tak, że ludzie odkrywają algorytmy, które są często średnio skuteczne (lub z nietrywialnym prawdopodobieństwem), nawet jeśli w najgorszym przypadku są one wykładnicze; to wystarczy, aby złamać krypto, nawet jeśli nie jest to sprzeczne z twardością NP.

$\ne$

Proponuję przeczytać więcej na ten temat. Przydatne punkty początkowe można znaleźć w : Znaczenie problemów trudnych dla NP w kryptografii , Problemy otwarte o średniej złożoności, inne niż funkcje jednokierunkowe , Status światów Impagliazzo? , Najgorsze przypadki do średnich redukcji przypadków .

Problem z twoim konkretnym schematem

Twoja konkretna propozycja nie jest w pełni określona. Aby przeanalizować schemat, musisz w pełni określić sposób jego działania. W twoim przypadku nie jest jasne, w jaki sposób wybierasz 4 z 7 klauzul w ogólnym przykładzie. (A pojedynczy przykład nie zastępuje specyfikacji, która opisuje, jak to robisz w ogóle).

$x_0,x_1,x_2,x_3,x_4$$2^5$możliwe przypisania do tych 5 zmiennych, więc wypróbuj je wszystkie i odrzuć każde przypisanie naruszone przez dowolną z 40 klauzul. Przewiduję, że pozostawi ci to tylko jedno zadanie, które jest zgodne ze wszystkimi klauzulami.

$1/2$$1/2^{10}$$2^5-1$$7/8$$(7/8)^{40} \approx 2^{-7.7}$$(2^5-1) \times 2^{-7.7} \approx 0.15$

Można to powtórzyć dla każdej grupy 5 zmiennych, jednoznacznie odzyskując unikalne, satysfakcjonujące przypisanie dla każdej z nich. W przypadku niejasności zadania kandydatów można sprawdzić pod kątem innych klauzul.

W ten sposób widzimy, że istnieje skuteczny algorytm, który zazwyczaj rozwiąże klasę instancji 3SAT wygenerowanych przez twoją procedurę. Nie rozwiąże wszystkich instancji 3SAT, ale generowane instancje mają specjalną strukturę i skutecznie rozwiązują instancje z tą specjalną strukturą. To dobrze ilustruje tę kwestię: niektóre wystąpienia 3SAT są łatwiejsze niż inne, a twardość 3SAT (w najgorszym przypadku złożoności) mówi niewiele lub nic o twardości specjalnych generowanych wystąpień lub twardości przeciętnej instancji 3SAT.