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

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

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

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

ОписаниеПравить

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

 

Идея дистанционно-ограниченного протокола Брандсона-Чаума основана на принципе «вызов-ответ». Пусть имеется два участника: $P$$P$  - доказывающая сторона, которая доказывает свое знание секрета. $V$$V$  - проверяющая сторона, которая проверяет подлинность этого секрета. Перед обменом сообщений, стороны $V$$V$  и $P$$P$  генерируют случайную последовательность $k$$k$ -бит, $\mathrm{\alpha <!--\; \alpha \; -->}=({\mathrm{\alpha <!--\; \alpha \; -->}}_1,...,{\mathrm{\alpha <!--\; \alpha \; -->}}_k)$$\alpha =(\alpha _{1},...,\alpha _{k})$  и $\mathrm{\beta <!--\; \beta \; -->}=({\mathrm{\beta <!--\; \beta \; -->}}_1,...,{\mathrm{\beta <!--\; \beta \; -->}}_k)$$\beta =(\beta _{1},...,\beta _{k})$  соответственно. Параметр $k$$k$  является секретным параметром протокола. Данный протокол разбивается на две части:

• Сначала происходит $k$$k$  мгновенных обменов битами - сторона $P$$P$  после получение бита ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  от $V$$V$  отправляет ответный бит ${\mathrm{\beta <!--\; \beta \; -->}}_i$$\beta _{i}$  незамедлительно(«low-level distance-bounding exchange»).

• После этого $P$$P$  отправляет сообщение $m={\mathrm{\alpha <!--\; \alpha \; -->}}_1|{\mathrm{\beta <!--\; \beta \; -->}}_1|...|{\mathrm{\alpha <!--\; \alpha \; -->}}_k|{\mathrm{\beta <!--\; \beta \; -->}}_k$$m=\alpha _{1}|\beta _{1}|...|\alpha _{k}|\beta _{k}$  с его секретным ключом стороне $V$$V$ . Далее проверяющая сторона $V$$V$  с помощью протокола идентификации проверяет достоверность секрета, а также вычислить расстояние(«upper-bound distance») между участниками $L=ma{x}_k(t_i)$$L=max_{k}(t_{i})$ , где $t_i$$t_{i}$ - время между отправлением ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  бита и получением ${\mathrm{\beta <!--\; \beta \; -->}}_i$$\beta _{i}$ .

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

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

 

При реализации протокола Брандсона-Чаума в случае когда, сторона $P$$P$  знает через какое время придет следующий ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  бит, ответный ${\mathrm{\beta <!--\; \beta \; -->}}_i$$\beta _{i}$  бит стороне $V$$V$  может отослать заранее, тем самым, совершив мошенничество с расстоянием между участниками.

Один из вариантов предотвращении данного обмана, заключается в случайном изменении времени отправления бита стороной $V$$V$ .

Другой вариант - это измененная версия протокола Брандсона-Чаума, предотвращающая сразу два вида мошенничества. Как и в основной версии, обе стороны генерируют случайную последовательность $k$$k$ -бит. При $k$$k$  мгновенных обменов битами сторона $V$$V$  отсылает ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  бит стороне $P$$P$ , в свою очередь, сторона $P$$P$  отсылает бит $m_i={\mathrm{\beta <!--\; \beta \; -->}}_i\oplus <!--\; \oplus \; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i$$m_{i}=\beta _{i}\oplus \alpha _{i}$  стороне $V$$V$ . После обмена, сторона $P$$P$  должна отправить биты $\mathrm{\beta <!--\; \beta \; -->}=({\mathrm{\beta <!--\; \beta \; -->}}_1,...,{\mathrm{\beta <!--\; \beta \; -->}}_k)$$\beta =(\beta _{1},...,\beta _{k})$  с секретным ключом стороне $V$$V$ по защищенному протоколу. Сторона $V$$V$  проверяет равенство ${\mathrm{\beta <!--\; \beta \; -->}}_i=m_i\oplus <!--\; \oplus \; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i,\mathrm{\forall <!--\; \forall \; -->}i=\stackrel{¯<!--\; ¯\; -->}{1,k}$$\beta _{i}=m_{i}\oplus \alpha _{i},\forall i={\overline {1,k}}$  и после этого с помощью протокола идентификации проверяет достоверность секрета.

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

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

 

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

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

