Атаки на криптосистеме

Размещено на http://www.allbest.ru/

АТАКИ НА КРИПТОСИСТЕМЕ

Введение

Разные люди понимают под шифрованием разные вещи. Дети играют в игрушечные шифры и секретные языки. Это, однако, не имеет ничего общего с настоящей криптографией. Настоящая криптография (strong cryptography) должна обеспечивать такой уровень секретности, чтобы можно было надежно защитить критическую информацию от расшифровки крупными организациями - такими как мафия, транснациональные корпорации и крупные государства. Настоящая криптография в прошлом использовалась лишь в военных целях. Однако сейчас, с становлением информационного общества, она становится центральным инструментом для обеспечения конфиденциальности.

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

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

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

1. Основные понятия

В криптографической терминологии исходное послание именуют открытым текстом (plaintext или cleartext). Изменение исходного текста так, чтобы скрыть от прочих его содержание, называют шифрованием (encryption). Зашифрованное сообщение называют шифротекстом (ciphertext). Процесс, при котором из шифротекста извлекается открытый текст называют дешифровкой (decryption). Обычно в процессе шифровки и дешифровки используется некий ключ (key) и алгоритм обеспечивает, что дешифрование можно сделать лишь зная этот ключ.

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

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

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

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

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

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

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

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

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

2. Атаки на криптосистеме

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

2.1 Атаки на криптосистемы с секретным ключом

И так опишем сначала атаки на криптосистемы с секретным ключом:

Атака с известным шифртекстом (ciphertext-only attack). Самая слабая из всех возможных атак. Предполагается, что противник знает криптосистему, т. е., алгоритмы шифрования и дешифрования, но не знает секретный ключ. Кроме этого, ему известен лишь набор перехваченных криптограмм.

Атака с известным открытым текстом (known-plaintext attack). То же, что предыдущая, но противник получает в свое распоряжение еще некоторый набор криптограмм и соответствующих им открытых текстов.

Простая атака с выбором открытого текста (chosen-plaintext attack). Предполагается, что противник имеет возможность выбрать необходимое количество открытых текстов и получить их криптограммы. При этом все открытые тексты должны быть выбраны заранее, т. е., до получения первой криптограммы. В зарубежной литературе эту атаку часто называют "полуночной" атакой (midnight attack) или coffee-break attack, что соответствует реальной ситуации, когда персонал оставил устройство шифрования в рабочем состоянии и им временно завладел противник. Хотя секретный ключ ему недоступен, противник может зашифровать подготовленные им открытые тексты, что дает ему дополнительную информацию для нападения на криптосистему.

Адаптивная атака с выбором открытого текста. То же, что предыдущая, но, выбирая очередной открытый текст, противник уже знает криптограммы всех предыдущих.

Простая атака с выбором шифртекста (chosen-ciphertext attack). Противник имеет возможность выбрать необходимое количество криптограмм и получить соответствующие им открытые тексты. При этом все криптограммы должны быть выбраны заранее, т. е., до получения первого открытого текста.

Адаптивная атака с выбором шифртекста. То же, что предыдущая, но, выбирая очередную криптограмму, противник уже знает открытые тексты, соответствующие всем предыдущим.

Атака с выбором текста (chosen-text attack). Противник имеет возможность атаковать криптосистему "с обоих концов", т. е., выбирать как криптограммы (и дешифровать их), так и открытые тексты (и шифровать их). Атака с выбором текста может быть простой, адаптивной, а также простой "с одного конца" и адаптивной с другого.

Атаки перечислены в порядке возрастания их силы, т. е., атака с выбором текста является самой сильной из всех известных атак на криптосистемы.

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

Кроме того, существуют атаки, специфические для криптосистем с открытым ключом. Например, если число возможных открытых текстов невелико, то противник, зная открытый ключ, может заранее заготовить достаточное количество криптограмм и затем, сравнивая эти "заготовки" с перехваченными криптограммами, с высокой вероятностью получать соответствующие открытые тексты. Такая атака называется атакой с проверкой текста (verifiable-text attack). Заметим, что эта атака невозможна для криптосистем вероятностного шифрования.

2.2 Атаки на схемы электронной подписи

Приведем теперь классификацию типов атак на схемы электронной подписи, предложенная Гольдвассер, Микали и Ривестом [GMRiv]. Атаки перечисляются таким образом, что каждая последующая сильнее предыдущей:

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

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

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

Направленная атака с выбором сообщений. То же, что предыдущая, но противник, выбирая сообщения, уже знает открытый ключ.

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

2.3 Наиболее распространенные атаки

И все же наибольшую вероятность проявить себя имеют такие атаки:

Атака со знанием лишь шифрованного текста (ciphertext-only attack): Это ситуация, когда атакующий не знает ничего о содержании сообщения, и ему приходтся работать лишь с самим шифрованным текстом. На практике, часто можно сделать правдоподобные предположения о структуре текста, поскольку многие сообщения имеют стандартные заголовки. Даже обычные письма и документы начинаются с легко предсказумой информации. Также часто можно предположить, что некоторый блок информации содержит заданное слово.

Атака со знанием содержимого шифровки (known-plaintext attack): Атакующий знает или может угадать содержимое всего или части зашифрованного текста. Задача заключается в расшифровке остального сообщения. Это можно сделать либо путем вычисления ключа шифровки, либо минуя это.

