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

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

Необратимость — по выходному значению практически невозможно восстановить исходные данные.
Псевдослучайность — выход кажется случайным, даже если вход известен.

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

Как отмечает профессор Ран Канетти (Бостонский университет), «сегодня трудно найти криптографическое приложение, в анализе безопасности которого не использовалась бы модель случайного оракула».

Однако новая работа группы исследователей — Дмитрия Ховратовича (Ethereum Foundation), Рона Ротблума (Succinct, Технион) и Льва Суханова ([[alloc] init]) — поставила под сомнение устойчивость этого подхода. Учёные показали, что даже в системах доказательств с нулевым разглашением, широко применяемых в блокчейнах, возможно создать ложные утверждения, которые проходят проверку, несмотря на формальное соблюдение модели.

Эйлон Йогев (Университет Бар-Илан) прокомментировал это так: «В блокчейн-среде у злоумышленников есть мощный стимул нарушать безопасность — это может принести реальную финансовую выгоду». Новые результаты показывают, что даже проверенные схемы могут быть уязвимы, если модель случайности в их основе не соответствует реальности. Йогев отметил: «У меня было ощущение, будто у меня выдернули ковёр из-под ног».

Преобразование Фиата — Шамира

Одним из краеугольных методов современных доказательств корректности вычислений является преобразование Фиата — Шамира. Оно позволяет превратить интерактивное доказательство — с чередованием вопросов и ответов — в неинтерактивное, где доказывающая сторона самостоятельно формирует доказательство, а проверяющий может в любой момент убедиться в его корректности.

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

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

Простая аналогия

Представим, что студенту выдали 100 задач, и преподаватель, стремясь упростить проверку, выбирает для анализа только 10 из них. Если ответы на выбранные задания оказываются правильными, можно с высокой вероятностью предположить, что и остальные решены верно. Такой подход — основанный на выборочной проверке — интуитивно ясен в очной ситуации. Однако в распределённой вычислительной среде, например в блокчейне, прямого взаимодействия между доказывающей и проверяющей сторонами не происходит. Поэтому механизм выбора должен быть детерминированным, проверяемым и неподконтрольным самому исполнителю.

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

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

В совокупности эти принципы и легли в основу преобразования Фиата — Шамира, которое стало поворотным моментом в развитии неинтерактивной криптографии. Благодаря ему доказывающая сторона может самостоятельно сформировать доказательство, верифицируемое любым участником системы без необходимости взаимодействия. Такой подход особенно важен для современных криптографических протоколов, включая zk-SNARKs и STARKs, где требуется проверка корректности сложных вычислений без раскрытия данных и при высокой вычислительной эффективности.

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

Переломный момент

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

В начале 2000-х теоретики разработали специальные доказательства, которые теряли безопасность при переходе к неинтерактивной форме. Но, по словам Канетти, «никто в здравом уме не стал бы разрабатывать протокол таким образом». Поэтому сообщество продолжало использовать схему Фиата — Шамира как практический стандарт, руководствуясь «прыжком веры».

Рон Ротблюм вместе с Дмитрием Ховратовичем и Львом Сухановым перевернули устоявшиеся представления о фундаментальном методе доказательства.

Однако Рон Ротблум не разделял этого оптимизма. Он долгие годы пытался найти пример реального протокола, который можно взломать. И в октябре прошлого года получил письмо от Ethereum Foundation — организации, занимающейся развитием блокчейн-платформы. Речь шла о потенциальной уязвимости.

Цепочка атаки

Ethereum Foundation инициировала открытый вызов: любому, кто найдёт атаку на протокол доказательства, использующий схему Фиата — Шамира с хеш-функцией Poseidon, обещано вознаграждение. Перед публикацией черновика фонд обратился к Ротблуму за рецензией.

Он указал, что формулировка задания чересчур общая, и был удивлён тем, что разработчики Ethereum не знали о более ранних теоретических атаках. В результате Ротблум начал сотрудничать с Ховратовичем и Сухановым. Последний предложил атаковать реализацию, основанную на протоколе GKR (Goldwasser–Kalai–Rothblum), соавтором которого является брат Рота — Гай Ротблум.

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

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

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

Джастин Талер (Джорджтаунский университет, Andreessen Horowitz) назвал результат «поразительным — с этим согласны многие».

Реакция индустрии

Компания Polyhedra, развивающая систему Expander — реализацию, основанную на уязвимом протоколе, — была заранее уведомлена об исследовании. Вместе с публикацией учёные предложили модификацию схемы Фиата — Шамира, и Polyhedra оперативно внедрила патч.

Когда Эйлон Йогев услышал о новой статье, он сказал: «У меня было ощущение, что кто-то выбивает почву у меня из-под ног».

Позднее Эйлон Йогев и Галь Арнон (Институт теории вычислений Саймонса) предложили альтернативную защиту: требовать, чтобы проверяемая программа была менее сложной, чем хеш-функция, и не могла её встраивать. Это разрывает рекурсивную зависимость и препятствует атаке. «Это позволило нам разорвать порочный круг», — отметил Йогев.

Но, как подчёркивает Ротблум, это не универсальное решение: «Тот факт, что текущая атака не работает, не означает, что нет других. Это расстраивает нас как криптографов».

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

Канетти настроен жёстче: сложный код, портируемый на разные системы, трудно проверить, и это даёт пространство для внедрения уязвимостей. «Я думаю, это действительно серьёзная атака», — сказал он.

Йогев поддерживает: «Если вы находите дыру, вы понимаете, что лодка уже даёт течь. Я не думаю, что это локальная проблема — при желании её можно было бы использовать для хищения средств».

Даже если практических атак не последует, доверие к самой модели случайного оракула и к преобразованию Фиата — Шамира оказалось подорвано. «Возможно, пришло время переосмыслить многое из того, что мы считали доказанным», — заключает Канетти.

Всё это и много другое — ТГ «Математика не для всех»
Взгляд на философию со стороны разочарованного технаря ТГ "Философия не для всех"

Как информатики научились разоблачать ложь