При шифровании сообщения открытым текстом называют незашифрованное сообщение, а шифротекстом - зашифрованное. Следовательно, шифр состоит из двух функций: функция шифрования преобразует открытый текст в шифротекст, а функция расшифрования вновь превращает шифротекст в открытый текст. Однако мы нередко будем говорить «шифр», подразумевая именно «шифрование». Например, на рис. 1-1 показан шифр E в виде блока, который принимает на вход открытый текст P и ключ K, а на выходе выдаёт шифротекст C. Это отношение я буду записывать как C = E(K, P). Аналогично, когда шифр работает в режиме расшифрования, я буду писать D(K, C).

Рисунок 1-1. Базовые операции шифрования и расшифрования

Примечание. У некоторых шифров шифротекст имеет тот же размер, что и открытый текст; у других шифротекст немного длиннее. Однако шифротекст никогда не может быть короче открытого текста.

Классические шифры появились раньше компьютеров и потому работают с буквами, а не с битами, что делает их значительно проще современного шифра вроде Data Encryption Standard. Например, в Древнем Риме или во время Первой мировой войны нельзя было воспользоваться вычислительной мощностью компьютерной микросхемы, чтобы перемешать сообщение: всё приходилось делать лишь ручкой и бумагой. Классических шифров существует много, но самые известные из них - шифр Цезаря и шифр Виженера.

Шифр Цезаря получил своё название потому, что римский историк Светоний сообщал о его использовании Юлием Цезарем. Этот шифр шифрует сообщение, сдвигая каждую букву на три позиции вперёд по алфавиту и возвращаясь к A, если при сдвиге достигнута Z. Например, ZOO шифруется как CRR, FDHVDU расшифровывается как CAESAR и так далее, как показано на рис. 1-2. В числе 3 нет ничего особенного; просто такой сдвиг легче вычислить в уме, чем сдвиг на 11 или 23 позиции.

Рисунок 1-2. Шифр Цезаря

Шифр Цезаря чрезвычайно легко взломать: чтобы расшифровать данный шифротекст, достаточно сдвинуть буквы на три позиции назад и получить открытый текст. Тем не менее во времена Красса и Цицерона шифр Цезаря, возможно, был достаточно стойким. Поскольку секретного ключа в нём нет (сдвиг всегда равен 3), пользователи шифра Цезаря исходили из того, что злоумышленники неграмотны или недостаточно образованны, чтобы во всём разобраться, - сегодня такое предположение гораздо менее реалистично. (На самом деле в 2006 году итальянская полиция арестовала босса мафии после расшифрования записок на клочках бумаги, зашифрованных одним из вариантов шифра Цезаря: например, ABC в нём превращалось в 456, а не в DEF.)

Можно ли сделать шифр Цезаря более стойким? Можно представить его версию, в которой вместо постоянного значения 3 используется секретная величина сдвига, но это мало чем поможет: злоумышленник сможет перебрать все 25 возможных значений, пока расшифрованное сообщение не приобретёт смысл.

Потребовалось около 1500 лет, чтобы шифр Цезаря получил существенное усовершенствование в виде шифра Виженера, созданного в XVI веке итальянцем Джованом Баттистой Беллазо. Название «Виженер» происходит от имени француза Блеза де Виженера, который в XVI веке изобрёл другой шифр, однако из-за исторически сложившейся ошибочной атрибуции за этим шифром закрепилось имя Виженера. Как бы то ни было, шифр Виженера приобрёл популярность и позднее применялся, помимо прочих, войсками Конфедерации во время Гражданской войны в США и швейцарской армией во время Первой мировой войны.

Шифр Виженера похож на шифр Цезаря, но буквы в нём сдвигаются не на три позиции, а на значения, заданные ключом - набором букв, представляющих числа в соответствии с положением букв в алфавите. Например, если ключ равен DUH, буквы открытого текста сдвигаются на 3, 20 и 7 позиций, поскольку D находится на три буквы дальше A, U - на 20 букв дальше A, а H - на семь букв дальше A. Последовательность 3, 20, 7 повторяется, пока не будет зашифрован весь открытый текст. Например, при использовании ключа DUH слово CRYPTO будет зашифровано как FLFSNV: C сдвигается на три позиции и превращается в F, R сдвигается на 20 позиций и превращается в L и так далее. На рис. 1-3 этот принцип показан при шифровании предложения THEY DRINK THE TEA.

Рисунок 1-3. Шифр Виженера

Шифр Виженера явно надёжнее шифра Цезаря, однако взломать его всё ещё довольно легко. Первый шаг при расшифровании - определить длину ключа. Возьмём пример с рис. 1-3, где THEY DRINK THE TEA шифруется как WBLBXYLHRWBLWYH с помощью ключа DUH. (Пробелы обычно удаляют, чтобы скрыть границы слов.) Обратите внимание: в шифротексте WBLBXYLHRWBLWYH трёхбуквенная группа WBL встречается дважды с интервалом в девять букв. Это наводит на мысль, что одно и то же трёхбуквенное слово было зашифровано с одинаковыми величинами сдвига и оба раза дало WBL. После этого криптоаналитик может заключить, что длина ключа равна либо девяти, либо делителю девяти (то есть трём). Более того, он может предположить, что повторяющееся трёхбуквенное слово - это THE, и тем самым определить DUH как возможный ключ шифрования.

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

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

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

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

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

Большинство классических шифров заменяет каждую букву другой буквой - иными словами, выполняет подстановку. В шифрах Цезаря и Виженера подстановка представляет собой сдвиг в алфавите, хотя алфавит или набор символов может быть иным: вместо английского алфавита может использоваться арабский, а вместо букв, например, слова, числа или идеограммы. Представление или кодирование информации - отдельный вопрос, по большей части не имеющий отношения к безопасности. (Мы рассматриваем латинские буквы, поскольку именно их используют классические шифры.)

Подстановкой в шифре не может быть любая произвольная подстановка. Это должна быть перестановка - такое переупорядочение букв от A до Z, при котором у каждой буквы имеется единственный обратный образ. Например, подстановка, преобразующая буквы A, B, C и D соответственно в C, A, D и B, является перестановкой, поскольку каждой букве соответствует ровно одна другая буква. Но подстановка, преобразующая A, B, C, D в D, A, A, C, перестановкой не является, поскольку и B, и C отображаются в A. При перестановке у каждой буквы имеется ровно один обратный образ.

Однако не всякая перестановка безопасна. Чтобы обеспечивать безопасность, перестановка шифра должна удовлетворять трём критериям:

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

• Разные ключи должны приводить к разным перестановкам. В противном случае расшифровать сообщение без ключа становится легче: если разные ключи дают одинаковые перестановки, значит, различных ключей меньше, чем различных перестановок, а следовательно, при расшифровании без ключа нужно перебрать меньше вариантов. В шифре Виженера каждая буква ключа определяет подстановку; существует 26 различных букв и столько же различных перестановок.

• Перестановка, грубо говоря, должна выглядеть случайной. После выполнения перестановки в шифротексте не должно оставаться закономерностей, поскольку они делают перестановку предсказуемой для злоумышленника, а значит, менее стойкой. Например, подстановка в шифре Виженера вполне предсказуема: если для некоторого смещения вы установили, что A шифруется как F, можно заключить, что величина сдвига равна 5, а также узнать, что B шифруется как G, C - как H и так далее. Но при случайно выбранной перестановке знание того, что A шифруется как F, сообщило бы вам лишь одно: B не шифруется как F.

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

Предположим, у нас есть безопасная перестановка, которая преобразует, например, A в X, B в M, а N в L. Тогда слово BANANA шифруется как MXLXLX, причём каждое вхождение A заменяется на X. Таким образом, применение одной и той же перестановки ко всем буквам открытого текста раскрывает все повторяющиеся буквы. Анализируя эти повторы, вы, возможно, не узнаете сообщение целиком, но всё же получите некоторую информацию о нём. В примере с BANANA ключ не нужен, чтобы догадаться: в трёх позициях с X в открытом тексте стоит одна и та же буква, а в двух позициях с L - другая общая буква. Если известно, что сообщение - название фрукта, можно определить, что это BANANA, а не CHERRY, LYCHEE или название другого фрукта из шести букв.

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

Частотный анализ можно сделать бесполезным, если шифр Виженера будет шифровать только открытые тексты той же длины, что и ключ. Но даже тогда останется ещё одна проблема: многократное использование одного ключа раскрывает сходство между открытыми текстами. Например, при ключе KYN слова TIE и PIE шифруются соответственно как DGR и ZGR. Оба шифротекста оканчиваются одинаковыми двумя буквами GR, показывая, что последние две буквы обоих открытых текстов также совпадают. В безопасном шифре обнаружить такие закономерности должно быть невозможно.

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

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

Вспомним, что для безопасности перестановка шифра должна выглядеть случайной. Конечно, лучший способ выглядеть случайной - действительно быть случайной, то есть выбирать каждую перестановку случайно из множества всех перестановок. А выбирать есть из чего. В случае английского алфавита из 26 букв существует приблизительно 2^88 перестановок:

Здесь восклицательный знак (!) обозначает факториал, который определяется следующим образом:

(Чтобы понять, откуда берётся это число, посчитайте перестановки как списки букв в изменённом порядке: для первой буквы имеется 26 вариантов, затем 25 вариантов для второй, 24 для третьей и так далее.) Это огромное число: оно имеет тот же порядок величины, что и число атомов в человеческом теле. Но классические шифры способны использовать лишь малую долю этих перестановок, а именно те, для которых требуются простые операции (например, сдвиги) и существует короткое описание (вроде короткого алгоритма или небольшой таблицы поиска). Проблема в том, что безопасная перестановка не может одновременно удовлетворять обоим этим ограничениям.

Безопасные перестановки можно получать с помощью простых операций: выбрать случайную перестановку, представить её таблицей из 25 букв (этого достаточно для представления перестановки 26 букв, поскольку 26-я определяется по отсутствующему значению) и применять, находя буквы в этой таблице. Но тогда описание уже не будет коротким. Например, для описания десяти разных перестановок потребуется 250 букв вместо всего десяти букв, используемых в шифре Виженера.

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

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

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

Одноразовый блокнот принимает открытый текст P и случайный ключ K той же длины, что и P, и создаёт шифротекст C, определяемый как

где C, P и K - битовые строки одинаковой длины, а xor - побитовая операция исключающего ИЛИ (XOR), определяемая так: 0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1, 1 xor 1 = 0.

Примечание. Я представляю одноразовый блокнот в его обычной форме, работающей с битами, однако его можно приспособить и к другим символам. Например, при работе с буквами получится вариант шифра Цезаря, в котором индекс сдвига выбирается случайно для каждой буквы.

Расшифрование в одноразовом блокноте полностью совпадает с шифрованием: это всего лишь операция XOR, P = C xor K. Действительно, можно проверить, что C xor K = P xor K xor K = P, поскольку операция XOR ключа K с самим собой даёт строку из одних нулей 000...000. Вот и всё - даже проще шифра Цезаря.

Например, если P = 01101101, а K = 10110100, можно вычислить следующее:

При расшифровании P восстанавливается следующим вычислением:

Важно, что одноразовый блокнот можно использовать один раз: каждый ключ K следует применять лишь однократно. Если один и тот же K используется для шифрования P_1 и P_2 в C_1 и C_2, то перехватчик сможет вычислить:

Таким образом, перехватчик узнает XOR-разность P_1 и P_2 - сведения, которые должны оставаться секретными. Более того, если известно хотя бы одно сообщение с открытым текстом, можно восстановить второе.

Одноразовый блокнот крайне неудобен в использовании, поскольку требует ключа той же длины, что и открытый текст, и нового случайного ключа для каждого нового сообщения или набора данных. Чтобы зашифровать жёсткий диск объёмом 1 Тбайт, для хранения ключа понадобится ещё один диск объёмом 1 Тбайт! Тем не менее одноразовый блокнот применялся на протяжении всей истории: британским Управлением специальных операций во время Второй мировой войны, советскими разведчиками, Агентством национальной безопасности США (NSA); в отдельных ситуациях его используют и сегодня. (Я слышал о швейцарских банкирах, которые не смогли договориться о шифре, которому доверяли бы обе стороны, и в итоге воспользовались одноразовыми блокнотами, но не советую так поступать.)

Хотя одноразовый блокнот непрактичен, важно понимать, благодаря чему он безопасен. В 1940-х годах американский математик Клод Шеннон доказал: чтобы добиться совершенной секретности, ключ одноразового блокнота должен быть не короче сообщения. Идея доказательства довольно проста. Мы предполагаем, что злоумышленник обладает неограниченными возможностями и поэтому способен перебрать все ключи. Цель шифрования состоит в том, чтобы при наличии некоторого шифротекста злоумышленник не мог исключить ни один возможный открытый текст.

Интуитивное объяснение совершенной секретности одноразового блокнота таково: если K случаен, то получившийся C выглядит для злоумышленника столь же случайным, как и K, поскольку XOR случайной строки с любой фиксированной строкой даёт случайную строку. Чтобы убедиться в этом, рассмотрим вероятность получить 0 в качестве первого бита случайной строки (она равна 1/2). Какова вероятность, что результат операции XOR случайного бита со вторым битом будет равен 0? Верно, снова 1/2. Тот же аргумент можно последовательно применить к битовым строкам любой длины. Таким образом, шифротекст C выглядит случайным для злоумышленника, не знающего K, поэтому получить из C какие-либо сведения о P буквально невозможно даже злоумышленнику, располагающему неограниченным временем и вычислительной мощностью. Иными словами, знание шифротекста не сообщает об открытом тексте совершенно ничего, кроме его длины, - почти точное определение безопасного шифра.

Например, если длина шифротекста равна 128 битам (а значит, длина открытого текста также равна 128 битам), существует 2^128 возможных шифротекстов; следовательно, с точки зрения злоумышленника должно существовать 2^128 возможных открытых текстов. Но если возможных ключей меньше 2^128, злоумышленник сможет исключить некоторые открытые тексты. Например, если длина ключа составляет лишь 64 бита, злоумышленник сможет определить 2^64 возможных открытых текстов и исключить подавляющее большинство 128-битных строк. Он не узнает, чем является открытый текст, но узнает, чем он не является, а значит, секретность шифрования окажется несовершенной.

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

ВЕРОЯТНОСТЬ В КРИПТОГРАФИИ

Вероятность - это число, выражающее правдоподобие, или шанс, наступления некоторого события. Она задаётся числом от 0 до 1, где 0 означает «никогда», а 1 - «всегда». Чем выше вероятность, тем больше шанс. Во многих объяснениях вероятности приводится пример с белыми и красными шарами в мешке и вероятностью вытянуть шар того или иного цвета.

В криптографии вероятности часто используются для измерения шансов на успех атаки: сначала подсчитывается число успешных событий (например, событие «найти правильный секретный ключ»), а затем общее число возможных событий (например, при n-битных ключах общее число ключей равно 2^n). В этом примере вероятность того, что случайно выбранный ключ окажется правильным, равна 1/2^n: это отношение числа успешных событий (один секретный ключ) к числу возможных событий (2^n возможных ключей). Для распространённых длин ключа, таких как 128 и 256 бит, число 1/2^n пренебрежимо мало.

Вероятность того, что событие не произойдёт, равна 1 - p, где p - вероятность события. Следовательно, вероятность получить неправильный ключ в нашем примере равна 1 - 1/2^n - числу, очень близкому к 1, что означает почти полную уверенность.

Классические шифры небезопасны, а совершенно безопасный шифр вроде одноразового блокнота непрактичен. Поэтому, если мы хотим получить безопасные и пригодные к использованию шифры, придётся немного поступиться безопасностью. Но что в действительности означает «безопасный», помимо очевидного и неформального утверждения «перехватчики не могут расшифровать защищённые сообщения»?

Шифр безопасен, если даже при наличии большого количества пар «открытый текст - шифротекст» невозможно ничего узнать о поведении шифра при его применении к другим открытым текстам или шифротекстам. Это порождает новые вопросы:

• Как злоумышленник получает эти пары? Насколько большим должно быть «большое количество»? Всё это определяется моделями атак - предположениями о том, что злоумышленник может и чего не может делать.

• Что именно можно «узнать» и о каком «поведении шифра» идёт речь? Это определяется целями безопасности - описаниями того, что считается успешной атакой.

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

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

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

• Дать пользователям ориентиры, позволяющие понять, безопасно ли применять шифр в их среде.

• Дать подсказки криптоаналитикам, пытающимся взломать шифры, чтобы они могли определить, допустима ли конкретная атака. Атака допустима только в том случае, если она осуществима в рассматриваемой модели.

Модели атак не обязаны точно совпадать с реальностью; они являются приближениями. Как выразился статистик Джордж Э. П. Бокс: «Все модели неверны; практический вопрос состоит в том, насколько неверной должна быть модель, чтобы перестать приносить пользу». Чтобы быть полезной в криптографии, модель атаки должна как минимум охватывать то, что злоумышленники действительно могут сделать для атаки на шифр. Полезно, когда модель переоценивает возможности злоумышленников, поскольку это помогает предвидеть будущие методы атак, - выживают только параноидальные криптографы. Плохая модель недооценивает злоумышленников и создаёт ложную уверенность в шифре, выставляя его безопасным в теории, хотя в действительности он небезопасен.

Во всех моделях принимается принцип Керкгоффса, согласно которому безопасность шифра должна зависеть только от секретности ключа, а не от секретности самого шифра. Сегодня, когда шифры и протоколы имеют открытые спецификации и используются всеми, это может показаться очевидным. Но исторически нидерландский лингвист Огюст Керкгоффс говорил о военных шифровальных машинах, специально созданных для определённой армии или подразделения. В своём эссе 1883 года «La Cryptographie Militaire», где он перечислил шесть требований к военной системе шифрования, Керкгоффс писал: «Система не должна требовать секретности и может быть похищена противником, не причинив неприятностей».

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

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

Существует несколько разных моделей атак на чёрный ящик. Ниже они перечислены от самой слабой к самой сильной с описанием возможностей злоумышленников в каждой модели:

• Атаки только по шифротексту (ciphertext-only attacks, COA). Злоумышленники наблюдают шифротексты, но не знают соответствующих открытых текстов и способа их выбора. В модели COA злоумышленники пассивны и не могут выполнять запросы шифрования или расшифрования.

• Атаки по известному открытому тексту (known-plaintext attacks, KPA). Злоумышленники наблюдают шифротексты и знают соответствующие открытые тексты. Таким образом, в модели KPA злоумышленник получает список пар «открытый текст - шифротекст», причём предполагается, что открытые тексты выбраны случайно. KPA - модель пассивного злоумышленника.

• Атаки с выбранным открытым текстом (chosen-plaintext attacks, CPA). Злоумышленники могут выполнять запросы шифрования для выбранных ими открытых текстов и наблюдать получившиеся шифротексты. Эта модель описывает ситуации, в которых злоумышленники могут выбрать весь шифруемый открытый текст или его часть, а затем увидеть шифротексты. В отличие от COA и KPA, являющихся пассивными моделями, в CPA злоумышленники активны, поскольку они воздействуют на процесс шифрования, а не просто пассивно прослушивают обмен.

• Атаки с выбранным шифротекстом (chosen-ciphertext attacks, CCA). Злоумышленники могут как шифровать, так и расшифровывать, то есть выполнять запросы шифрования и запросы расшифрования (для шифротекстов, отличных от целевого). Модель CCA сначала может показаться нелепой - если вы можете расшифровывать, что ещё вам нужно? Но, как и CPA, она предназначена для описания ситуаций, в которых злоумышленники способны некоторым образом повлиять на шифротекст, а позднее получить доступ к открытому тексту. Кроме того, одного расшифрования не всегда достаточно для взлома системы. Например, некоторые устройства защиты видео позволяют злоумышленникам выполнять запросы шифрования и расшифрования с помощью микросхемы устройства, однако в такой ситуации злоумышленникам нужен ключ, чтобы распространять его дальше; тогда возможность расшифровывать «бесплатно» недостаточна для взлома системы.

В описанных моделях наблюдаемые и запрашиваемые шифротексты не возникают бесплатно. Каждый шифротекст является результатом вычисления функции шифрования. Это означает, например, что получение 2^N пар «открытый текст - шифротекст» посредством запросов шифрования требует примерно столько же вычислений, сколько перебор 2^N ключей. При оценке стоимости атаки необходимо учитывать стоимость запросов.

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

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

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

До сих пор я неформально определял цель безопасности словами «о поведении шифра невозможно ничего узнать». Чтобы превратить эту идею в строгое математическое определение, криптографы выделяют две цели безопасности, соответствующие разным представлениям о том, что значит узнать нечто о поведении шифра:

• Неразличимость (indistinguishability, IND). Шифротексты должны быть неотличимы от случайных строк. Обычно это иллюстрируют воображаемой игрой: если злоумышленник выбирает два открытых текста, а затем получает шифротекст одного из них, выбранного случайно, он не должен суметь определить, какой открытый текст был зашифрован, даже выполняя запросы шифрования для этих двух открытых текстов (и запросы расшифрования, если рассматривается модель CCA, а не CPA).

• Неподатливость (nonmalleability, NM). Имея шифротекст C_1 = E(K, P_1), должно быть невозможно создать другой шифротекст C_2, соответствующий открытый текст P_2 которого содержательно связан с P_1 (например, создать P_2, равный P_1 xor 1 или P_1 xor X для некоторого известного значения X). Удивительно, но одноразовый блокнот податлив: имея шифротекст C_1 = P_1 xor K, можно определить C_2 = C_1 xor 1, и это будет допустимый шифротекст для P_2 = P_1 xor 1 при том же ключе K. Вот тебе и совершенный шифр.

Далее я рассмотрю эти цели безопасности в контексте разных моделей атак.

Цели безопасности полезны лишь в сочетании с моделью атаки. Согласно принятому соглашению, понятие безопасности записывается как ЦЕЛЬ-МОДЕЛЬ. Например, IND-CPA обозначает неразличимость при атаке с выбранным открытым текстом, NM-CCA - неподатливость при атаке с выбранным шифротекстом и так далее. Начнём с целей безопасности в отношении злоумышленника.

Важнейшее понятие безопасности - IND-CPA, называемое также семантической безопасностью. Оно выражает интуитивную идею: пока ключ остаётся секретным, шифротексты не должны раскрывать никакой информации об открытых текстах. Чтобы обеспечить безопасность IND-CPA, шифрование должно возвращать разные шифротексты при двух вызовах для одного и того же открытого текста; в противном случае злоумышленник сможет выявить одинаковые открытые тексты по их шифротекстам, что противоречит определению, согласно которому шифротексты не должны раскрывать никакой информации. Но обратите внимание: даже схема, безопасная в смысле IND-CPA, неизбежно раскрывает один фрагмент информации об открытом тексте - его длину или хотя бы приблизительную длину. Поэтому шифровать сжатые данные, как правило, не стоит: размер сжатых данных способен раскрыть сведения об исходных данных.

