Real-world stream ciphers (20 min)

У цьому сегменті я хочу дати кілька прикладів потокив шифрів, які використовуються на практиці.

Я збираюся почати з двох старих прикладів, які насправді не

повиненні використовуватися в нових системах.
Але тим не менше, вони як і раніше досить

широко використовується і тому я просто хочу, щоб згадати імена, так щоб ви були знайомі з

з цими поняттями. Перший потоковий шифр, про який я хочу поговорити, називається RC4, розроблений

ще в 1987 році. І я тільки збираюся дати вам його опис високого-рівня, а потім

ми будемо говорити про деякі недоліки RC4 і залишимо його. Так RC4

з перемінним розміром насіння, тут я просто навів приклад, де він буде приймати 128 біт

як розмір зерна, який потім будуть використовуватися в якості ключа для потокового шифру.

Перше, що він робить, він розширює 128-бітний секретний ключ до 2048 біт, який

буде використовуватися як внутрішній стан для генератора. А потім, після того, як це зробить

це розширення, він в основному виконує дуже простий цикл, де кожна ітерація

цього циклу виводить один байт вихідних. Так, по суті, ви можете запустити генератор

так довго, як ви хочете, і створити один байт в той час. Тепер RC4, насправді, як я сказав,

досить популярний. Він використовується в протоколі HTTPS, і досить часто.

У ці дні, наприклад, Google використовує RC4 в своєму HTTPS. Він також використовується у WEP як ми

обговорювалися в останньому сегменті, але, звичайно, у WEP, воно неправильно і

це повністю небезпечно, так, як воно всередині WEP. Так, протягом багатьох років,

деякі недоліки були знайдені в RC4, і як наслідок, рекомендується, щоб нові проекти

фактично не використовували RC4, а використовувати більш сучасні псевдо-генератор випадкових чисел, як ми будемо

обговорити в кінці відрізка. Отже, дозвольте мені просто згадати два недоліки.

Таким чином, перший з них, це свого роду дивні принципі, якщо ви подивитеся на другий байт

виходу RC4. Виявляється, другий байт трохи упереджено. Якщо RC4 був

зовсім випадковим, ймовірність того, що другий байт буває рівним нулю

б рівно через 256. Є 256 можливих байтів, ймовірність того, що

це нуль повинна бути одна на 256. Буває так, що для RC4 ймовірності

насправді два більше 256, що означає, що якщо ви використовуєте вихід RC4 для шифрування

повідомлення, другий байт, швидше за все, не будуть зашифровані взагалі. Іншими словами, це буде

XOR з нулем в два рази ймовірність того, що він повинен.

Так, дві за 256, замість одного за 256.
І до речі, я повинен сказати, що немає

нічого особливого в другому байті. Виявляється перший і третій байт

також упереджений. І справді тепер рекомендується, якщо ви збираєтеся використовувати RC4,

що ви повинні зробити, це ігнорувати основному перші 256 байт вихідний і просто

почати використовувати вихід генератора, починаючи від 257 байта. Перша пара

байтів, виявляється упередженною, тому ви просто ігноруєте їх. Друга атака що

була виявлена, що насправді, якщо ви подивитеся на дуже довге виведення з RC4 так буває

що ви швидше за все, отримаєте послідовність 00. Іншими словами, ви

швидше за все, отримаєте шістнадцять біт, два байти нуль, нуль, більше ніж потрібно. Знову ж таки якщо RC4

був цілком випадковий, ймовірність побачити нуль, нуль буде точно 1/256

в квадраті. Виявляється RC4 є трохи упередженим та зсуву складає 1/256 у кубі. Його

виявляється, це упередження фактично починається після того, як кілька гігабайт даних що виробляються

RC4. Але тим не менш, це щось, що може використовувати для прогнозування генератора

і безумовно ним можна відрізнити вихід генератора

з дійсно випадковою послідовностю. Основне те, що нуль, нуль частіше з'являється

чим потрібно є у distinguisher. А потім в останньому сегменті ми говорили про

пов'язані з ключем атаки, які були використані для нападу на WEP, які в основному говорять, що

якщо один використовує ключі, які тісно пов'язані один з одним тоді це дійсно можливо

щоб відновити кореневий ключ. Так що ці недоліки, які, як відомо, RC4 і як на

