Czy uczenie maszynowe może dekodować skróty SHA256?

Mam 64-znakowy skrót SHA256.

Mam nadzieję wytrenować model, który może przewidzieć, czy tekst jawny użyty do wygenerowania skrótu zaczyna się od 1, czy nie.

Niezależnie od tego, czy jest to „możliwe”, jaki algorytm byłby najlepszy?

Moje początkowe przemyślenia:

• Wygeneruj dużą próbkę skrótów rozpoczynających się od 1 i dużą próbkę skrótów, które nie zaczynają się od 1
• Ustaw każdy z 64 znaków skrótu jako parametr dla pewnego rodzaju nienadzorowanego modelu regresji logistycznej.
• Wytrenuj model, informując go, kiedy jest właściwy / zły.
• Mam nadzieję, że uda się stworzyć model, który będzie w stanie przewidzieć, czy tekst jawny zaczyna się od 1, czy nie z wystarczająco dużą dokładnością (i przyzwoitą kappą)

To nie jest odpowiedź na statystyki, ale:

Nie , nie można określić pierwszego znaku tekstu jawnego na podstawie skrótu, ponieważ dla danego skrótu nie ma czegoś takiego jak „tekst jawny”.

SHA-256 jest algorytmem mieszającym. Bez względu na zwykły tekst, otrzymasz 32-bajtową sygnaturę, często wyrażoną jako 64-znakowy ciąg szesnastkowy. Istnieje znacznie więcej możliwych tekstów jawnych niż możliwych 64-znakowych ciągów szesnastkowych - ten sam skrót można wygenerować z dowolnej liczby różnych tekstów jawnych. Nie ma powodu, aby sądzić, że pierwsza postać będąca / nie będąca „1” jest jednolita we wszystkich tekstach jawnych wytwarzających dany skrót.

SHA256 jest zaprojektowany tak, aby był jak najbardziej losowy, więc jest mało prawdopodobne, abyś był w stanie oddzielić skróty pochodzące od 1-tekstowego tekstu jawnego od tych, które tego nie robią; po prostu nie powinno być żadnej cechy łańcucha mieszającego, która zdradzałaby te informacje.

Niezależnie od tego, czy jest to „możliwe”, jaki algorytm byłby najlepszy?

Przepraszam, ale to bezsensowne pytanie. Jeśli coś jest niemożliwe, nie możesz znaleźć najlepszego podejścia do problemu.

W tym przypadku zdecydowanie powinno to być niemożliwe, ponieważ haszowanie jest funkcją jednokierunkową: kilka danych wejściowych (w rzeczywistości nieskończonych) może generować ten sam wynik. Jeśli pierwszy bit wejścia sam w jakiś sposób wpłynie na prawdopodobieństwo określonej wartości skrótu, oznacza to, że algorytm skrótu jest całkowicie wadliwy.

Z pewnością możesz wytrenować sieć neuronową, klasyfikator liniowy, SVM i cokolwiek innego, aby spróbować przewidzieć. A jeśli będziesz w stanie rzetelnie przewidzieć dane wejściowe z danych wyjściowych dla określonego algorytmu mieszającego, to udowodni to, że ten algorytm jest bezwartościowy. Powiedziałbym, że w przypadku powszechnie stosowanego algorytmu, takiego jak SHA256, taka możliwość jest znikomo niska. Jednak rozsądne jest szybkie wykluczenie nowych, niesprawdzonych i niesprawdzonych algorytmów mieszających.

Chociaż nie da się udowodnić negatywem na przykładzie. Nadal uważam, że przykład byłby sugestywny; i być może przydatne. I pokazuje, jak można (próbować) rozwiązać podobne problemy.

W przypadku, gdy chcę tworzyć prognozy binarne, używając funkcji, które są wektorami binarnymi , losowy las jest dobrym wyborem. Myślę, że tego rodzaju odpowiedzi stanowią drugą część twojego pytania: co to jest dobry algorytm.

Chcemy wstępnie przetworzyć łańcuchy SHA256 na wektory binarne (boolowskie), ponieważ każdy bit jest statystycznie niezależny, a zatem każdy bit jest dobrą cechą. Dzięki temu nasze wejściowe 256-elementowe wektory boolowskie.

Próbny

