Шифре тока које се стварно користе (20 min)

У овом одељку, желим да вам дам неколико примера шифара тока, које се користе у пракси.

Почећу од два стара примера, који не би

требало да се користе у новим системима. Међутим, и даље су доста заступљени,

тако да само желим да напоменем њихова имена, тако да би вам били познати ови концепти.

Прва шифра тока о којој желим да вам говорим је RC4, која је развијена

1987. Желим само да вам дам њен уопштени опис,

а онда ћемо да говоримо о њеним слабостима. RC4 има као улаз

неку вредност променљиве дужине - семе; овде ћемо као пример да узмемо

128 битова за семе, које се затим користи као кључ за шифру тока.

Прво што уради јесте да прошири 128-битни тајни кључ на 2048 битова,

који се користе као унутрашње стање генератора. Након што се уради

ово проширење, извршава се врло једноставна петља, где сваки пролаз

кроз петљу враћа као излаз један бајт. Тако да, у суштини, генератор може да се извршава

колико год пута желите, и сваки пролаз даје један бајт. RC4 је заправо врло заступљен.

Користи се уобичајено у HTTPS-у.

Гугл га на пример користи у свом HTTPS-у. Користи се и у WEP-у који

смо разматрали у претходном одељку, али ту се користи неправилно

тако да није нимало безбедан. Током година,

пронађене су неке слабости у RC4, тако да се препоручује да се у новим пројектима

не користи, већ да се користи савремени псеудо-случајни генератор који ћемо да

разматрамо при крају овог одељка. Споменућу само две његове слабости.

Прва, која је у ствари мало чудна, ако погледате други бајт

излаза RC4, испоставља се да је други бајт делимично пристрасан. Када би RC4 био потпуно

случајан, вероватноћа да други бајт буте 0

била би тачно 1 / 256. Постоји 256 могућих бајтова, тако да вероватноћа

да буде 0 треба да буде 1 / 256. Испоставља се да је за RC4 ова вероватноћа

у ствари 2 / 256, што значи да ако користите RC4 да шифрујете

поруку, постоји извесна вероватноћа да се други бајт уопште не шифрује. Другим речима,

биће ХОR-ован са 0 са два пута већом вероватноћом него што треба да буде.

Значи 2 / 256 уместо 1 / 256. Узгред треба да кажем да не постоји

ништа посебно везано за други бајт. Испоставља се да су први и трећи бајт

такође пристрасни. Тако да постоји препорука, да ако се користи RC4,

треба да се занемати првих 256 бајтова излаза, и да се

излаз генератора користи почев од бајта 257. Првих пар бајтова

је пристрасно, тако да их само занемарите.

Други напад који је откривен, јесте да ако погледате врло дугачак излаз из RC4,

постоји повећана вероватноћа да се добије низ 00. Другим речима,

постоји мало већа вероватноћа да се добије ових 16 битова (2 бајта) 0, 0, него што би требало.

Да је RC4 сасвим насумичан, вероватноћа да се појави 00 била би тачно (1 / 256) на 2.

Испоставља се да је RC4 делимично пристрасан, тако да вероватноћа износи (1 / 256) на 3.

Ова пристрасност се појављује тек након излаза дужине неколико гигабајта података.

Ипак, овако нешто може да се користи како би се предвидео генератор

и свакако може да послужи да би се разликовао излаз генератора

од истински случајног низа. Та чињеница да се 00 појављује чешће него што би требало

је показатељ разлике. У последњем одељку већ смо говорили

о нападима који користе везу између кључева, који су били уперени на WEP, а који показују

да ако се користе блиско повезани кључеви, тада је могуће

да се дође до полазног кључа. Дакле то су слабости које су уочене у RC4, тако да

се препоручује да нови системи не користе RC4, већ да уместо тога користе

савремене псеудо-насумичне генераторе. Други пример који желим да вам дам је

врло слаба шифра тока која се користи код шифровања двд филмова. Када купите

двд у радњи, сам филм се шифрује коришћењем шифре тока која се назива

систем за кодирање садржаја, CSS. CSS се показао као врло слаба шифра тока,

која лако може да се пробије, и ја желим да вам покажем како ради алгоритам напада.

Одрадићемо овај пример да бисте видели како изгледа алгоритам напада,

али постоје многи системи који користе управо овај напад да декриптују

шифроване двд-јеве. CSS шифра тока заснива се на нечему што воле пројектанти хардвера.

Развијена је да буде хардверска шифра тока,

која се лако хардверски примењује, а заснива се на механизму регистра са