результат, рекомендується в нових систем фактично не використовувати RC4 і замість цього використовувати

сучасні генератори псевдовипадкових. Гаразд, другий приклад, я хочу дати

вам зламаний потоковий шифр, який використовується для шифрування DVD фільмів.Коли ви купуєте DVD

у магазині, фактично фільм шифрується за допомогою потокового шифру під назвою на

система шифрування змісту, CSS. CSS виявляється зламанним потоковим шифром,

і ми дуже легко можна взламати його, і я хочу, показати вам, як атакуючий алгоритм

працює. Ми робимо це, так що ви можете бачити приклад алгоритма атаки, але

насправді, є багато систем, що в основному використовують цю атаку для розшифровки

зашифрованих дисків DVD. Так що CSS потоковий шифр заснований на те, що апаратні

дизайнери люблять. Він призначений до шифрованного потоку обладнання, яке повинна бути

легко здійсненним в устаткуванні і на основі механізму під назвою в лінійний

зворотній зв'язок змінити реєстр. Так нелінійним зворотним зв'язком зсувний регістр в основному зареєструвати

що складається з клітинок, де кожна клітинка містить один біт. Тоді в основному

що відбувається, є ці крани в певних клітинок, не всі клітинки, певні

позиції називаються крани. І тоді ці крани каналу в на XOR а потім в

Кожен цикл, зрушення зареєструвати зрушення вліво. Останній шматок падає

і перший біт, то стає результатом цього XOR. Так що ви можете бачити, що

Це дуже простий механізм реалізації і в обладнанні займає дуже мало

транзисторів. Просто зрушення прямо, останній біт падає з і перший біт тільки

стає XOR попередніх бітів. Так що насіння для цього LFSR

в основному, це початковий стан на LFSR.

І це в основі ряд потік шифрів. Нижче наведено кілька прикладів. Так, як

Я сказав, DVD шифрування використовує два LFSRs.
Я покажу вам, як це працює просто на

друге. GSM шифрування, вони алгоритмів, що називається A51 і A52. І що

три LFSRs. Bluetooth використовує шифрування — алгоритм під назвою Електронна нуля. Вони всі

потік шифри, і що використання чотирьох LFSRs. виявляється всі ці порушуються погано,

і дійсно, дійсно не слід довіряти для шифрування трафіку, але вони всі

реалізовані в апаратного забезпечення, так що це трохи складно зараз, змінити яке обладнання

робить. Але найпростіший з них, CSS, насправді має милий напасти на нього, так що хай

мені показати вам, як працює атака. Отже, давайте описати, як CSS насправді працює. Так,

ключ для CSS п'ять байт, а саме 40 біт, п'ять разів восьмий – 40 біт. На

причина, вони хочуть обмежити себе до лише 40 біт є був DVD шифрування

розроблений в той час, де експортувати США правил дозволено лише для експорту

crpyto алгоритми, де ключ був лише 40 біт. Таким чином були дизайнерів CSS

вже обмежена до дуже, дуже короткий ключів.
Просто 40 біт ключі. Отже, їх дизайн працює

наступним чином. В основному, CSS використовує два LFSR. Один, LFSR 17-біт. Іншими словами,

Реєстр містить 17 біти. А інші є 25-розрядні LFSR,

Це трохи більше часу, 25-розрядні LFSR. І як ці LFSRs seeded

виглядає наступним чином. Так ключ для шифрування, в основному виглядає наступним чином.

Ви починаєте з один, і використовується для його перші два байти

ключ. І це початковий стан на LFSR.

А потім другий LFSR в основному intitialized так само.

Один об'єднані останніх трьох байт ключ. Ось

завантажені в початковий стан на LFSR.
Ви можете побачити, що перші два байти

шістнадцять біти, плюс провідних один, що сімнадцять біти в цілому, у той час як другий

LFSR є 24 біта, плюс один, який є 25 біти.
І ви помітите, що ми використовували всі п'ять біти

ключ. Так, то ці LFSRs в основному балотуватися на вісім циклів, так що вони генерувати

8 біт виводу. І тоді вони пройти через цей суматора, яка в основному робить

Додавання за модулем 256. Так, так що це вікні Додавання за модулем 256. Є ще один

Технічні речі, що відбувається. Справді, давайте фактично — також додав є нести від на

