[oss-gost-crypto] EC-RDSA and a key substitution attack

[oss-gost-crypto] EC-RDSA and a key substitution attack

[Vitaly Chikunov]

Hi,

В превью к ISO/IEC 14888-3:2018 сказано 

  https://www.iso.org/obp/ui/#!iso:std:76382:en

  "NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
  vulnerable to a key substitution attack[10]. The attack is realized if
  an adversary can find two distinct public keys and one signature such
  that the signature is valid for both public keys. There are several
  approaches of avoiding this attack and its possible impact on the
  security of a cryptographic system. For example, the public key
  corresponding to the private signing key can be added into the message
  to be signed."

Где EC-RDSA это ГОСТ Р 34.10-2001 (а значит и 34.10-2012).

На сколько эта атака актуальна для ГОСТа или это очередной наговор на
российскую криптографию в стиле Н. Куртуа?

Добавить signing key к message не сложно, но я исхожу из того, что этого
делать не надо, так как в ГОСТе такого нет. Но если бы был
рекомендованный метод формирования подписи с учетом этой атаки, то
другое дело.

Re: [oss-gost-crypto] EC-RDSA and a key substitution attack

[Vitaly Chikunov]

On Tue, Dec 04, 2018 at 10:02:14AM +0300, Dmitry Belyavsky wrote:
>    А просто EC-DSA в данном контексте что?

Это американский ECDSA (FIPS 186-2, ANSI X9.62, ISO/IEC 15946-2).


> 
>    On Tue, Dec 4, 2018 at 9:54 AM Vitaly Chikunov <[1]vt@altlinux.org>
>    wrote:
> 
>      Hi,
>      В превью к ISO/IEC 14888-3:2018 сказано
>        [2]https://www.iso.org/obp/ui/#!iso:std:76382:en
>        "NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA
>      may be
>        vulnerable to a key substitution attack[10]. The attack is
>      realized if
>        an adversary can find two distinct public keys and one signature
>      such
>        that the signature is valid for both public keys. There are
>      several
>        approaches of avoiding this attack and its possible impact on the
>        security of a cryptographic system. For example, the public key
>        corresponding to the private signing key can be added into the
>      message
>        to be signed."
>      Где EC-RDSA это ГОСТ Р 34.10-2001 (а значит и 34.10-2012).
>      На сколько эта атака актуальна для ГОСТа или это очередной наговор
>      на
>      российскую криптографию в стиле Н. Куртуа?
>      Добавить signing key к message не сложно, но я исхожу из того, что
>      этого
>      делать не надо, так как в ГОСТе такого нет. Но если бы был
>      рекомендованный метод формирования подписи с учетом этой атаки, то
>      другое дело.
>      _______________________________________________
>      oss-gost-crypto mailing list
>      [3]oss-gost-crypto@lists.altlinux.org
>      [4]https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
> 
>    --
> 
>    SY, Dmitry Belyavsky
> 
> References
> 
>    1. mailto:vt@altlinux.org
>    2. https://www.iso.org/obp/ui/#!iso:std:76382:en
>    3. mailto:oss-gost-crypto@lists.altlinux.org
>    4. https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto

> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto@lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto

Re: [oss-gost-crypto] EC-RDSA and a key substitution attack

[Paul Wolneykien]

04.12.2018 09:54, Vitaly Chikunov пишет:
> Hi,
> 
> В превью к ISO/IEC 14888-3:2018 сказано 
> 
>   https://www.iso.org/obp/ui/#!iso:std:76382:en
> 
>   "NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
>   vulnerable to a key substitution attack[10]. The attack is realized if
>   an adversary can find two distinct public keys and one signature such
>   that the signature is valid for both public keys. There are several
>   approaches of avoiding this attack and its possible impact on the
>   security of a cryptographic system. For example, the public key
>   corresponding to the private signing key can be added into the message
>   to be signed."
> 
> Где EC-RDSA это ГОСТ Р 34.10-2001 (а значит и 34.10-2012).
> 
> На сколько эта атака актуальна для ГОСТа или это очередной наговор на
> российскую криптографию в стиле Н. Куртуа?

  Очень похоже. Не сказано, какова вероятность нахождения второго
подходящего ключа и какие условия поиска имеются в виду.

> Добавить signing key к message не сложно, но я исхожу из того, что этого
> делать не надо, так как в ГОСТе такого нет. Но если бы был
> рекомендованный метод формирования подписи с учетом этой атаки, то
> другое дело.
> 
> 
> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto@lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
> 

