Криптоанализ - Cryptanalysis

Из Википедии, бесплатной энциклопедии
Крупный план роторов шифровальной машины Фиалка

Криптоанализ (от греческого kryptós , «скрытый» и analýein , «анализировать») - это изучение анализа информационных систем с целью изучения скрытых аспектов систем. Криптоанализ используется для взлома систем криптографической безопасности и получения доступа к содержимому зашифрованных сообщений, даже если криптографический ключ неизвестен.

Помимо математического анализа криптографических алгоритмов, криптоанализ включает изучение атак по побочным каналам, которые не нацелены на слабые места в самих криптографических алгоритмах, а вместо этого используют недостатки в их реализации.

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

Обзор

Учитывая некоторые зашифрованные данные ( « зашифрованный текст » ), цель криптоаналитика - получить как можно больше информации об исходных незашифрованных данных ( « открытый текст » ).

Объем информации, доступной злоумышленнику

Атаки можно классифицировать в зависимости от того, какая информация доступна злоумышленнику. В качестве базовой отправной точки обычно предполагается, что для целей анализа известен общий алгоритм ; это максим Шеннона «враг знает систему» ​​- в свою очередь, эквивалент принципу Керкхоффа . На практике это разумное предположение - на протяжении всей истории существует бесчисленное множество примеров секретных алгоритмов, попадающих в более широкие знания, в том числе посредством шпионажа , предательства и обратной инженерии . (И иногда шифры были взломаны посредством чистой дедукции; например, немецкий шифр Лоренца и японский пурпурный код , а также множество классических схем):

Требуемые вычислительные ресурсы

Атаки также можно охарактеризовать по требуемым ресурсам. Эти ресурсы включают:

  • Время - количество этапов вычислений (например, тестовых шифров), которые необходимо выполнить.
  • Память - объем памяти, необходимый для выполнения атаки.
  • Данные - количество и тип открытых текстов и зашифрованных текстов, необходимых для конкретного подхода.

Иногда трудно точно предсказать эти количества, особенно когда атаку невозможно реализовать для тестирования. Но академические криптоаналитики обычно предоставляют по крайней мере примерный порядок сложности своих атак, говоря, например, «коллизии SHA-1 теперь 2 52 ».

Брюс Шнайер отмечает, что даже непрактичные с вычислительной точки зрения атаки можно считать взломами: «Взлом шифра просто означает обнаружение слабого места в шифре, которое можно использовать с меньшей сложностью, чем грубая сила. Неважно, что грубая сила может потребовать 2 128 шифров; атака, требующая 2 110 шифрований, будет считаться взломом ... Проще говоря, взлом может быть просто слабым местом сертификата: свидетельством того, что шифр не работает так, как заявлено ».

Частичные перерывы

Результаты криптоанализа также могут различаться по полезности. Например, криптограф Ларс Кнудсен (1998) классифицировал различные типы атак на блочные шифры в зависимости от количества и качества обнаруженной секретной информации:

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

Академические атаки часто направлены на ослабленные версии криптосистемы, такие как блочный шифр или хеш-функция с удаленными раундами. Многие, но не все атаки становятся экспоненциально сложнее выполнять по мере добавления раундов в криптосистему, поэтому полная криптосистема может быть сильной, даже если варианты с уменьшенным раундом слабые. Тем не менее, частичные взломы, близкие к взлому исходной криптосистемы, могут означать, что последует полный разрыв; всем успешным атакам на DES , MD5 и SHA-1 предшествовали атаки на ослабленные версии.

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

История

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

Классические шифры

Первая страница
рукописи
Аль-Кинди IX века по расшифровке криптографических сообщений

Хотя собственно слово « криптоанализ » появилось относительно недавно (оно было придумано Уильямом Фридманом в 1920 году), методы взлома кодов и шифров намного старше. Дэвид Кан отмечает в книге «Взломщики кодов», что арабские ученые были первыми, кто систематически документировал криптоаналитические методы.

Первое известное записанное объяснение криптоанализа было дано Аль-Кинди (ок. 801–873, также известным как «Алкиндус» в Европе), арабским эрудитом 9-го века в « Рисала фи Истихрадж аль-Муамма» ( Рукопись на Расшифровка криптографических сообщений ). В этом трактате содержится первое описание метода частотного анализа . Таким образом, Аль-Кинди считается первым в истории взломщиком кодов. На его прорывную работу оказал влияние Аль-Халил (717–786), написавший « Книгу криптографических сообщений» , в которой впервые используются перестановки и комбинации для перечисления всех возможных арабских слов с гласными и без них.

Частотный анализ - это основной инструмент для взлома большинства классических шифров . В естественных языках одни буквы алфавита встречаются чаще, чем другие; в английском языке « E », вероятно, будет самой распространенной буквой в любом образце открытого текста . Точно так же орграф «TH» - это наиболее вероятная пара букв в английском языке и так далее. Частотный анализ полагается на шифр, который не может скрыть эту статистику . Например, в простом шифре подстановки (где каждая буква просто заменяется другой) наиболее часто встречающаяся буква в зашифрованном тексте будет вероятным кандидатом на «E». Следовательно, частотный анализ такого шифра относительно прост при условии, что зашифрованный текст достаточно длинный, чтобы дать достаточно репрезентативное количество букв алфавита, которые он содержит.

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

