Криптоанализ алгоритма-А5/1

В данном разделе рассматриваются два метода криптоанализа алгоритма Д5/1, основанные на небольших недоработках авторов алгоритма при выборе разрядов регистров, образующих обратную связь регистров, и при создании не- инвертируемого механизма синхронизации (clock control). Этот механизм был призван обеспечить нелинейность работы регистров. Еще одной слабостью этого алгоритма является слишком частая инициализация алгоритма. Слишком частая инициализация алгоритма обусловлена тем, что длина кадра информации, передаваемой в системах GSM, составляет всего 228 бит и при зашифровании каждого кадра информации алгоритм инициализируется с помощью открытого номера очередного кадра. Сложность наиболее эффективных из известных на данный момент методов криптоанализа алгоритма А5/1 составляет около 245 шагов, что делает его уязвимым для аппаратных атак, но достаточно защищенным от программных атак. В методах, представленных в этой работе, после выполнения подготовительной стадии, которая проводится только один раз и состоит из 248 шагов, которые можно выполнять параллельно, атака может быть проведена в реальном масштабе времени на одном персональном компьютере,

Первый метод для своей работы требует наличия выходной последовательности алгоритма Д5/1 в течение первых двух минут разговора (около 6-106 бит), после чего вычисление ключа осуществляется примерно за одну секунду. Метод основан на широко известном парадоксе «дней рождений», который рассматривается ниже.

Второй метод требует наличия выходной последовательности алгоритма в течение примерно двух секунд разговора (около 10[1] бит), после чего вычисление ключа осуществляется за несколько минут. Метод основан на использовании графа состояний алгоритма. Оба подхода связаны между собой, но основаны на разном соотношении время/память (время, необходимое для осуществления атаки / необходимый объем доступного свободного дискового пространства для хранения заранее вычисленных данных). Методика криптоанализа поточных шифров, основанная на соотношении время/память, рассматривается ниже. Оба подхода к криптоанализу алгоритма A5!\ были проверены на существующих системах, за исключением подготовительной стадии, которая была тщательно промоделирована. Стоит отметить, что методика позволяет выбирать различные соотношения время/память (табл. 5.2).

Табл. 5.2. Характеристики различных атак на криптоалгоритм ^5/1

Атака

Количество шагов подготовительной стадии

Необходимый объем информации

Количество 73 GB дисков

Время атаки

Атака,

основанная на парадоксе «дней рождений»

242

2 мин разговора

4

1 сек

Атака,

основанная на парадоксе «дней рождения»

?48

2 мин разговора

~2

1 сек

Атака,

основанная на

графе

состояний

?48

2 сек разговора

~4

Несколько мин

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

Все атаки предполагают, что криптоаналитику известны определенные биты выходной последовательности A5/l в определенных кадрах данных. Это является стандартным предположением при криптоанализе поточных шифров, и обычно не приводится объяснение того, как можно получить эти биты. Для нашей ситуации можно отметить, что кадр формата GSM содержит ряд фиксированных полей. Сделаем также предположение, что криптоаналитик может получить все выходные биты в течение некоторого начального отрезка разговора, и его задачей является определить ключ, для того чтобы расшифровать оставшуюся часть разговора. Так как GSM-телефоны посылают новый кадр данных каждые 4.6 мсек, то каждая секунда разговора содержит около 28 кадров.

Основные подходы k криптоанализу алгоритма А5/1

Надежность алгоритма A5/1 была проанализирована в нескольких научных работах, некоторые из которых были основаны на неточном описании алгоритма, и, следовательно, они должны быть слегка переработаны. Все известные широкой общественности научные исследования в этой области можно разделить на следующие группы:

•     M. Брикено обнаружил, что во всех применяемых версиях Д5 последние десять бит 64-разрядного ключа всегда установлены в ноль. Следовательно, сложность полного перебора снижается до. Атаки, рассматриваемые в данной работе, не используют это предположение и могут применяться для вариантов A5/1, где используются все 64 бита ключа.

•     Р. Андерсон и M. Po предложили атаку, основанную на определении с помощью перебора 41 разряда состояний коротких регистров Ry и R2 и дальнейшем получении 23 бит состояния длинного регистра R^ с использованием выходной последовательности алгоритма. Однако этот тип атаки в некоторых случаях требует перебора дополнительных бит, необходимых для определения последовательности, которая управляет синхронизацией алгоритма; таким образом, конечная сложность атаки возрастала до, Предположив, что стандартный ПК может проверить около 10 миллионов вариантов в секунду, получим, что этот тип атаки требует около месяца для вычисления одного ключа.

•     Й. Голич описал усовершенствованную атаку, которая требуетшагов. Однако каждая операция в этой атаке намного сложнее, так как она основана на решении системы линейных уравнений. На практике этот алгоритм скорее всего не окажется более быстродействующим, чем предыдущий.

•     Й. Голич описал общую для всех поточных шифров атаку, позволяющую изменять соотношение время/память при криптоанализе алгоритма. За два года до этого эта атака была независимо от Голича разработана С. Бэбиджем. Атака позволяет найти ключ алгоритма Л5/1 с помощьювсего лишьобращений к заранее вычисленной таблице, состоящей из128-разрядных ячеек. Так как такая таблица занимает около 64 терабайт жесткого диска, то практическое осуществление атаки в данный момент не представляется возможным. В качестве альтернативы можно сократить необходимый объем пространства на жестком диске до 862 гигабайт, но тогда количество обращений к таблице возрастет до 228. Так как время произвольного доступа к наиболее быстрым из доступных на рынке жестких дисков составляет около 6 мс, общее время, необходимое для обращения к таблице, составляет почти три недели. Для успешного завершения такой атаки необходимо перехватить разговор, который длится более чем три часа, что также делает ее мало эффективной.

 

Источник: Acoсков А. В., Иванов М. A., Мирский А. A., Рузин А. В., Сланин А. В., Тютвин А. Н. Поточные шифры. – M.: КУДИЦ-ОБРАЗ, 2003. – 336 с.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100