Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Атаки на 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]. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|