взято с http://www.ssl.stu.neva.ru/psw/crypto/keylen.doc

Matt Blaze (AT&T Research), Whitfield Diffie (Sun Microsystems), Ronald L. Rivest (MIT Laboratory), Bruce Schneier (Counterpane Systems), Tsutomu Shimomura (San Diego Supercomputer Center), Eric Thompson, (Access Data Inc.), Michael Wiener (Вell Northern Research)

January 1996

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

Отчет группы криптографов и компьютерных исследователей

АННОТАЦИЯ
Шифрование играет существенную роль в сохранении в тайне электронной секретной информации от угроз со стороны потенциальных взломщиков. Для этого современная криптография использует комбинацию обычных (симметричных) криптографических систем для шифрования данных и открытых (ассиметричных) ключей для управления ключами симметричных систем. Следовательно, оценка стойкости симметричной системы есть существенный шаг в применении криптографии для компьютерной и коммуникационной безопасности.
Технологии, легко доступные сегодня (после 1995 г.) делают силовые атаки на криптографические системы быстрыми и дешевыми. Для этой цели могут быть использованы компьютеры общего назначения, но намного эффективнее использовать Набор Программируемых Чипов (НПЧ). Для взломщика, способного сделать большие начальные инвестиции, специальный чип может производить такие вычисления намного быстрее, и цена решения будет значительно дешевле.
В результате, с этой точки зрения, криптосистемы с 40-битовыми ключами фактически не обеспечивают защиты от силовой атаки. Даже американский государственный стандарт шифрования данных DES с 56-битовыми ключами является недостаточно надежным. Так как криптосистемы болеее подвержены взлому, чем силовой атаке, то важно помнить, что обсуждаемая длина ключа является минимально необходимой для обеспечения безопасности от вычислительных угроз.
К счастью, цена сильного шифрования не на много больше, чем цена слабого. Следовательно, для обеспечения необходимой защиты от наиболее серьезных угроз - крупных финансовых предприятий или иностранных разведслужб - ключи, используемые сегодня для защиты информации должны быть не менее 75-битовой дины. Для защиты информации на следующие 20 лет, перед лицом ожидаемого развития компьютерных мощностей, ключи в проектируемых системах должны быть не менее 90 битов.
1. Шифрование играет существенную роль для сохранения в тайне секретной информации
1.1 Необходимость защиты информации
Сегодня большинство форм информации могут быть записаны и обработаны в электронном виде. Это означает, что в компьютерных сетях может быть найдено большое разнообразие информации, с различными экономическими ценами и уровнями секретности, широким разнообразием во времени, в течение которого она должна быть секретной. Рассмотрим спектр:
• Международные переводы миллионов и, даже, миллиардов долларов, характеризующиеся коротким временем стойкости и существование которых непродолжиительно.
• Стратегический план действий корпорации, секретность которого должна сохраняться в течение некоторого небольшого количества лет. • Права на продукт (формула Коки, состав новых лекарств), которые должны быть защищены на всем протяжении существования и использования продукта, часто десятки лет.
• Информация принадлежащая частным лицам (состояние здоровья, зарплата) которые могут нуждаться в защите на все время жизни
1.2 Шифрование может обеспечить сильную защиту
Шифрование производится перемешиванием данных используя математические процедуры, которые делают его предельно сложным и времяпожирающим для всех, кто не является законным пользователем (обладающим необходимым ключом дешифрования для расшифрования исходного текста). Шифрование гарантирует, что информация будет в безопасности, даже если она попадет к неприятелю в руки. Степень защиты зависит от нескольких факторов: качество криптосистемы, способы ее использования в программах и аппаратуре (особенно ее надежность и способ выбора ключей), общее количество возможных ключей. Криптографический алгоритм считается стойким, если :
1. Не существует короткого пути, позволяющего противнику получить исходный текст без использования силовой атаки
2. Количество возможных ключей значительно больше того, чтобы сделать такую атаку успешной
Размеры ключей шифрования измеряются в битах, а сложность перебора всех возможных ключей растет экспоненциально с ростом числа битов. Добавление одного бита к ключу удваивает количество возможных ключей, добавление 10 - увеличивает его более, чем в 1000 раз. Не существует простого способа взглянуть на шифрсистему и определить существует ли короткий путь. Тем не менее, некоторые алгоритмы - наиболее известен DES - интенсивно изучались в открытой литературе и в них можно быть увереными с высокой степенью доверия. Существенный элемент в разработке криптографического алгоритма это то, что длина ключа есть верхняя грань стойкости шифрсистемы. Повсюду в этой статье мы будем полагать, что не существует короткого пути и считать длину ключа мерой стойкости системы - минимальное количество усилий требуемое для взлома системы. Важно помнить, что криптографы считают это слишком опрометчивым и многие из них рекомендуют ключи двойной или более длины, чем необходимо для защиты от силовой атаки. Предусмотрительный криптодизайн не только применяет более длинные ключи, чем необходимо, но и затрачивает больше вычислений для шифрования и дешифорования. Хороший пример этого - популярный подход к использованию тройного DES: шифрование выхода DES еще два раза используя в итоге разных ключа.
1.3 Существуют различные угрозы со стороны различных взломщиков
Угрозы безопасности исходят со многих сторон и их формы зависят от ресурсов нападающего. Хакеры - которые могут быть кем угодно, от студента до программиста - могут иметь доступ к майнфреймам или сотням рабочих станций. Те же лица могут отхотно покупать недорогие бывшие в употреблении платы, содержащие наборы программируемых чипов (НПЧ), которые чрезвычайно повышают результативность криптоаналитического усилия. Начинающая компания, или даже хорошо оснащенный индивидуум, могут позволить себе приобрести большое количество таких чипов. Крупные компании или организованные криминальные группировки с «серьезными деньгами» могут заказать компьютерный чип специально разработанный для шифрования. Разведслужбы, занятые в промышленном шпионаже, могут построить машину, состоящую из миллиона таких чипов.
1.4 Современные технологии дают сильное шифрование за туже цену, что и слабое
Особенность компьютерного шифрования в том, что малое увеличение стоимости вычислений может произвести огромное увеличение в безопасности. Очень стойкое шифрование сообщений (напр. с 128 - битовым ключом) обычно требует чуть больше вычислений, чем шифрование слабое (с 40-бтовыми ключами). Во многих приложениях криптография поглощает малую часть вычислительной мощности, по сравнению с такими процессами, как сжатие голоса или изображения, необходимые для подготовки материалов к шифрованию.
Одно из следствий такой единой цены состоит в том, что редко требуется ограничить определенным условием стойкость криптографии в зависимости от секретности информации. Даже если большинство информации в системе не является ни секретной ни финансово ценной, то нет практической или экономической причины для разработки аппаратуры или программ для обеспечения различных уровней шифрования для различных сообщений. Это простейший, наиболее осторожный (предусмотрительный) и т.о. фндаментально наиболее экономной, применить единый высокий уровень шифрования: сильное шифрование необходимо для любой информации, которая может быть сохранена или передана в защищенной системе.
2. Легкодоступные технолгии делают силовую атаку быстрой и дешевой
Особенности аппаратного обеспечения, используемого для проведения силовой атаки на шифровальный алгоритм зависят от количества криптоаналитических операций и свободных средств, доступных при нападении на предприятие. Ниже мы рассмотрим три главных класса, которые обычно применяются нападающими с различными ресурсами доступными им. криптоаналитические технологии, которые требуют больших начальных инвестиций, производят нижайшую цену за взломанный ключ, погашаемую за время износа аппаратуры.
Такова природа силовой атаки, которая может быть бесконечно распараллелена. Необходимо использовать так много машин, как это возможно, выделяя каждой свою часть работы. Время поиска сокращается вдвое, если вдвое увеличить объем оборудования. Общие затраты должны удвоиться, но если аппаратура постоянно используется для поиска ключей, цена взлома за один ключ не изменится.
На нижнем конце спектра находится использование неспециализированных персональных компьютеров или рабочих станций, запрограммированных для перебора ключей. Многие люди, благодаря обладанию или доступу к машинам, в состоянии использовать их ресурсы очнь дешево или бесплатно. Конечно, компьютеры общего назначения, нагруженные такими вспомогательными устройствами, как видеоконтроллеры, клавиатура, память и диски - делают поисковые вычисления дорогими. Следовательно, их будут применять только случайные лица, кто не может или не желает потратиться на более специализированное оборудование.
Более эффективный технолгический подход заключается в применении наборов программируемых чипов (НПЧ). НПЧ функционируют как программируемое аппаратное обеспечение и позволяют быстрее, чем обычные процессоры, выполнять такие задачи, как шифрование и дешифрование. НПЧ - обычный инструмент для вычислений, которые необходимо выполнить быстро, в реальном масштабе времени. НПЧ-технолгии быстрые и дешевые. Цена чипа АТ&Т ORCA, способного проверить 30 млн. ключей в секунду, составляет 200 долл. Это в 1000 раз быстрее, чем ПЭВМ, и, примерно, за 1/10 его цены. НПЧ легкодоступны, и установленные на плате могут применяться в стандартных ПЭВМ наподобие звуковых карт, модемов, или модулей памяти.
НПЧ-технологии оптимальны в том случае, когда один и тот же инструмент должен применяться для атаки различных криптосистем. Часто, как в с лучае с DES, криптосистема достаточно широко используется, чтобы оправдать применение более специализированных устройств. В этом случае более выгодна технология, требующая, однако, больших начальных вложений - использование специализированных интегральных схем (СИС). 10-долларовый чип способен проверить 200 млн. ключей в секунду, что еще в 7 раз быстрее и в 20 раз дешевле, чем НПЧ. Поскольку СИС требует гораздо больше инженерных усилий, чем НПЧ, и оправдывает инвестиции далеко не сразу, то этот подход доступен только серьезным, хорошо оснащенным организациям.
3. В действительности, 40-битовые ключи не обеспечивают защиты
Современная политика правительства США запрещает экспортировать программное обеспечение, включая шифрование по алгоритмам RC2, RC4 с 40-битовыми ключами. 40-битовый ключ означает, что существуют 240 возможных ключей. В среднем, для нахождения правильного ключа приблизительно половина из них должна быть перебрана. Экспорт других алгоритмов должен быть специально разрешен. Кто угодно, с современным компьютером и несколькими сотнями долларов способено взломать 40-битовое шифрование гораздо быстрее. Чип НПЧ - стоимостью около 400 долл. установленный на плате, сможет взломать 40-битовый ключ за 5 часов. Оценив работу НПЧ в течение трех лет для непрерывного поиска ключей, получим приблизительную оценку за ключ - 8 центов.
Более определенный коммерческий хищник, готовый потратить 10 000 долл. для установки 25 чипов ORCA, способен перебрать 40-битовые ключи в среднем за 12 минут, приблизительно по 8 центов за взломанный ключ. Затратив больше денег для покупки больше чипов укорачивает время соответственно 300 000 долл. - 24 сек., 10 000 000 долл - 0,7 сек.
Как уже отмечалось, корпорация с соответствующими ресурсами может заказать гораздо более быстрый чип. Сделав это, компания затратившая 300 000 долл должна найти правильный ключ приблизительно за 0,18 секунд, при цене 1/10 цента за решение; более крупная компания или правительственная агентство способное потратить 10 000 000 долл. должно найти правильный ключ приблизительно за 0,005 секунд (опять 1/10 цента за решение). Заметим, что цена за решение является константой, потому, что мы предположили константой цену чипа. В действительности увеличение объема закупки уменьшает среднюю цену чипа, т.к. стоимость разработки делится на большее число чипов.
4. Даже DES с 56-битовым ключом недостаточно сильный
4.1 DES уже не панацея
Стандарт шифрования данных DES был разработан в 1970 г. IBM и АНБ и одобрен Американским правительством в качестве федерального стандарта обработки информации. Он предназначен для сильного шифрования правительственной важной, но негрифованной информации. Многим было понятно, еще когда DES разрабатывался, что технологический прогресс сделает 56-битовые ключи DES уязвимыми, еще до конца текущего века.
Сегодня DES - может быть, наиболее широко распространенный шифровальный алгоритм и продолжает им быть. DES- шифрование еще сильно, но оно не панацея. Вычисления показывают, что DES недостаточно сильный, от корпоративной или правительственной атаки, поддержанной серьезными ресурсами. DES взломать легче, чем многие думают.
Как описно выше, 40-битовое шифрование не обеспечивает защиты даже от случайного взломщика с ограниченным временем и ленивой машиной, либо нежелающего потратить несколько сотен долларов. Против таких оппонентов DES сможет обеспечить существенную защиту. Потребуется 1,5 года для всякого, кто используя 10 000 долл. на НПЧ-технологии найдет ключ. За десять лет инвестиции этого размера позволят найти ключ менее, чем за неделю.
Реальная угроза коммерческим транзакциям и конфиденциальности в Интернете исходит от индивидуалов и организаций, желающих потратить значительное время и деньги. Поскольку все больше деловой и личной информации переводится в электронную форму, потенциальное вознаграждение коммерческому взломщику также увеличивается значительно и может оправдать затраты. Серьезная угроза - законный или незаконный бизнес сможет найти ключ приблизительноза 19 дней используя или за 3 часа с помощью заказного чипа. В последнем случае, это будет стоить примерно 38 долл. за ключ (из расчета 3 лет непрерывной работы). Правительство или бизнес способный затратить 10 млн. долл. на заказные чипы сможет вскрыть DES ключ приблизительно за 6 минут, при той же цене 38 долл. за ключ.
На самом верхнем конце, организации - преимущественно правительственные разведываетельные агентства - способные вложить 300 млн. долл. могут взломать DES за 12 секунд. Затраты огромные, но не запредельные для разведывательного сообщества. Это меньше, чем стоит построенный специально для поднятия одной руской подводной лодки «подводный исследователь», и намного меньше, чем цена разведывательных спутников. Такие деньги трудно оправдать атакой на одну цель, но, по-видимому, приемлемо против алгоримов типа DES, широко применяемых во всем мире.
Это достаточное доказательство опасности представляемой таким агентствами в поисках получения информации не только для военных целей но для коммерческий целей. Слушания в Конгрессе в 1993 высветили пример, в котором правительства Франции и Японии следили за бизнесом в своих собственных странах. Т.о. защита коммерческой информации от таких угроз это не гипотетическое предположение.
4.2 Анализ для других алгоритмов примерно одинаковых
Предыдущий анализ был сфокусирован на времени и деньгах, необходимых для дешифрования информации используя алгоритм RC4 с 40-битовым ключом или DES с 56-битовым ключом, но но результаты не были специфичными для каждого шифра. Хотя каждый алгоритм имеет свои особенности, усилия требуемые для нахождения ключа - сопоставимы. Возможны некоторые различия, но они не окажут значительный эффект на силовой взлом алгоритмов с примерно одинаковой длиной ключа.
Особенно это касается времени процедур установки, такие, как длительная установка ключа в RC4, результат в некоторых алгоритмах, имеющих существенно более длинный ключ, чем другие. Для целей нашего анализа такие факторы длина ключа изменяется не более, чем на 8 битов.
5. Соответствующая длина ключа на будущее - Предположения
Таблица 1 отражает стоимость силовой атаки против симметричной криптосистемы с 40-битовыми и 56-битовыми ключами, используя сети неспециализированных компьютеров, НПЧ и СИС технологии.

