Real-world stream ciphers (20 min)

В этой лекции я хочу показать несколько примеров потоковых шифров, которые используются на практике.

Я хочу начать с двух старых примеров, которые фактически не

должны использоваться в новых системах.
Но тем не менее, они все еще довольно

широко распространены и поэтому я просто хочу упомянуть их названия, чтобы вы познакомились с

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

в 1987 году. Я просто дам вам его общее описание, затем

мы поговорим о некоторых недостатках RC4 и на этом закончим. Итак RC4 занимает

переменный размер источника, для примера я взял 128

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

Первое, что она делает это расширяет 128-битный секретный ключ в 2048 бит, который

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

этого расширения, он в основном выполняет очень простой цикл, где на каждой итерации

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

очень долго и генерировать один байт все время. Сейчас RC4 , как я уже сказал, довольно

популярен. Он часто используется в протоколе HTTPS .

Сейчас, например, RC4 использует Google в своем HTTPS. А также он используется в WEP который мы

обсуждали на прошлой лекции, конечно, в WEP, он используется неправильно и

Это совершенно небезопасный путь использования его внутри WEP. Так с годами

некоторые недостатки были обнаружены в RC4, и в результате, реккомендуется, чтобы новые проекты

не использовали RC4, а использовали более современные псевдослучайные генараторы, о которых мы будем

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

Первый из них, покажется довольно странным, если вы посмотрите на второй байт

вывода RC4. Оказывается, второй байт немного ассиметричный(??). Если RC4 был

случайным то вероятность того, что второй байт будет нулем

одна к 256. Есть 256 возможных байтов, вероятность

нуля одна к 256. Случилось так, что для RC4 вероятность

два к 256, это означает, что если вы используете RC4 вывод для шифрования

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

этот ноль будет проXORен дважды

Поэтому два к 256, а не 1 к 256.
И кстати, я должен сказать, что нет

ничего особенного во втором байте. Оказывается, первый и третий байт

также ассиметричны. В настоящее время рекомендуется, если вы собираетесь использовать RC4,

игнорировать в основном первые 256 байт вывода и просто

начинать использовать выходные данные генератора, начиная с байта 257. Первая пара

байт оказалась ассиметричной, так что вы просто игнорируете ее. При второй аттаке

было обнаружено, что на самом деле, если вы посмотрите на очень длинный вывод из RC4, получается

что у вас больше шансов получить последовательность 00. Другими словами вы

скорее всего, получите шестнадцать битов по два байта ноль, ноль. Опять же если RC4

была совершенно случайная, вероятность получения ноль, ноль будет ровно 1/256

в квадрате. Оказывается, RC4 является немного ассиметричной и ассиметрия эта 1/256 в кубе. Этот

уклон фактически начинается после нескольких гигабайт данных и производятся

RC4. Но тем не менее, это как раз то, что может использоваться для прогнозирования генератора

и определенно может использоваться для различения вывода генератора

из действительно случайных последовательностей. В принципе тот факт, что ноль, ноль появляется чаще

чем он должен это и есть отличительный признак. И затем в последней лекции мы говорили о

связанных с ключом атаках, которые были использованы для атаки WEP, и которые в основном говорят, что

Если один использует ключи, которые тесно связаны друг с другом, то это на самом деле дает возможность

восстановления ключа корня. Вот такие недостатки присутствуют в RC4 и, как

результат, рекомендуется, не использовать RC4 в новых системах, а вместо нее использовать

современный псевдослучайный генератор. Ладно, второй пример, который я хочу вам показать это

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

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

content scrambling system, CSS. CSS оказывается взломанным потоковым шифром,

и мы очень легко можем взломать его, и я хочу показать вам, как работает алгоритм атаки.

Вы можете увидеть пример алгоритма нападения на слайде, но по

факту, существует множество других систем, которые в основном используют это нападение для расшифровки

зашифрованных DVD. Таким образом, CSS потоковый шифр основанный на том, что любят разработчики

аппаратной части. Он соответствует аппаратному потоковому шифру, который должен

быть легко осуществлен в аппаратной части и основывается на механизме с названием линейные

регистры сдвига с обратной связью . Таким образом линейные регистры сдвига с обратной связью - это в основном регистры

которые состоят из ячеек, где каждая ячейка содержит один бит. Что затем

происходит? В определенных ячейках есть отводы, не во всех, а на определенных

позициях. Затем эти отводы XORят и на

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

и затем первый бит становится результатом этого XOR. Так что вы можете видеть, что

этот механизм очень простой для реализации и в оборудовании занимает немного