попередній блоку. Але це не так важливо. Це докладно, що не так

відповідні. Гаразд, так що кожен блок, ви помітите, що ми робимо додавання за модулем 256 і

Ми ігнорування на нести, але до виконання в основному додається як нуль або один до на

Додавання наступний блок. Добре? І потім, в основному це вихід один байт на раунд.

Гаразд, і то цей байт, то звичайно використовується, XOR-Ед з підходящим

байт фільм, який під час шифрування.
Добре, так що це дуже простий потік

шифр, вона займає дуже мало устаткування для реалізації. Вона буде працювати швидко, навіть на дуже

Дешеві устаткування і вона буде шифрувати фільми.
Так виходить, що це дуже просто розірвати

у час приблизно двох до в сімнадцять років. Тепер, дозвольте мені показати вам, як.

Тому припустимо, що ви перехоплювати фільми, так що тут ми є

зашифровані фільму, які потрібно розшифрувати.
Так що давайте говорити, що це всі зашифровані так

вас не знаю, що там всередині тут.
Однак, так буває, що тільки тому, що

DVD шифрування використовує файли MPEG, так буває, якщо ви знаєте про префікс у

звичайний текст, давайте просто сказати, може бути це двадцять байт. Ну, ми знаємо, що якщо ви

XOR ці дві речі разом, так само в інших словах, ви робите XOR тут,

те, що ви отримаєте це початковий сегмент на PRG. Таким чином, ви отримаєте на

перші двадцять байт вихідний CSS, вихід цього PRG. Гаразд, так що тепер

Ось що ми будемо робити. Так, у нас є перші двадцять байт виводу. Зараз

Ми виконайте такі дії. Ми спробуємо всі двох до сімнадцять можливі значення першого

LFSR. Добре? Таким чином, два сімнадцять можливих значень. Так що для кожного значення, так і для

кожен з цих двох до сімнадцять початкові значення у LFSR, ми збираємося працювати на

LFSR для двадцяти байт, добре? Так що ми будемо генерувати двадцять байт виходи з цієї

Перший LFSR, припускаючи, — для кожної з двох сімнадцять можливі параметри.

Тепер пам'ятаю, ми маємо повний вихідний CSS системи. Так що ми можемо зробити це ми

можна прийняти цей висновок, який ми маємо. Вилучення його з двадцяти укусів і що ми

отримав від першого LFSR і якщо насправді наші припущення для початкового стану перший

LFSR є правильним, що ми повинні отримати є перші двадцять байтове вихід на

Другий LFSR. Право? Тому що, за визначенням, що вихід з CSS

система є. Тепер виявляється що дивлячись на 20-байтове послідовність, це дуже легко

щоб сказати, чи Ця послідовність 20-байтове прийшли з 25-розрядні LFSR, чи ні. Якщо це

не, то ми знаємо, що наші припущення за 17-розрядні LFSR

неправильні і потім ми перейдемо до наступного вгадати для LFSR 17-біт і

наступний думаю, і так далі і так далі.
Поки врешті-решт ми потрапили права початковий

держави за 17-трохи LFSR і тоді ми будемо реально отримати, ми побачимо, що

20 байтів, що ми отримуємо, як кандидат вихід для 25-розрядні LFSR

справді можливий вихід для 25-розрядні LFSR. І потім, не тільки буде ми повинні

дізнався правильну початковий стан для LFSR 17-біт, ми повинні також

дізнався правильну початкового стану 25-розрядні LFSR. І тоді ми можемо передбачити, що

залишаючись виходи, CSS і, звичайно, використовуючи, що, ми можемо дешифрувати залишок

фільм. Ми насправді можна відновити залишилися звичайний текст. Добре. Це

те, що ми говорили раніше. Так, я сказав це трохи швидко, але, сподіваюся,

було ясно. Ми також будемо робити домашнє завдання здійснювати на цей тип потоку

шифри і ви родом з отримаєте точку як ці атаки алгоритмів

роботи. І я повинен згадати, що є багато відкритих вихідних систем тепер, що насправді

використовувати цей метод, щоб дешифрувати дані, зашифровані CSS. Гаразд, так що тепер, що ми вже бачили два

слабкі прикладів, давайте перейдемо до найкращих прикладів і зокрема тим краще

псевдовипадкових генератори приходять від те, що називається eStream проекту. Це є

