Фрагмент книги
"Поточные шифры. Результаты зарубежной открытой криптологии"
(Москва, 1997 г.)

Описание криптосхемы неточное. Последние, проверенные результаты содержатся в работах
Alex Biryukov and Adi Shamir, "Real Time Cryptanalysis of the Alleged A5/1 on a PC"
Marc Briceno, Ian Goldberg, and David Wagner, "A pedagogical implementation of A5/1"


8.2 Алгоритм А5

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

Основные детали алгоритма A5 известны. Британская телефонная компания передала всю техническую документацию Брэдфордскому университету, забыв заключить соглашение о неразглашении информации. Поэтому детали о конструкции A5 понемногу стали просачиваться в печать, и в конце концов кто-то опубликовал схему в INTERNET [346].

8.2.1 Описание криптосхемы

Описание алгоритма дается по работе Йована Голича, представленной на конференции Eurocrypt '97 [152].

Пусть обозначает известный примитивный полином обратной связи РСЛОСi (регистра сдвига с линейной обратной связью) длины r i(i = 1,2,3). Известно, что r1 = 19, r2 = 22, r3 = 23. Известно также, что полиномы обратной связи прорежены (но в описанных криптоаналитических методах вскрытия этот факт не используется).

Пусть обозначает начальное заполнение РСЛОСi и пусть обозначает соответствующую последовательность максимальной длины и с периодом , порождаемую в РСЛОСi рекуррентой .

Пусть обозначает состояние РСЛОСi в момент t >= 0 в схеме с движением "стоп/вперед", описываемым ниже, и пусть обозначает средний отвод в регистре РСЛОСi , используемый для управления движением. В [346] полагается, что . Тогда управляющая движением регистров последовательность задается как

где g - это 4-значная мажоритарная функция от трех двоичных переменных, такая что если и g(s1 , s2, s3 ) = {1,2,3}, если s1 = s2 = s3 . Другими словами, значение управления движением C(t) определяет, какие РСЛОС сдвигаются для генерации выходного бита y(t) как суммы

(в каждом такте сдвигается по меньшей мере два регистра). Пусть обозначает двоичную управляющую последовательность для РСЛОСi (сдвигающийся, если ci(t) = 1 и стоящий на месте, если ci(t) = 0), которая очевидным образом получается из последовательности управления движением C. Так как последнее уравнение для y(t) формально можно использовать для генерации начального бита y(0) из S(0), то называют выходной последовательностью. Первые 100 бит выхода отбрасываются, следующие 114 бит используются в качестве гаммы для шифрования одного направления полной дуплексной связи, затем еще 100 бит отбрасываются, а следующие 114 бит используются в качестве гаммы для шифрования сигнала связи обратного направления. Таким образом, зашифрованные сообщения имеют очень короткую длину и часто происходит ресинхронизация.

Начальные заполнения РСЛОС определяются в терминах секретного и открытого ключей. Открытый ключ - это известный 22-битовый номер фрейма, генерируемый счетчиком и, следовательно, отличающийся для каждого нового сообщения. Секретный сеансовый ключ длиной 64 бита первым загружается в регистры (начальное заполнение из всех нулей избегается принудительной установкой 1 в выходе последней ячейки), а затем 22-битовый открытый ключ побитно добавляется в последовательности обратной связи каждого регистра в то время, когда они сдвигаются по описанному выше мажоритарному закону. Более строго, если обозначает открытый ключ, то для каждого t, -21 <= t <= 0, регистры сначала сдвигаются по заданному закону "стоп/вперед", а затем бит p(t) прибавляется в последнюю ячейку каждого РСЛОС. После 22 таких шагов заполнения РСЛОС образуют секретный ключ сообщения или начальные заполнения регистров при генерации шифрующей гаммы.

Как уже отмечалось, в системах GSM поточный шифр A5 используется для закрытия связи между абонентом и базовой станцией, так что фактически при связи двух абонентов шифрование происходит дважды. Это дает возможность строить криптоаналитическую атаку с известным открытым текстом (если заручиться небольшой поддержкой "помощника" на базовой станции). Кроме того, следует отметить, что 64-битовый секретный сеансовый ключ генерируется с помощью другого алгоритма, исходя из "основного" (master) ключа, специфического для каждого пользователя, и открытого случайного 128-битового ключа, передаваемого в незащищенной форме с базовой станции на аппарат абонента. Таким образом, успешное вскрытие одного или нескольких сеансовых ключей открывает дверь для криптоаналитических атак на основной ключ пользователя.

