sha256 и все-все-все

Читатель тж показывает, как работают хэш-функции.

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

Не хотелось бы оставаться обижулькой в памяти этого ресурса, так что пообещал – отвечу. Когда-нибудь обязательно. Например, сейчас.

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

А вот умножение – уже нет. Скорее всего. Обратная операция умножению – факторизация, и произвести её куда сложнее, чем просто умножить два числа. Знаем исходники:

Забегая вперёд скажу, что конкретно эта необратимость, конечно, используется в криптографии. Но не в sha256. В sha256 всё гораздо тупее и примитивнее. Другой пример проблемной математической операции: обычное суммирование, но с добавлением случайного шума, известное как subset sum problem.

И снова, попробуйте сами на менее примитивном примере. Я подожду.

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

Однако, всем нам с детства интуитивно понятно, что если взять Мону Лизу:

Наложить на неё некоторое количество случайного шума:

И удалить некоторую часть информации:

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

Итак, запомнили: смешивание со случайными данными + удаление части информации даёт необратимую функцию. На этом принципе основывается не вся криптография, конечно, но основные функции хэширования в основном да. Главный вызов алгоритма – избежать коллизий, и гарантировать, что самое небольшое изменение исходного файла приведёт к существенным изменениям результата, а вовсе не обеспечение необратимости алгоритма. Вот и всё. Просто, правда?

А теперь подробнее о том, что происходит внутри собственно sha265 (да, я её лично пошёл и расковырял, потому что могу лол).

Как я сказал выше, sha256 не полагается на односторонние функции, совсем. Она гораздо более примитивна. Прям как трюк с картинкой выше, только на уровне взаимодействий между числами. Она получает на вход некоторый набор единичек и нулей (каким образом всё существующее в мире становится единицами и нулями нужно объяснять? Не думаю), и делает две вещи: смешивание со случайными данными, и отрезание некоторой части информации. Для начала смешивание.

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

Договорились использовать набор из 8 и 64 соответственно квадартных и кубических корней первых простых чисел. Легко доказать аналитически, что эти числа иррациональны, так что всё в порядке, никто тут свой секретный алгоритм или дыру не спрятал. Далее с этим ворохом чисел последовательно блоками по 512 бит смешивается наша исходная строка. Примерно вот так:

И ещё один раз в каждом раунде похожим способом. Более подробно о том, что именно происходит вплоть до уровня размещения ячеек в памяти компьютера можно посмотреть в моём же отчёте, на который я уже ссылался.

Но простая сумма обратима. Приглядитесь к формуле выше, в ней только одна неизвестная: wj, все остальные – и массив wv, и j сама по себе – константы. А значит, зная их, и зная результат (t1), простой школьной арифметикой на уровне пятого класса можно было бы вычислить и w[j], а значит весь маскарад пошёл бы на смарку. Если бы не одна вещь.

Обратите внимание на кусок SHA256_F2(...), который применяется к некоторым слагаемым нашего кода. Не важно к каким, к некоторым из них – этого вполне достаточно. Она определена в заголовочном файле, и представляет из себя несколько двоичных сдвигов подряд. Что же за двоичный сдвиг?

Грубо говоря, почти то же самое, что и механическое отрезание части числа руками. 28343 -> 283, что-то вроде того. Потеря некоторой части информации, совершить которую легко, а восстановить, что там было, можно только перебором. Как-то так выглядит настоящий двоичный сдвиг в памяти, ничего сверхъестественного:

Узнали подобие тех операций, которые мы недавно проделывали с Моной Лизой? Только повторите их ещё 64 или 80 раз, в зависимости от алгоритма, и убедитесь, что строка на выходе всегда получается одинаковой длины – получите рабочий алгоритм хэширования. Который, тем не менее, скорее всего будет никуда не годным из-за множества коллизий, но тем не менее, отлаживать, тестировать и совершенствовать – больше рабочий, чем принципиальный вопрос. Вот и всё.

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

Который можно разделить на четыре стадии. Первая не делает ничего, только загоняет константы в память и объявляет пару переменных, вторая проверяет, длиннее ли вход 64-х битов, и разбивает его на равные кусочки, если да. Третья совершает вышеперечисленные действия 64 раза подряд над каждым из кусочков до полной нечитаемости результата, и четвёртая, final, подчищает и формирует вывод, который нужно показать пользователю.

Много кода не всегда равно много смысла.

На самом деле две вещи. Пояснить за нейроночки, и за асимметричную криптографию. Про асимметричную наверное напишу, если вам будет интересно (скажите в комментариях, интересно ли, но там длиннее выйдет). Когда-нибудь. Нейроночки же это такой же модный хипстерский buzzword, как и блокчейн, скорее даже ещё более более бессмысленный и беспощадный. Передаю слово чуваку из твитора:

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

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

А, нет, не всё. Ещё одну вещь забыл.

Специально для Paul Potseluev.