проект, що уклали в 2008 році, і вони право в основному п'ять різних потоку

шифри, але тут я хочу представити тільки один. Тому перше всіх параметрів для

Ці шифри потоку є трохи інакше, ніж те, що ми звикли. Так, ці

потік шифрів, як звичайно, вони мають насіння.
Але крім цього них, що і в

званих даний час і ми побачимо, що даний час використовується для в хвилину. Так

вони приймають два входи, насіння і в даний час.
Ми побачимо, що в даний час використовується для

за секунду. І звичайно, вони виробляють дуже великі виводу, так n, ось

набагато, набагато, набагато більше, ніж s. Тепер, коли я кажу nonce, що я маю на увазі — це значення, що з

ніколи не повторити тих пір, як ключ виправлена. І я поясню, що в більш

докладно в за секунду. Але зараз, просто думаю, що це як унікальну значення, ніколи не

повторення тих пір, як ключ це те ж саме.
І тому, звичайно, якщо у вас є цей PRG

Ви б зашифрувати, ви отримаєте шифр потоку як і раніше, за винятком зараз як бачите, на

PRG приймає як введення ключа і в даний час. І є власність в даний час

що пара, k r кома, так ключових кома nonce, що ніколи не — ніколи не повторюється. Він має

ніколи не використовуються більше одного разу. Так суть в тому, що можна повторно використовувати ключ, повторне використання

ключ, тому що в даний час робить пара унікальний, тому що k і r, лише

використовується один раз. Я скажу, що вони унікальні. Добре, так що ця nonce роду милий трюк що

рятує нас біда з переїзд в новий ключ кожного разу. Гаразд, так що зокрема

приклад з eStream, що я хочу, щоб показати вам, називається сальса двадцять. Це є

потік шифр, який призначений для реалізації програмного забезпечення та устаткування

реалізацій. Це навіть цікавий.
Ви розумієте, що деякі потік шифри

розроблений для програмного забезпечення, як RC4.
Все це робить покликана зробити

Програмна реалізація працювати швидко, в той час як інші потік шифри призначені для

устаткування, як CSS, за допомогою LFSR, які особливо покликаний зробити устаткування

реалізацій дуже дешево. Крім того, гарна річ про це є те, що

Таким чином, що це, як легко реалізувати його в апаратне та програмне забезпечення

Реалізація є також дуже швидко. Отже, дозвольте мені пояснити, як працює сальса. Ну, сальса

приймає або 128 або 256 біт ключі. Тільки я поясню 128-бітна версія сальси.

Так що це насіння. А потім вона також вимагає даний час, як перед, яка

трапляється бути 64 біт. І тоді він буде генерувати великі виводу. Тепер як це робить

дійсно працюють? Ну, сама функція визначається наступним чином. В основному, враховуючи

ключ і в даний час, він буде генерувати дуже довго, Ну, давно псевдовипадкових

послідовність, так довго, як це необхідно. І це зроблю це за допомогою цієї функції, які я будете позначимо

H. це функція h бере три входи.
В основному ключ. Ну, насіння k

nonce r а потім лічильник, який збільшує від кроку до кроку. Так само...

від нуля до один, два, три, чотири як тривалих як [нечутний] ми, щоб бути. Добре? Тому в основному,

на оцінці цього h на цьому k r, але з використанням цього incrementing лічильник, ми можемо отримати на

послідовності, що це так довго, як ми хочемо. Так що все, що потрібно зробити, це описати як ця функція

H працює. Тепер дозвольте мені зробити це тут для вас.
Як це працює, виглядає наступним чином. Ну, ми

Почніть шляхом розширення Штатів в щось досить великий, який є 64 байт

Це давно і ми зробити наступним чином. В основному ми будемо дотримуватися константа на початку, так

Існує Тао нуль, ці чотири байт, це чотири байт константа, так специфікації для

Сальса в основному надає значення для Тао нуль. Потім ми покласти k, у яких є

шістнадцять байт. Потім ми покласти іншу константа. Знову ж таки це чотири байт. І

як я вже сказав, специфікації в основному призначення те, що Ця фіксована константа. Потім ми покласти

в даний час, який є 8 байт. Потім ми ставимо індексу. Це лічильник нуль,

