id: Гость   вход   регистрация
текущее время 16:31 29/03/2024
Автор темы: Гость, тема открыта 01/12/2010 19:47 Печать
Категории: криптография, алгоритмы, симметричное шифрование, атаки
https://www.pgpru.com/Форум/Криптография/СтатистическийРазличительИАтакаНаОсновеПодобранногоОткрытогоТекста
создать
просмотр
ссылки

Статистический различитель и атака на основе подобранного открытого текста


По Шеннону шифр является совершенно стойким, если открытый и шифрованный тексты статистически независимы, то есть для любого открытого текста A и любой криптограммы Z выполняется
P(A)=P(A/Z), (*)
иначе говоря, распределение вероятностей на множестве открытых текстов после перехвата криптограммы Z не отличается от распределения вероятностей на множестве открытых текстов до получения перехваченной криптограммы Z

Можно ли тогда утверждать, что выполнение условия (*) автоматически влечёт неуязвимость шифра ко всем известным видам атак на основе подобранного открытого текста?

 
Комментарии
— Гость (02/12/2010 18:09)   <#>
Наверно надо уточнить, что речь идёт об симметричном блочном шифре (БШ). Если, допустим, некий симметричный алгоритм БШ успешно проходит статистические тесты типа NIST и DIEHARD, можно ли сказать, что этот БШ не подвержен атаке на основе подобранного открытого текста или нет? Подскажите кому не сложно, пока что-то не могу сам сообразить.
— unknown (02/12/2010 22:29, исправлен 02/12/2010 22:56)   профиль/связь   <#>
комментариев: 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) ;-)

— Гость (03/12/2010 16:56, исправлен 03/12/2010 20:27)   <#>

2 unknown: спасибо, вроде прояснилось. Тогда сразу другой вопрос возникает. В разделе FAQ-а Что такое модель идеального шифра?, в частности про PRP написано:

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

Означает ли это, что если в дизайне БШ используются S-блоки, то в случае, когда S-блоки секретны и являются частью ключевой информации (по аналогии с ГОСТ28147-89, где узлы замены могут являться частью ключа) RPR-таблица на каждом ключе своя по определению? Тогда получается, что такой БШ чисто теоретически должен удовлетворять модели идеального шифра и для проверки связи с любым открытым текстом достаточно тестирования на статистический различитель?

— Гость (04/12/2010 16:00)   <#>
Перепутал перестановки с подстановками, опять ничего не понятно. А где можно посмотреть какое-нибудь более-менее серьёзное теоретическое обоснование идеальной псевдослучайной перестановки и вообще модели идеального шифра?
— Гость (05/12/2010 18:37)   <#>
unknown, набирейте себе студентов пока не поздно. Смотрите, сколько талантов, подающих надежды!
— unknown (05/12/2010 18:56)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
В ГОСТ не меняются 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.

Пока в этом направлении не всё устоялось даже в области терминологии (у разных авторов могут быть разные определения, многое получило признание лет пять назад) и толковых книг вероятно нет. Читайте работы-первоисточники.
— unknown (05/12/2010 18:58)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664


Если у кого-то появляется интерес к теме, это уже хорошо.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3