Недавно я наткнулся на заметку от Брюса Шнайера про новую атаку на шифр RC4. Атака позволяет, используя статистические инструменты восстановить исходное сообщение, если вы обладаете достаточно большим (~230) числом разных шифровок этого сообщения. Пока, к сожалению, эта атака остаётся непрактичной к применению (раздобыть миллиард одинаковых шифровок проблематично), но, если бы мы могли уменьшить требуемое число хотя бы на 3 порядка, уже можно придумать различные схемы по получению иискомого материала (например, можно встроиться в канал источником шума, вызывая reset соединения и, вынуждая тем самым источник перепосылать исходное сообщение).
К сожалению, авторы промо-сайта, на который ссылается Шнайер, не раскрывают полностью подробности атаки (лишь обещают выпустить статью в скором времени). Я попробовал самостоятельно восстановить и даже чуть уcовершенствовать схему атаки, основываясь на выложенных слайдах.
Прежде, чем рассказать подробности, имеет смысл кратко рассказать про саму схему шифрования RC4.
RC4 является типичным представителем потоковых симметричных шифров. Строится он на основе идеи гаммирования, когда исходное сообщение ксорится с ключевым потоком (известным только отправителю и получателю). В теории это схема абсолютно криптостойка, но лишь в тех предположениях, что характеристики ключевого потока абсолютно неизвестны атакующему и ключевой поток непериодичен. На практике же невозможно сконструировать ключевой поток, обладающий такими характеристиками, потому обычно поточные алгоритмы шифрования конструируют ключевой поток в виде псевдослучайной последовательности байтов с известными только источнику и получателю сидами. RC4 поступает именно таким способом и алгоритм формирования его ключевого потока достаточно подробно и понятно рассказан в википедии.
Обнаруженная же криптоаналитиками уязвимость заключается в том, что получаемый алгоритмом RC4 псевдослучайный поток даёт неравномерное распределение значений каждого из байтов. А зная точные вероятности{pi,j} генерации значения j в i-ом байте ключевого потока уже можно восстановить исходное сообщение используя статистические методы.
Допустим, что у нас есть очень много шифровок исходного сообщения. Составим на их основе матрицу
{ēi,j} - выборочная частота встречаемости символа j на i-ой позиции. Заметим, что в каждой из шифровок символ j определяется как m[i] ⊕ K[i], а это значит, что реальная вероятность
ei,jравна
pi,j ⊕ m[i]
Как же восстановить исходное сообщение, имея матрицу
{ēi,j}?
- самый простой способ - сопоставить позиции максимальных значений в матрицах
ē
иp
; - чуть более эффективным и менее наивным способом является метод максимального правдоподобия
построим функцию правдоподобия того, что i-ый символ сообщения равен v:
F(i,v) = П (pi,j⊕v)ēi,j
илиlog F(i,v) = Σēi,jlog pi,j⊕v
и при декодировании v восстанавливаем как символ, на котором достигается максимум логарифма функции правдоподобия; - еще эффективнее вместо униграммных частот использовать биграмные частоты (вместо вероятности встретить значение j в байте с номером i - вероятность встретить значение
j0j1
в 2 байтах, начинающихся с позиции i), а исходные текст восстанавливать как текст, наилучшим образом соответствующий заданной биграммами языковой модели.
Подобные методы дешифрования я реализовал в специально заведённом github-проекте, желающие могут посмотреть на код (в случае биграммного подхода, кстати, используется динамическое программирование для восстановления текста и непопсовая диадическая свёртка). Ниже же представляю табличку, основанную на моих экспериментах по дешифровке первых 256 байтов классической рыбы "Lorem ipsum" вышеперечисленными подходами. Для дешифровки я использовал вероятности сключевого потока, расчитанные методом Монте-Карло на 246 точках (это даёт 4-5 десятичных знаков точности для униграмных частот и 3 для биграмных, если у кого-то есть идеи как посчитать вероятности точнее, welcome в комментарии).
| Число шифровок | Число правильно дешифрованных байтов | ||
|---|---|---|---|
| Maximum Position Decryption | Unigram Likelyhood Decryption | Bigram Likelyhood Decryption | |
| 225 | 11 | 16 | 16 |
| 226 | 19 | 33 | 23 |
| 227 | 43 | 55 | 53 |
| 228 | 114 | 120 | 122 |
| 229 | 164 | 167 | 185 |
| 230 | 214 | 223 | 240 |
| 231 | 248 | 250 | 255 |
| 232 | 251 | 254 | 256 |
Ну и на сладкое таблички с расшифровками, получаемыми каждым из методов (зелёным раскрашены верные байты).
Maximum Position Decrypion:25: .oy%!....%. .pl.d.....~u!..5.&q...t)...\!.B..L..>.i.@<...........[i....0F...ioo`.;*.W....a.I..........\5.O.4...E..H..M.b.DtH .....9.W...V.k.zgawn8..... Y.o.....zU............c|d.;.%'...A.....`f..-e.).B.i.t+.............../,N....?......9s3..q(....X}xK.P..d+ 26: ko.gkY...%. .>....h..._m..7 c&q...t)..... Y\.s...*i.....u.... ........o.vt...z'..a..S.d.nt.u.W........t5.fn4..Z..Jj..$.K...z ..C..^.....V.nlz9....... ...ho6.B.<5.0.........Qf.r.).x....m..........y..).y...$z....$....."e;..Z.<, (..Eq..&.f....>. .qi....;0fPD.'. 27: .orgmYPx.%+ .ol.d `i. vm..7 .qq..cT.l7..SdQ\vG..i*g..>[t).s<. ... i..mo. -..p.'..ac.^..un..u`.....e.det m$<..eAE.|nY.O.5/..H <[8J..m\.Z.V.nlz.....Vma .v.ho6...<.. .1...iq_.B.gE..Ca.'x./..l.V...8.y..a^J:.........;P.......=<....*.q7%.G2.......S.i.;./ ..{p... 28: orgm&nxsum iolor `it vmet, .oqsDctetur adi\vsicing..Z&t,.s.d do e*usmo. t.Z.or imcid]>unt u. l...re et ..Oo.e...|.#+.l;q.a..Ut8qnim<.. Vini =v...FL, .ui. ....<.. ....&iqutio. $lCa..W6.....ij.......a.y.ib..^g....P..o......cmn...ucr.GD..s.aj5.qir......N..!. 29: 0orch&nxsum dolor `it vmet, coqsectetur adi\isicing.elit, sed do eiusmod tempor incididunt ut la.ore .t dwlorE m.|na iliqua. UtsJnim\.d m.nim v.niam,n.ui. n.s.rkd Qxe..ix.tion ul.a.cW ...-.i. ...4 !t.>.i.0Au#eG]V. .oQ..z1#.fn!..u.t.G2B.s6ajta.i......(.o. . 30: .orch&npsum,iolor `it vmet, consectetur adipisicing.elit, sed do eiusmod tempor incididunt ut labore et dolore magna .liqua. Ut enim ad minim v.niam, quis n,strud exercixation ulVamco l.borib .i.i ut .liquAdWex et co.mod1 ..nuequa.....7s ajte i\ur. ..>o; . 31: .orch ipsum,dolor `it amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo con.equat. Duis aute irure ]olor . 32: .orcm ipsum,dolor `it amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor 1
25: Loye$....%. 9F-.d..o...u...}.oq..vt).1..!.B%...,>.i.@<^.....9..."e;.i.....F...ioo..;*.W....t.I..........\5.O.4...E..H..M.b.DtH......9.W...V.k.zgawn8..... Y.o..B..zS......i......|d[;.% ...A..=..`fO.-e.)..Ci.u+......,........-, \!..?....D.9.3..qS.i....x.f.Q..W 26: Lo.e_K.xz%. .o'or s.. vm..7.coq..2t)..... T..s`.i*g|...vg.."e;. ...3i...o.F.....'.6/..S.d.nt.u..........t5.fn4..Z..Jj..$.K...z ..C..^.....V.nlz9....... ...ho6.B.<5.0.........Qf.r.X.x...Fm'....h .O.y..).y...$.......*.b..E...<. (..9.....D....>.t.qi^....0fP@..W 27: Lorem.nx.um .olo! `i. vm.t7..qq.xcte}u..adQ\is..i*g..Z[t).s<. .@ ei..mo. -...f'.6/c./..un.gu......e.?et m$<..eAE.J?Y.O.5/..H <[8J..m\.Z.V.nlz.....Vma .v.h.6.?T<D{ .....iq..B.g...CaQZx./....V.m.8...&g^y:....6.....,.3......<Y.....q?%..2..s.j.tS.}.......C&..i 28: Lorem&nxsum iolor `it vmet, .oqsDctetur adi\isic.|g PZ.t,.sYd do e*usmo. -eZpor imci'?>unt u. l.b.re et ..Oo.e.E.|.#+.l;q.a..Ut8qnim... Vini =v...FL, .ui. ...T<.. .....iqutiog $lCa..W.....{ij..... .a.y.i...^g....v;3o.....tcmn...ucr.GD..s.#j5.qir.r...(l.. & 29: Loreh&nxsum dolor `it vmet, coqsectetur adi\isicing.el.t, sed do eiusmod tempor incididunt ut labore et dwlorE m.|n1 iliqu.. UtsJnim\.d m.nim v.ni.m,n.ui. n.s.rkd Qxe..ix.tion ul.a.@W ...-.i. ...4 !t.>.i..Au#.G];a .om.....con!..u....D..s6ajt.qi..r.._(..0 i 30: Loreh&npsum,dolor `it vmet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna .liqua. Ut enim ad minim v.niam, quis n.strud exercixation ullamco l.boris .isi .t.aliquAdLe. et commod1 ..nuequa.. D.7s .jte i\ure ...o. i 31: Lorem ipsum,dolor `it amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo conu.quat. Duis aute irzre ]olor i 32: Lorem ipsum,dolor `it amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor i
25: Loye.....%....-.u..{..vm...j.oq..vt)....!.B.......i..<^..~......"e;Ai..... .....o..;*.W....t.I./........\5.O.4......H.}.l..Ut....._.9.W ..V.k.zgai.8.....vY.o#hB.|z.,0....i......|d.;.% ...A......fK.-e.)d..i.u+......,........-. \........D...3..WN......x......W 26: Lore_M.xz%. .o'or2`...vm..,.c.q..2t)H.... T..s`.i.g....vg.."e;. ...3*.../.v....('.6/..S.d.n.......P.....t5.fn4`.E..Jj..$../._z...%_.^.W.(.V.n.zga...V.. ...ho6.B.<5S0e......u>Q.gr.)*.. ..m.....h....y..).y...$.....$.,.3.....$.. (.?9.....f...3..;.q.^.W...fPQ..W 27: Lorem.nxzum iolo0 si. vm.t,.coq.xcte}1..ad.\i]..i*g..Z[.)..<. .j ei..mo. ...pz'.6/c./..un.gu......e.d.t .$<..eAE..?Y.O.K/:.. <[J...m\...V.nhz*....Vm. .v.ho6.?.<.. .....iq....g...CaQZx./.p.ZV.I.8...&f^......6.....,.......=.Y.|...q7%0....s..*.S.}\../....&... 28: Lorem ixzum iolor sit vmet, .oqsectetur adi\isicing.el.t,.sed do e*usmo.i-eZpor imci'i.unt ut l.bRre e...R^o.e.E.|n#+.l;qua..Ut8qnim<x. Vini #v..V.L, .ui.....T..d .....i.utiog.$.C..RW......i_..... .....i...^g...VP.3.......conm..ucr..D..s #.T.q.r).Z..(C...G 29: Lorem ipsum dolor sit vmet, consectetur adipisicing.el.t, sed do eiusmod tempor incididunt ut labore et d.lor. m.|na aliqua. UtsJnim ad minim veni{m,n..i. n.s..kd exer.ixation ul.{.@W....-.is ...4 .t.>.i.0Au#.GJ;a .om...1#conu..u.t.G2uis aMt..ir...._(.o= i 30: Lorem ipsum dolor sit vmet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exer.itation ullamco l.boriq .isi ut aliqu6u0ex et commodo consequat. D.7s a[te irure 6.ioG i 31: Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo conuequat. Duis aute irure dolor i 32: Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor i
В качестве простейшего примера предлагаю взять игру с тривиальными правилами - бег на 100м. Выигрывает спортсмен, который быстрее всего пробежал дистанцию. Но как определить оптимальную стратегию забега? Каждому с детства известны 2 стратегии - выложиться в начале и тогда на концовку дистанции тебе не хватит сил, или же сэкономить силы в надежде на финишный рывок, но тогда ты можешь отпустить противников сильно вперёд. 
Чтобы не было ощущения, что пример слишком искусственный у нас есть даже физическая модель, в которой верится в реализацию этих случайных величин.
В конце нашей 100-метровки есть яма, вылезать из которой нужно ~16 мин, но если мы сэкономим силы, то легко перепрыгнем яму, а вот если экономить не будем, то перепрыгнем только с вероятностью 90%.