Статистический различитель и атака на основе подобранного открытого текста
По Шеннону шифр является совершенно стойким, если открытый и шифрованный тексты статистически независимы, то есть для любого открытого текста A и любой криптограммы Z выполняется
P(A)=P(A/Z), (*)
иначе говоря, распределение вероятностей на множестве открытых текстов после перехвата криптограммы Z не отличается от распределения вероятностей на множестве открытых текстов до получения перехваченной криптограммы Z
Можно ли тогда утверждать, что выполнение условия (*) автоматически влечёт неуязвимость шифра ко всем известным видам атак на основе подобранного открытого текста?
Наверно надо уточнить, что речь идёт об симметричном блочном шифре (БШ). Если, допустим, некий симметричный алгоритм БШ успешно проходит статистические тесты типа NIST и DIEHARD, можно ли сказать, что этот БШ не подвержен атаке на основе подобранного открытого текста или нет? Подскажите кому не сложно, пока что-то не могу сам сообразить.
Критерий Шеннона с трудом подходит для блочных щифров из-за конечности размера ключа и блока. Это вам не одноразовый блокнот всё-таки. Для блочного шифра критерий абсолютной стойкости — неразличимость от идеальной псевдослучайной перестановки.
Например 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-а Что такое модель идеального шифра?[link1], в частности про PRP написано:
Означает ли это, что если в дизайне БШ используются S-блоки, то в случае, когда S-блоки секретны и являются частью ключевой информации (по аналогии с ГОСТ28147-89, где узлы замены могут являться частью ключа) RPR-таблица на каждом ключе своя по определению? Тогда получается, что такой БШ чисто теоретически должен удовлетворять модели идеального шифра и для проверки связи с любым открытым текстом достаточно тестирования на статистический различитель?
Перепутал перестановки с подстановками, опять ничего не понятно. А где можно посмотреть какое-нибудь более-менее серьёзное теоретическое обоснование идеальной псевдослучайной перестановки и вообще модели идеального шифра?
unknown, набирейте себе студентов пока не поздно. Смотрите, сколько талантов, подающих надежды!
В ГОСТ не меняются S-блоки при каждой смене ключа.
Просто это наследие далёких времён, когда шифры использовали только милитазированные структуры, доказательная база при проектировании шифров была сравнительно ненадёжна, электронные шифровальные устройства были медленными и большими.
Поэтому сложный шифр и реализовать было сложно, а доверия даже к 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[link2].
Пока в этом направлении не всё устоялось даже в области терминологии (у разных авторов могут быть разные определения, многое получило признание лет пять назад) и толковых книг вероятно нет. Читайте работы-первоисточники.
Если у кого-то появляется интерес к теме, это уже хорошо.