линијским повратним померањем. Ово је регистар

који се састоји од једнобитних поља.

Постоје нека поља, не сва, која називамо доточним пољима,

а њихове вредности се доводе у ХОR,

а затим се на сваки циклус клока, регистар помера на десно. Последњи бит отпада

а нови први бит постаје излаз из овог ХОR-а.

Видите да је ово једноставан механизам за примену, и заузима врло мало транзистора.

Само померај удесно, последњи бит отпада, а први бит постаје

ХОR претходних битова. Дакле почетна вредност - семе - код овог регистра је

заправо његово почетно стање.

На њему се заснива више шифара тока. Ево и неких примера.

Рекли смо да двд шифровање користи два оваква регистра. То ћу да вам покажем за који тренутак.

GSM шифровање садржи два алгоритма, А51 и А52,

који користе 3 регистра померања. Bluetooth шифровање садржи алгоритам Е0, такође

шифру тока, са 4 регистра. Испоставља се да су сви они доста слаби,

и да заиста не би требало да се ослања на њих ради шифровања саобраћаја,

али су сви уграђени у хардвер, тако да је сада мало теже да се измени то што хардвер ради.

Најједноставнији од њих, CSS, може јако згодно да се нападне,

тако да хајде да вам покажем како се изводи овај напад.

Кључ за CSS је 5-бајтни, тј. 40-битни, 5 х 8 је 40 битова.

Ограничили су се на 40 битова зато што је двд шифровање развијено

у време када је прописима извоза из САД био дозвољен само извоз

алгоритама за шифровање где је кључ само 40 битова. Тако да су пројектанти CSS-а били

ограничени на јако, јако кратке кључеве. Њихов поступак је следећи:

користе се два регистра померања, један 17-битни,

и други 25-битни,

нешто дужи. Њима се почетна вредност задаје

на следећи начин. Дакле кључ изгледа овако.

Почне се са јединицом, која се придодаје на прва два бајта кључа.

А то је почетно стање регистра померања.

И другом регистру померања се почетно стање задаје на сличан начин.

Јединица придружена на последња 3 бајта кључа,

што се спушта као почетно стање регистра. Можете да видите да су прва два бајта

- 16 битова, плус почетни, то је укупно 17 битова, а за други регистар померања

24 бита плус један - то је 25 битова. Примећујете да смо искористили свих 5 битова кључа.

Затим се ови регистри померања покрећу у осам циклуса, тако да се њима добија

по 8 излазних битова. Излази пролазе кроз овај сабирач који извршава

сабирање по модулу 256. Дакле ово је блок сабирања по модулу 256. Постоји још једна

техничка ствар која се извршава - додаје се пренесени бит

из претходног блока. Али то није тако важно.

Дакле примећујете да у сваком блоку радимо сабирање по модулу 256

да бисмо занемарили бит преноса, мада се он у ствари додаје као 0 или 1 у збир

у наредном блоку. Тако да се у сваком пролазу добија по један бајт.

Затим се овај бајт наравно користи, у XOR-у са одговарајућим

бајтом филма који се шифрује. Тако да је ово врло једноставна шифра тока,

потребно је врло мало хардвера за имплементирање. Извршава се брзо, чак и на

јефтином хардверу, и шифрује филмове. Шифра се лако пробија

у времену оквирно 2 на 17. Да вам покажем како.

Претпоставимо да пресретнете филм, овде имамо рецимо

шифрован филм који желите да дешифрујете, и будући да је шифрован

немате никакву представу о томе шта је овде. Међутим, само захваљујући томе

што двд шифровање користи MPEG датотеке, ви знате префикс

отвореног текста, на пример можда је ово 20 бајтова. Дакле знамо да

ако извршите ХОR ових двеју ствари,

добијате почетни одељак од PRG-а. Дакле добићете

првих 20 бајтова излаза из CSS-a.

Дакле ево шта ћемо да урадимо. Имамо првих 20 бајтова излаза.

Урадимо сада следеће. Покушамо свих 2 на 17 могућих вредности за први

регистар померања. Дакле 2 на 17 могућих вредности. За сваку вредност,

за сваку од ових 2 на 17 почетних вредности регистра, одрадићемо пролазак

кроз регистар за 20 бајтова. Дакле добијамо 20 бајтова од овог

првог регистра, за сваки од 2 на 17 могућих почетних вредности.

Сетите се да имамо пун излаз из CSS-a. Тако да можемо

да узмемо овај излаз, и да га одузмемо од 20 бајтова

