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

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

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

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

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

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

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

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

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

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

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