Отправитель и получатель. Сообщения и шифрование 16 глава

Кроме того, решето общего поля чисел становится все быстрее и быстрее. Математики изобретают новые трюки, оптимизации, методы, и нет причин считать, что эта тенденция оборвется. Близкий алгоритм, решето специального поля чисел, уже может разлагать на множители числа определенной специализированной формы - обычно не используемые в криптографии - гораздо быстрее, чем решето общего поля чисел может разложить на множители любые числа того же размера. Разумно предположить, что решето общего поля чисел может быть оптимизировано, чтобы достичь такой же скорости [1190], возможно, что NSA уже знает, как это сделать. В Табл. -5 показано количество mips-лет, требуемое для разложения чисел различной длины при помощи решета специального поля чисел [1190].

Табл. -5.
Разложение на множители с помощью решета специального поля чисел

В 1991 году участники семинара Европейского института безопасности систем (European Institute for System Security) согласились, что 1024-битовых модулей будет достаточно для длительного хранения секретов до 2002 года [150]. Однако, они предупреждали: "Хотя участники этого семинара являются лучшими специалистами в соответствующих областях, это заявление (по поводу срока безопасности) должно быть воспринято с осторожностью." Это хороший совет.

Умный криптограф сверхконсервативен при выборе длин открытых ключей. Чтобы понять, насколько длинный ключ вам нужен, вам придется оценить нужную безопасность и время жизни ключа, не забывая о текущем состоянии искусства разлагать на множители. Чтобы получить тот же уровень безопасности, который давало 512-битовое число в начале восьмидесятых, сегодня вам понадобится 1024-битовое число. Если же вы хотите, чтобы ваши ключи оставались безопасными в ближайшие 20 лет, 1024-битовое число, по видимому, слишком коротко.

Даже если ваши конкретные секреты не стоят усилий, нужных для разложения вашего модуля, вы можете оказаться в опасности. Представьте себе автоматическую банковскую систему, использующую для безопасности RSA. Мэллори может предстать перед судом и заявить: "Читали ли вы в газете за 1994 год, что RSA-129 был взломан, и что 512-битовые числа могут быть разложены на множители любой организацией, которая может потратить несколько миллионов долларов и подождать несколько месяцев? Мой банк использует для безопасности 512-битовые числа и, между прочим, эти семь изъятий сделаны не мной." Даже если Мэллори лжет, судья, вероятно, может потребовать, чтобы банк это доказал.

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

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

Вот некоторые соображения из [66]:

Мы считаем, что сможем получить доступ к 100 тысячам компьютеров без сверхчеловеческих усилий и неэтичных действий. То есть, мы не собираемся выпускать в Internet "червя" или разрабатывать вирус, который бы предоставил бы нам вычислительные ресурсы. Во многих организациях многие тысячи машин подключены к сети. Доступ к их возможностям потребует искусной дипломатии, но не является невозможным. Приняв среднюю производительность машины равной 5 mips и время работы 1 год, вполне возможно осуществить проект, который требует полмиллиона mips-лет.

Проект разложения на множители 129-разрядного числа без значительных усилий смог задействовать 0.03 процента оценочной полной вычислительной мощности Internet [1190]. Разумно предположить, что хорошо разрекламированный проект получит на год 2 процента всемирной вычислительной мощности.

Предположим, что увлеченный криптоаналитик сможет получить в свое распоряжение 10000 mips-лет, большая корпорация - 10⁷ mips-лет, а правительство большой страны - 10⁹ mips-лет. Предположим также, что вычислительная мощь будет возрастать на порядок каждые пять лет. И , наконец, предположим также, что успехи в математике разложения на множители позволят нам раскладывать любые числа со скоростью, сравнимой с той, которую обеспечивает решето специального поля чисел. (Это пока невозможно, но прорыв может случиться в любой момент.) Табл. -6 рекомендует для различных лет использовать с целью обеспечения безопасности различные длины ключей.

Табл. -6.
Рекомендованные длины открытых ключей в (битах)

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