које смо добили из првог регистра, тако да ако је наш погодак за почетно стање првог регистра

исправан, оно што добијемо је првих 20 бајтова излаза

из другог регистра. Зато што је то оно што је по дефиницији излаз из CSS система.

Испоставља се да је посматрајући 20-бајтни низ, врло лако

да се закључи да ли је овај 20-бајтни низ потекао од 25-битног регистра померања или не.

Ако није, онда знамо да је наша претпоставка за 17-битни регистар померања била

погрешна, и тада прелазимо на следећи покушај за регистар,

па на следећи, итд. Све док коначно не погодимо право почетно стање

17-битног регистра померања, а тада заправо добијамо

да 20 бајтова које смо узели као кандидате за излаз 25-битног регистра

јесу заиста могући излаз из 25-битног регистра. А тада, не само да смо

открили право почетно стање за 17-битни регистар, већ смо открили

и право почетно стање за 25-битни регистар. А тада можемо да предвидимо

преостале излазе из CSS-a, и наравно, користећи ово, можемо да дешифрујемо остатак филма.

Можемо да откријемо преостали отворени текст.

О овоме смо и раније говорили. Испричао сам ово мало брже, али надам се

да је било јасно. Такође ћемо да урадимо вежбу за домаћи над овом врстом шифара тока

тако да ћете да стекнете представу како раде ови алгоритми напада.

И требало би још да напоменем да сада постоје многи системи са отвореним софтвером

који заправо користе овај начин рада да декриптују податке шифроване CSS-ом.

Сада када смо видели две слабе шифре, пређимо на боље примере; заправо

бољи псеудо-насумични генератори потичу од такозваног еСтрим пројекта. Ово је пројекат

који је завршен у 2008-ој, и њиме је квалификовано 5 различитих шифара тока,

али ћу овде да вам представим само једну. Пре свега, параметри за

ове шифре тока се мало разликују од оног на шта смо до сада навикли.

Дакле ове шифре тока као и обично имају семе. Али поред тога, имају и такозвану.

привремену вредност, видећемо како се она користи за који тренутак.

Дакле имамо два улаза: семе и привремену вредност, коју ћемо ускоро да објаснимо.

Наравно добија се јако велики излаз, n је

много, много веће него s. Под привременом вредношћу подразумевам вредност која

неће бити поновљена докле год је кључ исти. Ускоро ћу то мало темељније да

објасним. За сада, само је посматрајте као јединствену вредност која се не

понавља све док је вредност кључа иста. Једном када имате псеудо-насумични генератор (ПНГ),

са којим шифрујете, добијате шифру тока као и раније, осим што сада, као што видите,

ПНГ узима као улазне вредности и кључ и привремену вредност. Уз својство

да се пар (k, r), дакле (кључ, привремена вредност), никад, никад не понавља.

Никад се не користи више него једном. Суштина је у томе, да кључ може да се поново употреби,

зато што привремена вредност чини пар јединственим, зато што се k и r заједно

користе само једном. Пар је јединствен. Дакле привремена вредност је згодна досетка

која нас поштеђује тога да прелазимо на нови кључ сваки пут. Конкретан пример

из еСтрима који желим да вам покажем је Салса 20.

То је шифра тока која је развијена како за софтверску тако и за хардверску

примену. Ово је занимљиво. Разумели сте да су неке шифре тока

развијене за софтвер, као RC4. Све што се врши њоме је развијено на такав начин

да софтверску примену чини брзом, док су неке друге шифре тока развијене

за хардвер, на пример CSS, која користи регистар померања нарочито развијен

да хардверску примену учини јефтином. Добра ствар код Салсе је

што је развијена на такав начин, да осим што је лака за примену у хардверу, њена

софтверска примена је такође јако брза. Да вам објасним како Салса ради. Салса

узима 128-битне или 256-битне кључеве. Објаснићу вам 128-битну верзију.

Ово је семе. Затим се узима и привремена вредност, као и раније, која је

у овом случају 64 бита. И ствара се велики излаз. Како ово

заправо ради? Сама функција је одређена на следећи начин. За дате

вредности кључа и привремене вредности, ствара се јако дугачак, псеудонасумични

низ, које год дужине је потребно. А то ћу чини користећи ову функцију коју ћу да означим

са H. Функција Н има три улаза. Кључ, тј. семе k,

привремену вредност r, и бројач који се повећава из корака у корак. Дакле иде

од нуле, до 1, 2, 3, 4, докле год је потребно. Значи,

