-
В этой лекции я хочу показать несколько примеров потоковых шифров, которые используются на практике.
-
Я хочу начать с двух старых примеров, которые фактически не
-
должны использоваться в новых системах.
Но тем не менее, они все еще довольно
-
широко распространены и поэтому я просто хочу упомянуть их названия, чтобы вы познакомились с
-
этими концепциями. Первый потоковый шифр, о котором я хочу поговорить называется 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 финалистов. В частности вы могли бы использовать что-то вроде сальсы.