Один из способов обеспечить безопасность IND-CPA - использовать рандомизированное шифрование. Как следует из названия, оно вносит случайность в процесс шифрования и при повторном шифровании одного открытого текста возвращает разные шифротексты. Тогда шифрование можно выразить как C = E(K, R, P), где R - свежие случайные биты. Однако расшифрование остаётся детерминированным: вычислив D(K, R, C), вы всегда должны получить P независимо от значения R.

Что произойдёт, если шифрование не рандомизировано? В игре IND, описанной в разделе «Цели безопасности», злоумышленник выбирает два открытых текста P_1 и P_2 и получает шифротекст одного из них, но не знает, какому открытому тексту он соответствует. Иными словами, злоумышленник получает C_i = E(K, P_i) и должен угадать, равно ли i единице или двум. В модели CPA он может выполнить запросы шифрования, чтобы определить и C_1 = E(K, P_1), и C_2 = E(K, P_2). Если шифрование не рандомизировано, достаточно проверить, равен ли C_i значению C_1 или C_2, чтобы определить зашифрованный открытый текст и тем самым выиграть игру IND. Следовательно, рандомизация играет ключевую роль в понятии IND-CPA.

Если у вас нет генератора псевдослучайных чисел, безопасность IND-CPA всё же можно получить с помощью схемы шифрования, которой вместо случайного непредсказуемого значения требуется одноразовое число nonce (number used only once). Для каждого нового вызова шифрования nonce должно быть уникальным. Подойдёт даже простой счётчик (1, 2, 3, ...). Например, AES-CTR (блочный шифр AES, используемый в режиме CTR) безопасен в смысле IND-CPA, если его дополнительный вход - nonce - уникален. В отличие от некоторых схем рандомизированного шифрования, где случайность лишь является частью процесса шифрования, алгоритмам с nonce это значение необходимо для расшифрования.

Примечание. При рандомизированном шифровании шифротекст должен быть немного длиннее открытого текста, чтобы одному открытому тексту мог соответствовать не один шифротекст. Например, если каждому открытому тексту соответствуют 2^64 возможных шифротекстов, шифротекст должен быть как минимум на 64 бита длиннее открытого текста.

В одной из простейших конструкций семантически безопасного шифра используется детерминированный генератор случайных битов (deterministic random bit generator, DRBG) - алгоритм, который по некоторому секретному значению возвращает биты, выглядящие случайными:

Здесь R - строка, случайно выбираемая при каждом новом шифровании и передаваемая DRBG вместе с ключом (K || R обозначает строку, в которой за K следует R). Этот подход напоминает одноразовый блокнот: вместо выбора случайного ключа той же длины, что и сообщение, мы используем генератор случайных битов, чтобы получить строку, выглядящую случайной.

Доказательство безопасности этого шифра в смысле IND-CPA просто, если предположить, что DRBG выдаёт случайные биты. Оно проводится от противного: если вы можете отличить шифротекст от случайной строки, то есть отличить DRBG(K || R) xor P от случайной строки, значит, вы можете отличить от случайной строки и DRBG(K || R). Вспомним, что модель CPA позволяет получать шифротексты для выбранных значений P, поэтому можно выполнить XOR значения P со значением DRBG(K || R) xor P и получить DRBG(K || R). Но здесь возникает противоречие, поскольку изначально мы предположили, что DRBG(K || R) нельзя отличить от случайной строки и что DRBG выдаёт случайные строки. Поэтому мы заключаем, что шифротексты нельзя отличить от случайных строк, а следовательно, шифр безопасен.

Примечание. В качестве упражнения попробуйте определить, каким ещё понятиям безопасности удовлетворяет шифр E(K, R, P) = (DRBG(K || R) xor P, R). Является ли он NM-CPA? IND-CCA? Ответы вы найдёте в следующем разделе.

Вы узнали, что модели атак, такие как CPA и CCA, объединяются с целями безопасности, такими как NM и IND, образуя понятия безопасности NM-CPA, NM-CCA, IND-CPA и IND-CCA. Как эти понятия связаны между собой? Можно ли доказать, что удовлетворение понятию X влечёт удовлетворение понятию Y?

Некоторые связи очевидны: IND-CCA влечёт IND-CPA, а NM-CCA влечёт NM-CPA, поскольку всё, что может сделать злоумышленник CPA, способен сделать и злоумышленник CCA. Иными словами, если шифр невозможно взломать с помощью запросов с выбранным шифротекстом и выбранным открытым текстом, его невозможно взломать, выполняя лишь запросы с выбранным открытым текстом.

Менее очевидно, что IND-CPA не влечёт NM-CPA. Чтобы понять это, обратите внимание: приведённая выше конструкция IND-CPA (DRBG(K, R) xor P, R) не является NM-CPA. Имея шифротекст (X, R), можно создать шифротекст (X xor 1, R), являющийся допустимым шифротекстом для P xor 1, что противоречит понятию неподатливости.

Но обратная связь существует: NM-CPA влечёт IND-CPA. Интуитивно шифрование IND-CPA похоже на помещение предметов в мешок: вы их не видите, но можете менять их положение внутри мешка, встряхивая его вверх и вниз. NM-CPA больше похожа на сейф: поместив что-либо внутрь, вы уже не можете с ним взаимодействовать. Для IND-CCA и NM-CCA эта аналогия не работает: данные понятия эквивалентны, и каждое из них влечёт другое. Я избавлю вас от довольно технического доказательства.

ДВА ТИПА ПРИМЕНЕНИЯ ШИФРОВАНИЯ

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

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

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

Аутентифицированное шифрование (authenticated encryption, AE) - тип симметричного шифрования, который помимо шифротекста возвращает тег аутентификации. На рис. 1-4 показано, как аутентифицированное шифрование задаёт AE(K, P) = (C, T), где тег аутентификации T - короткая строка, которую невозможно угадать без ключа. Расшифрование принимает K, C и T и возвращает открытый текст P только в том случае, если проверка подтверждает, что T является допустимым тегом для этой пары открытого текста и шифротекста; в противном случае операция прерывается и возвращает ошибку.

Рисунок 1-4. Аутентифицированное шифрование

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

Примечание. Здесь я говорю «создатель», а не «отправитель», потому что перехватчик может записать несколько пар (C, T), отправленных стороной A стороне B, а затем вновь отправить их стороне B, выдавая себя за A. Это называется атакой повторного воспроизведения; предотвратить её можно, например, включив в сообщение значение счётчика. При расшифровании сообщения его счётчик i увеличивается на единицу: i + 1. Тогда по счётчику можно проверить, не было ли сообщение отправлено дважды, что указывало бы на попытку злоумышленника повторно воспроизвести сообщение. Это также позволяет обнаруживать потерянные сообщения.

Аутентифицированное шифрование с ассоциированными данными (authenticated encryption with associated data, AEAD) - расширение аутентифицированного шифрования, которое принимает открытые незашифрованные данные и использует их для создания тега аутентификации: AEAD(K, P, A) = (C, A, T). Типичное применение AEAD - защита дейтаграмм протоколов с открытым заголовком и зашифрованной полезной нагрузкой. В таких случаях по меньшей мере часть данных заголовка должна оставаться открытой; например, адрес назначения должен быть виден, чтобы сетевые пакеты можно было маршрутизировать.

Подробнее об аутентифицированном шифровании рассказано в главе 8.

Обычный шифр принимает биты и возвращает биты; ему безразлично, представляют ли они текст, изображение или PDF-документ. В свою очередь, шифротекст можно закодировать необработанными байтами, шестнадцатеричными символами, base64 и в других форматах. Но что делать, если шифротекст должен иметь тот же формат, что и открытый текст, как иногда требуется в системах баз данных, способных хранить данные лишь в предписанном формате?

Шифрование с сохранением формата (format-preserving encryption, FPE) решает эту проблему. Оно позволяет создавать шифротексты в том же формате, что и открытые тексты. Например, FPE может шифровать IP-адреса в IP-адреса (как показано на рис. 1-5), почтовые индексы в почтовые индексы, номера кредитных карт в номера кредитных карт с допустимой контрольной суммой и так далее.

Рисунок 1-5. Шифрование IP-адресов с сохранением формата

Полностью гомоморфное шифрование (fully homomorphic encryption, FHE) - святой Грааль криптографов: оно позволяет заменить шифротекст C = E(K, P) другим шифротекстом C' = E(K, F(P)), где F(P) может быть любой функцией от P, ни разу не расшифровывая исходный шифротекст C. Например, P может быть текстовым документом, а F - изменением части текста. Представьте облачное приложение, которое хранит ваши зашифрованные данные, но поставщик облачных услуг не знает ни содержания данных, ни характера изменений, которые вы вносите. Звучит потрясающе, не правда ли?

Но есть и обратная сторона: такое шифрование медленно - настолько медленно, что даже самая базовая операция заняла бы неприемлемо много времени. Первая схема FHE была создана в 2009 году, и с тех пор появились более эффективные варианты, однако до сих пор неясно, станет ли FHE когда-нибудь достаточно быстрым для практического применения. Вместе с тем ориентированные на конкретные приложения варианты использования (частично) гомоморфного шифрования оказались эффективнее для таких операций, как вычисление моделей машинного обучения.

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

Настраиваемое шифрование (tweakable encryption, TE) похоже на обычное, но использует дополнительный параметр, называемый настройкой (tweak), который предназначен для имитации разных версий шифра (см. рис. 1-6). Настройкой может служить уникальное значение для каждого клиента, гарантирующее, что шифр клиента нельзя клонировать другим сторонам, использующим тот же продукт, но основное применение TE - шифрование дисков. Впрочем, TE не привязано к одному применению: это низкоуровневый тип шифрования, используемый при построении других схем, например режимов аутентифицированного шифрования.

Рисунок 1-6. Настраиваемое шифрование

При шифровании дисков TE шифрует содержимое устройств хранения, таких как жёсткие или твердотельные диски. (Рандомизированное шифрование использовать нельзя, поскольку оно увеличивает объём данных, что неприемлемо для файлов на носителе.) Чтобы сделать шифрование непредсказуемым, TE использует значение настройки, зависящее от положения шифруемых данных, - обычно это номер сектора или индекс блока.

Алгоритмы шифрования или их реализации могут не обеспечить конфиденциальность по множеству причин. Проблема может состоять в несоответствии требованиям безопасности (таким как «быть безопасным в смысле IND-CPA») либо в выборе требований, не соответствующих действительности (если вы ориентируетесь лишь на безопасность IND-CPA, тогда как злоумышленники в действительности могут выполнять запросы с выбранным шифротекстом). Увы, многие инженеры вообще не задумываются о требованиях криптографической безопасности и хотят получить «безопасность», не понимая, что именно это значит. Обычно это верный путь к катастрофе. Рассмотрим два примера.

На протяжении всей книги мы подробнее рассматриваем шифрование и его различные формы, уделяя особое внимание работе современных безопасных шифров. И всё же я не могу охватить абсолютно всё и обошёл стороной множество увлекательных тем. Например, чтобы изучить теоретические основы шифрования и глубже понять понятие неразличимости, прочитайте статью 1982 года, в которой была введена идея семантической безопасности: «Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information» Голдвассер и Микали. Если вас интересуют физические атаки и криптографическое оборудование, главным источником служат материалы конференции Cryptographic Hardware and Embedded Systems (CHES).

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

Любой рандомизированный процесс характеризуется распределением вероятностей, которое сообщает всё, что можно знать о случайности этого процесса. Распределение вероятностей, или просто распределение, перечисляет исходы рандомизированного процесса и ставит каждому исходу в соответствие вероятность.

Энтропия - мера неопределённости, или беспорядка, в системе. Чем выше энтропия, тем меньше определённости в результате рандомизированного процесса.

Энтропию распределения вероятностей можно вычислить. Если распределение состоит из вероятностей p_1, p_2, ..., p_N, его энтропия равна отрицательной сумме произведений всех вероятностей на их логарифмы:

Здесь функция log означает двоичный логарифм, то есть логарифм по основанию два. В отличие от натурального логарифма, двоичный выражает информацию в битах и даёт целые значения, когда вероятности являются степенями двойки. Например, log(1/2) = -1, log(1/4) = -2, а в общем случае log(1/2^n) = -n. (Отрицательная сумма берётся как раз для того, чтобы получить положительное число.) Поэтому случайные 128-битные ключи, созданные с равномерным распределением, имеют следующую энтропию:

Если заменить 128 любым целым числом n, энтропия равномерно распределённой n-битной строки составит n бит.

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

Точно так же при неравномерном распределении энтропия ниже. Рассмотрим пример с броском монеты. Энтропия честного броска равна:

Что произойдёт, если вероятность выпадения одной стороны монеты выше, чем другой? Предположим, вероятность орла равна 1/4, а решки - 3/4. (Помните, что сумма всех вероятностей должна равняться 1.)

Энтропия такого смещённого броска равна:

Тот факт, что 0,81 меньше энтропии честного броска, равной 1 биту, показывает: чем сильнее смещена монета, тем менее равномерно распределение и тем ниже энтропия. Если продолжить этот пример, при вероятности орла 1/10 энтропия составит 0,469, а при снижении вероятности до 1/100 энтропия упадёт до 0,081.

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

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

• Источник энтропии, предоставляемый генераторами случайных чисел.

• Криптографический алгоритм, создающий из источника энтропии высококачественные случайные биты. Такой алгоритм реализуют генераторы псевдослучайных чисел.

Совместное использование генераторов случайных и псевдослучайных чисел - ключ к практичной и безопасной криптографии. Сначала кратко рассмотрим работу генераторов случайных чисел, а затем подробно разберём генераторы псевдослучайных чисел.

Случайность поступает из окружающей среды, которая аналогова, хаотична, неопределённа, а потому непредсказуема. Одни лишь компьютерные алгоритмы не могут создавать случайность. В криптографии она обычно поступает от генераторов случайных чисел (random number generators, RNG) - программных или аппаратных компонентов, которые используют энтропию аналогового мира для получения непредсказуемых битов в цифровой системе. Например, RNG может непосредственно выбирать биты из измерений температуры, акустического шума, турбулентности воздуха или статического электричества. К сожалению, такие аналоговые источники энтропии доступны не всегда, а их энтропию зачастую трудно оценить.

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

Примечание. Квантовые генераторы случайных чисел (quantum random number generators, QRNG) - разновидность RNG, использующая случайность, возникающую в квантово-механических явлениях, например радиоактивном распаде, поляризации фотонов или тепловом шуме. Эти явления, не описываемые уравнениями, которые определяют будущее состояние по текущему, случайны в абсолютном смысле. Однако на практике необработанные биты, извлечённые из QRNG, могут быть смещёнными и обычно создаются медленно. Как и упомянутые выше источники энтропии, они требуют постобработки, чтобы с высокой скоростью получать надёжные биты.

Генераторы псевдослучайных чисел (pseudorandom number generators, PRNG) решают проблему получения случайности, надёжно создавая множество искусственных случайных битов из небольшого количества истинно случайных. Например, RNG, преобразующий движения мыши в случайные биты, прекратит работу, если вы перестанете двигать мышь, тогда как PRNG по запросу всегда возвращает псевдослучайные биты.

PRNG опираются на RNG, но ведут себя иначе: RNG сравнительно медленно получают истинно случайные биты из аналоговых источников, недетерминированным образом, без гарантии равномерного распределения или высокой энтропии каждого бита. В противоположность им PRNG быстро создают из цифровых источников биты, которые выглядят случайными, причём делают это детерминированно, с равномерным распределением и гарантированно достаточно высокой для криптографических применений энтропией. По существу, PRNG преобразуют небольшое количество ненадёжных случайных битов в длинный поток надёжных псевдослучайных битов, пригодных для криптографии, как показано на рис. 2-1.

Рисунок 2-1. RNG создают небольшое количество ненадёжных битов из аналоговых источников, а PRNG разворачивают эти биты в длинный поток надёжных битов

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

Чтобы создать псевдослучайные биты, PRNG выполняет алгоритм детерминированного генератора случайных битов (deterministic random bit generator, DRBG), который разворачивает несколько битов из пула энтропии в гораздо более длинную последовательность. Как следует из названия, DRBG детерминирован, а не случаен: при одинаковых входных данных он всегда выдаёт одинаковый результат. PRNG следит за тем, чтобы его DRBG никогда не получал одни и те же входные данные дважды и мог создавать уникальные псевдослучайные последовательности.

В ходе работы PRNG выполняет три операции:

• init(). Инициализирует пул энтропии и внутреннее состояние PRNG.

• refresh(R). Обновляет пул энтропии некоторыми данными R, обычно полученными от RNG.

• next(N). Возвращает N псевдослучайных битов и обновляет пул энтропии.

Операция init сбрасывает PRNG в новое состояние, повторно инициализирует пул энтропии некоторым значением по умолчанию, а также инициализирует все переменные и буферы памяти, которые PRNG использует для выполнения операций refresh и next.

Операцию refresh часто называют повторным засевом, а её аргумент R - начальным значением, или зерном (seed). Когда RNG недоступен, зерном могут служить уникальные значения, жёстко заданные в системе. Операцию refresh обычно вызывает операционная система, а next обычно вызывают или запрашивают приложения. Операция next запускает DRBG и изменяет пул энтропии, чтобы следующий вызов выдал другие псевдослучайные биты.

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

Чтобы обеспечить устойчивость к восстановлению прошлого, PRNG должен гарантировать необратимость преобразований, выполняемых при обновлении состояния операциями refresh и next. Тогда, если злоумышленник скомпрометирует систему и получит значение пула энтропии, он не сможет определить предыдущие значения пула или ранее созданные биты. Для устойчивости к предсказанию PRNG должен регулярно вызывать refresh со значениями R, неизвестными злоумышленнику и трудно угадываемыми; это не позволит злоумышленнику определять будущие значения пула энтропии, даже если весь пул скомпрометирован. (Если бы список значений R был известен, для воссоздания пула понадобилось бы знать порядок вызовов refresh и next.)

Fortuna - конструкция PRNG, применяемая в Windows; первоначально её разработали в 2003 году Нильс Фергюсон и Брюс Шнайер. Fortuna пришла на смену Yarrow - разработке Джона Келси и Брюса Шнайера 1998 года, которая долго использовалась в операционных системах macOS и iOS, но затем также была заменена на Fortuna. Я не стану приводить здесь спецификацию Fortuna или показывать её реализацию, но постараюсь объяснить принцип работы. Полное описание Fortuna вы найдёте в главе 9 книги Фергюсона, Шнайера и Коно «Cryptography Engineering» (Wiley, 2010).

Внутренняя память Fortuna содержит следующее:

• 32 пула энтропии P_1, P_2, ..., P_32, причём P_i используется при каждом 2^i-м повторном засеве.

• Ключ K и счётчик C (оба по 16 байт). Вместе они образуют внутреннее состояние DRBG в Fortuna.

В самом упрощённом виде Fortuna работает так:

• init() присваивает K и C нулевые значения и очищает 32 пула энтропии P_i, где i = 1 ... 32.

• refresh(R) добавляет данные R в один из пулов энтропии. Система выбирает RNG, используемые для создания значений R, и должна регулярно вызывать refresh.

• next(N) обновляет K с помощью данных из одного или нескольких пулов энтропии; выбор пулов главным образом зависит от числа уже выполненных обновлений K. Затем запрошенные N битов создаются шифрованием C с ключом K. Если одного шифрования C недостаточно, Fortuna шифрует C + 1, затем C + 2 и так далее, пока не получит достаточно битов.

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

Даже при правильной реализации Fortuna нарушения безопасности возможны по причинам, не связанным с неверным алгоритмом. Например, Fortuna может не заметить, что RNG создаёт недостаточно случайных битов, и вследствие этого начнёт выдавать псевдослучайные биты более низкого качества или вовсе перестанет их выдавать.

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

Наконец, если два экземпляра Fortuna находятся в одинаковом состоянии, поскольку совместно используют один файл начальных значений (то есть во всех пулах энтропии находятся одинаковые данные, включая C и K), операция next вернёт одинаковые биты в обоих экземплярах.

PRNG бывают криптографическими и некриптографическими. Некриптографические PRNG предназначены для создания равномерных распределений в таких приложениях, как научное моделирование или видеоигры. Однако использовать некриптографические PRNG в криптографических приложениях нельзя: они небезопасны, поскольку учитывают лишь качество распределения вероятностей битов, но не их предсказуемость. Криптографические PRNG, напротив, непредсказуемы, так как в них учитывается также стойкость базовых операций, используемых для получения хорошо распределённых битов.

К сожалению, большинство PRNG, предоставляемых языками программирования, - например, rand и drand48 из libc, rand и mt_rand из PHP, модуль random в Python и класс java.util.Random в Java - являются некриптографическими. Выбор некриптографического PRNG по умолчанию - верный путь к катастрофе, потому что его нередко в итоге используют в криптографических приложениях. Поэтому для создания случайности, связанной с криптографией или безопасностью, обязательно применяйте только криптографические PRNG.

Алгоритм Mersenne Twister (MT) - некриптографический PRNG, который на момент написания книги используется в PHP, Python, R, Ruby и многих других системах. Его даже применяли, к сожалению, в генераторах ключей блокчейн-кошельков. MT создаёт равномерно распределённые случайные биты без статистического смещения, но он предсказуем: имея несколько битов, созданных MT, можно угадать, какие биты последуют далее.

Заглянем внутрь и посмотрим, почему Mersenne Twister небезопасен. Алгоритм MT значительно проще криптографических PRNG: его внутреннее состояние представляет собой массив S из 624 32-битных слов. Изначально этот массив равен S_1, S_2, ..., S_624, затем изменяется на S_2, ..., S_625, потом на S_3, ..., S_626 и так далее согласно уравнению:

Здесь xor обозначает побитовую операцию XOR (^ в языке C), and - побитовую операцию AND (& в C), or - побитовую операцию OR (| в C), а A - функцию, преобразующую некоторое 32-битное слово x в (x >> 1), если старший бит x равен 0, и в (x >> 1) xor 0x9908b0df в противном случае.

В этом уравнении биты S взаимодействуют друг с другом только посредством XOR. Операторы and и or никогда не объединяют два бита S между собой, а лишь объединяют биты S с битами констант 0x80000000 и 0x7fffffff. Поэтому любой бит S_625 можно выразить как XOR битов S_398, S_1 и S_2, а любой бит любого будущего состояния - как XOR-комбинацию битов из начального состояния S_1, ..., S_624. (Когда, например, S_(228+624) = S_852 выражается как функция от S_625, S_228 и S_229, значение S_625, в свою очередь, можно заменить его выражением через S_398, S_1 и S_2.)