Предсказывать более далекое будущее еще глупее. Кто может знать, каких успехов к 2020 году достигнет вычислительная техника, сетевые вычисления и математика? Однако, если окинуть взглядом всю картину, можно заметить, что в каждом следующем десятилетии мы получаем возможность разлагать на множители вдвое более длинные числа, чем в предыдущем. Это позволяет построить Табл. -7.

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

Не все согласятся с моими рекомендациями. NSA установило для своего Стандарта цифровой подписи (Digital Signature Standard, см. раздел 20.1) длину ключей от 512 до 1024 бит - намного меньше, чем я рекомендую для длительной безопасности. У Pretty Good Privacy ("Вполне надежный секрет", см. раздел 24.12) максимальная длина ключа RSA составляет 2047 бит. Аржан Ленстра, лучший в мире раскладыватель на множители, в течение последних 10 лет отказывается делать предсказания [949]. В Табл. -8 приведены рекомендации Рона Ривеста для длины ключей, которые сделаны в 1990 году и кажутся мне слишком оптимистичными [1323]. Хотя его анализ на бумаге выглядит хорошо, в недавней истории можно найти примеры регулярно происходящих сюрпризов. Чтобы предохранить себя от последствия этих сюрпризов, есть смысл выбирать ключи с запасом.

Табл. -7.
Долгосрочный прогноз разложения на множители

Минимальные оценки предполагают бюджет $25000, алгоритм "квадратичное решето " и скорость технического прогресса 20 процентов в год. Средние оценки предполагают бюджет 25 миллионов долларов, алгоритм "решето общего поля чисел" и скорость технического прогресса 33 процента в год. Максимальные оценки предполагают бюджет 25 миллиардов долларов, алгоритм "решето общего поля чисел", работающий со скоростью решета специального поля чисел и скорость технического прогресса 45 процентов в год.

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

Табл. -8.
Оптимистичные рекомендации Ривеста для длины ключей (в битах)

Вычисление с помощью ДНК

Это похоже на волшебство. В 1994 году Леонард Эдлман (Leonard M. Adleman) продемонстрировал метод решения задачи NP-полноты(см. раздел 11.2) в биохимической лаборатории, используя молекулы ДНК для представления возможных решений задачи [17]. Задача, решенная Эдлманом, была частным случаем задачи направленного гамильтонова пути: дана карта городов, соединенных однонаправленными дорогами, нужно найти путь из города A в город Z, который проходит через каждый город на карте только один раз. Каждый город был представлен своей случайной цепочкой ДНК с 20 основаниями. С помощью обычных методов молекулярной биологии Эдлман синтезировал 50 пикомолей (30 миллионов миллионов молекул) цепочки ДНК, представляющей каждый город. Каждая дорога была представлена цепочкой ДНК с 20 основаниями, но эти цепочки выбирались не случайным образом: они умело выбирались так, чтобы "начало" цепочки ДНК, представляющей дорогу от города P к городу K ("Дорога PK") стремилась бы соединиться со цепочкой ДНК, представляющей город P, а конец Дороги PK стремился бы соединиться с городом K.

Эдлман синтезировал 50 пикомолей ДНК, представляющих каждую дорогу, смешал их вместе с ДНК городами, представляющей города, и добавил фермент лигазу, которая связывает вместе концы молекул ДНК. Правильно подобранная связь между цепочками ДНК для дорог и цепочками ДНК для городов приводит к тому, что лигаза соединяет цепочки ДНК для дорог вместе правильным образом. То есть, "Выход" дороги PK всегда будет соединен со "входом" какой-либо дороги, начинающейся в городе K, но никогда с "выходом" любой дороги или со "входом" дороги, которая начинается не в городе K. После тщательно ограниченного времени реакции лигаза создала большое количество цепочек ДНК, представляющих возможные, но все равно случайные объединения путей карты.

В этом супе из случайных путей Эдлман может найти малейший след - может быть единственной молекулы - ДНК, которая является ответом задачи. Используя обычные методы молекулярной биологии, он удалил все цепочки ДНК, представлявшие слишком короткие или слишком длинные пути. (Число дорог в нужном пути должно равняться числу городов минус один.) Затем он удалил все цепочки ДНК, которые не проходили через город A, затем те, которые шли мимо города B, и так далее. Молекула ДНК, прошедшая через это сито, и представляет собой нужную последовательность дорог, являясь решением задачи направленного гамильтонова пути.

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

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

