Какого бы происхождения ни была случайность, генератор создаст ряд случайных битов. Затем их можно использовать как криптографические ключи и для всего остального, что нужно системе.
Один из простейших критериев сравнения криптографических алгоритмов – длина ключа. Пресса любит обращать на нее внимание, поскольку ее легко считать и сравнивать. Как и в большинстве случаев, когда речь идет о безопасности, реальность более сложна. Короткий ключ плох, но длинный ключ не будет хорошим автоматически. Почему это так, я расскажу в следующей главе, а сейчас лучше разъяснить понятие длины ключа и его важность.
Начнем с самого начала. Криптографический ключ – это секретное число, которое делает криптографический алгоритм уникальным для тех, кто совместно пользуется этим ключом. Если Алиса и Боб договорились об общем ключе, то при помощи алгоритма они могут тайно пообщаться. Если Ева-перехватчица не знает ключа, ей придется исследовать и ломать алгоритм.
Одна очевидная вещь, которую можно сделать, – это перепробовать все возможные ключи. Это так называемая атака «в лоб», или лобовая атака. Если длина ключа n битов, то существует 2^n всевозможных комбинаций ключей. При длине ключа в 40 бит, придется перебрать около триллиона вариантов ключей. Такая задача покажется ужасно скучной для Евы, но компьютеры неутомимы. Они лучше всех решают ужасно скучные задачи. В среднем компьютеру пришлось бы испробовать половину ключей, прежде чем он найдет правильный, то есть компьютер, который мог бы проверять миллиард ключей в секунду, потратил бы на поиски правильного 40-битового ключа примерно 18 минут. В 1998 году Electronic Frontier Foundation создала машину, которая могла атакой «в лоб» ломать DES-алгоритм. Эта машина, названная DES Deep Crack, проверяла 90 миллиардов ключей в секунду; она могла найти 56-битовый ключ DES в среднем за 4,5 дня. В 1999 году распределенный интернет-проект подбора ключей для взлома DES, distributed net (включающий в себя Deep Crack), был способен проверить 250 миллиардов ключей в секунду.
Все схемы таких взломов «в лоб» линейны: вдвое большее количество ключей потребует вдвое больше компьютерного времени. Но сложность такого взлома зависит от длины ключей экспоненциально: добавим один бит к длине ключа, и взлом «в лоб» станет в два раза сложнее. Добавим два бита – в четыре раза. Десять битов – в тысячу раз сложнее.
Сила атак «в лоб» в том, что они работают против любого алгоритма. Поскольку эта атака не касается внутренней математики алгоритма, ей все равно, что же там внутри. Одни алгоритмы могут быть быстрее других, и поэтому атака «в лоб» проходит быстрее, но длина ключа легко это перевешивает. Достаточно просто сравнить длины ключей различных алгоритмов, чтобы выяснить, какие из них более уязвимы для лобовой атаки.
В 1996 году группа шифровальщиков (включающая и меня) исследовала различные технологии, которые можно использовать для создания дешифрующих машин, действующих по принципу лобовой атаки, и пришла к выводу, что 90-битовый ключ сможет обеспечивать безопасность до 2016 года. Ключ Triple-DES состоит из 112 бит, а наиболее современные алгоритмы имеют по меньшей мере 128-битовые ключи. (Улучшенный стандарт шифрования (AES) правительства США поддерживает длины ключей 128,192 и 256 бит.) Даже машине, работающей в миллиард раз быстрее Deep Crack, потребовался бы миллион лет, чтобы перебрать 2^112 ключей и восстановить открытый текст; еще более, чем в тысячу раз, возрастает время при переходе к 128-битовому ключу. Он будет обеспечивать безопасность в течение тысячелетия.
К этим числам нужно относиться с некоторым скептицизмом. Я – не ясновидящий и ничего не знаю о будущих достижениях компьютерных технологий. Реальная безопасность зависит от нескольких вещей: насколько ваши данные ценны, как долго их требуется хранить в тайне и т. п. Но это означает, что должны существовать «законсервированные» числа – длины ключей для симметричных алгоритмов и MAC. Хэш-функции должны иметь длину, равную удвоенной длине ключа.
Длина ключа для симметричного алгоритма открытого ключа определяется более сложным образом. Наиболее эффективная атака против RSA, например, состоит в том, чтобы разложить на множители большое число. Наиболее действенная атака против Эль-Гамаля, алгоритма Диффи-Хеллмана, DSA и других систем – вычислить нечто, называемое дискретным логарифмом. (По существу, это – та же проблема.) Алгоритмы эллиптических кривых еще более сложны.
Для алгоритмов с открытым ключом специалисты сейчас рекомендуют 1024-битовые и более ключи. Параноики используют ключи еще длиннее. Системы, для которых не слишком важна долговременная секретность, пользуются 768-битовыми ключами. (Для алгоритмов эллиптических кривых применяют разные длины ключей.)
Трудно оценивать будущие трудности разложения на множители и вычисления дискретных логарифмов, поскольку нет никакого математического доказательства, что эти задачи имеют фиксированную степень сложности. (С другой стороны, мы знаем, насколько трудно перебирать все возможные ключи.) Итак, еще раз: отнеситесь ко всем этим рекомендациям, как к мнению квалифицированных специалистов – и не более того.
Глава 7Криптография в контексте
Если криптография так надежна, то почему же происходят сбои в системах защиты? Почему существуют электронные кражи, мошенничество, нарушения конфиденциальности и все прочие проблемы безопасности, которые обсуждались в предыдущих главах? Почему криптография не соответствует всем без исключения требованиям безопасности? Зачем я докучаю вам такой толстой книгой?
Достаточно неожиданно, но причина этого не в плохом качестве криптографии. (Многое лежит на поверхности, но есть и проблемы, упрятанные гораздо более глубоко.) Ответ нужно искать в различии между теорией и практикой.
Криптография – это раздел математики. Математика – теоретическая наука; она логична. Хорошая математика исходит из правильной предпосылки, следует единственным путем – доказательство за доказательством – через неизведанные земли и заканчивается неопровержимым выводом. По природе своей она хорошо выглядит на бумаге.
Корни проблем безопасности следует искать в физическом мире. Материальный мир во многом нелогичен. Он неупорядочен. В нем не существует единственного пути. В нем есть теории и выводы, но для того чтобы согласиться с выводами, вам необходимо принять предпосылки, модели и взаимосвязи между теориями и реальным миром. А это непросто. Люди не играют по правилам. Они делают то, чего от них не ожидают; они не укладываются в жесткие рамки. То же самое касается технических средств: время от времени все начинает плохо работать, а то и вовсе ломается. Это же можно сказать о программном обеспечении. Оно должно быть логичным и упорядоченным, как-никак это – просто комбинация нулей и единиц, но иногда оно настолько сложно, что становится больше похожим на организм, а не на творение математики. Неважно, насколько хороша криптографическая теория: когда она используется в системе, она сталкивается с практикой.
Я часто говорю о программах, что они – лишь дань моде. Когда реклама утверждает, что используется RSA, тройной DES или любой другой модный алгоритм криптографии, это равносильно заявлению о том, что дом полностью безопасен только потому, что у него надежный дверной замок. Этого недостаточно.
Несмотря на то что я сказал в предыдущей главе, длина ключа почти ничего не определяет в безопасности.
Внутри замка на входной двери вашего дома есть множество штырьков. Для каждого из них существуют различные возможные положения. Когда кто-то вставляет ключ в замочную скважину, все штырьки перемещаются в определенные позиции. Если положение, в которое ключ ставит штырьки, как раз то, которое необходимо, чтобы замок открылся, то он открывается. Если нет – не открывается.
У замков, наиболее часто используемых в жилых домах, пять штырьков, каждый из которых может располагаться в одном из десяти различных положений. Это означает, что существует 100 000 возможных ключей. Взломщик с огромной связкой ключей может перебрать все ключи один за другим и в конце концов попасть внутрь. Ему лучше набраться терпения, поскольку если даже он тратит на один ключ 5 секунд, ему потребуется примерно 69 часов, чтобы найти подходящий ключ (и это без перерывов на сон, еду и душ).
Однажды в вашу дверь звонит торговый агент и предлагает вам купить новый замок. У его замка семь штырьков по двенадцать положений у каждого. Агент скажет, что взломщику придется три года непрерывно перебирать ключи, прежде чем он сможет открыть дверь. Почувствуете ли вы себя в большей безопасности с таким замком?
Наверное, нет. Все равно ни один взломщик не стал бы стоять перед вашей дверью 69 часов. Он, скорее всего, откроет замок отмычкой, просверлит его, вышибет дверь, разобьет окно или просто спрячется в кустах до тех пор, пока вы не отправитесь на прогулку. Замок с большим количеством штырьков и положений не обеспечит вашему дому большую безопасность, поскольку атака, которая таким образом затрудняется – перебором еще большего количества ключей – не та атака, о которой стоит задумываться особо. До тех пор пока количества штырьков достаточно, чтобы сделать недопустимой такую атаку, вам не следует о ней беспокоиться.
То же самое справедливо для криптографических ключей. Если они достаточно длинные, то лобовые атаки просто лежат за пределами человеческих возможностей. Но здесь следует позаботиться о двух вещах. Во-первых, о качестве алгоритма шифрования, а во-вторых, о качестве ключа. Какой ключ является «достаточно длинным», зависит от обеих этих вещей.
Но в первую очередь нужно разъяснить понятие энтропии.
Энтропия – мера беспорядка или, более конкретно в контексте криптографии мера неопределенности. Чем больше неопределенность, тем больше энтропия. Например, случайно выбранный человек из обычной популяции является или мужчиной, или женщиной, в этом случае переменная «пол» составляет один бит энтропии. Если случайный человек сообщает, кто из четырех «Битлз» ему больше нравится, и все варианты равновероятны, этому соответствуют два бита энтропии. Пол члена женской олимпийской команды по бегу – это величина, у которой нет энтропии – они все женщины. Энтр