У кого ключ длиннее
АрхивВ криптологии опаснее всего то, что на ее "измерение" очень легко купиться...
В криптологии опаснее всего то, что на ее "измерение" очень легко купиться. Знание длины ключей и криптоаналитических приемов позволяет оценить "трудозатраты" на взлом определенного шифра. И возникает слишком сильный соблазн интерпретации этих цифр так, как если бы они были подлинной мерой безопасности системы. Мэтт Блэйз. Послесловие к книге [1] Не знаю, насколько в переводе текста, поставленного в эпиграф, мне удалось передать тонкую иронию известного криптографа Мэтта Блэйза (Matt Blaze), но суть его замечания - в том, что подавляющее большинство реальных атак предпринимается не против криптографического алгоритма как такового, а против недочетов в протоколе, его реализации, либо с использованием "человеческого фактора". Из этого, несомненно, справедливого наблюдения иногда делается весьма странный вывод: раз доски сарая гниловаты, замок вешать не обязательно (вместо того, чтобы заняться досками). Конечно, если речь идет о защите собственной (личной, корпоративной) приватности, это остается личным делом. Когда же защите подлежит чужая информация - долг оператора каждой системы обеспечить максимальную возможную степень защиты. Проектирование надежных систем - нетривиальная задача, и установка криптомодулей с адекватной длиной ключа, пожалуй, самый простой его элемент. Это не является достаточной мерой предосторожности, но сам факт того, что она не предпринята, однозначно свидетельствует о некомпетентности и/или безответственности оператора. В ноябре 1995 года, собравшись на однодневный митинг в Чикаго, семь видных специалистов в области криптографии и компьютерной инженерии составили ad hoc-доклад "Минимальная длина ключа симметричного шифрования, достаточная для коммерческой безопасности" [2]. В нем, в частности, с опорой на эмпирические оценки утверждалось: "сегодня 40-битные ключи практически не предоставляют никакой защиты против "лобовой" атаки. Даже DES с 56-битными ключами становится все менее адекватным". В то же время, "к счастью, издержки стойкого шифрования лишь незначительно превышают стоимость шифрования слабого". Авторы рекомендовали в качестве адекватной защиты от атак со стороны серьезных оппонентов, как минимум, 75 бит ключа, а в двадцатилетней перспективе - минимум 90 бит. Отчет 1995 года стал первым в ряду согласованных публичных оценок адекватной длины ключа для гражданских криптографических применений. Полученные тогда оценки не подвергались сколько-нибудь значительному пересмотру. Приведенная эффективная длина 90 бит соответствует приблизительно килобитному ключу в асимметричных алгоритмах шифрования и цифровой подписи. Исходя из этого и определены базовые криптофункции для массовых применений: они предусматривают реализацию асимметричных алгоритмов (RSA, ElGamal, DSA) с ключом от 1024 бит и симметричных с ключом 112 (3DES) или 128 (RC5, Blowfish и т. п.) бит. Можно ли считать эти оценки справедливыми? Довольно интересные результаты получил старший научный сотрудник RSA Labs. Роберт Силверман, проанализировавший в недавнем отчете оценки и эмпирические данные по стойкости симметричных и асимметричных алгоритмов в компактном исследовании [3]. Несмотря на то что оценка стоимости "взломов" включает в себя крайне нелинейные компоненты (связанные как со стоимостью оборудования, так и с организационными моментами и мотивацией участников), исторические результаты демонстрационных "взломов" показывают потрясающе линейный рост во времени. Так, академические опыты по факторизации (разложению на множители) больших чисел [1] за тридцатилетний период (1970-99 гг.) ложатся на график эмпирической формулы длина = 4,23(год - 1970) + 23 с коэффициентом корреляции 0,955. Силверман предлагает достаточно сложное (и не менее эмпирическое, чем сам результат) объяснение этого феномена, но более важным кажется то, что, несмотря на развитие методов факторизации, расширение сообщества числовых теоретиков и академических криптоаналитиков и повышение мотивации его участников, за тридцать лет серьезных сюрпризов не было [2]. В таблице приведены оценки стойкости популярных криптоалгоритмов в предположении, что оппонент распоряжается бюджетом в 10 млн. долларов. |
| Длина ключа, бит | Время на взлом | Количество машин | Необходимая память | ||
| симметричного криптоалгоритма | эллиптического криптоалгоритма | алгоритма RSA | |||
| 56 | 112 | 430 | < 5 мин. | 105 | пренебрежимо мала |
| 80 | 160 | 760 | 600 мес. | 4300 | 4 Гбайт |
| 96 | 192 | 1020 | 3 млн. лет | 114 | 170 Гбайт |
| 128 | 256 | 1620 | 1016 лет | 16 | 120 Тбайт |
| В Заключении к отчету Силверман приводит интересные соображения касательно мотиваций к атаке. По Силверману, атака может мотивироваться экономически, "зловредно", академически и политически. Относительно четвертого мотива автор замечает: "Гражданам не стоит бояться того, что правительство предпримет атаку из соображений экономической выгоды, поскольку стоимость атаки превысит любую такую выгоду. Чего стоит опасаться, так это вторжения в частную жизнь [под предлогом охраны правопорядка и защиты национальной безопасности]. Ответить на вопрос о том, сколько ресурсов правительство может потратить на атаку в этих целях, не представляется возможным". Одним из важных инструментов оценки затрат на практический криптоанализ и стимулирования академического криптоанализа в целом являются конкурсы, проводимые различными корпорациями, в частности, RSA Security. Скажем, последние успехи в факторизации больших чисел были достигнуты именно в ходе таких конкурсов, причем уже более десяти лет побеждают операторы систем, распределяющих вычисления посредством локальных сетей и Internet. RSA также проводит конкурсы на "взлом" симметричных шифров; о текущем конкурсе, его российских участниках и команде, собранной в прошлом году под флагом "Компьютерры", см. материал во врезке.
Литература [1] Bruce Schneier. Applied Cryptography, 2nd Ed. - N.Y.: 1996. [2] Matt Blaze, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, and Michael Wiener. Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security. January 1996 (www.counterpane.com/keylength.html). [3] Robert D. Silverman. A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths // RSA Laboratories Bulletin, No. 13, April 2000. 1 (обратно к тексту) - Это самый "трудоемкий" элемент в атаке на шифрование и цифровую подпись по алгоритму RSA. 2 (обратно к тексту) - Некая смута среди "слышавших звон" периодически возникает по поводу так называемых ДНК-вычислений. ДНК-вычисления реализованы достаточно давно, а в 1994 году Леонард Адлеман продемонстрировал пригодность ДНК-компьютера для решения теоретико-числовых задач, эквивалентных задачам криптоанализа. Существенное обстоятельство, однако, заключается в том, что даже универсальный ДНК-компьютер, будучи построен, останется "классическим" компьютером (хотя реализованным не в электромагнитных полях, а в биологической материи), и, следовательно, его производительность будет ограничена теми же фундаментальными физическими принципами, что и производительность электронного оборудования. Квантовые вычисления, будучи реализованы, напротив, заставили бы произвести самую серьезную "переоценку ценностей" в криптологии. Реализуемость квантовых вычислений для практических применений, впрочем, представляет собой открытую исследовательскую проблему. Очень важно проведение достаточного количества открытых исследований. "Компьютерра" регулярно освещает эту тематику и старается рецензировать- пока еще редкую - новую русскую литературу по квантовым вычислениям. |
