Исследование механизма криптозащиты RFID-карты Hitag и его уязвимостей для атак

Данная работа посвящена исследованию защищенных носителей информации, использующих технологию радиочастотной идентификации (RFID). Эта технология широко используется во всем мире в десятках применений. С некоторым отставанием, но весьма интенсивно она развивается и в России. Работа касается одного из применений RFID, а именно в системах безопасности объектов, в частности, в системах контроля и управления доступом (СКУД).

Актуальность и новизна темы заключается в том, что в настоящее время в российских системах контроля и управления доступом с применением RFID в подавляющем большинстве случаев применяются незащищенные носители (карты) и даже чаще всего типа read only. Существует запрос на повышение надежности ограничения доступа на режимные объекты и предприятия. Рассмотрению подлежит криптозащищенная карта Hitag.

1 Принципы построения и области применения RFID-систем

Система радиочастотной идентификации состоит из 2 основных компонентов:

транспондер;

считывающее устройство.

Транспондеры могут быть выполнены в виде диска, ключа, брелока, бесконтактной карты, этикетки и других конструкций. Преимущество формы бесконтактной чип-карты для использования в RFID-системах с индуктивной связью заключается в большой площади антенны, представляющей собой плоскую катушку, благодаря чему данные транспондеры могут иметь большую дальность действия. Кроме того, эта форма наиболее удобна при переносе, хранении. Поэтому объектом исследования являются ВЧ RFID-карты, используемые в системах контроля и управления доступом (СКУД), виды атак и методы защиты от них.

Системы RFID находят свое применение в самых различных областях, вот лишь некоторые из них:

системы идентификации животных;

контроль доступа;

системы продажи билетов, в том числе на общественном транспорте;

система eurobalise;

электронные иммобилайзеры и др. [1].

Это лишь некоторые сферы применения систем RFID.

Несмотря на активную деятельность компаний — производителей RFID продукции стоит отметить, что на Российском рынке пока существуют некоторые факторы, сдерживающие продвижение RFID: высокая стоимость оборудования; низкий уровень технологической базы, используемой на предприятиях потребителя; нехватка российских стандартов; низкая осведомленность потребителей.

Применение RFID особенно хорошо отработано и распространено в системах контроля и управления доступом.

Существует ряд компаний, которые зарекомендовали себя в качестве крупнейших производителей микросхем для RFID-меток и считывателей, среди них NXP Semiconductors, Infineon, Texas Instruments, Inside, EM Marin, и другие. Безусловным лидером производства микросхем для бесконтактных микросхем и RFID является NXP Semiconductors: на долю этой компании приходится 80 %. На рынке представлен огромный выбор RFID-носителей (карт): Hitag, Mifare 1K Classic, Mifare Plus, Mifare Ultralight, Mifare Desfire, HID iCLASS, NFC. Для подробного рассмотрения в качестве примера выберем криптозащищенную карту Hitag.

2 Hitag

Первые бесконтактные Smart-карты появились на рынке в конце 1990-х гг. и существенно отличались от тех, что были прежде. Они создавались в соответствии с требованиями Международной организации по стандартизации (ISO), имели функцию защищенного взаимодействия благодаря использованию различных криптографических механизмов и позволяли не только считывать id карты, но и хранить на ней информацию.

2.1 Протокол аутентификации

Протокол аутентификации, используемый в Hitag 2 в крипторежиме, был восстановлен с помощью обратного проектирования (реверс инжиниринга) и опубликован в 2007 году (рисунок 1). Считыватель посылает команду аутентификации, в ответ на которую карта посылает id. C этого момента взаимодействие шифруется путем выполнения операции XOR с ключевым потоком. Считыватель отвечает зашифрованным вызовом n_R и зашифрованным ответом a_R = 0xFFFFFFFF. Чтобы доказать знание ключа, карта заканчивает аутентификацию, посылая зашифрованный ответ a_T, содержащийся в блоке 3.

  

Рис. 1. Протокол аутентификации Hitag2

 

Во время выполнения протокола аутентификации внутреннее состояние потокового шифратора инициализируется. Исходное состояние состоит из 32-х битового идентификатора карты, и первых 16-ти битов ключа. Затем считыватель генерирует n_R, выполняя операцию XOR последних 32 бит ключа, задвигаемых в шифратор с его выходом. Во время инициализации обратная связь с РСЛОС отключена. Так как обмен зашифрован, начиная с n_R и далее, на шифрование конечных битов n_R влияет шифрование предыдущих битов. Аутентификация достигается за счет получения того же самого внутреннего состояния шифратора после сдвига n_R.