Re: [oss-gost-crypto] EC-RDSA and a key substitution attack

[Дмитрий Державин]

Вт, 04 дек 2018, 09:54, Vitaly Chikunov:

>   NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
>   vulnerable to a key substitution attack[10]. […]
>
> Где EC-RDSA это ГОСТ Р 34.10-2001 (а значит и 34.10-2012).
>
> На сколько эта атака актуальна для ГОСТа или это очередной наговор на
> российскую криптографию в стиле Н. Куртуа?

Вопрос неоднократно обсуждался. Например, по-моему, тут:
https://events.yandex.ru/lib/talks/2970/

> Добавить signing key к message не сложно, но я исхожу из того, что
> этого делать не надо, так как в ГОСТе такого нет. Но если бы был
> рекомендованный метод формирования подписи с учетом этой атаки, то
> другое дело.

В общем, это, видимо, и есть рекомендованный метод. Спросил у Смышляева,
вот что он ответил:

«Да, это известное свойство схем на основе конструкции Эль-Гамаля, в
т.ч. нашего ГОСТ Р 34.10.

В российской литературе иногда встречается как "атака Грунтовича".
http://itsec.ru/articles2/crypto/sertifitsirovannye-skzi-chto-nuzhno-znat--chtoby-pravilno-ih-vybrat

Фактически при использовании на практике ландшафт для проведения атаки
создать не удастся по следующим причинам:

1) Сертифицированные СКЗИ не дают возможности через API фиксировать
значение закрытого ключа, он создается только с помощью встроенных
ДСЧ. Хотя, конечно, под отладчиком нарушитель вполне может это обойти.

2) Электронная подпись имеет смысл в документообороте только как ЭП,
формируемая на ключах, на открытые компоненты которых выданы
сертификаты в УЦ (аккредитованном в случае квалифицированной ЭП или УЦ
с внутренним регламентом в случае, например, внутренней подписи в
банке). А УЦ как правило работают по схеме, предполагающей генерацию
ключа на АРМе на территории самого УЦ.

3) На практике в документообороте ЭП применяется не абы как, а в
форматах CAdES, PAdES и пр. - расширенных форматах, предоставляющих
информацию о сертификатах.

4) Массово распространяемая сейчас облачная подпись (см. КриптоПро DSS
или SafeTech myDSS) - средство, которое гарантировано устраняет эту
проблему, так как ключи генерятся в HSM и не извлекаются из него.

Конечно, при всем при этом сама реализация примитива остается как бы
без мер защиты против такого рода атак. Но и применяют ее не в чистом
виде, а в системах. Собственно, защита против подобных атак на систему
и является одним из вопросов, рассматриваемых в процессе сертификации
СКЗИ (с прикладными компонентами) и контроля встраивания в ФСБ России.

Защищаться от этого на нижнем уровне, вводя некий самописный формат
(при том, что и так есть упомянутые выше CAdES и прочие, защищающие от
такой атаки и подобных ей) полагаю малоосмысленным.»

От себя добавлю, что вариант «2» с генерацией ключа в УЦ выглядит,
по-моему, просто ужасно. В отличие от «3». Кстати, CADES мы умеем
генерировать. Ну почти умеем. ;)

-- 
Дмитрий Державин,
BaseALT/Базальт СПО

Re: [oss-gost-crypto] EC-RDSA and a key substitution attack

[Vitaly Chikunov]

Дмитрий,

Большое спасибо за подробную информацию!

Виталий,

