Искусственные агенты под наблюдением человека позволили Google DeepMind определить два способа снизить стоимость атаки на криптосистемы RSA 1024 бит. Эта работа, проведенная совместно с криптографами из UC San Diego и Inria, показывает, что атаки на устаревший RSA-1024 требуют меньше вычислений, чем считалось ранее.
RSA — это система шифрования с открытым ключом, надежность которой основана на сложности разложения большого числа на простые множители. Однако Пушмит Кохли, вице-президент Google DeepMind и главный научный сотрудник Google Cloud, призывает оценивать эти результаты в перспективе: «На практике эти результаты касаются только устаревших систем RSA 1024 бит, а современные протоколы шифрования, которые почти повсеместно используют ключи длиной 2048 бит и более, остаются безопасными».
Цифровые подписи и дополнение
Первое открытие касается цифровых подписей и дополнения — заранее установленных данных, которые многие стандарты подписи добавляют к сообщению, чтобы довести его до размера фиксированного блока. Этот механизм был известен тем, что усложняет подделку, но его эффективность против атакующего, который может выбирать, что подписывать, оставалась неясной. DeepMind установил, что всё зависит от доли подписываемого блока, которую контролирует атакующий. Как объясняет Пушмит Кохли, «как только они контролируют примерно половину блока или больше, дополнение больше не обеспечивает никакой защиты».
Согласно научной статье, сопровождающей эту работу, это касается формата PKCS#1 v1.5, используемого интерфейсом подписи PKCS#11 криптографических устройств, таких как аппаратные модули безопасности (HSM).
В тесте, проведенном в изолированной среде, агенты повторно запустили атаку с подделкой, уже описанную в академическом исследовании, на том же 1024-битном ключе. Время вычислений на процессоре сократилось в 3,5 раза. Первая подделка потребовала 391 год-ядро процессорного времени против 1380 лет в исходном исследовании.
Два искусственных агента спроектировали, выполнили и скорректировали вычисления для подделки менее чем за четыре дня, получив около 20 сообщений от исследователя-человека, в основном с одобрениями. Ключ не был факторизован — операция, которую источник оценивает в 500 000–1 000 000 лет-ядер процессорного времени. Когда атакующий контролирует меньшую часть блока, например, 32-байтовый хэш, подделка становится сложнее. Тем не менее, DeepMind утверждает, что нашел алгоритм, который, по их теоретическим оценкам, примерно в 1600 раз эффективнее предыдущего самого эффективного метода для 1024-битных ключей.
Факторизация нескольких ключей
Второе открытие касается факторизации множества RSA-ключей одинакового размера. Атакующий может распределить высокую стоимость единичного первоначального вычисления на все эти ключи. Агенты DeepMind разработали алгоритм, который в среднем делает факторизацию каждого дополнительного 1024-битного ключа примерно в 30 раз дешевле, чем лучший предыдущий подход. Однако эта теоретическая оценка предполагает, что первоначальное вычисление столь же затратно, как факторизация одного ключа, и метод не был реализован на практике.
Исследователи подчеркивают, что атака на подписи не позволяет восстановить закрытый ключ. Для неё требуется заранее около 4 миллиардов запросов на подпись, и она не работает против устройств, которые хэшируют сообщения внутри себя. «Вместе эти результаты показывают, что в новую эру математики и вычислений, поддерживаемых ИИ, мы не можем рассматривать криптографическую сложность как фиксированную гипотезу», — заключает Пушмит Кохли. Он добавляет: «Использование ИИ для строгой проверки наших прежних предположений позволит гарантировать, что современное шифрование останется безопасным».