Поскольку начальное состояние содержит ровно 624 * 32 = 19 968 битов (или 624 32-битных слова), любой выходной бит можно выразить уравнением не более чем из 19 969 членов (19 968 битов и одного постоянного бита). Это около 2,5 Кбайт данных. Верно и обратное: биты начального состояния можно выразить как XOR выходных битов.

XOR-комбинацию битов называют линейной комбинацией. Например, если X, Y и Z - биты, выражение X xor Y xor Z является линейной комбинацией, а (X and Y) xor Z - нет, поскольку содержит AND (and). Если инвертировать бит X в X xor Y xor Z, результат также изменится независимо от значений Y и Z. Напротив, если инвертировать бит X в (X and Y) xor Z, результат изменится только тогда, когда бит Y в той же позиции равен 1. Суть в том, что линейные комбинации предсказуемы: не нужно знать значения битов, чтобы предсказать, как изменение их значений повлияет на результат.

Для сравнения: если бы алгоритм MT был криптографически стойким, его уравнения были бы нелинейными и включали бы не только отдельные биты, но и их AND-комбинации (произведения), например S_1S_15S_182 или S_17S_256S_257S_354S_498S_601. Хотя линейные комбинации этих битов содержат не более 624 переменных, нелинейные комбинации допускают до 2^624 переменных. Полную систему таких уравнений было бы невозможно не только решить, но даже записать. (Заметьте, что 2^305 - значительно меньшее число - считается оценкой информационной ёмкости наблюдаемой Вселенной.)

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

Примечание. Линейность - лишь один из множества критериев безопасности. Нелинейность необходима, но сама по себе не делает PRNG криптографически безопасным.

Наборы статистических тестов, такие как TestU01, Diehard или набор Национального института стандартов и технологий США (NIST), являются одним из способов проверки качества псевдослучайных битов. Эти тесты принимают образец созданных PRNG псевдослучайных битов (например, объёмом 1 Мбайт), вычисляют статистические показатели распределения определённых битовых шаблонов и сравнивают результаты с типичными результатами для равномерного распределения. Например, некоторые тесты подсчитывают количество единичных и нулевых битов или распределение 8-битных шаблонов. Но статистические тесты по большей части не имеют отношения к криптографической безопасности: можно создать криптографически слабый PRNG, который обманет любой статистический тест.

Запуская статистические тесты на случайно сгенерированных данных, вы обычно получите множество статистических показателей. Как правило, это p-значения - распространённый статистический показатель. Результаты не всегда легко истолковать, поскольку они редко сводятся к простому «пройдено» или «не пройдено». Если первые результаты кажутся аномальными, не беспокойтесь: причиной может быть случайное отклонение либо слишком малое число проверяемых образцов. Чтобы убедиться, что наблюдаемые результаты нормальны, сравните их с результатами для некоторого надёжного образца того же размера, например созданного набором OpenSSL следующей командой:

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

Далее мы рассмотрим наиболее широко распространённые PRNG: применяемые в Linux, Android и многих других системах на основе Unix; используемые в Windows; а также аппаратный PRNG в современных микропроцессорах Intel.

Файл устройства /dev/urandom - интерфейс пользовательского пространства к криптографическому PRNG в операционных системах на основе ядра Linux. Обычно именно его используют для создания надёжных случайных битов. Поскольку это файл устройства, случайные биты запрашиваются у /dev/urandom путём чтения файла. Например, следующая команда использует /dev/urandom, чтобы записать 10 Мбайт случайных битов в файл:

Можно написать наивную и небезопасную программу на C, подобную показанной в листинге 2-1, прочитать случайные биты и надеяться на лучшее, но это плохая идея.

Листинг 2-1. Небезопасное использование /dev/urandom

Этот код небезопасен; он даже не проверяет возвращаемые значения open() и read(), поэтому буфер, в котором ожидаются случайные данные, может оказаться заполненным нулями или остаться неизменённым.

В листинге 2-2, скопированном из библиотеки LibreSSL, показан более безопасный способ использования /dev/urandom.

Листинг 2-2. Безопасное использование /dev/urandom

В отличие от листинга 2-1, в листинге 2-2 выполняется несколько проверок разумности. Сравните, например, вызовы open() 1 и read() 2 с их аналогами в листинге 2-1: более безопасный код проверяет возвращаемые значения этих функций, а при сбое закрывает файловый дескриптор и возвращает -1.

PRNG Linux, определённый в файле drivers/char/random.c ядра Linux, в 2022 году претерпел значительные изменения, начиная с версии ядра 5.17.

Прежде всего общая структура PRNG, сходная в старых и новых версиях, основана на сборе энтропии из различных источников (включая системную активность, например работу с клавиатурой, мышью и дисками), а также на пуле энтропии, который можно представить как большой массив, заполняемый хешированными данными, собранными из источников энтропии. Затем DRBG создаёт потоки псевдослучайных данных, возвращаемые при чтении /dev/random или /dev/urandom либо при системном вызове getrandom().

Исторически, до версии ядра 5.17, PRNG Linux вёл себя следующим образом: в отличие от /dev/urandom, интерфейс /dev/random был блокирующим. Если, по оценке ядра, уровень энтропии PRNG был недостаточен, /dev/random при чтении переставал возвращать байты, то есть «блокировался», пока ядро не оценивало уровень энтропии как достаточный. Это была неудачная идея. Во-первых, оценки энтропии печально известны своей ненадёжностью и могут быть обмануты злоумышленниками (это одна из причин, по которым Fortuna отказалась от оценки энтропии, применявшейся в Yarrow). Кроме того, оценённая энтропия /dev/random довольно быстро исчерпывалась, что могло приводить к отказу в обслуживании, замедляя приложения, вынужденные ожидать дополнительной энтропии. В итоге на практике /dev/random не превосходил /dev/urandom и создавал больше проблем, чем решал.

В версии ядра Linux 2022 года (5.17 и новее) было внесено несколько улучшений. Во-первых, при формировании содержимого пула хеш-функцию SHA-1 заменили на BLAKE2. Самое значительное изменение коснулось относительного поведения /dev/random и /dev/urandom; предлагалось даже полностью устранить различия между ними. На момент написания книги на большинстве платформ оба интерфейса определяют, достаточно ли энтропии, но /dev/urandom возобновляет создание псевдослучайных битов, если ядру не удаётся собрать достаточно энтропии, тогда как /dev/random блокируется.

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

Значение энтропии системы Linux можно прочитать в файле /proc/sys/kernel/random/entropy_avail. В старых версиях ядра это значение имело максимум 4096 бит и уменьшалось при создании битов PRNG. В новых ядрах оно ограничено 256 битами и потому больше не уменьшается.

В Windows устаревшим интерфейсом пользовательского пространства к системному PRNG является функция CryptGenRandom() из интерфейса прикладного программирования Cryptography API. В современных версиях Windows функция CryptGenRandom() заменена функцией BCryptGenRandom() из Cryptography API: Next Generation (CNG). PRNG Windows получает энтропию от драйвера режима ядра cng.sys (ранее ksecdd.sys), сборщик энтропии которого в общих чертах основан на Fortuna. Как это часто бывает в Windows, процесс сложен.

В листинге 2-3 показан типичный вызов CryptGenRandom() на C++ со всеми необходимыми проверками.

Листинг 2-3. Использование интерфейса PRNG CryptGenRandom() в Windows

Перед вызовом самого PRNG необходимо объявить поставщика криптографических служб (HCRYPTPROV), а затем получить криптографический контекст с помощью CryptAcquireContext(), что повышает вероятность ошибки. Например, было обнаружено, что в последней версии программы шифрования TrueCrypt функция CryptAcquireContext() вызывалась так, что могла незаметно завершиться сбоем, приводя к неоптимальной случайности без уведомления пользователя. К счастью, новый и более простой интерфейс BCryptGenRandom() в Windows не требует от кода явно открывать дескриптор (или, по крайней мере, значительно облегчает использование без дескриптора).

До сих пор мы обсуждали только программные PRNG, поэтому теперь рассмотрим аппаратный. Intel Digital Random Number Generator, также называемый Intel Secure Key, - аппаратный PRNG, представленный в 2012 году в микроархитектуре Intel Ivy Bridge. Он основан на рекомендациях NIST SP 800-90 и стандарте Advanced Encryption Standard (AES) в режиме CTR_DRBG. Доступ к PRNG Intel осуществляется через ассемблерную инструкцию RDRAND, которая предоставляет интерфейс, независимый от операционной системы, и в принципе работает быстрее программных PRNG.

В то время как программные PRNG пытаются собирать энтропию из непредсказуемых источников, Intel Secure Key располагает единственным источником энтропии, выдающим последовательный поток данных энтропии в виде нулей и единиц. В терминах аппаратной инженерии этот источник энтропии представляет собой двойную дифференциальную защёлку с обратной связью и режимом конфликтного состояния: по существу, небольшую аппаратную схему, которая переключается между двумя состояниями, 0 и 1, в зависимости от колебаний теплового шума с частотой 3 ГГц. Обычно она довольно надёжна.

Ассемблерная инструкция RDRAND принимает в качестве аргумента регистр размером 16, 32 или 64 бита и записывает в него случайное значение. При вызове RDRAND устанавливает флаг переноса в 1, если данные в регистре назначения являются допустимым случайным значением, и в 0 в противном случае; если вы непосредственно пишете ассемблерный код, обязательно проверяйте флаг CF. Обратите внимание: встроенные функции C, доступные в распространённых компиляторах, не проверяют флаг CF, но возвращают его значение.

Примечание. Платформа PRNG Intel предоставляет помимо RDRAND ещё одну ассемблерную инструкцию: RDSEED возвращает случайные биты непосредственно из источника энтропии после некоторой обработки, нормализующей или криптографической. Она предназначена для получения начальных значений другими PRNG.

Intel Secure Key документирован лишь частично, однако построен на известных стандартах и прошёл аудит у уважаемой компании Cryptography Research (см. её отчёт «Analysis of Intel’s Ivy Bridge Digital Random Number Generator»). Тем не менее высказывались опасения по поводу его безопасности, особенно после разоблачений Эдварда Сноудена о криптографических бэкдорах: PRNG и в самом деле представляет собой идеальную цель для саботажа. Если вас это беспокоит, но вы всё же хотите использовать RDRAND или RDSEED, смешивайте их выход с другими источниками энтропии. За исключением самых невероятных сценариев, это предотвратит успешную эксплуатацию гипотетического бэкдора в аппаратной части Intel Secure Key или в связанного с ней микрокода.

В заключение я приведу несколько примеров сбоев случайности. Выбирать можно из бесчисленного множества случаев, но я остановился на четырёх, достаточно простых для понимания и иллюстрирующих разные проблемы.

В 1996 году реализация SSL в браузере Netscape вычисляла 128-битные начальные значения PRNG согласно псевдокоду из листинга 2-4, скопированному со страницы Голдберга и Вагнера https://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html.

Листинг 2-4. Псевдокод создания 128-битных начальных значений PRNG браузером Netscape

Проблема в том, что PID и микросекунды можно угадать. Если предположить, что значение секунд удастся угадать, у микросекунд имеется лишь 10^6 возможных значений, а значит, энтропия log(10^6), или около 20 бит. Идентификатор процесса (PID) и идентификатор родительского процесса (PPID) являются 15-битными значениями, поэтому можно ожидать дополнительных 15 + 15 = 30 бит энтропии. Но если посмотреть, как вычисляется b 1, видно, что перекрытие трёх битов даёт энтропию около 15 + 12 = 27 бит, а общая энтропия составляет лишь 47 бит, хотя у 128-битного начального значения должно быть 128 бит энтропии.

В 2012 году исследователи просканировали интернет и собрали открытые ключи из сертификатов TLS и узлов SSH. Они обнаружили, что у небольшого числа систем открытые ключи совпадали, а в некоторых случаях были очень похожи (а именно, ключи RSA имели общие простые множители). Иными словами, имелись два числа n = pq и n' = p'q' при p = p', хотя в норме все значения p и q в разных модулях должны различаться.

Оказалось, что многие устройства создавали открытый ключ слишком рано, при первой загрузке, прежде чем успевали собрать достаточно энтропии, хотя использовали в остальном приличный PRNG (обычно /dev/urandom). Из-за одинакового источника энтропии, например жёстко заданного начального значения, PRNG в разных системах создавали одинаковые случайные биты.

На высоком уровне одинаковые ключи возникают из-за схем создания ключей, подобных следующей, представленной псевдокодом:

Если две системы выполнят этот код с одинаковым начальным значением, они создадут одинаковое p, одинаковое q, а следовательно, и одинаковое n.

Общие простые множители в разных ключах возникают в схемах создания ключей, где во время процесса добавляется дополнительная энтропия, как показано ниже:

Если две системы выполнят этот код с одинаковым начальным значением, они создадут одинаковое p, но добавление энтропии посредством prng.add_entropy() обеспечит разные значения q.

Проблема общих простых множителей состоит в том, что при известных n = pq и n' = pq' общее значение p элементарно восстанавливается вычислением наибольшего общего делителя (НОД) чисел n и n'. Подробности приведены в статье Хенингер, Дюремерика, Вустроу и Халдермана «Mining Your Ps and Qs», доступной по адресу https://factorable.net.

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

Популярное приложение MediaWiki работает на Wikipedia и множестве других вики-сайтов. Случайность используется в нём для создания, помимо прочего, маркеров безопасности и временных паролей, которые должны быть непредсказуемыми. К сожалению, одна ныне устаревшая версия MediaWiki создавала эти маркеры и пароли с помощью некриптографического PRNG Mersenne Twister. Ниже приведён фрагмент уязвимого исходного кода MediaWiki; найдите функцию, вызываемую для получения случайного бита, и прочитайте комментарии:

Заметили mt_rand() в приведённом коде? Здесь mt означает Mersenne Twister. В 2012 году исследователи показали, как воспользоваться предсказуемостью Mersenne Twister, чтобы по паре маркеров безопасности предсказывать будущие маркеры и временные пароли. MediaWiki исправили, переведя на криптографический PRNG.

Следующая ошибка показывает, как даже сильный криптографический PRNG с достаточной энтропией может создавать смещённое распределение. Программа чата Cryptocat была предназначена для защищённой связи. В ней использовалась функция, пытавшаяся создать равномерно распределённую строку десятичных цифр, то есть чисел от 0 до 9. Однако простое вычисление случайных байтов по модулю 10 не даёт равномерного распределения: если взять все числа от 0 до 255 и привести их по модулю 10, количество получившихся значений от 0 до 9 будет неодинаковым.

Чтобы решить эту проблему и получить равномерное распределение, Cryptocat выполняла следующее:

И это было почти безупречно. Если брать только числа до значения, кратного 10, а остальные отбрасывать, можно ожидать равномерного распределения цифр от 0 до 9. К сожалению, в условии if была ошибка на единицу. Подробности я оставлю вам в качестве упражнения. Вы должны обнаружить небольшое статистическое смещение в пользу индекса 0 (подсказка: вместо <= следовало использовать <).

Я лишь слегка коснулся темы случайности в криптографии. О теории случайности можно узнать гораздо больше: существуют различные понятия энтропии, экстракторы случайности и даже вопросы о возможностях рандомизации и дерандомизации в теории сложности. Чтобы подробнее узнать о PRNG и их безопасности, прочитайте классическую статью 1998 года Келси, Шнайера, Вагнера и Холла «Cryptanalytic Attacks on Pseudorandom Number Generators». Затем изучите реализации PRNG в своих любимых приложениях и попробуйте найти их слабости. (Поищите в интернете «random generator bug» - и найдёте множество примеров.)

Блочный шифр состоит из алгоритма шифрования и алгоритма расшифрования:

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

Вычисление блочного шифра сводится к вычислению последовательности раундов. Раунд в блочном шифре - базовое преобразование, простое в описании и реализации, которое повторяется несколько раз, образуя алгоритм блочного шифра. Конструкция из небольшого многократно повторяемого компонента проще для реализации и анализа, чем конструкция из одного огромного алгоритма.

Например, блочный шифр с тремя раундами шифрует открытый текст, вычисляя C = R_3(R_2(R_1(P))), где R_1, R_2 и R_3 - раунды, а P - открытый текст. У каждого раунда также должно существовать обратное преобразование, чтобы получатель мог восстановить открытый текст. В частности, P = iR_1(iR_2(iR_3(C))), где iR_1 - преобразование, обратное R_1, и так далее.

Раундовые функции R_1, R_2 и последующие обычно представляют собой один и тот же алгоритм, но параметризуются значением, называемым раундовым ключом. Две раундовые функции с разными раундовыми ключами будут вести себя по-разному и потому при одинаковых входных данных дадут разные результаты.

Раундовые ключи выводятся из главного ключа K с помощью алгоритма развёртывания ключа. Например, R_1 принимает раундовый ключ K_1, R_2 - раундовый ключ K_2 и так далее.

Раундовые ключи должны различаться на каждом раунде. Более того, не все раундовые ключи должны совпадать с ключом K; иначе все раунды окажутся одинаковыми, и блочный шифр будет менее безопасен, как описано далее.

В блочном шифре ни один раунд не должен совпадать с другим, чтобы избежать атаки скольжением. Как показано на рис. 4-1, атака скольжением ищет две пары «открытый текст - шифротекст» (P_1, C_1) и (P_2, C_2), где P_2 = R(P_1), если R - раунд шифра. Когда раунды одинаковы, отношение между двумя открытыми текстами P_2 = R(P_1) влечёт отношение C_2 = R(C_1) между соответствующими шифротекстами. На рис. 4-1 показаны три раунда, но отношение C_2 = R(C_1) сохраняется при любом числе раундов: 3, 10 или 100. Проблема состоит в том, что знание входа и выхода одного раунда часто помогает восстановить ключ. (Подробности приведены в статье Алекса Бирюкова и Дэвида Вагнера 1999 года «Advanced Slide Attacks».)

Рисунок 4-1. Принцип атаки скольжением на блочные шифры с одинаковыми раундами

Использование разных раундовых ключей в качестве параметров гарантирует, что раунды будут вести себя по-разному, и тем самым разрушает атаки скольжением.

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

Если вы читали учебники по криптографии, то, вероятно, сталкивались с понятиями смешивания и рассеивания. Смешивание означает, что входные данные, то есть открытый текст и ключ шифрования, подвергаются сложным преобразованиям, а рассеивание - что эти преобразования в равной степени зависят от всех входных битов. На высоком уровне смешивание относится к глубине, а рассеивание - к широте. При проектировании блочного шифра смешивание и рассеивание принимают форму операций подстановки и перестановки, объединяемых в подстановочно-перестановочные сети (substitution-permutation networks, SPN).

Подстановка часто реализуется в виде S-блоков, или блоков подстановки, - небольших таблиц поиска, преобразующих фрагменты по 4 или 8 бит. Например, первый из восьми S-блоков блочного шифра Serpent состоит из 16 элементов (3 8 f 1 a 6 5 b e d 4 2 7 0 9 c), каждый из которых представляет 4-битную тетраду. Этот S-блок отображает 4-битную тетраду 0000 в 3 (0011), 4-битную тетраду 0101 (5 в десятичной системе) - в 6 (0110) и так далее.

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

Перестановка в подстановочно-перестановочной сети может сводиться к простому изменению порядка битов, которое легко реализовать, но которое не слишком сильно перемешивает биты. Вместо переупорядочивания битов в некоторых шифрах для их перемешивания применяют базовую линейную алгебру и умножение матриц: выполняется последовательность операций умножения на фиксированные значения (элементы матрицы), после чего результаты складываются. Такие операции способны быстро создать зависимости между всеми битами шифра и тем самым обеспечить сильное рассеивание. Например, блочный шифр FOX преобразует четырёхбайтовый вектор (a, b, c, d) в (a', b', c', d'), определённый следующим образом:

В этих уравнениях числа 2 и 253 интерпретируются как двоичные многочлены, а не как целые числа, поэтому сложение и умножение определяются несколько иначе, чем мы привыкли. Например, вместо 2 + 2 = 4 получается 2 + 2 = 0. Как бы то ни было, каждый байт начального состояния влияет на все четыре байта конечного состояния.

В 1970-х годах инженер IBM Хорст Фейстель разработал блочный шифр Lucifer, работающий следующим образом:

1. Разделить 64-битный блок на две 32-битные половины L и R.

2. Присвоить L значение L xor F(R), где F - подстановочно-перестановочный раунд.

3. Поменять значения L и R местами.

4. Перейти к шагу 2 и повторить его 15 раз.

5. Объединить L и R в выходной 64-битный блок.

Эта конструкция представляет собой схему Фейстеля, показанную на рис. 4-2. Слева изображена только что описанная схема; справа - функционально эквивалентное представление, где вместо перестановки L и R раунды поочерёдно выполняют операции L = L xor F(R) и R = R xor F(L).

Рисунок 4-2. Построение блочного шифра по схеме Фейстеля в двух эквивалентных формах

Чтобы упростить схемы, я не показал на рис. 4-2 ключи, но обратите внимание: первая функция F принимает раундовый ключ K_1, а вторая - другой раундовый ключ K_2. В DES функции F принимают 48-битный раундовый ключ, выведенный из 56-битного ключа K.

В схеме Фейстеля функция F может быть либо псевдослучайной перестановкой (PRP), либо псевдослучайной функцией (pseudorandom function, PRF). PRP даёт разные выходы для любых двух разных входов, тогда как у PRF существуют значения X и Y, для которых F(X) = F(Y). Но в схеме Фейстеля эта разница несущественна, пока F криптографически стойка.

Сколько раундов должно быть в схеме Фейстеля? DES выполняет 16 раундов, а ГОСТ 28147-89 - 32 раунда. Если функция F максимально стойка, в теории достаточно четырёх раундов, однако реальные шифры используют больше раундов для защиты от возможных слабостей F.

AES - самый широко используемый шифр в мире. До принятия AES стандартным шифром был DES с его смехотворной 56-битной стойкостью, а также усовершенствованная версия DES, известная как Triple DES, или 3DES. Хотя 3DES обеспечивает более высокий уровень стойкости - 112 бит, - он неэффективен: для получения 112-битной стойкости требуется ключ длиной 168 бит, а программная реализация медленна (DES создавался для быстрой работы в интегральных схемах, а не на массовых процессорах). AES устраняет обе проблемы.

В 2000 году NIST стандартизировал AES в качестве замены DES, после чего AES фактически стал мировым стандартом шифрования. Сегодня AES поддерживает большинство коммерческих продуктов шифрования, а NSA одобрило его для защиты совершенно секретных сведений. (Некоторые страны предпочитают собственные шифры главным образом потому, что не хотят применять стандарт США, но в действительности AES скорее бельгийский, чем американский.)

