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

43

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ą)
Jan
źródło
22
FYI: Prawdopodobnie jest to motywowane wydobyciem bitcoinów.
ClojureMostly
55
„Jak wytrenować model, który pozwala mi podróżować w czasie, niezależnie od tego, czy jest to„ możliwe ”?”
Konrad Rudolph,
13
@Joshua OP chce odwrócić SHA-256. Pozwolę mu opublikować, nawet jeśli zajmie to tysiąc razy więcej kroków niż SHA-256. Przestanę też istnieć, ponieważ rozwiązanie prawie na pewno wykorzystuje błąd w obrębie samej rzeczywistości, aby pokonać logikę.
Konrad Rudolph,
15
Wszystkie skróty SHA256 mogą być generowane przez ciąg rozpoczynający się od „1”.
Reactgular,
8
@cgTag Przykro mi, ale to po prostu źle. Wejście steruje wyjściem, w przeciwnym razie nie byłaby to funkcja. Ponadto, ponieważ masz nieskończoną listę rzeczy, nie oznacza to, że jedna z nich zaczyna się od 1. Próbujesz udowodnić znaną hipotezę kryptograficzną w komentarzu do SE. Uwaga: Wierzę również, że to prawda, ale twierdzenie, że to prawda, jest mylące. Jeśli masz rację, na pewno będzie papier lub inne odniesienia.
Pedro A

Odpowiedzi:

98

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.

Chris H.
źródło
21
To jak dotąd (moim zdaniem) jedyna poprawna odpowiedź. Wszystkie pozostałe odpowiedzi wydają się bardziej zajmować problemem uczenia się funkcji skrótu niż nauki odwracania skrótu (pytanie rzeczywiste). Wszyscy wydają się ignorować to, że nie jest to funkcja iniekcyjna.
Luca Citi,
7
Czy nie mógłbyś przewidzieć prawdopodobieństwa, że pierwszy znak jest jednym? Brak relacji jeden do jednego nie jest rzadkim problemem w nauce statystycznej.
Matthew Drury,
16
@MatthewDrury Biorąc pod uwagę, że SHA256 jest zaprojektowany tak, aby wszystkie dane wejściowe były jednakowo prawdopodobne dla danego skrótu, mam nadzieję, że będzie nieskończenie wiele wejść zaczynających się od 1, dla każdego danego skrótu . Więc jeśli chcesz oszacować prawdopodobieństwo, najlepszym oszacowaniem będzie z grubsza . 1256±ε
Konrad Rudolph,
12
Tak, zgadzam się. Chciałem tylko zauważyć, że brak iniekcji nie jest tak naprawdę problemem strukturalnym w zastosowaniu uczenia maszynowego.
Matthew Drury,
6
@IMil Powodem, dla którego wspomniałem konkretnie o tym, że jest to funkcja skrótu, nie jest sugerowanie, że żadna funkcja skrótu nie mogłaby kiedykolwiek ujawnić tej informacji, ale motywowanie stwierdzenia, że ​​nie ma czegoś takiego jak „zwykły tekst”. Oczywiście (zła) funkcja skrótu może być częściowo odwracalna i wyraźnie powiedzieć nam coś o całym zestawie tekstów jawnych, które by ją wytworzyły, ale nie ma powodu, aby sądzić, że SHA-256.
Chris H
51

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.

Pavel Komarov
źródło
5
„mało prawdopodobne” i „powinno” - to właśnie powie mi algorytm. Na pierwszy rzut oka wydaje się to niemożliwe, ale chciałbym wiedzieć, jaki algorytm i podejście przyjąć, aby przetestować tę hipotezę.
Jan
24
+1 Gwarantowane jest, że jakikolwiek rodzaj „nienadzorowanego modelu regresji logistycznej” nie będzie w stanie zrobić nic lepszego niż zgadywanie, chyba że zostanie mu dostarczona prawdziwie astronomiczna liczba przypadków. Problemem jest przechylanie się wiatraków.
whuber
44
Możesz spróbować, ale uczeń będzie próbował znaleźć relację statystyczną, która celowo została zaprojektowana tak, by nie istniała.
Pavel Komarov,
32
„Zaprojektowany tak, aby był jak najbardziej losowy” to mało powiedziane. W szczególności projekt ma na celu uzyskanie maksymalnie nieliniowej zależności, w której każdy bit wejściowy wpływa na około 50% bitów wyjściowych, a każdy bit wyjściowy zależy od około 50% bitów wejściowych. Jest to znane jako zamieszanie i dyfuzja . To sprawia, że ​​zadanie tutaj (odzyskanie pierwszego bitu) jest tak samo trudne jak odzyskanie całej wiadomości.
MSalters,
12
Myślę, że możesz wzmocnić „mało prawdopodobne” w tej odpowiedzi. OP ma zerową szansę na zastosowanie technik statystycznych do przewidywania dowolnej części skrótu SHA256 na podstawie zawartości lub odwrotnie, z nawet wykrywalną poprawą w stosunku do losowego zgadywania. Praktycznym rozwiązaniem jest wstępne obliczenie całej docelowej populacji oryginalnej treści.
Neil Slater,
43

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.

