Дешифровка с помощью Kraken

Проект, публично анонсированный в августе 2009 года предоставил способ эффективного взлома шифра A5/1. Имя проекта без особой фантазии тоже было A5/1 [14]. Однако, в июле 2010 года поисковые таблицы для этого проекта были реализованы под именем Kraken. Чтобы избежать любой путаницы с самим шифром, мы будем называть проект A5/1 именем Kraken.

Проект Kraken главным образом состоит в создании больших таблиц в рамках обмена времени на память. Это было предложено ранее [15], но отличительный фактор этого нового проекта в том, чтобы вместо просчёта таблиц в одном месте, кто-угодно в интернете может присоединиться к расчётам и делиться ими с помощью битторрента [16]. Код вычисления этих таблиц может быть загружен и запущен на разных типах графических карт NVIDIA и ATI.

Идея, лежащая в основе этих таблиц, состоит в следующем. Содержимое множества импульсов передачи данных, которые передаются в эфире при включенном шифровании может быть в большей части угадано. Это даёт образцы известного открытого текста. XOR этих образцов открытого текста с текущими полученными шифртекстами даёт образцы гаммы шифрования. Теперь таблицы выступают в роли кодовой книги с 64 битами гаммы, которые связаны с внутренними состояниями A5/1, дающими соответствующие фрагменты гаммы.

Существуют 2^64 возможных внутренних состояния для A5/1. Это число слишком велико для того, чтобы получить отображение всех внутренних состояний. Вместо того, чтобы просто сохранять все внутренние состояния и соответствующие им 64-битные фрагменты гаммы, выполняется просчёт больших цепочек, в которых каждые 64 бита выхода снова используются как внутреннее состояние. Сохраняются только начальные и конечные точки этих цепочек. Теперь, как только восстановлен фрагмент гаммы, атакующий начинает считать цепочку из этой гаммы и для каждого проверенного звена он проверяет, нет ли полученного значения в таблице. Как только атакующий найдёт совпадение, то он может восстановить внутреннее состояние оригинальной цепочки из сохранённого значения начальной точки — из исходного состояния ключа сессии, который был использован для вычисления текущей коммуникации. Это уменьшает размер таблиц, но время атаки возрастает и таблицы больше не гарантируют, что внутреннее состояние может быть найдено. Но значительно большая проблема состоит в перекрывании цепочек. Множество различных внутренних состояний может дать при вычислении те же самые 64 бита гаммы, что приводит к перекрыванию цепочек и покрывает одинаковую часть ключевого пространства. Это делает таблицы значительно менее эффективными. Для контрмер против некоторых из этих проблем используется комбинация двух техник — одной, увеличивающей время атаки и одной, снижающей число перекрывающихся цепочек. Эти техники состоят соответственно в различающихся точках и радужных таблицах. Комбинирование этих техник было предложено до [17,18].

С учётом слияния цепочек нужно произвести определённое число различных таблиц. Эти таблицы также должны покрывать определённый объём ключевого пространства. Незадолго до написания данной статьи был реализован набор таблиц, названный "Берлинским набором", совместно с утилитой поиска Kraken. Таблицы были распространены через битторент в специальном транспортном формате. Они составили на этот момент 1,5 Тбайта данных. Транспортный формат может быть перекодирован в актуальный формат чтения, занимающий всего 1,7 Тбайт дискового пространства. На тот момент таблицы покрывали 22% ключевого пространства. Если ключ содержится в таблице, то Kraken обычно находит его за несколько минут (в среднем от 1 до 4 минут) на машине с процессором Intel Core2 Quad 2.33 GHz с таблицами, разделёнными на несколько дисков. Использование твёрдотельных накопителей вместо обычных жёстких дисков значительно увеличивает скорость поиска, но повышает затраты.

Значительным недостатком этого решения является требование безошибочного приёма последовательности 64 бит. Единственная невыявляемая ошибка в приёме сделает невозможным получение сессионного ключа из этих таблиц. В GSM шифрование выполняется поверх кодов коррекции ошибок, поэтому коррекция ошибок не может быть применена для поиска ошибок приёма до шага дешифровки. В настоящее время приём с USRP при запущенном AirProbe не обеспечивает безошибочного приёма, необходимого для Kraken.