2.2 Шифратор Hitag

В режиме шифрования информация между картой и считывателем (после успешной аутентификации) шифруется с потоковым шифром Hitag2. Шифратор состоит из 48-битного РСЛОС и нелинейной фильтрующей функции f. В каждом такте двадцать битов РСЛОС проходят через фильтрующую функцию f, создавая один бит ключевого потока. Тогда РСЛОС смещается на один бит влево, используя полином для генерирования нового бита справа. На рисунке 2 схематическое представление шифратора Hitag2.

Рис. 2. Шифратор Hitag2

 

Определение 1: Функция обратной связи L: F₂⁴⁸ → F₂ определяется

L(x₀...x₄₇):=x₀⊕x₂⊕x₃⊕x₆⊕x₇⊕x₈⊕x₁₆⊕x₂₂⊕x₂₃⊕x₂₆⊕x₃₀⊕x₄₁⊕x₄₂⊕x₄₃⊕x₄₆⊕x_47.

Фильтрующая функция f состоит из трех различных функций f_a, f_b и f_c. На выход каждой из них приходится один бит. Функции f_a и f_b применяются более одного раза, используя в общей сложности двадцать входных бит из РСЛОС. Эти результирующие биты применяются в качестве входных данных для f_c. Функции представлены тремя логическими таблицами, которые содержат результирующие биты для каждого входа.

Определение 2: Фильтрующая функция f: F₂⁴⁸ → F₂ определяется

f (x₀... x₄₇) = f_c(f_a (x₂x₃x₅x₆), f_b(x₈x₁₂x₁₄x₁₅), f_b(x₁₇x₂₁x₂₃x₂₆), f_b(x₂₈x₂₉x₃₁x₃₃),f_a(x₃₄x₄₃x₄₄x₄₆)),

где f_a,f_b: F₂⁴ → F₂ и f_c: F₂⁵ → F₂; f_a (i) = (0xA63C)_i; f_b(i) = (0xA770)_i; f_c (i) = (0xD949CBB0)_i.

Каждый из блоков f (и, следовательно, сама f) обладает свойством выдавать ноль для половины возможных входов (и единицу соответственно) [2].

2.3 Особенности реализации Hitag2

В этом разделе описаны три слабых места в устройстве Hitag2. Первым является недостаток протокола, а последние два — слабостью конструкции шифратора.

2.3.1 Случайная длина ключевого потока

Эта слабость описывает, что без знания секретного ключа, но, имея попытку только одной аутентификации, можно получить любую нужную длину ключевого потока от карты. В [13] описываются команды считывателя, которые могут изменять или прекращать работу карты Hitag2. Можно увеличить длину такой команды на величину, кратным пяти битам. 10-битная команда может иметь дополнительное число сообщений r с резервированием, так что общее количество бит в сообщении составит 10 + 5r бит. Из-за ограничения по мощности и памяти, Hitag2, похоже, не имеет приёмопередающего буфера. Таким образом, все операции шифрации выполняются непосредственно при получении или передачи битов. Эксперименты показывают, что карта Hitag2 успешно принимает зашифрованные команды от считывателя, которые направляются с 1000 сообщениями избыточности. Размер такой команды состоит из 10 + 5 × 1000 = 5010 бит.

Поскольку не существует никакой дополнительной проверки от карты можно повторить любую действительную пару {n_R} {а_R} к карте, чтобы достичь успешной аутентификации. После получения a_T, внутреннее состояние карты инициализируется и ждет зашифрованной команды от считывателя, как определено на рисунке 5. Все возможные комбинации должны быть оценены без знания ключевого потока b₉₆b₉₇.,, и далее. Команда состоит из по крайней мере, 10 битов, поэтому есть 210 возможностей. Каждая команда требует 3-битный параметр, содержащий номер блока. Обе команды read и!read получают 32-битный ответ, в то время как операции записи и прекращения имеют разную длину отклика.

Следовательно, при поиске 10-битных зашифрованных команд которые получают 32-битный ответ, существует ровно 16 из 210 значений, которые подходят. В среднем первая команда read находится после 32 попыток, дополнение к этой команде read и её линейным параметрам изменяется линейно и требует всего-лишь еще 15 попыток.

Один из 16 догадок представляет зашифрованные биты команды чтения на первом блоке памяти. Этот блок содержит идентификатор, который известен в виде открытого текста, так как он передается в открытом виде во время аутентификации. Таким образом, есть предположение, так что передаваемые биты равны сообщению на рисунке 6.

