Отличительная атака

Форма криптоанализа, которая позволяет злоумышленнику отличить зашифрованные данные от случайных данных.

В криптографии различительная атака — это любая форма криптоанализа данных, зашифрованных шифром, которая позволяет злоумышленнику отличить зашифрованные данные от случайных данных. ^[1] Современные симметричные шифры специально разработаны для защиты от такой атаки. ^[2] Другими словами, современные схемы шифрования представляют собой псевдослучайные перестановки и разработаны так, чтобы иметь неразличимость шифротекста . Если найден алгоритм, который может отличить вывод от случайного быстрее, чем поиск методом грубой силы , то это считается взломом шифра.

Похожая концепция — это атака с известным ключом , при которой злоумышленник знает ключ и может найти структурное свойство в шифре, где преобразование из открытого текста в зашифрованный текст не является случайным. ^[3]

Обзор

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

Пример

Пусть T — последовательность случайных битов, сгенерированная случайным оракулом, а S — последовательность, сгенерированная псевдослучайным генератором битов . Две стороны используют одну систему шифрования для шифрования сообщения M длины n как побитовое XOR M и следующих n бит T или S соответственно. Выход шифрования с использованием T действительно случаен. Теперь, если последовательность S нельзя отличить от T, выход шифрования с S также будет казаться случайным. Если последовательность S различима, то шифрование M с помощью S может раскрыть информацию о M.

Две системы S и T называются неразличимыми, если не существует алгоритма D, связанного либо с S, либо с T, способного решить, связан ли он с S или T.

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

Примеры

Классические примеры различающей атаки на популярный потоковый шифр были у Ицика Мантина и Ади Шамира , которые показали, что 2-й выходной байт RC4 был сильно смещен в сторону нуля. ^[4] В другом примере Соурадьюти Пол и Барт Пренил из COSIC показали, что значение XOR 1-го и 2-го выходов RC4 также неравномерно. Примечательно, что оба вышеуказанных теоретических смещения могут быть продемонстрированы с помощью компьютерного моделирования. ^[5]

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

Тест на случайность

Ссылки

^ Мейер, Вилли; Кунцли, Саймон (2005). «Distinguishing Attack on MAG» (PDF) . Проект потокового шифра ENCRYPT . eSTREAM . Получено 8 февраля 2013 г. .
^ Леонид Рейзин (2004). "Симметричная криптография" (PDF) . Конспект лекций для Бостонского университета CAS CS 538: Основы криптографии .
^ Елена Андреева; Андрей Богданов; Барт Меннинк (8 июля 2014 г.). К пониманию безопасности блочных шифров с известным ключом. FSE 2014.
^ Ицик Мантин и Ади Шамир , Практическая атака на вещание RC4. FSE 2001, стр. 152–164 (PS) Архивировано 12 июня 2011 г. на Wayback Machine .
^ Соурадьюти Пол и Барт Пренел , Анализ неслучайных предсказательных состояний генератора ключевого потока RC4. INDOCRYPT 2003, стр. 52–67 (PDF).

Внешние ссылки

Источник
Недифференцируемость

[MAG-1] Мейер, Вилли; Кунцли, Саймон (2005). «Distinguishing Attack on MAG» (PDF) . Проект потокового шифра ENCRYPT . eSTREAM . Получено 8 февраля 2013 г. .

[cs-538-2] Леонид Рейзин (2004). "Симметричная криптография" (PDF) . Конспект лекций для Бостонского университета CAS CS 538: Основы криптографии .

[3] Елена Андреева; Андрей Богданов; Барт Меннинк (8 июля 2014 г.). К пониманию безопасности блочных шифров с известным ключом. FSE 2014.

[4] Ицик Мантин и Ади Шамир , Практическая атака на вещание RC4. FSE 2001, стр. 152–164 (PS) Архивировано 12 июня 2011 г. на Wayback Machine .

[5] Соурадьюти Пол и Барт Пренел , Анализ неслучайных предсказательных состояний генератора ключевого потока RC4. INDOCRYPT 2003, стр. 52–67 (PDF).