транзисторов. Простой сдвиг вправо, последний бит уходит и первый бит просто

становится XORом предыдущих битов. Так что источник для этого LFSR

в основном является начальным состоянием LFSR.

И это является основой целого ряда потоковых шифров. Так вот несколько примеров. Как

я сказал, DVD шифрования использует два LFSRs.
Я покажу вам как это работает через

минуту. Шифрование GSM, а именно алгоритмы с названием A51 и A52. Они

используют три LFSRs. Bluetooth Шифрование — алгоритм шифрования с названием E ноль. Это все

потоковые шифры, которые используют четыре LFSRs. получается, все это - взломанные шифры,

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

реализованы аппаратно, поэтому довольно сложно сейчас изменить то, что заложено в оборудование.

Но самый простой из них, CSS, очень мило взламывается, поэтому позвольте

мне показать вам, как работает эта атака. Итак рассмотрим как фактически CSS работает.

Ключ для CSS состоит их пяти байтов, а именно 40 бит, пять раз по восемь это 40 бит.

Причина, по которой стоит ограничение 40 бит состоит в том, что DVD шифрование было

разработано тогда, когда экспорт США был разрешен только для

крипто алгоритмы с ключем в 40 бит. Поэтому разработчики CSS

были ограничены очень очень короткими ключами.
Ключ всего из 40 бит. Таким образом их проект был

следующим. В основном CSS использует два LFSR. Один является 17-битным LFSR. Другими словами,

Регистр содержит 17 бит. И второй — 25-битный LFSR,

Он немного больше - 25-бит. Исследованием LFSRs

является следующим. Ключ для шифрования, в основном выглядит таким следующим образом.

Вы начинаете с одного и объединяете первые два байта

ключа. Это и есть начальное состояние LFSR.

И тогда второй LFSR инициализируется таким же образом.

Один соединен с последним тремя байтами ключа. Это

загружается в начальное состояние LFSR.
Вы можете увидеть что первые два байта

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

LFSR — 24 бита, плюс один, в итоге 25 бит.
Заметьте, что мы использовали все пять бит

ключа. Дажее эти LFSRs в основном запускаются для восьми циклов, так что они генерируют

восемь бит вывода. И затем они идут через сумматор, который в основном производит

сложение по модулю 256.Да, это блок сложения по модулю 256. Существует еще одна

техническая вещь. В самом деле давайте добавим это к информации из

предыдущего блока. Но это не так важно. Это деталь не столь

так уместна. Хорошо, итак в каждом блоке, заметьте что мы делаем сложение по модулю 256 и

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

в следующий блок. Понятно? И затем выводим один байт за раунд.

Затем этот байт тогда конечно используется, проXORенный с соответствующим

байтом из фильма, который был зашифрован.
Итак, это очень простой потоковый

шифр, который занимает очень мало аппаратных средств для реализации. Он будет работать быстро, даже на очень

дешевом оборудовании, шифруя фильмы.
Поэтому его легко взломать

в промежутке времени от 2 до 17 переборов. Теперь позвольте мне показать вам это.

Предположим, что вы перехватили фильм, поэтому десь мы имеем

зашифрованный фильм, который вы хотите расшифровать.
Давайте скажем, что вы не имеете понятия о том

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

DVD шифрование использует MPEG файлы, так случилось, что вы знаете префикс

открытого текста, давайте просто скажем что он равен 20 байт. Мы знаем, что если вы

проXORите эти две вещи вместе, другими словами, вы делаете здесь XOR

в итоге получаете первоначальный сегмент PRG. Таким образом, вы получите

первые 20 байт вывода CSS, используя вывод PRG. Ладно, теперь

вот что мы собираемся делать. У нас первые 20 байт выходных данных. Теперь

мы делаем следующее. Мы пробуем все от двух до семнадцати возможных значений первого

LFSR. Хорошо? От двух до семнадцати возможных значений. Таким образом, для каждого значения, и для каждого из

этих двух до семнадцати начальных значений LFSR, мы запускаем

LFSR для 20 байт, понятно? Поэтому мы будем генерировать 20 байт выходов из

Первого LFSR, предполагая — для каждого от двух семнадцати возможных параметров.

Теперь вспомните, что у нас есть полный вывод CSS системы. Все что мы можем сделать это

взять этот вывод и вычесть его из двадцати байтов, которые у нас есть

из первого LFSR и, если на самом деле наша догадка для начального состояния первого

LFSR является верной, все что мы должны получить - это первый двадцатибайтовый вывод

второго LFSR. Правильно? Потому что это по определению вывод CSS

