Topic: Czym jest "tagged hash", czyli "oznaczony skrót"? (Read 59 times)

Skoro już zostałem wywołany do tablicy, to skrobnę coś niecoś na ten temat. Tym razem po polsku, prosto w tej sekcji, w końcu trzeba zrobić tutaj trochę ruchu, bo coś zbyt pusto się tu robi.

Zatem do rzeczy: czym jest "oznaczony skrót"? Jak zapewne niektórzy zauważyli, swego czasu opisałem szczegółowo na anglojęzycznych częściach, jak działają funkcje skrótu, rozłożone na czynniki pierwsze:

Dlaczego funkcje skrótu są bezpieczne?
Wzmocnione SHA-1 kontra osłabione SHA-256: Jak je testować?

Na podstawie tych dwóch tematów wyżej (a zwłaszcza tego pierwszego, gdzie pokazuję podział na wektor inicjalizacyjny, dane, oraz hash końcowy) można zademonstrować, czym tak naprawdę jest "oznaczony skrót". Wróćmy do obrazka, który pokazałem w tamtym temacie:
Jak łatwo zauważyć, naszym punktem wyjścia jest 160-bitowa wartość "67452301 efcdab89 98badcfe 10325476 c3d2e1f0". W przypadku SHA-1, ta konkretna wartość jest używana domyślnie, głównie po to, aby nie zaczynać od samych zer, tylko aby mieć jakiś niezerowy początek, wygenerowany w przejrzysty sposób, bez wyciągania królika z kapelusza.

Następnie mamy wiadomość, w przypadku SHA-1 oraz SHA-256, składającą się z 512-bitowego zestawu, który jest odpowiednio rozszerzany. Obie wymienione funkcje skrótu implementują samą wiadomość identycznie, nawet sposób dokładania jedynki na końcu, zer w celu wyrównania danych, a także 64-bitowego rozmiaru całości w bitach, wygląda dokładnie tak samo. Różnice występują dopiero przy rozszerzaniu wiadomości na kolejne rundy.

Ostatecznie, uzyskujemy skrót końcowy, który przy tych samych danych wejściowych, będzie zawsze identyczny. Oznacza to tyle, że SHA-1 pustej wiadomości zawsze i wszędzie wynosi dokładnie "da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709".

W przeciwieństwie do poprzedniego tematu, tutaj zakładamy, że mamy do czynienia z więcej niż jednym blokiem danych. Dlaczego? Otóż cała idea oznaczonego skrótu polega właśnie na tym, aby wykorzystać atak rozszerzający wiadomość i zamienić go w coś pożytecznego. Spróbujmy zatem wykonać właśnie ten atak na dwóch blokach i zobaczyć, co nam z tego wyjdzie. Zaatakujmy pusty blok w taki sposób, aby dołożyć kolejny pasujący blok, dokładając tylko tyle danych, ile musimy:
A teraz czas na magiczną sztuczkę: wyobraźmy sobie, że usuniemy pierwszy blok i że zmienimy nasz wektor inicjalizacyjny na taki skrót, jaki uzyskaliśmy w środku. Co się wówczas stanie? Otóż: niespodzianka! Skróty pozostaną nienaruszone! Wniosek? Możemy wystartować od "da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709" i podać jako drugą wiadomość dokładnie taki blok, jaki mamy wyżej: z jedynką na początku, garścią zer w ramach wyrównania, a także wartością 512, zapisaną jako 0x200 na ostatnich 64 bitach.

I właśnie na tym polega ten słynny oznaczony skrót, używany w Taproocie. Zamiast używać typowego wektora inicjalizacyjnego, mamy do czynienia z jakimiś danymi początkowymi, które zmieniają nam wektor inicjalizacyjny i sprawiają, że startujemy od innej wartości niż zwykle.

Przejdźmy zatem do SHA-256 i zobaczmy, jak to wygląda w praktyce. Naszym źródłem będzie tutaj BIP-340:

W tym przypadku, implementacja Taproota korzysta z faktu, że blok danych składa się z 512 bitów, zaś SHA-256 produkuje nam dokładnie 256-bitowy skrót. Bierzemy zatem dwa takie skróty i łączymy ze sobą, uzyskując wiadomość z pierwszego bloku. Następnie obliczamy skrót pośredni i od tej pory nie musimy już liczyć go ponownie, tylko wykorzystujemy go odtąd jako nasz nowy wektor inicjalizacyjny. Zobaczmy zatem, jak to wygląda na praktycznych przykładach:
Na podobnej zasadzie możemy ustalić pozostałe skróty pośrednie, używane w ramach BIP-340:
Wiedza przedstawiona powyżej powinna wystarczyć, aby tworzyć dowolne oznaczone skróty. W przypadku innych funkcji skrótu, takich jak SHA-1, również da się to łatwo osiągnąć, wystarczy chociażby wstawić potrojony wynik SHA-1 i dołożyć dowolną 32-bitową wartość, choćby taką, która oznaczałaby użyty protokół. Cała trudność przy 160-bitowych funkcjach skrótu polega na znalezieniu dobrego pomysłu na utworzenie 512-bitowego bloku danych, dalej całość wygląda analogicznie, jak w przypadku SHA-256.

Planuję jeszcze odgrzebać stare tematy związane z Taprootem, bo z tego co pamiętam, tam mogły być też używane takie hashe, bodajże przy tworzeniu klucza publicznego, który może być wydany tylko przez pojedynczą sygnaturę Schnorra, bez żadnego TapScriptu. Poszukam i postaram się to uzupełnić, na razie kończę w tym miejscu.

Zachęcam do pytań, żeby wiedzieć, w jakim kierunku pisać i czy w ogóle chcecie tego więcej, czy też idę w zbyt ciężkostrawne technikalia i powinienem zacząć od przetłumaczenia swoich starszych wpisów o funkcjach skrótu, zanim dotknę oznaczonych skrótów i innych nowszych tematów.