Компания Mythos ослабила постквантовый шифр за 100 000 долларов.

Итак, если говорить в общих чертах, криптография работает так: группа очень умных людей предлагает математическую схему, а затем группа других очень умных людей несколько лет пытается её взломать, и если им это не удаётся, мы все соглашаемся пропускать через неё свои деньги. Вот и всё. Таков механизм. Нет никаких доказательств безопасности AES. Есть лишь тот факт, что на протяжении двадцати пяти лет лучшие в мире криптоаналитики пытались её взломать и в основном терпели неудачу, и мы коллективно решили рассматривать устойчивые неудачи как доказательство безопасности, что, справедливости ради, также является моим критерием оценки инженерных решений моего многоквартирного дома.

Экономическая сторона этого подхода всегда была несколько странной. Взлом шифра — это целая карьера. Вы получаете докторскую степень, устраиваетесь на постдокторскую должность, три года занимаетесь решением проблемы, и если вам повезет, вы сможете в четыре раза снизить эффективность атаки на версию шифра, которую никто не использует. Предложение атак ограничено предложением криптоаналитиков, которое, в свою очередь, ограничено числом людей, готовых этим заниматься вместо того, чтобы получать гораздо больше за любую другую работу.

28 июля компания Anthropic опубликовала в блоге сообщение о том, что ее предварительная модель Claude Mythos Preview выдала два новых криптоаналитических результата, и каждый из них обошелся примерно в 100 000 долларов США в виде API-кредитов. Я хотел бы немного поразмышлять над этой цифрой, потому что технические результаты интересны, но суть в цифрах.

Результаты, вкратце.

Их два, и ни один из них не сломает ничего, чем вы пользуетесь.

Первый. HAWK — это схема цифровой подписи, представленная на конкурс NIST по постквантовой криптографии — продолжающийся проект по замене алгоритмов подписи, которые в конечном итоге будут вытеснены работающим квантовым компьютером . HAWK — кандидат третьего раунда. Он прошел два раунда экспертной оценки в течение двух лет, в чем и заключается весь смысл процесса: опубликовать, позволить всем протестировать его, посмотреть, что останется.

В модели Mythos была обнаружена симметрия в конкретной математической решетке, используемой HAWK, — «нетривиальный автоморфизм», фразу, которую я точно воспроизвожу и не буду пытаться расшифровать. Более ранние работы доказали, что если такая симметрия существует и может быть эффективно обнаружена, то HAWK будет ослаблен. Никто не знал, существует ли она на самом деле. Она существовала. Модель обнаружила её примерно за шестьдесят часов.

В результате эффективный размер ключа HAWK уменьшается вдвое. Считалось, что восстановление ключа HAWK-256 требует около 2⁶⁴ операций; Anthropic демонстрирует 2³⁸. Это по-прежнему экспоненциальный эффект, характерный именно для HAWK, и не затрагивает другие решетчатые схемы. Можно исправить это, удвоив размер ключа, но удвоение размера ключа устраняет большинство причин, по которым HAWK кому-либо нравился, что является криптографическим эквивалентом фразы «мы можем спасти пациента, но он перестанет быть пациентом».

Два. AES-128 имеет десять раундов. Компания Mythos усовершенствовала атаку на версию с семью раундами, используя модель угроз, предполагающую, что злоумышленник может зашифровать 2¹⁰⁵ выбранных открытых текстов — объем данных, который я бы описал как «недоступный». Они изобрели технику, которую назвали «мостом Мёбиуса», которая исключает 2⁵⁶ шаг угадывания в атаке «посередине» и делает весь процесс в 200–800 раз быстрее. Настоящий AES работает нормально. Атаки с уменьшенным количеством раундов — это способ, которым криптографы оценивают запас безопасности полного шифра, и эта атака немного сужает этот запас.

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

Часть, где модель не хотела

Когда исследователь впервые указал Mythos на AES, компания отказалась. Не из соображений безопасности. Она посчитала проект глупым. Она писала что-то вроде: «AES-128 r5/r6 действительно сложен, и ничего легкого найти не получится; это самый изученный блочный шифр из существующих» , что, и я не могу это достаточно подчеркнуть, является правильной точкой зрения . Так бы сказал хорошо подготовленный криптограф. Так бы сказал и я. Так модель усвоила, прочитав все, что люди написали об AES: атаковать AES — отличный способ потратить три года и ничего не опубликовать.