При правильной догадке могут быть восстановлены 40 бит ключевого потока. Этот ключевой поток затем используется для шифрования команды read слегка измененный на блоке 0 с шестью избыточными сообщениями, как описано в [13] Транспондер отвечает следующими 32-битами ключевого потока, которые используются для шифрования карты. Следовательно, ближайшие 30 бит ключевого потока были получены с помощью ранее восстановленного ключевого потока и расширения команды read. Эта операция может быть повторена много раз. Например, с использованием выделенного ключевого потока b₉₆...b₁₆₇ можно построить 70-разрядную команду read с 12 избыточными сообщениями. На практике восстановление 2048 бит ключевого потока занимает менее 30 секунд.

2.3.2    Зависимости между сессиями

В статье [2] показано, что при состоянии шифратора α₇₉ шифратор полностью инициализируется, а с этого момента шифратор только производит ключевой поток. Это показывает, что 48-битное внутреннее состояние шифра рандомизировано только 32-битным параметром n_R. Следовательно, в состоянии α₇₉ только биты РСЛОС с 16 по 47 влияют на считыватель. Поэтому биты регистра с 0 по 15 остаются неизменными на протяжении сессии, что дает сильную зависимость между ними. Эти неизменные 16 бит сессии соответствуют битам k₀…k₁₅ секретного ключа.

2.3.3    Низкий уровень детерминации фильтрующей функции

Фильтрующая функция f: F⁴⁸₂ → F₂ состоит из трех блоков f_a, f_b и f_c, расположенных в двух слоях структуры. Из-за этой определенной структуры, входные биты a₃₄...a₄₇ влияют только на правый входной бит f_c. Кроме того, простой осмотр f_c показывает, что в 8 из 32 конфигураций входных битов, правый вход не имеет никакого влияния на выходе f_c. В других случаях, выход f_c определяется ее 4-мя левыми входными битами. Кроме того, это означает, что с вероятностью 1/4 фильтрующая функция f определяет 34-левых бита внутреннего состояния. Следующая теорема утверждает это точно.

Теорема 1. Пусть X — переменная, равномерно распределенная на F₂³⁴, тогда

 P [∀Y,Y′ ∈ F₂¹⁴: f (XY) = f (XY′)] = 1/4

Доказательство.

Определение 1. Функция, которая проверяет это свойство P: F⁴⁸₂→F₂ определяется через

 P(x₀... x₄₇) = (0x84D7)_i,

где i = f_a(x₂x₃x₅x₆) f_b(x₈x₁₂x₁₄x₁₅) f_b(x₁₇x₂₁x₂₃x₂₆) f_b(x₂₈x₂₉x₃₁x₃₃).

Так как P(x₀…x₄₇) зависит только от x₀…x₃₃, мы перегрузим значение и будем рассматривать P(·) как функцию F³⁴₂→F₂, записывая P(x₀…x₄₇) как P(x₀…x₃₃0¹⁴).

2.4 Атаки на Hitag2

Данный раздел описывает три вида атак на Hitag2. Первая атака прямая и предоставляет противнику доступ к чтению\записи памяти транспондера (карты). С помощью метода криптоанализа, описанного во второй атаке, можно восстановить секретный ключ после нескольких сеансов взаимодействия считывателя и карты. Эта атака использует основные техники, которые могут быть также применены к другим основанным на РСЛОС потоковым шифрам. Третья атака описывает особый вид криптоанализа шифра Hitag2. Ему необходимо лишь несколько попыток аутентификации со считывателем, и он позволяет противнику восстановить секретный ключ с вычислительной сложностью в 2³⁵ операций. Последние две атаки предлагают компромисс между временем\памятью\данными и временем\трассами соответственно. Для упрощения атаки описаны со значениями либо оптимальными, либо с теми, которые являются «разумными» с точки зрения доступного оборудования.

2.4.1 Атака с изменением сообщения

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

После восстановления битов ключевого потока b₉₆…b₁₃₇ противник может получить дамп памяти карты, в котором хранится его пароль. Восстановление ключевого потока и создание дампа памяти занимает в общей сложности меньше секунды и требует лишь находиться в радиусе действия считывателя.

Блоки памяти, хранящие криптографический ключ, имеют дополнительный защитный механизм. В них есть однократно программируемый бит, который определяет доступность данных блоков для чтения. Если считывающее устройство пытается прочитать защищенный блок — карта не отвечает. Если карта настроена некорректно (не запрограммирован защитный бит), она позволяет противнику считать все необходимые данные.