Квантовые вычисления

А теперь еще большая фантастика. В основе квантовых вычислений используется двойственная природа материи (и волна, и частица). Фотон может одновременно находиться в большом количестве состояний. Классическим примером является то, что фотон ведет себя как волна, встречая частично прозрачное зеркало. Он одновременно и отражается и проходит через зеркало подобно тому, как морская волна, ударяясь о волнолом с небольшим отверстием в нем, одновременно отразится от стены и пройдет сквозь нее. Однако, при измерении фотон ведет себя подобно частице, и только одно состояние может быть обнаружено.

В [1443] Питер Шор (Peter Shor) очертил принципы построения машины для разложения на множители, основанной на законах квантовой механики. В отличие от обычного компьютера, который можно представить как машину, имеющее в каждый момент времени единственное фиксированное состояние, квантовый компьютер обладает внутренней волновой функцией, являющейся суперпозицией комбинаций возможных основных состояний. Вычисления преобразуют волновую функцию, меняя весь набор состояний единым действием. Таким образом, квантовый компьютер имеет преимущество над классическим конечным автоматом: он использует квантовые свойства для числа разложения на множители за полиномиальное время, теоретически позволяя взломать криптосистемы, основанные на разложении на множители или задаче дискретного логарифма.

Общепризнанно, что квантовый компьютер не противоречит фундаментальным законам квантовой механики. Однако, непохоже, что квантовая машина для разложения на множители будет построена в обозримом будущем ... если вообще будет построена. Одним из главных препятствий является проблема некогерентности, которая является причиной потери отчетливости волновыми огибающими и приводит к сбою компьютера. Из-за некогерентности квантовый компьютер, работающий при 1К, будет сбиваться каждую наносекунду. Кроме того, для построения квантового устройства для разложения на множители потребуется огромное количество вентилей, а это может не дать построить машину. Для проекта Шора нужно совершенное устройство для возведения в степень. Внутренние часы не используются, поэтому для разложения на множители криптографически значимых чисел могут потребоваться миллионы или, возможно, миллиарды индивидуальных вентилей. Если минимальная вероятность отказа каждого из nквантовых вентилей равна p, то среднее количество испытаний, необходимое для достижения успеха, составит (1/(1-p))ⁿ. Число нужных вентилей, по видимому, растет полиномиально с ростом длины числа (в битах), поэтому число требуемых попыток будет расти с увеличением длины используемых чисел сверхэкспоненциально - хуже чем при разложении делением!

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

7.3 Сравнение длин симметричных и открытых ключей

Система взламывается обычно в ее слабейшем месте. Если вы проектируете систему, которая использует и симметричную криптографию, и криптографию с открытыми ключами, то длины ключей для криптографии каждого типа должны выбираться так, чтобы вскрыть любой из компонентов системы было одинаково трудно. Бессмысленно использовать симметричный алгоритм со 128-битовым ключом вместе с алгоритмом с открытыми ключами, использующим 386-битовый ключ. Точно так же бессмысленно использовать в одной системе симметричный алгоритм с 56-битовым ключом и алгоритм с открытыми ключами, применяющий 1024-битовый ключ.

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

Табл. -9.
Длины симметричных и открытых ключей с аналогичной устойчивостью к вскрытию грубой силой

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

7.4 Вскрытие в день рождения против однонаправленных хэш-функций

Существует два способа вскрытия однонаправленных хэш-функций грубой силой. Первый наиболее очевиден: дано значение хэш-функции сообщения, Н(M), врагу хотелось бы суметь создать другой документ, М', такой, что Н(M')=Н(M). Второй способ более тонок: врагу хотелось бы найти два случайных сообщения, Mи М', таких, что Н(M')=Н(M). Такой способ называется столкновениеми является более простым, чем первый, способом вскрытия.