Примечание. Когда алгоритм участвовал в конкурсе AES как один из 15 кандидатов, он назывался Rijndael - это имя образовано из фамилий его создателей, Реймена и Дамена, и произносится примерно как «рейн-дал». Конкурс AES проводился NIST с 1997 по 2000 год, чтобы определить «несекретный, открыто опубликованный алгоритм шифрования, способный защищать конфиденциальные государственные сведения далеко в следующем столетии», как было сказано в объявлении конкурса 1997 года в Federal Register. Конкурс AES был своего рода состязанием талантов для криптографов, где любой желающий мог участвовать, представив шифр или взломав шифр другого участника.

AES обрабатывает блоки по 128 бит с помощью секретного ключа длиной 128, 192 или 256 бит. Чаще всего используется 128-битный ключ, поскольку с ним шифрование немного быстрее, а различие между 128- и 256-битной стойкостью не имеет значения для большинства применений.

Некоторые шифры работают с отдельными битами или 64-битными словами, а AES манипулирует байтами. Он рассматривает 16-байтовый открытый текст как двумерный массив байтов (s = s_0, s_1, ..., s_15), как показано на рис. 4-3. (Мы используем букву s, поскольку этот массив является внутренним состоянием, или просто состоянием.) AES преобразует байты, столбцы и строки этого массива, создавая конечное значение - шифротекст.

Рисунок 4-3. Внутреннее состояние AES в виде массива 4 x 4 из 16 байт

Для преобразования состояния AES использует структуру SPN, показанную на рис. 4-4: 10 раундов при 128-битном ключе, 12 - при 192-битном и 14 - при 256-битном.

Рисунок 4-4. Внутренние операции AES

На рис. 4-4 показаны четыре строительных блока раунда AES. Обратите внимание: все раунды, кроме последнего, представляют собой последовательность SubBytes, ShiftRows, MixColumns и AddRoundKey:

• AddRoundKey. Выполняет XOR раундового ключа с внутренним состоянием.

• SubBytes. Заменяет каждый байт (s_0, s_1, ..., s_15) другим байтом согласно S-блоку. В данном случае S-блок представляет собой таблицу поиска из 256 элементов.

• ShiftRows. Сдвигает i-ю строку на i позиций, где i изменяется от 0 до 3 (см. рис. 4-5).

• MixColumns. Применяет одно и то же линейное преобразование к каждому из четырёх столбцов состояния, то есть к каждой группе ячеек одинакового оттенка серого на левой стороне рис. 4-5.

Рисунок 4-5. ShiftRows циклически сдвигает байты в каждой строке внутреннего состояния.

Помните, что в SPN буква S означает подстановку, а P - перестановку. Здесь слоем подстановки является SubBytes, а слоем перестановки - сочетание ShiftRows и MixColumns.

Функция развёртывания ключа KeyExpansion, показанная на рис. 4-4, является алгоритмом развёртывания ключа AES. Она создаёт из 16-байтового ключа 11 раундовых ключей (K_0, K_1, ..., K_10) по 16 байт каждый, используя тот же S-блок, что и SubBytes, и сочетание операций XOR. Важное свойство KeyExpansion состоит в том, что, имея любой раундовый ключ K_i, злоумышленник может определить все остальные раундовые ключи, а также главный ключ K, обратив алгоритм. Возможность получить ключ из любого раундового ключа снижает устойчивость шифра к атакам по побочным каналам, при которых злоумышленник может без труда восстановить раундовый ключ.

Без этих операций AES был бы совершенно небезопасен. Каждая операция вносит свой вклад в безопасность AES:

• Без KeyExpansion все раунды использовали бы один и тот же ключ K, и AES был бы уязвим для атак скольжением.

• Без AddRoundKey шифрование не зависело бы от ключа, поэтому любой мог бы расшифровать любой шифротекст без ключа.

• SubBytes добавляет нелинейные операции, повышающие криптографическую стойкость. Без неё AES представлял бы собой лишь большую систему линейных уравнений, которую можно решить методами школьной алгебры, а именно методом исключения Гаусса.

• Без ShiftRows изменения в одном столбце никогда не влияли бы на остальные столбцы, а значит, AES можно было бы взломать, построив для каждого столбца по четыре кодовые книги из 2^32 элементов. (Помните, что в безопасном блочном шифре инвертирование одного входного бита должно влиять на все выходные биты.)

• Без MixColumns изменения одного байта не влияли бы ни на какие другие байты состояния. Тогда злоумышленник с выбранным открытым текстом мог бы расшифровать любой шифротекст, сохранив 16 таблиц поиска по 256 байт каждая, содержащих зашифрованные значения каждого возможного значения байта.

Обратите внимание: на рис. 4-4 последний раунд AES не содержит операции MixColumns. Она опущена, чтобы избежать бесполезных вычислений: поскольку MixColumns линейна, эффект этой операции в самом последнем раунде можно устранить, комбинируя биты способом, не зависящим от их значений или ключа. Но обратить SubBytes невозможно, не зная значения состояния до AddRoundKey.

Чтобы расшифровать шифротекст, AES разворачивает каждую операцию, применяя обратную функцию: обратная таблица поиска SubBytes отменяет преобразование SubBytes, ShiftRows выполняет сдвиг в противоположном направлении, применяется обратная MixColumns, то есть матрица, обратная матрице, задающей эту операцию, а XOR в AddRoundKey остаётся неизменным, поскольку операцией, обратной XOR, является другая XOR.

В качестве упражнения можно воспользоваться библиотекой cryptography в Python, чтобы зашифровать и расшифровать блок данных с помощью AES, как показано в листинге 4-1.

Листинг 4-1. Шифрование и расшифрование блока с помощью AES в Python

Выполнение этого сценария даёт примерно следующий результат:

У вас результаты будут другими, потому что при каждом новом запуске ключ выбирается случайно.

Реальное программное обеспечение AES работает не так, как алгоритм на рис. 4-4. В коде AES промышленного уровня вы не найдёте последовательных вызовов функций SubBytes(), ShiftRows() и MixColumns(), поскольку это было бы неэффективно. Вместо этого быстрые программные реализации AES используют таблицы и собственные инструкции процессора.

В табличных реализациях AES последовательность SubBytes-ShiftRows-MixColumns заменяется сочетанием операций XOR и поисков в таблицах, жёстко заданных в программе и загружаемых в память во время выполнения. Это возможно потому, что MixColumns эквивалентна XOR четырёх 32-битных значений, каждое из которых зависит от одного байта состояния и от SubBytes. Поэтому можно построить четыре таблицы по 256 записей, по одной для каждого значения байта, и реализовать последовательность SubBytes-MixColumns поиском четырёх 32-битных значений с последующим выполнением их XOR.

Например, табличная реализация на C из набора OpenSSL выглядит как листинг 4-2.

Листинг 4-2. Фрагмент табличной реализации AES на C в OpenSSL

Базовой табличной реализации шифрования AES требуются четыре таблицы общим объёмом 4 Кбайт, потому что каждая хранит 256 32-битных значений, занимающих 256 * 32 = 8192 бита, или 1 Кбайт. Для расшифрования нужны ещё четыре таблицы, то есть ещё 4 Кбайт. Однако существуют приёмы, позволяющие сократить объём с 4 Кбайт до 1 Кбайт и даже меньше.

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

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

Собственные инструкции AES (AES native instructions, AES-NI) решают проблему атак по времени доступа к кешу на программные реализации AES. Чтобы понять принцип AES-NI, вспомните, как программное обеспечение выполняется аппаратурой: для запуска программы микропроцессор преобразует двоичный код в последовательность инструкций, выполняемых компонентами интегральной схемы. Например, ассемблерная инструкция MUL над двумя 32-битными значениями активирует транзисторы, реализующие 32-битный умножитель микропроцессора. При реализации криптографического алгоритма обычно задаётся сочетание базовых операций - сложений, умножений, XOR и так далее, - а микропроцессор активирует схемы сложения, умножения и XOR в предписанном порядке.

Собственные инструкции AES поднимают этот подход на совершенно иной уровень, предоставляя разработчикам специализированные ассемблерные инструкции, вычисляющие AES. Вместо кодирования раунда AES последовательностью ассемблерных инструкций при использовании AES-NI достаточно вызвать инструкцию AESENC, и микросхема вычислит раунд за вас. Собственные инструкции позволяют приказать процессору выполнить раунд AES, а не программировать раунды как сочетание базовых операций.

Типичная ассемблерная реализация AES с собственными инструкциями выглядит как листинг 4-3.

Листинг 4-3. Реализация AES-128 с собственными инструкциями AES

Этот код шифрует 128-битный открытый текст, изначально находящийся в регистре xmm0, предполагая, что в регистрах с xmm5 по xmm15 хранятся предварительно вычисленные раундовые ключи; каждая инструкция записывает результат в xmm0. Начальная инструкция PXOR выполняет XOR первого раундового ключа перед вычислением первого раунда, а заключительная инструкция AESENCLAST выполняет последний раунд несколько иначе, чем остальные: MixColumns опускается.

Примечание. На платформах с собственными инструкциями AES работает примерно в десять раз быстрее; на момент написания книги к таким платформам относились практически все микропроцессоры ноутбуков, настольных компьютеров и серверов, а также большинство мобильных телефонов и планшетов. Хотя Intel впервые предложила инструкции AES в 2008 году, они доступны и в процессорах AMD, а большинство архитектур помимо x86 также имеют эквивалентные инструкции, аппаратно реализующие AES. Например, набор инструкций Armv8 содержит инструкции AESSE, вычисляющую SubBytes и ShiftRows, и AESMS, вычисляющую MixColumns.

В микроархитектуре Intel Ice Lake задержка инструкции AESENC составляет три такта при обратной пропускной способности в половину такта: вызов AESENC завершается за три такта, а в каждом такте можно сделать два новых вызова инструкции. Фактически внутренняя структура микроопераций, выполняющих AESENC, позволяет начать вычисление новой инструкции до завершения предыдущей. Более того, архитектура Ice Lake использует векторизованную версию инструкций AES, позволяющую запускать несколько инструкций одновременно. Подробности приведены в статье Нира Друкера, Шая Герона и Влада Краснова «Making AES Great Again».

Для последовательного шифрования серии блоков выполнение десяти раундов занимает 3 * 10 = 30 тактов, или 30/16 = 1,875 такта на байт. При частоте 2 ГГц (2 * 10^9 тактов в секунду) теоретическая максимальная пропускная способность составляет около 1 Гбайт/с. Если блоки можно обрабатывать параллельно, дожидаться завершения одного вызова AESENC перед запуском другого не требуется. В таком случае за такт можно выполнять два вызова AESENC и получать два результата, что даёт значительно более высокую теоретическую пропускную способность - свыше 10 Гбайт/с при 2 ГГц - в зависимости от размера данных и режима работы.

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

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

После более чем 15 лет и сотен исследовательских публикаций мы лишь слегка прикоснулись к теоретической безопасности AES. В 2011 году криптоаналитики нашли способ восстановить ключ AES-128, выполнив около 2^126 операций вместо 2^128, то есть ускорив перебор в четыре раза. Но этой «атаке» требуется огромное число пар «открытый текст - шифротекст» - около 2^88 битов данных. Это интересный результат, но беспокоиться о нём не стоит.

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

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

Самый простой режим шифрования блочным шифром - электронная кодовая книга (electronic codebook, ECB), которую вообще едва ли можно назвать режимом работы. ECB принимает блоки открытого текста P_1, P_2, ..., P_N и обрабатывает каждый независимо, вычисляя C_1 = E(K, P_1), C_2 = E(K, P_2) и так далее, как показано на рис. 4-6. Операция проста, но небезопасна: ECB небезопасен, и использовать его не следует.

Рисунок 4-6. Режим ECB

Криптограф Microsoft Марш Рэй однажды сказал: «Все знают, что режим ECB плох, потому что мы видим пингвина». Он имел в виду знаменитую иллюстрацию небезопасности ECB с изображением талисмана Linux - пингвина Такса, как на рис. 4-7.

Рисунок 4-7. Исходное изображение (слева) и изображение, зашифрованное в ECB (справа)

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

Программа на Python в листинге 4-4 также демонстрирует небезопасность ECB. Она выбирает псевдослучайный ключ и шифрует 32-байтовое сообщение p, содержащее два блока нулевых байтов. Обратите внимание: шифрование даёт два одинаковых блока, а повторное шифрование с тем же ключом и тем же открытым текстом снова создаёт те же два блока.

Листинг 4-4. Использование AES в режиме ECB в Python

Выполнение этого сценария даёт следующие блоки шифротекста:

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

Другая проблема ECB состоит в том, что режим принимает только полные блоки данных. Поэтому при 16-байтовых блоках, как у AES, можно шифровать лишь фрагменты длиной 16, 32, 48 байт или любое другое число байтов, кратное 16. Существует несколько способов решить эту проблему, как вы увидите на примере следующего режима CBC. (Я не стану рассказывать, как эти приёмы работают с ECB, потому что ECB вообще не следует использовать.)

Сцепление блоков шифротекста (cipher block chaining, CBC) похоже на ECB, но с небольшим изменением, которое приводит к большой разнице: вместо шифрования i-го блока P_i как C_i = E(K, P_i) режим CBC задаёт C_i = E(K, P_i xor C_(i-1)), где C_(i-1) - предыдущий блок шифротекста; тем самым блоки C_(i-1) и C_i сцепляются. При шифровании первого блока P_1 предыдущего блока шифротекста ещё нет, поэтому CBC принимает случайное начальное значение (initial value, IV), как показано на рис. 4-8.

Рисунок 4-8. Режим CBC

Режим CBC делает каждый блок шифротекста зависимым от всех предыдущих блоков и гарантирует, что одинаковые блоки открытого текста не станут одинаковыми блоками шифротекста. Случайное начальное значение гарантирует, что два одинаковых открытых текста будут зашифрованы в разные шифротексты, если два вызова шифра используют два разных начальных значения.

Листинг 4-5 иллюстрирует оба преимущества. Программа принимает 32-байтовое сообщение из одних нулей, как в листинге 4-4, дважды шифрует его в CBC и показывает два шифротекста. Выделенная в оригинале строка iv = urandom(BLOCK_SIZE) выбирает новое случайное IV для каждого нового шифрования.

Листинг 4-5. Использование AES в режиме CBC

Два открытых текста одинаковы и состоят из двух нулевых блоков, но зашифрованные блоки должны различаться, как в следующем примере выполнения:

Увы, CBC часто используют с постоянным, а не случайным IV, что раскрывает одинаковые открытые тексты и открытые тексты, начинающиеся с одинаковых блоков. Например, предположим, что CBC шифрует двухблочный открытый текст P_1 || P_2 в двухблочный шифротекст C_1 || C_2. Если CBC с тем же IV шифрует P_1 || P_2', где P_2' - блок, отличный от P_2, получившийся шифротекст будет выглядеть как C_1 || C_2', где C_2' отличается от C_2, но первый блок C_1 совпадает. Поэтому злоумышленник может догадаться, что первый блок обоих открытых текстов одинаков, хотя видит лишь шифротексты.

Примечание. Для расшифрования в режиме CBC необходимо знать IV, использованное при шифровании, поэтому IV передаётся вместе с шифротекстом в открытом виде.

Благодаря параллелизму расшифрование CBC может быть значительно быстрее шифрования. При шифровании нового блока P_i необходимо дождаться предыдущего блока C_(i-1), а расшифрование блока вычисляет P_i = D(K, C_i) xor C_(i-1), и предыдущий блок открытого текста P_(i-1) не требуется. Это означает, что все блоки можно расшифровывать параллельно и одновременно, если известен предыдущий блок шифротекста, а обычно он известен.

Вернёмся к проблеме завершения блока и рассмотрим обработку открытого текста, длина которого не кратна длине блока. Например, как зашифровать 18-байтовый открытый текст с помощью AES-CBC при 16-байтовых блоках? Что делать с оставшимися двумя байтами? Мы рассмотрим два широко применяемых решения. Первое, заполнение, делает шифротекст немного длиннее открытого текста, а второе, похищение шифротекста, создаёт шифротекст той же длины, что и открытый текст.

Заполнение - метод, позволяющий зашифровать сообщение любой длины, даже короче одного блока. Стандарт PKCS#7 и RFC 5652 определяют заполнение для блочных шифров, применяемое почти везде, где используется CBC.

С помощью заполнения сообщение расширяют до полного блока, добавляя к открытому тексту дополнительные байты. Для 16-байтовых блоков действуют следующие правила:

• Если остаётся 1 байт, например длина открытого текста равна 1, 17 или 33 байтам, сообщение дополняется 15 байтами 0f (15 в десятичной системе).

• Если остаётся 2 байта, сообщение дополняется 14 байтами 0e (14 в десятичной системе).

• Если остаётся 3 байта, сообщение дополняется 13 байтами 0d (13 в десятичной системе).

Если имеется 15 байт открытого текста и для заполнения блока не хватает одного байта, добавляется единственный байт 01. Если длина открытого текста уже кратна 16 - длине блока, добавляется 16 байтов 10 (16 в десятичной системе). Этот приём обобщается на любую длину блока до 255 байт; для более крупных блоков одного байта недостаточно, чтобы закодировать значения больше 255.

Расшифрование заполненного сообщения работает так:

1. Расшифровать все блоки, как в CBC без заполнения.

2. Убедиться, что последние байты последнего блока соответствуют правилу заполнения: оканчиваются как минимум одним байтом 01, как минимум двумя байтами 02, как минимум тремя байтами 03 и так далее. Если заполнение недопустимо, например последние байты равны 01 02 03, сообщение отклоняется. В противном случае расшифрование удаляет байты заполнения и возвращает оставшиеся байты открытого текста.

Один из недостатков заполнения состоит в том, что оно увеличивает шифротекст как минимум на один байт и максимум на целый блок.

Похищение шифротекста - ещё один приём шифрования сообщений, длина которых не кратна размеру блока. Он сложнее и менее популярен, чем заполнение, но даёт несколько преимуществ:

• Открытые тексты могут иметь любую длину в битах, а не только целое число байтов. Например, можно зашифровать 131-битное сообщение.

• Длина шифротекста в точности совпадает с длиной открытого текста.

• Похищение шифротекста не уязвимо для атак на оракул заполнения - мощных атак, иногда действующих против CBC с заполнением, как вы увидите в разделе «Атаки на оракул заполнения».

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

На рис. 4-9 показаны три блока, последний из которых, P_3, неполон и обозначен нулём. Если P_3 имеет длину 3 байта, мы выполняем его XOR с последними 12 байтами предыдущего блока шифротекста E(K, P_2) и возвращаем зашифрованный результат как C_2. Последний блок шифротекста C_3 затем состоит из первых четырёх байтов E(K, P_2). Расшифрование представляет собой простое обращение этой операции.

Рисунок 4-9. Похищение шифротекста при шифровании в режиме CBC

У похищения шифротекста нет серьёзных проблем, но этот метод неизящен, и реализовать его правильно трудно, особенно учитывая, что стандарт NIST определяет три разных способа реализации (см. Special Publication 800-38A).

Чтобы избежать проблем и сохранить преимущества похищения шифротекста, используйте режим счётчика (counter mode, CTR). CTR едва ли можно назвать режимом блочного шифра: он превращает блочный шифр в потоковый, который просто принимает биты и выдаёт биты, не обременяя себя понятием блоков. (Потоковые шифры подробно рассматриваются в главе 5.)

В режиме CTR (см. рис. 4-10) алгоритм блочного шифра не преобразует данные открытого текста. Вместо этого он шифрует блоки, составленные из счётчика и nonce. Счётчик - целое число, увеличиваемое для каждого блока. В пределах одного сообщения никакие два блока не должны использовать одинаковый счётчик, но разные сообщения могут применять одну и ту же последовательность значений счётчика (1, 2, 3, ...). Nonce - число, используемое только один раз. Оно одинаково для всех блоков одного сообщения, но никакие два сообщения не должны использовать одно и то же nonce.

Рисунок 4-10. Режим CTR

На рис. 4-10 показано, что при шифровании в режиме CTR выполняется XOR открытого текста с потоком, полученным «шифрованием» nonce N и счётчика Ctr. Расшифрование выполняется так же, поэтому и для шифрования, и для расшифрования нужен только алгоритм шифрования. Практический пример приведён в сценарии Python из листинга 4-6.

Листинг 4-6. Использование AES в режиме CTR

В этом примере выполнения четырёхбайтовый открытый текст шифруется в четырёхбайтовый шифротекст. Затем шифротекст расшифровывается с помощью функции шифрования:

Как и начальное значение CBC, nonce режима CTR задаётся шифрующей стороной и отправляется вместе с шифротекстом в открытом виде. Но в отличие от начального значения CBC nonce CTR не обязано быть случайным; оно должно быть лишь уникальным. Nonce должно быть уникальным по той же причине, по которой нельзя повторно использовать одноразовый блокнот: если при вызове псевдослучайного потока S с одним nonce зашифровать P_1 в C_1 = P_1 xor S, а P_2 - в C_2 = P_2 xor S, то C_1 xor C_2 раскроет P_1 xor P_2.

Случайное nonce решает задачу, только если оно достаточно длинное. Например, если длина nonce равна n битам, после 2^(n/2) шифрований и такого же числа nonce, скорее всего, появятся повторы. Для случайного nonce 64 бит недостаточно, поскольку повторения можно ожидать приблизительно после 2^32 nonce, а это неприемлемо малое число.

Уникальность счётчика гарантируется, если он увеличивается для каждого нового открытого текста и достаточно длинен, например имеет длину 64 бита.

Особое преимущество CTR состоит в возможности работать быстрее любого другого режима. Он не только допускает распараллеливание: шифрование можно начать ещё до получения сообщения, выбрав nonce и вычислив поток, с которым позднее будет выполнен XOR открытого текста.

Примечание. В зависимости от реализуемой версии CTR nonce, передаваемое API как аргумент, можно конкатенировать со счётчиком, как на рис. 4-10, либо непосредственно использовать счётчик шириной в целый блок.

Необходимо знать две атаки на блочные шифры: атаку «встреча посередине» - метод, открытый в 1970-х годах, но по-прежнему применяемый во многих криптоаналитических атаках и не имеющий отношения к атаке «человек посередине», - и атаку на оракул заполнения, класс атак, открытый академическими криптографами в 2002 году, затем по большей части проигнорированный и наконец вновь открытый десятилетие спустя вместе с несколькими уязвимыми приложениями.

