Bankir.Ru
8 декабря, четверг 14:56

Объявление

Свернуть
Пока нет объявлений.

Серьёзная ошибка в Ecdsa?

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

  • Серьёзная ошибка в Ecdsa?


    Серьёзная ошибка в ECDSA.

    В матаппарате новейшего американского стандарта ЭЦП известного как ECDSA [1 cтр. 25-30] (DSA для эллиптических кривых) существует серьёзная ошибка позволяющая выбрать такое значение секретного ключа, чтобы получить одинаковые подписи для разных документов.
    Описанная ошибка отличается от уже известных и сходных по смыслу DSKS [1 стр. 30-32]. (Duplicate Signature Key Selection), тем, что не требует участия злоумышленника в выборе параметров подписи (G,q и т.д.). Таким образом она доступна практически любому пользователю ЭЦП.

    В описании сохранены обозначения принятые в стандарте.

    Эта ошибка вызвана равенством x-координат противоположных точек эллиптической кривой

    _x(G)==_x(-G) . (1)

    Легко увидеть, что если nG=0, то (n-1)G=-G. (2)

    Отсюда следует,
    r1= _x(kG)==r2=_x( (n-1)kG)==r (3)
    где k – случайный ключ подписи для простоты принимаемый за 1.

    Кстати k может быть >1, это ничего не меняет, но так проще.


    Описание ошибки.

    Пусть нам необходимо подобрать одинаковую подпись для сообщений M1 и М2. Мы можем рассчитать личный секретный ключ d такой, что подписи для этих сообщений будут одинаковыми.

    Пусть k1=1, k2=n-1, тогда r1=r2=r=x(G). (3a)

    Посмотрим внимательнее на формулы подписи:

    s1=k1’(e1+dr) mod n и s2=k2’(e2+dr) mod n (4a,б)
    где
    k1'*k1 mod n =1 ; k1'=1 ;
    k2'*(n-k1) mod n =1; k2'=n-1

    e1=SHA(M1) mod n ; e2=SHA(M2) mod n

    Отсюда очевидно, что s2=s1=s если
    (e1+dr) == (n-1)*(e2+dr) (mod n) (5)
    или
    e1+dr= (n-1) dr + (n-1)e2 (mod n) (5а)
    ------------------------------------
    2dr=(n-1)(e2+e1) (mod n) (5б)

    Отсюда легко находится d:

    d=z’(n-1)(e2+e1) mod n (6)
    где
    z'*(2r) mod n==1


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

    Вроде я нигде не ошибся?

    С Уважением A.V. Komlin

    Литература.
    Подробное описание стандарта ECDSA и основных атак на него приведено в книге
    1. The Eliptic Curve Digital Signature Algorithm (ECDSA)
    Don Johnson (Gerticom Research), Alfred Menezes (University of Waterloo) February 24, 2000
    Эта книга доступна в PDF-формате по адресу:
    http://rook.uinc.ru/pdf/ecdsa.zip
    Последний раз редактировалось AVKomlin; 25.10.2002, 09:52.

  • #2
    Кстати решить эту проблему несложно. Нужно всего лишь обеспечить доказательную генерацию d.
    Например:выбираются случайное значение d0
    Личный ключ d:=SHA-1(d0+...)
    Сохраняются оба значения.

    В этой схеме желаемое значение d выбрать не получится.
    Время генерации ключа конечно увеличиться, но ведь оно не критично в большинстве случаев.
    Последний раз редактировалось Komlin; 25.10.2002, 10:53.

    Комментарий


    • #3
      Можно ли узнать: AVKomlin и Komlin - это одно лицо?
      И если да- зачем Вас так много?

      Sorry, это я так шучу.

      У меня вопрос: в первой редакции постинга был заговоловок (за точность не ручаюсь, но суть передам):

      Внимание! Материал не проверен эксплойтом!

      Потом он исчез. Это значит есть эксплойт? Что он из себя представляет и нельзя ли поделиться?

      Комментарий


      • #4
        Экспойтом это назвать трудно. Скорее контрольный пример для одной из стандартных федеральных кривых Curve-192 (FIPS2)

        d= 1178245955426869512043687994537032188531516960958826812264
        SHA (s,r)
        1141540178566516516516498491316516179510456516546761214564
        (3199476249460516057593544464771366849438044062282169166762,
        602046282375688656758213480587526111916698976636884684818)

        1019689415032165165165198984949841494401563165165265165121
        (3199476249460516057593544464771366849438044062282169166762,
        602046282375688656758213480587526111916698976636884684818)

        /******************************/
        /**
        * ECDSA Bug
        * @author A.V. Komlin (Kobets)
        * @version 1.0
        **/

        import java.math.BigInteger;
        import java.security.SecureRandom;

        public class ecdsabug {

        public static void main(String[] args)
        { // Curve P-192
        BigInteger n=new BigInteger ("6277101735386680763835789423176059013767194773182842284081",10);
        BigInteger x_G=new BigInteger ("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",16);
        //x(G)
        BigInteger SHA1=new BigInteger ("1141540178566516516516498491316516179510456516546761214564",10);
        // SHA1("I like ECDSA");
        BigInteger SHA2=new BigInteger ("1019689415032165165165198984949841494401563165165265165121",10);
        // SHA1("I don't like ECDSA");


        BigInteger k=new BigInteger ("1",16);

        BigInteger One=new BigInteger ("1",16);
        BigInteger Two=new BigInteger ("2",16);

        BigInteger n_2=n.subtract(Two);
        BigInteger n_1=n.subtract(One);


        BigInteger e1=SHA1.mod(n);
        BigInteger e2=SHA2.mod(n);

        BigInteger r=x_G;
        BigInteger z=r.multiply(Two); // z=2r
        BigInteger _z=z.modPow(n_2,n); // z'
        BigInteger tmp=e1.add(e2); // (e1+e2)
        BigInteger d=_z.multiply(n_1).multiply(tmp); //d=z'*(n-1)*(e1+e2);
        d=d.mod(n);

        System.out.println("d: "+d.toString(10));

        BigInteger k1=k;
        BigInteger k2=n_1.multiply(k1); // k2=(n-1)*k1
        BigInteger _k1=k1.modPow(n_2,n);
        BigInteger _k2=k1.modPow(n_2,n);;
        BigInteger dr=d.multiply(r);
        BigInteger s1=(k1.multiply(e1.add(dr))).mod(n); // s1=k1(e1+dr) mod n
        BigInteger s2=(k2.multiply((e2.add(dr)))).mod(n); // s1=k1(e1+dr) mod n
        System.out.println("("+s1.toString(10)+",\n"+r.toString(10)+")");
        System.out.println("("+s2.toString(10)+",\n"+r.toString(10)+")");
        }
        }

        /************************************/

        Комментарий


        • #5
          Форум что-то заглючил и не захотел меня узнать.

          Комментарий


          • #6
            На указанной ниже страничке находится Java-апплет, позволяющий в интерактивном режиме за несколько секунд расчитать одинаковые подписи и требуемые для этого ключи для любых двух разных сообщений, в пяти стандартных кривых NIST или в любой своей.

            http://www.venue.ru/sign1.htm

            Код апплета не обфусцирован, желающие могут посмотреть его JAD'ом.

            ----------------
            Контрольный пример
            Curve-192 (NIST)
            M1- "ECDSA is GOOD"
            M1- "ECDSA is BAD"
            d - 302035990567828412089108831099891370757859899245436683119
            s - 3138550867696141607436413456015998514180639734009232307827
            r - Ox 188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012

            Комментарий


            • #7
              Все это может быть и хорошо, только как быть с первым пунктом генерации подписи под сообщением: выбрать случайное или псевдослучайное число k??? По числу r, являющемуся x-координатой точки G, легко понять, что значение k выбрано отнюдь не случайно.
              Just do it!

              Комментарий


              • #8
                По числу r, являющемуся x- координатой точки G, легко понять, что значение k выбрано отнюдь не случайно.
                А как именно понятно?
                Ведь k можно выбрать любое.
                Случай с k=1 расмотрен лишь из-за его простоты

                Комментарий


                • #9
                  А как именно понятно?
                  Ведь k можно выбрать любое.
                  Случай с k=1 расмотрен лишь из-за его простоты


                  X-координаты у двух точек k_1G и k_2G совпадают в том и только том случае, если k_1=n-k_2.
                  Just do it!

                  Комментарий


                  • #10
                    Приветствую, Сергей

                    Извините за задержку с ответом . Из-за большой загрузки на работе я просто прозевал Ваш ответ.

                    Теперь, наконец, мне понятна Ваша мысль ( о корреляции значений хэшей или случайных ключей), но думаю, что этот факт не играет большой роли в схемах применения «двойной подписи». Я поленился указывать их потому, что они подробно описаны .
                    Рассмотрим простой пример:
                    «Плохой бухгалтер» госпредприятия отсылает платёжку на сумму ZZZZZZZZZZZ на фирму однодневку. После её прохождения возмущается : «Я посылал на сумму ZZ.ZZ. Почему система не выявила искажения информации при передаче?» Тот факт, что внутренние параметры подписи документов как-то коррелируют между собой может лишь объяснить причину произошедшего, но ничего не изменит в его юридических последствиях.
                    Разумеется денег банк не вернёт – это тоже не его проблема, но об этом речи и не шло.
                    Всё что нужно было «плохому бухгалтеру», это чтобы его не посадили. Ведь невозможно доказать, что это не случайный форс-мажор.

                    Другой пример – имитация форс-мажора в отношениях между фирмой и банком для имитации убытков.

                    С Уважением, Александр.

                    Комментарий


                    • #11
                      -

                      Комментарий


                      • #12
                        Приветствую, Сергей
                        Михаил, если быть точнее.

                        Александр, Ваш пример понятен и очевиден.
                        Давайте не будем вдаваться во взаимоотношения клиента и банка (бухгалтер должен получить подтверждение, что платеж принят и если сумма не та, то должен отозвать платеж, так что могут и посадить).

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

                        Мое мнение, что станадарты служат для защиты от человека извне, который может пытаться подобрать ключ или подпись к определенному сообщению. И с такой ролью прекрасно справляются.
                        Just do it!

                        Комментарий


                        • #13
                          Извините за ошибку с именем, Михаил. Запарка
                          Что касается подтверждения и тем более возможности отзыва платежа то это вопросы реализации. Вообще говоря платёж обрабатывается некоторое время и бухгалтер не обязан дожидаться его в онлайне.


                          ...если поступать так, как написано в стандарте, то есть генерировать случайным образом ключ, то никакой ошибки нет.
                          Мое мнение, что станадарты служат для защиты от человека извне, который может пытаться подобрать ключ или подпись к определенному сообщению. И с такой ролью прекрасно справляются.
                          Эта точка зрения несомненно имеет право на существование, но всё-таки в идеале система ЭЦП должна обеспечивать и надёжную авторизацию сообщения (как это делало DSA).

                          Кроме того от злоумышленника нельзя требовать, чтобы он ограничивал себя законодательными ограниченими. В этом случае ЭЦП не нужна вовсе
                          IMHO, реальными являются только те ограничения, выполнение которых можно проверить. В сущности на этом идея ЭЦП и основанна. Иначе бы достаточно логина и пароля.

                          Ещё раз подчеркну, что это моя точка зрения.
                          Дальше решать читателям.

                          Комментарий

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

                          Свернуть

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

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