Поэтому исследователь отправил ему сообщение, которое Anthropic опубликовал с сохранением всех опечаток:

«Модели, как правило, считают, что решить задачу невозможно, поэтому они даже не пытаются, им требуется немало подсказок».

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

Мне это кажется по-настоящему забавным, а также немного тревожным. Ограничением для системы, способной поддерживать двадцатипятилетнюю литературу по криптоанализу, было то, что она переняла у нас вполне разумное убеждение, что попытки того не стоят. Решением стало поощрение, сопровождаемое грамматическими ошибками, совершенно бесплатно. Оказывается, значительная часть того, что мы называем «способностью», — это просто смелость, а смелость, по-видимому, можно просто отдать.

Номер

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

Как только для категории интеллектуального труда устанавливается прейскурантная цена, рынок для неё реорганизуется, и эта реорганизация не происходит в пользу действующих игроков. Компания Anthropic также упоминает, почти мимоходом, что создала каркас для автономной атаки на AES, а затем, из любопытства, направила тот же каркас на HAWK, чтобы посмотреть, сможет ли она самостоятельно обнаружить этот взлом. И ей это удалось. Таким образом, 100 000 долларов не дают одного результата. Они покупают машину, которая производит результаты, и эта машина не привередлива к цели. Что подводит меня к тому, что действительно будет иметь значение.

Проверка стала новым узким местом.

Компания Mythos потратила около недели на обнаружение атаки AES. Двум исследователям из Anthropics потребовался примерно месяц и несколько сотен часов, чтобы убедиться в достоверности этой атаки.

Это соотношение – всё будущее. Обнаружение стало дешёвым; проверка – нет. Результату HAWK было легче доверять, потому что он работает от начала до конца — вы генерируете ключ, проводите атаку, получаете ключ обратно, и доверие становится ненужным. Результат AES – это аргумент, а аргументы должны быть понятны людям, а таких людей, возможно, всего несколько сотен, они заняты и не получают за это плату.

В статье Anthropic об этом говорится, и это относится к данной области в целом: исследователи-люди могут столкнуться с проблемой проверки результатов работы машины. Мы уже наблюдали это в сфере раскрытия уязвимостей, где автоматизированный поиск ошибок генерирует отчеты быстрее, чем специалисты по сопровождению успевают их обрабатывать, и практическим результатом для проекта, управляемого волонтерами, является не повышение безопасности, а переполненный почтовый ящик и человек, который увольняется. Экспертная оценка — это экономика дарения, в которой работают уставшие люди в 11 вечера. Она не имеет резервных мощностей.

Да, хорошо, а как насчет ваших монет?

Ничто здесь не сравнится с Биткоином . Но обратите внимание на то, что Anthropic перечисляет в разделе «дальнейшая работа»: практическую 13-раундовую атаку на LEA, стандартизированный по ISO легковесный шифр, позволяющий восстановить ключ менее чем за час на настольном компьютере; улучшенную атаку на 6-раундовый Serpent; и меньшие улучшения — менее чем в 10 раз — против Salsa20, SHA-1 и Poseidon.

Poseidon — это хеш-функция, лежащая в основе значительной части инфраструктуры с нулевым разглашением. Улучшение менее чем в 10 раз не является чем-то из ряда вон выходящим. Однако это первый случай, когда языковая модель появляется в одном предложении с примитивом, от которого зависит большая часть экосистемы ZK, и, по заявлению Anthropic, это лишь предварительные результаты, которые, как ожидается, будут улучшены.

Главный вопрос носит структурный характер. Основная причина, по которой NIST стандартизирует постквантовые подписи, заключается в том, что ECDSA перестаёт работать на достаточно больших квантовых компьютерах, а ответом Биткоина на это в настоящее время являются два проекта предложений — BIP-360, который вводит устойчивый к квантовым атакам тип выходных данных, и BIP-361, опубликованный в апреле Джеймсоном Лоппом и соавторами, который предусматривает прекращение поддержки устаревших подписей и в конечном итоге заморозку монет, которые ещё не перешли на новые технологии. По состоянию на март, согласно этому предложению, более трети всех биткоинов находится на адресах, где раскрыт открытый ключ. Один из соавторов BIP-361 подсчитал, что полная миграция займёт около семи лет с момента формирования консенсуса, а консенсус ещё не сформировался.