После этого, начинается серия из $n$$n$  мгновенных обменов битами между двумя сторонами: сгенерированное случайным образом стороной $V$$V$  бит $C_i$$C_{i}$ («отклик») отправляется стороне $P$$P$ , при этом, если бит $C_i=0$$C_{i}=0$ , то сторона $P$$P$  отправляет в ответ бит $R_i^0$$R_{i}^{0}$ , в противном случае, бит $R_i^1$$R_{i}^{1}$ . Сторона $V$$V$  же проверяет полученный бит на равенство со своим битом $R_i^{C_i}$$R_{i}^{C_{i}}$ , а также для каждого $i$$i$  вычисляет расстояние $d^{\prime }$$d'$  между $P$$P$  и $V$$V$ , и проверяет, чтобы $d'<d$ , где $d^{\prime }=\frac{c\ast <!--\; \ast \; -->t_m}{2}$$d'={\frac {c*t_{m}}{2}}$  , $t_m$$t_{m}$ - время между обменом битами, $c$$c$  - скорость света, $d$$d$  - фиксированная величина.

Если сторону $V$$V$  удовлетворяют условия, то обмен считается успешным.

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

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

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

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

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

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

Стороны $P$$P$  и $V$$V$  заранее договариваются, на какой итерации произойдет пустой отклик. Если во время пустого отклика, сторона $P$$P$  получает бит $0$$0$  или $1$$1$ , то $P$$P$  заключает, что протокол ненадежный.

Перед началом медленной фазы стороны разделяют секрет $x$$x$ , получают секретный ключ протокола $n$$n$  и псевдослучайную функцию $H$$H$ , выдающую случайную последовательность бит размера $4n$$4n$ , и устанавливают временной порог одиночного обмена битами $\mathrm{\Delta <!--\; \Delta \; -->}{t}_{max}$$\Delta t_{max}$ .

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

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

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

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

Протокол ХитомиПравить

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

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

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

Дальше наступает фаза из $n$$n$  быстрых обменов битами: на $i$$i$  итерации, $R$$R$  генерирует случайный бит $c_i$$c_{i}$  и отравляет $T$$T$ , зафиксировав, при этом, время $t_1$$t_{1}$ . Сторона $T$$T$  получает бит $c_i^{\prime }$$c_{i}'$ , который может не равняться биту $c_i$$c_{i}$ , из-за ошибок в канале связи или стороннего вмешательства. В ответ, $T$$T$  отправляет бит $r_i=R_i^{c_i}$$r_{i}=R_{i}^{c_{i}}$ , и незамедлительно, после получение бита $r_i^{\prime }$$r_{i}'$ , который не обязан равняться $r_i$$r_{i}$ , сторона $R$$R$  фиксирует время $t_2$$t_{2}$  и вычисляет время $\mathrm{\Delta <!--\; \Delta \; -->}{t}_i=t_2-<!--\; -\; -->t_1$$\Delta t_{i}=t_{2}-t_{1}$ .

В финальной фазе, $T$$T$  отправляет сообщение $m=(c_1^{\prime },...,c_n^{\prime },r_1^{\prime },...,r_n^{\prime })$$m=(c_{1}',...,c_{n}',r_{1}',...,r_{n}')$  и $T_B=F_x(m,ID,N_R,N_{T_1},N_{T_2},N_{T_3})$$T_{B}=F_{x}(m,ID,N_{R},N_{T_{1}},N_{T_{2}},N_{T_{3}})$  стороне $R$$R$ , где $ID$$ID$  - уникальный идентификатор передатчика. В конечном итоге, $R$$R$  разбивает ошибки на три типа:

• $c_i\ne <!--\; \ne \; -->c_i^{\prime }$$c_{i}\neq c_{i}'$ 
• $c_i=c_i^{\prime }$$c_{i}=c_{i}'$ , но $r_i\ne <!--\; \ne \; -->R_i^{c_i}$$r_{i}\neq R_{i}^{c_{i}}$ 
• $c_i=c_i^{\prime }$$c_{i}=c_{i}'$ , но $\mathrm{\Delta <!--\; \Delta \; -->}{t}_i>t_{max}$$\Delta t_{i}>t_{max}$ 

Если суммарное количество ошибок удовлетворяет начальным условиям стороны $R$$R$ , и, в случае необходимости аутентификации, стороне $T$$T$  удовлетворяет число $T_A=F_x(N_R,k_2)$$T_{A}=F_{x}(N_{R},k_{2})$  , полученное от $R$$R$ , то протокол является надежным для обмена.

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

ЛитератураПравить

• Brands S. A., Chaum D. Distance-Bounding Protocols (англ.): Extended abstract // Advances in Cryptology — EUROCRYPT ’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T. Helleseth — 1 — Berlin: Springer Berlin Heidelberg, 1994. — P. 344—359. — 465 p. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_30
• International Journal of Critical Infrastructure Protection (англ.) — Elsevier BV. — Vol. 11. — P. 51—61. — ISSN 1874-5482; 2212-2087
• Progress in Cryptology — INDOCRYPT 2009 (англ.): 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009. Proceedings / B. Roy, N. Sendrier — Springer Berlin Heidelberg, 2009. — P. 293—295. — ISBN 978-3-642-10627-9
• 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.