Может ли машинное обучение расшифровать хэши SHA256?

У меня есть хэш-код SHA256 из 64 символов.

Я надеюсь обучить модель, которая может предсказать, будет ли открытый текст, используемый для генерации хеша, начинаться с 1 или нет.

Независимо от того, является ли это «возможным», какой алгоритм будет наилучшим подходом?

Мои первые мысли:

• Создайте большую выборку хэшей, начинающуюся с 1, и большую выборку хешей, которые не начинаются с 1
• Установите каждый из 64 символов хеша в качестве параметра для некоторой неконтролируемой модели логистической регрессии.
• Обучите модель, сообщая ей, когда она правильная / неправильная.
• Надеемся, что удастся создать модель, которая может предсказать, начинается ли открытый текст с 1 или нет с достаточно высокой точностью (и с приличной каппой)

Это не совсем статистический ответ, но:

Нет , вы не можете определить первый символ открытого текста из хэша, потому что для данного хэша нет такого понятия, как «открытый текст».

SHA-256 - это алгоритм хеширования. Независимо от того, какой у вас открытый текст, вы получаете 32-байтовую подпись, часто выражаемую в виде шестнадцатеричной строки из 64 символов. Существует гораздо больше возможных открытых текстов, чем возможных шестнадцатеричных строк из 64 символов - один и тот же хэш может быть сгенерирован из любого числа различных открытых текстов. Нет оснований полагать, что первый символ, являющийся / не являющийся '1', является единообразным по всем открытым текстам, производящим данный хэш.

SHA256 спроектирован так, чтобы быть как можно более случайным, поэтому маловероятно, что вы сможете отделить хэши, полученные из открытого текста с 1 префиксом, от тех, которые этого не делают; просто не должно быть никакой особенности строки хеша, которая выдала бы эту информацию.

Независимо от того, является ли это «возможным», какой алгоритм будет наилучшим подходом?

Извините, но это бессмысленный вопрос. Если что-то невозможно, то вы не можете найти лучший подход к проблеме.

В этом случае это определенно должно быть невозможно, поскольку хеширование является односторонней функцией: несколько входов (фактически бесконечных) могут выдавать один и тот же результат. Если первый бит ввода сам по себе каким-то образом повлияет на вероятность конкретного значения хеш-функции, это будет означать, что алгоритм хеширования полностью ошибочен.

Вы, конечно, можете обучить нейронную сеть, линейный классификатор, SVM и еще много чего, чтобы попытаться сделать прогноз. И если вы сможете надежно предсказать входные данные для определенного алгоритма хеширования, это докажет, что этот алгоритм бесполезен. Я бы сказал, что для широко используемого алгоритма, такого как SHA256, такая возможность исчезающе мала. Тем не менее, это разумный подход для быстрого исключения новых, непроверенных и непроверенных алгоритмов хеширования.

Пока нельзя доказать отрицание на примере. Тем не менее, я чувствую, что пример был бы наводящим на размышления; и, возможно, полезно. И это показывает, как можно (пытаться) решить подобные проблемы.

В случае, когда я хочу делать двоичные предсказания, используя функции, которые являются двоичными векторами , случайный лес является хорошим выбором. Я думаю, что такого рода ответы на вторую часть вашего вопроса: что такое хороший алгоритм.

Мы хотим предварительно обработать строки SHA256 в двоичные (булевы) векторы, поскольку каждый бит статистически независим, поэтому каждый бит является хорошей особенностью. Так что это сделает наши входные данные 256-элементными логическими векторами.

демонстрация

Вот демонстрация того, как все это можно сделать с помощью библиотеки Julia DecisionTree.jl .

Вы можете скопировать вставить ниже в подсказку Джулии.

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)

Полученные результаты

Когда я это сделал, тренировался на 100 000 случайных ASCII-строк длиной до 10000. Вот результаты, которые я видел:

Тренируй модель

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

Точность тренировочного набора:

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

Точность тестового набора:

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

обсуждение

Так что это в принципе ничего. Мы прошли с 95% на тренировочном наборе до чуть более 50% на тестовом наборе. Кто-то может применить надлежащие проверки гипотез, чтобы увидеть, можем ли мы отвергнуть нулевую
гипотезу, но я почти уверен, что мы не сможем. Это небольшое улучшение по сравнению с вероятностью угадывания.

Это говорит о том, что этому нельзя научиться. Если Случайный Лес, может перейти от хорошо приспособленного к поражению только вероятности. Случайные леса довольно способны к изучению сложных входных данных. Если бы было чему поучиться, я бы ожидал как минимум несколько процентов.

Вы можете поиграть с различными хэш-функциями, изменив код. Что может быть интересно Я получил в основном те же результаты при использовании встроенной hashфункции julia (которая не является криптографически защищенной hsah, но все же является хорошим хэшем, поэтому действительно должна посылать подобные строки отдельно). Я также получил в основном те же результаты для CRC32c.

Хеш-функции (по замыслу) крайне плохо подходят для выполнения с ними машинного обучения.

