Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 38
Брутфорс не числа (оно не секретное) а параметров, которые с помощью этого числа получаются
Тоже сильно заинтересовало это число:
Вот понятно описано: https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана
Вот понятно описано: https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана
При известном простом числе вычисляются все возможные варианты открытых и закрытых ключей, которые получаются с использованием этого простого числа, на выходе получается множество пар открытый ключ-закрытый ключ, перехватывается трафик, из него берется открытый ключ и из таблицы берется закрытый ключ, далее сообщение расшифровывается.
К сожалению, для протокола Диффи — Хеллмана в поле вычетов по модулю (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 млн).
В частности, заметно более простая задача полного перебора 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 :-).
В обсуждаемой же работе 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 статьи):
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 млн).
Вот понятным языком про Диффи-Хеллмана: тыц
Если прям очень-очень грубо написать, то на основе этого числа генерируются ключ. И если сгенерировать на основе одного этого числа все возможные ключи, то можно прослушивать трафик, приложений где используется это число.
Если прям очень-очень грубо написать, то на основе этого числа генерируются ключ. И если сгенерировать на основе одного этого числа все возможные ключи, то можно прослушивать трафик, приложений где используется это число.
Я кстати после прочтения статьи тоже хотел написать, что не проще ли дизассемблировать приложения и извлечь оттуда эти числа. Из текста статьи следует, что секретным является именно число. Я ничего не понимаю в криптографии, но интуитивно понятно, что тут какая-то недосказанность. Если число не секретное, какие секретные параметры могут с его помощью получаться?
После прочтения статьи достаточно взглянуть на имя автора и понять, что это очередная туфта.
Вот описание
А весь смысл в том, что эти простые числа много где одинаковые по умолчанию (их довольно долго нужно генерить, чтобы этот процесс был прозрачным при установке) и если взломают закономерность, на них основанную, то все сгенеренные ключевые пары можно будет отправить в помойку.
Так что нет, АНБ ничего еще не скомпрометировало, просто очередная желтизна
Вот описание
А весь смысл в том, что эти простые числа много где одинаковые по умолчанию (их довольно долго нужно генерить, чтобы этот процесс был прозрачным при установке) и если взломают закономерность, на них основанную, то все сгенеренные ключевые пары можно будет отправить в помойку.
Так что нет, АНБ ничего еще не скомпрометировало, просто очередная желтизна
Нет, комментарий выше правильно излагает суть
geektimes.ru/post/264040/#comment_8838450
geektimes.ru/post/264040/#comment_8838450
Вот очень понятное описание алгоритма Диффи-Хеллмана
https://youtu.be/vFjq9pID4-E
https://youtu.be/vFjq9pID4-E
Вы про дефолтные параметры в серверах типа apache/nginx? Так ssllabs уже давным давно ругается на них, это не новость
А почему бы не увеличить длину с 1024 бит до 4096 бит? Кто-нибудь может подскажет, помогло ли бы это защитить протокол от взлома даже при использовании супер-компьютера?
Или Почему бы не сделать двойную систему шифрования
Шифрование протокола шифрования, так сказать
Или Почему бы не сделать двойную систему шифрования
Шифрование протокола шифрования, так сказать
Сделать то можно что угодно, проблема в том что существует множество серверов и ПО, которые используют алгоритм в текущей реализации и изменить это даже при всем желании быстро нельзя, не говоря уже о том, что АНБ будет противодействовать таким новациям, по крайней мере для американских компаний, на которые оно может оказать давление.
В некоторых странах максимальная длинна ключа ограничена законодательно. Т.о. использование длинного ключа будет нелегальным.
Это при условии, что в АНБ/ФСБ нет недобросовестных сотрудников, которые могут использовать данные, к которым имеют доступ, в личных и преступных целях. Ну и что недобросовестным не становится всё государство.
Знаете, если так рассуждать, то обвинять АНБ в том, что оно скомпрометировало протокол, вообще глупо.
С 4096 просядет конкретно перфоманс. Гугл вон долго тянул с переходом на 2048 из-за этого.
ИМХО, каждый tls-сервер должен самостоятельно генерировать параметры DH. Это же так просто:
openssl dhparam -out dhparam.pem 4096
Вот, кстати, тоже сильно удивился этому. Какой смысл в DH, если параметры генерации ключа уже зашиты…
Только не в неизвестном направлении. Они идут жаловаться тем кто пишет законы и те запрещают использование слов «openssl» и «dhparam» в комбинации с числами больше 512 на одной строке. Большие фирмы против закона не попрут, а значит практически весь трафик будет уязвим перед АНБ. Впрочем, судя по всему, они уже давно так сделали — см. законы об ограничении длины ключа шифрования.
Человек читает ализара и удивляется желтизне?
Там есть набор стандартных кривых, которыми (и только ими) тоже пользуются все:
Пока, конечно, не опубликовано способа, который может ускорить вычисления закрытых ключей, сгенерированных над этими кривыми, но утверждать, что в ECDH/ECDSA совсем нет общих параметров, нельзя.
openssl ecparam -list_curves
Пока, конечно, не опубликовано способа, который может ускорить вычисления закрытых ключей, сгенерированных над этими кривыми, но утверждать, что в ECDH/ECDSA совсем нет общих параметров, нельзя.
Это в первую очередь касается https: там практически не используется эллиптическая крипто (должно быть в сертификатах) а админы нихрена не понимают и не перегенируют ничего.
Можете пояснить что и на каком этапе нужно перегенерировать? Или кинуть «правильный» мануал, с описанием всех шагов?
Вот документация: wiki.mozilla.org/Security/Server_Side_TLS
А вот даже готовый генератор конфигов: mozilla.github.io/server-side-tls/ssl-config-generator
А вот даже готовый генератор конфигов: mozilla.github.io/server-side-tls/ssl-config-generator
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
АНБ скомпрометировало протокол Диффи-Хеллмана?