Атака с заданным текстом (chosen-plaintext attack): Атакующий имеет возможнот получить шифрованный документ для любого нужного ему текста, но не знает ключа. Задачей является нахождение ключа. Некоторые методы шифрования и, в частности, RSA, весьма уязвимы для атак этого типа. При использовании таких алгоритмов надо тщательно следить, чтобы атакующий не мог зашифровать заданный им текст.

Атака с подставкой (Man-in-the-middle attack): Атака направлена на обмен шифрованными сообщениями и, в особенности, на протокол обмена ключами. Идея заключается в том, что когда две стороны обмениваются ключами для секретной коммуникации (например, используя шифр Диффи-Хелмана, Diffie-Hellman), противник внедряется между ними на линии обмена сообщениями. Далее противник выдает каждой стороне свои ключи. В результате, каждая из сторон будет иметь разные ключи, каждый из которых известен противнику. Теперь противник будет расшифровывать каждое сообщение своим ключом и затем зашифровывать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, в то время как на самом деле противник читает все сообщения. Одним из способов предотвратить такой тип атак заключается в том, что стороны при обмене ключами вычисляют криптографическую хэш-функцию значения протокола обмена (или по меньшей мере значения ключей), подписывают ее алгоритмом цифровой подписи и посылают подпись другой стороне. Получатель проверит подпись и то, что значение хэш-функции совпадает с вычисленным значением. Такой метод используется, в частности, в системе Фотурис (Photuris).

Атака с помощью таймера (timing attack): Этот новый тип атак основан на последовательном измерении времен, затрачиваемых на выполнение операции возведения в стенень по модулю целого числа. Ей подвержены по крайней мере следующие шифры: RSA, Диффи-Хеллман и метод эллиптических кривых. Дополнительную информацию смотрите в оригинальной статье и во множестве последовавших статей.

3. Типы угроз

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

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

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

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

3.1 Угрозы для схемы электронной подписи

Угрозами для схемы электронной подписи являются раскрытие схемы или подделка подписи. Гольдвассер, Микали и Ривест [GMRiv] уточняют понятие угрозы, определяя следующие (перечисленные в порядке ослабления) типы угроз.

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

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

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

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

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

криптография атака схема шифратор

4. Задача

Описать заданный алгоритм шифрования. Разработать структурную схему шифратора и блок-схему алгоритма. Привести пример шифрования сообщения из 20 символов русского алфавита без учета пробелов.

Используемый шифр: Биграмный шифр Плейфера.

4.1 Описание заданного алгоритма шифров

Базируется на методе многобуквенного шифрования, где элементом считается биграма (2 буквы). Основан на использовании буквенной матрицы (для русского алфавита удобно взять матрицу 4х8). Матрица строится на основе некоторого ключевого слова. Матрица заполняется слева направо, сверху вниз. Сначала записывается ключевое слово (причём повторяющиеся буквы пропускаются). Затем записывается весь оставшийся алфавит (опять же исключая те буквы, которые уже находятся в матрице). В результате построения будет получена буквенная матрица с неповторяющимися символами.

Так как число русских букв 33, а число клеток - 32, исключим из таблицы букву Ё.

Основные требования к открытому (исходному) тексту:

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

Шифрование каждой биграммы происходит по следующим правилам:

Если буквы биграммы попадают в одну и туже строчку матрицы, то каждую из них заменяем буквой следующую за ней (справа) в той же строке. (строку считаем цикличной).

Если буквы биграммы попадают в один и тот же столбец матрицы, то каждую из них заменяем буквой следующую за ней (вниз) в том же столбце (столбец считаем цикличным).

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

Дешифрование:

Аналогично правилам при шифровании:

Если буквы биграммы попадают в одну и туже строчку матрицы, то каждую из них заменяем предыдущей буквой (слева) в той же строке. (строку считаем цикличной).

Если буквы биграммы попадают в один и тот же столбец матрицы, то каждую из них заменяем предыдущей буквой (вверх) в том же столбце (столбец считаем цикличным).

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

4.2 Пример шифрования сообщения

Сообщение: нахождение ключа шифра

Ключ: столбец

Строим буквенную матрицу:

Разобьем сообщение на биграммы: на хо жд ен ие кл юч аш иф ра

Биграмма НА формирует прямоугольник, заменяем её на ЧТ.

Биграмма ХО формирует прямоугольник, заменяем её на ПЦ.

Биграмма ЖД находится в одной строке, заменяем её на ЗЁ .

Биграмма ЕН расположена в одном столбце, заменяем её на ТФ.

Биграмма ИЕ формирует прямоугольник, заменяем её на ЗЦ.

Биграмма КЛ формирует прямоугольник, заменяем её на ЁА .

Биграмма ЮЧ формирует прямоугольник, заменяем её на ЯХ.

Биграмма АШ формирует прямоугольник, заменяем её на СА.

Биграмма ИФ формирует прямоугольник, заменяем её на ЗХ.

Биграмма РА формирует прямоугольник, заменяем её на ЧЛ.

Получаем зашифрованный текст: ЧТ ПЦ ЗЁ ТФ ЗЦ ЁА ЯХ СА ЗХ ЧЛ

Таким образом сообщение (нахождение ключа шифра) преобразуется в (чтпцзётфзцёаяхсазхчл).

4.3 Блок-схема алгоритма

Рисунок 1 - Блок-схема алгоритма

4.4 Структурная схема шифратора

Рисунок 2 - Структурная схема шифратора

Размещено на Allbest.ru