Czy istnieją „refleksyjne” algorytmy mieszające?

Czy istnieje klasa algorytmów mieszających, teoretycznych lub praktycznych, tak że algorytm w tej klasie można uznać za „zwrotny” zgodnie z definicją podaną poniżej:

hash1 = algo1 („tekst wejściowy 1”)
hash1 = algo1 („tekst wejściowy 1” + hash1)

Operator + może być konkatenacją lub dowolną inną określoną operacją, aby połączyć wynik (hash1) z powrotem w dane wejściowe („tekst wejściowy 1”), aby algorytm (algo1) dał dokładnie ten sam wynik. tj. kolizja na wejściu i wejściu + wyjściu. Operator + musi połączyć całość obu danych wejściowych, a algo nie może odrzucić części danych wejściowych.

Algorytm musi generować wysoką entropię na wyjściu. Może być, ale nie musi, być kryptograficznie trudne odwrócenie wyjścia z powrotem do jednego lub obu możliwych wejść.

Nie jestem matematykiem, ale dobra odpowiedź może zawierać dowód na to, że taka klasa algorytmów nie może istnieć. Nie jest to jednak abstrakcyjne pytanie. Naprawdę jestem zainteresowany wykorzystaniem takiego algorytmu w moim systemie, jeśli taki istnieje.

Jest to duplikat pytania, które zostało po raz pierwszy opublikowane na stronie /programming/4823680/reflexive-hash

ds.algorithms hash-function Społeczność
źródło

Powiązane: Asocjacyjne mieszanie skrótów

Tsuyoshi Ito

Czy interesuje Cię ta właściwość przechowująca cały tekst wejściowy lub jeden tekst wejściowy? Jeśli chcesz, aby przechowywał cały tekst wejściowy, tworzenie kolizji jest z założenia trywialne, więc nie sądzę, że można go uznać za dobrą funkcję skrótu.

Peter Taylor

Ktoś chce hashować pliki, które zawierają własne skróty! ;)

Raphael

@Peter Taylor - Szukam funkcji, która działa jak opisano dla dowolnego tekstu wejściowego. Każde inne wejście tworzy skrót, który ogólnie ma wysoką wzajemną entropię do każdego innego możliwego wejścia. Tak jak działa dobra nieodwracalna funkcja skrótu. Jednak szukana funkcja skrótu nie musi mieć właściwości nieodwracalności. Wysoka entropia jest wystarczająca.

@Raphael - Tak, to zwięzły sposób.

Odpowiedzi:

Daję trywialną konstrukcję, która spełnia ten wymóg. Podaję to, aby jedynie odpowiedzieć na istnienie „refleksyjnej” funkcji skrótu.

Niech będzie dowolną funkcją skrótu wytwarzającą wysoką entropię na wyjściu. Załóżmy, że hashuje łańcuchy binarne o dowolnej długości do bitowych łańcuchów binarnych, gdzie jest dowolną liczbą całkowitą dodatnią. Niech oznacza operator konkatenacji i niech $G$ $G$ $k$ $k$ $+$ oznacza długość ciągu binarnego . $|x|$ $x$

Zdefiniuj funkcję skrótu na wejściu w następujący sposób: $H$ $x$

$|x| \le k$ $H(x) \overset{\text{def}}{=} G(x)$
$|x| > k$ $L$ $R$ $(|x|-k)$ $k$ $x$ $x = L + R$ $|R|=k$ $R = H(L)$ $H(L)$ $H(x) \overset{\text{def}}{=} R$ $H(x) \overset{\text{def}}{=} G(x)$

Jak powiedziałem, jest to trywialna konstrukcja. Można go zastosować do dowolnej funkcji skrótu, praktycznej (takiej jak MD5, SHA-1, ...) lub teoretycznej.

MS Dousti
źródło

H

$H$

| R | = k

$|R|=k$

@Raphael: Dziękujemy za wskazanie literówki (poprawione). H ma taką samą entropię jak G, chyba że w stanie, w którym R = G (L). Zgodnie z wymaganiem, w tym stanie H (x) powinno być równe R. Nie możemy tutaj nic zrobić, aby zwiększyć entropię; ponieważ wymóg „refleksyjności” uniemożliwia nam zmianę produkcji.

MS Dousti

@Sadeq: Czy wymagane jest, aby funkcja mieszająca była obliczana rekurencyjnie? Czy algorytm w jakikolwiek sposób korzysta z tego faktu?

Yasser Sobhdel

H (M + H (M) + H (M) + \dots + H (M))

$H(M+H(M)+H(M)+\ldots+H(M))$

H (M)

$H(M)$

Sadeq, dziękuję. Wierzę, że może to odpowiedzieć na moje pytanie, tak jak zostało zadane. Odpowiedziałeś w odpowiednim zastrzeżeniu. Z pragmatycznego punktu widzenia podoba mi się fakt, że jest to nakładka na każdy dobrze znany algorytm, taki jak SHA-1. Jeśli dobrze zrozumiałem, algorytm będzie kontynuował obliczanie skrótów rekurencyjnie, dopóki nie osiągnie wymaganej kolizji, a następnie zatrzyma się. W takim przypadku być może możemy nazwać to naiwnym rozwiązaniem. Obawiam się, że wydaje się, że istnieje domniemane założenie, że osadzony algorytm (powiedzmy SHA-1) ostatecznie trafi w wymagany skrót mieszający, biorąc pod uwagę