Русская Википедия:Дистанционно-ограниченные протоколы
Дистанционно-ограниченные протоколы (Шаблон:Lang-en) — криптографический протоколы аутентификации, основанные на определении расстояния между взаимодействующими лицами. Впервые протокол был разработан Стефаном Брандсом (Шаблон:Lang-en) и Дэвидом Чаумом (Шаблон:Lang-en) в 1993 годуШаблон:Sfn.
Основная идея заключается в достоверности знаний доказывающего участника («Prover»), путем проверки подлинности этих знаний проверяющим участником («Verifier») и в необходимости, что доказывающий участник находится на расстоянии от проверяющего, не более определенногоШаблон:Sfn.
Данные протоколы позволяют предотвратить такие виды криптографических атак на RFID-системы, как: атака посредника; обман, выполненный мафией; обман, выполненный террористами; мошенничество с расстояниемШаблон:Sfn.
Описание
Протокол Брандса-Чаума
Идея дистанционно-ограниченного протокола Брандсона-ЧаумаШаблон:Sfn основана на принципе «вызов-ответ». Пусть имеется два участника: <math>P</math> - доказывающая сторона, которая доказывает свое знание секрета. <math>V</math> - проверяющая сторона, которая проверяет подлинность этого секрета. Перед обменом сообщений, стороны <math>V</math> и <math>P</math> генерируют случайную последовательность <math>k</math>-бит, <math>\alpha=(\alpha_1,...,\alpha_k)</math> и <math>\beta=(\beta_1,...,\beta_k)</math> соответственно. Параметр <math>k</math> является секретным параметром протокола. Данный протокол разбивается на две части:
- Сначала происходит <math>k</math> мгновенных обменов битами - сторона <math>P</math> после получение бита <math>\alpha_i</math> от <math>V</math> отправляет ответный бит <math>\beta_i
</math> незамедлительно(«low-level distance-bounding exchange»).
- После этого <math>P</math> отправляет сообщение <math>m=\alpha_1|\beta_1|...|\alpha_k|\beta_k</math> с его секретным ключом стороне <math>V</math>. Далее проверяющая сторона <math>V</math> с помощью протокола идентификации проверяет достоверность секрета, а также вычислить расстояние(«upper-bound distance») между участниками <math>L=max_{k}(t_i)</math>, где <math>t_i</math>- время между отправлением <math>\alpha_i</math> бита и получением <math>\beta_i
</math>.
Данный протокол предотвращает обман, выполненный мафией с вероятностью <math>\frac{1}{2^k}</math>.Шаблон:Sfn
Измененная версия протокола Брандса-Чаума
При реализации протокола Брандсона-Чаума в случае когда, сторона <math>P</math> знает через какое время придет следующий <math>\alpha_i</math> бит, ответный <math>\beta_i </math> бит стороне <math>V</math> может отослать заранее, тем самым, совершив мошенничество с расстоянием между участникамиШаблон:Sfn.
Один из вариантов предотвращении данного обмана, заключается в случайном изменении времени отправления бита стороной <math>V</math>.
Другой вариант - это измененная версия протокола Брандсона-Чаума, предотвращающая сразу два вида мошенничества. Как и в основной версии, обе стороны генерируют случайную последовательность <math>k</math>-бит. При <math>k</math> мгновенных обменов битами сторона <math>V</math> отсылает <math>\alpha_i</math> бит стороне <math>P</math>, в свою очередь, сторона <math>P</math> отсылает бит <math>m_i=\beta_i\oplus\alpha_i</math> стороне <math>V</math>. После обмена, сторона <math>P</math> должна отправить биты <math>\beta=(\beta_1,...,\beta_k)</math> с секретным ключом стороне <math>V</math>по защищенному протоколу. Сторона <math>V</math> проверяет равенство <math>\beta_i=m_i\oplus\alpha_i, \forall i=\overline{1,k} </math> и после этого с помощью протокола идентификации проверяет достоверность секрета.
Недостаток протокола в том, что он не обрабатывает ошибки, связанные с потерей бита при обмене.Шаблон:Sfn
Протокол Ханке-Куна
В 2005 году Герхард Ханке(Шаблон:Lang-en) и Маркус Кун(Шаблон:Lang-en)Шаблон:Sfn предложили свою версию дистанционно-ограниченного протокола, широко применяемая в RFID-системахШаблон:Sfn.
Пусть имеются две стороны: <math>V</math> («RFID-reader») и <math>P</math> («RFID-token»). Сторона <math>V</math> генерирует случайным образом одноразовый ключ <math>N_v</math> и отправляет стороне <math>P</math>. Использовав псевдослучайную функцию (MAC или криптографическую хеш-функцию) обе стороны генерируют последовательность бит: <math>h(k,N_v)= R^0 || R^1</math>,где <math>R^0=(R_1^0,...,R_n^0), R^1=(R_1^1,...,R_n^1)</math>, a <math>k</math> - секретный ключ, известный обеим сторонам.
После этого, начинается серия из <math>n</math> мгновенных обменов битами между двумя сторонами: сгенерированное случайным образом стороной <math>V</math> бит <math>C_i</math>(«отклик») отправляется стороне <math>P</math>, при этом, если бит <math>C_i=0</math>, то сторона <math>P</math> отправляет в ответ бит <math>R_i^0</math>, в противном случае, бит <math>R_i^1</math>. Сторона <math>V</math> же проверяет полученный бит на равенство со своим битом <math>R_i^{C_i}</math>, а также для каждого <math>i</math> вычисляет расстояние <math>d'</math> между <math>P</math> и <math>V</math>, и проверяет, чтобы <math>d'< d</math>, где <math>d'=\frac{c*t_m}{2}</math> , <math>t_m</math>- время между обменом битами, <math>c</math> - скорость света, <math>d</math> - фиксированная величина.
Если сторону <math>V</math> удовлетворяют условия, то обмен считается успешным.
Вероятность атаки выполненной мафией и обмана с расстоянием при использовании данного протокола равна <math>\left ( \frac{3}{4} \right )^n</math>.Шаблон:Sfn
Также, на основе данного протокола, был создан протокол Ту-Пирамуту(Шаблон:Lang-en), который снижает вероятность успешной атаки до <math>\frac{9}{16}</math> (для одного обмена битами).Шаблон:Sfn
Недостатком протокола является потеря производительности при передаче подписанного сообщения, так как из-за возможности потери битов вследствие шума, сообщение нельзя послать через канал быстрого обмена битами.Шаблон:Sfn
Протокол Мунильи-Пейнадо
Для уменьшения вероятности мошенничества, на основе протокола Ханке-Куна, в 2008 году Ортиз Мунилья(Шаблон:Lang-en) и Пейнадо(Шаблон:Lang-en)Шаблон:Sfn создали свою версию дистанционно-ограниченного протокола. Главной особенностью протокола является возможность обнаружения атаки вовремя обмена битовШаблон:Sfn. Обмен битами разбивается на две категории:
- Полный отклик («full challenge») - стандартный обмен битами.
- Пустой отклик («void challenge») - никакого обмена битами не происходит.
Стороны <math>P</math> и <math>V</math> заранее договариваются, на какой итерации произойдет пустой отклик. Если во время пустого отклика, сторона <math>P</math> получает бит <math>0</math> или <math>1</math>, то <math>P</math> заключает, что протокол ненадежный.
Перед началом медленной фазы стороны разделяют секрет <math>x</math>, получают секретный ключ протокола <math>n</math> и псевдослучайную функцию <math>H</math>, выдающую случайную последовательность бит размера <math>4n</math>, и устанавливают временной порог одиночного обмена битами <math>\Delta t_{max}</math>.
Далее, в медленной фазе, стороны <math>P</math> и <math>V</math> после генерации одноразовых ключей <math>N_p</math> и <math>N_v</math>, соответственно, обмениваются этими ключами, для вычисления <math>H^{4n} = H(x,N_p,N_v)</math>. Получившаяся последовательность <math>4n</math>-бит разбивается на последовательность <math>R^0 = (H_1,...,H_{2n})</math> размера <math>2n</math> бит, <math>R^1=(H_{2n+1},...,H_{3n})</math>и <math>R^2=(H_{3n+1},...,H_{4n})</math> по <math>n</math> бит каждый. Бит <math>T_i</math> устанавливает, какой отклик вовремя быстрой фазы будет пустым или полным: если <math>H_{2i-1}H_{2i}=00</math>, <math>01</math> или <math>10</math>, то <math>T_i=0</math> - пустой отклик, в противном случае <math>T_i=1</math> - полный отклик, где биты <math>H_{2i-1}H_{2i}\subset R_0</math>.
После этого, в быстрой фазе, происходит аналогичный обмен битами, с помощью последовательностей <math>R_1</math> и <math>R_2</math>, как и в протоколе Ханке-Куна. В конечном итоге, если сторона <math>P</math> считает протокол надежным, то она отправляет <math>H(x, R^1, R^2)</math> стороне <math>V</math>.
Вероятность успешной криптоатаки равна <math>p = \left ( \frac{5}{8} \right )^n</math>.Шаблон:Sfn
Недостатком протокола является сложная реализация трех (физических) состояний протокола.Шаблон:Sfn
Протокол Хитоми
В 2010 году Педро Перис-Лопес (Шаблон:Lang-es), Хулио Эрнандес-Кастро (Шаблон:Lang-es) и др. на основе протокола «Швейцарского-ножа» создали протокол ХитомиШаблон:Sfn. Протокол обеспечивает аутентификацию между считывателем и передатчиком и гарантирует конфиденциальностьШаблон:Sfn.
Протокол разбивается на 3 части: две медленные фазы - подготовительная и финальная; и быстрая фаза - быстрый обмен битами между считывателем <math>R</math> (он же <math>V</math>) и передатчиком <math>T</math> (он же <math>P</math>).
В ходе подготовительной фазы <math>R</math> выбирает случайное число <math>N_R</math> и отравляет его стороне <math>T</math>. После этого, <math>T</math> генерирует 3 случайных числа <math>N_{T_1}</math>, <math>N_{T_2}</math>, <math>N_{T_3}</math>и вычисляет временные ключи <math>k_1 = F_x(N_R,N_{T_1},W)</math> и <math>k_2 = F_x(N_{T_2},N_{T_3},W')</math>, где <math>F_x(\bullet)</math>- псевдослучайная функция, зависящая от секретного ключа <math>x</math>, а <math>W</math> и <math>W'</math> два постоянных параметра. Далее, постоянный секретный ключ <math>x</math> разделяется на два регистра <math>R^0=k_1</math> и <math>R^1 = k_2 \oplus x</math>. И в завершении фазы, <math>T</math> отправляет стороне <math>R</math> числа <math>N_{T_1}</math>, <math>N_{T_2}</math>, <math>N_{T_3}</math>.
Дальше наступает фаза из <math>n</math> быстрых обменов битами: на <math>i</math> итерации, <math>R</math> генерирует случайный бит <math>c_i</math> и отравляет <math>T</math>, зафиксировав, при этом, время <math>t_1</math>. Сторона <math>T</math> получает бит <math>c_i'</math>, который может не равняться биту <math>c_i</math>, из-за ошибок в канале связи или стороннего вмешательства. В ответ, <math>T</math> отправляет бит <math>r_i = R_i^{c_i}</math>, и незамедлительно, после получение бита <math>r_i'</math>, который не обязан равняться <math>r_i</math>, сторона <math>R</math> фиксирует время <math>t_2</math> и вычисляет время <math>\Delta t_i = t_2 - t_1</math>.
В финальной фазе, <math>T</math> отправляет сообщение <math>m = (c_1',...,c_n',r_1',...,r_n')</math> и <math>T_B = F_x(m,ID,N_R,N_{T_1},N_{T_2},N_{T_3})</math> стороне <math>R</math>, где <math>ID</math> - уникальный идентификатор передатчика. В конечном итоге, <math>R</math> разбивает ошибки на три типа:
- <math>c_i \neq c_i'</math>
- <math>c_i = c_i'</math>, но <math>r_i \neq R_i^{c_i}</math>
- <math>c_i = c_i'</math>, но <math>\Delta t_i > t_{max}</math>
Если суммарное количество ошибок удовлетворяет начальным условиям стороны <math>R</math>, и, в случае необходимости аутентификации, стороне <math>T</math> удовлетворяет число <math>T_A = F_x(N_R,k_2)</math> , полученное от <math>R</math>, то протокол является надежным для обмена.
Вероятность криптоатаки выполненной мафией или мошенничества с расстоянием <math>p=\left ( \frac{1}{2} \right )^n</math>.Шаблон:Sfn
Примечания
Литература
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
.png){kind=link}
