Отчёт об уязвимости, раздвигающий границы криптографии

Это перевод Pushing the boundaries of cryptography in a security vulnerability report. Автор: Реймонд Чен.

К нам поступил отчёт об уязвимости в безопасности, в котором сообщалось, что автор отчёта сделал инновационное открытие в криптографии. В частности, он утверждал, что обнаружил эффективный способ решения задачи факторизации больших целых чисел, используемых в крипто-алгоритме RSA.

Если бы это было правдой, это, действительно, стало бы выдающимся достижением. Однако описание алгоритма, хотя и полностью верное математически (да, я действительно его всё прочёл и разобрал), не выдавало эффективный алгоритм. Оно сводилось к попытке найти коллизию среди множества возможных значений, размер которого пропорционален меньшему коэффициенту, с дополнительной оптимизацией по уменьшению количества вычислений до квадратного корня из этого пространства (мне показалось, что именно эта дополнительная оптимизация и стала для автора "инновационным открытием").

Да, геометрическое снижение сложности - это хорошо, но оно меркнет в сравнении с экспоненциальным ростом сложности.

В 2013 году web-браузеры требовали применения минимум RSA-2048. Это означает, что возможное множество значений для подбора коллизии примерно 2¹⁰²⁴, и парадокс дней рождения говорит нам о том, что с вероятностью 50% коллизия будет найдена при переборе 2⁵¹² чисел. Применение указанной оптимизации снижает это число до 2²⁵⁶.

Но, позвольте, это даже хуже чем генерация списка всех возможных GUID. GUID то, по крайней мере, "всего" 2¹²⁸.

Такой алгоритм факторизации числа RSA-2048 потребует хранения 2²⁵⁶ значений. Это квадрат от числа всех возможных GUID.

Ранее мы выяснили, что для хранения всех возможных GUID на SSD дисках нам потребуется примерно 100 планет размером с Землю. Следовательно, для хранения всех значения для работы указанного алгоритма потребуется... эммм... существенно больше.

Современные оценки массы нашей Галактики (Млечный путь) оценивают её массу в 4.5 × 10¹² Солнц, или (округляя) 10¹⁹ Земли. Если нам требовалось 100 планет Земля для хранения 2¹²⁸ 128-битных значений, то для хранения 2²⁵⁶ 1024-битных значений нам потребуется 2¹³² × 100 ≅ 10⁴¹ планет Земля или ≅ 10²² Галактик размером с Млечный путь.

Этот метод не кажется практичным.

Автор, однако, не согласился с таким анализом и настаивал, что при тестах на небольших числах время работы подбора было линейным по показателю. "Мне удалось факторизовать числа размером до 64 бит, при этом факторизация самого большого числа заняла меньше секунды".

Мы решили воспользоваться советом от математика, которому приходилось иметь дело с алгоритмами факторизации, отправленными ему разными чудаками, и предложили автору использовать его продвинутый алгоритм для факторизации одного из наших корневых сертификатов.

Автор ответил: "Я знаю, что вы пытаетесь провернуть, но я вам говорю, что не могу запустить алгоритм для больших чисел на моем ноутбуке. Но вы можете запустить его на одном из своих более мощных компьютеров. Я продемонстрировал, что алгоритм является линейным по длине ключа, и мой личный недостаток доступа к суперкомпьютерам не умаляет этого факта. Я связался с СМИ об этом открытии, но, к счастью для вас, они, похоже, не заинтересованы, что дает вам больше времени для решения проблемы".

Если бы алгоритм был действительно линейным по показателю, то переход от 64-битных чисел к 2048-битным потребовал бы больше времени всего в 32 раза. Т.е. секундное время работы увеличится до 32 секунд. Ну так дай своему алгоритму поработать минуту. Пять минут, чтобы быть уверенным. Ваш ноутбук, безусловно, справится с этим.

Но вместо ответа мы решили промолчать. Никогда не боритесь с свиньёй. Вы испачкаетесь, а свинье это понравится.