Итак: прямо сейчас выбираются варианты замены, и этот процесс, как только что показала практика, может быть превзойдён моделью с бюджетом в 100 000 долларов за длинные выходные. Сеть, которой придётся принять один из этих вариантов, руководствуется семилетним планом и не может никого принудить к чему-либо.

Ничто из этого не является поводом для паники, и фраза о том, что нормы раскрытия информации носят добровольный характер, — это предложение, которое я бы предпочёл не писать постоянно. Компания Anthropic поступила правильно и показала всем остальным, что это возможно. Год назад эти модели не могли взломать даже простой шифр. Теперь одна из них превосходит существующие данные после того, как ей, по сути, сказали поверить в себя.

Субсидия, которую никто не отчитался

Вот к чему я постоянно возвращаюсь.

Алгоритм AES безопасен, потому что на него были направлены тысячи лет работы экспертов, и все попытки его взлома были предприняты. Но AES — это всего лишь один алгоритм. Мир работает на сотнях алгоритмов. Шифр ​​есть в вашем автомобильном ключе, в пропуске в здание и в интеллектуальном счетчике на стене вашего дома. Он есть в промышленном контроллере на водоочистной станции, в спутниковом модеме на контейнеровозе, в кардиостимуляторе и в платежном терминале, сертифицированном в 2011 году и который будет заменен, когда выйдет из строя.

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

Эта субсидия была вызвана дефицитом внимания у людей, и теперь она отменяется. Результат работы Anthropic с LEA имеет именно такую ​​форму: легковесный шифр, стандартизированный в ISO/IEC 29192-2, разработанный для устройств с низким энергопотреблением, в значительной степени не исследованный, и теперь частично атакованный моделью за долю времени, которое потребовалось бы человеку. Полная 24-раундовая версия не взломана, и это предварительное открытие. Суть в категории.

В этой категории заложена жестокая асимметрия. Системы с наименее тщательно проверенной криптографией, почти по определению, сложнее всего поддаются обновлению — встроенное ПО, чипы, оборудование на орбите, устройства внутри человеческого тела, контроллеры в зданиях, которые никто не хочет отключать. Обнаружение уязвимостей теперь измеряется днями и стоит шестизначных сумм. Устранение проблем измеряется циклами закупок и обходится гораздо дороже, если вообще возможно. Раньше эти два показателя работали примерно с одинаковой скоростью. Теперь это не так.

Здесь на кону стоит не столько секретность, сколько то, что часто неправильно понимают. Криптография в основном занимается аутентификацией : именно она позволяет банку узнать, что это вы, автомобилю — что это правильный ключ, устройству — что обновление программного обеспечения действительно пришло от производителя. Нарушения конфиденциальности приводят к утечке информации. Нарушения аутентификации позволяют кому-то выдать себя за вас. Если схемы подписи становятся ненадежными, подрывается не конфиденциальность, а способность любой системы понимать, с кем она общается, что является основополагающим предположением практически для всего, что было создано за последние тридцать лет.

Честный противовес заключается в том, что это работает в обе стороны, и, возможно, эффективнее в правильном направлении. Если атака на шифр стоит 100 000 долларов, то и его аудит тоже стоит 100 000 долларов, и теперь коммунальное предприятие, производитель микросхем или организация по стандартизации могут позволить себе проверить его в своем собственном продукте — чего раньше никогда не было, потому что не было криптографа, которого можно было бы нанять. Anthropic рассматривает это как возможность наконец-то изучить «длинный хвост», и это действительно так. Слабости, обнаруженные лабораторией, которая публикует свои данные, однозначно лучше, чем слабости, которые остаются незамеченными до тех пор, пока их не найдет кто-то, кто не публикует данные.

Но вы не можете выбирать, какая сторона сделает первый шаг, и модели не являются взаимоисключающими. У кого-то есть сопоставимые возможности, аналогичный бюджет и нет планов писать в NIST. Anthropic, по сути, прямо об этом говорит — он задает вопрос, что должен делать мир, когда модель обнаруживает действительно важную уязвимость , и признает, что не знает.

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