Блочный шифр 3DES - усовершенствованная версия стандарта DES 1970-х годов, принимающая ключ длиной 56 * 3 = 168 бит, что лучше 56-битного ключа DES. Но из-за атаки «встреча посередине» (meet-in-the-middle, MitM) уровень стойкости 3DES равен 112, а не 168 битам.

На рис. 4-11 показано, как 3DES шифрует блок с помощью функций шифрования и расшифрования DES: сначала выполняется шифрование с ключом K_1, затем расшифрование с ключом K_2 и, наконец, шифрование с другим ключом K_3. Если K_1 = K_2, первые два вызова взаимно уничтожаются, и 3DES сводится к одному DES с ключом K_3. В 3DES выполняется последовательность «шифрование - расшифрование - шифрование», а не тройное шифрование, чтобы при необходимости системы могли имитировать DES через новый интерфейс 3DES.

Рисунок 4-11. Конструкция блочного шифра 3DES

Почему используется тройной DES, а не просто двойной DES, то есть почему открытый текст P не шифруется в E(K_2, E(K_1, P))? Оказывается, из-за атаки MitM двойной DES лишь настолько же безопасен, как одинарный. Атака MitM показана на рис. 4-12.

Рисунок 4-12. Атака MitM

Атака на двойной DES методом MitM работает следующим образом:

1. Предположим, у вас имеются P и C = E(K_2, E(K_1, P)) с двумя неизвестными 56-битными ключами K_1 и K_2. (DES принимает 56-битные ключи, поэтому в двойном DES суммарно 112 бит ключа.) Вы строите таблицу «ключ - значение» из 2^56 записей E(K_1, P), где в качестве значения хранится K_1.

2. Для всех 2^56 значений K_2 вычисляете D(K_2, C) и проверяете, присутствует ли полученное значение в таблице как индекс, то есть как среднее значение, обозначенное вопросительным знаком на рис. 4-12.

3. Если среднее значение обнаружено как индекс таблицы, извлекаете из таблицы соответствующий K_1 и по другим парам P и C проверяете, что найденная пара (K_1, K_2) верна. Зашифруйте P с помощью K_1 и K_2, а затем проверьте, совпадает ли полученный шифротекст с заданным C.

Этот метод восстанавливает K_1 и K_2, выполняя около 2^57 вместо 2^112 операций: на шаге 1 шифруются 2^56 блоков, затем на шаге 2 расшифровывается не более 2^56 блоков, что в сумме даёт 2^56 + 2^56 = 2^57 операций. Кроме того, необходимо хранить 2^56 элементов по 15 байт, или около одного эксабайта. Это много, но существует приём, позволяющий выполнить ту же атаку с пренебрежимо малым объёмом памяти, как вы увидите в главе 6.

Атаку MitM можно применить к 3DES почти так же, как к двойному DES, за исключением того, что на третьем этапе перебираются все 2^112 сочетаний K_2 и K_3. Вся атака завершается примерно за 2^112 операций, поэтому при 168 битах ключевого материала 3DES обеспечивает лишь 112-битную стойкость.

Эту главу завершает одна из простейших и вместе с тем самых разрушительных атак 2000-х годов - атака на оракул заполнения. Помните, что заполнение дополняет открытый текст лишними байтами до целого блока. Например, открытый текст длиной 111 байт представляет собой последовательность из шести 16-байтовых блоков, за которыми следуют 15 байт. В таком случае для образования полного блока заполнение добавляет байт 01. К 110-байтовому открытому тексту добавляются два байта 02, к 109-байтовому - три байта 03 и так далее, вплоть до случая, когда добавляются 16 байтов 10, где шестнадцатеричное значение 10 равно 16.

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

Предположим, вы хотите расшифровать блок шифротекста C_2. Обозначим через X искомое значение D(K, C_2), а через P_2 - блок, полученный после расшифрования в режиме CBC (см. рис. 4-13). Если выбрать случайный блок C_1 и отправить оракулу двухблочный шифротекст C_1 || C_2, расшифрование завершится успешно только в том случае, если C_1 xor X = P_2 оканчивается допустимым заполнением: одним байтом 01, двумя байтами 02, тремя байтами 03 и так далее.

Рисунок 4-13. Атака на оракул заполнения восстанавливает X, выбирая C1 и проверяя допустимость заполнения.

Исходя из этого наблюдения, атака на оракул заполнения в режиме CBC может расшифровать блок C_2 следующим образом. Байты обозначаются как элементы массива: C1[0] - первый байт C_1, C1[1] - второй и так далее до C1[15], последнего байта C_1.

1. Выберите случайный блок C_1 и изменяйте его последний байт, пока оракул заполнения не примет шифротекст как допустимый. Обычно в допустимом шифротексте C_1[15] xor X[15] = 01, поэтому X[15] будет найден приблизительно после перебора 128 значений C_1[15].

2. Найдите значение X[14], присвоив C1[15] значение X[15] xor 02 и подбирая C1[14], дающий правильное заполнение. Когда оракул принимает шифротекст как допустимый, это означает, что найдено значение C1[14], при котором C_1[14] xor X[14] = 02.

3. Повторите шаги 1 и 2 для всех 16 байтов.

Атаке в среднем требуется 128 запросов к оракулу для каждого из 16 байтов, то есть всего около 2000 запросов. (Обратите внимание: каждый запрос должен использовать одно и то же начальное значение.)

Примечание. На практике реализовать атаку на оракул заполнения несколько сложнее, чем описано здесь, поскольку на шаге 1 приходится учитывать ошибочные догадки. Шифротекст может иметь допустимое заполнение не потому, что P_2 оканчивается единственным байтом 01, а потому, что оканчивается двумя байтами 02 или тремя байтами 03. С этим можно справиться, проверяя допустимость шифротекстов, в которых изменено больше байтов.

О блочных шифрах можно рассказать очень многое: и о работе алгоритмов, и о способах атак на них. Например, сети Фейстеля и SPN - не единственные способы построения блочного шифра. В блочных шифрах IDEA и FOX используется конструкция Лая-Мэсси, а в Threefish - сети ARX, сочетающие сложение, циклические сдвиги слов и XOR.

MAC защищает целостность и подлинность сообщения, создавая значение T=MAC(K,M), которое называется тегом аутентификации сообщения M, хотя его часто не вполне точно называют MAC сообщения M. Подобно тому как знание ключа шифра позволяет расшифровать сообщение, знание ключа MAC позволяет проверить, что сообщение не было изменено.

PRF использует секретный ключ и возвращает PRF(K,M), причем результат выглядит случайным. Поскольку ключ секретен, выходные значения непредсказуемы для атакующего.

В отличие от MAC, PRF предназначены не для самостоятельного использования, а для включения в криптографический алгоритм или протокол. Например, с помощью PRF можно создавать блочные шифры внутри конструкции Фейстеля; см. раздел «Как строятся блочные шифры» главы 4. Схемы получения ключей применяют PRF для генерации криптографических ключей из мастер-ключа или пароля, а схемы идентификации - для создания ответа на случайный вызов. В сущности, сервер отправляет случайное сообщение-вызов M, а клиент в ответ возвращает PRF(K,M), доказывая знание K. Стандарт мобильной связи 5G использует PRF для взаимной аутентификации SIM-карты и поставщика услуг, а похожая PRF формирует ключ шифрования и ключ MAC для телефонного разговора. Протокол TLS использует PRF для формирования ключевого материала из главного секрета и случайных значений конкретного сеанса. PRF есть даже во встроенной некриптографической функции hash() языка Python, используемой для сравнения объектов.

Безопасная псевдослучайная функция не должна иметь закономерностей, отличающих ее выходные данные от истинно случайных значений. Атакующий, не знающий ключа K, не должен уметь отличить результаты PRF(K,M) от случайных значений. Иначе говоря, у атакующего не должно быть способа понять, взаимодействует он с алгоритмом PRF или со случайной функцией. Научное название этого свойства безопасности - «неразличимость со случайной функцией». Подробнее о теоретических основах PRF см. том 1, раздел 3.6 книги Голдрайха «Foundations of Cryptography».

PRF и MAC являются хешами с ключом, но PRF принципиально сильнее MAC, потому что требования безопасности к MAC слабее. MAC считается безопасным, если атакующий не способен подделывать теги, то есть угадывать выходные данные MAC, тогда как PRF безопасна только в том случае, если ее выходные данные неотличимы от случайных строк. Если выходные данные PRF невозможно отличить от случайных строк, их значения невозможно угадать. Иными словами, любая безопасная PRF является также безопасным MAC.

Обратное утверждение неверно: безопасный MAC не обязательно является безопасной PRF. Предположим, имеется безопасная функция PRF_1, на основе которой требуется построить вторую функцию PRF_2 следующим образом:

Поскольку выход PRF_2 определяется как выход PRF_1 с приписанным нулевым битом, он не выглядит столь же случайным, как истинно случайная строка: выходные данные можно отличить по последнему нулевому биту. Следовательно, PRF_2 не является безопасной PRF. Однако благодаря безопасности PRF_1 функция PRF_2 все равно будет безопасным MAC. Если бы вы могли подделать тег T=PRF_2(K,M) для некоторого M, вы могли бы подделать и тег PRF_1, а это, как известно из исходного предположения, невозможно, поскольку PRF_1 - безопасный MAC. Таким образом, PRF_2 представляет собой хеш с ключом, являющийся безопасным MAC, но не безопасной PRF.

Но не волнуйтесь: в реальных приложениях такие конструкции MAC не встречаются. В действительности многие развернутые или стандартизированные MAC являются также безопасными PRF и часто используются в обеих ролях. Например, TLS применяет алгоритм HMAC-SHA-256 и как MAC, и как PRF.

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

Первый рассматриваемый метод - конструкция с секретным префиксом - превращает обычную хеш-функцию в хеш с ключом, приписывая ключ перед сообщением и возвращая Hash(K || M). Этот подход небезопасен, когда хеш-функция уязвима к атакам с удлинением сообщения, рассмотренным в главе 6, и когда хеш поддерживает ключи разной длины.

Напомним из главы 6, что хеш-функции семейства SHA-2 позволяют атакующим вычислить хеш частично неизвестного сообщения, если известен хеш более короткой версии этого сообщения. Формально атака с удлинением сообщения позволяет вычислить Hash(K || M_1 || M_2), зная только Hash(K || M_1) и не зная ни M_1, ни K. Эти функции позволяют атакующим бесплатно подделывать действительные теги MAC, поскольку они не должны уметь угадывать MAC сообщения M_1 || M_2, имея только MAC сообщения M_1. Поэтому конструкция с секретным префиксом небезопасна как MAC и PRF при использовании, например, с SHA-256 или SHA-512. Уязвимость к атакам с удлинением сообщения - слабость конструкции Меркла - Дамгора; ни у одного финалиста SHA-3 ее нет. Способность противостоять таким атакам была обязательным требованием к кандидатам SHA-3, см. главу 6.

Конструкция с секретным префиксом также небезопасна, если разрешены ключи разной длины. Например, если ключ K - 24-битная шестнадцатеричная строка 123abc, а M равно def00, функция Hash() обрабатывает значение K || M=123abcdef00. Если же K - 16-битная строка 123a, а M равно bcdef000, функция Hash() также обрабатывает K || M=123abcdef00. Поэтому результат конструкции с секретным префиксом Hash(K || M) для обоих ключей одинаков.

Эта проблема не зависит от лежащего в основе хеша. Ее можно исправить, хешируя длину ключа вместе с ключом и сообщением: например, закодировать битовую длину ключа 16-битным целым числом L, а затем вычислить Hash(L || K || M). Однако делать это самостоятельно не следует: современные хеш-функции, такие как BLAKE2 и SHA-3, включают режим с ключом, лишенный этих недостатков и формирующий безопасную PRF, а значит, и безопасный MAC.

Вместо того чтобы хешировать ключ перед сообщением, как в конструкции с секретным префиксом, его можно хешировать после сообщения. Именно так работает конструкция с секретным суффиксом, строящая PRF из хеш-функции как Hash(M || K).

Размещение ключа в конце существенно меняет ситуацию. Атака с удлинением сообщения, работающая против MAC с секретным префиксом, не работает против секретного суффикса. Применение удлинения к MAC с секретным суффиксом дает Hash(M_1 || K || M_2) из Hash(M_1 || K), но это не действительная атака, поскольку Hash(M_1 || K || M_2) не является допустимым MAC с секретным суффиксом: ключ должен находиться в конце.

Однако конструкция с секретным суффиксом слабее против другого типа атак. Предположим, имеется коллизия хеша Hash(M_1)=Hash(M_2) для двух разных сообщений M_1 и M_2, возможно, разной длины. Для хеш-функции M-D, такой как SHA-256, это означает также равенство Hash(M_1 || P_1 || K) и Hash(M_2 || P_2 || K), где P_1 и P_2 - данные дополнения до полного блока. После обработки M_1 || P_1 состояние хеш-функции совпадает с состоянием после обработки M_2 || P_2. Добавление K к каждому экземпляру сохраняет равенство состояний и приводит к коллизии независимо от значения K.

Чтобы воспользоваться этим свойством, атакующий:

1. Находит два коллидирующих сообщения M_1 и M_2.

2. Запрашивает тег MAC сообщения M_1: Hash(M_1 || K).

3. Предполагает, что Hash(M_2 || K) совпадает с ним, тем самым подделывая действительный тег и нарушая безопасность MAC.

Конструкция hash-based MAC (HMAC) позволяет построить MAC из хеш-функции и безопаснее как секретного префикса, так и секретного суффикса. HMAC дает безопасную PRF, пока лежащий в ее основе хеш устойчив к коллизиям. Но даже если это не так, HMAC все равно дает безопасную PRF при условии, что функция сжатия хеша является PRF. HMAC применялся в протоколах защищенной связи IPsec, SSH и TLS. Спецификации HMAC находятся в стандарте NIST FIPS 198-1 и RFC 2104.

HMAC использует хеш-функцию Hash для вычисления тега MAC, как показано на рисунке 7-1 и в следующем выражении:

Значение opad, внешнее дополнение, представляет собой шестнадцатеричную строку 5c5c5c...5c длиной с блок функции Hash. Ключ K обычно короче одного блока; его дополняют байтами 00 и складывают посредством XOR с opad. Например, если K - однобайтовая строка 00, то K xor opad=opad. То же верно, если K является строкой из одних нулей любой длины, не превышающей длину блока. K xor opad - первый блок, обрабатываемый внешним вызовом Hash, то есть крайним левым Hash в приведенном выражении или нижним хешем на рисунке 7-1.

Рисунок 7-1. Конструкция MAC на основе хеша HMAC для хеш-функции, основанной на функции сжатия

Значение ipad, внутреннее дополнение, представляет собой строку 363636...36 длиной с блок функции Hash и дополняется байтами 00. Полученный блок первым обрабатывается внутренним вызовом Hash, то есть крайним правым Hash в выражении или верхним хешем на рисунке 7-1.

Примечание. Метод конверта безопаснее конструкции с секретным префиксом или секретным суффиксом. Он выражается как Hash(K || M || K) и представляет собой MAC-сэндвич, но теоретически уступает HMAC по безопасности.

Если в качестве Hash используется хеш-функция SHA-256, экземпляр HMAC называется HMAC-SHA-256. В общем случае экземпляр HMAC с хеш-функцией Hash называют HMAC-Hash. Поэтому, если кто-то просит вас использовать HMAC, всегда следует спросить: «С какой хеш-функцией?»

Существует атака, работающая против всех MAC на основе итеративной хеш-функции. Вспомните атаку на конструкцию с секретным суффиксом, где коллизия хеша использовалась для получения коллизии MAC. Та же стратегия применима против MAC с секретным префиксом или HMAC, хотя последствия менее разрушительны.

На рисунке 7-2 показан MAC с секретным префиксом Hash(K || M).

Рисунок 7-2. Принцип универсальной атаки с подделкой на MAC на основе хеша

Если длина дайджеста равна n битам, можно найти два сообщения M_1 и M_2, такие что Hash(K || M_1)=Hash(K || M_2), запросив примерно 2^(n/2) тегов MAC у системы, хранящей ключ. Вспомните атаку дней рождения из главы 6. Если хеш допускает удлинение сообщения, как SHA-256, затем можно использовать M_1 и M_2 для подделки MAC: выбрать произвольные данные M_3 и запросить у оракула MAC значение Hash(K || M_1 || M_3), то есть MAC сообщения M_1 || M_3. Оказывается, это также MAC сообщения M_2 || M_3, поскольку внутреннее состояние хеша для M_1 с M_3 совпадает с состоянием для M_2 с M_3. Тег MAC успешно подделан. При n больше, например, 128 битов требуемые усилия становятся неосуществимыми.

Эта атака работает, даже если хеш-функция не уязвима к удлинению сообщения, и применима также к HMAC. Достаточно внутренней коллизии хеш-функции, необязательно коллизии полного хеша. Стоимость атаки зависит как от размера цепочного значения, так и от длины MAC: если цепочное значение MAC имеет длину 512 битов, а теги - 128 битов, вычисление за 2^64 операций найдет коллизию MAC, но, скорее всего, не коллизию внутреннего состояния, поскольку для ее нахождения требуется в среднем 2^(512/2)=2^256 операций.

Функции сжатия во многих хеш-функциях строятся на блочных шифрах, см. главу 6. Например, PRF HMAC-SHA-256 представляет собой последовательность вызовов функции сжатия SHA-256, которая является блочным шифром, повторяющим последовательность раундов. Иными словами, HMAC-SHA-256 - это блочный шифр внутри функции сжатия внутри хеша внутри конструкции HMAC. Так почему бы не использовать блочный шифр напрямую вместо такой многослойной конструкции?

Cipher-based MAC (CMAC) - именно такая конструкция: она создает MAC, имея только блочный шифр, например AES. Хотя CMAC менее популярен, чем HMAC, он развернут во множестве систем, включая протокол Internet Key Exchange (IKE), входящий в набор IPsec. Например, IKE генерирует ключевой материал, используя в качестве основного алгоритма конструкцию AES-CMAC-PRF-128, то есть основанный на AES CMAC со 128-битным выходом. CMAC определен в RFC 4493.

CMAC был разработан в 2005 году как улучшенная версия CBC-MAC - более простого MAC на основе блочного шифра, производного от режима работы блочного шифра с сцеплением блоков шифртекста (CBC), рассмотренного в главе 4.

CBC-MAC, предшественник CMAC, прост: чтобы вычислить тег сообщения M при помощи блочного шифра E, нужно зашифровать M в режиме CBC с нулевым начальным значением (IV) и отбросить все блоки шифртекста, кроме последнего. Иными словами, вычисляется

и так далее для каждого блока M, после чего сохраняется только последний C_i - тег CBC-MAC сообщения M. Просто и так же просто атакуется.

Чтобы понять, почему CBC-MAC небезопасен, рассмотрим тег CBC-MAC T_1=E(K,M_1) одноблочного сообщения M_1 и тег T_2=E(K,M_2) другого одноблочного сообщения M_2. Имея две пары (M_1,T_1) и (M_2,T_2), можно заключить, что T_2 является также тегом двухблочного сообщения M_1 || (M_2 xor T_1). Если применить CBC-MAC к M_1 || (M_2 xor T_1), получится C_1=E(K,M_1)=T_1, а затем C_2=E(K,(M_2 xor T_1) xor T_1)=E(K,M_2)=T_2. Таким образом, из двух пар «сообщение/тег» можно создать третью, не зная ключа. Иными словами, можно подделывать теги CBC-MAC, нарушая его безопасность.

CMAC исправляет CBC-MAC, обрабатывая последний блок ключом, отличным от ключа предыдущих блоков. Для этого CMAC сначала получает из основного ключа K два ключа K_1 и K_2, причем K, K_1 и K_2 различны. Последний блок CMAC обрабатывает либо с K_1, либо с K_2, тогда как предыдущие блоки используют K.

Чтобы определить K_1 и K_2, CMAC сначала вычисляет временное значение L=E(0,K), где 0 служит ключом блочного шифра, а K - блоком открытого текста. Затем CMAC полагает K_1=(L<<1), если старший значащий бит (most significant bit, MSB) L равен 0, и K_1=(L<<1) xor 87, если MSB L равен 1. Шестнадцатеричное число 87, равное 135 в десятичной системе, выбрано за математические свойства для 128-битных блоков данных; если размер блока отличается от 128 битов, требуется другое значение. Ключ K_2 полагается равным (K_1<<1), если MSB K_1 равен 0, и K_2=(K_1<<1) xor 87 в противном случае.

Имея K_1 и K_2, CMAC работает как CBC-MAC, за исключением последнего блока. Если последний фрагмент сообщения M_n имеет ровно размер блока, CMAC возвращает в качестве тега E(K,M_n xor C_(n-1) xor K_1), как показано на рисунке 7-3.

Рисунок 7-3. Конструкция MAC на основе блочного шифра CMAC, когда сообщение состоит из целого числа блоков

Если в M_n меньше битов, чем в блоке, CMAC дополняет его единичным битом и нулями и возвращает в качестве тега E(K,M_n xor C_(n-1) xor K_2), как показано на рисунке 7-4.

Рисунок 7-4. Конструкция MAC на основе блочного шифра CMAC, когда последний блок сообщения дополняется единичным битом и нулями до полного блока

В первом случае используется только K_1, а во втором - только K_2, но в обоих случаях фрагменты сообщения перед последним обрабатываются основным ключом K.

В отличие от режима шифрования CBC, CMAC не принимает IV как параметр и является детерминированным: при одном ключе CMAC всегда возвращает один и тот же тег заданного сообщения M, поскольку вычисление CMAC(M) не рандомизировано. Это допустимо: в отличие от шифрования, вычисление MAC не обязано быть рандомизированным для безопасности, что избавляет от необходимости выбирать случайный IV.

Вы увидели, как повторно использовать хеш-функции и блочные шифры для построения PRF, остающихся безопасными, пока безопасен лежащий в основе хеш или шифр. Такие схемы, как HMAC и CMAC, просто объединяют доступные хеш-функции или блочные шифры, получая безопасную PRF или MAC. Повторное использование готовых алгоритмов удобно, но действительно ли это самый эффективный подход?

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

Следующие разделы посвящены двум таким алгоритмам: Poly1305 и SipHash. Я объясню принципы их устройства и причины их предполагаемой безопасности.

Алгоритм Poly1305, произносимый «поли-тринадцать-ноль-пять», был разработан в 2005 году Дэниелом Дж. Бернстайном, создателем потокового шифра Salsa20 из главы 5 и шифра ChaCha, вдохновившего хеш-функции BLAKE и BLAKE2 из главы 6. Poly1305 оптимизирован для сверхбыстрой работы на современных CPU и на момент написания книги входит в число алгоритмов, поддерживаемых TLS 1.3 и OpenSSH, а также множеством других приложений. В отличие от Salsa20, конструкция Poly1305 основана на методах 1970-х годов: универсальных хеш-функциях и конструкции Вегмана - Картера.