On Wed, Dec 05, 2018 at 10:35:05AM +0300, Дмитрий Державин wrote:
> Вт, 04 дек 2018, 09:54, Vitaly Chikunov:
> 
> >   NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
> >   vulnerable to a key substitution attack[10]. […]
> >
> > Где EC-RDSA это ГОСТ Р 34.10-2001 (а значит и 34.10-2012).
> >
> > На сколько эта атака актуальна для ГОСТа или это очередной наговор на
> > российскую криптографию в стиле Н. Куртуа?
> 
> Вопрос неоднократно обсуждался. Например, по-моему, тут:
> https://events.yandex.ru/lib/talks/2970/
> 
> > Добавить signing key к message не сложно, но я исхожу из того, что
> > этого делать не надо, так как в ГОСТе такого нет. Но если бы был
> > рекомендованный метод формирования подписи с учетом этой атаки, то
> > другое дело.
> 
> В общем, это, видимо, и есть рекомендованный метод. Спросил у Смышляева,
> вот что он ответил:
> 
> «Да, это известное свойство схем на основе конструкции Эль-Гамаля, в
> т.ч. нашего ГОСТ Р 34.10.
> 
> В российской литературе иногда встречается как "атака Грунтовича".
> http://itsec.ru/articles2/crypto/sertifitsirovannye-skzi-chto-nuzhno-znat--chtoby-pravilno-ih-vybrat
> 
> Фактически при использовании на практике ландшафт для проведения атаки
> создать не удастся по следующим причинам:
> 
> 1) Сертифицированные СКЗИ не дают возможности через API фиксировать
> значение закрытого ключа, он создается только с помощью встроенных
> ДСЧ. Хотя, конечно, под отладчиком нарушитель вполне может это обойти.
> 
> 2) Электронная подпись имеет смысл в документообороте только как ЭП,
> формируемая на ключах, на открытые компоненты которых выданы
> сертификаты в УЦ (аккредитованном в случае квалифицированной ЭП или УЦ
> с внутренним регламентом в случае, например, внутренней подписи в
> банке). А УЦ как правило работают по схеме, предполагающей генерацию
> ключа на АРМе на территории самого УЦ.
> 
> 3) На практике в документообороте ЭП применяется не абы как, а в
> форматах CAdES, PAdES и пр. - расширенных форматах, предоставляющих
> информацию о сертификатах.
> 
> 4) Массово распространяемая сейчас облачная подпись (см. КриптоПро DSS
> или SafeTech myDSS) - средство, которое гарантировано устраняет эту
> проблему, так как ключи генерятся в HSM и не извлекаются из него.
> 
> Конечно, при всем при этом сама реализация примитива остается как бы
> без мер защиты против такого рода атак. Но и применяют ее не в чистом
> виде, а в системах. Собственно, защита против подобных атак на систему
> и является одним из вопросов, рассматриваемых в процессе сертификации
> СКЗИ (с прикладными компонентами) и контроля встраивания в ФСБ России.
> 
> Защищаться от этого на нижнем уровне, вводя некий самописный формат
> (при том, что и так есть упомянутые выше CAdES и прочие, защищающие от
> такой атаки и подобных ей) полагаю малоосмысленным.»
> 
> От себя добавлю, что вариант «2» с генерацией ключа в УЦ выглядит,
> по-моему, просто ужасно. В отличие от «3». Кстати, CADES мы умеем
> генерировать. Ну почти умеем. ;)
> 
> -- 
> Дмитрий Державин,
> BaseALT/Базальт СПО
> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto@lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto

Re: [oss-gost-crypto] EC-RDSA and a key substitution attack

[Дмитрий Державин]

Ср, 05 дек 2018, 10:35, Дмитрий Державин:

>>   NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
>>   vulnerable to a key substitution attack[10]. […]

[…]

> Вопрос неоднократно обсуждался. […]

Вдогонку — статья Николаева, в которой тема раскрыта очень подробно:
http://www.mathnet.ru/links/b6caaa0250ad0cebf13bad371799b3b2/mvk177.pdf

Комментарий автора:

«В списке литературы, в частности, есть ссылки на базовые работы
Менезеса и Роса, которые стоит рассмотреть, если появится
желание/необходимость более полно погрузиться в тему.»

-- 
Дмитрий Державин,
BaseALT/Базальт СПО

Re: [oss-gost-crypto] EC-RDSA and a key substitution attack

[Vitaly Chikunov]

Дмитрий,

On Wed, Dec 05, 2018 at 12:55:25PM +0300, Дмитрий Державин wrote:
> Ср, 05 дек 2018, 10:35, Дмитрий Державин:
> 
> >>   NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
> >>   vulnerable to a key substitution attack[10]. […]
> 
> […]
> 
> > Вопрос неоднократно обсуждался. […]
> 
> Вдогонку — статья Николаева, в которой тема раскрыта очень подробно:
> http://www.mathnet.ru/links/b6caaa0250ad0cebf13bad371799b3b2/mvk177.pdf
> 
> Комментарий автора:
> 
> «В списке литературы, в частности, есть ссылки на базовые работы
> Менезеса и Роса, которые стоит рассмотреть, если появится
> желание/необходимость более полно погрузиться в тему.»

Спасибо!

> 
> -- 
> Дмитрий Державин,
> BaseALT/Базальт СПО
> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto@lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto