ЗАЩИТА ПРОТОКОЛОВ УЛЬТРАЛЕГКОЙ АУТЕНТИФИКАЦИИ ОТ АТАК НА LSB
58 Д. А. Ковалев, С. В. Беззатеев
УДК 004.056
Д. А. КОВАЛЕВ, С. В. БЕЗЗАТЕЕВ
ЗАЩИТА ПРОТОКОЛОВ УЛЬТРАЛЕГКОЙ АУТЕНТИФИКАЦИИ ОТ АТАК НА LSB
Предложен подход к улучшению версии протокола взаимной аутентификации LMAP++ путем замены стандартной операции сложения по модулю 2m на операцию сложения по модулю 2m–1 и использованием только простейших арифметических операций. Проведено сравнение сложности предложенной версии со сложностью известных методов повышения надежности протокола LMAP++.
Ключевые слова: RFID, ультралегкие протоколы, LMAP++, аутентификация.
Введение. Ультралегкие протоколы аутентификации для RFID построены на простейших арифметических операциях. Такие протоколы предназначены для сфер, требующих массового использования RFID-меток.
Ультралегкая RFID-метка имеет существенные ограничения по вычислительным возможностям и памяти, поэтому такие распространенные криптографические решения по обеспечению безопасности, как RSA, DES, AES, не могут быть реализованы в криптографических функциях, используемых в ультралегких протоколах, в них применяется следующий набор операций [1]:
— ⊕ XOR — поразрядная операция ИСКЛЮЧАЮЩЕГО ИЛИ, — ∨ OR — поразрядное логическое ИЛИ, — ∧ AND — поразрядное логическое И, — + — сложение m-битных чисел с игнорированием переполнения (сложение по модулю 2m). Несмотря на существенные ограничения по вычислительным возможностям, к безопасности ультралегких RFID-меток предъявляются достаточно высокие требования: — анонимность метки, — взаимная аутентификация между RFID-считывателем и меткой при минимальном числе сообщений, которыми они обмениваются. В ультралегких протоколах можно выделить следующие основные этапы. 1. Считыватель посылает некоторую, инициализирующую протокол, команду метке. На этот запрос RFID-метка всегда отвечает своим динамическим идентификатором. 2. Считыватель находит в базе ключи и статический идентификатор метки по полученному динамическому идентификатору. Далее считыватель генерирует случайные числа и использует их и ключ метки для создания сообщения, которое на следующем шаге будет использоваться для взаимной аутентификации. 3. Считыватель и метка обмениваются сообщениями аутентификации. 4. Обновляются ключи и динамический идентификатор на считывателе и метке. В 2006 г. P. Peris-Lopez предложил несколько ультралегких протоколов взаимной аутентификации — LMAP [2], EMAP [1], M2AP [3], но в них было обнаружено множество уязвимостей [4, 5]. В 2007 г. Li и Wang предложили улучшенную версию протокола LMAP: SLMAP, в которой также были найдены слабые места [6, 7]. В 2008 г. Tieyan Li улучшил свой протокол и назвал его LMAP++ [8], улучшенная версия также имела недостатки [9, 10]. Основные уязвимости протоколов аутентификации ультралегких радиочастотных идентификаторов. Большинство атак на ультралегкие протоколы используют идентичность операции сложения по модулю 2m и операции XOR (⊕) для наименее значимых битов (LSB)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Защита протоколов ультралегкой аутентификации от атак на LSB
59
[a + b]0 = a 0⊕ b0 ,
[a − b]0 = a 0⊕ b0 .
Для представления старших битов используется следующая формула:
[a + b]i = ai ⊕ bi ⊕ s(a,b, i −1) ,
[a − b]i = ai ⊕ bi ⊕ t(a, b,i −1) ,
где 0≤i 1) + IDSULAP + IDSULAP +n; } где IDSULAP >>1 — сдвиг вектора IDSULAP на 1 бит вправо.
Считыватель
“hello”||n IDSULAP
Метка
Рис. 1
В протоколах UMA-RFID [13], SASI [14], SULMA [15] при создании сообщений для взаимной аутентификации используется операция Rot(x,y), т.е. циклический сдвиг влево вектора x, на wt(y) позиций, где wt — вес Хемминга.
В протоколе RAPP [16] при создании сообщений используется операция перестановки Per(x,y) битов в векторе x в соответствии со значениями битов в векторе y.
Перестановка Per(x,y) выполняется следующим образом. Предположим, что x и y — два 96-битных числа, где
x = x0x2...x95, xi ∈{0,1}, i = 0,1, 2,..., 95,
y = y0 y2...y95, yi ∈{0,1}, i = 0,1, 2,...,95 ,
и вес Хемминга вектора y равен m (0≤m≤95), при yk1 = yk2 = ... = ykm = 1, ykm = ykm+1 = ... = yk95 = 0,
где 0 ≤ k1 < k2 < ... < km ≤ 95 и 0 ≤ km+1 < km+2 < ... < k95 ≤ 95. Тогда перестановка Per(x,y)=
= xk1 xk2 ... xkm xk95 ... xkm+2 xkm+1 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
60 Д. А. Ковалев, С. В. Беззатеев
В протоколе EMAP [1] при обновлении ключей и динамического идентификатора метки используется операция Fp(a) при m=96, вектор a будет разбит на 24 блока по 4 бита, и для каждого блока будет вычисляться бит четности.
Пусть a = a0, a1, a2,…, a95 , тогда Fp(a) = (a0 ⊕ a1 ⊕ a2 ⊕ a3, a4 ⊕ a5 ⊕ a6 ⊕ a7 ,..., a92 ⊕ a93 ⊕ a94 ⊕ a95 ) .
Использование операции сложения по модулю 2m–1. Для устранения возможности проведения атак, построенных на уязвимости LSB, предлагается заменить операцию сложения по модулю 2m на операцию сложения по модулю 2m–1. Реализовать эту операцию можно с помощью элементарных арифметических операций и архитектуры сумматора (рис. 2).
A+B flag
flag
A B
— XOR
— OR
— AND
Рис. 2
Сложение по модулю 2m –1 для чисел A и B можно провести за 5 шагов. Шаг 1. C' =A+B mod 2m, flag=1 если A+B > 2m–1 и flag=0 — в противном случае. Шаг 2. C'=C'+0+flag mod 2m. Шаг 3. D=C mod 2m. Шаг 4. D=D+1 mod 2m, flag=1, если D=2m–1, и flag=0 — в противном случае. Шаг 5. C=C'+0+flag mod 2m. Таким образом, результатом сложения чисел A и B по модулю 2m–1 будет число C. При использовании операции сложения по модулю 2m–1 исключаются уязвимости, существовавшие ранее вследствие идентичности операций сложения по модулю 2m и XOR для
LSB, так как равенства [a + b]0 = a 0⊕b0 и [a − b]0 = a 0⊕b0 не выполняются для операций арифметического сложения и вычитания по модулю 2m–1.
В таблице сравниваются параметры операций, использовавшихся для предотвращения
атаки по LSB.
Операции
Сложность в логических вентилях
при m=96
MixBits
8120
Rot (x,y)
480
Permutation
~45794
Fp Сложение по mod 2m–1
468 173
Выводы. Предложена операция, предотвращающая атаки LSB, которая менее требова-
тельна к вычислительным возможностям RFID-метки, чем предлагавшиеся ранее операции.
СПИСОК ЛИТЕРАТУРЫ
1. Peris-Lopez P., Hernandez-Castro J. C., Estevez-Tapiador J. M., Ribagorda A. EMAP: An Efficient Mutual Authentication Protocol for Low-cost RFID Tags // OTM Federated Conf. and Workshop: IS Workshop (IS’06). Montpellier, France: Springer-Verlag, 2006. Vol. 4277 of LNCS. P. 352—361.
2. Peris-Lopez P., Hernandez-Castro J. C., Estevez-Tapiador J. M., Ribagorda A. LMAP: A Real Lightweight Mutual Authentication Protocol for Low-cost RFID tags // Workshop on RFID Security (RFIDSec’06). Graz Austria, 2006.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Защита протоколов ультралегкой аутентификации от атак на LSB
61
3. Peris-Lopez P., Hernandez-Castro J. C., Estevez-Tapiador J. M., Ribagorda A. M2AP: A Minimalist mutual authentication protocol for low-cost RFID tags // 3rd Intern. Conf. on Ubiquitous Intelligence and Computing (UIC’06). 2006. Vol. 4159. P. 912—923.
4. Barasz M., Boros B., Ligeti P., Loja K., Nagy D. A. Breaking LMAP // Proc of RFIDSec. 2007. P. 11—16.
5. Li T., Wang G., Deng R. H. SecurityAnalysisona Family of Ultra-lightweight RFID Authentication Protocols // J. of Software. 2008. Vol. 3. P. 1—10.
6. Safkhani M., Bagheri N., Naderi M., Sanadhya S. K. Security Analysis of LMAP++, an RFID Authentication Protocol // 6th Intern. Conf. Internet Technology and Secured Transactions. 2011. P. 689—694.
7. Hernandez-Castro J. C., Tapiador J. E., Peris-Lopez P., Clark J. A., Talbi E. Metaheuristic Traceability Attack against SLMAP, an RFID Lightweight Authentication Protocol // Intern. J. Foundations of Computer Science. 2009. P. 543—553.
8. Li T. Employing Lightweight Primitiveson Low-Cost RFID Tags for Authentication // Vehicular Technology Conf. 2008. P. 770—776.
9. Wangand S.-H., Zhang W.-W. Passive Attack on RFID LMAP++ Authentication protocol // CANS. 2009. P. 185—193.
10. Hernandez-Castro J. C., Tapiador J. E., Peris-Lopez P., Clark J. A., Talbi E. Metaheuristic Traceability Attackagainst SLMAP, an RFID Lightweight Authentication Protocol // IPDPS’09. Proc. of the 2009 IEEE Intern. Symp. Parallel & Distributed Processing. 2009. P. 1—5.
11. Tanenbaum A. S. Structured Computer Organization. 2001.
12. Barasz M., Boros B., Ligeti P., Loja K., Nagy D. A. Breaking EMAP // SecureComm. 2007. P. 514—517.
13. Li T., Wang G. Security Analysis of Two UltraLightweight RFID Authentication Protocols // IFIPSEC’07. 2007. P. 109—120.
14. Yu H. SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity // Dependable and Secure Computing. IEEE Transact. on Date of Publication. 2007.
15. Kianersi M., Gardeshi M., Arjmand M.SULMA: A Secure Ultra Light-Weight Mutual Authentication Protocol for Lowcost RFID Tags // Intern. J. of UbiComp. 2011. Vol. 2. P. 17.
16. Peris-Lopez P., Hernandez-Castro J. C., Tapiador J. M. E., Ribagorda A. Advances in Ultralightweight Cryptography for Low-cost RFID Tags: Gossamer Protocol // Workshop on Information Security Applications. 2008. Vol. 5379. P. 56—68.
Данил Александрович Ковалев Сергей Валентинович Беззатеев
Сведения об авторах — аспирант; Санкт-Петербургский государственный университет аэро-
космического приборостроения, кафедра технологий защиты информации; E-mail: iostreamawm@gmail.com — д-р техн. наук, доцент; Санкт-Петербургский государственный университет аэрокосмического приборостроения, кафедра технологий защиты информации; заведующий кафедрой; E-mail: bsv@aanet.ru
Рекомендована кафедрой № 51 безопасности информационных систем
Поступила в редакцию 01.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
УДК 004.056
Д. А. КОВАЛЕВ, С. В. БЕЗЗАТЕЕВ
ЗАЩИТА ПРОТОКОЛОВ УЛЬТРАЛЕГКОЙ АУТЕНТИФИКАЦИИ ОТ АТАК НА LSB
Предложен подход к улучшению версии протокола взаимной аутентификации LMAP++ путем замены стандартной операции сложения по модулю 2m на операцию сложения по модулю 2m–1 и использованием только простейших арифметических операций. Проведено сравнение сложности предложенной версии со сложностью известных методов повышения надежности протокола LMAP++.
Ключевые слова: RFID, ультралегкие протоколы, LMAP++, аутентификация.
Введение. Ультралегкие протоколы аутентификации для RFID построены на простейших арифметических операциях. Такие протоколы предназначены для сфер, требующих массового использования RFID-меток.
Ультралегкая RFID-метка имеет существенные ограничения по вычислительным возможностям и памяти, поэтому такие распространенные криптографические решения по обеспечению безопасности, как RSA, DES, AES, не могут быть реализованы в криптографических функциях, используемых в ультралегких протоколах, в них применяется следующий набор операций [1]:
— ⊕ XOR — поразрядная операция ИСКЛЮЧАЮЩЕГО ИЛИ, — ∨ OR — поразрядное логическое ИЛИ, — ∧ AND — поразрядное логическое И, — + — сложение m-битных чисел с игнорированием переполнения (сложение по модулю 2m). Несмотря на существенные ограничения по вычислительным возможностям, к безопасности ультралегких RFID-меток предъявляются достаточно высокие требования: — анонимность метки, — взаимная аутентификация между RFID-считывателем и меткой при минимальном числе сообщений, которыми они обмениваются. В ультралегких протоколах можно выделить следующие основные этапы. 1. Считыватель посылает некоторую, инициализирующую протокол, команду метке. На этот запрос RFID-метка всегда отвечает своим динамическим идентификатором. 2. Считыватель находит в базе ключи и статический идентификатор метки по полученному динамическому идентификатору. Далее считыватель генерирует случайные числа и использует их и ключ метки для создания сообщения, которое на следующем шаге будет использоваться для взаимной аутентификации. 3. Считыватель и метка обмениваются сообщениями аутентификации. 4. Обновляются ключи и динамический идентификатор на считывателе и метке. В 2006 г. P. Peris-Lopez предложил несколько ультралегких протоколов взаимной аутентификации — LMAP [2], EMAP [1], M2AP [3], но в них было обнаружено множество уязвимостей [4, 5]. В 2007 г. Li и Wang предложили улучшенную версию протокола LMAP: SLMAP, в которой также были найдены слабые места [6, 7]. В 2008 г. Tieyan Li улучшил свой протокол и назвал его LMAP++ [8], улучшенная версия также имела недостатки [9, 10]. Основные уязвимости протоколов аутентификации ультралегких радиочастотных идентификаторов. Большинство атак на ультралегкие протоколы используют идентичность операции сложения по модулю 2m и операции XOR (⊕) для наименее значимых битов (LSB)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Защита протоколов ультралегкой аутентификации от атак на LSB
59
[a + b]0 = a 0⊕ b0 ,
[a − b]0 = a 0⊕ b0 .
Для представления старших битов используется следующая формула:
[a + b]i = ai ⊕ bi ⊕ s(a,b, i −1) ,
[a − b]i = ai ⊕ bi ⊕ t(a, b,i −1) ,
где 0≤i 1) + IDSULAP + IDSULAP +n; } где IDSULAP >>1 — сдвиг вектора IDSULAP на 1 бит вправо.
Считыватель
“hello”||n IDSULAP
Метка
Рис. 1
В протоколах UMA-RFID [13], SASI [14], SULMA [15] при создании сообщений для взаимной аутентификации используется операция Rot(x,y), т.е. циклический сдвиг влево вектора x, на wt(y) позиций, где wt — вес Хемминга.
В протоколе RAPP [16] при создании сообщений используется операция перестановки Per(x,y) битов в векторе x в соответствии со значениями битов в векторе y.
Перестановка Per(x,y) выполняется следующим образом. Предположим, что x и y — два 96-битных числа, где
x = x0x2...x95, xi ∈{0,1}, i = 0,1, 2,..., 95,
y = y0 y2...y95, yi ∈{0,1}, i = 0,1, 2,...,95 ,
и вес Хемминга вектора y равен m (0≤m≤95), при yk1 = yk2 = ... = ykm = 1, ykm = ykm+1 = ... = yk95 = 0,
где 0 ≤ k1 < k2 < ... < km ≤ 95 и 0 ≤ km+1 < km+2 < ... < k95 ≤ 95. Тогда перестановка Per(x,y)=
= xk1 xk2 ... xkm xk95 ... xkm+2 xkm+1 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
60 Д. А. Ковалев, С. В. Беззатеев
В протоколе EMAP [1] при обновлении ключей и динамического идентификатора метки используется операция Fp(a) при m=96, вектор a будет разбит на 24 блока по 4 бита, и для каждого блока будет вычисляться бит четности.
Пусть a = a0, a1, a2,…, a95 , тогда Fp(a) = (a0 ⊕ a1 ⊕ a2 ⊕ a3, a4 ⊕ a5 ⊕ a6 ⊕ a7 ,..., a92 ⊕ a93 ⊕ a94 ⊕ a95 ) .
Использование операции сложения по модулю 2m–1. Для устранения возможности проведения атак, построенных на уязвимости LSB, предлагается заменить операцию сложения по модулю 2m на операцию сложения по модулю 2m–1. Реализовать эту операцию можно с помощью элементарных арифметических операций и архитектуры сумматора (рис. 2).
A+B flag
flag
A B
— XOR
— OR
— AND
Рис. 2
Сложение по модулю 2m –1 для чисел A и B можно провести за 5 шагов. Шаг 1. C' =A+B mod 2m, flag=1 если A+B > 2m–1 и flag=0 — в противном случае. Шаг 2. C'=C'+0+flag mod 2m. Шаг 3. D=C mod 2m. Шаг 4. D=D+1 mod 2m, flag=1, если D=2m–1, и flag=0 — в противном случае. Шаг 5. C=C'+0+flag mod 2m. Таким образом, результатом сложения чисел A и B по модулю 2m–1 будет число C. При использовании операции сложения по модулю 2m–1 исключаются уязвимости, существовавшие ранее вследствие идентичности операций сложения по модулю 2m и XOR для
LSB, так как равенства [a + b]0 = a 0⊕b0 и [a − b]0 = a 0⊕b0 не выполняются для операций арифметического сложения и вычитания по модулю 2m–1.
В таблице сравниваются параметры операций, использовавшихся для предотвращения
атаки по LSB.
Операции
Сложность в логических вентилях
при m=96
MixBits
8120
Rot (x,y)
480
Permutation
~45794
Fp Сложение по mod 2m–1
468 173
Выводы. Предложена операция, предотвращающая атаки LSB, которая менее требова-
тельна к вычислительным возможностям RFID-метки, чем предлагавшиеся ранее операции.
СПИСОК ЛИТЕРАТУРЫ
1. Peris-Lopez P., Hernandez-Castro J. C., Estevez-Tapiador J. M., Ribagorda A. EMAP: An Efficient Mutual Authentication Protocol for Low-cost RFID Tags // OTM Federated Conf. and Workshop: IS Workshop (IS’06). Montpellier, France: Springer-Verlag, 2006. Vol. 4277 of LNCS. P. 352—361.
2. Peris-Lopez P., Hernandez-Castro J. C., Estevez-Tapiador J. M., Ribagorda A. LMAP: A Real Lightweight Mutual Authentication Protocol for Low-cost RFID tags // Workshop on RFID Security (RFIDSec’06). Graz Austria, 2006.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Защита протоколов ультралегкой аутентификации от атак на LSB
61
3. Peris-Lopez P., Hernandez-Castro J. C., Estevez-Tapiador J. M., Ribagorda A. M2AP: A Minimalist mutual authentication protocol for low-cost RFID tags // 3rd Intern. Conf. on Ubiquitous Intelligence and Computing (UIC’06). 2006. Vol. 4159. P. 912—923.
4. Barasz M., Boros B., Ligeti P., Loja K., Nagy D. A. Breaking LMAP // Proc of RFIDSec. 2007. P. 11—16.
5. Li T., Wang G., Deng R. H. SecurityAnalysisona Family of Ultra-lightweight RFID Authentication Protocols // J. of Software. 2008. Vol. 3. P. 1—10.
6. Safkhani M., Bagheri N., Naderi M., Sanadhya S. K. Security Analysis of LMAP++, an RFID Authentication Protocol // 6th Intern. Conf. Internet Technology and Secured Transactions. 2011. P. 689—694.
7. Hernandez-Castro J. C., Tapiador J. E., Peris-Lopez P., Clark J. A., Talbi E. Metaheuristic Traceability Attack against SLMAP, an RFID Lightweight Authentication Protocol // Intern. J. Foundations of Computer Science. 2009. P. 543—553.
8. Li T. Employing Lightweight Primitiveson Low-Cost RFID Tags for Authentication // Vehicular Technology Conf. 2008. P. 770—776.
9. Wangand S.-H., Zhang W.-W. Passive Attack on RFID LMAP++ Authentication protocol // CANS. 2009. P. 185—193.
10. Hernandez-Castro J. C., Tapiador J. E., Peris-Lopez P., Clark J. A., Talbi E. Metaheuristic Traceability Attackagainst SLMAP, an RFID Lightweight Authentication Protocol // IPDPS’09. Proc. of the 2009 IEEE Intern. Symp. Parallel & Distributed Processing. 2009. P. 1—5.
11. Tanenbaum A. S. Structured Computer Organization. 2001.
12. Barasz M., Boros B., Ligeti P., Loja K., Nagy D. A. Breaking EMAP // SecureComm. 2007. P. 514—517.
13. Li T., Wang G. Security Analysis of Two UltraLightweight RFID Authentication Protocols // IFIPSEC’07. 2007. P. 109—120.
14. Yu H. SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity // Dependable and Secure Computing. IEEE Transact. on Date of Publication. 2007.
15. Kianersi M., Gardeshi M., Arjmand M.SULMA: A Secure Ultra Light-Weight Mutual Authentication Protocol for Lowcost RFID Tags // Intern. J. of UbiComp. 2011. Vol. 2. P. 17.
16. Peris-Lopez P., Hernandez-Castro J. C., Tapiador J. M. E., Ribagorda A. Advances in Ultralightweight Cryptography for Low-cost RFID Tags: Gossamer Protocol // Workshop on Information Security Applications. 2008. Vol. 5379. P. 56—68.
Данил Александрович Ковалев Сергей Валентинович Беззатеев
Сведения об авторах — аспирант; Санкт-Петербургский государственный университет аэро-
космического приборостроения, кафедра технологий защиты информации; E-mail: iostreamawm@gmail.com — д-р техн. наук, доцент; Санкт-Петербургский государственный университет аэрокосмического приборостроения, кафедра технологий защиты информации; заведующий кафедрой; E-mail: bsv@aanet.ru
Рекомендована кафедрой № 51 безопасности информационных систем
Поступила в редакцию 01.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8