Дистанционно-ограниченные протоколы

Дистанционно-ограниченные протоколы (англ. Distance-bounding protocols) — криптографический протоколы аутентификации, основанные на определении расстояния между взаимодействующими лицами. Впервые протокол был разработан Стефаном Брандсом (англ. Stefan Brands) и Дейвидом Чаумом (англ. David Chaum) в 1993 году.

Основная идея заключается в достоверности знаний доказывающего участника («Prover»), путем проверки подлинности этих знаний проверяющим участником («Verifier») и в необходимости, что доказывающий участник находится на расстоянии от проверяющего, не более определенного.

Данные протоколы позволяют предотвратить такие виды криптографических атак на RFID-системы, как: атака посредника; обман, выполненный мафией; обман, выполненный террористами; мошенничество с расстоянием.

Описание

Протокол Брандсона-Чаума

Идея дистанционно-ограниченного протокола Брандсона-Чаума основана на принципе «вызов-ответ». Пусть имеется два участника: [math]\displaystyle{ P }[/math] - доказывающая сторона, которая доказывает свое знание секрета. [math]\displaystyle{ V }[/math] - проверяющая сторона, которая проверяет подлинность этого секрета. Перед обменом сообщений, стороны [math]\displaystyle{ V }[/math] и [math]\displaystyle{ P }[/math] генерируют случайную последовательность [math]\displaystyle{ k }[/math]-бит, [math]\displaystyle{ \alpha=(\alpha_1,...,\alpha_k) }[/math] и [math]\displaystyle{ \beta=(\beta_1,...,\beta_k) }[/math] соответственно. Параметр [math]\displaystyle{ k }[/math] является секретным параметром протокола. Данный протокол разбивается на две части:

• Сначала происходит [math]\displaystyle{ k }[/math] мгновенных обменов битами - сторона [math]\displaystyle{ P }[/math] после получение бита [math]\displaystyle{ \alpha_i }[/math] от [math]\displaystyle{ V }[/math] отправляет ответный бит [math]\displaystyle{ \beta_i }[/math] незамедлительно(«low-level distance-bounding exchange»).

• После этого [math]\displaystyle{ P }[/math] отправляет сообщение [math]\displaystyle{ m=\alpha_1|\beta_1|...|\alpha_k|\beta_k }[/math] с его секретным ключом стороне [math]\displaystyle{ V }[/math]. Далее проверяющая сторона [math]\displaystyle{ V }[/math] с помощью протокола идентификации проверяет достоверность секрета, а также вычислить расстояние(«upper-bound distance») между участниками [math]\displaystyle{ L=max_{k}(t_i) }[/math], где [math]\displaystyle{ t_i }[/math]- время между отправлением [math]\displaystyle{ \alpha_i }[/math] бита и получением [math]\displaystyle{ \beta_i }[/math].

Данный протокол предотвращает обман, выполненный мафией с вероятностью [math]\displaystyle{ \frac{1}{2^k} }[/math].

Измененная версия протокола Брандсона-Чаума

При реализации протокола Брандсона-Чаума в случае когда, сторона [math]\displaystyle{ P }[/math] знает через какое время придет следующий [math]\displaystyle{ \alpha_i }[/math] бит, ответный [math]\displaystyle{ \beta_i }[/math] бит стороне [math]\displaystyle{ V }[/math] может отослать заранее, тем самым, совершив мошенничество с расстоянием между участниками.

Один из вариантов предотвращении данного обмана, заключается в случайном изменении времени отправления бита стороной [math]\displaystyle{ V }[/math].

Другой вариант - это измененная версия протокола Брандсона-Чаума, предотвращающая сразу два вида мошенничества. Как и в основной версии, обе стороны генерируют случайную последовательность [math]\displaystyle{ k }[/math]-бит. При [math]\displaystyle{ k }[/math] мгновенных обменов битами сторона [math]\displaystyle{ V }[/math] отсылает [math]\displaystyle{ \alpha_i }[/math] бит стороне [math]\displaystyle{ P }[/math], в свою очередь, сторона [math]\displaystyle{ P }[/math] отсылает бит [math]\displaystyle{ m_i=\beta_i\oplus\alpha_i }[/math] стороне [math]\displaystyle{ V }[/math]. После обмена, сторона [math]\displaystyle{ P }[/math] должна отправить биты [math]\displaystyle{ \beta=(\beta_1,...,\beta_k) }[/math] с секретным ключом стороне [math]\displaystyle{ V }[/math]по защищенному протоколу. Сторона [math]\displaystyle{ V }[/math] проверяет равенство [math]\displaystyle{ \beta_i=m_i\oplus\alpha_i, \forall i=\overline{1,k} }[/math] и после этого с помощью протокола идентификации проверяет достоверность секрета.

Недостаток протокола в том, что он не обрабатывает ошибки, связанные с потерей бита при обмене.

Протокол Ханке-Куна

В 2005 году Герхард Ханке(англ. Gerhard P. Hancke) и Маркус Кун(англ. Markus G. Kuhn) предложили свою версию дистанционно-ограниченного протокола, широко применяемая в RFID-системах.

Пусть имеются две стороны: [math]\displaystyle{ V }[/math] («RFID-reader») и [math]\displaystyle{ P }[/math] («RFID-token»). Сторона [math]\displaystyle{ V }[/math] генерирует случайным образом одноразовый ключ [math]\displaystyle{ N_v }[/math] и отправляет стороне [math]\displaystyle{ P }[/math]. Использовав псевдослучайную функцию(MAC или криптографическую хеш-функцию) обе стороны генерируют последовательность бит: [math]\displaystyle{ h(k,N_v)= R^0 || R^1 }[/math],где [math]\displaystyle{ R^0=(R_1^0,...,R_n^0), R^1=(R_1^1,...,R_n^1) }[/math], a [math]\displaystyle{ k }[/math] - секретный ключ, известный обеим сторонам.

После этого, начинается серия из [math]\displaystyle{ n }[/math] мгновенных обменов битами между двумя сторонами: сгенерированное случайным образов стороной [math]\displaystyle{ V }[/math] бит [math]\displaystyle{ C_i }[/math](«отклик») отправляется стороне [math]\displaystyle{ P }[/math], при этом, если бит [math]\displaystyle{ C_i=0 }[/math], то сторона [math]\displaystyle{ P }[/math] отправляет в ответ бит [math]\displaystyle{ R_i^0 }[/math], в противном случае, бит [math]\displaystyle{ R_i^1 }[/math]. Сторона [math]\displaystyle{ V }[/math] же проверяет полученный бит на равенство со своим битом [math]\displaystyle{ R_i^{C_i} }[/math], а также для каждого [math]\displaystyle{ i }[/math] вычисляет расстояние [math]\displaystyle{ d' }[/math] между [math]\displaystyle{ P }[/math] и [math]\displaystyle{ V }[/math], и проверяет, чтобы [math]\displaystyle{ d'\lt d }[/math], где [math]\displaystyle{ d'=\frac{c*t_m}{2} }[/math] , [math]\displaystyle{ t_m }[/math]- время между обменом битами, [math]\displaystyle{ c }[/math] - скорость света, [math]\displaystyle{ d }[/math] - фиксированная величина.

Если сторону [math]\displaystyle{ V }[/math] удовлетворяют условия, то обмен считается успешным.

Вероятность атаки выполненной мафией и обмана с расстоянием при использовании данного протокола равна [math]\displaystyle{ \left ( \frac{3}{4} \right )^n }[/math].

Также, на основе данного протокола, был создан протокол Ту-Пирамуту(англ. Tu-Piramuthu), который снижает вероятность успешной атаки до [math]\displaystyle{ \frac{9}{16} }[/math] (для одного обмена битами).

Недостатком протокола является потеря производительности при передаче подписанного сообщения, так как из-за возможности потери битов вследствие шума, сообщение нельзя послать через канал быстрого обмена битами.

Протокол Мунильи-Пейнадо

Для уменьшения вероятности мошенничества, на основе протокола Ханке-Куна, в 2008 году Ортиз Мунилья(англ. Ortiz Munilla) и Пейнадо(англ. Peinado) создали свою версию дистанционно-ограниченного протокола. Главной особенностью протокола является возможность обнаружения атаки вовремя обмена битов. Обмен битами разбивается на две категории:

• Полный отклик («full challenge») - стандартный обмен битами.
• Пустой отклик («void challenge») - никакого обмена битами не происходит.

Стороны [math]\displaystyle{ P }[/math] и [math]\displaystyle{ V }[/math] заранее договариваются, на какой итерации произойдет пустой отклик. Если во время пустого отклика, сторона [math]\displaystyle{ P }[/math] получает бит [math]\displaystyle{ 0 }[/math] или [math]\displaystyle{ 1 }[/math], то [math]\displaystyle{ P }[/math] заключает, что протокол ненадежный.

Перед началом медленной фазы стороны разделяют секрет [math]\displaystyle{ x }[/math], получают секретный ключ протокола [math]\displaystyle{ n }[/math] и псевдослучайную функцию [math]\displaystyle{ H }[/math], выдающую случайную последовательность бит размера [math]\displaystyle{ 4n }[/math], и устанавливают временной порог одиночного обмена битами [math]\displaystyle{ \Delta t_{max} }[/math].

Далее, в медленной фазе, стороны [math]\displaystyle{ P }[/math] и [math]\displaystyle{ V }[/math] после генерации одноразовых ключей [math]\displaystyle{ N_p }[/math] и [math]\displaystyle{ N_v }[/math], соответственно, обмениваются этими ключами, для вычисления [math]\displaystyle{ H^{4n} = H(x,N_p,N_v) }[/math]. Получившаяся последовательность [math]\displaystyle{ 4n }[/math]-бит разбивается на последовательность [math]\displaystyle{ R^0 = (H_1,...,H_{2n}) }[/math] размера [math]\displaystyle{ 2n }[/math] бит, [math]\displaystyle{ R^1=(H_{2n+1},...,H_{3n}) }[/math]и [math]\displaystyle{ R^2=(H_{3n+1},...,H_{4n}) }[/math] по [math]\displaystyle{ n }[/math] бит каждый. Бит [math]\displaystyle{ T_i }[/math] устанавливает, какой отклик вовремя быстрой фазы будет пустым или полным: если [math]\displaystyle{ H_{2i-1}H_{2i}=00 }[/math], [math]\displaystyle{ 01 }[/math] или [math]\displaystyle{ 10 }[/math], то [math]\displaystyle{ T_i=0 }[/math] - пустой отклик, в противном случае [math]\displaystyle{ T_i=1 }[/math] - полный отклик, где биты [math]\displaystyle{ H_{2i-1}H_{2i}\subset R_0 }[/math].

После этого, в быстрой фазе, происходит аналогичный обмен битами, с помощью последовательностей [math]\displaystyle{ R_1 }[/math] и [math]\displaystyle{ R_2 }[/math], как и в протоколе Ханке-Куна. В конечном итоге, если сторона [math]\displaystyle{ P }[/math] считает протокол надежным, то она отправляет [math]\displaystyle{ H(x, R^1, R^2) }[/math] стороне [math]\displaystyle{ V }[/math].

Вероятность успешной криптоатаки равна [math]\displaystyle{ p = \left ( \frac{5}{8} \right )^n }[/math].

Недостатком протокола является сложная реализация трех (физических) состояний протокола.

Протокол Хитоми

В 2010 году Педро Перис-Лопес (исп. Pedro Peris-Lopez), Хулио Эрнандес-Кастро (исп. Julio C. Hernandez-Castro) и др. на основе протокола «Швейцарского-ножа» создали протокол Хитоми. Протокол обеспечивает аутентификацию между считывателем и передатчиком и гарантирует конфиденциальность.

Протокол разбивается на 3 части: две медленные фазы - подготовительная и финальная; и быстрая фаза - быстрый обмен битами между считывателем [math]\displaystyle{ R }[/math] (он же [math]\displaystyle{ V }[/math]) и передатчиком [math]\displaystyle{ T }[/math] (он же [math]\displaystyle{ P }[/math]).

В ходе подготовительной фазы [math]\displaystyle{ R }[/math] выбирает случайное число [math]\displaystyle{ N_R }[/math] и отравляет его стороне [math]\displaystyle{ T }[/math]. После этого, [math]\displaystyle{ T }[/math] генерирует 3 случайных числа [math]\displaystyle{ N_{T_1} }[/math], [math]\displaystyle{ N_{T_2} }[/math], [math]\displaystyle{ N_{T_3} }[/math]и вычисляет временные ключи [math]\displaystyle{ k_1 = F_x(N_R,N_{T_1},W) }[/math] и [math]\displaystyle{ k_2 = F_x(N_{T_2},N_{T_3},W') }[/math], где [math]\displaystyle{ F_x(\bullet) }[/math]- псевдослучайная функция, зависящая от секретного ключа [math]\displaystyle{ x }[/math], а [math]\displaystyle{ W }[/math] и [math]\displaystyle{ W' }[/math] два постоянных параметра. Далее, постоянный секретный ключ [math]\displaystyle{ x }[/math] разделяется на два регистра [math]\displaystyle{ R^0=k_1 }[/math] и [math]\displaystyle{ R^1 = k_2 \oplus x }[/math]. И в завершении фазы, [math]\displaystyle{ T }[/math] отправляет стороне [math]\displaystyle{ R }[/math] числа [math]\displaystyle{ N_{T_1} }[/math], [math]\displaystyle{ N_{T_2} }[/math], [math]\displaystyle{ N_{T_3} }[/math].

Дальше наступает фаза из [math]\displaystyle{ n }[/math] быстрых обменов битами: на [math]\displaystyle{ i }[/math] итерации, [math]\displaystyle{ R }[/math] генерирует случайный бит [math]\displaystyle{ c_i }[/math] и отравляет [math]\displaystyle{ T }[/math], зафиксировав, при этом, время [math]\displaystyle{ t_1 }[/math]. Сторона [math]\displaystyle{ T }[/math] получает бит [math]\displaystyle{ c_i' }[/math], который может не равняться биту [math]\displaystyle{ c_i }[/math], из-за ошибок в канале связи или стороннего вмешательства. В ответ, [math]\displaystyle{ T }[/math] отправляет бит [math]\displaystyle{ r_i = R_i^{c_i} }[/math], и незамедлительно, после получение бита [math]\displaystyle{ r_i' }[/math], который не обязан равняться [math]\displaystyle{ r_i }[/math], сторона [math]\displaystyle{ R }[/math] фиксирует время [math]\displaystyle{ t_2 }[/math] и вычисляет время [math]\displaystyle{ \Delta t_i = t_2 - t_1 }[/math].

В финальной фазе, [math]\displaystyle{ T }[/math] отправляет сообщение [math]\displaystyle{ m = (c_1',...,c_n',r_1',...,r_n') }[/math] и [math]\displaystyle{ T_B = F_x(m,ID,N_R,N_{T_1},N_{T_2},N_{T_3}) }[/math] стороне [math]\displaystyle{ R }[/math], где [math]\displaystyle{ ID }[/math] - уникальный идентификатор передатчика. В конечном итоге, [math]\displaystyle{ R }[/math] разбивает ошибки на три типа:

• [math]\displaystyle{ c_i \neq c_i' }[/math]
• [math]\displaystyle{ c_i = c_i' }[/math], но [math]\displaystyle{ r_i \neq R_i^{c_i} }[/math]
• [math]\displaystyle{ c_i = c_i' }[/math], но [math]\displaystyle{ \Delta t_i \gt t_{max} }[/math]

Если суммарное количество ошибок удовлетворяет начальным условиям стороны [math]\displaystyle{ R }[/math], и, в случае необходимости аутентификации, стороне [math]\displaystyle{ T }[/math] удовлетворяет число [math]\displaystyle{ T_A = F_x(N_R,k_2) }[/math] , полученное от [math]\displaystyle{ R }[/math], то протокол является надежным для обмена.

Вероятность криптоатаки выполненной мафией или мошенничества с расстоянием [math]\displaystyle{ p=\left ( \frac{1}{2} \right )^n }[/math].

Литература

• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Gerhard P. Hancke, Markus G. Kuhn. An RFID Distance Bounding Protocol // SECURECOMM '05 Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks. — IEEE Computer Society Washington, DC, USA, 2005. — С. 67–73. Архивировано 21 октября 2016 года.
• Chong Hee Kim, Gildas Avoine, Fran ̧cois Koeune, Fran ̧cois-Xavier Standaert, Olivier Pereira. The Swiss-Knife RFID Distance Bounding Protocol // Information Security and Cryptology – ICISC 2008. — Springer Berlin Heidelberg, 2008. — С. 98-115.
• Yu-Ju Tu, Selwyn Piramuthu. RFID Distance Bounding Protocols // In 1st International EURASIP Workshop in RFID Technology, Vienna, Austria. — 2007.
• Сhong Hee Kim, Gildas Avoine. RFID distance bounding protocol with mixed challenges to prevent relay attacks // Universit ́e Catholique de Louvain Louvain-la-Neuve, B-1348, Belgium. — 2009.
• Fatemeh Baghernejad, Nasour Bagheri, Masoumeh Safkhan. Journal of Electrical and Computer Engineering Innovations // JECEI, Vol.2, No.2. — 2014.
• Pedro Peris-Lopez, Julio C. Hernandez-Castro, Christos Dimitrakakis, Aikaterini Mitrokotsa, Juan M. E. Tapiador. Shedding light on RFID distance bounding protocols and terrorist attacks // Computer Science, Cryptography and Security. — 2010.
• Agnes Brelurut, David Gerault, and Pascal Lafourcade. Survey of Distance Bounding Protocols and Threats // University Clermont Auvergne, LIMOS, France. — 2016.
• Gildas Avoine, Muhammed Ali Bingol, Suleyman Kardas, Cedric Lauradoux, Benjamin Martin. A Framework for Analyzing RFID Distance Bounding Protocols.
• Mohammad Reza Sohizadeh Abyaneh. Secutity Analysis of two Distance-Bounding Protocols // 7th International Workshop, RFIDSec 2011, Amherst, USA. — 2011.