Статистический различитель и атака на основе подобранного открытого текста
По Шеннону шифр является совершенно стойким, если открытый и шифрованный тексты статистически независимы, то есть для любого открытого текста A и любой криптограммы Z выполняется
P(A)=P(A/Z), (*)
иначе говоря, распределение вероятностей на множестве открытых текстов после перехвата криптограммы Z не отличается от распределения вероятностей на множестве открытых текстов до получения перехваченной криптограммы Z
Можно ли тогда утверждать, что выполнение условия (*) автоматически влечёт неуязвимость шифра ко всем известным видам атак на основе подобранного открытого текста?
комментариев: 9796 документов: 488 редакций: 5664
Критерий Шеннона с трудом подходит для блочных щифров из-за конечности размера ключа и блока. Это вам не одноразовый блокнот всё-таки. Для блочного шифра критерий абсолютной стойкости — неразличимость от идеальной псевдослучайной перестановки.
Например DES проходит статистические тесты на случайных открытых текстах, но не стоек к дифференциальному анализу (с подобранным открытым текстом).
Вот ещё пример такого шифра E':
E'K (x || x' ) = EK (x) || EK(x ⊕ x')
Здесь блок исходного текста P разбивается на две части x и x', они шифруются стойким шифром E по формуле с ксором и объединением. Вся эта
махинацияоперация и есть шифр E'. Поскольку он остаётся перестановкой, то функцию шифрования E', составленную из стойкого шифра E, можно считать блочным шифром.Все статтесты на случайных P он (т.е. E') пройдёт (с погрешностью на атаки перебором по размеру ключа или блока). А вот если специально подобрать, что в P половины будут x = x' или x' = 0, то будет ой (в смысле совсем неидеальная PRP) ;-)
2 unknown: спасибо, вроде прояснилось. Тогда сразу другой вопрос возникает. В разделе FAQ-а Что такое модель идеального шифра?, в частности про PRP написано:
Означает ли это, что если в дизайне БШ используются S-блоки, то в случае, когда S-блоки секретны и являются частью ключевой информации (по аналогии с ГОСТ28147-89, где узлы замены могут являться частью ключа) RPR-таблица на каждом ключе своя по определению? Тогда получается, что такой БШ чисто теоретически должен удовлетворять модели идеального шифра и для проверки связи с любым открытым текстом достаточно тестирования на статистический различитель?
комментариев: 9796 документов: 488 редакций: 5664
Просто это наследие далёких времён, когда шифры использовали только милитазированные структуры, доказательная база при проектировании шифров была сравнительно ненадёжна, электронные шифровальные устройства были медленными и большими.
Поэтому сложный шифр и реализовать было сложно, а доверия даже к 128-битному ключу могло и не быть. Пользовались обычными 128-бит ключами, которые можно было легко менять (с клавиатуры, переключателей или доставая перфокарту из конверта). А для перестраховки использовали ещё и секретные S-блоки, как долговременную часть ключа. Их могли менять редко (раз в год) или по особым случаям и держать запечатанными в железе, подальше от операторов-шифровальщиков.
Секретные S-блоки не делают шифр идеальным в рамках ICM.
Сложностно-теоретическую концепцию случайных функций предложили Goldreich, Goldwasser и Micali в 1986 году — How to construct random functions. Journal of the ACM, Vol. 33, No. 4, 1986, pp. 210–217.
Затем M. Luby и C. Rackoff. опубликовли работу по псевдослучайным перестановкам: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput, Vol. 17, No. 2, April 1988.
M. Bellare, J. Kilian и P. Rogaway вероятно впервые предложили использовать эту теорию для теоретического моделирования блочных шифров в более практическом аспекте: The security of the cipher block chaining message authentication code. Journal of Computer and System Sciences, Vol. 61, No. 3, Dec 2000, pp. 362–399.
Сама модель идеального шифра действительно восходит к определениям Шеннона, почитать об этом можно например здесь:
The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function.
Пока в этом направлении не всё устоялось даже в области терминологии (у разных авторов могут быть разные определения, многое получило признание лет пять назад) и толковых книг вероятно нет. Читайте работы-первоисточники.
комментариев: 9796 документов: 488 редакций: 5664
Если у кого-то появляется интерес к теме, это уже хорошо.