Bankir.Ru
5 декабря, понедельник 11:43

Объявление

Свернуть
Показать больше
Показать меньше

Серьёзная ошибка нового ГОСТА ЭЦП

Свернуть
X
  • Фильтр
  • Время
  • Показать
Очистить всё
новые сообщения

  • Серьёзная ошибка нового ГОСТА ЭЦП

    Настоящая заметка посвящена недостатку нового российского ГОСТа 34.19-2001, теоретически позволяющему сформировать к некоторому документу подпись без знания секретного ключа (далее назовем эту подпись "независимой") . Эта ошибка присутствует во всех методах основанных на идее Эль-Гамаля, но из-за неудачно сформированных требований к граничным условиям именно в новой редакции ГОСТа она имеет наибольшую вероятность практические перспективы.

    1. Описание ошибки.
    Наиболее наглядна она на примере DSA. Формула проверки подписи имеет вид.
    Открытый ключ : y=a^x %p, p, q , a.
    Длина q -128 бит, p>1000
    Подпись: (r,s).
    Хэш: h.

    w=s^-1 %q == s^(q-2) %q;
    z1= wh %q ; z2=wr %q

    Условие проверки подписи
    r== a^z1*y^z2 %p %q.

    Допустим, что r=s=h. Тогда w=s^-1
    z1= h^-1 * h %q ==1
    z2= h^-1* h%q ==1

    r==ya = a^(x+1) yaq.

    Следовательно, при yaq, для h=y*a , подходит подпись вида (y*a, y*a). Очевидно, что для её вычисления не требуется знание секретного ключа.
    Хотя с теоретической точки зрения это и ошибка, очевидно, что перспектив практического применения она пока не имеет, т. к. вероятность соответствия нужного документа хэшу y*a составляет 1^-128.
    Конечно, можно пойти от обратного и попытаться подобрать открытый ключ соответствющий y=h/a , проверяя корректность открытого ключа по формуле y^q %q=1, но вероятность успеха будет ещё ниже (hq, соотв. вероятность yq составляет q/p ~ 2^-900 даже, не учитывая требования о допустимости ключа)!

    Схожая ситуация и в старом ГОСТе

    v= (h)^q-2 (mod q) => vh== 1 %q.
    z1 = sv (mod q) и z2 = (q-r' ) v (mod q)
    u = (a^z1 y^z2 (mod p)) (mod q)

    Условие проверки
    u==r.

    Отсюда
    r=h=s=a*y^(q-1)=a^(q+1-x) %p.

    Вероятность соответствия хэша 2^-256, q/p ~ 2^-256.
    2. Перспективы применения в новом ГОСТЕ


    Давайте теперь рассмотрим новый ГОСТ.

    Он основан на применении эллиптических кривых определённых над простым полем Fp, но никаких принципиальных отличий в вычислении "независимой" подписи нет.
    В нём также приняты чуть другие обозначения которыми мы и пользуемся далее.
    секретный ключ x отныне d, хэш - e.
    Q- ключ проверки, заданный в виде точки с координатами Q=dP ( где P такая, что qP==0)

    q принадлежит диапазону (2^254; 2^256)
    p>2^256.


    v=e^-1 %q (ф. №20 в ГОСТЕ)
    z1 = sv (mod q) и z2 = -rv (mod q) (ф. №22)

    C=z1*P+z2*Q

    r==X(C) %q ( где, Xc=X(C) - x -координата точки С)

    Очевидно, что при r=s=e (h)
    C = P-Q = (q+1-d)P
    r= X(C) %q.

    "Независимая" подпись для хэша X((q+1-d)P) имеет вид (X((q+1-d)P), X((q+1-d)P)).

    В чём же отличие ситуации от прочих стандартов?

    Из определения поля и формул ГОСТа № 1, 4-7 следует , что координаты X,Y любых точек кривой p.

    Учитывая, что ГОСТом допускаются примерно равные разрядности q и p, мы можем утверждать что появилась возможность подобрать ключ Q, такой, что X(P-Q) ==h. Координату У можно вычислить по формуле №1 Y*Y=X^3+ aX+b (%q).
    Проверить допустимость ключа Q можно по формуле qQ=0.

    Вероятность подбора составляет q/p.
    Вероятность того, что требуемое Q окажется корректным ключём q/2p (учитывая квадратичную связь между x,y). Проверить допустимость полученного ключа Q можно по формуле qQ=0.


    Таким образом, если разработчики программы ограничатся минимально рекомендуемым диапазоном p, вполне возможно, незначительно варьируя текстом документа подобрать такое значение ключа проверки, что подпись для данного документа может быть рассчитана без знания секретного ключа. На этом же основании вполне можно и отказаться от неё.

    Конечно комплексная защита методики работы с секретным ключём (например требование контрольной подписи) позволяет исключить возможность подобной атаки, но это никак не извиняет ГОСТ.

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

    С Уважением A. V. Komlin
    avkvladru@mail.ru

  • #2
    Хотелось бы добавить, что этот метод также может быть применим и для
    ECDSA, но там его применимость зависит от реализации т.к. стандарт не оговаривает чётких соотношений p,q

    Комментарий

    Пользователи, просматривающие эту тему

    Свернуть

    Присутствует 1. Участников: 0, гостей: 1.

    Обработка...
    X