2.4.2 Атака по времени\памяти

Данный вид атаки может быть применен к любым основанным на РСЛОС потоковым шифрам, пока доступен смежный ключевой поток. Так и происходит с Hitag2. Эта атака требует налаженного взаимодействия считывающего устройства с транспондером. Следующее утверждение представляет небольшой трюк, с помощью которого можно выполнить n шагов шифра за раз. Интуитивно данное утверждение показывает, что линейная разница между состоянием s и его n-м потомком, это комбинация линейных разниц, генерируемых каждым битом. Это будет в дальнейшем использовано в атаке.

Утверждение 1:

Пусть у нас есть РСЛОС состояние и n ∈ N. Далее, пусть d_i = sucⁿ(2ⁱ), то есть состояние РСЛОС, получаемое выполнением n шагов шифратора от состояния 2ⁱ, т. е. sucⁿ(s)= ⊕⁴⁷_i=0(d_i,s_i)

Для выполнения атаки противник А выполняет следующие действия:

1.    А однократно создает таблицу, содержащую 2³⁷ элементов. Каждый элемент таблицы имеет вид (ks,s), где s ∈ F₂⁴⁸ это состояние РСЛОС и ks ∈ F₂ это 48 битов ключевого потока, созданных в результате выполнения шифрации из s. Начиная с некоего состояния где s≠0, А создает 48 битов ключевого потока и хранит их. Затем противник использует Утверждение 1 чтобы быстро перейти к следующему элементу таблицы, пропуская n=2ⁱ состояний шифра. Это уменьшает вычислительную сложность таблицы от 2⁴⁸ до 2³⁷×48=2^42,5 тактов шифрации. Более того, для улучшения времени поиска по таблице, она разделена на 2²⁴ подтаблиц, структурированных в виде /ks_byte1/ks_byte2/ks_byte3.bin, где каждый файл занимает объем 8 КБ. Общий объем таблицы 1.2ТБ.

2.    А эмулирует карту и запускает попытку аутентификации со считывателем. Согласно протоколу аутентификации, считыватель отвечает сообщением {n_R}{a_R}.

3.    Далее, противник удаленно транслирует сообщение для легитимной карты и, используя уязвимость, получает 256 байт ключевого потока. Это может быть исполнено пока ключ находится в сумке или кармане жертвы.

4.    А устанавливает i=0.

5.    Далее он ищет ключевой поток ks_i…ks_i+47 в таблице из шага 1.

6.    Если искомый ключ не найден, i инкрементируется и повторяется шаг 5. Если совпадение найдено, то данный ключ устанавливается как искомый, и противник с помощью оставшихся битов ключевого потока утверждает текущее состояние как внутреннее состояние шифратора.

7.    Далее противник использует откат состояния шифратора и восстанавливает секретный ключ.

Сложность и время.

На шаге 1 противнику необходимо вычислить таблицу объемом 1,2 ТБ, что эквивалентно 2³⁷ кодированиям. Во время генерации каждый элемент хранится в соответствующем файле.bin. Каждый из этих 8 КБ файлов также должен быть отсортирован, но это занимает всего несколько минут. Вычисление и сортировка всей таблицы занимает в среднем день на стандартном ноутбуке. Шаги 2–3 требуют около 30 секунд для получения 256 байт ключевого потока от карты. Шаги 4–6 требуют (в худшем случае) 2000 просмотра таблицы, что занимает около 30 секунд на стандартном ноутбуке. Таким образом, для осуществления атаки с начала и до конца требуется одна минута.

2.4.3 Криптоаналитическая атака

Комбинация уязвимостей из пп. 2.3.1–2.3.3 позволяет противнику получить секретный ключ после нескольких попыток аутентификации со считывателем. В случае если используется список достоверных идентификаторов, как дополнительная мера предосторожности, противнику сначала необходимо получить достоверный id карты.

Предположения в основе атаки лежат достаточно простые. Предположительно, противник имеет представление о первых 34 битах ключа. Одна из четырех команд позволяет противнику выполнить тест на первый бит {a_R}. Зависимости между сессиями, описанные в разделе 2.3.2, позволяют противнику выполнять этот тест несколько раз, кардинально сокращая количество возможных ключей. Если атакующий получил 136 команд, это позволяет ему в среднем провести 34 битовых теста, то есть столько же, сколько битов уже было угадано. Для ключей, прошедших проверку, противник запускает поиск оставшихся 14 битов ключа.