MAC Poly1305 использует универсальную хеш-функцию. Такая хеш-функция слабее криптографической, но намного быстрее. Например, универсальные хеш-функции не обязаны быть устойчивыми к коллизиям.

Подобно PRF, универсальный хеш параметризуется секретным ключом: результат универсальной хеш-функции UH для сообщения M и ключа K будем записывать как UH(K,M). У универсальной хеш-функции только одно требование безопасности: для любых двух сообщений M_1 и M_2 и случайного ключа K вероятность равенства UH(K,M_1) и UH(K,M_2) должна быть пренебрежимо мала. В отличие от PRF, универсальный хеш не обязан быть псевдослучайным; просто не должно существовать пары (M_1,M_2), дающей один хеш для множества разных ключей. Поскольку их требования безопасности выполнить легче, универсальные хеш-функции требуют меньше операций и намного быстрее PRF.

Однако универсальный хеш можно использовать как MAC для аутентификации не более одного сообщения. В качестве примера рассмотрим универсальный хеш с вычислением многочлена, применяемый в Poly1305. См. основополагающую статью Эдгара Гилберта, Джесси Мак-Уильямс и Нила Слоуна «Codes Which Detect Deception» 1974 года, где это понятие описано подробнее. Такой хеш с вычислением многочлена параметризуется простым числом p и принимает ключ из двух чисел R и K в диапазоне [1,p) и сообщение M, состоящее из n блоков (M_1,M_2,...,M_n). Результат универсального хеша вычисляется следующим образом:

В этом уравнении знак плюс обозначает сложение положительных целых чисел, K^i - число K в степени i, а mod p - приведение результата по модулю p, то есть остаток от деления результата на p. Например, 12 mod 10=2, 10 mod 10=0, 8 mod 10=8 и так далее.

Поскольку хеширование должно выполняться как можно быстрее, MAC на основе универсального хеша часто работают со 128-битными блоками сообщений и простым числом p, немного превышающим 2^128, например 2^128+51. Ширина 128 битов позволяет создавать очень быстрые реализации, эффективно использующие 32- и 64-битные арифметические устройства распространенных CPU.

У универсальных хешей есть одна слабость: поскольку универсальный хеш безопасно аутентифицирует лишь одно сообщение, атакующий может взломать приведенный выше MAC с вычислением многочлена, запросив теги всего двух сообщений. В частности, он может запросить тег сообщения, все блоки которого равны нулю, M_1=M_2=...=0, и получить UH(R,K,0)=R, тем самым найдя секретное значение R. Затем он может запросить тег сообщения, в котором M_1=1, а M_2=M_3=...=0; его тег равен T=R+K. Вычтя R из T, атакующий найдет K. Теперь он знает весь ключ (R,K) и способен подделать MAC любого сообщения.

К счастью, существует способ перейти от безопасности одного сообщения к безопасности множества сообщений.

Прием аутентификации множества сообщений с помощью универсальной хеш-функции появился благодаря исследователям IBM Марку Вегману и Лоуренсу Картеру и их статье 1981 года «New Hash Functions and Their Use in Authentication and Set Equality». Конструкция Вегмана - Картера строит MAC из универсальной хеш-функции и PRF, использует два ключа K_1 и K_2 и возвращает

где N - одноразовый номер, который должен использоваться не более одного раза для каждого ключа K_2, а выход PRF имеет тот же размер, что выход универсальной хеш-функции UH. При сложении этих значений сильный псевдослучайный выход PRF маскирует криптографическую слабость UH. Это можно рассматривать как шифрование результата универсального хеша, где PRF действует как потоковый шифр и предотвращает описанную выше атаку, позволяя аутентифицировать множество сообщений одним ключом K_1.

Подведем итог: конструкция Вегмана - Картера UH(K_1,M)+PRF(K_2,N) дает безопасный MAC при следующих предположениях:

• UH является безопасным универсальным хешем.

• PRF является безопасной PRF.

• Каждый одноразовый номер N используется только один раз для каждого ключа K_2.

• Выходные значения UH и PRF достаточно длинны для обеспечения требуемого уровня безопасности.

Теперь рассмотрим, как Poly1305 использует конструкцию Вегмана - Картера для построения безопасного и быстрого MAC.

Изначально Poly1305 был предложен как Poly1305-AES, объединяющий универсальный хеш Poly1305 с блочным шифром AES. Poly1305-AES намного быстрее MAC на основе HMAC и даже CMAC, поскольку вычисляет всего один блок AES, а сообщение обрабатывает параллельно с помощью ряда простых арифметических операций.

Для 128-битных K_1, K_2 и N и сообщения M Poly1305-AES возвращает

Приведение по модулю 2^128 гарантирует, что результат помещается в 128 битов. Poly1305 разбирает сообщение M как последовательность 128-битных блоков (M_1,M_2,...,M_n) и добавляет к старшему разряду каждого блока 129-й бит, делая все блоки 129-битными. Если последний блок короче 16 байтов, перед добавлением последнего 129-го бита он дополняется единичным битом, за которым следуют нулевые. Затем Poly1305 вычисляет многочлен:

Результат этого выражения - целое число длиной не более 129 битов. Когда к нему прибавляется 128-битное значение AES(K_2,N), результат приводится по модулю 2^128 и образует 128-битный MAC.

Примечание. Я описал конструкцию Вегмана - Картера как использующую PRF, однако AES - не PRF, а псевдослучайная перестановка (pseudorandom permutation, PRP). Но это несущественно, поскольку конструкция Вегмана - Картера хорошо работает и с PRP, и с PRF. Если дана функция, являющаяся либо PRF, либо PRP, по одним ее выходным значениям трудно определить, к какому типу она относится. Иными словами, отличить PRP от PRF вычислительно трудно.

Анализ безопасности Poly1305-AES, см. статью «The Poly1305-AES Message-Authentication Code», показывает, что Poly1305-AES обеспечивает 128-битную безопасность, пока AES остается безопасным блочным шифром и все реализовано правильно, как и должно быть для любого криптографического алгоритма.

Универсальный хеш Poly1305 можно объединять не только с AES. Например, Poly1305 применялся с потоковым шифром ChaCha, см. RFC 7539 «ChaCha20 and Poly1305 for IETF Protocols». Нет сомнений, что Poly1305 продолжат использовать везде, где требуется быстрый MAC.

Хотя Poly1305 быстр и безопасен, у него есть несколько недостатков. Во-первых, вычисление многочлена трудно реализовать эффективно, особенно тем, кто не знаком с соответствующими математическими понятиями; примеры см. на https://github.com/floodyberry/poly1305-donna. Во-вторых, сам по себе он безопасен лишь для одного сообщения, если не используется конструкция Вегмана - Картера. Но в таком случае ему нужен одноразовый номер, и при его повторении алгоритм становится небезопасным. Наконец, Poly1305 оптимизирован для длинных сообщений, но избыточен при обработке только коротких, например короче 128 байтов. В таких случаях хорошим решением является SipHash.

Я разработал SipHash в 2012 году вместе с Дэном Бернстайном, первоначально для решения некриптографической проблемы: атак отказа в обслуживании на хеш-таблицы. Хеш-таблицы - это структуры данных, широко применяемые, в частности, в языках программирования для эффективного внутреннего хранения элементов. До SipHash хеш-таблицы использовали некриптографические хеш-функции с ключом, коллизии для которых часто было легко найти; это позволяло замедлять систему и проводить атаки отказа в обслуживании. Мы заметили, что PRF решит эту проблему, и приступили к разработке SipHash - PRF, подходящей для хеш-таблиц. Поскольку хеш-таблицы в основном обрабатывают короткие входные данные, SipHash оптимизирована для коротких сообщений. SipHash - полноценная PRF и MAC, особенно эффективная там, где большинство входных данных короткие.

SipHash использует прием, делающий ее безопаснее базовых губчатых функций: вместо однократного XOR блока сообщения с состоянием перед перестановкой SipHash выполняет XOR до и после перестановки, как показано на рисунке 7-5. 128-битный ключ SipHash рассматривается как два 64-битных слова K_1 и K_2, складываемых посредством XOR с фиксированным 256-битным начальным состоянием, которое рассматривается как четыре 64-битных слова. После этого ключи отбрасываются, и вычисление SipHash сводится к итеративному применению основной функции SipRound и XOR фрагментов сообщения для изменения внутреннего состояния из четырех слов. Наконец, SipHash возвращает 64-битный тег, складывая посредством XOR четыре слова состояния.

Рисунок 7-5. Обработка 15-байтового сообщения функцией SipHash-2-4: блок M_1 из 8 байтов, блок M_2 из 7 байтов и 1 байт дополнения

Функция SipRound использует множество XOR вместе со сложениями и циклическими сдвигами слов для обеспечения безопасности. SipRound преобразует состояние из четырех 64-битных слов (a,b,c,d), выполняя следующие операции сверху вниз. Операции слева и справа независимы и могут выполняться параллельно:

Здесь a += b - сокращенная запись a = a + b, а b <<<= 13 - сокращенная запись b = b <<< 13, то есть 64-битное слово b циклически сдвигается на 13 битов влево.

Эти простые операции над 64-битными словами - почти все, что нужно реализовать для вычисления SipHash, хотя самостоятельно реализовывать ее не придется. Готовые реализации доступны для большинства языков, включая C, Go, Java, JavaScript, Python и Rust.

Примечание. Обозначение SipHash-x-y означает версию SipHash, выполняющую x раундов SipRound между каждым вводом блока сообщения, а затем y раундов. Большее число раундов требует больше операций и замедляет работу, но повышает безопасность. Версия по умолчанию - SipHash-2-4, обычно обозначаемая просто SipHash; пока она успешно противостоит криптоанализу. Я также определил SipHash128 - версию SipHash со 128-битными тегами.

Многие системы, в том числе язык Rust, операционная система OpenBSD и блокчейн Bitcoin, используют SipHash внутри. Ядро Linux тоже использует SipHash, а также HalfSipHash, «небезопасного младшего родственника SipHash», - уменьшенную версию с 64-битным ключом и 32-битным выходом; см. https://docs.kernel.org/security/siphash.html.

Подобно шифрам и хеш-функциям без ключа, MAC и PRF, безопасные на бумаге, могут оказаться уязвимыми к атакам в реальной среде. Рассмотрим два примера.

Атаки по побочным каналам направлены не на сам криптографический алгоритм, а на его реализацию. В частности, атаки по времени используют длительность выполнения алгоритма для определения секретных данных: ключей, открытого текста и секретных случайных значений. Сравнение строк за переменное время создает уязвимости не только при проверке MAC, но и во множестве других криптографических функций и средств безопасности.

MAC могут быть уязвимы к атакам по времени, если удаленная система проверяет теги за время, зависящее от значения тега. Это позволяет атакующему определить правильный тег сообщения, испытывая множество неправильных и выявляя тот, проверка которого занимает больше всего времени. Проблема возникает, когда сервер сравнивает правильный тег с неправильным, последовательно сопоставляя две строки байт за байтом до первого различия. Например, код Python в листинге 7-1 сравнивает две строки байт за байтом за переменное время: если первые байты различаются, функция возвращает результат после одного сравнения; если строки x и y совпадают, функция выполняет n сравнений по длине строк.

Листинг 7-1. Сравнение двух n-байтовых строк за переменное время

Чтобы продемонстрировать уязвимость функции compare_mac(), напишем программу, измеряющую время 100 000 вызовов compare_mac(): сначала для одинаковых 16-символьных значений x и y, а затем для значений, различающихся третьим байтом. Второе сравнение должно занимать заметно меньше времени, поскольку compare_mac() сравнивает меньше байтов, чем при одинаковых x и y, как показано в листинге 7-2.

Листинг 7-2. Измерение различий во времени выполнения compare_mac() из листинга 7-1

На MacBook Pro с процессором ARM M1 один запуск программы из листинга 7-2 выводит время выполнения около 67 и 26 миллисекунд соответственно. Разница достаточно велика, чтобы понять, что происходит внутри алгоритма. Перемещая различающийся байт в другие позиции строки, можно наблюдать разное время выполнения для разных смещений. Если MAC1 - правильный тег MAC, а MAC2 - тег, испытываемый атакующим, легко определить положение первого различия, то есть число правильно угаданных байтов.

Если время выполнения не зависит от секретного значения, атака по времени не сработает. Поэтому разработчики стремятся создавать реализации с постоянным временем - код, выполняющийся строго за одно и то же время при любом значении секретных входных данных. Например, функция C в листинге 7-3 сравнивает два буфера длиной size байтов за постоянное время: временная переменная result отлична от нуля тогда и только тогда, когда два буфера где-либо различаются.

Листинг 7-3. Сравнение двух буферов за постоянное время для более безопасной проверки MAC

Алгоритмы на основе перестановок, такие как SHA-3 и SipHash, просты, легко реализуются и имеют компактные реализации, но уязвимы перед атаками по побочным каналам, восстанавливающими снимок состояния системы. Например, если процесс способен в любой момент прочитать значения оперативной памяти и регистров либо дамп памяти процесса, атакующий может определить внутреннее состояние SHA-3 в режиме MAC или внутреннее состояние SipHash, а затем выполнить обратную перестановку и восстановить исходное секретное состояние. После этого он сможет подделывать теги любых сообщений, нарушив безопасность MAC.

К счастью, такая атака не работает против MAC на основе функций сжатия, таких как HMAC-SHA-256 и BLAKE2 с ключом, поскольку атакующему требуется снимок памяти в точный момент использования ключа. Следовательно, если в среде возможна утечка частей памяти процесса, можно использовать MAC на основе необратимого преобразования функции сжатия, а не перестановки.

Почтенный HMAC заслуживает большего внимания, чем позволяет объем этой главы, особенно цепочка идей, приведшая к его широкому распространению и последующему краху при объединении со слабой хеш-функцией. Рекомендую статью Михира Белларе, Рана Канетти и Хьюго Кравчика 1996 года «Keying Hash Functions for Message Authentication», в которой были представлены HMAC и родственная конструкция NMAC, а также последующую статью Белларе 2006 года «New Proofs for NMAC and HMAC: Security Without Collision-Resistance». В ней доказано, что HMAC не требуется устойчивый к коллизиям хеш: достаточно хеша с функцией сжатия, являющейся PRF. Что касается атак, в статье Пьера-Алена Фука, Гаэтана Лерена и Фонга Нгуена 2007 года «Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5» показано, как атаковать HMAC и NMAC, построенные поверх хрупкой хеш-функции, такой как MD4 или MD5. HMAC-MD5 и HMAC-SHA-1 не полностью взломаны, но риск достаточно высок.

На рисунке 8-1 показаны три способа объединить MAC и шифры для одновременного шифрования и аутентификации открытого текста: «шифрование и MAC», «MAC, затем шифрование» и «шифрование, затем MAC».

Рисунок 8-1. Комбинации шифра и MAC

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

В композиции «шифрование и MAC» открытый текст шифруется, а тег аутентификации формируется непосредственно из открытого текста. Две операции - шифрование и аутентификация - независимы и потому могут выполняться параллельно. В схеме «MAC, затем шифрование» сначала из открытого текста создается тег, а затем открытый текст и MAC шифруются вместе. В методе «шифрование, затем MAC» сначала шифруется открытый текст, а потом из шифртекста формируется тег. Посмотрим, какой метод, вероятнее всего, безопаснее.

При подходе «шифрование и MAC» шифртекст и тег MAC вычисляются отдельно. Для открытого текста P отправитель вычисляет шифртекст C=E(K_1,P), где E - алгоритм шифрования, а C - получившийся шифртекст. Тег аутентификации T вычисляется из открытого текста как T=MAC(K_2,P). Две операции независимы и потому могут выполняться параллельно.

Сформировав шифртекст и тег аутентификации, отправитель передает оба предполагаемому получателю. Получив C и T, получатель расшифровывает C и получает открытый текст P, вычисляя P=D(K_1,C). Затем он вычисляет MAC(K_2,P) по расшифрованному открытому тексту и сравнивает результат с полученным T. Если C или T повреждены, проверка завершается неудачей и сообщение считается недействительным.

Теоретически «шифрование и MAC» - наименее безопасная композиция MAC и шифра, поскольку даже безопасный MAC может раскрывать сведения о P, облегчая его восстановление. Цель применения MAC состоит лишь в том, чтобы теги нельзя было подделать; теги не обязаны выглядеть случайными. Поэтому тег аутентификации T открытого текста P может раскрывать информацию, хотя MAC считается безопасным. Если MAC является псевдослучайной функцией, тег ничего не раскроет о P.

Несмотря на относительную слабость, многие системы продолжают поддерживать «шифрование и MAC», включая протокол защищенного транспортного уровня SSH. В нем за каждым зашифрованным пакетом C следует тег T=MAC(K,N || P), где N - 32-битный порядковый номер, увеличиваемый для каждого пакета. На практике «шифрование и MAC» оказалось достаточно надежным для SSH благодаря сильным алгоритмам MAC, таким как HMAC-SHA-256, которые не раскрывают сведений о P. Введите следующую команду, чтобы увидеть список MAC, поддерживаемых OpenSSH:

Композиция «MAC, затем шифрование» защищает сообщение P, сначала вычисляя тег аутентификации T=MAC(K_2,P). Затем она создает шифртекст, совместно шифруя открытый текст и тег: C=E(K_1,P || T).

После этих действий отправитель передает только C, содержащий и зашифрованный открытый текст, и тег. Получатель расшифровывает C, вычисляя P || T=D(K_1,C), и получает открытый текст и тег T. Затем он проверяет полученный тег T, непосредственно вычисляя MAC(K_2,P) по открытому тексту и подтверждая равенство результата тегу T.

Как и при «шифровании и MAC», при использовании «MAC, затем шифрование» получатель должен расшифровать C, прежде чем сможет определить, поврежден ли пакет. В результате потенциально поврежденный открытый текст попадает к получателю. Тем не менее «MAC, затем шифрование» безопаснее «шифрования и MAC», поскольку скрывает тег аутентификации открытого текста и тем самым не позволяет тегу раскрывать сведения об открытом тексте.

Протокол TLS много лет использовал «MAC, затем шифрование», но в TLS 1.3 эту композицию заменили аутентифицированными шифрами; подробнее о TLS 1.3 см. в главе 13.

Композиция «шифрование, затем MAC» отправляет получателю два значения: шифртекст C=E(K_1,P) и основанный на нем тег T=MAC(K_2,C). Получатель вычисляет MAC(K_2,C) и проверяет равенство полученному T. Если значения равны, открытый текст вычисляется как P=D(K_1,C); если нет, шифртекст отбрасывается.

Преимущество этого метода в том, что для обнаружения поврежденных сообщений получателю достаточно вычислить MAC, а расшифровывать поврежденный шифртекст не нужно. Кроме того, атакующий не может отправлять получателю пары C и T для расшифрования, не взломав MAC, поэтому передать получателю вредоносные данные становится труднее.

Благодаря сочетанию этих свойств «шифрование, затем MAC» сильнее подходов «шифрование и MAC» и «MAC, затем шифрование». Это одна из причин, по которым широко используемый набор протоколов защищенной связи IPsec применяет его для защиты пакетов, например внутри VPN-туннелей.

Обратите внимание, что SSH и TLS не используют «шифрование, затем MAC», поскольку на момент их создания другие подходы казались достаточными, а не потому, что теоретических слабостей не существовало. Нежелательные свойства не обязательно превращаются в реальные уязвимости.

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

С начала 2000-х годов исследователи пытаются определить, каким должен быть хороший аутентифицированный шифр, но однозначного ответа до сих пор нет. Из-за множества входных данных AEAD, играющих разные роли, понятие безопасности определить труднее, чем для обычных шифров, которые лишь шифруют сообщение. Например, в исследовательской статье «Nonces Are Noticed: AEAD Revisited» предложена теоретическая основа шифрования с одноразовыми номерами. Тем не менее в этом разделе я обобщу важнейшие критерии оценки безопасности, производительности и функциональности аутентифицированного шифра.

AES-GCM - самый широко применяемый аутентифицированный шифр. Он основан на алгоритме AES, а режим работы счетчика Галуа (Galois counter mode, GCM) по существу представляет собой модификацию CTR с небольшим эффективным компонентом для вычисления тега аутентификации. На момент написания книги AES-GCM является стандартом NIST SP 800-38D, входит в Suite B АНБ и признан IETF для протоколов защищенной сети IPsec, SSH и TLS 1.2 и 1.3.

Примечание. Хотя GCM работает с любым блочным шифром, почти наверняка вы встретите его только с AES.

На рисунке 8-2 показана работа AES-GCM: экземпляры AES, параметризованные секретным ключом K, преобразуют блок, состоящий из одноразового номера N, сцепленного со счетчиком, который начинается здесь с 1, а затем увеличивается до 2, 3 и так далее. После этого результат складывается посредством XOR с блоком открытого текста и дает блок шифртекста. Пока ничего нового по сравнению с режимом CTR.

Рисунок 8-2. Режим AES-GCM, примененный к одному блоку связанных данных A_1 и двум блокам открытого текста P_1 и P_2. Обведенный знак умножения означает умножение многочлена на H - ключ аутентификации, полученный из K

Затем блоки шифртекста смешиваются сочетанием XOR и умножений, как будет показано далее. AES-GCM можно рассматривать как выполнение 1) шифрования в режиме CTR и 2) MAC над блоками шифртекста. Поэтому AES-GCM по существу представляет собой конструкцию «шифрование, затем MAC», где AES-CTR шифрует со 128-битным ключом K и 96-битным одноразовым номером N.

Для аутентификации шифртекста GCM использует MAC Вегмана - Картера, см. главу 7, который складывает посредством XOR значение AES(K,N || 0) с выходом универсальной хеш-функции GHASH. На рисунке 8-2 GHASH соответствует последовательности операций «x H», за которыми следует XOR с len(A) || len(C), то есть битовой длиной A, связанных данных, сцепленной с битовой длиной C, шифртекста.

Таким образом, значение тега аутентификации выражается как

где H - ключ хеширования, или ключ аутентификации. Он определяется как H=AES(K,0), то есть шифрование блока, равного последовательности нулевых байтов. Для ясности этот шаг не показан на рисунке 8-2.

Примечание. В GCM функция GHASH не использует K напрямую, чтобы при компрометации ключа GHASH мастер-ключ K оставался секретным. Зная K, можно получить H, вычислив AES(K,0), но восстановить K из этого значения невозможно, поскольку здесь K служит ключом AES.

GHASH использует многочленную запись для умножения каждого блока шифртекста на ключ аутентификации H. Благодаря такому умножению GHASH быстро работает в аппаратуре и программах с помощью специальной инструкции умножения многочленов, имеющейся во многих распространенных микропроцессорах: CLMUL, carry-less multiplication, умножение без переносов.

