Встраиваем бэкдор в Bitcoin (ECDSA) или еще раз о клептографии

    Привет, %username%!
    Пользуешься неофициальными bitcoin клиентами? Есть повод присмотреться к ним повнимательней.
    После реализации бэкдора для RSA мне стало интересно, как обстоят дела с остальными криптографическими примитивами. Оказывается, целая наука под названием клептография занимается передачей информации в так называемых «подсознательных» каналах. Таких, о которых никому не известно кроме отправителя и получателя. Вроде стеганографии, только внутри криптоалгоритмов.

    Вообще, такой класс атак на криптоалгоритмы называется SETUP (Secretly Embedded Trapdoor with Embedded Protection). То есть, обычно есть и бэкдор и защита, такая, что даже при обнаружении бэкдора невозможно будет узнать что передавалось.

    SETUP (буду говорить о SETUP в мужском роде) может быть слабым и сильным.

    Weak SETUP — Если узнать сгенерированные ключи может не только атакующий, но и владелец девайса, на котором установлено скомпрометированное ПО.
    Соответственно Strong SETUP — если узнать ключи может только атакующий.

    Еще одна характеристика называется Leakage bandwidth, она показывает сколько секретных данных «утекает» при повторяющемся процессе шифрования\подписи. Обозначается (m,n), что означает утечку m секретных сообщений/ключей за n передаваемых.

    Такие атаки существуют практически для всех схем с открытым ключом. DSA, ElGamal, Diffie-Helman, везде есть способ хоть один бит да передать скрытно. Далеко не всегда это получается так красиво как получилось с RSA, но при желании практическое применение найти можно. Например, для ECDSA провести SETUP атаку проще, потому что параметры генерации ключей (кривая, базовая точка, порядок кривой) известны заранее, а в DSA соответствующие параметры генерируются случайным образом для каждой ключевой пары.

    Как мы все знаем, кошелек в Bitcoin — это ключевая пара ECDSA.

    Сегодня мы рассмотрим сильную SETUP атаку (1,2) на ECDSA, то есть атакующий может узнать секретный ключ пользователя за 2 подписи, при чем, кроме него никто это сделать не сможет.

    Для начала упрощенно вспомним как генерируется подпись ECDSA.

    У нас есть закрытый ключ d — число и открытый ключ Q — точка эллиптической кривой, равная dG, где G — базовая точка кривой.

    • Для подписи выбирается случайное число k, в диапазоне [1, n-1].
    • Вычисляется точка кривой (x1 ,y1 ) = k*G
    • Вычисляется r = x1 mod N, где N — порядок кривой.
    • Вычисляется s = k-1(H(m)+rd) mod N, где k-1 — число, обратное по модулю N к k. H(m) — хэш подписываемого сообщения.


    Подписью является пара (r,s).

    Как видно, тут k выбирается случайно. Мы немного видоизменим процесс так, чтобы атакующий смог вычислить приватный ключ пользователя d.

    Закрытый и открытый ключи атакующего назовем v и V = vG.

    Шаг первый. Пользователь генерирует подпись первый раз (отправляет кому-то биткоины)


    Такой же, как в обычной подписи. За тем исключением, что нам будет нужно где-то сохранить k. Назовем его k1 Получаем пару (r1, s1)

    Шаг второй (отправляет биткоины второй раз)


    Вычисляем скрытый элемент поля Z = a*k1 G + b*k1 V + h*jG + e*uV,
    где a, b, h, e < n − фиксированные целые числа; j, u ∈ {0, 1} – случайные.

    a, b, h, e можно генерировать детерминировано, например используя хэш от сообщения как seed для ГПСЧ. Это усложнит обнаружение закладки.

    k2 у нас выбирается не случайно, а является теперь хэшем от Z. Хэшем от точки кривой будем считать хэш её X координаты.
    Далее всё как обычно, получаем пару (r2, s2).

    Итак, атакующий получил пары (r1, s1 ) и (r2, s2). Как ему получить закрытый ключ пользователя?

    1) Вычисляем R1′ = s-1(H(m1)G + r1Q) = (x1 ′, y1 ′). Это мы и так делаем, когда проверяем цифровую подпись.
    2) Z1 = aR1′ + b * vR1′, где v — закрытый ключ атакующего
    3) Для каждого возможного значения j, u вычисляем:
    Z2 = Z1 + h * jG + e * uV
    k2′ = H(Z2)
    R2′ = k2′G = (x2′, y2′)
    r2′ = x2′ mod n
    Если r2′ = r2, тогда k2′ = k2, мы нашли k, это то, что нам нужно

    Закрытый ключ d пользователя = (s2k2 − h(m2)) × r2-1 mod n

    Как вы понимаете, k2 тоже можно запомнить и продолжить генерировать k+1 по цепочке, давая таким образом атакующему возможность узнать закрытый ключ пользователя по любым двум идущим подряд подписям.

    Ничего сверхъестественного тут нет, атакующему лишь нужно заранее выбрать числа a, b, h, e и поместить их в бекдор вместе со своим открытым ключом. Либо генерировать их на основе подписываемого сообщения.

    Сама атака хоть и сильная, но неустойчивая. Это значит, что пользователь, владеющий своим закрытым ключом, теоретически может вычислить, что k2 генерится неслучайным образом. Для этого и вводятся j,u, чтобы разнообразить возможные значения на случай проверки бдительным пользователем. Их можно сделать отличными от 0 и 1, тогда вариантов будет еще больше. Правда, и брутфорсить придется подольше. На самом деле можно особо не беспокоиться, все равно скорей всего наличие закладки выяснится лишь постфактум когда код разберут по косточкам.

    Рабочий код этой атаки я добавил к коду атаки на RSA. Не вижу причин, по которым бы уже не существовало, или не появилось бы троянов для bitcoin, реализующих эту технику. Да, трояны могут сразу пересылать закрытый ключ (и спалиться на первом же фаерволе), а могут ничего вообще не пересылать — злоумышленник будет тихо ждать, пока на затрояненных кошельках появятся серьезные суммы.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 36

      +2
      Ещё одна причина для каждого перевода денег использовать новые адреса-получатели.
      Да, трояны могут сразу пересылать закрытый ключ (и спалиться на первом же фаерволе),
      Если пользователь проворонил такой троян, то вряд ли у него будет такой хитрый файрвол. Можно же пересылать информацию в DNS-запросах, к примеру.
        0
        Не вижу причин, по которым бы уже не существовало, или не появилось бы троянов для bitcoin, реализующих эту технику.

        тут сообщают, что такие есть.
          0
          Ватермарка
          • UFO just landed and posted this here
              0
              С одной стороны это на руку атакующему — можно не заморачиваться со случайными параметрами и тогда, как и у DJB параметр k будет всегда одинаковый для одного и того же сообщения.
              С другой стороны пользователь может сам независимо от программы посчитать HMAC(key, hash) и убедиться, что там совсем не то.
              • UFO just landed and posted this here
                  0
                  А по хорошему подпись одного и того же сообщения и должна быть всегда одинаковой, если ключ не менялся.

                  А как же такое понятие как семантическая стойкость и утечки информации об открытом тексте в детерминированных криптосистемах? Рандомизация это очень даже полезно, не стоит от нее добровольно отказываться, еще неизвестно выиграешь от этого или проиграешь.
                  • UFO just landed and posted this here
                      0
                      Я просто не согласен с тем, что подпись одного сообщения должна быть всегда одинакова. Это я не о какой то конкретной реализации говорю, а в целом. К примеру, если валидная подпись сообщения всегда одинакова, то это открывает широкие перспективы для всякого рода replay attack.
                        +2
                        Я просто не согласен с тем, что подпись одного сообщения должна быть всегда одинакова.

                        … широкие перспективы для всякого рода replay attack.

                        Это разные вещи. Детерминированность — свойство алгоритма. Например, блочный шифр AES — это детерминированный алгоритм, и это хорошо, т.к. это псевдослучайная перестановка. От атаки на протоколы, которые используют детерминированный алгоритм, защищаются на уровне самого протокола: с помощью режимов шифрования, например. С помощью уникального номера для каждого сообщения, например. В общем, на алгоритм это не влияяет.

                        Подпись не обязана быть детерминированным алгоритмом, но в этом есть польза: проще делать безопасную реализацию (особенно на каких-нибудь чипах). Недерминированность самой подписи вообще не защищает от replay никак (ну кто мешает послать тот же блок данных еще раз?), поэтому лично я вот не вижу никакой пользы от рандома.
                          0
                          А знаете вы меня переубедили. Я почему то когда говорил о рандомизации держал в уме RSA. Но для ECDSA, вариант описанный Ivan_83 действительно лишен недостатков наивного RSA и при этом избавляет от проблем с PRNG.
                          Спасибо за ответы, Ivan_83 и grich
              +1
              Оказывается, целая наука под названием клептография занимается передачей информации в так называемых «подсознательных» каналах. Таких, о которых никому не известно кроме отправителя и получателя. Вроде стеганографии, только внутри криптоалгоритмов.

              а можно поподробнее — я не могу найти никаких упоминаний об этой науке
                +1
                Подробней есть на английском. У нас эта тема мало освещена.
                  0
                  Спасибо, почитаю — я искал как cLyptography — вроде слова встречаются, но не то что надо, а на русском/укр. вообще ничего.
                0
                Такие атаки решают Дилемму заключённого.

                При чем здесь это?

                Есть такой пример в схемах с подсознательным каналом: заключенный Алиса пытается передать Бобу какую-то информацию, чтобы факт передачи не заметил охранник. Но при чем здесь теория игр?
                  0
                  Передавать в подсознательных каналах можно не только закрытый ключ, можно и сообщения
                    0
                    Я могу лишь спросить еще раз: «при чем здесь теория игр?»
                    Как методы клептографии могут заставить участников сотрудничать и придти к Парето-оптимуму?

                    Мне кажется, кроме слова «заключенный» тут ничего общего нет.
                      0
                      Об этом есть в книжке G. J. Simmons, The Prisoners' Problem and the Subliminal Channel, in: D. Chaum (Ed.), Proceedings of Crypto ’83, Plenum Press, 1984, ISBN 978-0-306-41637-8, но я её не смог найти
                        0
                        Если не смогли найти, то откуда знаете, что там написано?
                        Попробуйте вторую ссылку в гугле по запросу «The Prisoners' Problem and the Subliminal Channel». И найдите в тексте описание дилеммы заключенного из теории игр, на которую дали ссылку.

                        Не найдете, там его нет. Ставится другая проблема, тоже со словом «заключенный». Об этом я и говорю: это разные вещи в принципе.
                          0
                          Ок, убрал
                  0
                  Простите за глупый вопрос в столько серьезном топике. Я правильно понимаю, что для того, чтоб совершить какие-то вредоносные действия атакующий должен заставить жертву выполнить некий вредоносный код у себя на машине (затрояненный генератор ключевой пары, в данном конкретном случае должен быть затроянен биткойн-клиент). И только после этого злоумышленник сможет получить закрытый ключ жертвы?
                    0
                    Да, вроде того
                      0
                      Уже легче. А правильно ли я понимаю, что вся суть в том, что пока жертва не поймет сам факт выполнения ею этого вредоносного кода (что практически невозможно в случае отсутствия исходников ПО) факт утечки данных узнать никак не получится?
                      А в случае strong setup даже после понимания и полного «расковыривания» трояна узнать что именно за данные были переданы не получится.
                        0
                        Правильно. Можно будет по коду узнать что передавался именно закрытый ключ, например. Но что это за ключ — увы
                          –1
                          Что-то ни как не могу понять, данный бакдор модифицирует клиента биткоин или просто ворует закрытые ключи от кошелька с целью из старых закрытых ключей, в определенных условиях (перевод с этих ключей), получить закрытые ключи от вновь сгенерированых после деинсталляции бакдора?
                            0
                            данный бекдор ничего не ворует, он модифицирует подписи так, что тот, кто об этом знает, может узнать закрытый ключ
                              –1
                              А в каком конкретном месте происходит модификация? В системе или в клиенте биткоина?
                                –2
                                А давайте вы статью прочитаете сначала?
                                  –1
                                  Прочитал и не раз, однако хотелось бы пару строчек о том, как на практике это может быть реализовано и как от этого можно защититься. Какие конкретно действия троян незаметно произведет на удаленной машине с кошельком и как их можно обнаружить?

                                  пока на затрояненных кошельках появятся серьезные суммы.

                                  затрояненные кошельки, это как вообще?
                                    –2
                                    как на практике это может быть реализовано

                                    Там выше целая статья на тему как это может быть реализовано на практике. Даже код есть! Если вам оттуда ничего непонятно, то я ничем больше помочь не могу, это все таки хабр, а не школа
                                      –1
                                      Большое спасибо за развернутый ответ.
                                • UFO just landed and posted this here
                          • UFO just landed and posted this here
                          +1
                          Проблема в том, что навыками аудита исходного кода криптографических программ обладают единицы, а пользуются такими программами все. И это не считая закрытых программ. И встроить туда подобный бекдор — не проблема.
                          0
                          А в моем произношении из-за дефекта дикции «клептографию» от «криптографии» совсем почти не отличить :)
                            +3
                            такой класс атак на криптоалгоритмы называется SETUP (Secretly Embedded Trapdoor with Embedded Protection)

                            … у меня получается SETEP…

                            Only users with full accounts can post comments. Log in, please.