Описание атаки:

1.    Противник использует эмулятор карты (например, Proxmark III) для проведения 136 попыток аутентификации со считывателем, используя фиксированный идентификатор(id). Таким образом, противник получает 136 команд вида {n_R}{a_R}. Далее начинает искать секретный ключ. Для этого он разбивает ключ k на три части k=kk’k’’, где k=k₀…k₁₅, k’=k₁₆…k₃₃, k”= k₃₄…k₄₇.

2.    Для каждого k=k₀…k₁₅ строит таблицу T_k, содержащую элементы вида

(y ⊕ b₀... b₁₇, b₃₂, ky)

Для всех у ϵ F²₁₈ P(ky0¹⁴)=1. Ожидаемый объем таблицы 2¹⁸ x ¼ = 2¹⁶, что легко умещается в память.

3.    Для всех k’=k₁₆…k₃₃ ϵ F²₁₈ и для каждого пути {n_R}{a_R} нарушитель z:=k’⊕{n_R}₀…{n_R}₁₇. Если на входе в T_k которого y ⊕ b₀... b₁₇ высчитывает z но b₃₂ ≠{a_R}₀ тогда нарушитель узнает, что k’ — неверное предположение, он пробует следующее. По-другому, если b₃₂ ={a_R}₀ тогда k’ подходящее и тогда противник пробует следующий путь.

4.    Каждый kk’, который проходит тест для всех трасс, это возможный ключ. Для каждого из таких возможных ключей противник выполняет исчерпывающий поиск оставшихся k”= k₃₄…k₄₇. Для каждого целого возможного ключа противник дешифрует две трассы и проверяет, чтобы для обеих трасс {a_R} дешифровался в ряд единиц, как того требует аутентификационный протокол. Если ключ проходит тест — это искомый секретный ключ. Если нет — противник возвращается на шаг 2 и повторяет алгоритм с другим k.

Сложность и время

На шаге 1 противнику необходимо получить 136 частичных аутентификационных трасс. Используя Proxmark III это можно сделать за минуту. На шагах 2 и 3 противнику необходимо построить 2¹⁶ таблиц. Для каждой их них необходимо выполнить 2¹⁸ просмотров и кодировок. Шаг 4 имеет мизерную сложность, поэтому мы его игнорируем. Это добавляет 2³⁵ кодировок\просмотров. Поисковое пространство для k можно разделить на произвольное количество процессов. На стандартном четырехядерном ноутбуке данные вычисления займут меньше 5 минут. Таким образом, всю атаку можно выполнить меньше чем за 360 секунд.

Вывод

На предприятии осуществляется контроль физического перемещения носителя через зону прохода. Критически важным фактором является невозможность получения несанкционированной копии данного носителя. Из этого следует два основных требования к рассматриваемым RFID-носителям, исключающие доступ к содержимому памяти. Первым требованием является высокая криптостойкость алгоритмов, исключащая аналитические атаки и атаки прямого подбора ключа. Вторым требованием, как показывают проведенные выше исследования, является отсутствие уязвимостей при реализации кристалла RFID-носителя. Данные требования являются основными показателями для выбора RFID-носителя для системы, в которой осуществляется контроль физического перемещения носителя через зону прохода.

В картах первого поколения Hitag использован проприетарный алгоритм шифрования с небольшой длиной ключа, не превышающей 64 битов. Данные алгоритмы шифрования на сегодняшний день не являются криптостойкими, что подтверждается приведенными в этой работе способами атаки. Кроме того, карты имеют явные уязвимости при реализации, позволяющие взломщику выполнить эффективные атаки.

В ходе выполнения данной работы были выполнены исследования средств защиты карты Hitag. Используя доступную научно-техническую информацию, были подробно изучены протокол аутентификации, алгоритм шифрования, уязвимости при реализации карты и соответствующие способы атаки на них.

 

Литература:

 

1.         Финкенцеллер К. RFID-технологии. Справочное пособие. — М.:Додэка-XXI, 2010–496 с.: — Доп.тит.л.нем. — ISBN 978–5-94120–232–4.

2.         Roel Verdult, Flavio D. Garcia, Josep Balasch, Gone in 360 Seconds: Hijacking with Hitag2. — 16c.

3.         Product short data sheet: HT2x, HITAG 2 transponder IC, ноябрь 2014. — 9c. [Электронный ресурс]. — Режим доступа: http://www.nxp.com/documents/short_data_sheet/HT2X_SDS.pdf.