системы. Теперь получается, что глядя на 20-байтную последовательность, очень легко

сказать является ли эта 20-байтная последовательность 25-разрядным LFSR или нет. Если нет

тогда мы знаем, что наша догадка для 17-разрядного LFSR

неправильна и затем мы перейдем к следующему предположению для 17-разрядного LFSR и

затем следующей догадке и так далее и так далее.
До тех пор, пока в конце концов мы не попадем в верное первоначальное

состояние для 17-битных LFSR и тогда мы увидим, что

20 байт, которые мы получаем на выходе для 25-разрядного LFSR

в самом деле возможны на выходе для 25-разрядного LFSR. И тогда, мы не только

научимся правильно определять начальное состояние для 17-битных LFSR, мы также

узнаем верное начальное состояние 25-разрядного LFSR. И затем мы сможем предсказать

оставшиеся выводы CSS и, используя это, мы сможем расшифровать остальную часть

фильма. На самом деле мы можем восстановить оставшуюся часть открытым текстом. Отлично. Это

вещи, о который мы уже говорили. Я рассказал это довольно быстро, но надеюсь,

было ясно. Также на этот тип потового шифра есть домашнее задание

и вы получите своего рода понятие о том, как эти атакующие алгоритмы

работают. И я должен отметить, что сейчас существует множество открытых систем, которые

Используют этот метод для расшифровки данных, зашифрованных с помощью CSS. Хорошо. Итак мы уже рассмотрели два

простенький примера, давайте перейдем на более серьезные примеры, в частности лучшие

псевдослучайные генераторы приходят из так называемого eStream проекта. Этот

проект был основан в 2008 году, и они квалифицируются в основном на пяти различных потоковых

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

этих потоковых шифров, немного отличается, от тех которые мы использовали. Эти

потоковые шифры как и все имеют источник.
Кроме того они имеют, так называемый

случайный код и мы увидим, для чего используется данный случай через минуту.

Итак они принимают на входе два параметра: источник и случайный код. Мы увидим, для чего используется случайный код

через секунду. И конечно они производят очень большой выход, так что n здесь

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

никогда не будут повторяться до тех пор, пока ключ будет фиксированным. Я объясню более

подробно через секунду. Но теперь, просто думайте о нем, как об уникальном значении, которое не будет

повторятся до тех пор пока длится ключ.
И поэтому, конечно, как только вы получите PRG,

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

PRG принимает как входные данные ключ и одноразовый код. И свойство случайного кода это

пара: k запятая r, поэтому ключ запятая случайный код, никогда не — никогда не повторяются. Он

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

ключ, потому что случайный код делает пару уникальной, потому что k и r

используются только один раз. Я скажу, что они уникальны. Ладно, этот случайный код это своего рода трюк, который,

спасает нас от проблемы перехода на новый ключ каждый раз. Ладно, итак

пример из eStream, который я хочу показать вам называют Сальса двадцать. Это

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

Это достаточно интересно.
Вы должны понимать, что некоторые потоковые шифры

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

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

аппартаного обеспечения, как CSS, с помощью LFSR, частично разработано для того, чтобы сделать

реализацию дешевле. Еще одна хорошая вещь в том

что это легко осуществить его в аппаратном обеспечении и его программная

разработка является также очень быстрой. Поэтому позвольте мне объяснить, как работает Сальса. Ну, сальса

содержит 128 или 256-разрядный ключи. Только я объясню 128-разрядную версию сальсы.

Это источник. И затем он также принимает случайный код, просто как и прежде

случалось с 64 битами. И тогда он будет генерировать большой вывод. Теперь как это

на самом деле работает? Ну сама функция определяется следующим образом. В основном учитывая

ключ и случайный код, он будет генерировать очень длинную, ну, длинную псевдослучайную

последовательность, так долго, как необходимо. И он делает это с помощью этой функции, которую я обозначу

H. Эта функция H принимает три входа.
В основном ключ. Источник k,

случайный код r, а затем счетчик, который увеличивается от шага к шагу. Так он идет

от нуля до одного, двух, трех, четырех до тех пор пока нужно. Ладно? Поэтому в основном,

по оценке этой H на этом k r, но используя этот счетчик приращения, мы можем получить

последовательность такую, как нам нужно. Поэтому все что нужно сделать, это описать как эта функция

H работает. Теперь позвольте мне сделать это здесь для вас.
Она работает следующим образом. Ну мы

начинаем путем расширения состояния в нечто довольно большое, длиной 64 байт

