Самопрореживаемый генератор

Самопрореживаемый (self-shrinking) генератор [1050] является вариантом прореживаемого генератора. Вме­сто двух LFSR используется пара битов одного LFSR. Протактируйте LFSR дважды. Если первым битом пары будет 1, то второй бит будет выходом генератора. Если первый бит - 0, сбросьте оба бита и попробуйте снова. Хотя для самопрореживаемого генератора нужно примерно в два раза меньше памяти, чем для прореживаем о-

го, он работает в два раза медленнее.

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

16.5 А5

А5 - это потоковый шифр, используемый для шифрования GSM (Group Special Mobile). Это европейский стандарт для цифровых сотовых мобильных телефонов. Он используется для шифрования канала "телефон-базовая станция". Оставшаяся часть канала не шифруется, телефонная компания может легко сделать что-нибудь с вашими разговорами.

Вокруг этого протокола ведутся странные политические игры. Первоначально предполагалось, что крипто­графия GSM позволит запретить экспорт телефонов в некоторые страны . Теперь ряд чиновников обсуждает, не повредит ли А5 экспортным продажам несмотря на то, что он так слаб, что вряд ли сможет служить препятс т-вием. По слухам в середине 80-х различные секретные службы НАТО сцепились по вопросу, должно ли шифр о-вание GSM быть сильным или слабым. Немцам была нужна сильная криптография, так как рядом с ними нах о-дился Советский Союз. Взяла верх другая точка зрения, и А5 представляет собой французскую разработку.

Большинство деталей нам известно. Британская телефонная компания передала всю документацию Брэ д-фордскому университету (Bradford University), не заставив подписать соглашение о неразглашении. Информа­ция где-то просочилась и наконец была опубликована в Internet. A5 описывается в [1622], также в конце этой книги приведен код этого протокола.

А5 состоит из трех LFSR длиной 19, 22 и 23, все многочлены обратной связи - прорежены. Выходом являет­ся XOR трех LFSR. В А5 используется изменяемое управление тактированием. Каждый регистр тактируется в зависимости от своего среднего бита, затем выполняется XOR с обратной пороговой функцией средних битов всех трех регистров. Обычно на каждом этапе тактируется два LFSR.

Существует тривиальное вскрытие, требующее 2⁴⁰ шифрований: предположите содержание первых двух LFSR и попытайтесь определить третий LFSR по потоку ключей. (Действительно ли такой способ вскрытия возможен, остается под вопросом, который скоро будет разрешен разрабатываемой машиной для аппаратного поиска ключей [45].)

Тем не менее, становится ясно, что идеи, лежащие в основе А5, неплохи. Алгоритм очень эффективен. Он удовлетворяет всем известным статистическим тестам, единственной его слабостью является то, что его регис т-ры слишком коротки, чтобы предотвратить поиск ключа перебором . Варианты А5 с более длинными сдвиговы­ми регистрами и более плотными многочленами обратной связи должны быть безопасны .

16.6 Hughes XPD/KPD

Этот алгоритм был предложен Hughes Aircraft Corp. Эта фирма встроила его в армейские тактические рации и оборудование поиска направления для продажи за границу. Алгоритм был разработан в 1986 году и получил название XPD, сокращение от Exportable Protection Device - Экспортируемое устройство защиты. Позднее он был переименован в KPD - Устройство кинетической защиты - и рассекречен [1037, 1036].

Алгоритм использует 61-битовый LFSR. Существует 2¹⁰ различных примитивных многочлена обратной свя­зи, одобренных NSA. Ключ выбирает один из этих многочленов (хранящихся где-то в ПЗУ), а также начальное состояние LFSR.

В алгоритме восемь различных нелинейных фильтров, каждый из которых использует шесть отводов LFSR, выдавая один бит. Объединяясь, эти биты образуют байт, который и применяется для шифрования или деши ф-рирования потока данных.

Этот алгоритм выглядит очень привлекательно, но у меня есть определенные сомнения . NSA разрешило его экспорт, следовательно должен быть способ вскрытия порядка, не большего чем 2 ⁴⁰. Но какой?

16.7 Nanoteq

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

Более или менее этот алгоритм описан в [902, 903]. Он использует 127-битовый LFSR с фиксированным многочленом обратной связи, ключ представляет собой начальное состояние регистра . При помощи 25 элемен­тарных ячеек 127 битов регистра превращаются в один бит потока ключей. У каждой ячейки 5 входов и один выход:

f(x_b х₂, х₃, х₄, х₅) = х_х + х₂ + {х_х + х₃) (х₂+ х₄ + х₅) + (х_х + х₄) (х₂ + х₃) + х₅