ML - это, по сути, семейство методов для моделирования / оценки локально непрерывных функций. То есть, вы пытаетесь описать некоторую физическую систему, которая, хотя и может иметь определенные разрывы, в некотором смысле является достаточно гладкой в ​​большей части пространства параметров, так что для прогнозирования результата для других можно использовать только разрозненную выборку тестовых данных. вход. Чтобы сделать это, алгоритмы ИИ должны каким-то образом разложить данные в умное базисное представление, для которого обучение предложило, что, например, если вы видите такую-то и такую-то форму (которая, кажется, коррелирует с результатом такой-то свертки), то есть хороший шанс, что выходные данные должны иметь в соответствующей области такую-то структуру (которая может быть снова описана сверткой или чем-то еще).

(Я знаю, что многие ML-подходы совсем не похожи на свертку, но общая идея всегда одна и та же: у вас есть какое-то пространство ввода, которое настолько многомерно, что невозможно произвести исчерпывающую выборку, поэтому вы найдете умную декомпозицию, которая позволяет экстраполировать результаты сравнительно редкого образца.)

Идея криптографической хэш-функции заключается в том, что любое изменение открытого текста должно привести к совершенно другому дайджесту. Поэтому независимо от того, как вы разложите функцию, локальные оценки не позволят вам экстраполировать, как небольшие колебания вокруг этой части влияют на результат. Если, конечно, вы фактически не обрабатываете всю информацию ограниченного набора, но это не будет называться машинным обучением: вы просто создадите радужный стол .

Это интересный вопрос, потому что он поднимает вопросы о том, что считается «машинным обучением». Существует, конечно, алгоритм, который в конечном итоге решит эту проблему, если она может быть решена. Это выглядит так:

1. Выберите свой любимый язык программирования и выберите кодировку, которая отображает каждую строку в (потенциально очень большое) целое число.

2. Выберите случайное число и преобразуйте его в строку. Проверьте, действительно ли это программа на вашем языке. Если это не так, выберите другой номер и попробуйте снова. Если это так, запустите его, немедленно сделайте паузу и добавьте его в список приостановленных программ.

3. Запустите все приостановленные программы на некоторое время. Если какой-либо из них остановится, не найдя адекватного решения, удалите их из списка. Если кто-то найдет адекватное решение, все готово! В противном случае вернитесь к 2 после того, как дадите им всем немного поработать.

Нет сомнений в том, что если у вас бесконечное хранилище и бесконечное время, приведенный выше алгоритм в конечном итоге найдет хорошее решение. Но это, вероятно, не то, что вы подразумеваете под «машинным обучением».

Вот в чем проблема: если учесть все возможные проблемы, ни один алгоритм машинного обучения в среднем не будет лучше! Это известно как теорема об отсутствии бесплатного обеда . Это доказывает, что среди всех возможных проблем, которые вы можете бросить в любой данный алгоритм машинного обучения, число, которое он может быстро решить, исчезающе мало.

Он может быстро решить эти проблемы только потому, что они управляются шаблонами, которые алгоритм может предвидеть. Например, многие успешные алгоритмы предполагают следующее:

1. Решения могут быть описаны некоторыми сложными сериями матричных умножений и нелинейных искажений, управляемых набором параметров.

2. Хорошие решения будут сгруппированы вместе в пространстве параметров, поэтому все, что вам нужно сделать, это выбрать область поиска, найти там лучшее решение, сместить область поиска так, чтобы лучшее решение находилось в центре, и повторить.

Очевидно, что ни одно из этих предположений не выполняется в целом. Второе особенно подозрительно. И не бесплатный обед говорит нам, что эти предположения даже не держатся большую часть времени. На самом деле они почти никогда не держатся! Нам просто повезло, что они справляются с определенными проблемами, которые действительно имеют значение.

Выбранная вами проблема с самого начала предназначена для того, чтобы нарушать предположение 2. Хеш-функции специально разработаны таким образом, чтобы схожие входы давали совершенно разные выходы.

Итак, ваш вопрос - каков наилучший алгоритм машинного обучения для решения этой проблемы? - вероятно, имеет очень простой ответ: случайный поиск.

Это почти невозможно. Тем не менее, люди наблюдали некоторые паттерны в SHA256, которые могут указывать на его неслучайность . Отличитель SHA256 с использованием биткойнов (майнинг быстрее по пути) . Их тдлр:

«Чтобы различить идеальный хэш случайной перестановки и SHA256, дважды сделайте хэш большого количества (~ 2 ^ 80) возможных 1024-битных блоков, как это делается в биткойнах. Убедитесь, что биты блоков-кандидатов установлены редко (намного меньше, чем 512 означает ожидаемое), согласно протоколу Биткойн, отбрасывая блоки-кандидаты, которые не соответствуют стандарту «сложность» Биткойн (где результирующие хэши начинаются с большого числа 0.) С оставшимся набором допустимых входных кандидатов (467369, когда этот анализ был выполнен), наблюдайте за конкретным набором из 32 битов во входном блоке (расположенном там, где биткойн имеет одноразовый номер, входные биты 607-639). Обратите внимание, что среднее число битов, установленное в поле одноразового номера, смещено влево, т.е. меньше, чем ожидаемое значение из 16 установленных битов (среднее значение оценивается в 15,428). "