Парадокс дня рождения является стандартной статистической проблемой. Сколько человек должно собраться в одной комнате, чтобы с вероятностью 1/2 хотя бы у кого-нибудь из них был бы общий с вами день рождения? Ответ - 183. Хорошо, а сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был бы общий день рождения? Ответ удивителен - 23. 23 человека, находящихся в комнате, образуют 253 различных пары.

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

Предположим, что однонаправленная хэш-функция безопасна, и лучшим способом ее вскрытия является вскрытие грубой силой. Результатом функции является m-битовое число. Поиск сообщения, хэш-значение которого совпадает с заданным, в среднем потребовал бы хэширования 2^m случайных сообщений. А для обнаружения двух сообщений с одинаковым хэш-значением потребуется только 2^m/2 случайных сообщений. Компьютеру, который хэширует миллион сообщений в секунду, потребовалось бы 600000 лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значением. Тот же компьютер сможет найти пару сообщений с общим хэш-значением примерно за час

Это значит, что, если вы опасаетесь вскрытия в день рождения, вы должны выбирать длину хэш-значения в два раза длиннее, чем вам потребовалось бы в противном случае. Например, если вы хотите уменьшить вероятность взлома вашей системы до 1 шанса из 2⁸⁰, используйте 160-битовую однонаправленную хэш-функцию.

7.5 Каков должны быть длина ключа?

На этот вопрос нет единого ответа, ответ этот зависит от ситуации. Чтобы понять, какая степень безопасности вам нужна, вы должны задать себе несколько вопросов. Сколько стоит ваша информация? Как долго она должна безопасно храниться? Каковы ресурсы ваших врагов?

Список клиентов может стоить $1000. Финансовая информация при неожиданном разводе могла бы стоить $10000. Реклама и данные маркетинга для большой корпорации могли бы стоить 1 миллион долларов. Главный ключ для системы электронных наличных может стоить миллиарды.

В мире торговли предметами потребления секреты должны только сохраняться в течение нескольких минут. В газетном бизнесе сегодняшние секреты - это завтрашние заголовки. Информация о разработке какого-то продукта, возможно, должна будет храниться в секрете в течение года или двух Изделия(программы) могла бы была бы должна остаться секретом в течение года или два. Данные переписи США в соответствии с законом должны храниться в секрете в течение 100 лет.

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

В этих терминах даже можно определить требования к безопасности Можно. Например:

Длина ключа должна быть такой, чтобы взломщик, готовый потратить 100 миллионов долларов, мог взломать систему в течение года с вероятностью не более, чем 1/2³², даже с учетом скорости технического прогресса 30 процентов в год.

В Табл. -10, частично взятой из [150], приведены оценки требований к безопасности для различной информации:

Будущую вычислительную мощь оценить нелегко, но вот разумное эмпирическое правило: эффективность вычислительных средств удваивается каждые 18 месяцев и возрастает на порядок каждые 5 лет. Следовательно, через 50 лет самые быстрые компьютеры будут в 10 миллиардов быстрее, чем сегодня! Кроме того, не забывайте, что эти числа относятся только к универсальным компьютерам, кто знает, какие специализированные устройства для вскрытия криптосистем будут разработаны в следующие 50 лет?

Предполагая, что криптографический алгоритм будет использоваться в ближайшие 30 лет, вы можете представить себе, насколько он должен быть безопасен. Алгоритм, созданный сегодня, возможно не станет широко использоваться до 2000 года, и все еще будет использоваться в 2025 для шифрования сообщений, которые должны оставаться в секрете до 2075 года и позже.

Табл. -10.
Требования к безопасности различной информации

7.6 Caveat emptor[1]

Вся эта глава - просто много чепухи. This entire chapter is a whole lot of nonsense. Смешно говорить даже о самом понятии предсказания вычислительной мощи на 10, а тем более на 50 лет вперед. Эти расчеты приведены только для ориентировки, ни для чего больше. Экстраполируя прошлое, мы получаем будущее, которое, возможно, будет иметь мало общего с грядущей реальностью.

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

8 Управление ключами

