Zderzenie CRC32

To zależy całkowicie od tego, co rozumiesz przez "wiadomość". Jeśli możesz dołączyć cztery bajty bełkotu do jednej z wiadomości. (Tzn. cztery bajty, które nie mają znaczenia w kontekście wiadomości.) Wtedy staje się trywialne w najprawdziwszym tego słowa znaczeniu.

Myślenie w kategoriach bitów poruszających się przez maszynę stanową CRC32.

CRC32 jest oparty na rejestrze przesunięć sprzężenia zwrotnego galois, każdy bit w swoim stanie zostanie zastąpiony indukcją 32 bitów z danych ładunku. Na indukcja każdego bitu, pozycje wskazane przez wielomian będą wyłączne lub z sekwencją obserwowaną od końca rejestru przesunięcia. Ta sekwencja nie jest zależna od danych wejściowych, dopóki rejestr zmiany nie zostanie wypełniony.

Jako przykład, wyobraźmy sobie, że mamy rejestr przesunięcia wypełniony stanem początkowym 10101110, wielomianem 10000011 i wypełnionym nieznanymi bitami, X.

Polynomial *     **  |feedback (End of SR.)
State      10101110     0
State      X1010111     1
State      XX101000     0
State      XXX10100     0
State      XXXX1010     0
State      XXXXX101     1
State      XXXXXX01     1
State      XXXXXXX1     1
State      XXXXXXXX     0

Informacja zwrotna nie jest w kategoriach X, dopóki SR nie zostanie wypełniona! Aby więc wygenerować wiadomość z określoną sumą kontrolną, bierzesz nową wiadomość, generujesz CRC i ustalasz, że to kolejne 32 bity sprzężenia zwrotnego. Można to zrobić w 32 krokach funkcji CRC. Następnie należy obliczyć wpływ, jaki ta informacja zwrotna ma na zawartość rejestru zmian.

Skrótem do zrobienia tego jest umieszczenie wiadomości z czterema zerowymi bajtami, a następnie spojrzenie na sumę kontrolną. (Suma kontrolna to stan SR na końcu, który jeśli jest wypełniony czterema zerowymi bajtami to wpływ sprzężenie zwrotne i puste bajty.)

Exclusive lub, że wpływa z wartości sumy kontrolnej chcesz, zastąpić przyczepę czterech bajtów z tej wartości obliczeniowej i zregenerować sumę kontrolną. Możesz to zrobić za pomocą dowolnego programu, który generuje CRC32, edytora szesnastkowego i kalkulatora, który może obsługiwać szesnastkowy.

Jeśli chcesz wygenerować dwie wiadomości, które mają pełny sens i nie zawierają końcowych śmieci, sprawy stają się trochę trudniejsze. Określ liczbę sekcji, które możesz napisać możliwe alternatywy, o dokładnie tej samej długości.

Używając prozy Angielskiej jako przykładu. "Myślę, że to może zadziałać" oraz "Wierzę w takie podejście" Mają zasadniczo podobne znaczenia i dokładnie taką samą długość.

Identyfikacja wystarczającej liczby przykładów w wiadomości jest trudnym bitem (chyba że chcesz oszukiwać z białymi spacjami!) CRC 32 jest liniowy, pod warunkiem, że dane mają poprawne przesunięcie w obrębie wiadomości. Więc CRC([messagea][padding])^CRC ([padding] [messageb])=CRC ([messagea] [messageb]) Istnieją pewne zastrzeżenia z wyrównaniem słów, z którymi musisz sobie poradzić, jako ogólna wskazówka, chcesz rozszerzyć fragmenty na "stałe" części wiadomości. Zasadniczo chcemy mieć alternatywy dla N * 1,5, gdzie n jest wielkością CRC.

Możesz teraz obliczyć CRC, jaki ma wiadomość szkieletowa, wrażenie, że każdy alternatywny fragment miałby na niej, a następnie sporządzić tabela porównująca wpływ, jaki miałaby każda alternatywa dla każdego fragmentu. Następnie musisz wybrać alternatywy, które zmodyfikują szkieletowy CRC, aby dopasować CRC, który chcesz. Ten problem jest rzeczywiście dość zabawne do rozwiązania, po pierwsze znaleźć wszelkie alternatywy, które jednoznacznie zmodyfikować trochę, jeśli ten bit musi zmienić dla CRC, wybierz tę alternatywę i złożyć to wpływ na CRC, a następnie przejść ponownie. To powinno zmniejszyć przestrzeń rozwiązania, które następnie trzeba przeszukiwać.

To dość trudne do zakodowania, ale generowałoby to kolizje w bardzo krótkim czasie.