и мы делаем это следующим образом. В основном мы придерживаемся констант в начале, так

есть tao ноль, эти четыре байта, это константа 4 байта, поэтому спецификации

Сальсы в основном дает вам значение для tao ноль. Затем мы ставим k в котором

шестнадцать байт. Затем мы ставим другую константу. Опять же это четыре байта. И

как я сказал, спецификация в основном определяет фиксированную константу. Затем мы ставим

случайный код, из восемь байтов. Затем индекс. Этот Счетчик ноль,

один, два, три, четыре, который содержит еще восемь байт. Затем мы ставим другую константу

Тау два, которая является еще четырьмя байтами.
Затем мы ставим ключ снова, это еще

шестнадцать байт. И затем, наконец, мы ставим третью константу, Тау три, которая содержит

еще четыре байта. Ладно, так, как я сказал, если вы, просуммируете все это, то получите 64

байта. Поэтому мы расширили ключ, случайны код и счетчик в 64

байт. В основном ключ повторяется дважды. И то, что мы делаем это применяем

функцию, я буду называть эту функцию маленькой h. хорошо, поэтому мы применяем эту функцию, маленькую h.

И это функция, которая является один к одному, поэтому он сопоставляется 64 байта 64 байт. Это

полностью обратимой функция, ладно? Так что эта функция h, как я говорю, это

invertable функция. Учитывая входные данные вы можете получить результат и учитывая

выход, вы можете вернуться к входу. И он предназначен специально, поэтому он имеет - легко

для реализации в аппаратных средств и b-на x 86, это очень легко осуществить, поскольку

x 86 имеет этой SSE2 инструкции набор, который поддерживает все операции, вам нужно сделать

для этой функции. Это очень, очень быстро.
В результате сальса имеет очень быстрый поток

шифр. А затем она делает это в основном снова и снова. Поэтому он применяется это

Функция h снова и он получает еще 64 байта. И так далее и так далее, в основном

Он делает это в десять раз. Итак все это здесь, говорят повторяется в десять раз, так что

в основном применяют h в десять раз. И затем сам по себе, это на самом деле не совсем случайно.

Он является не собираешься смотреть случайные потому, что как мы сказали, H является полностью invertable. Так что

Этот конечный результат, это очень легко просто инвертировать h и затем вернуться к оригиналу

входы и затем тест, что ввод имеет право структуру. Так вы сделать еще один

вещь, которая является в основном XOR входов и конечных мероприятий. На самом деле,

Извините. Это не XOR. Это на самом деле дополнением. Таким образом вы сделать дополнение слово

слово. Так что если есть 64 байта, вы сделать добавить слово в слово четырех байтов

время и, наконец, вы получите 64-байтовый вывода, и вот оно. Это весь

генератор псевдослучайных. Так что, что вся функция, мало h. И, как я

объяснил, эта вся конструкция является функция большой H. И тогда вы оценить

большой H путем увеличения счетчика I, ноль, один, два, три года. И что

даст вам псевдослучайной последовательности, которая является столько, сколько вам нужно оно быть. И

в принципе существует не signifigant нападения на это. Это имеет безопасности это

непосредственной близости от двух до 128. Мы увидим, что это означает, что более точно позже на.

Это очень быстрый потоковый шифр, аппаратного и программного обеспечения. И, насколько

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

следует сказать, что eStream проекта на самом деле имеет пять потоковые шифры как

это. Я только выбрал сальса, потому что я думаю, что это самый элегантный. Но я могу дать вам

Некоторые номера производительность здесь. Таким образом вы можете видеть, это показателей деятельности на

2,2 Гигагерца, вы знаете, x 86 типа машины.
И вы можете видеть, что на самом деле является RC4

медленный. Потому что по существу, ну он не принимает действительно преимущество

аппаратное обеспечение. Она только не байтовые операции.
И так много впустую циклов,

не используются. Но E-поток кандидатов, сальса и другие

кандидат, называется Sosemanuk. Я должен сказать, что эти eStream финалистов. Эти

на самом деле потоковых шифров, которые утверждаются eStream проекта. Вы можете видеть, что

они достигли значительную скорость.
Это 643 МБ в секунду на этот

Архитектура, более чем достаточно для кино и они на самом деле впечатляет

Тарифы. И поэтому теперь вы видели примеры двух старых потоковые шифры, которые не должны быть

используется, включая нападения на эти потоковые шифры.
Вы видели, современные поток шифры

как выглядеть с этой nonce. И вы увидите число показателей для этих

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

eStream финалистов. В частности вы могли бы использовать что-то вроде сальсы.