методы защиты информации. безопасность баз анных. 1. Математические (криптографические) методы защиты информации (ммзи) элемент системы инженернотехнической защиты информации Вопрос История криптографии
 Скачать 0.5 Mb.
|
|
Тема 4. Криптографическая стойкость шифров Цель: Получить представление о криптографической стойкости шифров – основной характеристике данного математического преобразования, методах ее формирования, а также классификации криптоалгоритмов по различным критериям стойкости. Задачи: 1. Изучить: методические подходы к оценке криптостойкости шифров; проблемные вопросы, возникающие при генерации ключей и подготовке сообщений к шифрованию; практическую реализацию идеального (совершенного) способа шифрования. 2. Приобрести компетенции: анализа представленных на рынке криптоалгоритмов; выбора криптоалгоритмов по критерию «эффективность/стоимость». Содержание темы: 1. Криптографическая стойкость шифров. 2. Ненадежность ключей и сообщений. 3. Совершенные шифры. 4. Безусловно, стойкие и вычислительно стойкие шифры. Вопрос 1. Криптографическая стойкость шифров. Надежность или стойкость шифров определяется объемом работы криптоаналитика, необходимой для их вскрытия. Шифрсистема может служить объектом нападения противника, располагающего разного уровня интеллектуальным и вычислительным потенциалом. Нападающий может быть одиночкой хакером, имеющим персональный компьютер. Задача криптоанализа может интересовать некую фирму, обладающую солидным персоналом и оборудованием. Наконец, речь может идти о работе по добыванию информации мощной государственной организацией типа АНБ США. Возможности потенциального противника определяют требования, предъявляемые к надежности шифрования. Исходная информация и цели криптоаналитика могут быть разными. Несомненно, основная цель состоит в получении конфиденциальной информации. Целью нападения может служить также примененный секретный ключ, с помощью которого криптоаналитик может вскрывать другие криптограммы. Шифрсистема может быть надежно защищенной от одних угроз и быть уязвимой по отношению к другим. Попытки противника по добыванию зашифрованной информации называют криптоатаками. Шифры, используемые специальными службами, всемерно охраняются. Это обусловлено необходимостью дополнительного запаса прочности, поскольку до сих пор создание шифров с доказуемой стойкостью является очень сложной проблемой. Обоснование надежности шифрсистем осуществляется, как правило, теоретически и экспериментально при моделировании криптоатак с привлечением группы высококвалифицированных специалистов, которым предоставляются благоприятные условия для работы и необходимая техника. На государственном уровне гарантию надежности криптографической защиты дают уполномоченные для этой цели организации. Рассмотрение вопросов надежности шифрования невозможно без введения качественной и количественной мер. В криптографии рассматривают два подхода к стойкости — теоретическую стойкость и практическую (или вычислительную) стойкость. Но прежде рассмотрим основной элемент шифра – ключ. Вопрос 2. Ненадежность ключей и сообщений. Длина ключа почти ничего не определяет в безопасности. Внутри замка на входной двери вашего дома есть множество штырьков. Для каждого из них существуют различные возможные положения. Когда кто-то вставляет ключ в замочную скважину, все штырьки перемещаются в определенные позиции. Если положение, в которое ключ ставит штырьки, как раз то, которое необходимо, чтобы замок открылся, то он открывается. Если нет — не открывается. У замков, наиболее часто используемых в жилых домах, пять штырьков, каждый из которых может располагаться в одном из десяти различных положений. Это означает, что существует 100 000 возможных ключей. Взломщик с огромной связкой ключей может перебрать все ключи один за другим и, в конце концов, попасть внутрь. Ему лучше набраться терпения, поскольку если даже он тратит на один ключ 5 секунд, ему потребуется примерно 69 часов, чтобы найти подходящий ключ. Однако ни один взломщик не стал бы стоять перед вашей дверью 69 часов. Он, скорее всего, откроет замок отмычкой, просверлит его, вышибет дверь, разобьет окно или просто спрячется в кустах до тех пор, пока вы не отправитесь на прогулку. Замок с большим количеством штырьков и положений не обеспечит вашему дому большую безопасность, поскольку атака, которая таким образом затрудняется — перебором еще большего количества ключей — не та атака, о которой стоит задумываться особо. До тех пор пока количества штырьков достаточно, чтобы сделать недопустимой такую атаку, вам не следует о ней беспокоиться. То же самое справедливо для криптографических ключей. Если они достаточно длинные, то лобовые атаки просто лежат за пределами человеческих возможностей. Но здесь следует позаботиться о двух вещах. Во-первых, о качестве алгоритма шифрования, а во-вторых, о качестве ключа. Какой ключ является «достаточно длинным», зависит от обеих этих вещей. Но в первую очередь нужно разъяснить понятие энтропии. Энтропия — мера беспорядка или, более конкретно в контексте криптографии мера неопределенности. Чем больше неопределенность, тем больше энтропия. Например, случайно выбранный человек из обычной популяции является или мужчиной, или женщиной, в этом случае переменная «пол» составляет один бит энтропии. Если случайный человек сообщает, кто из четырех «Битлз» ему больше нравится, и все варианты равновероятны, этому соответствуют два бита энтропии. Пол члена женской олимпийской команды по бегу — это величина, у которой нет энтропии — они все женщины. Энтропия предпочтений одного из «Битлз» на собрании фан-клуба Джона Леннона существенно меньше двух битов, поскольку наиболее вероятно, что выбранный наугад человек предпочитает Джона. Чем больше определенность переменной, тем меньше энтропия. То же самое верно для криптографических ключей. То, что алгоритм использует 128-битовый ключ, не означает, что у него 128 бит энтропии для ключа. Или точнее, лучший способ сломать данную реализацию 128-битового алгоритма шифрования может состоять не в том, чтобы перебрать все ключи. «128 бит» — это просто мера максимального количества работы, которая потребуется, чтобы восстановить ключ; но про минимум ничего не сказано. Затем следует позаботиться о происхождении ключа. Все вычисления, касающиеся длины ключа, производились, исходя из предположения, что каждый ключ имеет при создании максимальную энтропию. Другими словами, все варианты ключа равновероятны, что генератор случайных чисел, создавший ключ, работает идеально. Это допущение не совсем верно. Многие ключи создаются на основе паролей и ключевых фраз. Система, принимающая пароль из 10 ASCII-символов, предоставляет для него 80 бит, но ее энтропия будет значительно меньше 80 бит. Некоторые символы ASCII никогда не появляются, а пароли, которые представляют собой реальные слова (или что-то похожее на слова), гораздо вероятнее, чем произвольные строки символов. Оценки энтропии для английского языка, меньшие 1,3 бит на символ; у пароля энтропия меньше, чем 4 бит на символ. Это значит, что пароль из 8 символов будет приблизительно соответствовать 32-битовому ключу, а если вы захотите 128-битовый ключ, вам нужен пароль из 98 символов (на базе английского алфавита). Видите ли, разумный взломщик не будет перебирать все возможные пароли по порядку. Он сначала испробует наиболее вероятные, а затем проверит остальные — в порядке убывания вероятности. Он проверит тривиальные пароли (типа «пароль» или «1234»), после этого — весь английский словарь, а затем различные заглавные буквы, цифры и т. п. Это называют словарной атакой. Второй предмет заботы — это качество алгоритма шифрования. Все предыдущие расчеты предполагали, что алгоритм получал ключи при помощи вычислений и использовал их совершенным образом. Если в алгоритме есть слабые места, доступные для атаки, это существенно снижает энтропию ключей. Например, алгоритм А5/1, используемый европейской сетью сотовых телефонов GSM, имеет 64-битовый ключ, но может быть взломан за время, требующееся для взлома 30-битового ключа при помощи атаки «в лоб». Это значит, что хотя у алгоритма имеется ключ с 64-битовой энтропией, он задействует для ключа только 30 бит энтропии. Вы можете с тем же успехом использовать хороший алгоритм с 30-битовым ключом. По этой причине проходит довольно много времени, прежде чем шифровальщики начинают доверять новому алгоритму. Когда кто-то предлагает новый алгоритм, у него есть определенная длина ключа. Но обеспечивает ли алгоритм реально ту энтропию, которая заявлена? Может потребоваться несколько лет анализа, прежде чем мы поверим, что он это делает. И даже тогда мы можем легко ошибиться: возможно, кто-то придумает новые математические подходы, которые понизят энтропию алгоритма и сломают его. Поэтому рекламу программ, в которых обещаются тысячебитовые ключи, трудно воспринимать серьезно — ее создатели не имеют понятия, как работают ключи и энтропия. Вопрос 3. Совершенные шифры. Рассмотрим идеальный способ шифрования. Он называется одноразовым блокнотом и был изобретен в 1917 году Мэйджором Джозефом Моборном ( Major Joseph Mauborgne) и Гилбертом Вернамом (Gilbert Vernam) из AT&T. В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и приклеенных к листу блокнота. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю 26 символа открытого текста и символа ключа из одноразового блокнота. Каждый символ ключа используется только единожды и для единственного сообщения. Отправитель шифрует сообщения и уничтожает использованные страницы блокнота или использованную часть ленты. Получатель, в свою очередь, используя точно такой же блокнот, дешифрирует каждый символ шифротекста. Расшифровав сообщение, получатель уничтожает соответствующие страницы блокнота или часть ленты. Новое сообщение - новые символы ключа. Например, если сообщением является: ONЕTIMHPAD а ключевая последовательность в блокноте: TBFRGKARFM то шифротекст будет выглядеть как: IPKLPSFHGQ так как Q + T mod 26 = I N + В mod 26 = Р Е + F mod 26 = К и т. д. Впредположении, что злоумышленник не сможет получить доступ к одноразовому блокноту, использованному для шифрования сообщения, эта схема совершенно безопасна. Данное шифрованное сообщение на вид соответствует любому открытому сообщению того же размера. Так как все ключевые последовательности совершенно одинаковы (помните, символы ключа генерируются случайным образом), у противника отсутствует информация, позволяющая подвергнуть шифротекст криптоанализу. Кусочек шифротекста может быть похож на: POYYAEAAZX, что дешифрируется как: SALMONEGGS или на: ВXНСIВMTVI, что дешифрируется как: GREENFLUID Повторю еще раз: так как все открытые тексты равновероятны, у криптоаналитика нет возможности определить, какой из открытых текстов является правильным. Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный шифротекст, и никакие вычислительные мощности не смогут это изменить. Необходимо напомнить, что символы ключа должны генерироваться случайным образом. Любые попытки вскрыть такую схему сталкиваются со способом, которым создается последовательность символов ключа. Использование генераторов псевдослучайных чисел не считается, у них всегда неслучайные свойства. Если вы используете действительно случайный источник - это намного труднее, чем кажется на первый взгляд,- это совершенно безопасно. Другой важный момент ключевую последовательность никогда нельзя использовать второй раз. Даже если вы используете блокнот размером в несколько гигабайт, то если криптоаналитик получит несколько текстов с перекрывающимися ключами, он сможет восстановить открытый текст. Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. Если шифротексты смещены правильно, соотношение совпадений резко возрастет - точное значение зависит от языка открытого текста. С этой точки зрения криптоанализ не представляет труда. Не используйте ключевую последовательность повторно. Идея одноразового блокнота легко расширяется на двоичные данные. Вместо одноразового блокнота, состоящего из букв, используется одноразовый блокнот из битов. Вместо сложения открытого текста с ключом одноразового блокнота используйте XOR. Для дешифрирования примените XOR к шифротексту с тем же одноразовым блокнотом. Все остальное не меняется, и безопасность остается такой же совершенной. Все это хорошо, но существует несколько проблем. Так как ключевые биты должны быть случайными и не могут использоваться снова, длина ключевой последовательности должна равняться длине сообщения. Одноразовый блокнот удобен для нескольких небольших сообщений, но его нельзя использовать для работы по каналу связи с пропускной способностью 1,544 Мбит/с. Вы можете хранить 650 Мбайт случайных данных на CD-ROM, но и тут есть проблемы. Во-первых, вам нужно только две копии случайных битов, но CD-ROM экономичны только при больших тиражах. И во-вторых, вам нужно уничтожать использованные биты. Для CD-ROM нет другой возможности удалить информацию кроме как физически разрушить весь диск. Гораздо больше подходит цифровая лента. Даже если проблемы распределения и хранения ключей решены, вам придется точно синхронизировать работу отправителя и получателя. Если получатель пропустит бит (или несколько бит пропадут при передаче), сообщение потеряет всякий смысл. С другой стороны, если несколько бит изменятся при передаче (и ни один бит не будет удален или добавлен - что гораздо больше похоже на влияние случайного шума), то лишь эти биты будут расшифрованы неправильно. Но одноразовый блокнот не обеспечивает проверку подлинности. Вопрос 4. Безусловно, стойкие и вычислительно стойкие шифры. При рассмотрении вопроса о теоретической стойкости шифров отвлекаются от реальных временных и стоимостных затрат по вскрытию шифра (что определяет подход к практической стойкости). Во главу угла ставится принципиальная возможность получения некоторой информации об открытом тексте или использованном ключе. Впервые такой подход исследовал К. Шеннон. Он рассматривал уже знакомую нам модель шифра и единственную криптоатаку на основе шифртекста. Проследим за его рассуждениями. Как мы указывали, конечной целью работы криптоаналитика является текст сообщения или ключ шифрования. Однако весьма полезной может быть даже некоторая вероятностная информация об открытом тексте. Например, уже предположение о том, что открытый текст написан по-английски, предоставляет криптоаналитику определенную априорную информацию об этом сообщении даже до того, как он увидит шифртекст. Так, например, он заранее знает, что слово "hello" является более вероятным началом сообщения, чем, скажем, набор букв "abcde". Поэтому первая цель криптоанализа состоит в том, чтобы увеличить количество этой априорной информации, относящейся к каждому возможному открытому тексту таким образом, чтобы истинный открытый текст сделать более вероятным после получения шифртекста, хотя, конечно, и не обязательно точным. Пусть, например, криптоаналитик перехватил текст "abccd" и знает (или предполагает), что он был зашифрован при помощи шифра простой замены. Этот шифртекст говорит ему о том, что открытый текст состоит из пяти букв, третья и четвертая из которых являются одинаковыми, а остальные отличными от этой буквы и разными. Хотя он не может быть уверенным, что этим словом является "hello" (это может быть еще "lessy" или что-то подобное), тем не менее апостериорные вероятности таких открытых текстов возрастают относительно их априорных вероятностей. Криптоаналитик, кроме того, полностью уверен (в предположении, что использовалась именно простая замена) в том, что этот открытый текст не может быть ни словом "after", ни словом "catch", и, таким образом, апостериорная вероятность обоих этих открытых априорных вероятностей. Шеннон назвал шифр совершенным, если для любого открытого текста знания, которые могут быть получены из соответствующего ему шифртекста, не раскрывают никакой информации об открытом тексте, за исключением, возможно, его длины. Другими словами, для совершенных шифров апостериорные вероятности открытых текстов (вычисленные после получения криптограммы) совпадают с их априорными вероятностями. Рассматривая практическую стойкость шифров предполагается, что для рассматриваемого шифра, обычно будет существовать единственное решение (х или к) криптограммы. Задача дешифрования и состоит в нахождении этого единственного решения, имеющего высокую вероятность (р(х/у) или р(к/у)). До того как объем перехвата достигнет расстояния единственности, задача состоит в нахождении всех решений, имеющих большую вероятность (по сравнению с остальными решениями), и, конечно, в определении вероятностей этих решений. Несмотря на то, что эти решения можно в принципе найти, поочередно перебирая, например, все ключи при расшифровании, для различных шифров нужно будет затратить для этого весьма различающиеся объемы работы. Средний объем работы W(N), необходимый для определения ключа по криптограмме, состоящей из N букв, измеренный в удобных элементарных операциях, К.Шеннон предложил назвать рабочей характеристикой шифра. Это среднее значение берется по всем сообщениям и всем ключам с соответствующими им вероятностями. Функция W(N) характеризует средние затраты (временные и материальные), необходимые для практического дешифрования криптограммы. Подобную характеристику можно рассматривать не только для одной конкретной криптоатаки, но и для других постановок задач криптоанализа простой замены, сопоставив ее с неопределенностью шифра по открытому тексту (как функцией длины сообщения). Наибольший интерес представляет предельное значение W(N) при N →∞ (то есть W(∞)), которое можно рассматривать как среднюю работу по дешифрованию при неограниченном объеме шифртекста. Практическое вычисление W(∞) представляет собой весьма сложную задачу. В связи с этим практическую стойкость шифра обычно оценивают с помощью величины W(∞), которую можно назвать достигнутой оценкой рабочей характеристики. Она определяется средней трудоемкостью наилучшего из известных методов вскрытия данного шифра. Если значение W(∞) вычисляет криптоаналитик, которому известны все имеющиеся в настоящее время методы анализа шифров, то полученная оценка практической стойкости шифра заслуживает доверия, особенно если вычисления сделаны с достаточным «запасом». Имеется в виду правильный выбор нижнего порога сложности выделяющий практически стойкие шифры. Большое значение имеет математическая модель вычислений, используемая при оценке практической стойкости шифра. По сути, речь идет о модели гипотетической ЭВМ, которой располагает потенциальный противник и которая способна реализовать крупный фрагмент алгоритма вскрытия как одну элементарную операцию. Например, опробование одного ключа и проверку результата расшифрования по критерию открытого текста Перечень литературы и Интернет-ресурсов: 1. А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. Основы криптографии: Учебное пособие. – М.: Гелиос АРВ, 2005. стр. 39-45. 2. В.М. Фомичев. Дискретная математика и криптология Курс лекций. – М.: ДИАЛОГ-МИФИ, 2003. стр. 121-128. 3. Шаньгин В.Ф. Защита компьютерной информации. Эффективные методы и средства. – М.: ДМК Пресс, 2008. стр. 131-140. 4. http://www.fstec.ru/ 5. http://www.cryptopro.ru/ |