Смотрите обсуждение на lobste.rs . Одним из возможных объяснений является предвзятость, внесенная майнерами.

Я отвечу с помощью программы. Чтобы уменьшить вычислительные требования, я буду использовать вариант sha256, который я называю sha16, который является только первыми 16 битами 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))

Это производит вывод:

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
[...]

Я оставлю полное доказательство в качестве упражнения для читателя, но поверьте мне на слово: есть ввод, который начинается с «1» для каждого возможного дайджеста от 0000 до ffff.

Также есть ввод, который не начинается с «1». И еще один начинается с полного собрания сочинений Шекспира.

Это справедливо для любой достаточно хорошей хэш-функции, хотя моё доказательство грубой силы может оказаться невозможным в вычислительном отношении.

То, что вы описываете, это в основном атака перед изображением. Вы пытаетесь найти входные данные таким образом, чтобы при хешировании выходные данные имели какое-либо свойство, например «ведущий 1». *

Это явная цель криптографических хэшей для предотвращения таких атак перед изображением. Если вы можете сделать такую ​​атаку, мы склонны считать этот алгоритм небезопасным и прекратить его использование.

Таким образом, хотя это означает, что это не невозможно, это означает, что ваш алгоритм машинного обучения должен был бы одновременно перехитрить большую часть математиков в мире и их суперкомпьютеры. Вряд ли вы это сделаете.

Однако, если вы это сделаете, вы станете известны как кто-то, кто сломал основной криптографический алгоритм хеширования. Эта слава чего-то стоит!

^{* Технически "первая атака прообраза" пытается найти соответствие для конкретного хеша. Однако, чтобы показать, что алгоритм хеширования имеет устойчивость к первым атакам прообраза, они обычно показывают, что вы не можете найти какой-либо значимой информации о входных данных из хэша.}

Почти все ответы здесь говорят вам, почему вы не можете сделать это, но вот прямой ответ на:

Независимо от того, является ли это «возможным», какой алгоритм будет наилучшим подходом?

Предполагая, что ввод достаточно велик:

1. Взять подсчет набора допустимых символов.
2. Возьмите ответное число от шага 1.

Это вероятность того, что входная строка начинается с «1». Вам даже не нужно смотреть на вход. Если вы можете сделать это лучше, это будет означать, что хеш очень сломан. Вы можете сэкономить много циклов ЦП, пытаясь обучить алгоритм выбора случайных чисел.

Вы могли бы обучить алгоритм, и он мог бы придумать другой ответ из-за переоснащения. Это если что-то не так с алгоритмом хеширования. Использование этого алгоритма в этом случае происходит чаще, чем если бы вы просто выбирали случайное значение.

Функции хеширования специально разработаны для того, чтобы их было сложно смоделировать, поэтому (как уже отмечалось) это, вероятно, будет очень сложно. Тем не менее, любая слабость в функции хеширования уменьшит ее энтропию, сделав ее более предсказуемой.

Независимо от того, является ли это «возможным», какой алгоритм будет наилучшим подходом?

Полезным примером является Physical Unclonable Function , или PUF, которая аналогична аппаратной функции хеширования. Как правило, производственные вариации целенаправленно используются для того, чтобы дать каждому PUF немного другой отклик, так что их «хешированный» выходной сигнал различен для данного входного сигнала. Однако недостатки проектирования ограничивают энтропию, и, учитывая достаточное количество пар «вызов-ответ», часто можно построить модель «черного ящика» PUF, чтобы можно было предсказать ответ на новый, ранее невидимый вызов.

Логистическая регрессия является наиболее часто используемым подходом для этих атак моделирования, как, например, в этой статье Rührmair .

Генетические алгоритмы (или, в более общем смысле, эволюционные стратегии) ​​могут быть альтернативным подходом, поскольку они применимы к задачам, которые нельзя дифференцировать и / или линейно разделить. Они также обсуждаются в вышеприведенном документе.

$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}$

Проблема в том, что «машинное обучение» не разумно. Он просто пытается найти шаблоны. В SHA-256 нет шаблонов. Там нет ничего, чтобы найти. У машинного обучения нет шансов, что это лучше, чем грубая сила.

Если вы хотите взломать SHA-256 с помощью компьютера, единственная возможность - создать настоящий интеллект, а поскольку многие умные люди не нашли способа создать SHA-256, вам нужно создать искусственный интеллект, который намного выше, чем это из многих умных людей. В этот момент мы не знаем, взломает ли такой сверхчеловеческий интеллект SHA-256, докажет, что его нельзя взломать, или решит, что он недостаточно умен, чтобы сделать это (так же, как люди). Четвертая возможность, конечно, заключается в том, что такой сверхчеловеческий искусственный интеллект даже не беспокоит, а думает о более важных для него проблемах.