Таблица 1

Она показывает, что 56 бит обеспечивают степень защиты около 1,5 года - которая должна быть подходящим для многих коммерческих целей при оппоненте способнов вложить 10 000 долл. От оппонента, способного вложить 300 000 долл.период защиты сократится до малейшего минимума в 19 дней. Учитывая вышеизложенное, стойкость быстро падает до минимума. Очень большие, но близкие к реальным, инвестиции в соответствующие спецслужбы могут легко позволить ломать ключи в реальном времени.
Какая длина ключа требуется на сегодняшний день? Для инвестора, чей бюджет лежит в диапазоне от 10 до 300 млн. время требуемое для перебора ключей соответствующих 75 битам лежит между 6 годами и 70 днями. Хотя последняя цифра очень похожа на наименьший минимум в 19 дней, она соответствует цене в 19 млн. долл. и уровню взлома 5 ключей в год. Жертва такой атаки должна представлять собой лакомый кусочек.
Поскольку многие виды инфомации должны находиться в секрете долгий период времени, оценка не может быть ограничена защитой, требуемой сегодня. Также важно, что криптосистемы (особенно стандарты) часто предполагается использовать годы и даже десятилетия. DES, к примеру, использовался более 20 лет, и, возможно, будет использоваться еще. В частности, время жизни криптосистемы часто равно времени существования некоторого продукта, воплощающего ее.
Грубая прикидка минимальной стойкости, как функции времени, может быть получена эмпирическим путем, часто называемым «законом Мура», который гласит, что вычислительные мощности при одной и той же стоимости удваиваются каждые 18 месяцев. Возьмите вместе время жизни криптографического оборудования, время жизни секретов и, как мы полагаем благоразумно потребовать, что шифрованные данные должны быть в безопасности еще 20 лет. В этом случае закон Мура означает, что ключи должны быть приблизительно на 14 битов длинее, чем требуется для предотвращения атаки сегодня.
Необходимо помнить, что дополнительные вычислительные цены сильного шифрования скромные, поэтому мы очень рекомендуем минимальную длину ключа в 90 битов для симметричных систем.
Поучительно сравнить эти рекомендации с Федеральным стандартом обработки информации 46, DES, Федеральным стандартом обработки информации 185, Стандартом шифрования ЕЕS. DES был предложен 21 год назад и использует 56-битовый ключ. Применяя закон Мура и добавляя 14 битов получаем, что стойкость DES в том году, когда он был принят (1975 г.), сопоставима с 70-битовой системой сегодня. Подсчитано, что время в течение которого и что ключи могут быть перебраны в один день соответствуют инвестициям в 20 млн. долл. Наш 75-битовый расчет сегодня соответствует 61 биту в 1975 г., достаточно, чтобы вывести цену перебора ключей за достижимые пределы. EES пока неприемлем для многих потенциальных пользователей по многи причинам, воплощает понятие о соответствующей длине ключа, что похоже на наши. Он использует 80-битовые ключи, количество которых лежит между нашими значениями 75 и 90 битов.
Об авторах
Матт Блейз - старший исследователь в AT&T. Исследования в области компьютерной безопасности и криптографии. Недавно Блейз продемонстрировал слабость американской правительственной системы шифрования «Клиппер». В настоящее время он работает в области крупномасштабного управления доверием и приложений смарт-карт.
Уитфилд Диффи - заслуженный инженер в Sun Microsystems в области безопасности. В 1976 г. Диффи и Мартин Хеллман разработали криптографию с открытым ключом, которая решила проблемы обмена ключами по открытым каналам, создали базис для широкого применения шифрования в эпоху цифровой информации.
Рональд Райвест - профессор компьютерных наук Массачусетского Технологического института (МТИ) и заместитель директора Лаборатории Компьютерных наук МТИ. Райвест, совместно с Леонардом Эйдельманом и Эди Шамиром предложили криптосистему с открытым ключом, которая широко используется в индустрии. Рон Райвест - один из основателей компании RSA Data Security Inc. и разработчик серии алгоритмов шифрования с симметричным ключом различной длины (например RC4).
Брюс Шнейер - президент «Counterpane Systems» - консультационной фирмы специализирующейся в области криптографии и компьютерной безопасности. Шнейер много пишет и говорит о компьютерной защите и безопасности, он автор популярной книги «Прикладная криптография» и создатель симметричного алгоритма шифрования «Blowfish».
Цутоми Шимомура - специалист в вычислительной физике, работает в Суперкомпьютерном центре в Сан-Диего в качестве эксперта по созданию программных средств защиты. В прошлом году Шимомура организовывал операцию по поимке компьютерного нарушителя Кевина Митника, который воровал различную электронную информацию по всей стране.
Эрик Томсон - возглавляет криптоаналитическую команду корпорации «AccessData» («Доступ к данным») и популярный лектор по прикладной криптографии. Компания AccessData специализируется в области взлома данных и дешифрования информации методом «силовой атаки». Постоянными клиентами компании являются ФБР и другие правоохранительные органы и компании.
Майкл Винер - криптографический советник компании Bell-Northern Research, где он занимается криптоанализом, архитектурой безопасности и открытыми ключами. Под его влиянием 1993 газеты, эффективный поиск ключей DES, детальное описание машины для силовой атаки на DES-шифрованную информацию.
БЛАГОДАРНОСТИ
Авторы выражают свою признательность Ассоциации производителей программного обеспечения Business Software Alliance за ее поддержку в подготовке однодневного семинара прошедшего в Чикаго 20 ноября 1995 г.