У Алисы и Боба есть безопасная система связи. Они играют в мысленный покер, одновременно подписывают контракты и даже меняют цифровые наличные. Их протоколы безопасны. Их алгоритмы -самые лучшие. К несчастью, они покупают свои ключи от "Keys-R-Us" Евы, чей лозунг - "Вы можете доверять нам: Безопасность - среднее имя человека, которого туристический агент нашей бывшей тещи встретил в "Kwik-E-Mart".

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

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

Криптоаналитики часто вскрывают и симметричные криптосистемы, и криптосистемы с открытыми ключами через распределение ключей. Зачем Еве беспокоиться об проблеме вскрытия криптографического алгоритма целиком, если она может восстановить ключ из-за неаккуратного хранения ключа? Зачем ей тратить 10 миллионов долларов на создание машина для криптоанализа, если она может подкупить клерка за 1000 долларов? Миллион долларов за клерка связи на хорошем месте в дипломатическом посольстве может быть выгодной сделкой. Уолкеры годами продавали Советам ключи шифрования ВМС США. Руководитель контрразведки ЦРУ стоил меньше 2 миллионов долларов, включая жену. Это намного дешевле, чем строить огромные машины вскрытия и нанимать блестящих криптоаналитиков. Ева может выкрасть ключи. Она может арестовать или похищать кого-то, кто знает ключи. Она может совращать кого-то и получать ключи таким образом. (Морские пехотинцы, охранявшие посольство США в Москве не устояли перед подобной атакой.) Намного проще находить дефекты в людях, чем в криптосистемах.

Алиса и Боб должны защищать и свой ключ, и в той степени шифруемые им данные. Если ключ не изменять регулярно, то количество данных может быть огромно. К сожалению, многие коммерческие продукты просто объявляют "Мы используем DES" и забывают обо всем остальном. Результаты не слишком впечатляют.

Например, программа DiskLock для Macintosh (версия 2.l), продававшаяся в большинстве магазинов программного обеспечения, претендует на безопасное шифрование DES. Она шифрует файлы, используя DES. Реализация DES алгоритма правильна. Однако, DiskLock сохраняет ключ DES вместе с зашифрованным файлом. Если вы знаете, где искать ключ, и хотеть прочитать файл, шифрованный DiskLock с помощью DES, восстановите ключ из шифрованного файла и затем расшифровывать файл. Не имеет значение, что программа использует шифрование DES - реализация абсолютно небезопасна.

Дальнейшую информацию относительно управления ключами можно найти в [457, 98, 1273, 1225, 775, 357]. В следующих разделах обсуждаются некоторые из вопросов и решений.

8.1 Генерация ключей

The security of an algorithm rests in the key. If you're using a cryptographically weak process to generate keys, then your whole system is weak. Eve need not cryptanalyze your encryption algorithm; she can cryptanalyze your key generation algorithm.

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

Уменьшенные пространства ключей

DES использует 56-битовый ключ с битами. Любая правильно заданная 56-битовая строка может быть ключом, существует 2⁵⁶ (10¹⁶) возможных ключей. Norton Discreet for MS-DOS (версии 8.0 и более ранние) разрешает пользоваться только ключам ASCII, делая старший бит каждого байта нолем. Программа также преобразует символы нижнего регистра в верхний регистр (так что пятый бит каждого байта всегда противоположен шестому бита) и игнорирует бит младшего разряда каждого байта, что приводит к пространству в 2⁴⁰ возможных ключей. Эти ущербные процедуры генерации ключей сделали свою реализацию DES в десять тысяч раз проще для вскрытия.

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

Могут быть использованы для вскрытия грубой силой любые специализированные аппаратные и параллельные реализации. При проверке миллиона ключей в секунду (одной машиной или несколькими параллельно) физически возможно расколоть ключи из символов нижнего регистра и ключи из цифр и символов нижнего регистра длиной до 8 байтов, алфавитно-цифровые ключи - длиной до 7 байтов, ключи из печатаемых символов и ASCII-символов - длиной до 6 байтов, в ключи из 8-битовых ASCII-символов - длиной до 5 байтов.

Табл-1.
Количество возможных ключей в различных пространствах ключей

Табл. -2.
Время исчерпывающего поиска различных пространства ключей (при одном миллионе проверок в секунду)