Заместитель главного редактора
3,5
рейтинг
3 августа 2013 в 08:57

Разработка → Эксперты призывают готовиться к криптоапокалипсису



На прошедшей в Лас-Вегасе конференции Black Hat с особым заявлением выступили четверо исследователей кибербезопасности: Алекс Стеймос, Том Риттер, Томас Птачек и Джавед Сэмюель. Суть их просьбы сводилась к следующему: существующие алгоритмы, лежащие в основе современной криптографии, могут находиться в опасности прогресса решения математических задач, поэтому всем нам следует отказаться от существующих SSL-сертификатов в пользу более новых методов криптографии.

Общеизвестно, что в основе асиметричной криптографии лежит два ключа: один может зашифровать данные, другой используется для их расшифровки. Это возможно благодаря свойствам односторонних функций. Предполагается, что некоторые математические операции трудны и могут быть выполнены лишь за экспоненциальное время, то есть за время, возрастающее экспоненциально при линейном увеличении размерности задачи. Однако, существование таких функций, то есть свойство экспоненциального возрастания сложности так и остаётся недоказанной гипотезой.

Существует ненулевая вероятность того, что в будущем найдётся подобное решение, возможное за полиномиальное время, что сулит криптографический апокалипсис. Суть доклада квартета исследователей сводилась к тому, что этот момент может быть не так отдалён от настоящего времени, в то время как альтернативные и более современные методы криптографии не имеют большого распространения.

Наиболее распространённые асимметричные алгоритмы — алгоритм Диффи — Хеллмана, RSA, DSA — полагаются на сложность двух задач: факторизации целых чисел и дискретного логарифмирования. Современная математика не располагает простыми решениями, выполняемыми за полиномиальное время, однако в сравнении с десятилетиями медленного продвижения вперёд резкая активность в этой области последнего полугода очень подозрительна.

Были получены быстрые алгоритмы дискретного логарифмирования, имеющие ограниченное применение. На данный момент не существует известных способов использования этих наработок в практической криптографии, но даже эти математические достижения пугают криптографов. Исследователи проводили аналогии с атаками на SSL вида BEAST, CRIME и BREACH. Использованные для этих атак особенности асимметричной криптографии точно так же долгие годы считались сугубо теоретическими и не имеющими практического применения, но всё вышло иначе.

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

Стоит помнить, что пострадать от полиномиальных алгоритмов общего применения факторизации целых чисел и дискретного логарифмирования может не только SSL, но и другие протоколы и методы шифрования данных: SSH, PGP и т. д. Под угрозой будут обновления с новыми методами криптографии для операционных систем и прикладного ПО: поскольку программы опираются на цифровые подписи, быстро появятся поддельные пакеты обновлений. Хотя эта катастрофа может произойти не скоро, а может, и вовсе не произойдёт никогда, поскольку будет доказана невозможность решения соответствующих математических задач за полиномиальное время, нам следует обезопасить себя развертываением альтернативных методов криптографии, считают исследователи.

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

Поддержка же эллиптической криптографии имеет свои проблемы. Большая часть технологии запатентована компанией BlackBerry, и патентные проблемы заставили некоторых производителей отказаться от поддержки технологии. Использующие эллиптическую криптографию протоколы (к примеру, последняя реализация технологии SSL — TLS 1.2) пока ещё не поддерживаются достаточно широко. Виновны в этом также сертификационные центры, пока что почти не предоставляющие сертификатов эллиптической криптографии.

