Документы не дают понять, как такое возможно. 13 октября на конференции ACM CCS выступили известные криптографы Алекс Халдерман (Alex Halderman) и Надя Хенингер (Nadia Heninger) с докладом, в котором они предполагают, что решили эту таинственную загадку. Кстати, их работа признана лучшим докладом конференции.
По мнению специалистов, проблема в алгоритме Диффи-Хеллмана, который широко используется в интернете для обмена ключами при установке защищённого канала. Это краеугольный камень надёжной криптографической защиты. Он используется в VPN, HTTPS и многих других протоколах.
Протокол Диффи-Хеллмана позволяет двум и более сторонам получить общий секретный ключ, используя незащищённый от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
Проблема вот в чём. Если клиент и сервер обмениваются ключами по протоколу Диффи-Хеллмана, то изначально им нужно договориться о большом простом числе, которое используется для дальнейших вычислений. Казалось бы, нет проблем, если все будут использовать одно и то же число, и в реальности во многих приложениях жёстко зашиты такие числа. Но есть одна важная деталь. А что, если некий злоумышленник вложит гигантские средства, чтобы выполнить единственное вычисление и «взломать» конкретное простое число, а потом легко будет расшифровывать коммуникации всех, кто использует это число.
В своей работе Халдерман и Хенингер оценивают масштаб инвестиций. Для наиболее распространённого типа Диффи-Хеллмана (1024 бит) такой суперкомпьютер, сделанный на стандартном железе, будет стоить несколько сотен миллионов долларов. Он сможет взломать одно простое число примерно за год.
Есть ли смысл разведывательному агентству инвестировать такие деньги, чтобы обрабатывать по одному числу за год? Халдерман и Хенингер считают, что есть. Дело в том, что если взломать самое распространённое в реальных приложениях простое число, то вы сможете дешифровать две трети мирового VPN-трафика и получите доступ к четверти SSH-серверов!
Взлом второго по популярности числа даёт вам доступ к пассивной прослушке примерно 20% HTTPS-серверов из списка миллиона самых популярных сайтов.
Другими словами, однократные инвестиции в оборудование позволят расшифровать триллионы зашифрованных соединений.
Бюджет АНБ, несомненно, достаточен для этого.
Подробнее см. работу Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice.
Комментарии (37)
Scratch
15.10.2015 19:37Вы про дефолтные параметры в серверах типа apache/nginx? Так ssllabs уже давным давно ругается на них, это не новость
EvilGenius18
15.10.2015 20:08+1А почему бы не увеличить длину с 1024 бит до 4096 бит? Кто-нибудь может подскажет, помогло ли бы это защитить протокол от взлома даже при использовании супер-компьютера?
Или Почему бы не сделать двойную систему шифрования
Шифрование протокола шифрования, так сказать
grokinn
15.10.2015 20:18+4Сделать то можно что угодно, проблема в том что существует множество серверов и ПО, которые используют алгоритм в текущей реализации и изменить это даже при всем желании быстро нельзя, не говоря уже о том, что АНБ будет противодействовать таким новациям, по крайней мере для американских компаний, на которые оно может оказать давление.
6opoDuJIo
16.10.2015 01:50+3В некоторых странах максимальная длинна ключа ограничена законодательно. Т.о. использование длинного ключа будет нелегальным.
vlreshet
16.10.2015 10:46+3Очень странные законы существуют в нашем мире, оказывается. То есть если я возьму рецепт куриного пирога, потом порешаю над ним очень сложную математику (зашифрую в 4096 бит), и кину итог другу Ивану — то я стану преступником?
roboq6
16.10.2015 11:31+2Наоборот, закон очень логичный. Ведь если шифрование будет слишком надежным, то даже товарищи из КГБ не смогут взломать ваш шифр. Хорошо если это рецепт куринного пирога, а вдруг это план путча/революции против власть имущих?
vlreshet
16.10.2015 12:29+4Но погодите, шифрование и нужно чтобы никто не мог прочитать мою информацию, разве нет? Откуда мне знать что нет таких же умных товарищей как товарищи из КГБ, которые тоже смогут сломать мой шифр? Почему вообще я должен думать о том что кому-то будет сложно меня взломать?
roboq6
16.10.2015 12:40По идее Ваше шифрование должно быть достаточно стойким, чтобы противостоять атакам криминальных элементов и нечистых на руку конкурентов, но при этом достаточно слабым для КГБ/ФСБ и т.д. То есть, выражаясь фигурально у Вас должна быть достаточно крепкая дверь, чтобы предотвратить проникновение бандитов, но при этом НЕ настолько крепкая, чтобы предотвратить доступ агентов ФСБ.
Digwener
16.10.2015 13:29+3Это при условии, что в АНБ/ФСБ нет недобросовестных сотрудников, которые могут использовать данные, к которым имеют доступ, в личных и преступных целях. Ну и что недобросовестным не становится всё государство.
6opoDuJIo
17.10.2015 03:53Так уж получилось что некоторые инстанции являются доверительными. В противном случае, ничего не работало-бы вообще.
zagayevskiy
16.10.2015 13:52Знаете, если так рассуждать, то обвинять АНБ в том, что оно скомпрометировало протокол, вообще глупо.
vlreshet
16.10.2015 14:26+1Нет, это я прекрасно понимаю. Вопрос в другом — а почему я должен ставить недостаточно крепкую дверь для агентов ФСБ? Почему я впринципе не могу делать со своей информацией всё что хочу? Если злоумышленники захотят — они будут использовать и 4096 бит, им всё равно уже, они и так преступники. А мне почему нельзя?
roboq6
16.10.2015 14:51+2а почему я должен ставить недостаточно крепкую дверь для агентов ФСБ?
Потому что те люди, которые контролируют государство, так хотят. Захотят — сошлют Вас в Гулаг как врага народа. Захотят — кожу живьем сдерут.
Почему они этого хотят? Сложный вопрос, для этого нужен контекст. Они могут боятся исламского терроризма,
они могут бояться восстания народных масс. Если они и есть народные массы, то демагоги могли промыть им мозги, что их безопасности что-то угрожает, хотя на самом деле всё ОК.
Если злоумышленники захотят — они будут использовать и 4096 бит, им всё равно уже, они и так преступники.
Зато рядовой гражданин сможет спокойно обойтись и более слабой защитой, в то время как для настоящих преступников это будет насущная необходимость. Уже самим использованием более мощной защиты они будут выдавать себя с головой.vlreshet
16.10.2015 15:01-2С последним аргументом соглашусь. Что-то похожее говорят при обсуждении легализации оружия — что сейчас человек с пистолетом но не в форме — это почти полюбом преступник, а при легализации все будут с пушками и преступникам будет куда легче.
Athari
16.10.2015 16:23Уже самим использованием более мощной защиты они будут выдавать себя с головой.
Не уверен, что такое уж большое палево, учитывая массовое распространение паранойи среди гиков после откровений Сноудена.roboq6
16.10.2015 16:37А у них своя логика: используешь слишком сильную криптографию? Значит тебе есть что скрывать от НАС.
А если используешь просто так, то получишь от нас за это тумак, ибо нефиг.
Nagg
16.10.2015 21:32+2С 4096 просядет конкретно перфоманс. Гугл вон долго тянул с переходом на 2048 из-за этого.
GamePad64
15.10.2015 20:26+15ИМХО, каждый tls-сервер должен самостоятельно генерировать параметры DH. Это же так просто:
Всего одна команда, и все АНБ идут в известном направлении.openssl dhparam -out dhparam.pem 4096ankh1989
16.10.2015 09:47+3Только не в неизвестном направлении. Они идут жаловаться тем кто пишет законы и те запрещают использование слов «openssl» и «dhparam» в комбинации с числами больше 512 на одной строке. Большие фирмы против закона не попрут, а значит практически весь трафик будет уязвим перед АНБ. Впрочем, судя по всему, они уже давно так сделали — см. законы об ограничении длины ключа шифрования.
Ivan_83
16.10.2015 01:44+8Желтина!
Протокол не скомпрометирован, скомпрометированы те идиоты кто им не умеет пользоваться.
Это в первую очередь касается https: там практически не используется эллиптическая крипто (должно быть в сертификатах) а админы нихрена не понимают и не перегенируют ничего.
SSH: касается виндузятников, потому что в виндовых клиентах нет эллиптической крипты (кроме тератерм).
Всех кто юзают эллиптическую крипту это не касается: см Elliptic curve Diffie–Hellman (ECDH) — там вообще нет никаких чисел, стороны обмениваются публичными ключами и всё. Эти публичные ключи умножаются на секретные ключи и обе стороны получают общий секретный ключ.
Тоже самое примерно и в Curve25519.
makkarpov
16.10.2015 12:32+1Там есть набор стандартных кривых, которыми (и только ими) тоже пользуются все:
openssl ecparam -list_curves
Пока, конечно, не опубликовано способа, который может ускорить вычисления закрытых ключей, сгенерированных над этими кривыми, но утверждать, что в ECDH/ECDSA совсем нет общих параметров, нельзя.
bootch
16.10.2015 13:36Это в первую очередь касается https: там практически не используется эллиптическая крипто (должно быть в сертификатах) а админы нихрена не понимают и не перегенируют ничего.
Можете пояснить что и на каком этапе нужно перегенерировать? Или кинуть «правильный» мануал, с описанием всех шагов?lexore
16.10.2015 14:35Вот документация: wiki.mozilla.org/Security/Server_Side_TLS
А вот даже готовый генератор конфигов: mozilla.github.io/server-side-tls/ssl-config-generator
roboq6
Спрашивается, зачем тратить столько времени и ресурсов на брутфорс этого числа, если его можно просто выдрать из кода программ которые его используют? Даже если программа проприетарная, то наверняка дизассемблирование дешевле обойдется.
Scratch
Брутфорс не числа (оно не секретное) а параметров, которые с помощью этого числа получаются
roboq6
Похоже я плохо понимаю как происходит использование простого числа в по протоколу Диффи-Хеллмана. Не могли бы описать?
Я просто думал, что простое число выполняет функцию ключа.
prishelec
Тоже сильно заинтересовало это число:
Вот понятно описано: https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана
grokinn
При известном простом числе вычисляются все возможные варианты открытых и закрытых ключей, которые получаются с использованием этого простого числа, на выходе получается множество пар открытый ключ-закрытый ключ, перехватывается трафик, из него берется открытый ключ и из таблицы берется закрытый ключ, далее сообщение расшифровывается.
a5b
К сожалению, для протокола Диффи — Хеллмана в поле вычетов по модулю (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
В обсуждаемой же работе weakdh.org/imperfect-forward-secrecy-ccs15.pdf Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice // CCS’15, October 12–16, 2015, Denver, Colorado, USA. ACM 978-1-4503-3832-5/15/10. DOI: dx.doi.org/10.1145/2810103.2813707
речь идет о намного более практичной атаке на проблему дискретного логарифирования (дано ключ y = g^a mod p; заранее известны g и p, получен y, найти a) с помощью лучших методов решета числового поля (number field sieve, GNFS). В данных методах требуется очень большой объем вычислений для каждого модуля p, но большая часть вычислений не зависит от конкретных ключей (см precomputation из Figure 1 статьи):
Авторами статьи был проведен предварительный расчет для трех 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 млн).
GAS_85
Это тот самый случай, когда комментарий лучше статьи.
NeoCode
Я кстати после прочтения статьи тоже хотел написать, что не проще ли дизассемблировать приложения и извлечь оттуда эти числа. Из текста статьи следует, что секретным является именно число. Я ничего не понимаю в криптографии, но интуитивно понятно, что тут какая-то недосказанность. Если число не секретное, какие секретные параметры могут с его помощью получаться?
Scratch
После прочтения статьи достаточно взглянуть на имя автора и понять, что это очередная туфта.
Вот описание
А весь смысл в том, что эти простые числа много где одинаковые по умолчанию (их довольно долго нужно генерить, чтобы этот процесс был прозрачным при установке) и если взломают закономерность, на них основанную, то все сгенеренные ключевые пары можно будет отправить в помойку.
Так что нет, АНБ ничего еще не скомпрометировало, просто очередная желтизна
dom1n1k
Нет, комментарий выше правильно излагает суть
geektimes.ru/post/264040/#comment_8838450
Dragonim
Вот очень понятное описание алгоритма Диффи-Хеллмана
https://youtu.be/vFjq9pID4-E