один, два, три, чотири, яка є ще вісім байт. Потім ми покласти іншу константа

Тау два, яка є ще чотирьох байтів.
Потім ми покласти ключ знову, це ще одна

шістнадцять байт. І потім, нарешті ми третій постійною, Тау три, яка є

інший чотирьох байтів. Добре, так як я вже сказав, якщо ви підсумувати дані, ви бачите, що ви отримаєте 64

байт. Тому в основному ми розширювались ключ і в даний час і лічильник на 64

байт. В основному ключ повторюється двічі я думаю. І тоді ми робимо ми застосовувати на

функція, я буду називати h цей функціональний мало. добре, так що ми застосувати цю функцію, мало h.

І це функція, що один до одного, так що це співставляє 64 байт 64 байт. Це є

повністю оборотна функції, добре? Тому ця функція h, як я вже сказав, це є

invertable функції. Так дано вводу можна отримати на виході і з огляду на

Ви можете повернутися до вводу виводу. І призначений спеціально тому вона має на - легко

для реалізації в устаткування і b-x-86, це дуже легко реалізувати, тому що

x86 має цей SSE2 інструкція встановити, який підтримує всі операції потрібно робити

для цієї функції. Це дуже, дуже швидко.
В результаті, сальса має дуже швидкий потік

шифр. І тоді він робить це в основному знову і знову. Так що це відноситься це

Функція h знову і він отримує інший 64 байт. І так далі і тому подібне, в основному

він робить це в десять разів. Добре, так що все це тут, сказати повторюється в десять разів, так

в основному застосовуються h десять разів. А то сам по собі, це насправді не досить випадковий.

Це не буде дивитися випадкові, тому що, як ми вже казали, H є повністю invertable. Так, зважаючи

Цей кінцевого виводу, це дуже легко, просто Інвертувати h і потім повернутися до оригіналу

входи і потім тест, що введення має право структури. Так робити ще одна

річ, яка є в основному XOR, входи і виходи остаточний. Фактично,

Вибач. Це не є XOR. Це насправді доповненням. Так ви зробити доповнення-слово

слово. Так що якщо 64 байт, ви робите слово за словом доповнення чотирьох байтів в на

час і, нарешті, ви отримаєте 64-байтове виводу, і все. Це весь

генератор псевдовипадкових. Так що, що є функції, мало h. І, як я

пояснили, це цілий будівництво тут є функція великих h. І тоді вам оцінити

Великий h на збільшує лічильник я з нуля, один, два, три року. І що

дасть вам псевдовипадкових послідовності, що це так довго, як це буде потрібно. І

в основному, це не signifigant зазнає нападу на це. Це має безпеки що з

дуже близько двох до 128. Ми побачимо, що це означає, що більше саме пізніше на.

Це дуже швидкий потік шифр, як апаратного і програмного забезпечення. І, наскільки

Ми можемо сказати, що це, як видається, непередбачуваний, як це потрібно для потоку шифр. Так я

треба сказати, проект eStream насправді має п'ять потік шифри як

це. Я тільки вибрав сальса, тому що я думаю, це самий елегантний. Але я можу дати вам

деякі продуктивність номери тут. Так що ви можете бачити, це продуктивність чисел на на

2.2 Гігагерц, ви знаєте, x86 типа.
І ви можете бачити, що RC4 фактично на

повільний. Тому, що по суті, Ну це не дійсно скористатися на

устаткування. Він тільки робить байтів операцій.
І так багато даремно циклів,

не використовується. Але E-потік кандидатів, сальса та інші

кандидат називається Sosemanuk. Я повинен сказати, що це eStream фіналістів. Ці

власне потік шифрів, які затверджені eStream проекту. Ви можете бачити, що

вони досягли значних ставки.
Це 643 мегабайт за секунду на цьому

Архітектура, більш ніж достатньо для фільму і ці насправді просто вражало

ставки. І тепер ви бачили приклади двох старі шифрів потоку, що не повинно бути

використовуються, включаючи нападів на ці потік шифрів.
Ви бачили, сучасний ефір шифри

схожі з цього nonce. І ви побачите цифри продуктивності для цих

сучасний ефір шифрів, так що якщо вам трапиться потрібен шифр потоку ви могли б використовувати один з

eStream фіналістів. Зокрема, ви могли б використовувати щось подібне до сальси.