Увы, GHASH далека от идеала. Во-первых, ее скорость неоптимальна. Даже с инструкцией CLMUL слой AES-CTR, шифрующий открытый текст, остается быстрее MAC GHASH. Во-вторых, GHASH трудно правильно реализовать. Даже опытные разработчики OpenSSL - безусловно, самого широко применяемого криптографического программного обеспечения в мире - допустили ошибку в GHASH AES-GCM. В одном коммите функция gcm_ghash_clmul содержала ошибку, позволявшую атакующим подделывать действительные MAC для AES-GCM. К счастью, инженеры Intel заметили ошибку до того, как она попала в следующий выпуск OpenSSL.

УМНОЖЕНИЕ МНОГОЧЛЕНОВ

Хотя оно сложнее классической целочисленной арифметики, для компьютеров умножение многочленов проще, поскольку в нем нет переносов. В частности, можно вычислять модульное умножение многочленов в структуре, определенной заданным многочленом; такие структуры называются фактор-кольцами. Предположим, требуется вычислить произведение многочленов (1+X+X^2) и (1+X^2) по модулю (1+X+X^3). Сначала два многочлена перемножаются как обычно, что дает следующее выражение. Два члена X^2 взаимно уничтожаются, поскольку мы работаем с булевыми многочленами, в мире которых 1+1=0:

Выполняется приведение по модулю: 1+X+X^3+X^4 по модулю 1+X+X^3 дает X+X^2, поскольку

В общем виде A+BC по модулю B по определению равно A.

Главная слабость AES-GCM - хрупкость при повторении одноразового номера. Если два разных сообщения зашифровать с одним одноразовым номером N, атакующий, наблюдающий два шифртекста, сможет определить XOR соответствующих открытых текстов. Кроме того, он сможет восстановить ключ аутентификации H и использовать его для подделки тегов любого шифртекста, связанных данных или их комбинации.

Эта хрупкость становится понятнее при рассмотрении базовой алгебры вычислений AES-GCM, показанных на рисунке 8-2. Тег T вычисляется как T=GHASH(H,A,C) xor AES(K,N || 0), где GHASH - универсальная хеш-функция с линейно связанными входами и выходами.

Если вычислить два тега T_1 и T_2 с одним одноразовым номером N, часть AES исчезнет. Пусть

Их XOR равен

Таким образом, при двукратном использовании одного одноразового номера атакующий может восстановить GHASH(H,A_1,C_1) xor GHASH(H,A_2,C_2) для известных A_1, C_1, A_2 и C_2. Линейность GHASH затем позволяет восстановить H.

В 2016 году исследователи просканировали интернет в поисках экземпляров AES-GCM, доступных через HTTPS-серверы, чтобы найти системы с повторяющимися одноразовыми номерами; см. исследовательскую статью. Они обнаружили 184 сервера с повторяющимися номерами, в том числе 23 сервера, всегда использовавших нулевую строку в качестве одноразового номера.

Преимущество режима GCM в том, что при шифровании и расшифровании блоки обрабатываются независимо, что позволяет распараллелить вычисления. Однако вычисление GMAC не распараллеливается, поскольку после обработки GHASH всех связанных данных оно должно выполняться от начала до конца шифртекста. Из-за отсутствия распараллеливания любая система, которая сначала получает открытый текст, а затем связанные данные, должна дождаться чтения и хеширования всех связанных данных, прежде чем хешировать первый блок шифртекста.

Однако GCM поддерживает потоковую обработку: поскольку вычисления двух его слоев можно организовать конвейером, хранить все блоки шифртекста перед вычислением GHASH не требуется - GHASH обрабатывает каждый блок по мере его шифрования. Иными словами, P_1 шифруется в C_1, затем GHASH обрабатывает C_1, пока P_2 шифруется в C_2, после чего P_1 и C_1 больше не нужны, и так далее.

Offset codebook (OCB), впервые разработанный в 2001 году, появился раньше GCM и, как GCM, создает аутентифицированный шифр из блочного, но делает это быстрее и проще. OCB пока не получил более широкого распространения, поскольку до 2021 года его использование было запатентовано и требовало лицензии изобретателя. Теперь любой может свободно применять OCB в любых приложениях.

В отличие от GCM, OCB объединяет шифрование и аутентификацию в одном слое обработки с одним ключом. Отдельного слоя аутентификации нет, поэтому OCB обеспечивает аутентификацию почти бесплатно и выполняет почти столько же вызовов блочного шифра, сколько выполнял бы неаутентифицированный шифр. OCB почти так же прост, как режим ECB, см. главу 4, но намного безопаснее.

На рисунке 8-3 показана работа OCB: каждый блок открытого текста P шифруется в блок шифртекста C=E(K,P xor O) xor O, где E - функция шифрования блочного шифра. Здесь O, смещение, - значение, зависящее от ключа и одноразового номера и изменяемое для каждого нового обрабатываемого блока.

Рисунок 8-3. Процесс шифрования OCB для двух блоков открытого текста без связанных данных

Чтобы сформировать тег аутентификации, OCB сначала складывает блоки открытого текста посредством XOR и вычисляет S=P_1 xor P_2 xor P_3 xor .... Затем тег вычисляется как T=E(K,S xor O^*), где O^* - значение смещения, вычисленное из смещения последнего обработанного блока открытого текста.

Подобно AES-GCM, OCB поддерживает связанные данные в виде последовательности блоков A_1, A_2 и так далее. Если зашифрованное OCB сообщение содержит связанные данные, тег аутентификации вычисляется по формуле

где OCB определяет смещения, отличные от используемых для шифрования P.

В отличие от GCM и «шифрования, затем MAC», где для формирования тега объединяются блоки шифртекста, OCB вычисляет тег аутентификации, объединяя данные открытого текста. В этом нет ничего плохого, а безопасность OCB подтверждается строгими доказательствами.

Примечание. Подробнее о реализации OCB см. RFC 7253 или статью Теда Кровеца и Филлипа Рогавея 2011 года «The Software Performance of Authenticated-Encryption Modes», посвященную новейшей и лучшей версии OCB - OCB3. Дополнительные сведения об OCB см. в FAQ.

OCB немного менее хрупок при повторении одноразовых номеров, чем GCM. Если использовать одноразовый номер дважды, атакующий, видящий два шифртекста, может заметить, например, что третий блок открытого текста первого сообщения совпадает с третьим блоком второго. При использовании GCM атакующие способны обнаруживать не только совпадения, но и XOR-разности блоков в одинаковых позициях. Поэтому последствия повторения одноразовых номеров для GCM хуже, чем для OCB.

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

В 2023 году криптографы обнаружили, что применение OCB3 с очень короткими одноразовыми номерами длиной 6 битов значительно снижает его безопасность; см. статью. Обратите внимание, что версия OCB2 была взломана, как описано в этой статье.

OCB и GCM примерно одинаково эффективны. Подобно GCM, OCB распараллеливается и поддерживает потоковую обработку. По чистой эффективности GCM и OCB выполняют примерно одинаковое число вызовов лежащего в основе блочного шифра, обычно AES, но OCB немного быстрее GCM, поскольку просто складывает открытый текст посредством XOR вместо сравнительно дорогостоящего вычисления вроде GHASH. В предыдущих поколениях микропроцессоров Intel AES-GCM был более чем в три раза медленнее AES-OCB, потому что инструкции AES и GHASH конкурировали за ресурсы CPU и не могли выполняться параллельно.

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

Synthetic IV (SIV) - режим аутентифицированного шифра, обычно используемый с AES. В отличие от GCM и OCB, SIV безопасен даже при двукратном использовании одного одноразового номера: атакующий, получивший два шифртекста, зашифрованных с одинаковым номером, сможет узнать лишь то, был ли один открытый текст зашифрован дважды. В отличие от GCM или OCB, он не сможет определить, совпадает ли первый блок двух сообщений, поскольку одноразовый номер, используемый для шифрования, сначала вычисляется как комбинация заданного номера и открытого текста.

Теперь рассмотрим совершенно другой подход к построению аутентифицированного шифра: вместо режима работы вокруг блочного шифра вроде AES возьмем шифр, строящий режим вокруг перестановки. Перестановка просто и обратимо преобразует входные данные в выходные того же размера без ключа - трудно представить более простой компонент. Еще лучше то, что получившийся AEAD быстр, имеет доказанную безопасность и устойчивее к повторному использованию одноразовых номеров, чем GCM и OCB.

На рисунке 8-4 показана работа AEAD на основе перестановки: начиная с фиксированного начального состояния H_0, вы складываете с внутренним состоянием посредством XOR ключ K, а затем одноразовый номер N, получая новое внутреннее состояние того же размера, что исходное. Затем новое состояние преобразуется перестановкой P, дающей следующее значение состояния. Теперь первый блок открытого текста P_1 складывается посредством XOR с состоянием, а получившееся значение принимается как первый блок шифртекста C_1; P_1 и C_1 имеют один размер, но короче состояния.

Рисунок 8-4. Аутентифицированный шифр на основе перестановки

Для шифрования второго блока состояние преобразуется посредством P, следующий блок открытого текста P_2 складывается посредством XOR с текущим состоянием, а получившееся значение принимается как C_2. Затем процесс повторяется для всех блоков открытого текста, а после последнего вызова P биты внутреннего состояния берутся как тег аутентификации T, что показано в правой части рисунка 8-4.

Примечание. Режим на рисунке 8-4 можно адаптировать для поддержки связанных данных, но процесс немного сложнее, поэтому я опущу его описание.

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

Кроме того, блоки нужно правильно дополнять дополнительными битами так, чтобы любые два разных сообщения давали разные результаты. В качестве контрпримера: если последний блок открытого текста короче полного, нельзя просто дополнять его нулями. Иначе блок открытого текста, например, из 2 байтов 0000 превратится в полный блок 0000...0000, как и блок из 3 байтов 000000. В результате оба сообщения получат один тег, хотя различаются размером.

Если повторно использовать одноразовый номер в таком шифре на основе перестановки, последствия не столь тяжелы, как в GCM или OCB: стойкость тега аутентификации не нарушается. При повторении одноразового номера атакующий узнает только то, начинаются ли два зашифрованных сообщения с одного значения, и длину этого общего значения, или префикса. Например, при шифровании двух шестиблочных сообщений ABCXYZ и ABCDYZ, где каждая буква обозначает блок, с одним одноразовым номером могут получиться два шифртекста JKLTUV и JKLMNO с одинаковыми префиксами. Но атакующий не сможет узнать, что у двух открытых текстов совпадали последние два блока YZ.

С точки зрения производительности шифры на основе перестановок обладают преимуществами одного слоя операций, потоковой обработки и одного основного алгоритма для шифрования и расшифрования. Однако они не распараллеливаются подобно GCM или OCB, поскольку каждый новый вызов P должен ждать завершения предыдущего.

Примечание. Если вам захочется взять любимую перестановку и изобрести собственный аутентифицированный шифр, пожалуйста, не делайте этого. Вы, скорее всего, ошибетесь в деталях и получите небезопасный шифр. Прочитайте спецификации, написанные опытными криптографами, для таких алгоритмов, как Keyak, производный от Keccak, конструкция Duplex и deck-функции на https://keccak.team. Вы увидите, что шифры на основе перестановок сложнее, чем кажутся на первый взгляд.

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

Требований много, и даже у AES-GCM есть несколько недостатков.

Одна из слабостей AES-GCM находится в алгоритме аутентификации GHASH: некоторые значения ключа хеширования H значительно упрощают атаки на механизм аутентификации GCM. В частности, если H принадлежит некоторым строго определенным математическим подгруппам всех 128-битных строк, атакующие могут угадать действительный тег аутентификации некоторого сообщения, просто переставляя блоки предыдущего сообщения.

Чтобы понять эту слабость, рассмотрим работу GHASH.

Как показано на рисунке 8-2, GHASH начинает со 128-битного значения H, первоначально равного AES(K,0), а затем многократно вычисляет

начиная с X_0=0 и обрабатывая блоки шифртекста C_1, C_2 и так далее. GHASH возвращает итоговое X_i для вычисления окончательного тега.

Для простоты предположим, что все значения C_i равны 1, так что для любого i

Теперь вычисление X_1 по первому уравнению дает

где X_0 заменено на 0, а C_1 - на 1, так что

Благодаря дистрибутивности x относительно xor подставим вместо X_1 значение H, вместо C_2 - 1 и вычислим следующее значение X_2:

где H^2 - квадрат H, то есть H x H.

Теперь выведем X_3, подставив выражение для X_2:

Далее получаем X_4=H^4 xor H^3 xor H^2 xor H и так далее, а итоговое X_i в конце равно

Напомним, что все блоки C_i были положены равными 1. Если же они произвольны, получится

Затем GHASH складывает с последним X_n посредством XOR длину сообщения, умножает результат на H и складывает полученное значение посредством XOR с AES(K,N || 0), создавая окончательный тег аутентификации T.

Что теперь может пойти не так? Начнем с простейших случаев:

• Если H=0, то X_n=0 независимо от значений C_i, а значит, и от сообщения. Иными словами, при H=0 у всех сообщений будет один тег аутентификации.

• Если H=1, тег представляет собой просто XOR блоков шифртекста, и их перестановка даст тот же тег аутентификации.

Поскольку 0 и 1 - лишь два из 2^128 возможных значений H, вероятность их появления равна всего 2/2^128=1/2^127. Но существуют и другие слабые значения: все значения H, принадлежащие короткому циклу при возведении в степень i. Например, значение H 10d04d25f93556e69f58ce2f8d035a4 принадлежит циклу длиной 5, поскольку удовлетворяет H^5=H, а следовательно, H^e=H для любого e, кратного 5. Именно так определяется цикл относительно пятых степеней. Поэтому в приведенном выше выражении окончательного значения GHASH X_n перестановка блока C_n, умножаемого на H, и блока C_(n-4), умножаемого на H^5, не изменяет тег аутентификации, что равносильно подделке. Атакующий может использовать это свойство для создания нового сообщения и действительного тега к нему без знания ключа, что для безопасного аутентифицированного шифра должно быть невозможно.

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

Примечание. Подробнее об этой атаке см. статью Маркку-Юхани О. Сааринена «Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes».

На практике AES-GCM обычно возвращает 128-битные теги, но способен формировать теги любой длины. К сожалению, при использовании более коротких тегов вероятность подделки значительно возрастает.

При 128-битном теге атакующий, пытающийся выполнить подделку, должен добиться успеха с вероятностью 1/2^128, поскольку существует 2^128 возможных 128-битных тегов. В общем случае для n-битного тега вероятность успеха должна быть равна 1/2^n, где 2^n - число возможных значений n-битного тега. Но при более коротких тегах из-за выходящих за рамки этого обсуждения слабостей структуры GCM вероятность подделки намного выше 1/2^n. Например, при 32-битном теге атакующий, знающий тег аутентификации некоторого сообщения размером 2 Мбайт, добьется успеха с вероятностью 1/2^16 вместо 1/2^32.

В общем случае для n-битных тегов вероятность подделки равна не 1/2^n, а 2^m/2^n, где 2^m - число блоков самого длинного сообщения, тег которого наблюдал успешный атакующий. Например, при 48-битных тегах и сообщениях объемом 4 Гбайт, то есть 2^28 блоков по 16 байтов, вероятность подделки равна 2^28/2^48=1/2^20, или примерно одному шансу на миллион. Для криптографии это сравнительно высокая вероятность. Подробнее об атаке см. статью Нильса Фергюсона 2005 года «Authentication Weaknesses in GCM».

Чтобы больше узнать об аутентифицированных шифрах, посетите главную страницу CAESAR - Competition for Authenticated Encryption: Security, Applicability, and Robustness по адресу http://competitions.cr.yp.to/caesar.html. Конкурс CAESAR начался в 2012 году по образцу конкурсов AES и SHA-3, хотя организован не NIST.

Вычислительная задача - вопрос, на который можно ответить, выполнив достаточный объем вычислений, например: «Является ли 217 простым числом?» или «Сколько букв i в слове incomprehensibilities?» Первый вопрос является задачей разрешимости, поскольку на него можно ответить «да» или «нет», а второй - задачей поиска.

Вычислительная трудность - свойство вычислительных задач, для которых не существует алгоритма, выполняющегося за разумное время. Такие задачи также называются практически неразрешимыми. Вычислительная трудность не зависит от вида вычислительного устройства: центрального процессора общего назначения (CPU), графического процессора (GPU), интегральной схемы или механической машины Тьюринга. Одно из первых открытий теории вычислительной сложности состоит в эквивалентности всех моделей вычислений. Если одно вычислительное устройство способно эффективно решить задачу, любое другое также сможет сделать это после переноса алгоритма на его язык. Исключение составляют квантовые компьютеры, которые мы обсудим в главе 14. Поэтому при обсуждении вычислительной трудности не требуется указывать конкретное вычислительное устройство или аппаратуру: речь будет идти просто об алгоритмах.

Чтобы оценивать вычислительную трудность, сначала нужен способ измерить сложность алгоритма, то есть время его выполнения. Затем времена выполнения делятся на трудные и легкие.

Вычислительная сложность алгоритма - приблизительное число выполняемых им операций как функция размера входных данных. Размер можно считать в битах или в числе входных элементов. Например, рассмотрим записанный псевдокодом алгоритм из листинга 9-1. Он ищет значение x в массиве из n элементов и возвращает его индекс либо -1, если x не найден.

Листинг 9-1. Простой алгоритм поиска, сложность которого линейна относительно длины массива n

Этот алгоритм использует цикл for для поиска заданного значения x в массиве, перебирая значения переменной i начиная с 0. Он проверяет, равно ли значение в позиции i массива значению x. Если равно, возвращается позиция i. В противном случае i увеличивается и проверяется следующая позиция, пока алгоритм не достигнет n-1, последней позиции массива, после чего возвращается -1.

Для такого алгоритма сложность считается как число итераций цикла for: 1 в лучшем случае, если x равно array[0]; n в худшем, если x равно array[n-1] или отсутствует в array; и в среднем n/2, если x равномерно случайно распределен по одной из n ячеек массива. Для массива в 10 раз большего размера алгоритм будет в 10 раз медленнее. Поэтому сложность пропорциональна n, или «линейна» по n. Сложность, линейная относительно размера входных данных, считается быстрой, в отличие от экспоненциальной. Хотя обработка больших входных данных в этом примере медленнее, вычислительная стоимость не растет экспоненциально, а остается пропорциональной размеру таблицы.

Однако многие полезные алгоритмы медленнее и имеют сложность выше линейной. Классический пример - алгоритмы сортировки: чтобы упорядочить список из n значений в случайном порядке, в худшем случае требуется n*log n базовых операций. Иногда это называется линейно-логарифмической сложностью. Поскольку n*log n растет быстрее n, скорость сортировки с ростом n снижается быстрее, чем пропорционально. И все же такие алгоритмы сортировки остаются в области практических вычислений, которые можно выполнить за разумное время.

Обычно неразумны сложности, экспоненциально зависящие от размера входных данных. В какой-то момент предел осуществимого будет достигнут даже при сравнительно коротких входах. Рассмотрим простейший пример из криптоанализа - полный перебор секретного ключа. Напомним из главы 1, что для открытого текста P и шифртекста C=E(K,P) восстановление n-битного симметричного ключа требует не более 2^n попыток, поскольку существует 2^n возможных ключей. Это пример экспоненциально растущей сложности. Задачу с экспоненциальной сложностью практически невозможно решить, потому что с ростом n требуемые усилия быстро становятся неосуществимыми.

Можно возразить, что мы сравниваем несопоставимое: в функции search() из листинга 9-1 считалось число операций if (array[i] == x), а при восстановлении ключа - число шифрований, каждое из которых в тысячи раз медленнее одного сравнения ==. Эта кажущаяся непоследовательность может иметь значение при сравнении двух алгоритмов с очень близкими сложностями, но обычно несущественна, поскольку число операций влияет сильнее стоимости отдельной операции. Кроме того, при оценке сложности игнорируют постоянные множители: когда говорят, что алгоритм требует порядка n^3 операций, то есть имеет кубическую сложность, на самом деле он может выполнять 41* n^3 или даже 12 345* n^3 операций. Но с ростом n постоянные множители теряют значение настолько, что ими можно пренебречь. Анализ сложности посвящен теоретической трудности как функции размера входных данных; точное число тактов CPU на вашем компьютере его не интересует.

Для выражения сложности часто применяется нотация O(), «большое O». Например, O(n^3) означает, что сложность растет не быстрее n^3, если не учитывать возможные постоянные множители. O() обозначает верхнюю границу сложности алгоритма. Запись O(1) означает, что алгоритм выполняется за постоянное время, то есть его время работы не зависит от длины входа. Например, алгоритм, определяющий четность целого числа по его младшему значащему биту (least significant bit, LSB) и возвращающий «четное», если он равен нулю, и «нечетное» в противном случае, выполняет одну и ту же работу с одной стоимостью независимо от длины целого числа.

Чтобы увидеть разницу между линейной, квадратичной и экспоненциальной временной сложностью, посмотрим на рост O(n), линейной, O(n^2), квадратичной, и O(2^n), экспоненциальной, на рисунке 9-1.

Рисунок 9-1. Рост экспоненциальной, квадратичной и линейной сложности - от самой быстрорастущей до самой медленнорастущей

Экспоненциальная сложность означает, что задачу практически невозможно решить, а линейная - что решение осуществимо; квадратичная сложность находится где-то между ними.

Квадратичная сложность O(n^2), средняя кривая на рисунке 9-1, - частный случай более широкого класса полиномиальных сложностей O(n^k), где k - некоторое фиксированное число, например 3, 2,373, 7/10 или квадратный корень из 17. Алгоритмы полиномиального времени исключительно важны в теории сложности и криптографии, поскольку именно они определяют практическую осуществимость. Если алгоритм работает за полиномиальное время, сокращенно polytime, он завершается за приемлемое время даже при больших входных данных. Поэтому для теоретиков сложности и криптографов полиномиальное время является синонимом эффективности.

Напротив, алгоритмы сверхполиномиального времени, то есть O(f(n)), где f(n) растет быстрее любого многочлена, можно считать непрактичными. Я говорю именно о сверхполиномиальном, а не только об экспоненциальном времени, поскольку между полиномиальной и хорошо известной экспоненциальной сложностью O(2^n) существуют промежуточные сложности, например O(n^(log n)), как показано на рисунке 9-2.

Рисунок 9-2. Рост функций 2^n, n^(log n) и n^2 - от самой быстрорастущей до самой медленнорастущей

