Интернет остался без криптографии. Прощайте, VPN и HTTPS!

Что объединяет такие популярнейшие технологии интернет-безопасности, как VPN, SSL и SSH? В их основе лежит один и тот же криптографический алгоритм Диффи-Хеллмана. И математики нашли в нем уязвимость.

Дыра в VPN и SSL

Сильнейшие криптоаналитики мира собрались на конференции ACM CCСS, на которой был зачитан 14-страничный сенсационный доклад под названием «Почему Диффи-Хеллман не работает на практике». Смысл простой: защита основана на том известном факте, что перемножить два простые числа намного проще, чем разложить полученное число на простые множители. Ученые подсчитали, что для разложения 1024-битного числа потребуется суперкомпьютер, год времени и 100 млн долларов. И это ради расшифровки одной единственной сессии HTTPS, VPN или SSH. И до недавнего времени всем было очевидно, что никто заниматься этим не станет по причине финансовой нецелесообразности.

Но авторы доклада подошли к проблеме с другой стороны: а что, если попытаться расшифровывать не конкретное защищенное соединение, а заранее найти произведения простых чисел нужной размерности (1024 бита) и уже среди установленных соединений искать совпадение ключа? Так вот, суть открытия в том, что подходящих простых чисел оказалось намного меньше, чем предполагалось ранее и найти большую их часть — вполне посильная задача для крупной корпорации, не говоря уже о таких хорошо финансируемых структурах, как АНБ (годовой бюджет — $11 млрд).

Исследователи уверены, что это слабое звено в алгоритме Диффи-Хеллмана наверняка обнаружили и математики, работающие на АНБ. С высокой долей вероятности данная дыра давно и успешно используется для прослушки соединений, защищенных с помощью VPN, SSL, SSH и т.д. Следует напомнить, что Эдвард Сноуден неоднократно заявлял, что АНБ может прослушивать (и прослушивает) каналы, защищенные, казалось бы, надежной криптографией.

Фраза из комментария к докладу

Breaking a single, common 1024-bit prime would allow NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally.

Взломав всего одно общее 1024-битное простое число, АНБ сможет пассивно прослушивать две трети всех VPN-соединений и четверть всех SSH-соединений в мире.

Ваша оценка: Нет Средняя оценка: 5 (8 votes)
a

Так, а как быть с 2048- и 4096-битными ключами?

Ваша оценка: Нет Средняя оценка: 5 (2 votes)
a

Вот на них и нужно срочно переходить. Но это очень инерционный процесс, на долгие годы. Вычислительные мощности спецслужб могут расти намного быстрее.

Ваша оценка: Нет
6

В голове хранить, или на бумажке в надежном месте, правда от терморектального криптоанализа не спасет!:)

Ваша оценка: Нет Средняя оценка: 3 (2 votes)
a

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

К сожалению, для протокола Диффи — Хеллмана в поле вычетов по модулю (mod p) размером 512 (1024) бита возможно слишком много различных пар ключей (более чем порядка 2^500 и 2^1000 пар). Подобные объемы информации находятся далеко за физическими пределами хранения информации (Limits to computation) и за пределами вычислимости (Transcomputational problem — более 2^310 операций).

В частности, заметно более простая задача полного перебора 2^256 ключей (для симметричного 256-битного алгоритма, например, AES-256) потребовала бы по принципу Ландауэра (при необратимых вычислениях) потребления энергии, превышающей энерговыделение нескольких миллионов сверхновых: everything2.com/title/Thermodynamics+limits+on+cryptanalysis

...brute force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space". ---Bruce Schneier in Applied Cryptography
… Even sucking all the energy from a supernova would be just enough to pass through all states of a 219-bit counter… As long as computers are made of matter, 256-bit keys will be secure against brute-force. Except of course… if we break the second law of thermodynamics :-).

В обсуждаемой же работе imperfect-forward-secrecy-ccs15.pdf Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
речь идет о намного более практичной атаке на проблему дискретного логарифирования (дано ключ y = g^a mod p; заранее известны g и p, получен y, найти a) с помощью лучших методов решета числового поля (number field sieve, GNFS). В данных методах требуется очень большой объем вычислений для каждого модуля p, но большая часть вычислений не зависит от конкретных ключей (см precomputation из Figure 1 статьи):

With state-of-the-art number field sieve algorithms, computing a single discrete log is more difficult (примерно в 10 раз сложнее) than factoring an RSA modulus of the same size. However, an adversary who performs a large precomputation for a prime p can then quickly calculate arbitrary discrete logs in that group, amortizing the cost over all targets that share this parameter. Although this fact is well known among mathematical cryptographers, it seems to have been lost among practitioners deploying cryptosystems.

Авторами статьи был проведен предварительный расчет для трех 512-битных простых модулей (в т.ч. два из набора DHE_EXPORT), на что потребовалось 7 дней: выбор и просеивание полиномов на 2-3 тысячах ядер Sandy Bridge (8+21 тыс ядро-часов; 3 + 15 часов, идеально распараллеливается) и решение линейной системы (60 тысяч ядро-часов; пять суток на кластере из 36 машин с 2x8-core E5-2650 + Infiniband FDR, с параллельностью уже хуже). Результатом расчета для каждого модуля стали 2.5 ГБ чисел.
Затем авторы продемонстрировали решение задачи логарифмирования для ключей в этих полях на машине с 2-мя 18-ядерными Intel Xeon E5-2699 и 128 ГБ ОЗУ, в среднем за 70 секунд на ключ (от 34 до 206 секунд).

Для 768- и 1024-битного модуля они оценивают время предварительных вычислений в 8 тысяч ядро-лет и 10 миллионов ядро-лет соответственно, а время логарифмирования отдельных ключей — в 2 и 30 суток. При этом линейная система будет уже не из 2 миллионов строк как для 512 бит, а уже из 150 миллионов для 768 бит и 5.2 миллиардов для 1024 бит. Столь большие системы еще не решали, и по самым грубым оценкам их решение может потребовать сотен лет работы крупнейших суперкомпьютеров США (Titan имеет 300 тыс ядер и стоил ~$100 млн).

Сам я ярый противник теории неуловимого Джо (когда подавляющее большинство пользователей считает себя абсолютно никому не интересными с точки зрения взлома), однако в данном случае, я сомневаюсь, что "ядро-годы" работы суперкомпьютеров, стоящих в датацентрах АНБ будут тратиться (по крайней мере в ближайшем обозримом будущем) для прослушивания защищенных соединений, впрямую не связанных с нацбезопасностью США.
В этом смысле мы можем продолжать считать наши SSH-и и VPN-ы неуязвимыми.

Ваша оценка: Нет Средняя оценка: 4.9 (7 votes)
a

Впечатляет! Было весьма интересно почитать :)

Ваша оценка: Нет
a

Сильнейшие криптоаналитики мира только сейчас узнали про Rainbow Table, с помощью которых хэши пытались подбирать как бы не в 90е ещё? Обнять и плакать.

Ваша оценка: Нет Средняя оценка: 5 (5 votes)
Отправить комментарий
КАПЧА
Вы человек? Подсказка: зарегистрируйтесь, чтобы этот вопрос больше никогда не возникал. Кстати, анонимные ссылки запрещены.
CAPTCHA на основе изображений
Enter the characters shown in the image.
Linux I класса
Linux II класса
Linux III класса
Счетчики
  • Самый популярный сайт о Linux и Windows 10
О Либератуме

Liberatum — это новости мира дистрибутивов Linux, обзоры, сборки, блоги, а также лучший сайт об Ubuntu*.