одређујући вредност за Н за ове k, r и растући бројач, добијамо

низ који је оне дужине коју хоћемо. Све што имам да урадим јесте да опишем како функција

Н ради. Хајде да то и урадимо. Она ради на следећи начин.

Почнемо тако што проширимо стања на прилично велику вредност, 64-бајтну,

на следећи начин. Поставимо константу на почетак,

т0, ово је 4 бајта, 4-бајтна константа,

Салса вам задаје вредност за т0. Затим стављамо k које је

16 бајта. Затим ставимо још једну константу. Поново, ово је 4 бајта.

Као што сам рекао, ова константа има унапред задату вредност. Затим ставимо

привремену вредност, која је 8 бајта. Затим ставимо индекс - то је бројач - 0,

1, 2, 3, 4, који заузима још 8 бајта. Затим ставимо још једну константу,

т2, која заузима још 4 бајта. Затим поново ставимо кључ, ово је додатних

16 бајтова. Најзад стављамо и трећу константу, т3, која је

4-бајтна. Као што само рекао, сабравши ово имамо укупно 64

бајта. Дакле проширили смо кључ, привремену вредност и бројач до 64

бајта. Значи кључ се јавља два пута. А затим применимо

функцију, назваћу је малим словом h. Дакле применимо ову функцију h,

а она је 1-на-1, дакле додељује 64-бајтну вредност за 64-бајтни улаз.

Она је потпуно иверзибилна. Дакле функција h је

иверзибилна функција. То значи да за задати улаз добијамо један излаз, и за задати

излаз добијамо улаз. Развијена је нарочито на такав начин да буде, као прво, лака

за примену у хардверу, а као друго, на х86 је нарочито лака за примену зато што

х86 има SSE2 скуп наредби, који подржава све операције потребне

за ову функцију. Она је врло, врло брза. Захваљујући томе, Салса је јако брза

шифра тока. Ово се затим извршава поново, и поново, и поново. Дакле врши

се ова функција h поново и добије још 64 бајта. И тако даље,

ово се одради 10 пута. Дакле све ово овде се понавља 10 пута,

дакле применити h 10 пута. Само по себи, ово и није тако насумично.

Неће да изгледа насумично зато што, као што сам рекао, H је потпуно иреверзибилна.

Имајући коначни излаз, лако је да се обрне h и да се врати

до изворног улаза и провери да ли улаз има праву грађу. Зато се изврши још једна

ствар, а то је да се изврши XOR над улазом и коначним излазом. У ствари,

ово није XOR већ збир. Врши се сабирање реч по

реч. Имамо 64 бајта, сабирамо реч по реч, 4 бајта

у истом кораку, и коначно добијамо излаз од 64 бајта, и то је то. То је цели

псеудо-насумични генератор. Дакле то је цела функција h.

Као што сам објаснио, цела ова конструкција овде јесте функција Н. Она се рачуна

тако што се бројач i повећава од 0 на 1, 2, 3 итд.

То вам даје псеудо-насумични низ који је оне дужине која вам треба.

Не постоје значајни напади на ово. Безбедност овог система је

јако близу 2 на 128. Видећемо шта то значи нешто касније.

То је јако брза шифра тока, и хардверски и софтверски. Колико

можемо да видимо, изгледа непредвидиво као што је и захтев за шифру тока.

Треба да напоменем да пројекат еСтрим има 5 шифара тока попут

ове. Одабрао сам Салсу зато што ми делује најелегантније. Али могу да вам дам

неке вредности перформанси. Овде можете да видите вредности перформанси за

машину типа х86, на 2.2 гигахерца. И можете да видите да је RC4 заправо најспорији.

Зато што он и не користи заправо предности хардвера,

јер обавља само бајтне операције. Тако да има много изгубљених циклуса.

Али кандидати еСтрима, како Салса тако и овај

други кандидат, Сосеманук (треба рећи да су ово еСтрим финалисти,

шифре тока које је одобрио еСтрим пројекат), као што видите

постигли су значајну стопу. Ово је 643 мегабајта у секунди

на овој архитектури, више него довољно за један филм, ово су у ствари прилично упечатљиве

стопе. Дакле, сада сте видели примере двеју старих шифара тока које не би требало

да се користе, као и нападе на ове шифре. Видели сте како изгледају савремене шифре тока

са привременом вредношћу. И видите вредности перформански за ове

савремене шифре тока, тако да ако вам буде била потребна шифра тока, можете да користите неку

од финалиста еСтрима, на пример Салсу.