В общем и целом исследователи призывают индустрию информационных технологий начать поддерживать эллиптическую криптографию уже сегодня, а также удостовериться в защищенности систем, использующих криптографию: они не должны полагаться на устаревшие алгоритмы и протоколы. Программное обеспечение должно быть легко обновляемым, позволяя держать паритет с математическим прогрессом и техническими достиженями отрасли. Криптоапокалипсис может и не случиться, но готовность к нему обязательна уже сейчас.
По материалам Ars Techica. Фотография пользователя lyudagreen.
@atomlib
карма
268,7
рейтинг 3,5
Заместитель главного редактора
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (79)

  • +21
    А я думал там только полезные доклады…
    • +6
      Полезность… она субъективна, так же как и интересность. По крайней мере я знаю конкретных людей, кому этот доклад полезен и интересен.
      • +7
        Вообще они ничего нового не рассказали.

        На счет полиномиальности решения NPC задач. Даже если и найдут полиномиальный алгоритм, то это еще не факт, что он будет малой степени.
        Есть случаи когда находят теоретическую оценку на алгоритм вроде O(n^32). Фактически даже для n = 3 такой алгоритм выглядит ужасающе.
      • +10
        для подавляющего большинства участников этой конференции такая информация звучит как в сотый раз реферат школьного уровня.
        натурально — ничего нового не сказано.
        • 0
          Возможно я паранойик, но я так понял по этому докладу что они что-то знают, но боятся афишировать из-за возможных последствий.
          • +7
            Да-да-да. Именно поэтому они всё выступление подмигивали. Левым глазом — точка, правым — тире.
            Результат декодировать пока не удалось, но мы уверены, что в результате узнаем доказательство.
  • +12
    А причем тут дискретный логарифм и факторизация? Атаки, которые авторы приводят в пример это просто ошибки в реализации, причем не в части асимметричного шифрования. думаю все очень сильно притянуто за уши. Хотя посыл в целом верный. Давно пора на эллиптику переходить.
    • +7
      о которой пока тоже не особо-то известно.
      там задача логарифмирования так же не доказана же.
      • +3
        Совершенно согласен. Можно даже под сомнение поставить что лучше, алгоритмы основанные на простом дискретном логарифме или на эллиптике. Для вторых с их то размером ключа появление субэкспоненциального решения фатально. Но это если уж режим параноика включить)
    • +1
      Автор имел в виду что точно также как внезапно нашлись уязвимости в протоколе — могут найтись уязвимости в алгоритме.
      • +3
        Просто сравнение очень неудачное. RSA появился в 70-х годах. За условные 40 лет использования практически осуществимых уязвимостей не найдено. TLS 1.0 разработан в 1999 году, в том же году Брюс Шнайер предсказывал практические атаки на протокол(он об этом в своем блоге писал, после публикации атаки BEAST). Да, для реализации уязвимостей потребовалось более 10 лет, но эти уязвимости предсказывались специалистами. С RSA и DSA такого не было. Поэтому с авторами доклада не согласен.
        • +1
          Практически осуществимые варианты факторизации появлялись.
          Когда эллиптикой стало возможно мочить 256битные числа за единицы минут — за RSA мне было по-настоящему страшно.
          К счастью, пока, всё-таки, барьер в 768 взят в единичных вариантах, а не массовых.
          Это, конечно, настораживает, что почти за 2 десятилетия (если не ошибаюсь, ECM появился в 87 году?) ничего более оптимального не появилось, но с тем же успехом может означать что лучше-то и нетути.
          • +1
            И все таки, согласись, что примерная оценка времени в 2^90, которую имеют самые быстрые субэкспоненциальные алгоритмы, для ключа RSA длиной в 1024 бит это с сегодняшним уровнем вычислительной техники еще далеко не угроза для асимметричной криптографии. А ведь еще есть солидный запас, практически все решения поддерживают длину ключа в 4096 бит.
            • +1
              Пока да. Главная проблема — это расслабон. Ну сменили 4k RSA на 384bit ECDSA, и опять дудим в трубочку.
              Не могу сходу вспомнить по какому запросу гуглил, но была же табличка — товарищи снимали по сети доступные сертификаты, и считали НОД для них, тем самым смогли вскрыть значительное количество их ключей.
              Самое же главное в этом — что подавляющее большинство ключей и сертификатов в Сети — всё еще 1к размером.
              • +3
                Да тоже читал что то такое. Там вроде неправильно работал PRNG в UNIX системах. Но мы опять приходим к тому с чего начинали. Об атаках на сами криптопримитивы речи не идет. Все сводится к неправильным реализациям. Это беда конечно, но такое всегда было и всегда будет.
                • +1
                  да, плюс роутеры, у которых просто нет нужного количества энтропии
                • +2
                  По описанию похоже на www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf — Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices
                  • +1
                    оно! 512-bit RSA KEY: 1% — всё еще хуже, чем я помнил
                    еще была табличка с распределением по длине ключа. помнится, 1K — подавляющее большинство.
          • +1
            Как-то я безнадёжно отстал, 512 бит похоже уже берётся за считанное время на домашних пеньках:
            www.math.ttu.edu/~cmonico/software/ggnfs/
            • +2
              Там вроде тока про числа определенного вида говорится.
              • +1
                да, похоже на то. ggnfs+msieve не разжевал за пару часов тестовый пример. может, если оставить на недельку и разжуёт, но не хочется греть комнату, и так жарко.
    • +1
      Согласен. Чаще всего ошибка таится в реализации. А для асимметрического протокола на трудноразрешимых задачах стойкость доказана практикой. Ну подойдет вычислительная мощность и что, на 1024 бита параметры увеличат и снова можно лет 50 пользоваться. А для эллиптических кривых так вообще есть куда расти в этом плане. Там, вроде как, проблема только при шифровании (биекция алфавита и точек), но пусть шифрование самих данных так и остается на симметричных протоколах с доказуемой стойкостью :)
      Про уши точно подмечено)
    • +1
      удалено (не туда попал)
  • +6
    Соглашусь с NeverWalkAloner
    То, что авторы протокола изменяют размер криптованного сообщения при незначительном изменении содержащихся в нем данных и открывает класс «Oracle» атак вида «а давайте вот сюда прибавим один байтик и посмотрим изменится ли размер ответа от сервера».
  • +7
    Не увидел чего-то такого, что срывало бы покровы. Думал конкретика, а тут сплошное «могут появиться». Интересно, а они про квантовые компьютеры и связанные с этим проблемы криптографии слышали? Или это будет темой следующего доклада?
    • +6
      А на нём, вероятно, они расскажут, что алгоритм Шора…
    • +2
      Скорее всего на доклад нужно смотреть не в научном аспекте. Я бы изучил список приглашённых гостей и личности докладчиков (нет ли там кого-то от правительства / армии / спецслужб / казначейства). Такие страшилки, из разряда «существует ненулевая возможность, что кругом враги, давайте покупать пулемёт» — обычно только попытка вытрясти денег (в данном случае на лицензирование технологий и на их внедрение), либо артподготовка к последующей попытке вытрясти денег.
  • +3
    Большая часть её реализации запатентована компанией BlackBerry, и патентные проблемы заставили некоторых производителей отказаться от поддержки технологии.

    Патентами покрыта реализация или алгоритм? Если запатентованы реализации (т.е. исходный код), то черт с ним, можно сделать новую реализацию уже имеющегося алгоритма. (Для ясности добавляю, что патенты на исходные коды ПО выдаются в очень немногих странах, в остальных исходники защищаются законодательством об авторских правах по тому же принципу, что и литературные произведения).
    Т.е., если патенты на реализацию, а сам алгоритм извесен — наличие патентов не проблема.
    Если патент получен на сам алгоритм, тогда выступление математиков выглядит не более как рекламная акция компании BlackBerry: «Ай-я-яй, что ж вы такие не хорошие, не пользуетесь технологиями, покрытыми нашими патентами».
    • +1
      Скорее всего реализация. В I2P-Bote пользуются эллиптикой и ничего…
    • +1
      Bitcoin эллиптику использует.
  • +4
    Действительно, больше похоже на рекламу BlackBerry. Если задачу факторизации и научат решать за полиномиальное время, то к этому времени, вполне возможно все уже перейдут на квантовую передачу данных. В крайнем случае, вернёмся к шифрам Вернама;)
  • +10
    «Существует ненулевая вероятность того, что в будущем найдётся подобное решение, возможное за полиномиальное время, что сулит криптографический апокалипсис.»
    Для чего, что произойдёт в будущем, нулевая вероятность?
    • +1
      Для чего, что произойдёт в будущем, нулевая вероятность?

      Солнце будет светить вечно…
  • +25
    А ничего, что OpenSSH уже два года использует по умолчанию ECDSA (на базе эллиптических кривых), а уж российские ГОСТы и уже более десяти лет как переведены на эллиптические рельсы?

    Смешно читать этот текст…
  • +2
    По моему, бОльшие риски для криптографии связаны с развитием квантовых вычислений. Есть-ли сейчас какие-то криптографические технологии которые могут помочь против них?
    • +2
      только-шифровальный блокнот.
      • 0
        Шифровальный блокнот не поможет. Если шифрующая последовательность (ключ) повторится хотя бы несколько раз (может и двух хватит) то начнёт проявляться когерентность.
        Спасение только в бесконечном ключе — но тогда ведь весь смысл возни с сертификатами пропадает.
        • 0
          Думаю для квантового компьютера код длиной в биллионы знаков-обычное дело. Тем паче, если использовать на каждое слово свой код, то как алгаритм будет разбиратся, из множества противоречивых друг другу вариантов, правильный?
        • +3
          > Если шифрующая последовательность (ключ) повторится хотя бы несколько раз

          … то это не одноразовый блокнот (One-time pad).
      • +1
        А если найти сложные вычисления для квантого компьютера и на их основе создать ассиметричный алгоритм?
        • +1
          А зачем? Проще использовать квантовую сцепленность.
          • +1
            Ага, и доставлять частицу и детектор (по количеству сайтов) к каждому домой?
            • +1
              А вот и механизм монетизации веб-сайтов нашелся :)
          • +1
            … проще?
    • +3
      Есть ряд асимметричных алгоритмов основанных на принципиально других проблемах нежели факторизация и дискретный логарифм. Для таких задач пока неизвестны квантовые алгоритмы решения. Об одном из таких алгоритмов я когда то писал на хабре.
      • +1
        я думаю 1 моль вещества возмёт его и брутом.
        • +2
          Я думаю, 2^512 вариантов 512-битного ключа рассмеются в лицо 6*10^23 молекулам одного моля.
          • +1
            Квантовый компьютер использует квантовые состояния частиц, число которых растёт по экспаненте от числа состовляющих систему частиц. Так, что теоретически е^(6*10^23) это явно больше 2^512.
            • +2
              Я думал, речь о вычислениях на ДНК ( www.keldysh.ru/papers/2005/prep57/prep2005_57.html ), а не о мифических квантовых.

              Просто никто не меряет мощность квантового в молях, это скорее свойство химических компов.
              Квантовые считалки потребуют точной настройки каждой частицы, как и сейчас организованы процессоры, а не кучу-малу.
              • +1
                Согласен. Я говорил про теоретическую возможность данной технологии, а не про практическую возможность её реализации.
                • +1
                  в общем, если предварительно настроить комп для вычисления (и потратить для этого 2^511 времени), результат будет моментально, да.
                  • +1
                    Всё зависит от квантового алгоритма. Если придумают квантовый алгоритм, чьё время вычисления падает по быстрорастущей функции(вроде логарифма или степенных функций, экспоненте), то время вычисления снизится до вполне приемлемых порядков. Как пример, квантовый алгоритм факторизация чисел(алгоритм Шора).
    • +1
      Сами же квантовые вычисления и помогут, см. квантовая криптография.
    • +1
      А что там сейчас с алгоритмом Шора и квантовыми вычислениями, на больших числах? Я слышал, что успешно разложили какое-то двухзначное число, на этом и остановились.
  • +15
    Новость вкратце: Если докажут, что P=NP, то нынешние алгоритмы криптографии будет возможно сломать. А пока-что ломают через баги в имплементации.
    А, секунду… Тоесть и не новость вовсе?
    • +2
      Если докажут, что P=NP, это будет означать, что быстрый алгоритм разложения произвольного числа на простые множители существует. Но сам по себе он от этого не найдется. Другое дело, что из доказательства P=NP, возможно, будет видно, в каком направлении копать, чтобы этот алгоритм найти. А может и не будет видно.
      • +1
        Само по себе доказательство может заключаться в обнаружении такого алгоритма.
        • +2
          А может и не заключаться… ;-)
        • +2
          Теорема о P=NP носит более общий характер, поэтому не может доказываться через нахождение такого алгоритма для частного случая.
          • +1
            Разумно.
          • +1
            Однако она может доказываться через нахождение полиномиального алгоритма для решения любой NP-полной задачи.
          • +1
            Кстати, нам и не нужно знать, что P=NP для того, чтобы сломать криптографию. Нам достаточно найти сам этот частный случай.
            • +1
              Вы правы, но ветка комментариев начиналась не с этого.
              А мысль о том, что чтобы сломать конкретный криптографический алгоритм надо его сломать, мне кажется и так достаточно очевидной.
              Понятно, что для того. чтобы опрокинуть алгоритм RSA, надо просто найти быстрый алгоритм разложения произвольного числа на простые множители, и черт с ними с P и NP.
          • +1
            Нет. Если я не ошибаюсь, все эн-пэ-полные задачи эквивалентны. Быстрое решение одной из них означает быстрое решение остальных, и означает, что п равно нп
    • +2
      Если мне не изменяет память, не доказано, что задача факторизации или дискретного логарифмирования является NP-полной.
  • –4
    Общеизвестно, что в основе асиметричной криптографии лежит два ключа: один может зашифровать данные, другой используется для их расшифровки.

    Не первый раз вижу это утверждение, но это же ерунда: для зашифрования используется закрытый ключ отправителя и открытый получателя, а для расшифрования используется закрытый получателя и открытый отправителя. Т.е. в обоих процессах используются и открытые, и закрытые ключи.
    • +5
      Неверно. (Такое ощущение, что вы путаете основы и базирующийся на них протокол Диффи-Хеллмана. Читайте матчасть.)

      Вкратце: я зашифровываю вашим открытым ключом и отдаю вам. Только вы можете расшифровать своим закрытым ключом. Вы сможете прочитать содержимое, но не узнаете, кто отправил его.

      В общем, есть два варианта:
      — Я шифрую своим закрытым ключом — это моя подпись. С помощью моего открытого ключа (доступного всем) можно доказать, что сообщение создал (зашифровал) именно я, т.к. открытый ключ подошёл именно мой, а только у меня есть соответствующий закрытый ключ.
      — Я шифрую вашим закрытым ключом — это я защищаю сообщение от кражи для передачи вам. Только вы, владелец закрытого ключа, сможете увидеть содержимое сообщения.

      Часто подпись и защита от подсматривания используются вместе (причём подписывают не сообщение, а его хеш, и защищают не сообщение, а некий случайный ключ симметричного алгоритма, которым уже шифруют само сообщение), однако никто не обязывает вас одновременно защищать и подписывать. Для каждой из этих отдельных задач нужно ровно два ключа.
      • +3
        «Я шифрую вашим закрытым ключом» — это конечно ошибка, читать как «Я шифрую вашим открытым ключом».
        • +1
          Прошу прощения, что-то меня глючит.
  • +4
    Пока что из всех криптоугроз для SSL самой близкой и серьёзной можно считать визит сотрудников несуществующего агентства в офис веризон или там геотраст с просьбой отдать им маленький файлик ca.key.
  • +2
    Не криптографистов, а криптографов.
  • +2
    Я даже подумал, что это Ализар написал :)
  • +1
    С точки зрения квантовых вычислений эллиптические кривые не сложнее факторизации.
    • +3
      пруф?
      • +2
        Та же самая проблема логарифмирования, просто немного другое поле, в котором нужно производить операции. А так — оригинальные алгоритмы Шора (1994) решают и дискретное логарифмирование, и разложение на множители.

        www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf
        It is straightforward to use Shor’s algorithm to solve the discrete log problem for an elliptic curve over F_p in time poly(log p).… Thus, in practice, much smaller key sizes are used in elliptic curve cryptography than in factoring-based cryptography. Ironically, Shor’s algorithm takes a comparable number of steps for both factoring and discrete log (regardless of the group involved), with the caveat that group operations on an elliptic curve take more time to calculate than ordinary multiplication of integers.


        arxiv.org/pdf/quant-ph/0301141v2.pdf
        It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits.
        • +1
          Огромная просьба отсыпать!
          Я, по моему скромному мнению, мастер сутры гуглинга, но это было вне моих сил.
          Спасибо. Выкурю на выходных.
  • +1
    Нас ждет очередная компания типа проблемы 2000-года, чтобы индустрия заработала бабла :)
    • +1
      да главная проблема — всё уже есть, надо только приложить усилия.
      как с IPv6.

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