Max Home IndustryРазница между правильной и неправильной защитой может превратить то, что теоретически безопасно, во что-то практически взломанное. Новые результаты демонстрируют, как возврат к небольшому ключу шифрования может сделать данные доступными для чтения почти всем, у кого есть необходимость — это уязвимость LOGJAM. Но при наличии достаточных ресурсов могут ли государственные органы взломать 1024-битные ключи?
Это новость, но не менее важно то, что при наличии достаточных ресурсов даже большие ключи могут быть взломаны, и предполагается, что АНБ делает это на регулярной основе.
Уязвимость LOGJAM проистекает из ограничения США на продажу по всему миру программного обеспечения для шифрования, которое работает с ключами более 512 бит, так что коды могут быть взломаны. Это ограничение было отменено много лет назад, но программное обеспечение для шифрования, такое как TLS, все еще имело и должно справляться с программным обеспечением, которое не может работать с более чем 512 битами. В результате у многих все еще есть резервные протоколы.
Для начала нам понадобится немного теории, чтобы понять, как работает протокол обмена ключами DHM Диффи-Хеллмана-Меркла. DHM был первым протоколом, который позволил двум сторонам безопасно обмениваться ключами шифрования по открытой сети.
Прежде чем читать дальше, подумайте, насколько хорош протокол DHM. Как можно передать секретный номер при открытом соединении, чтобы номер был известен только отправителю и получателю?
Ответ очень умный.
Алиса и Боб договариваются о большом простом p и числе g — они могут делать это публично или тайно, это не имеет большого значения.
Затем Алиса выбирает число a и отправляет Бобу ga mod p.
Боб выбирает число b и отправляет Алисе gb mod p.
И снова оба значения могут быть переданы по общедоступному Интернету, но Алиса должна хранить в секрете, а Боб — в секрете.
Теперь Алиса вычисляет (gb) mod p — напомним, что только Алиса знает a.
Боб вычисляет (ga) b mod p — и снова только Боб знает b.
Конечно, (ga) b mod p = (gb) a mod p = gab mod p, и поэтому Алиса и Боб имеют один и тот же результат — ключ шифрования.
Причина, по которой ключ шифрования есть только у Алисы и Боба, заключается в том, что внешнему миру известны только значения ga mod p и gb mod p, и нет прямого способа использовать их для формирования gab mod p. Если вы умножите их вместе, вы получите ga + b mod p.
Единственный способ сформировать gab mod p — вывести a или b, а это означает решение:
v = ga mod p
найти.
Это проблема дискретного журнала, и нет известного быстрого способа сделать это, кроме как угадать значения a и посмотреть, дают ли они вам значение v. Если бы у вас была обратная функция, то есть журнал, тогда решение было бы просто a = loggv мод p.
Вся безопасность обмена ключами DHM зависит от сложности вычисления дискретного логарифма, и, несмотря на некоторый прогресс в ускорении работы, это все еще считается проблемой, требующей времени, экспоненциального по количеству битов.
Теперь мы подошли к провалу реализации, обещанному во введении. Информация предполагает, что у АНБ есть проект по чтению зашифрованных данных. Могли ли они использовать квантовый компьютер или они могли решить проблему дискретного логарифмирования?
Последние результаты предлагают гораздо более простое, теоретически более простое решение.
Первый сюрприз заключается в том, что большинство систем DHM используют небольшое количество простых чисел для p. Это не должно иметь никакого значения, потому что протокол позволяет знать p, а проблема дискретного журнала столь же сложна, пока простое число велико. Однако предположим, что использовалось только одно простое число, тогда вы могли бы вычислить полную таблицу для дискретного журнала и просто использовать поиск, чтобы найти a или b. Конечно, вы можете сделать лучше, чем вычисление методом грубой силы, но это основная идея.
Для 512-битного ключа вычисление таблицы возможно всего с несколькими тысячами ядер. Исследователи выполнили эту работу за 7 дней, и в результирующей справочной таблице объемом 2,5 ГБ можно найти дискретный журнал всего за 90 секунд с использованием 24-ядерной машины. Это означает, что 512-битные ключи могут быть взломаны практически любым человеком, имеющим доступ к вычислительному кластеру.
Процедура LOGJAM — это атака типа «злоумышленник в середине», которая сначала заставляет сервер понижать версию до 512 бит, а затем останавливается на 12 секунд, пока вычисляет ключ сеанса. С этого момента человек посередине может перехватывать все сообщения и даже изменять их.
Конечно, реакцией на все это будет переход на 1024-битное шифрование, но исследования показывают, что агентство, располагающее ресурсами государственного уровня, могло бы взломать даже это. Предполагается, что для компиляции таблицы для 1024-битного ключа потребуется 45 миллионов лет. Звучит огромно, но с помощью специального оборудования предприятие стоимостью несколько сотен миллионов долларов могло бы создать стол примерно за год. После создания таблицы терабайтного размера поиск дискретного журнала можно было выполнить за несколько минут с помощью суперкомпьютера.
Все эти оценки основаны на известных алгоритмах и методах. Вполне вероятно, что государственное агентство могло бы найти теоретиков для работы над проблемой и сделать методы более эффективными.
Решение проблемы состоит в том, чтобы либо увеличить размер ключа — 2048 битов сделало бы вычисление таблицы недоступным даже для государственного агентства без каких-либо серьезных теоретических прорывов, либо прекратить использование одних и тех же простых чисел. Генерация огромных простых чисел стоит дорого, но работа с более крупной библиотекой простых чисел затруднит построение таблиц.