Дефиниције и безбедност (16 min)

Прошле недеље, проучили смо теорију бројева која нам је потребна за шифровање јавним кључем.

Ове недеље ћемо да применимо ово знање, и да саградимо

неколико безбедних шема за шифровање јавним кључем. Али најпре ћемо да дефинишемо шта је

шифровање јавним кључем, и шта значи да ово шифровање буде безбедно.

Да вас подсетим да у шеми са шифровањем јавним кључем,

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

који означавамо са D. Међутим, овде алгоритам шифровања узима

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

Јавни кључ се користи за шифровање, а тајни за

дешифровање порука. У овом случају порука m је шифрована

јавним кључем, а излаз је шифрат с. И слично томе,

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

излаз из алгоритма дешифровања је изворна порука m. Шифровање јавним кључем

има пуно примена. Прошле недеље смо видели класичну примену

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

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

Алиса би произвела пар јавни кључ - тајни кључ,

послала би јавни кључ Бобу, Боб би произвео случајно х,

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

шифровано њеним јавним кључем. Алиса може да дешифрује, поврати х, и сада обоје

имају заједнички кључ х који могу да користе да безбедно комуницирају међусобно.

Нападач може да види само јавни кључ,

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

било каквих података о х. Дефинисаћемо тачније шта то значи

не бити у стању да сазнате било шта о х. Шифровање јавним кључем има

у ствари много других примена. На пример, јако је корисно код

неинтерактивних апликација. Рецимо сетите се система е-поште.

Овде Боб жели да пошаље писмо Алиси, и када га пошаље, писмо прелази од

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

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

немеђудејствујућих окружења, где Боб шаље писмо, и Алиса треба да прими то писмо,

а да при томе не треба да комуницира са Бобом да би га дешифровала.

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

да се успостави заједнички тајни кључ између Алисе и Боба. У овом случају,

Боб би послао писмо шифровано коришћењем Алисиног јавног кључа.

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

коришћењем њеног јавног кључа. Када Алиса прими ово писмо, користи

свој тајни кључ да дешифрује шифрат и поврати отворени текст поруке.

Наравно мана оваквог система је што Боб треба да некако

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

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

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

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

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

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

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

Шифровање јавним кључем је такође јако корисно код неинтерактивних апликација,

када било ко на свету, неинтерактивно, треба да пошаље поруку Алиси,

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

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

шта је систем за шифровање јавним кључем. Састоји се из три алгоритма, G, E и D.

G је алгоритам за стварање кључа, који у основи

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

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

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

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

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

који узима одговарајући тајни кључ и шифрат и производи одговарајућу поруку.

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

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

добијемо изворну поруку. А сада, шта значи за шифовање јавним кључем да буде безбедно?

Почећу од дефинисања безбедности од прислушкивања.

А затим ћемо да дефинишемо безбедност од активних напада.

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

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

Нападачка игра се дефинише на следећи начин. Дефинисали смо ова два огледа,

оглед нула и један. У оба огледа, изазивач

ствара пар од јавног и тајног кључа. Он ће да преда јавни кључ

нападачу. Нападач ће да избаци две поруке, m0 и m1,

исте дужине, и да добије натраг било шифровану m0 или

шифовану m1. У огледу 0 он добија шифровану m0, а у огледу 1,

шифровану m1. А затим нападач треба да каже

коју је добио - да ли је добио шифровану m0 или m1?

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

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

А његов циљ је да каже да ли је шифрат с шифровање од m0 или од m1.

Није дозвољено никакво петљање у сам шифрат с за сада. Као и обично, кажемо да је

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

да разликује оглед 0 од огледа 1. Другим речима, не може да каже

да ли је добио шифровање од m0 или од m1. Пре него што пређемо

на активне нападе, желим да напоменем у каквом су односу дефиниција коју смо

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

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

разликовали смо случај када је кључ коришћен једном, и случај када је

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

разлика. На пример, једнократна бележница је безбедна ако се кључ користи само једном

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

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

за једнократну безбедност, и посебну дефиницију, која је

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

слајду је јако слична дефиницији једнократне безбедности

симетричних шифара. Заправо се испоставља да, код шифровања јавним кључем,

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

Другим речима, не морамо да изричито дамо нападачу могућност да

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

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

шифрује коју год поруку жели. Из тога произилази да се сваки пар јавног и тајног кључа

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

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

коришћењем датог јавног кључа који смо му дали у првом кораку. Последица тога је

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

због чега овај појам називамо нераспознавањем под нападом са произвољним

отвореним текстом. Ово је само мања напомена којом објашњавамо зашто нам у поставци за јавно

шифровање не треба сложенија дефиниција да обухватимо

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

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

Конкретно, погледајмо пример е-поште. Овде имамо нашег пријатеља Боба

који жели да пошаље писмо својој пријатељици Каролини. Каролина има

налог на Г-мејлу. Ово ради тако што се писмо шаље

Г-мејл серверу, шифровано. Г-мејл сервер дешифрује писмо, погледа ко је прималац,

и затим, ако је прималац Каролина,

прослеђује писмо Каролини. Ако је прималац нападач,