Oto demonstracja tego, jak można to wszystko zrobić przy użyciu biblioteki Julia DecisionTree.jl .

Możesz skopiować wklej poniżej do monitu Julia.

using SHA
using DecisionTree
using Statistics: mean
using Random: randstring

const maxlen=10_000 # longest string (document) to be hashed.

gen_plaintext(x) = gen_plaintext(Val{x}())
gen_plaintext(::Val{true}) = "1" * randstring(rand(0:maxlen-1))
gen_plaintext(::Val{false}) = randstring(rand(1:maxlen))


bitvector(x) = BitVector(digits(x, base=2, pad=8sizeof(x)))
bitvector(x::AbstractVector) = reduce(vcat, bitvector.(x))

function gen_observation(class)
    plaintext = gen_plaintext(class)
    obs = bitvector(sha256(plaintext))
    obs
end

function feature_mat(obs)
    convert(Array, reduce(hcat, obs)')
end

########################################

const train_labels = rand(Bool, 100_000)
const train_obs = gen_observation.(train_labels)
const train_feature_mat = feature_mat(train_obs)

const test_labels = rand(Bool, 100_000)
const test_obs = gen_observation.(test_labels)
const test_feature_mat = feature_mat(test_obs)


# Train the model
const model = build_forest(train_labels, train_feature_mat)
@show model


#Training Set accuracy:
@show mean(apply_forest(model, train_feature_mat) .== train_labels)

#Test Set accuracy:
@show mean(apply_forest(model, test_feature_mat) .== test_labels)

Wyniki

Kiedy to zrobiłem, trenowałem na 100 000 losowych ciągów ASCII o długości do 10 000. Oto wyniki, które zobaczyłem:

Trenuj model

julia> const model = build_forest(train_labels, train_feature_mat)
Ensemble of Decision Trees
Trees:      10
Avg Leaves: 16124.7
Avg Depth:  17.9

Dokładność zestawu treningowego:

julia> mean(apply_forest(model, train_feature_mat) .== train_labels)
0.95162

Dokładność zestawu testowego:

julia> mean(apply_forest(model, test_feature_mat) .== test_labels)
0.5016

Dyskusja

Więc to w zasadzie nic. Przeszliśmy z 95% na zestawie treningowym do niewiele ponad 50% na zestawie testowym. Ktoś mógłby zastosować odpowiednie testy hipotez, aby sprawdzić, czy możemy odrzucić
hipotezę zerową , ale jestem pewien, że nie możemy. Jest to niewielka poprawa w stosunku do współczynnika zgadywania.

To sugeruje, że nie można się tego nauczyć. Jeśli losowy las, możesz przejść od dobrze dopasowanego do trafiania tylko w liczbę trafień. Losowe lasy są w stanie nauczyć się trudnych danych wejściowych. Gdyby było coś do nauczenia, oczekiwałbym co najmniej kilku procent.

Możesz bawić się różnymi funkcjami skrótu, zmieniając kod. Co może być interesujące, otrzymałem w zasadzie takie same wyniki, gdy hashużywałem Julii we wbudowanej funkcji (która nie jest bezpieczną kryptograficznie hsah, ale nadal jest dobrym hashem, więc rzeczywiście powinna wysyłać podobne ciągi znaków osobno). Mam też w zasadzie te same wyniki CRC32c.

Funkcje skrótu są (z założenia) bardzo źle przystosowane do robienia czegokolwiek przy użyciu uczenia maszynowego.

ML jest zasadniczo rodziną metod modelowania / szacowania funkcji lokalnie ciągłych . To znaczy, próbujesz opisać jakiś system fizyczny, który, choć może mieć pewne nieciągłości, jest w pewnym sensie w większości przestrzeni parametrów wystarczająco gładki, aby można było użyć tylko rozproszonej próbki danych testowych do przewidzenia wyniku dla innych Wejście. Aby to zrobić, algorytmy AI muszą w jakiś sposób rozkładać dane na sprytną reprezentację podstawową, dla której szkolenie sugeruje, że np. Jeśli widzisz taki i taki kształt (który wydaje się korelować z wynikiem takiego i takiego splotu), to istnieje spora szansa, że ​​wyjście powinno mieć w odpowiednim regionie taką i taką strukturę (którą ponownie można opisać przez splot lub coś takiego).

(Wiem, wiele podejść ML wcale nie przypomina splotu, ale ogólna idea jest zawsze taka sama: masz trochę przestrzeni wejściowej, która jest tak wielowymiarowa, że ​​nie można jej wyczerpująco próbkować, więc znajdziesz sprytny rozkład, który pozwala ci ekstrapolować wyniki ze stosunkowo rzadkiej próbki).

Idea kryptograficznej funkcji skrótu polega jednak na tym, że każda zmiana tekstu jawnego powinna spowodować zupełnie inne podsumowanie. Tak więc bez względu na to, jak rozkładasz funkcję, lokalne estymatory nie pozwolą ci na ekstrapolację wpływu niewielkich wahań wokół tej części na wynik. O ile oczywiście nie przetworzysz wszystkich informacji z ograniczonego zestawu, ale nie nazywa się to uczeniem maszynowym: po prostu budujesz tęczowy stół .

To interesujące pytanie, ponieważ rodzi problemy dotyczące tego, co liczy się jako „uczenie maszynowe”. Z pewnością istnieje algorytm, który ostatecznie rozwiąże ten problem, jeśli można go rozwiązać. Wygląda to tak:

1. Wybierz swój ulubiony język programowania i zdecyduj o kodowaniu, które odwzorowuje każdy ciąg znaków na (potencjalnie bardzo dużą) liczbę całkowitą.

2. Wybierz liczbę losową i zamień ją na ciąg. Sprawdź, czy jest to prawidłowy program w Twoim języku. Jeśli nie, wybierz inny numer i spróbuj ponownie. Jeśli tak, uruchom go, natychmiast wstrzymaj i dodaj do listy wstrzymanych programów.

3. Uruchom na chwilę wszystkie wstrzymane programy. Jeśli któryś z nich zatrzyma się bez odpowiedniego rozwiązania, usuń go z listy. Jeśli ktoś opracuje odpowiednie rozwiązanie, gotowe! W przeciwnym razie powróć do 2 po pozostawieniu ich wszystkich na chwilę.

Nie ma wątpliwości, że jeśli masz nieskończoną pamięć i nieskończony czas, powyższy algorytm ostatecznie znajdzie dobre rozwiązanie. Ale prawdopodobnie nie to rozumiesz przez „uczenie maszynowe”.

Oto pocieranie: jeśli weźmiesz pod uwagę wszystkie możliwe problemy, żaden algorytm uczenia maszynowego nie poradzi sobie lepiej! Jest to znane jako twierdzenie o braku darmowego lunchu . Dowodzi to, że spośród wszystkich możliwych problemów, które można rzucić na dowolny algorytm uczenia maszynowego, liczba, którą można szybko rozwiązać, jest znikomo mała.

Może szybko rozwiązać te problemy tylko dlatego, że rządzą nimi wzorce, które algorytm może przewidzieć. Na przykład wiele udanych algorytmów zakłada, że:

1. Rozwiązania można opisać pewną złożoną serią mnożenia macierzy i zniekształceń nieliniowych, rządzonych przez zestaw parametrów.

2. Dobre rozwiązania będą grupowane w przestrzeni parametrów, dzięki czemu wystarczy wybrać otoczenie wyszukiwania, znaleźć najlepsze rozwiązanie, przesunąć sąsiedztwo wyszukiwania, aby najlepsze rozwiązanie znalazło się na środku i powtórzyć.

Oczywiście żadne z tych założeń nie ma zastosowania. Drugi jest szczególnie podejrzany. A darmowy lunch mówi nam, że te założenia nawet nie przydają się przez większość czasu. W rzeczywistości prawie nigdy się nie trzymają! To tylko nasze szczęście, że trzymają się pewnych ważnych problemów.

Wybrany problem od samego początku narusza założenie 2. Funkcje skrótu są specjalnie zaprojektowane, aby podobne dane wejściowe dawały zupełnie inne wyniki.

Zatem twoje pytanie - jaki jest najlepszy algorytm uczenia maszynowego do rozwiązania tego problemu? - prawdopodobnie ma bardzo prostą odpowiedź: wyszukiwanie losowe.

Jest to prawie niemożliwe. Jednak ludzie zaobserwowali pewne wzorce w SHA256, które mogą sugerować jego nieprzypadkowość Wyróżnienie dla SHA256 przy użyciu Bitcoin (szybsze wydobywanie po drodze) . Ich tldr:

„Aby rozróżnić idealny skrót losowej permutacji od SHA256, haszuj dużą ilość (~ 2 ^ 80) kandydujących bloków 1024-bitowych dwa razy, tak jak w Bitcoin. Upewnij się, że bity bloków kandydujących są ustawione rzadko (znacznie mniej niż 512 średnia oczekiwana), zgodnie z protokołem Bitcoin, odrzucanie bloków kandydujących, które nie spełniają standardu „trudności” Bitcoin (gdzie wynikowe skróty zaczynają się od dużej liczby 0.) Z pozostałym zestawem poprawnych kandydatów na dane wejściowe (467369, gdy ta analiza została wykonana), obserwuj szczególny zestaw 32 bitów w bloku wejściowym (znajduje się tam, gdzie Bitcoin ma wartość jednorazową, bity wejściowe 607-639). Zauważ, że średnia liczba bitów ustawiona w polu jednorazowym jest przekrzywiona w lewo, tj. mniej niż oczekiwana wartość zestawu 16 bitów (szacowana średnia 15,428). ”

Zobacz dyskusję na lobste.rs . Jednym z możliwych wyjaśnień jest uprzedzenie wprowadzone przez górników.

Odpowiem z programem. Aby zmniejszyć wymagania obliczeniowe, użyję wariantu sha256, który nazywam sha16, który jest tylko pierwszymi 16 bitami sha256.

#!/usr/bin/python3

import hashlib
from itertools import count

def sha16(plaintext):
    h = hashlib.sha256()
    h.update(plaintext)
    return h.hexdigest()[:4]

def has_plaintext_start_with_1(digest):
    """Return True if and only if the given digest can be generated from a
    plaintext starting with "1" first bit."""
    return True

def plaintext_starting_with_1(digest):
    """Return a plaintext starting with '1' matching the given digest."""
    for c in count():
        plaintext = (b'\x80' + str(c).encode('ascii'))
        d = sha16(plaintext)
        if d == digest:
            return plaintext

for digest in range(0x10000):
    digest = "%04x" % (digest,)
    plain = plaintext_starting_with_1(digest)
    print("%s hashes to %s" % (plain, digest))

To daje wynik:

b'\x8094207' hashes to 0000
b'\x8047770' hashes to 0001
b'\x8078597' hashes to 0002
b'\x8025129' hashes to 0003
b'\x8055307' hashes to 0004
b'\x80120019' hashes to 0005
b'\x8062700' hashes to 0006
b'\x8036411' hashes to 0007
b'\x80135953' hashes to 0008
b'\x8044091' hashes to 0009
b'\x808968' hashes to 000a
b'\x8039318' hashes to 000b
[...]

Zostawię pełny dowód jako ćwiczenie dla czytelnika, ale uwierz mi na słowo: istnieje wejście, które zaczyna się od „1” dla każdego możliwego skrótu od 0000 do ffff.

Jest też wejście, które nie zaczyna się od „1”. Jest też taki, który zaczyna się od pełnych dzieł Szekspira.

Odnosi się to do każdej dość dobrej funkcji skrótu, chociaż mój dowód na brutalną siłę może stać się niewykonalny obliczeniowo.

Opisujesz w zasadzie atak przed obrazem. Próbujesz znaleźć dane wejściowe takie, że po ich zaszyfrowaniu dane wyjściowe mają jakąś właściwość, np. „Wiodącą 1”. *

Jest to wyraźny cel szyfrowania kryptograficznego, aby zapobiec takim atakom przed obrazem. Jeśli możesz wykonać taki atak, zwykle uważamy ten algorytm za niepewny i przestajemy go używać.

Chociaż oznacza to, że nie jest to niemożliwe, oznacza to, że algorytm uczenia maszynowego musiałby jednocześnie przechytrzyć dużą część matematyków na świecie i ich superkomputerów. Jest mało prawdopodobne, że to zrobisz.

Jeśli jednak tak zrobisz, staniesz się znany jako ktoś, kto złamał główny algorytm szyfrowania kryptograficznego. Ta sława jest coś warta!

^{* Technicznie rzecz biorąc, „pierwszy atak typu preimage” próbuje znaleźć dopasowanie do określonego skrótu. Jednak aby pokazać, że algorytm skrótu ma pierwszą odporność na atak typu preimage, zazwyczaj pokazują, że nie można znaleźć żadnych znaczących informacji o danych wejściowych z skrótu.}

Większość wszystkich odpowiedzi tutaj mówi, dlaczego nie możesz tego zrobić, ale oto bezpośrednia odpowiedź na:

Niezależnie od tego, czy jest to „możliwe”, jaki algorytm byłby najlepszy?

Zakładając, że dane wejściowe są wystarczająco duże:

1. Policz zestaw prawidłowych znaków.
2. Weź odwrotność liczby z kroku 1.

Takie jest prawdopodobieństwo, że łańcuch wejściowy zaczyna się od „1”. Nie musisz nawet patrzeć na dane wejściowe. Jeśli możesz to zrobić lepiej, oznaczałoby to, że skrót jest bardzo zepsuty. Możesz zaoszczędzić wiele cykli procesora, próbując ćwiczyć algorytm wybierania liczb losowych.

Możesz wytrenować algorytm, który może dać inną odpowiedź z powodu nadmiernego dopasowania. Tak jest, chyba że coś jest nie tak z algorytmem mieszającym. Korzystanie z tego algorytmu jest wtedy błędne częściej niż w przypadku wybrania losowej wartości.

Funkcje mieszania są celowo zaprojektowane tak, aby były trudne do modelowania, więc (jak już wspomniano) może to być bardzo trudne. Niemniej jednak wszelkie słabości funkcji haszującej zmniejszą jej entropię, czyniąc ją bardziej przewidywalną.

Niezależnie od tego, czy jest to „możliwe”, jaki algorytm byłby najlepszy?

Przydatnym przykładem jest funkcja fizycznie niesklonowalna lub PUF - analogiczna do sprzętowej funkcji skrótu. Zazwyczaj zmiany produkcyjne są celowo stosowane, aby nadać każdemu PUF nieco inną odpowiedź, tak że ich „zakodowana” moc wyjściowa jest inna dla danego wkładu. Słabości konstrukcyjne ograniczają jednak entropię, a biorąc pod uwagę wystarczającą liczbę par wyzwanie-odpowiedź, często można zbudować model czarnej skrzynki PUF, aby można było przewidzieć odpowiedź na nowe, wcześniej niewidoczne wyzwanie.

Regresja logistyczna jest najczęściej stosowanym podejściem do tych ataków modelujących, tak jak w niniejszym artykule Rührmaira .

Algorytmy genetyczne (lub bardziej ogólnie strategie ewolucyjne) mogą być alternatywnym podejściem, ponieważ mają zastosowanie do problemów, których nie można rozróżnić i / lub rozdzielić liniowo. Są one również omówione w powyższym artykule.

$2^{512}$$2^{256}$$2^{256}$

$2^{64}$$0$$2^{64}-1$

$2^{256}-2^{64}$$(2^{256}-2^{64})!$

$S=(2^{256}-2^{64})$
$C=\frac{90}{100}*S$
$C$$S-C$

$2^{256}$$2^{512}$

Problem polega na tym, że „uczenie maszynowe” nie jest inteligentne. Po prostu próbuje znaleźć wzory. W SHA-256 nie ma wzorów. Nie ma nic do znalezienia. Uczenie maszynowe nie ma szans lepszych niż brutalna siła.

Jeśli chcesz złamać SHA-256 za pomocą komputera, jedyną możliwością jest stworzenie prawdziwej inteligencji, a ponieważ wielu sprytnych ludzi nie znalazło sposobu na stworzenie SHA-256, musisz stworzyć sztuczną inteligencję, która jest znacznie wyższa niż wielu mądrych ludzi. W tym momencie nie wiemy, czy taka nadludzka inteligencja złamie SHA-256, udowodni, że nie da się jej złamać, czy zdecyduje, że nie jest wystarczająco sprytna (tak jak ludzie). Czwarta możliwość polega oczywiście na tym, że taka nadludzka sztuczna inteligencja nawet nie zawracałaby sobie głowy myśleniem o ważniejszych dla niej problemach.