O(n^2) или O(n^3) может быть эффективной, но O(n^(99 999 999 999)) очевидно не является таковой. Иными словами, полиномиальное время быстро на практике, пока показатель степени не слишком велик. К счастью, все найденные алгоритмы полиномиального времени для реальных задач имеют небольшие показатели. Например, O(n^(2,373)) - теоретическая временная сложность лучшего известного алгоритма умножения двух матриц n* n, хотя на практике он никогда не используется. Прорывной детерминированный алгоритм полиномиального времени 2002 года для определения простоты n-битных чисел первоначально имел сложность O(n^12), но позже был улучшен до O(n^6). Поэтому полиномиальное время, возможно, не идеально определяет практичность алгоритма, но это лучшее доступное определение.

Соответственно, задачу, которую нельзя решить алгоритмом полиномиального времени, можно считать непрактичной, или трудной. Например, при прямом переборе ключа нельзя превзойти сложность O(2^n), если только сам шифр каким-либо образом не взломан.

Примечание. Экспоненциальная сложность O(2^n) - не худший вариант. Некоторые сложности растут еще быстрее и характеризуют еще более медленные алгоритмы: например, O(n^n) или экспоненциальный факториал O(n^(f(n-1))), где функция f рекурсивно определяется для любого x как f(x)=x^(f(x-1)). На практике алгоритмы с такими нелепыми сложностями вам никогда не встретятся.

Вы знаете, что сложность полного перебора ключа O(2^n) невозможно превзойти, пока шифр безопасен, но в общем случае самый быстрый способ решения вычислительной задачи известен не всегда. Значительная часть исследований в теории сложности посвящена доказательству границ сложности времени выполнения алгоритмов, решающих заданную задачу. Чтобы облегчить работу, теоретики сложности распределили вычислительные задачи по разным группам, или классам, в зависимости от усилий, необходимых для решения.

В математике класс - группа объектов с некоторым общим свойством. Например, все вычислительные задачи, решаемые за время O(n^2), которое теоретики сложности обозначают просто TIME(n^2), образуют один класс. Аналогично, TIME(n^3) - класс задач, решаемых за время O(n^3), TIME(2^n) - класс задач, решаемых за время O(2^n), и так далее. По той же причине, по которой суперкомпьютер способен вычислить все, что способен ноутбук, любая задача, решаемая за O(n^2), решается и за O(n^3). Поэтому любая задача класса TIME(n^2) принадлежит также классу TIME(n^3), оба они принадлежат TIME(n^4) и так далее. Объединение всех классов TIME(n^k) для любых констант k называется P, что означает polynomial time, полиномиальное время.

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

Формально расход памяти алгоритма определяется как функция длины входа n точно так же, как временная сложность. Класс задач, решаемых с использованием f(n) битов памяти, называется SPACE(f(n)). Например, SPACE(n^3) - класс задач, решаемых с использованием порядка n^3 битов памяти. Подобно тому как P является объединением всех TIME(n^k), объединение всех задач SPACE(n^k) называется PSPACE.

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

Любой задаче, решаемой за время f(n), требуется не более f(n) памяти, поэтому TIME(f(n)) входит в SPACE(f(n)). За время f(n) можно записать не более f(n) битов, поскольку предполагается, что запись или чтение одного бита занимает одну единицу времени; следовательно, любая задача из TIME(f(n)) не может использовать больше f(n) памяти. Поэтому P является подмножеством PSPACE.

NP, nondeterministic polynomial time, недетерминированное полиномиальное время, - второй по важности класс сложности после P, класса всех алгоритмов полиномиального времени.

NP - класс задач разрешимости, для которых решение можно проверить за полиномиальное время, то есть эффективно, хотя найти решение может быть трудно. Под проверкой я подразумеваю, что, имея потенциальное решение, можно выполнить некоторый алгоритм полиномиального времени и установить, действительно ли решение найдено. Например, задача определения того, существует ли ключ K, такой что C=E(K,P), при заданных P и C для симметричной криптосистемы E принадлежит NP. Причина в том, что для ключа-кандидата K_0 можно проверить его правильность, установив равенство E(K_0,P) и C. Найти потенциальный ключ, то есть решение, за полиномиальное время нельзя, если он существует, но проверить правильность ключа можно.

Теперь контрпример: что насчет атак с известным шифртекстом? На этот раз даны лишь некоторые значения E(K,P) для случайных неизвестных открытых текстов P. Если P неизвестны, проверить правильность потенциального ключа K_0 невозможно. Иными словами, задача восстановления ключа при атаке с известным шифртекстом не принадлежит NP, а тем более P, поскольку ее нельзя выразить как задачу разрешимости.

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

NP-полные задачи - самые трудные задачи разрешимости класса NP; способы решения их худших случаев за полиномиальное время неизвестны. Когда в 1970-х годах теоретики сложности разработали теорию NP-полноты, они обнаружили, что самые трудные задачи NP в основе своей одинаково трудны. Это было доказано демонстрацией того, что любое эффективное решение любой NP-полной задачи можно превратить в эффективное решение любой другой NP-полной задачи. Иными словами, если вы умеете эффективно решать хотя бы одну NP-полную задачу, то сможете решить их все, а вместе с ними все задачи NP. Как это возможно?

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

Вот несколько примеров NP-полных задач:

Задача коммивояжера. Даны множество точек на карте, например городов, расстояния между каждой парой точек и максимальное расстояние x. Нужно определить, существует ли путь, посещающий каждую точку, общая длина которого меньше x. Обратите внимание, что такой путь можно найти практически с той же сложностью, что решить задачу разрешимости, но определение оптимальности пути не принадлежит NP, поскольку правильность решения невозможно эффективно проверить.

Задача о клике. Даны число x и граф, то есть множество узлов, соединенных ребрами, как на рисунке 9-3. Нужно определить, существует ли множество не более чем из x узлов, каждый из которых соединен со всеми остальными.

Рисунок 9-3. Граф, содержащий клику из четырех узлов. Общая задача поиска в графе клики заданного размера, то есть множества узлов, каждый из которых соединен со всеми остальными, является NP-полной

Задача о рюкзаке. Даны два числа x и y и набор предметов, для каждого из которых известны ценность и вес. Нужно определить, существует ли группа предметов с общей ценностью не менее x и общим весом не более y.

NP-полные задачи встречаются повсюду: от планирования, где задания с заданным приоритетом и длительностью нужно распределить по одному или нескольким процессорам, соблюдая приоритет и минимизируя общее время выполнения, до удовлетворения ограничений, где требуется определить значения, удовлетворяющие набору математических ограничений, например логических уравнений. Было доказано, что даже задача победы в некоторых видеоиграх NP-трудна, в том числе для известных игр Tetris, Super Mario Bros., Pokémon и Candy Crush Saga. Например, статья «Classic Nintendo Games are (Computationally) Hard» рассматривает «задачу разрешимости достижимости», чтобы определить возможность добраться до целевой точки из заданной начальной; см. https://arxiv.org/abs/1203.1895.

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

NP-полные задачи обязаны быть задачами разрешимости, то есть иметь ответ «да» или «нет». Поэтому, строго говоря, задачи вычисления «лучшего» значения решения не могут быть NP-полными, но могут быть NP-трудными. Например, в задаче коммивояжера вопрос «Существует ли путь, посещающий все точки и имеющий длину меньше X?» является NP-полным, а требование «Найти самый быстрый путь, посещающий все точки» - NP-трудным.

Обратите внимание, что не все экземпляры NP-трудных задач действительно трудно решать. Некоторые экземпляры могут эффективно решаться благодаря малому размеру или особой структуре. Возьмем, например, граф на рисунке 9-3. В нем легко заметить клику - четыре верхних соединенных узла. Хотя упомянутая задача поиска клики NP-трудна, здесь нет ничего трудного. NP-трудность означает не то, что трудны все экземпляры задачи, а то, что некоторые становятся трудными с ростом размера. Именно поэтому криптографов больше интересуют задачи, трудные в среднем, а не только в худшем случае.

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

Как бы безумно это ни звучало, никто не доказал различие P и NP, несмотря на премию в миллион долларов. Институт математики Клэя вручит ее тому, кто докажет либо P!= NP, либо P=NP. Эту проблему, известную как P против NP, знаменитый теоретик сложности Скотт Ааронсон назвал «одним из глубочайших вопросов, когда-либо заданных человечеством». Подумайте: если бы P равнялось NP, любое легко проверяемое решение было бы легко найти. Вся практическая криптография стала бы небезопасной, поскольку симметричные ключи можно было бы эффективно восстанавливать, а хеш-функции - обращать.

Но не паникуйте: большинство теоретиков сложности полагают, что P не равно NP и потому P является строгим подмножеством NP, как показано на рисунке 9-4, где NP-полные задачи образуют другое подмножество NP, не пересекающееся с P. Иными словами, задачи, выглядящие трудными, действительно трудны. Просто математически доказать это сложно. Для доказательства P=NP достаточно одного алгоритма полиномиального времени для NP-полной задачи, а доказать отсутствие такого алгоритма принципиально труднее. Это не мешает математикам предлагать простые доказательства, обычно очевидно ошибочные, но нередко забавные; пример см. на «The P-versus-NP page».

Рисунок 9-4. Классы NP и P и множество NP-полных задач

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

Задача факторизации состоит в нахождении простых чисел p и q по большому числу N=p* q. Широко применяемые алгоритмы RSA основаны на трудности факторизации: схемы шифрования и подписи RSA безопасны, потому что факторизация - трудная задача. Прежде чем в главе 10 мы увидим, как RSA использует факторизацию, я хотел бы убедить вас, что версия этой задачи в форме разрешимости - «Имеет ли N множитель меньше k, не равный 1?» - действительно трудна, но, вероятно, не является NP-полной.

Сначала немного базовой математики. Простое число не делится ни на какое другое число, кроме себя и 1. Например, 3, 7 и 11 - простые числа, а 4, то есть 2*2, 6, то есть 2*3, и 12, то есть 2*2*3, - нет. Основная теорема арифметики утверждает, что любое целое число можно единственным образом записать как произведение простых чисел; такое представление называется факторизацией числа. Например, факторизация 123 456 равна 2^6*3*643, факторизация 1 234 567 - 127*9721 и так далее. У каждого целого числа есть единственная факторизация, то есть единственный способ записи в виде произведения простых чисел. Алгоритмы проверки простоты полиномиального времени позволяют эффективно установить, является ли заданное число простым и содержит ли заданная факторизация только простые числа. Однако переход от числа к его простым множителям - совсем другое дело.

Как же перейти от числа к его факторизации, то есть разложению в произведение простых чисел? Самый простой способ факторизовать число N - пробовать делить его на все меньшие числа, пока не найдется число x, делящее N. Затем попытаться разделить N на следующее число x+1 и так далее. В результате получится список множителей N. Какова временная сложность? Сначала вспомним, что сложность выражается как функция длины входных данных. Битовая длина числа N равна n=log_2N. По определению логарифма это означает N=2^n. Поскольку все числа меньше N/2 являются разумными кандидатами на роль множителей N, нужно испытать около N/2=2^n/2 значений. Поэтому сложность наивного алгоритма факторизации равна O(2^n), если в нотации O() отбросить коэффициент 1/2.

Многие числа легко факторизовать: сначала найти небольшие множители 2, 3, 5 и так далее, а затем итеративно факторизовать остальные непростые множители. Но нас интересуют встречающиеся в криптографии числа вида N=p* q, где p и q велики.

Поступим немного умнее: проверять все числа меньше N/2 не нужно, достаточно простых чисел меньше квадратного корня из N. Если N не является простым, у него должен быть хотя бы один множитель меньше sqrt(N). Если бы оба множителя N, p и q, были больше sqrt(N), их произведение было бы больше sqrt(N)timessqrt(N)=N, что невозможно. Например, если N=100, множители p и q не могут оба быть больше 10, поскольку тогда произведение превысило бы 100. Либо p, либо q обязано быть меньше или равно sqrt(N).

Какова сложность проверки только простых чисел меньше sqrt(N)? Теорема о распределении простых чисел утверждает, что простых чисел меньше N приблизительно N/log N. Следовательно, простых чисел меньше sqrt(N) приблизительно sqrt(N)/logsqrt(N). Выразив это значение через n=log_2N, получим примерно 2^(n/2+1)/n возможных простых множителей, а значит, сложность O(2^(n/2)/n), поскольку sqrt(N)=2^(n/2) и 1/logsqrt(N)=1/(n/2)=2/n. Это быстрее проверки всех простых чисел, но все равно мучительно медленно: порядка 2^120 операций для 256-битного числа. Такие вычислительные усилия совершенно непрактичны. Но можно намного лучше.

Самый быстрый алгоритм факторизации - общее решето числового поля (general number field sieve, GNFS). Я не буду описывать его здесь, поскольку для этого пришлось бы ввести несколько продвинутых математических понятий. Грубая оценка сложности GNFS равна

где n=log_2N - битовая длина N, а exp(...) - другая запись экспоненциальной функции e^x, причем экспоненциальная константа e приблизительно равна 2,718. Однако точно оценить фактическую сложность GNFS для заданного размера числа трудно. Поэтому приходится опираться на эвристические оценки сложности, показывающие рост безопасности с увеличением n. Например:

• Факторизация 1024-битного числа с двумя простыми множителями примерно по 500 битов требует порядка 2^70 базовых операций.

• Факторизация 2048-битного числа с двумя простыми множителями примерно по 1000 битов требует порядка 2^90 базовых операций - примерно в миллион раз больше, чем для 1024-битного числа.

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

• В 2005 году примерно после 18 месяцев вычислений группа исследователей факторизовала 663-битное число, состоявшее из 200 десятичных цифр, благодаря мощности кластера из 80 процессоров. Общие усилия соответствовали 75 годам вычислений на одном процессоре.

• В 2009 году примерно после двух лет работы на нескольких сотнях процессоров другая группа исследователей факторизовала 768-битное число из 232 десятичных цифр. Общие усилия соответствовали приблизительно 2000 годам вычислений на одном процессоре.

• В 2020 году после нескольких месяцев вычислений на десятках тысяч процессоров и суперкомпьютере еще одна группа факторизовала 829-битное число из 250 десятичных цифр. Общие усилия соответствовали примерно 2700 годам вычислений на одном процессоре.

Как видите, факторизованные исследователями числа короче применяемых в реальных приложениях, где длина составляет не менее 1024, а часто более 2048 битов. На момент написания книги никто не сообщил о факторизации 1024-битного числа, но многие предполагают, что хорошо финансируемые организации вроде АНБ способны это сделать.

Итак, 1024-битный RSA следует считать небезопасным и использовать RSA со значением длиной не менее 2048 битов, а для более высокой безопасности предпочтительно 4096 битов.

Мы не знаем, как эффективно факторизовать большие числа, поэтому, вероятно, задача факторизации не принадлежит P. Однако версия факторизации в форме задачи разрешимости явно принадлежит NP: имея факторизацию, можно проверить решение, установив с помощью упомянутого алгоритма проверки простоты, что все множители просты, и убедившись, что их произведение дает ожидаемое число. Например, чтобы проверить, что 3*5 является факторизацией 15, нужно подтвердить простоту 3 и 5 и равенство произведения 3 и 5 числу 15.

Итак, у нас есть принадлежащая NP и выглядящая трудной задача. Но так ли она трудна, как самые трудные задачи NP? Иными словами, является ли версия факторизации в форме задачи разрешимости NP-полной и, следовательно, факторизация NP-трудной? Спойлер: вероятно, нет.

Математического доказательства того, что факторизация не NP-трудна, не существует, но есть несколько косвенных свидетельств. Во-первых, все известные NP-трудные задачи в NP могут иметь одно решение, несколько решений или не иметь ни одного. Факторизация, напротив, всегда имеет ровно одно решение. Кроме того, задача факторизации обладает математической структурой, позволяющей алгоритму GNFS значительно превосходить наивный алгоритм, тогда как у NP-трудных задач такой структуры нет. Факторизация была бы легкой для квантового компьютера - вычислительной модели, использующей явления квантовой механики для выполнения алгоритмов иного типа, способной эффективно факторизовать большие числа. Не потому, что такой компьютер быстрее выполнял бы обычный алгоритм, а потому, что он мог бы выполнить квантовый алгоритм, специально предназначенный для факторизации больших чисел. Однако такого квантового компьютера пока не существует и, возможно, никогда не будет. Считается, что для решения NP-трудных задач квантовый компьютер бесполезен, поскольку будет не быстрее классического; см. главу 14.

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

Задача факторизации - одна из нескольких задач, используемых в криптографии как предположение о трудности, то есть предположение о вычислительной трудности некоторой задачи. Оно применяется при доказательстве того, что нарушение безопасности криптосистемы не легче решения данной задачи. Другая задача, используемая как предположение о трудности, - задача дискретного логарифмирования (discrete logarithm problem, DLP), которая на самом деле является семейством задач.

В официальной истории криптографии задача дискретного логарифмирования появилась раньше задачи факторизации. RSA возникла в 1977 году, а другой криптографический прорыв - согласование ключей Диффи - Хеллмана, рассматриваемое в главе 11, - произошел годом раньше и основывал безопасность на трудности DLP. Подобно факторизации, DLP имеет дело с большими числами, но устроена менее очевидно и требует больше математики. Начнем с математического понятия группы в контексте дискретных логарифмов.

Более чем через 40 лет мы все еще не знаем, как эффективно факторизовать большие числа или решать дискретные логарифмы. Без математического доказательства всегда можно предположить, что однажды они будут взломаны. Но у нас нет и доказательства P!= NP, поэтому можно предположить P=NP; однако специалисты считают такой сюрприз маловероятным. Большинство развернутой сегодня криптографии с открытым ключом опирается либо на факторизацию, RSA, либо на DLP: Диффи - Хеллман, ElGamal, криптография на эллиптических кривых. Возможно, математика нас не подведет, но могут вмешаться практические обстоятельства и человеческие ошибки.

Факторизация больших чисел трудна не всегда. Рассмотрим, например, следующее 1024-битное число N:

Для 1024-битных чисел в схемах шифрования или подписи RSA, где N=pq, ожидается, что лучшим алгоритмам факторизации потребуется около 2^70 операций, как обсуждалось выше. Но этот пример можно факторизовать за секунды с помощью SageMath - математической программы на основе Python. Функция factor() SageMath на моем MacBook 2023 года нашла следующую факторизацию менее чем за секунду:

Да, я схитрил. Это число не имеет вида N=pq, поскольку у него не два больших простых множителя, а пять, включая очень малые, поэтому его легко факторизовать. Сначала часть 2^800*641*6 700 417 обнаруживается перебором малых простых чисел из заранее вычисленного списка, после чего остается 192-битное число, факторизовать которое намного легче, чем 1024-битное число с двумя большими множителями.

Факторизация может быть легкой не только при наличии у N малых простых множителей, но и когда N или его множители p и q имеют особую форму, например когда N=pq, причем и p, и q близки к некоторому 2^b; когда N=pq и известны некоторые биты p или q; либо когда N имеет вид N=p^rq^s, а r больше log p. Однако подробное объяснение причин этих слабостей слишком техническое для этой книги.

В результате алгоритмы шифрования и подписи RSA, см. главу 10, должны работать со значением N=pq, где p и q тщательно выбраны, чтобы избежать легкой факторизации N, способной привести к катастрофе безопасности.

Вычислительно трудные задачи и даже алгоритмы экспоненциального времени становятся практичными, если достаточно малы. Симметричный шифр может быть безопасен в том смысле, что атаки быстрее полного перебора за 2^n не существует, но при длине ключа n=32 шифр будет взломан за минуты. Это кажется очевидным, и можно подумать, что никто не станет настолько наивно использовать короткие ключи, однако в действительности такое может происходить по множеству причин. Вот две реальные истории.

Предположим, вы разработчик, ничего не знающий о криптографии, но имеющий API для шифрования RSA, и вам велели обеспечить 128-битную безопасность. Какой размер ключа RSA вы выберете? Я встречал реальные случаи 128-битного RSA, то есть RSA на основе 128-битного числа N=pq. Но хотя факторизация практически неосуществима для N длиной в тысячи битов, 128-битное число факторизовать легко. Следующие команды SageMath в листинге 9-2 выполняются мгновенно.

Листинг 9-2. Создание модуля RSA путем выбора двух случайных простых чисел и его мгновенная факторизация

Листинг 9-2 показывает, что на обычном ноутбуке легко факторизовать случайное 128-битное число, являющееся произведением двух 64-битных простых. Но если вместо этого выбрать 1024-битные простые числа с помощью p = random_prime(2**1024), команда factor(p*q) никогда не завершится, по крайней мере при моей жизни.

Справедливости ради, доступные инструменты не помогают предотвращать наивное применение небезопасно коротких параметров. Например, инструментарий OpenSSL прежде позволял без всякого предупреждения создавать ключи RSA длиной всего 31 бит; такие короткие ключи совершенно небезопасны, как показано в листинге 9-3. С тех пор OpenSSL был исправлен, и версия 1.1.1t от февраля 2023 года возвращает ошибку key size too small, если запросить ключ короче 512 битов.

Листинг 9-3. Создание небезопасного закрытого ключа RSA старой версией инструментария OpenSSL

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

В 2015 году исследователи обнаружили, что многие HTTPS- и почтовые серверы поддерживали старую небезопасную версию протокола согласования ключей Диффи - Хеллмана. В частности, лежащая в основе реализация TLS поддерживала Диффи - Хеллман в группе Z_p^*, определенной простым числом p длиной всего 512 битов, где задача дискретного логарифмирования уже не была практически неразрешимой.

Серверы не только поддерживали слабый алгоритм: атакующие могли принудить обычного клиента использовать его, внедрив вредоносный трафик в сеанс клиента. Что еще лучше для атакующих, основную часть атаки можно было выполнить один раз и повторно использовать против множества клиентов. После приблизительно недели вычислений для атаки на конкретную группу Z_p^* взлом отдельного сеанса любого пользователя занимал всего 70 секунд.

Безопасный протокол ничего не стоит, если его подрывает ослабленный алгоритм, а надежный алгоритм бесполезен, если саботирован слабыми параметрами. В криптографии всегда нужно читать мелкий шрифт.

Подробности этой истории см. в исследовательской статье «Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice».

Я призываю глубже изучить основополагающие аспекты вычислений в контексте вычислимости - какие функции можно вычислить? - и сложности - с какой стоимостью? - а также их связь с криптографией. Я говорил в основном о классах P и NP, но существует множество других классов и тем, интересных криптографам. Настоятельно рекомендую книгу Скотта Ааронсона «Quantum Computing Since Democritus» (Cambridge University Press, 2013). Она в значительной степени посвящена квантовым вычислениям, но первые главы блестяще знакомят с теорией сложности и криптографией.