8.2.2 Криптоанализ шифра

Лобовое вскрытие. Вскоре после появления криптосхемы A5 в Internet появились и публикации о методах вскрытия этого шифра. В частности, достаточно короткие длины регистров позволяют организовать разновидность лобового вскрытия ключа на основе тотального перебора около 240 возможных вариантов: делается предположение о содержимом первых двух регистров криптосхемы, а затем содержимое третьего регистра восстанавливается по шифрующей гамме и проверяется совместность предположенных заполнений [11] (так называемый метод атаки "встреча посередине", см. Раздел 9.1). Строгих оценок для вычислительных затрат этого метода не давалось.

Корреляционный анализ. Известно, что в июне 1994 года д-р Саймон Шеферд из Брэдфордского университета должен был представить на коллоквиуме IEE в Лондоне свой корреляционный способ вскрытия A5. Однако, в последний момент его выступление было запрещено Штаб-квартирой правительственной связи Великобритании [11]. О корреляционном методе Шеферда известно следующее: (a) для восстановления начальных заполнений используется техника разреженной матрицы (была опубликована в апреле 1993г. в издании "Mobile Europe"); для вскрытия используются приемы из криптоаналитических работ Андерсона [7] и Доусона, Кларка [94].

В 1997 году опубликованы результаты корреляционного анализа A5, проведенного Йованом Голичем [152]. Поставленная им цель - определить начальные заполнения РСЛОС по известному отрезку гаммы, соответствующему одной паре "открытый текст - шифртекст". Установлено, что на самом деле для решения этой задачи требуется всего 64 последовательных бита гаммы. Построен метод, реализующий классическую стратегию "разделяй и вскрывай" и эксплуатирующий специфический для данной схемы закон движения. Средняя вычислительная сложность вскрытия оценивается величиной, примерно равной 240 .

Балансировка "время-память". Голичем [152] построен также метод вскрытия, эксплуатирующий балансировку "время-память" на базе вероятностного парадокса "дней рождений". Метод позволяет вскрывать неизвестное начальное заполнение за известное время для известного отрезка гаммы. Атака приводит к успеху, если T x M >= 263.32 , где T и M - требуемые для вычислений время и память (в 128-битовых словах), соответственно. Время предвычислений оценено величиной O(M) , а требуемое количество известных последовательностей гаммы, сгенерированных при разных открытых ключах, составляет около T / 102. Например, можно выбрать соотношение параметров T ~= 227.67 и M ~= 235.65 .

Для получения секретного сеансового ключа по определенному внутреннему состоянию регистров предложена так называемая "реверсионная атака" , эффективность которой проанализирована с помощью аппарата "критических и субкритических ветвящихся процессов [16] [171].

Цикловая структура A5. В работе У.Дж. Чамберса [70] приводится любопытный результат относительно цикловой структуры последовательностей, порождаемых всеми возможными начальными состояниями регистров криптосхемы. Оказывается, что свыше 40 процентов ключей алгоритма A5 приводят к циклу, длина которого наименьшая из всех возможных, а именно (223 - 1)4/3 бит.


Ссылки на литературу

[7] R. Anderson. "Solving a class of stream ciphers", Cryptologia, 14(3):285-288,1990

[11] R. Anderson, post to Newsgroup sci.crypt, 17 Jun 1994, Subject: A5

[16] K.B. Athreya and P.E.Ney, Branching Process. Berlin, Springer-Verlag, 1972

[70] W.G. Chambers, "On Random Mappings and Random Permutations", Fast Software Encryption - Second International Workshop, Leuven, December 1994, Springer-Verlag, Berlin, 1995, pp 22-28

[94] E. Dawson and A.Clark, "Divide and conquer attacks on certain classes of stream ciphers", Cryptologia XVIII, N 1, 1994 pp 25-40.

[152] J. D. Golic, "Cryptanalysis of Alleged A5 Stream Cipher", in Lecture Notes in Computer Science 1233; Advances in Cryptology: Proc. Eurocrypt '97, W. Fumy, Ed., May 1997, pp. 239-255, Berlin: Springer-Verlag, 1997

[171] T.H.Harris, The Theory of Branching Processes. Berlin, Springer-Verlag, 1963

[346] B. Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons, New York,1996