В Европе итальянский ученый Джамбаттиста делла Порта (1535-1615) был автором основополагающей работы по криптоанализу De Furtivis Literarum Notis .

Успешный криптоанализ, несомненно, повлиял на историю; способность читать предположительно секретные мысли и планы других может быть решающим преимуществом. Например, в Англии в 1587 году, Мария Стюарт был осужден и казнен за измену в результате ее участия в трех участков с целью убийства Елизаветы I в Англии . Планы выяснились после того, как ее закодированная переписка с другими заговорщиками была расшифрована Томасом Фелиппесом .

В Европе в 15-16 веках идея полиалфавитного шифра замещения была разработана, в частности, французским дипломатом Блэзом де Виженером (1523–1596). В течение примерно трех столетий шифр Виженера , который использует повторяющийся ключ для выбора различных алфавитов шифрования по очереди , считался полностью безопасным ( le chiffre indéchiffrable - «неразборчивый шифр»). Тем не менее Чарльз Бэббидж (1791–1871), а позже независимо Фридрих Касиски (1805–81) сумели взломать этот шифр. Во время Первой мировой войны , авторы в ряде стран разработали роторные шифровальные машины , такие как Артур Шербиуса " Энигма , в попытке свести к минимуму повторения , которое было использовано для взлома системы Виженера.

Шифры Первой и Второй мировых войн

Расшифрованная Telegram Циммермана .

Во время Первой мировой войны нарушение Telegram Циммермана сыграло важную роль в вовлечении Соединенных Штатов в войну. В Второй мировой войне , что союзники выиграли огромную пользу от их совместного успеха криптоанализа немецких шифров - включая Энигмы и шифр Lorenz - и японские шифры, в частности , «Фиолетовые» и JN-25 . «Ультра» разведке приписывают все - от сокращения окончания европейской войны на срок до двух лет до определения конечного результата. Войне на Тихом океане также помогли «Мэджик» .

Криптоанализ вражеских сообщений сыграл значительную роль в победе союзников во Второй мировой войне. FW Винтерботы , цитируемые западный Верховный главнокомандующий ОВС НАТО, Дуайт Д. Эйзенхауэр , в конце войны, как описывающее Ультра интеллекта как были «решающим» для победы союзников. Сэр Гарри Хинсли , официальный историк британской разведки во Второй мировой войне, сделал аналогичную оценку в отношении Ultra, заявив, что это сократило войну «не менее чем на два года, а возможно, и на четыре года»; более того, он сказал, что без Ultra неясно, чем бы закончилась война.

На практике частотный анализ в такой же степени полагается на лингвистические знания, как и на статистику, но по мере того, как шифры стали более сложными, математика стала более важной в криптоанализе. Это изменение было особенно очевидно до и во время Второй мировой войны , когда попытки взломать шифры Оси потребовали нового уровня математической сложности. Более того, автоматизация была впервые применена к криптоанализу в ту эпоху с использованием польского устройства Bomba , британской Bombe , использования оборудования с перфокартами и компьютеров Colossus - первых электронных цифровых компьютеров, управляемых программой.

Индикатор

В случае взаимных машинных шифров, таких как шифр Лоренца и машина Enigma, использовавшаяся нацистской Германией во время Второй мировой войны , каждое сообщение имело свой собственный ключ. Обычно передающий оператор информирует принимающего оператора об этом ключе сообщения, передавая некоторый открытый текст и / или зашифрованный текст перед зашифрованным сообщением. Это называется индикатором , поскольку он указывает принимающему оператору, как настроить его машину на расшифровку сообщения.

Плохо спроектированные и реализованные системы индикаторов позволили сначала польским криптографам, а затем британским криптографам в Блетчли-парке взломать систему шифров Enigma. Подобные плохие индикаторные системы позволили британцам определить глубину, которая привела к диагностике системы шифров Lorenz SZ40 / 42 и всестороннему взлому ее сообщений без того, чтобы криптоаналитики увидели шифровальную машину.

Глубина

Отправка двух или более сообщений с одним и тем же ключом - небезопасный процесс. Криптоаналитику тогда говорят, что сообщения «глубокие». Это может быть обнаружено сообщениями, имеющими тот же индикатор, с помощью которого отправляющий оператор информирует принимающего оператора о начальных настройках генератора ключей для сообщения.

Как правило, криптоаналитик может извлечь выгоду из выстраивания идентичных операций шифрования среди набора сообщений. Например, шифр Вернама шифрует побитовое комбинирование открытого текста с длинным ключом с использованием оператора « исключающее ИЛИ », которое также известно как « сложение по модулю 2 » (обозначается знаком ⊕):