Каждый выход функции подвергается операции XOR с некоторым битом ключа. Кроме того, существует секретная перестановка, зависящая от конкретной реализации и не описанная в статьях подробно . Этот алго­ритм доступен только в аппаратном виде.

Безопасен ли он? Я не уверен. Ряд интересных факсов, передаваемых между полицейскими участками, ин о-гда появлялся в либеральных газетах. Это вполне могло быть результатом американской, английской или сове т-ской разведывательной деятельности. Росс Андерсон (Ross Anderson) предпринял ряд первых шагов, криптоа-нализируя этот алгоритм в [46], я думаю, что скоро появятся новые результаты.

16.8 Rambutan

Rambutan - это английский алгоритм, разработанный Communications Electronics Security Croup (Группа по безопасности электронных коммуникаций, одно из объединений, использованное CCHQ). Он продается только в виде аппаратного модуля и одобрен для защиты документов вплоть до грифа "Конфиденциально" . Сам алго­ритм засекречен, и микросхема не предназначена для широкой коммерческой продажи .

Rambutan использует 112-битовый ключ (плюс биты четности) и может работать трех режимах: ЕСВ, СВС, и 8-битовый CFB. Это сильный аргумент в пользу того, что этот алгоритм - блочный, но слухи утверждают иное. Предположительно это потоковый шифр с LFSR. У него пять приблизительно 80-битовых сдвиговых р е-гистров различной длины. Полиномы обратной связи значительно прорежены, в каждом из них всего лишь 10 отводов. Каждый сдвиговый регистр обеспечивает четыре входа для очень большой и сложной нелинейной функции, которая и выдает единственный бит.

Почему Rambutan? Возможно из-за фрукта, который колючий и неприступный снаружи, но мягкий и неж­ный внутри. Но с другой стороны никакой причины может и не быть.

16.9 Аддитивные генераторы

Аддитивные генераторы(иногда называемые запаздывающими генераторами Фиббоначи) очень эффек­тивны, так как их результатом являются случайные слова, а не случайные биты [863]. Сами по себе они не безопасны, но их можно использовать в качестве составных блоков для безопасных генераторов .

Начальное состояние генератора представляет собой массив и-битовых слов: 8-битовых слов, 16-битовых слов, 32-битовых слов, и т.д.: Х_ъ Х₂, Х_ъ, ..., Х_т. Это первоначальное состояние и является ключом. г-ое слово генератора получается как

X_t = (X_t._a + X__b + Х,__с + + X_L._m) mod 2"

При правильном выборе коэффициентов а, Ъ, с, . . . , тпериод этого генератора не меньше 2^я-1. Одним из требований к коэффициентам является то, что младший значащий бит образует LFSR максимальной длины.

Например, (55,24,0) - это примитивный многочлен mod 2 из 14-й. Это означает, что длина следующего адди­тивного генератора максимальна.

X_i = ^_i.₅₅ +X_i._v) mou2ⁿ

Это работает, так как у примитивного многочлена три коэффициента . Если бы их было больше, для получе­ния максимальной длины потребовались бы дополнительные условия . Подробности можно найти в [249].

Fish

Fish - это аддитивный генератор, основанный на методах, используемых в прореживаемом генераторе [190]. Он выдает поток 32-битовых слов, которые могут быть использованы (с помощью XOR) с потоком открытого текста для получения шифротекста или с потоком шифротекста для получения открытого текста . Название алго­ритма представляет собой сокращение от Fibonacci shrinking generator - прореживаемый генератор Фиббоначи.

Во первых используйте два следующих аддитивных генератора. Ключом является начальные состояния этих генераторов.

B_l = (B_l.₅₂ +B_lA9) mod 2³²

Эти последовательности прореживаются попарно в зависимости от младшего значащего бита В,: если его значение равно 1, то пара используется, если 0 - игнорируется . С, - это последовательность используемых слов Ai, a Dj - это последовательность используемых слов Д. Для генерации двух 32-битовых слов-результатов К_у и K_2j+l эти слова используются парами - C_2j, C_2j+h D_2j, D_2j+l.

E_2j = C_2j © (D_2j, a D_2j+l)

F2j = D2_J+1 a (Ej, a C2j+i)

K2j = E2j ® F2j

K2j+_l = C2j+_l © F2j

Этот алгоритм быстр. на процессоре i486/33 реализация Fish на языке С шифрует данные со скоростью 15-Мбит/с. К сожалению он также не безопасен, порядок вскрытия составляет около 2⁴⁰ [45].