прослеђује писмо нападачу. Ово личи на прави начин рада Г-мејла,

зато што би пошиљалац послао писмо шифровано путем SSL-a Г-мејл серверу,

сервер би отклонио SSL и проследио писмо

одговарајућем примаоцу. Претпоставимо сада да Боб шифрује писмо коришћењем система

који омогућава нападачу да мења шифрат непримећен.

На пример, замислимо да је писмо шифровано коришћењем бројача, или нечим сличним.

Тада када нападач пресретне писмо, он може да промени примаоца,

тако да је прималац сада нападач@gmail.com, а знамо да је код

бројача ово врло лако да се уради. Нападач зна да је

писмо упућено Каролини, занима га само тело писма.

Лако може да промени примаоца писма на нападач@gmail.com, и сада када сервер

прими писмо, он га дешифрује, види да је прималац наводно нападач,

и прослеђује писмо нападачу. И сада нападач може

да прочита тело писма које је било упућено Каролини.

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

да дешифрује сваки шифрат где је прималац "за: нападач".

Дакле сваки шифрат где отворени текст почиње речима "за: нападач".

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

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

да је овде циљ нападача да добије тело поруке.

Нападач већ зна да је писмо намењено Каролини. Све што је морао да уради је

да промени примаоца. Овај напад мењањем шифрата подстиче

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

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

Као што сам рекао, циљ нам је да направимо системе који су безбедни под овим врло затвореним

појмом шифровања. Дакле имамо шему шифровања (G, E, D). Рецимо

да је дефинисана над простором порука и шифрата (М, С), и као и обично

дефинисаћемо два огледа, оглед 0 и 1.

Дакле b нам говори да ли изазивач имплементира оглед 0 или 1.

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

јавни кључ нападачу. Сада нападач може да каже: "Ево ти гомила

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

шифрат с1, и добија дешифровање шифрата с1, наиме m1.

Може да ово уради опет и опет, дакле подноси шифрат с2, и добија дешифровање

а то је m2, шифрат с3, и добија дешифровање m3, и тако даље.

Коначно нападач каже: "Завршили смо са фазом упита", и сада

подноси две поруке подједнаке дужине, m0 и m1 као и обично,

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

m0 или m1, у зависности од тога да ли смо у огледу 0 или 1.

Сада нападач може да настави да издаје упите у виду

шифрата. Дакле може да настави да издаје захтеве за дешифровањем. Дакле он поднесе

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

мора да постоји ограничење. Када би нападач могао да поднесе произвољни шифрат,

наравно да би могао да добије изазов. Само би требало да поднесе

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

да ли је у фази изазова добио шифроване m0 или m1.

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

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

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

осим шифрата изазова. Али и поред тога што су му дата сва ова дешифровања, и даље

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

или m1. Примећујете да је ово јако затворена дефиниција, која

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

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

"за: нападач". Овде, кажемо да нападач може да дешифрује произвољни шифрат,

докле год је он различит од шифрата изазова, с. А његов циљ

је да каже да ли је шифрат изазова шифровање од m0

или од m1. Као и обично, ако то не може, другим речима,

ако је његово понашање у огледу 0 исто као и понашање у огледу 1,

дакле ако није успео да разликује шифровање од m0 од шифровања од m1,

иако је имао сву ову моћ, тада кажемо да је систем безбедан

под произвољним шифратима - ССА безбедан. Понекад постоји акроним

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

кажем само ССА безбедан. Погледајмо сада како ово обухвата пример са е-поштом који смо видели

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

само шифру поруке, нападач може да промени примаоца

од Алисе на, рецимо, Чарлија. Ево како тада добијамо ССА игру.

У првом кораку, нападач наравно добија јавни кључ. А тада нападач

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

тело је 0, а у другој 1. Али обе поруке су

намењене Алиси. Као одговор, он добија шифрат изазова, с.

Дакле сада имамо наш шифрат изазова с. Сада нападач

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

Он ће да пошаље шифрат с', где је с' шифрована

порука Чарлију, чије је тело управо тело изазова, b. Дакле ако се сећате, b

је или 0 или 1. Пошто је отворени текст различит, знамо да

и шифрат мора да буде различит. Дакле с' мора да буде различито

од шифрата изазова, с. Дакле с' мора да буде различито од с.

Сходно томе, изазивач мора да дешифрује, у складу да дефиницијом ССА игре.

Изазивач мора да дешифрује било који шифрат који није једнак шифрату

изазова. Дакле изазивач дешифрује, и даје нападачу m'.

Дакле дао је нападачу b, и сада нападач може да избаци вредност за b

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

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

примаоца поруке, то му омогућава да победи у ССА игри са

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

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

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

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

да открије који је шифрат изазова. Дакле циљ до краја ове целине

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

Изузетно је што је ово могуће, и показаћу вам

како се то ради. У ствари ССА системи које ћемо да изградимо

су управо они који се користе у стварности. Сваки пут када је неки систем покушао да примени

неки механизам шифровања јавним кључем који није био ССА безбедан, неко би пронашао

напад и успевао да га разбије. Видећемо неке примере ових напада

у неколико следећих одељака.