Открытый текст ⊕ Ключ = Шифрованный текст

Расшифровка объединяет те же ключевые биты с зашифрованным текстом для восстановления открытого текста:

Шифрованный текст ⊕ Ключ = Открытый текст

(В арифметике по модулю 2 сложение совпадает с вычитанием.) Когда два таких шифротекста выровнены по глубине, их объединение устраняет общий ключ, оставляя только комбинацию двух открытых текстов:

Зашифрованный текст1 ⊕ Зашифрованный текст2 = Открытый текст1 ⊕ Открытый текст2

Затем отдельные открытые тексты можно обработать лингвистически, пробуя возможные слова (или фразы), также известные как «шпаргалки», в различных местах; правильное предположение в сочетании с объединенным потоком открытого текста дает понятный текст из другого компонента открытого текста:

(Plaintext1 ⊕ Plaintext2) ⊕ Plaintext1 = Plaintext2

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

Открытый текст1 ⊕ Шифрованный текст1 = Ключ

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

Развитие современной криптографии

Правительства давно осознали потенциальные преимущества криптоанализа для разведки , как военной, так и дипломатической, и создали специализированные организации, занимающиеся взломом кодов и шифров других стран, например, GCHQ и NSA , организации, которые все еще очень активны сегодня.

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

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

Многие из криптосистем, предлагаемых сегодня сотнями коммерческих поставщиков, не могут быть взломаны никакими известными методами криптоанализа. Действительно, в таких системах даже атака по выбранному открытому тексту , в которой выбранный открытый текст сопоставляется с его зашифрованным текстом, не может дать ключ, который разблокирует другие сообщения. Таким образом, в некотором смысле криптоанализ мертв. Но это не конец истории. Криптоанализ может быть мертв, но, если смешать мои метафоры, есть несколько способов снять шкуру с кошки.

Кан далее упоминает возросшие возможности для перехвата, подслушивания , атак по побочным каналам и квантовые компьютеры как замену традиционным средствам криптоанализа. В 2010 году бывший технический директор АНБ Брайан Сноу сказал, что как академические, так и государственные криптографы «очень медленно продвигаются вперед в зрелой области».

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

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

Симметричные шифры

Асимметричные шифры

Асимметричная криптография (или криптография с открытым ключом ) - это криптография, основанная на использовании двух (математически связанных) ключей; один частный и один общедоступный. Такие шифры неизменно полагаются на «сложные» математические задачи как на основу своей безопасности, поэтому очевидной точкой атаки является разработка методов решения проблемы. Безопасность двухключевой криптографии зависит от математических вопросов, в отличие от одноключевой криптографии, которая обычно не зависит, и, наоборот, по-новому связывает криптоанализ с более широкими математическими исследованиями.

Асимметричные схемы разработаны с учетом (предполагаемой) сложности решения различных математических задач. Если можно найти улучшенный алгоритм для решения проблемы, то система ослабнет. Например, безопасность схемы обмена ключами Диффи – Хеллмана зависит от сложности вычисления дискретного логарифма . В 1983 году Дон Копперсмит нашел более быстрый способ нахождения дискретных логарифмов (в определенных группах) и, таким образом, потребовал от криптографов использовать более крупные группы (или группы разных типов). Безопасность RSA зависит (частично) от сложности целочисленной факторизации - прорыв в факторинге повлияет на безопасность RSA.

В 1980 году можно было разложить сложное 50-значное число на множители за счет 10 12 элементарных компьютерных операций. К 1984 году уровень техники в алгоритмах факторинга достиг уровня, когда 75-значное число могло быть разложено на 10 12 операций. Достижения в области вычислительной техники также означали, что операции можно было выполнять намного быстрее. Закон Мура предсказывает, что скорость компьютеров будет продолжать расти. Методы факторинга также могут продолжать действовать, но, скорее всего, будут зависеть от математической проницательности и творческого потенциала, ни одно из которых никогда не было предсказуемо. Были учтены 150-значные числа, которые когда-то использовались в RSA. Усилия были больше, чем указано выше, но были разумными на быстрых современных компьютерах. К началу 21 века 150-значные числа уже не считались достаточно большим размером ключа для RSA. Числа, состоящие из нескольких сотен цифр, по-прежнему считались слишком сложными для факторизации в 2005 году, хотя методы, вероятно, со временем будут совершенствоваться, требуя, чтобы размер ключа не отставал, или использовать другие методы, такие как криптография с эллиптической кривой .

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

Атака на криптографические хеш-системы

Атаки по побочным каналам

Приложения квантовых вычислений для криптоанализа

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

Используя алгоритм Гровера на квантовом компьютере, поиск ключей методом перебора может быть ускорен в квадратическом порядке. Однако этому можно было противодействовать, удвоив длину ключа.

Смотрите также

Исторические криптоаналитики

Рекомендации

Цитаты

Источники

дальнейшее чтение

внешняя ссылка