Импортозамещение в I2P: подпись по ГОСТ Р 34.10-2012

    Эллиптическая криптография, обладая высокой стойкостью и широкой распространенностью, всегда вызывала много споров и спекуляций на предмет возможных закладок для разных кривых и схем подписи. При этом никто не смог привести пример подобной закладки или же доказать их отсутствие. Потому, в отличие от симметричной криптографии, где лидерство безоговорочно принадлежит AES, асимметричная криптография используется разных видов, в зависимости от предпочтений, технических или законодательных требований. Дополнительные типы подписей адресов в I2P предоставляют больший выбор и гибкость для приложений. ГОСТ поддерживается в openssl через EVP интерфейс, однако в версии 1.1 он исключен из стандартной поставки, кроме того существующая реализация предполагает хранение и передачу публичных ключей и подписей в формате DER, а I2P работает непосредственно с числами, определяя необходимые параметры из типа подписи.

    Типы подписей в I2P


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

    1. ECDSA_SHA256_P256
    2. ECDSA_SHA384_P384
    3. ECDSA_SHA512_P521
    4. RSA_SHA256_2048
    5. RSA_SHA384_3072
    6. RSA_SHA512_4096
    7. EdDSA_SHA512_Ed25519
    8. EdDSA_SHA512_Ed25519ph

    Также в старых адресах используется тип 0 — DSA_SHA1, считающийся устаревшим.
    Рекомендуется использовать типы 1 и 7.

    Для ГОСТ-а нам, по моей просьбе, выделено два типа:
    9 — GOSTR3410_GOSTR3411_256_CRYPTO_PRO_A
    10 — GOSTR3410_GOSTR3411_512_TC26_A
    для 256 и 512-битных ключей соответственно.

    Длина публичного ключа для 9 составляет 64 байта (по 32 байта на каждую координату точки) и 128 байт для 10.

    Реализация подписи ГОСТ Р 34.10


    Предполагается, что подписывается и проверяется хэш длиной 256 или 512 бит. Подробно и с примерами описан здесь.

    Используется обычная эллиптическая кривая, поэтому для работы с ней могут использоваться функции из криптографической библиотеки. В частности это EC_GROUP_* и EC_POINT_* из openssl, главная из которых это:

    int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *n, const EC_POINT *q, const BIGNUM *m, BN_CTX *ctx)
    

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

    Для кривой задаются 6 параметров: p — модуль, a и b — коэффициенты уравнения кривой, P(x,y) — базовая точка, q — простое число, умножение на которое базовой точки дает нуль.

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

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

    • GostR3410_2001_CryptoPro_A_ParamSet (OID 1.2.643.2.2.35.1) для 256-битных ключей, заимствован из ГОСТ Р 34.10-2001;
    • id-tc26-gost-3410-12-512-paramSetA (OID 1.2.643.7.1.2.1.2.1) для 512-битных ключей, разработанный ТК26(tc26.ru) специально для ГОСТ Р 34.10-2012.

    В отличие от кривой, схема подписи в ГОСТ своя, поэтому функции ECDSA_sign и ECDSA_verify использовать нельзя и следует реализовать подпись и проверку подписи в своем коде.

    Для подписи (r,s) выбирается случайное число k, и вычисляется точка R=k*P, координата x которой становится компонентой r подписи. Компонента s = r*d + h*k, где d — секретный ключ, h — хэш подписи сообщения в Big Endian.

    Для проверки подписи умножим обе части равенства на базовую точку P.

    Действительно s*P = r*d*P + h*k*P = r*Q + h*R, где Q — публичный ключ. В этом равенстве нам неизвестна точка R, и хотя можно восстановить координату y по r, это является крайне медленной операцией. Поэтому перепишем равенство в виде h*R = s*P — r*Q, далее
    R = (s*P -r *Q)/h и сравнение только координаты x.

    В коде i2pd это выглядит так
    bool GOSTR3410Curve::Verify (const EC_POINT * pub, const BIGNUM * digest, const BIGNUM * r, const BIGNUM * s)
    {
    	BN_CTX * ctx = BN_CTX_new ();
    	BN_CTX_start (ctx);
    	BIGNUM * q = BN_CTX_get (ctx);
    	EC_GROUP_get_order(m_Group, q, ctx);
    	BIGNUM * h = BN_CTX_get (ctx);
    	BN_mod (h, digest, q, ctx); // h = digest % q
    	BN_mod_inverse (h, h, q, ctx); // 1/h mod q
    	BIGNUM * z1 = BN_CTX_get (ctx);
    	BN_mod_mul (z1, s, h, q, ctx); // z1 = s/h
    	BIGNUM * z2 = BN_CTX_get (ctx);				
    	BN_sub (z2, q, r); // z2 = -r
    	BN_mod_mul (z2, z2, h, q, ctx); // z2 = -r/h
    	EC_POINT * C = EC_POINT_new (m_Group);
    	EC_POINT_mul (m_Group, C, z1, pub, z2, ctx); // z1*P + z2*pub
    	BIGNUM * x = BN_CTX_get (ctx);	
    	GetXY  (C, x, nullptr); // Cx
    	BN_mod (x, x, q, ctx); // Cx % q
    	bool ret = !BN_cmp (x, r); // Cx = r ?
    	EC_POINT_free (C);
    	BN_CTX_end (ctx);
    	BN_CTX_free (ctx);
    	return ret;
    }	
    


    Хэш функция ГОСТ Р 34.11-2012(стрибог)


    Хотя для подписи сообщения можно использовать любую функцию, вычисляющую хэш подходящего размера, например SHA256/SHA512, мы будем использовать предписываемый стандартом ГОСТ Р 34.11-2012, в том числе и для совместимости с существующими реализациями. В отличие от подписи, хэш устроен много проще.

    Подробное описание и примеры. Отметим основные моменты:

    • Исходное сообщение разбивается на блоки по 64 байта. Если не сообщение не кратно 64, то первый блок дополняется слева нулевыми и единичным байтами.
    • Каждый блок хэшируется отдельно с учетом хэша предыдущего блока. Для самого первого блока в качестве предыдущего хэша задается вектор инциализации(iv). Проход по блокам осуществляется в обратном порядке — от последнего к первому.
    • Каждый блок «шифруется» 12 раундов заданными ключами, каждый раунд представляет собой применение трех преобразований S, P, L с использованием заданных таблиц и XOR с раундовым ключом.
    • S представляет собой побайтную замену, P — транспонирование хэша как матрицы 8x8, L — умножение на заданную матрицу.
    • 256-битный хэш представляет собой левую половину 512-битного хэша, однако используется другой iv, поэтому вычислять их одновременно не получится.

    Подпись внешним криптопровайдером по протоколу I2CP


    Если адрес подключается к маршрутизатору по протоколу I2CP, то знание секретного ключа подписи маршрутизатором не требуется.

    Вместо этого маршрутизатор отправляет сообщение RequestLeaseSetMessage (или RequestVariableLeaseSetMessage), ожидая в ответ сообщение CreateLeaseSetMessage, содержащее LeaseSet, подписанный секретным ключом адреса. Как можно заметить из описания протокола, в старых версиях I2P требовалось передавать этот ключ в сообщении, больше этого не требуется.
    Таким образом, приложение, реализующее I2P адрес, может использовать для подписи API одного из существующих криптопровайдеров с ГОСТ, позволяя эффективно встроить I2P решение в существующую инфраструктуру.

    Реализация


    В настоящее время i2pd полностью поддерживает типы подписи 9 и 10. Любые клиентские адреса будут работать с адресами на i2pd. Пример использования. Для работы серверных адресов требуется поддержка со стороны floodfill-ов, либо может быть построенна независимая от основной I2P сеть с netid, отличным от 2. В основной же сети требуется ждать, когда это будет реализовано в джаве или дополнительный параметр floodfill-ов.
    Метки:
    • +17
    • 5,3k
    • 7
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 7
    • +1

      Красиво. Но дополнительный хаб "Ненормальное программирование" был бы тут не лишним.

      • 0
        «Каждый блок хэшируется отдельно с учетом хэша предыдущего блока. Для самого первого блока в качестве предыдущего хэша задается вектор инциализации(iv). Проход по блокам осуществляется в обратном порядке — от последнего к первому» — ФЕЙЛ!
        https://habrahabr.ru/post/273055/
        читайте мои комменты.
        Проход по блокам всегда от начала, даже чисто логически хэш функция которой данные нужно подавать с конца никому нафик не сдалась.
        • –2
          Я все таки лучше почитаю стандарт, в которым черным по белому написано «вычислить подвектор m сообщения M=M'||m». И все реализации (возможно кроме вашей) идут в обратном порядке.
          • 0
            Ivan_83 всё же прав. Как минимум, это было бы просто не логично: хэш который считается над данными в обратном порядке никому не нужен, так как это бы банально бы не позволило потоково обрабатывать данные. 34.11-2012 есть в https://tools.ietf.org/html/rfc6986.html#section-10 где в примерах показано как его надо высчитывать. Сбивает с толку то, что авторы любят записывать *примеры* в обратном порядке. Все использующиеся в «бою», на практике реализации делают как описал Ivan_83.
            • 0
              КриптоПро, однако, придерживается иного мнения, и вычисляет именно так, как описано в стандарте.
              В этом легко убедиться, воспользовавшись их утилитой для файла с примером.
              • 0
                Хм, я возможно тогда не так понял Ivan_83. КриптоПро утилитка которую вы показали делает хэши точно так же как вот например (я просто их автор) http://pygost.cypherpunks.ru/ и http://gogost.cypherpunks.ru/. То есть, с моей точки зрения — всё правильно, как и ожидалось. Если у вас всё так же как и у ней — то и у вас всё правильно. Просто ещё и взглянул на ваш C++ код в котором для 256-бит версии Стрибога делается memcpy — я не C программист и подумал что «отрезаются» первые 32 байта от хэша и это становится возвращаемым значением функции. Или я не так понял memcpy или ещё где-то что-то «крутится», но КриптоПро утилита действительно верна.
                • 0
                  Вся соль в том, что можно вычислять с зада на перёд, переворачивая всё и в итоге получить тоже самое, насколько я помню.
                  Но это как минимум медленно (префетчи то обычно вперёд читают в железе), и крайне не практично: нельзя принимать поток и одновременно считать его хэш.
                  А можно взять и сделать правильно.
                  Я же вам написал, там выложена реализация Дегтярева, он один из авторов этого несчастного хэша с дважды поксроренным счётчиком. У него всё считается с переда к заду, как во всём нормальном мире.
                  Если вы потрудитесь найти то там были именно файлы которые входили в примеры и именно от них стоит отталкиваться, а то во всяких стандартах оно то перевёрнутое то нет. Хотя то что лежит на ТК26 за авторством ТК обычно нормальное.
                  У меня в исходнике есть линки на все источники проверочных векторов, на случай если лень искать.

                  Можете libressl заглянуть, там оно есть.
                  А лучше выкиньте из своего проекта OpenSSL и юзайте libressl, там сразу все госты прямо в коробке есть.

                  И последнее, если так любите криптопро можете натравить на неё процесс монитор а саму утилиту на большой файл и сами увидите в каком направлении она читает.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.