Complexity estimation for a differential attack on a block cipher with given parameters.pdf Дифференциальный криптоанализ [1] является распространенным подходом к построениюатак на блочные шифры. Однако, как было замечено в [2], большинствосуществующих на сегодняшний день результатов криптоанализа блочных шифровпредставляют собой конкретные атаки на конкретные шифры. В работе [2] частичновосполняется данный пробел. В предположении, что ключ является аддитивным,описывается дифференциальная атака в общем виде и сводится к решению системыуравнений.В настоящей работе акцент делается на то, что в ряде случаев дифференциальнаяатака не является детерминированной, то есть она имеет вероятность успеха и неудачи.Под успехом понимается тот факт, что, отработав, атака на выходе даст верныйискомый ключ. В частности, в работах, посвященных дифференциальному криптоанализушифров MARS и CAST-256, описывались атаки, для которых подсчитывалисьвероятности успеха [3, 4].Схемы этих атак похожи, различие заключается по сути только в дифференциальныххарактеристиках, на основании которых атаки строятся. В связи с этим возникаетидея описать алгоритм в общем виде в зависимости от различных параметров блочногошифра и тем самым позволить криптоаналитику построить дифференциальнуюхарактеристику и автоматически получить вероятность успеха и сложность атаки, основаннойна этой характеристике. Таким образом, криптоаналитик сфокусируется наспецифических свойствах шифра, не отвлекаясь на построение атаки. В настоящейработе реализуется эта идея и рассчитывается сложность атаки при различных параметрахблочного шифра с целью достичь вероятности успеха не менее 99 %.Дифференциальная атака в общем видеПусть имеется дифференциальная характеристика с разностью входных блоковAinp и разностью выходных блоков Aout. Атака, направленная на отыскание подключапоследнего раунда и основанная на данной характеристике, выглядит так:1. Сформировать G групп различных пар блоков Ag, Bg (g = 1,..., G; t = 1,..., T )с разностью A inp.2. Для каждой из пар (Ag, Bg) запросить пару шифртекстов X g = Cipher(Ag) иYg = Cipher(Bg), полученные G T пар шифртекстов сохранить в памяти.3. Перебрать все возможные значения искомого подключа k Е {0,1,..., 2n - 1} идля каждого из них выполнить следующие действия:а) g := 1;б) с помощьюпоследнего раунда и подключа k расшифровать сохраненныев памяти пары шифртекста из группы g и получить пары Ptg и Qg;в) если Ptg ф Qg = A out для всех t = 1,...,T , то k - это неправильныйподключ-кандидат. Отбросить его и перейти к п. 3, где выбрать следующийподключ-кандидат; если хотя бы одна из пар обеспечивает условиеPf Ф Qg = Aout, то перейти к п. г;г) если g < G, то g := g + 1 и перейти к п. б; иначе k - это верный подключ.Параметры описанной атаки зависят от вероятности дифференциальной характеристики,параметров блочного шифра и желаемой вероятности успеха атаки. В даннойработе параметры G и T подбирались таким образом, чтобы вероятность атаки составлялана менее 99%. Затем полученные значения использовались для вычислениясложности атаки.Результаты расчетов для некоторых параметров шифра приведены в таблице.Расчет параметров атаки и ее сложностипри различных параметрах шифраПараметры шифра Параметры атаки СложностьРазмер Размер переВероятностьКолиКоличествоВыбранПамять,Колиблока,бираемого характечествопар блоков ные байт чествобит подключа,битристикиг) пяв группе(T)блоки шифрований64 32 2 -1 6 1 2 -1 9 220 223 2532 -3 2 1 2 - 35 236 239 2692 -4 8 2 2 - 51 253 256 28664 2 - 16 1 2 -1 9 220 223 2852 - 32 2 2 - 35 237 240 2 1022 - 48 4 2 - 51 254 257 2 11996 2 -1 6 2 2 -1 9 221 224 2 1182 - 32 3 2 -3 5 238 241 2 1352 - 48 6 2 -5 1 255 258 2 152128 2 - 16 2 2 -1 9 221 224 2 1502 - 32 4 2 -3 5 238 241 2 1672 - 48 8 2 -5 1 255 258 2 184128 32 2 - 16 1 2 -1 9 220 224 2532 - 32 1 2 -3 5 236 240 2692 - 48 1 2 -5 1 252 256 2852 - 64 1 2 - 67 268 272 2 1012 - 80 1 2 -8 3 284 2 88 2 1172 - 96 1 2 -9 9 2 100 2 104 2 1332 - 112 2 -115 2 117 2 121 2 15064 2 -1 6 1 2 -1 9 220 224 2852 - 32 1 2 -3 5 236 240 2 1012 - 48 1 2 -5 1 252 256 2 1172 - 64 1 2 - 67 268 272 2 1332 - 80 1 2 -8 3 284 2 88 2 1492 - 96 2 -9 9 2 101 2 105 2 1662 - 112 2 -115 2 118 2 122 2 18396 2 -1 6 1 2 -1 9 220 224 2 1172 - 32 1 2 -3 5 236 240 2 1332 - 48 1 2 -5 1 252 256 2 1492 - 64 1 2 - 67 268 272 2 1652 - 80 2 2 -8 3 285 289 2 1822 - 96 3 2 -9 9 2 102 2 106 2 1992 - 112 6 2 -115 2 119 2 123 2 216128 2 -1 6 1 2 -1 9 220 224 2 1492 - 32 1 2 -3 5 236 240 2 1652 - 48 1 2 -5 1 252 256 2 1812 - 64 2 2 - 67 269 273 2 1982 - 80 2 2 -8 3 285 289 2 2142 - 96 4 2 -9 9 2 102 2 106 2 2312 - 112 8 2 -115 2 119 2 123 2 248

Скачать электронную версию публикации