Введение в современную криптографию



Pdf көрінісі
бет163/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   159   160   161   162   163   164   165   166   ...   249
Криптография Катц

Атаки на RC4. Хотя RC4 широко распространен в современных системах, 
различные атаки на RC4 были известны на протяжении нескольких лет. Из-за 
этого RC4 больше не следует использовать; вместо него следует использовать 
более новый потоковый шифр или блочный шифр.
Мы начнем с демонстрации простой статистической атаки на RC4, которая не 
опирается на доверенные стороны, которые используют IV . Атака эксплуатирует 
тот факт, что второй выходной байт RC4 (слегка) отклонен к 0. Пусть St обосзначает 
состояние массива S после t итераций GetBits с S0 , обозначающим начальное со-
стояние. Рассматривая S0 (эвристически) как универсальную перестановку {0, . . . , 
255} с вероятностью 1/256 • (1 − 1/255) ≈ 1/256, справедливо, что S0[2] = 0 и X
S [1] ƒ= 2. Предположим на мгновение, что это наш случай. При первой итерации 
GetBits значение i инкрементируется до 1, и j устанавливается на S0[i] = S0[1] = X. 
Затем S0[1] и S0[X] меняются местами так, что в конце итерации мы имеем S1[X] = 
S0[1] = X. При второй итерации i инкрементируется к 2, и j приписывается значение
j + S1[i] = X + S1[2] = X + S0[2] = X,
так как S0[2] = 0. Затем S1[2] и S1[X] меняются местами так, что S2[X] = S1[2] 
= S0[2] = 0 и S2[2] = S1[X] = X. Наконец, выводится значение S2 на позиции 


220
S2[i]+S2[j] = S2[2]+S2[X] = X ; это и есть значение S2[X] = 0. Когда S0[2] ƒ= 0, 
второй выходной байт единообразно распределен. Таким образом, вероятность 
того, что второй выходной байт - это 0 равняется 
или вдвое больше, что было бы прогнозируемо для универсального значения.
Сам по себе вышеописанный пример может и не рассматриваться как серьезная 
атака, хотя, кажется, он действительно указывает на внутреннюю проблему RC4. 
Более серьезная атака на RC4 вполне возможна, если IV водится путем добавления 
его в начало ключа. Такая атака может быт использована, чтобы извлечь ключ, не-
зависимо от его длины, и это реально намного серьезнее, чем дифференциальная 
атака, наподобие той, что была описана выше. Важно отметить, что такая атака 
может быть использована, чтобы полностью взломать стандарт шифрования WEP, 
упомянутый ранее, и она сделала много, чтобы стандарт был заменен.
Ядро атаки - это способ расширить знание о первых n байтах k до знания о 
первых (n + 1) бoайтах k. Обратите внимание, что если IV прикреплен в начало 
действующего ключа kr (поэтому k = IV ||kr), первые несколько байт k отдают-
ся атакующему даром! Если IV длиной n байт, тогда злоумышленник может 
использовать эту атаку, чтобы сначала извлечь (n + 1) байт ключа k (который 
является первым байтом настоящего ключа kr), затем следующий байт ключа k 
и так далее, пока не извлечет весь ключ.
Предположим, что IV длиной 3 байта, ка в случае с WEP. Атакующий ждет, пока 
первые два байта IV не примут специфическую форму. Атака может быть произве-
дена с несколькими вариантами для первых двух байтов IV , но мы рассматриваем 
случай, когда IV принимает форму IV = (3, 255, X) для X произвольного байта. Это 
означает, коненчо же, что k[0] = 3, k[1] = 255, и k[2] = X в Алгоритме 6.1. Можно 
проверить, что после первых четырех итераций второго витка Init, у нас будет
S[0] = 3, S[1] = 0, S[3] = X + 6 + k[3]. 
(6.1)
При следующих 252 итерациях алгоритма Init, i всегда будет больше 3. По-
этому значения S[0], S[1] и S[3], соответственно, не будут изменены, так как 
j никогда не примет значения 0, 1 или 3. Если мы (эвристически) рассмотрим 
j как принимающее универсальное значение при каждой итерации, это будет 
означать, что S[0], S[1] и S[3], соответствнно, не будут меняться с вероятностью
(253/256)252 ≈ 0.05 или 5% времени. Предполгая, что дело обстоит именно так, 
первый байт, выведеный GetBits будет S[3] = X + 6 + k[3]; поскольку X известен, 


221
это открывает k[3].
Итак, атакующий знает, что 5% времени первый байт вывода коррелируется с 
k[3], как и описано выше. (Это уже намного лучше, чем случайное гадание, ко-
торое верное 1/256 = 0.4% времени.) Таким образом, собирая достаточно много 
образцов первого байта вывода, для нескольких IV , имеющих правильную фор-
му, атакующий получает высокую достоверность возможного значения для k[3].


Достарыңызбен бөлісу:
1   ...   159   160   161   162   163   164   165   166   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет