Длина ключа и безопасность
Несмотря на то что я сказал в предыдущей главе, длина ключа почти ничего не определяет в безопасности.
Внутри замка на входной двери вашего дома есть множество штырьков. Для каждого из них существуют различные возможные положения. Когда кто-то вставляет ключ в замочную скважину, все штырьки перемещаются в определенные позиции. Если положение, в которое ключ ставит штырьки, как раз то, которое необходимо, чтобы замок открылся, то он открывается. Если нет – не открывается.
У замков, наиболее часто используемых в жилых домах, пять штырьков, каждый из которых может располагаться в одном из десяти различных положений. Это означает, что существует 100 000 возможных ключей. Взломщик с огромной связкой ключей может перебрать все ключи один за другим и в конце концов попасть внутрь. Ему лучше набраться терпения, поскольку если даже он тратит на один ключ 5 секунд, ему потребуется примерно 69 часов, чтобы найти подходящий ключ (и это без перерывов на сон, еду и душ).
Однажды в вашу дверь звонит торговый агент и предлагает вам купить новый замок. У его замка семь штырьков по двенадцать положений у каждого. Агент скажет, что взломщику придется три года непрерывно перебирать ключи, прежде чем он сможет открыть дверь. Почувствуете ли вы себя в большей безопасности с таким замком?
Наверное, нет. Все равно ни один взломщик не стал бы стоять перед вашей дверью 69 часов. Он, скорее всего, откроет замок отмычкой, просверлит его, вышибет дверь, разобьет окно или просто спрячется в кустах до тех пор, пока вы не отправитесь на прогулку. Замок с большим количеством штырьков и положений не обеспечит вашему дому большую безопасность, поскольку атака, которая таким образом затрудняется – перебором еще большего количества ключей – не та атака, о которой стоит задумываться особо. До тех пор пока количества штырьков достаточно, чтобы сделать недопустимой такую атаку, вам не следует о ней беспокоиться.
То же самое справедливо для криптографических ключей. Если они достаточно длинные, то лобовые атаки просто лежат за пределами человеческих возможностей. Но здесь следует позаботиться о двух вещах. Во-первых, о качестве алгоритма шифрования, а во-вторых, о качестве ключа. Какой ключ является «достаточно длинным», зависит от обеих этих вещей.
Но в первую очередь нужно разъяснить понятие энтропии.
Энтропия – мера беспорядка или, более конкретно в контексте криптографии мера неопределенности. Чем больше неопределенность, тем больше энтропия. Например, случайно выбранный человек из обычной популяции является или мужчиной, или женщиной, в этом случае переменная «пол» составляет один бит энтропии. Если случайный человек сообщает, кто из четырех «Битлз» ему больше нравится, и все варианты равновероятны, этому соответствуют два бита энтропии. Пол члена женской олимпийской команды по бегу – это величина, у которой нет энтропии – они все женщины. Энтропия предпочтений одного из «Битлз» на собрании фан-клуба Джона Леннона существенно меньше двух битов, поскольку наиболее вероятно, что выбранный наугад человек предпочитает Джона. Чем больше определенность переменной, тем меньше энтропия.
То же самое верно для криптографических ключей. То, что алгоритм использует 128-битовый ключ, не означает, что у него 128 бит энтропии для ключа. Или точнее, лучший способ сломать данную реализацию 128-битового алгоритма шифрования может состоять не в том, чтобы перебрать все ключи. «128 бит» – это просто мера максимального количества работы, которая потребуется, чтобы восстановить ключ; но про минимум ничего не сказано.
Во-первых, следует позаботиться о происхождении ключа. Все вычисления, касающиеся длины ключа, я производил, предполагая, что каждый ключ имеет при создании максимальную энтропию. Другими словами, я рассчитывал, что все варианты ключа равновероятны, что генератор случайных чисел, создавший ключ, работает идеально. Это допущение не совсем верно.
Многие ключи создаются на основе паролей и ключевых фраз. Система, принимающая пароль из 10 ASCII-символов, предоставляет для него 80 бит, но ее энтропия будет значительно меньше 80 бит. Некоторые символы ASCII никогда не появляются, а пароли, которые представляют собой реальные слова (или что-то похожее на слова), гораздо вероятнее, чем произвольные строки символов. Я видел оценки энтропии для английского языка, меньшие 1,3 бит на символ; у пароля энтропия меньше, чем 4 бит на символ. Это значит, что пароль из 8 символов будет приблизительно соответствовать 32-битовому ключу, а если вы захотите 128-битовый ключ, вам нужен пароль из 98 символов (на базе английского алфавита).
Видите ли, разумный взломщик не будет перебирать все возможные пароли по порядку. Он сначала испробует наиболее вероятные, а затем проверит остальные – в порядке убывания вероятности. Он проверит тривиальные пароли (типа «пароль» или «1234»), после этого – весь английский словарь, а затем различные заглавные буквы, цифры и т. п. Это называют словарной атакой. Программа для взлома пароля, реализующая такую атаку, называется L0phtcrack; на 400-мегагерцовом Quad Pentium II она может протестировать зашифрованный пароль по 8-мегабайтовому словарю распространенных паролей за считанные секунды.
Вот почему смешно, когда компании вроде Microsoft рекламируют 128-битовое шифрование, а затем берут за основу ключа пароль. (Это в высшей степени характерно для всей системы безопасности Windows NT[22].) Используемые алгоритмы могут допускать 128-битовый ключ, но энтропия пароля гораздо меньше. Фактически, качество криптографии и длина ключа не важны; причиной выхода системы из строя послужит слабый пароль. (Очевидное решение – не допустить, чтобы люди перебирали множество паролей, – не срабатывает. Я подробнее остановлюсь на этой проблеме в главе 9.)
Это очень важно. Я знаю сложные системы, секретный ключ которых защищен паролем. В основе безопасности практически любого зашифрованного продукта на жестком диске компьютера лежит ключ, запоминаемый пользователем. Почти вся система безопасности Windows NT приходит в негодность из-за того, что она построена на основе пароля, запоминаемого пользователем. Даже система PGP (Pretty Good Privacy) распадется, если пользователь выберет плохой пароль.
Не важно, какие алгоритмы и насколько длинные ключи используются; секреты, которые хранятся в памяти пользователя, беззащитны сами по себе.
Ключ, сгенерированный случайным образом, намного лучше, но проблемы остаются. Генератор случайных чисел должен создавать ключи с максимальной энтропией. Недостатки генератора случайных чисел – те же, что привели к сбоям системы шифрования в Netscape Navigator 1.1. Хотя генератор случайных чисел применяли для создания 128-битовых ключей, максимальная энтропия достигала примерно 20 бит. То есть алгоритм был не лучше, чем если бы использовался 20-битовый ключ[23].
Второй предмет заботы – это качество алгоритма шифрования. Все предыдущие расчеты предполагали, что алгоритм получал ключи при помощи вычислений и использовал их совершенным образом. Если в алгоритме есть слабые места, доступные для атаки, это существенно снижает энтропию ключей. Например, алгоритм А5/1, используемый европейской сетью сотовых телефонов GSM, имеет 64-битовый ключ, но может быть взломан за время, требующееся для взлома 30-битового ключа при помощи атаки «в лоб». Это значит, что хотя у алгоритма имеется ключ с 64-битовой энтропией, он задействует для ключа только 30 бит энтропии. Вы можете с тем же успехом использовать хороший алгоритм с 30-битовым ключом.
По этой причине проходит довольно много времени, прежде чем шифровальщики начинают доверять новому алгоритму. Когда кто-то предлагает новый алгоритм, у него есть определенная длина ключа. Но обеспечивает ли алгоритм реально ту энтропию, которая заявлена? Может потребоваться несколько лет анализа, прежде чем мы поверим, что он это делает. И даже тогда мы можем легко ошибиться: возможно, кто-то придумает новые математические подходы, которые понизят энтропию алгоритма и сломают его. Поэтому рекламу программ, в которых обещаются тысячебитовые ключи, трудно воспринимать серьезно – ее создатели не имеют понятия, как работают ключи и энтропия.
Похожая проблема существует и для физических ключей и замков. Принято думать, что слесарь возит в своем грузовике огромное кольцо с ключами от машин. Может потребоваться 10 000 ключей, чтобы открыть все замки, но в реальности несколько дюжин ключей откроют любой из них. Иногда слесарю достаточно просто взять другой ключ, отличающийся от предыдущего на 1-2 «бита», – отметим, что это комбинация анализа и лобовой атаки – и этого уже достаточно. Да, процесс долгий, но совсем не такой, как проверка всех 10 000 возможных ключей (старые замки – четырехштырьковые). Действительная надежность дверного замка существенно отличается от теоретической.
То же самое с комбинациями замков. Вы можете перебрать все возможные комбинации – и существуют машины для взлома сейфов, которые так и делают, – или поступить хитрее. Современные машины для взлома сейфов применяют микрофон, чтобы слушать звук, производимый дисками, когда их поворачивают, и они могут открыть сейф намного быстрее, чем старые, действующие «в лоб».
Сказанное здесь заставляет очень внимательно подходить к выбору алгоритма. Мы еще обсудим это более детально в конце этой главы.