автор: Йохан

фон

Уязвимость Frozen Heart «Bingxin» была названа командой Trail of Bits, где Frozen означает создание доказательств с нулевым знанием, а Heart относится к трансформации Фиата-Шамира, которая является ядром многих систем доказательств. Эта уязвимость относится к проблеме безопасности, которая возникает, когда применяется «слабое преобразование Фиата-Шамира», которое хэширует только часть сообщения проверяющего без хеширования общедоступной информации (например, параметров, общедоступных входных данных и т. д.).

Ниже мы проведем комплексный анализ этой уязвимости.Давайте сначала поговорим о том, что такое трансформация Фиат-Шамир.

Фиат-Шамир Трансформация

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

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

Интерактивные доказательства Шнорра можно преобразовать в неинтерактивные с помощью преобразования Фиата-Шамира.

Шнорра можно реализовать на конечных полях или эллиптических кривых (EC). Технические характеристики в основном те же, отличается только базовая циклическая группа. Ниже мы в основном описываем эти два процесса в виде конечных полей [1]:

* Описание символа:

  • Алиса: Предполагаемая личность доказывающего в протоколе.

  • Боб: Предполагаемая личность валидатора в протоколе.

  • а | б: а делит б

  • а || б: связь между а и б

  • [a, b]: диапазон целых чисел, включая a и b

  • t: количество битов в вызове, выбранном Бобом.

  • H: Безопасная криптографическая хеш-функция.

  • p: большое простое число

  • q: большой простой делитель p-1, то есть q |

  • Zp*: мультипликативная группа целых чисел по модулю p

  • Gq: подгруппа Zp* простого порядка q

  • г: генератор Gq

  • g^d: g возведено в степень d

  • а по модулю b: а по модулю b

  • Fp: конечное поле из p элементов, где p — простое число.

Реализация на основе конечных полей

1. Интерактивный

Сначала Алиса вычисляет A = g^a mod p, где закрытый ключ a принимает значение [0, q-1], а затем раскрывает открытый ключ A;

Затем Алиса доказывает Бобу, что она знает закрытый ключ a, соответствующий A, не раскрывая a:

Если проверка верна, то можно доказать, что Алиса знает a. Принцип следующий:

Причина, по которой Бобу здесь необходимо сгенерировать случайное значение c, заключается в том, что если злоумышленник знает это значение до раскрытия A, то он может подделать доказательство, не зная реального значения a. Злоумышленник подделывает (A, V, r) следующим образом:

1) Сгенерировать случайное значение r

2) Метод расчета V остается неизменным, пусть

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

Неинтерактивное преобразование также очень просто. На основе интерактивного измените процесс Боба случайной генерации c на хэш-форму параметров:

Реализация на основе эллиптических кривых

Сначала Алиса вычисляет A = G x [a], где закрытый ключ a принимает значение [0, n-1], а затем раскрывает открытый ключ A;

Затем Алиса доказывает Бобу, что она знает закрытый ключ a, соответствующий A, не раскрывая a:

Если проверка верна, то можно доказать, что Алиса знает a. Принцип следующий:

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

Слабое преобразование Фиата-Шамира

В приведенном выше процессе неинтерактивной реализации случайные числа:

Это правильный и безопасный способ генерации, но, к сожалению, в некоторых ранних работах этот процесс не описывался строго, а просто описывался как:

Существует проблема безопасности, мы называем ее слабым преобразованием Фиата-Шамира, которое можно использовать для подделки доказательства и обмана проверяющего путем предварительного вычисления A.

Восстановите параметры (A, r), используя:

1. Генерация случайного значения

2. Рассчитаем a=(v-r)/c, метод расчета остается неизменным.

3. Расчет

Мы видим, что A становится параметром, который не имеет ничего общего с a и подставляется в уравнение проверки:

может быть равен В.

Это означает, что злоумышленник может пройти проверку протокола, не зная секретного значения.

Есть также несколько работ [3], описывающих этот процесс следующим образом:

Выраженное содержание одно и то же.

Бинсинь лазейка

Команда Trail of Bits опубликовала статью [2], в которой указано, что реализация Fiat-Sharmir в системах ZKP, таких как Bulletproofs и Plonk, имеет уязвимости, позволяющие злоумышленникам подделывать доказательства случайных утверждений.

На примере Plonk алгоритм Фиата-Шамира используется для генерации случайных чисел в раундах 2, 3, 4 и 5, генерируемых доказательством.

В статье [3] были исследованы многие реализации современных систем доказательства с нулевым разглашением с открытым исходным кодом и обнаружено, что 36 из них использовали слабые преобразования Фиата-Шамира, включая Bulletproofs, Plonk, Spartan и VDF Весоловского и т. д. Злоумышленник может создать доказательство, которое пройдет проверку, не зная действительного секрета доказательства.

Пример уязвимости

1. раздражать

Здесь fs — это экземпляр вычисления Фиата-Шамира. Когда доказательство Round2 вычисляет параметр z(X), информация доказательства может быть подделана, поскольку общедоступный ввод не связан с задачей.

2. снаркджс

Кроме того, поскольку publicSignals не включен, сертификационную информацию можно подделать.

Подведем итог

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

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

Справочные документы:

[1]. https://datatracker.ietf.org/doc/html/rfc8235

[2]. https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/

[3]. https://eprint.iacr.org/2023/691.pdf