IMil
źródło
6
sign(x)
11
@KonradRudolph: „Funkcja jednokierunkowa” ma w tym kontekście określone znaczenie, które nie jest tym, o którym myślisz. sign(x)w tym sensie nie jest funkcją jednokierunkową, ponieważ znalezienie preimage jest banalne.
user2357112,
4
To powiedziawszy, nie sądzę, że odpowiedź używa poprawnie „funkcji jednokierunkowej”.
user2357112,
1
@ user2357112 Dzięki, nie wiedziałem o tym. Znałem to znaczenie tylko jako funkcję, która jest przejmująca, ale nie biotywna. Taka jest również definicja podana w odpowiedzi, do czego się sprzeciwiłem.
Konrad Rudolph,
1
Tak, przepraszam, jestem trochę rozluźniony z definicjami. Uważam jednak, że „jednokierunkowy” jest bardziej zrozumiały dla nowicjuszy niż bardziej surowe warunki.
IMil
26

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.

Lyndon White
źródło
15

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ół .

po lewej stronie
źródło
4
Czytając to, przyszło mi do głowy, że a) aby zbudować tęczową tabelę, musisz wiedzieć, jakiej funkcji skrótu użyć, ib) być może algorytm uczenia maszynowego może określić, który algorytm jest używany, biorąc pod uwagę wystarczająco duży próbka wejść i wyjść (przynajmniej jeśli algorytm ma możliwe do zidentyfikowania wady). Więc jeśli pierwotny problem został przekształcony w nieznaną funkcję skrótu, którą należy zidentyfikować, może być bardziej praktyczny.
senderle
7

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.

senderle
źródło
Zastanawiam się, jak obliczenia kwantowe wpłyną na twierdzenie o braku obiadu. Można przypuszczać, że także ograniczenie przetwarzania kwantowego.
Max Vernon,
1
@ MaxVernon och, ciekawe. Spodziewałbym się, że wszystkie algorytmy kwantowe mają tę samą właściwość w porównaniu z innymi algorytmami kwantowymi . Nie wiem, czy wszystkie algorytmy kwantowej optymalizacji przyspieszają średnie przypadki w porównaniu do klasycznych. Mogą! Mam pytanie i odpowiedź na pytanie , które mogą dotyczyć twierdzenia o „darmowym obiedzie”. (tldr; obiad jest bezpłatny tylko wtedy, gdy zignorujesz część wykonanej pracy ... ale zastanawiam się, czy to zmieni się w przypadku kwantowym.)
senderle
5

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.

IndieSolver
źródło
2
To jest interesujące. Ale odpowiedź na lobste.rs jest prawdopodobnie prawidłowa. To ogromne uprzedzenie, łatwe do wykrycia. Pojęcie, że przez tak długi czas było niezauważone, jest dość dalekie.
senderle
1
@senderle W celu wykorzystania błędu (jeśli w ogóle) należy opracować algorytm (zasadniczo algorytm ML / optymalizacyjny), który jest tani obliczeniowo, tak aby jego własny koszt był wdrożony / mierzony na najnowocześniejszym sprzęcie jest kompensowane przez przyspieszenie, które zapewnia. Domyślam się, że współczynnik # haszytów powinien być większy niż 10x, aby pokonać brutalną siłę i jej superoptymalizowane implementacje. Konsekwencje mogą być bardzo poważne, szczególnie dla osób obstawiających krypto i protokoły bezpieczeństwa.
IndieSolver,
4

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.

Phil Frost
źródło
W matematyce nie lubię wierzyć na słowo . Twój program pokazuje, że twoja funkcja sha16 jest zaskakująca, ale nic więcej. Nie podałeś formalnego dowodu, że ten program może udowodnić faktyczną funkcję SHA-256. Według twojego stylu wniosku hipoteza Collatza zostałaby rozwiązana, ponieważ jest już rozwiązana dla 32 bitów, a program można łatwo uruchomić dłużej.
Roland Illig,
4

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.

Cort Ammon
źródło
2

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.

JimmyJames
źródło
1

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.

4Oh4
źródło
1

251222562256

26402641

2256264(2256264)!

S=(2256264)
C=90100S
CSC

(1S1S11S2...1S(C1))(SC1SCSC2SC1SC3SC2...12)=(SC1)!S!

=(110(2256264)1)!(2256264)!
2(2263.99184665662260.6509677217)
210.13222373912260.6509677217

22562512

użytkownik96549
źródło
1

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.

gnasher729
źródło