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

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

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

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

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

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

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

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

При реализации протокола Брандсона-Чаума в случае когда, сторона ${\displaystyle P}$ знает через какое время придет следующий ${\displaystyle \alpha _{i}}$ бит, ответный ${\displaystyle \beta _{i}}$ бит стороне ${\displaystyle V}$ может отослать заранее, тем самым, совершив мошенничество с расстоянием между участниками^[1].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дальше наступает фаза из ${\displaystyle n}$ быстрых обменов битами: на ${\displaystyle i}$ итерации, ${\displaystyle R}$ генерирует случайный бит ${\displaystyle c_{i}}$ и отравляет ${\displaystyle T}$, зафиксировав, при этом, время ${\displaystyle t_{1}}$. Сторона ${\displaystyle T}$ получает бит ${\displaystyle c_{i}'}$, который может не равняться биту ${\displaystyle c_{i}}$, из-за ошибок в канале связи или стороннего вмешательства. В ответ, ${\displaystyle T}$ отправляет бит ${\displaystyle r_{i}=R_{i}^{c_{i}}}$, и незамедлительно, после получение бита ${\displaystyle r_{i}'}$, который не обязан равняться ${\displaystyle r_{i}}$, сторона ${\displaystyle R}$ фиксирует время ${\displaystyle t_{2}}$ и вычисляет время ${\displaystyle \Delta t_{i}=t_{2}-t_{1}}$.

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

• ${\displaystyle c_{i}\neq c_{i}'}$
• ${\displaystyle c_{i}=c_{i}'}$, но ${\displaystyle r_{i}\neq R_{i}^{c_{i}}}$
• ${\displaystyle c_{i}=c_{i}'}$, но ${\displaystyle \Delta t_{i}>t_{max}}$

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

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

• 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.
• Chong 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.