Новости Аудит кода Bulletproofs+ от JP Aumasson

Тема в разделе "Новости", создана пользователем Mr. Pickles, 6 апр 2021.

  1. Mr. Pickles

    Команда форума Модератор Редактор

    Регистрация:
    11 сен 2017
    Сообщения:
    891
    Симпатии:
    242
    Содержание

    1 Введение

    1.1 Область применения

    1.2 Аннотация

    2 Наблюдения (вопросы, не связанные с безопасностью)

    2.1 Как избежать утечки неправильного индекса доказательства со временем?

    2.2 Добавление проверок согласованности maxN

    2.3 Исключение лишней ненулевой проверки

    2.4 Исключение сравнения жёстко закодированных значений

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

    2.6 Обнаружение сбоев программного обеспечения по отказам при статистически маловероятных событиях

    1.1 Введение
    Проектом Monero были запрошены наши услуги для проверки безопасности реализации системы доказательства диапазона Bulletproofs+ (BP+), интегрированной в Monero с целью уменьшения размера и повышения скорости создания транзакций.

    Первый аудит, проведённый zenGo X, охватывал протокол, точность реализации и в некоторой степени безопасность кода.

    Основной целью этого нового аудита является проверка безопасности кода и возможности злоупотребления им или его неправильного использования в контексте Monero. Этот аудит меньше по объёму, чем предыдущий (на него ушло 5 дней, в то время как на предшествующий — 40), и он дополняет собой исследования, проведённые ZenGo.

    Нами были рассмотрены следующие аспекты реализации BP+:
    • валидация входов при доказательстве и верификации;
    • риск злоупотребления криптографической логикой;
    • возможность реализации подобных DoS сценариев (бесконечных циклов и т. д.);
    • наличие в программном обеспечении ошибок, угрожающих безопасности BP+;
    • слабый набор параметров сценариев использования;
    • возможность злоупотребления групповой/агрегированной проверкой;
    • небезопасная или недостаточная обработка ошибок;
    • безопасность примитивов и параметров;
    • надёжность зависимостей;
    • общее обеспечение безопасности.
    1.1 Область применения

    Нами был проверен код, содержащийся в коммите 0c6dfc9 (11 февраля, 21), при этом особое внимание уделялось файлам
    • src/ringct/bulletproofs_plus.h
    • src/ringct/bulletproofs_plus.h
    и использованию тестовых программ из test/unit_tests/bulletproofs_plus.cpp при тестировании различных сценариев использования.

    Вот основные функции (на обзор и тестирование которых мы потратили больше всего времени):
    • bulletproof_plus_PROVE(const rct::keyV &sv, const rct::keyV &gamma)
    • bulletproof_plus_VERIFY(const std::vector<const BulletproofPlus*> &proofs)
    Мы также рассмотрели вспомогательные арифметические функции возведения в степень, инициализации показателей, внутреннего произведения, векторных операций, суммы степеней и т. д. Эти (статические) функции были оценены с точки зрения правильности и относительно предварительных условий, определяемых теми, кто их вызывает. Таким образом, они не оценивались в условиях, когда злоумышленник все возможности для произвольного ввода искаженных данных.

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

    Наконец, мы рассмотрели изменения, связанные с полной интеграцией кода в Monero, произведённые в отдельном PR. Мы считаем, что эти изменения не ставят под угрозу безопасность реализации BP+ и не расширяют поверхность атаки в большей мере, чем это необходимо.

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

    Отсутствие обнаруженных ошибок не означает их полное отсутствие, а просто снижает такую вероятность. Мы могли пропустить некоторые ошибки из-за отсутствия знаний об определенных классах атак, из-за недостаточного тестирования или из-за неправильного понимания BP+ или логики кода.

    Тем не менее, мы считаем, что достаточно хорошо поняли логику BP+ и механизма её реализации, в частности, благодаря результатам предварительного исследования, изложенным в отчёте ZenGo X, где была задокументирована роль каждой переменной относительно спецификации BP+. (Следует отметить, что нами не было замечено ошибок в описании кода, выполненном ZenGo X, и мы вполне уверены в его точности.)

    Обратите внимание, что мы рассмотрели безопасность реализации в контексте использования кода в Monero с заданными жёстко закодированными параметрами. При необходимости нами анализировалась часть внутренних зависимостей (например, генерация случайных объектов и множественное возведение в степень), где мы не заметили ничего страшного.

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

    Мы хотели бы выразить свою благодарность сообществу Monero за вновь оказанное нам доверие.

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

    2.1 Как избежать утечки неправильного индекса доказательства со временем?
    Пакетная верификация в конечном счёте запускает агрегированную проверку с использованием (по алгоритму Пиппенгера) множественного возведения в степень. Однако, если доказательство искажено, выполнение алгоритма верификации будет прервано напрямую при циклическом просмотре всех доказательств. Таким образом напрямую путём измерения времени раскрывается индекс неверного доказательства.

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

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

    Подобным образом функция доказательства может привести к раскрытию индекса недействительного элемента в sv или gamma.

    2.2 Добавление проверок согласованности maxN
    Пространство имён rct объявляет

    static constexpr size_t maxN = 64; // maximum number of bits in range

    а затем в зависимости от этого значения статически выделяются некоторые массивы. Тем не менее, в функции доказательства maxN не используется, а заявляется локальная переменная logN, которой присваивается значение 6:
    Код:
    // Useful proof bounds
    //
    // N: number of bits in each range (here, 64)
    // logN: base-2 logarithm
    // M: first power of 2 greater than or equal to the number of range proofs to aggregate
    // logM: base-2 logarithm
    constexpr size_t logN = 6; // log2(64)
    constexpr size_t N = 1<<logN;
    size_t M, logM;
    for (logM = 0; (M = 1<<logM) <= maxM && M < sv.size(); ++logM);
    CHECK_AND_ASSERT_THROW_MES(M <= maxM, "sv/gamma are too large");
    const size_t logMN = logM + logN;
    const size_t MN = M * N;
    Если переменная logN не соответствует maxN, всё будет работать неправильно. Это маловероятно, поскольку оба значения жёстко закодированы, но если в результате модификации одно значение будет изменено независимо от другого, мы рекомендуем произвести проверку согласованности на предмет соответствия maxN переменной logN.

    То же относится и к функции верификации.

    2.3 Исключение лишней ненулевой проверки
    При верификации:
    Код:
    // Random weighting factor must be nonzero, which is exceptionally unlikely!
    rct::key weight = ZERO;
    while (weight == ZERO)
    {
    weight = rct::skGen();
    }
    В этой проверке нет необходимости, поскольку rct::skGen() гарантирует наличие ненулевого входа, поскольку он проходит через sc_isnonzero().

    2.4 Исключение сравнения жёстко закодированных значений

    При проведении множественного возведения в степень происходит сравнение значения 232 со значением STRAUS_SIZE_LIMIT, которое также равно 232. Поэтому данное сравнение, по сути, не нужно (и, вероятно, оптимизировано компилятором):
    Код:
    static inline rct::key multiexp(const std::vector<MultiexpData> &data, size_t HiGi_size)
    {
    if (HiGi_size > 0)
    {
    static_assert(232 <= STRAUS_SIZE_LIMIT, "Straus in precalc mode can only be calculated \
    till STRAUS_SIZE_LIMIT");
    return HiGi_size <= 232 && data.size() == HiGi_size ? straus(data, straus_HiGi_cache, 0) : pippenger(data, pippenger_HiGi_cache, HiGi_size, get_pippenger_c(data.size()));
    }
    2.5 Сохранение результатов вычислений путём раннего прерывания при наличии слишком большого доказательства
    При верификации проверка максимальной длины доказательства выполняется единожды после предварительной обработки всех доказательств:
    Код:
    for (const BulletproofPlus *p: proofs)
    {
    (...)
    }
    CHECK_AND_ASSERT_MES(max_length < 32, false, "At least one proof is too large");
    Проверка каждого доказательства во время прохождения цикла позволит сэкономить на некоторых вычислениях (но позволит при этом выявить ошибочный индекс доказательства при помощи временных измерений).

    2.6 Обнаружение сбоев программного обеспечения по отказам при статистически маловероятных событиях

    Хеш транскрипта по нулевому скаляру проверяется в рамках процедуры доказательства, например, в следующих строках:
    Код:
    rct::key y = transcript_update(transcript, A);
    if (y == rct::zero())
    {
    MINFO("y is 0, trying again");
    goto try_again;
    }
    rct::key z = transcript = rct::hash_to_scalar(y);
    if (z == rct::zero())
    {
    MINFO("z is 0, trying again");
    goto try_again;
    }
    При обнаружении нулевого значения операция повторяется.

    Однако, ошибка выполнения (то есть, наличие нулевого значения) с большей вероятностью будет вызвана каким-либо программным сбоем, чем фактическим достижением нулевого значения (что составляет вероятность около 2 из 252 на один тест).

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

    ---

    Источник: Audit of Bulletproofs+ code by JP Aumasson

    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
    #1 Mr. Pickles, 6 апр 2021
    Последнее редактирование: 6 апр 2021
  • О нас

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