Обман, здійсненний мафією

Обман, здійсненний мафією (англ. Mafia fraud attack) — один із способів зловживання доведенням з нульовим пізнанням. Вперше даний метод був описаний Іво Десмедтом (англ. Yvo Desmedt). Свою назву метод отримав завдяки висловлюванню Аді Шаміра, сказаному ним під час обговорення протоколу ідентифікації із нульовим знанням Файга-Фіата-Шаміра:

Я можу ходити в магазин, який належить мафії, хоч мільйон разів поспіль, а вони все одно не матимуть можливості видати себе за мене.

Оригінальний текст (англ.)

I can go to a Mafia-owned store a million successive times and they still will not be able to misrepresent themselves as me.

Але насправді подібне шахрайство можливе.

Опис

Опис Обману, виконаного мафією

Нехай є 4 учасника: A, B, C, D. Причому B і С співпрацюють між собою («належать одній мафії»). А доводить свою особистість B, а С хоче видати себе за A перед D. Зазвичай, шахрайство описують наступною ситуацією: B володіє рестораном, що належать мафії, С — також представник мафії, D — ювелір. A і D не знають про майбутнє шахрайство. В момент, коли A готовий заплатити за обід і ідентифікувати себе перед B, B сповіщає С про початок шахрайства. Це можливо, завдяки наявності радіо-каналу між ними. У цей час, С вибирає діамант, який хоче купити, і D починає ідентифікувати особу С (а насправді A). С передає питання по протоколу B, а той, у свою чергу, задає його А. Відповідь передається у зворотному порядку. Таким чином, А не заплатить тільки за обід, але і за дорогий діамант.

Як видно з вищеописаного, існують певні вимоги для подібного шахрайства. Наприклад, моменти, коли А починає доводити свою особу перед B, а С — перед D повинні бути точно синхронізовані.

Обман, виконаний мафією, виявляється дієвим в ситуаціях, коли потрібно здійснити атаку на систему, в якій аутентифікація є успішною лише за умови, що учасник знаходиться в безпосередній близькості від перевіряючої сторони, і успішна аутентифікація дозволяє тому, хто доказує, отримати якийсь сервіс, що надається стороною, яка перевіряє.

Приклади застосування

• Обман, виконаний мафією, широко застосовується для атаки на RFID-системи. RFID-система (англ. Radio Frequency IDentification, радіочастотна ідентифікація) складається з пристрою, що зчитує (рідер) і транспондера (RFID-мітки). Припустимо, зловмисник збирається отримати несанкціонований доступ до автомобіля. Доступ забезпечується за допомогою RFID (в даному випадку транспондером буде безконтактна картка). Зловмисник, у якого є підроблена картка («rogue card»), розташований поруч з автомобілем і встановлює зв'язок між своєю карткою і рідером RFID-системи автомобіля («legitimate reader»). У той же час спільник, який володіє ще одним зчитувальним пристроєм («rogue reader»), знаходиться поруч з власником автомобіля і встановлює з'єднання із картою легітимного власника. Таким чином, той із злочинців, хто володіє підробленою карткою, передає повідомлення, отримані від легітимного рідера, своєму спільнику, який пересилає ці повідомлення карті (транспондеру) власника автомобіля. Відповідь, одержана із легітимного транспондера, пересилається з того ж ланцюга у зворотному напрямку і, зрештою, доходить до рідера, встановленого на автомобілі.
• Mafia fraud attack також може застосовуватися для атаки на системи радіолокаційного розпізнавання «Свій-чужий» (IFF — Identification Friend or Foe). Багато IFF-системи використовують спосіб аутентифікації «виклик-відповідь» («challenge — response authentication»). Наприклад, два літака W і B можуть ідентифікувати один одного за допомогою IFF, в той час, як два ворожих літака A1 і A2 намагаються видати себе за «своїх». У цьому випадку застосовується схема, аналогічна схемі для атаки на RFID-системи. Наприклад, W посилає запит A1, для того щоб він підтвердив свою особистість, A1 пересилає повідомлення A2, A2, в свою чергу, надсилає цей запит літака B, який, будучи «своїм» для W, відповідає вірним повідомленням. Дана відповідь тим же шляхом передається W. Таким чином, W і B будуть вважати «своїми» A1 і A2 відповідно.

Способи запобігання

Дистанційно-обмежені протоколи (Distance-bounding protocols)

Техніка запобігання обману, виконаного мафією, яка задіює, так звані, дистанційно-обмежені протоколи («distance-bounding protocols»), вперше була наведена в роботі Стефана Брандса (Stefan Brands) і Дейвіда Чаума (David Chaum). Ця техніка застосовується, коли одній із взаємодіючих, відповідно до певного криптографічного протоколу, сторін необхідно знати, що інший учасник знаходиться на відстані, не більшій за визначену. Наприклад, якщо людина застосовує електронний пропуск на вході в будівлю, система аутентифікації повинна визначити, що людина перебуває від входу на відстані, не більшій певного. Згідно Брандсу і Чауму, основний елемент дистанційно-обмеженого протоколу простий. Він ґрунтується на принципі «виклик-відповідь». Відбувається k миттєвих обмінів бітами («rapid bit exchanges») між учасниками P та V, де P («Prover») — той, хто доводить своє знання, V («Verifier») — той, хто перевіряє справжність того, що доводить P. Параметр k є секретним параметром протоколу. Обмін бітами є миттєвим в тому сенсі, що P після отримання біта від V відправляє відповідний біт негайно.

Приклад дистанційно-обмеженого протоколу

Опис протоколу Ханке і Куна російською мовою.

Одним з поширених дистанційно-обмежених протоколів є протокол Герхарда Ханке (Gerhard P. Hancke) і Маркуса Куна (Markus G. Kuhn), широко застосовуваний в RFID-системах.

На першому етапі протоколу P (Prover) і V (Verifier) обмінюються одноразовими кодами, згенерованими випадковим чином (Nonce) (тобто P і V генерують і передають послідовності біт $N_{p}$ і $N_{v}$ відповідно). Потім обидві сторони обчислюють однакові бітові послідовності $v^{\left({0}\right)}$ і $v^{\left({1}\right)}$, використовуючи псевдовипадкову функцію (зазвичай це MAC або Криптографічна геш-функція), тобто $MAC_{K}\left({N_{v},N_{p}}\right)=v^{\left({0}\right)}\left|\right|v^{\left({1}\right)}$, тут K — це секретний ключ, відомий обом сторонам. Далі проводиться серія з n миттєвих обмінів бітами між двома сторонами. У кожному окремо взятому обміні V відправляє біт $C_{i}$ («виклик») стороні, що доказує, P. Якщо цей біт дорівнює 0, то P відправить в якості відповідного повідомлення біт під номером i з послідовності $v^{\left({0}\right)}$. Якщо ж $C_{i}$ дорівнює 1, то у відповідь повідомленням буде біт з номером i з послідовності $v^{\left({1}\right)}$. У свою чергу після кожного обміну бітами V перевіряє всі отримані повідомлення на коректність, а також порівнює час, що минув із моменту відправки повідомлення $C_{i}$ до моменту отримання відповідного біта, з деяким встановленим значенням t . Якщо всі отримані повідомлення і часи коректні, то обмін вважається успішним

Для того щоб здійснити атаку, зловмисник вбудовується в цю схему і до того, як V відправив повідомлення $C_{i}$, вгадує відповідний біт ${C_{i}}'$, потім відразу передає його стороні P. Коли зловмисник отримує повідомлення від P, то він порівнює $C_{i}$ і ${C_{i}}'$. Якщо біти збігаються (ймовірність збігу дорівнює 1/2), значить зловмисник передасть коректне повідомлення $v_{i}^{\left({C_{i}}\right)}$ стороні, яка перевіряє V, в більшості випадків, коли біти не співпали, шахрай намагається вгадати значення тепер уже $v_{i}^{\left({C_{i}}\right)}$ і передає його V. Таким чином, ймовірність, що зловмисник видасть правильне значення $v_{i}^{\left({C_{i}}\right)}$ дорівнює 3/4. Для n обмінів бітами отримуємо, що імовірність успішної атаки дорівнює ${\left({3 \over 4}\right)}^{n}$.

З моменту публікації роботи Ханке і Куна було запропоновано кілька рішень для збільшення ефективності протоколу, наприклад, Ту (Yu-Ju Tu) і Пірамуту (Selwyn Piramuthu) запропонували свій дистанційно-обмежений протокол, який задіює деякі принципи протоколу Ханке і Куна, але дозволяє знизити ймовірність успішної атаки до 9/16 (для одного обміну бітами).

Інші способи

1. Ідентифікація повинна проходити в клітці Фарадея. Якщо в магазині ювеліра буде клітка Фарадея, то мафіозі не зможуть обмінюватися повідомленнями.
2. Іво Десмедт і Томас Бет (англ. Thomas Beth) запропонували використовувати точний годинник. Якщо кожен етап протоколу буде проходити за точний період часу, то мафіозі просто не встигнуть передавати повідомлення один одному. Варто також враховувати, що повідомлення між стороною, яка доводить і стороною, яка підтверджує, передаються не миттєво, а з деякою затримкою. Ця затримка пов'язана з тим, що швидкість світла не безкінечна, тому на передачу повідомлень витрачається час, рівний $l/c$, де l — відстань між сторонами, а с — швидкість світла.

Інші методи зловживання доказом з нульовим розголошенням

Цікавим розширенням обману, виконаного мафією, є атака типу «обман, виконаний терористами». У даному вигляді атаки зловмисник A (adversary) і сторона, що доводить, поеребувають у змові, тобто, учасник, що доводить, P є нечесним учасником взаємодії (dishonest prover). P використовує допомогу шахрая, щоб довести стороні, яка перевіряє V, що знаходиться поблизу. Зловмисник не знає значення секретного ключа, яким володіє P. У цьому немає нічого дивного, так як зазвичай на практиці, A — це малий пристрій, що володіє деякою обчислювальною потужністю і пам'яттю. Даний пристрій має бути розташований поблизу V (перевіряюча сторона). Доводяча сторона не має повного контролю над зловмисником, таким чином, P не може довірити свій пароль пристрою A. В іншому випадку, наприклад, який-небудь інший шахрай може здійснити атаку на пристрій, заволодіти секретним ключем, що належать P, і видати себе за P.

Основним способом запобігання обману, виконаного терористами, також є застосування дистанційно-обмежених протоколів. Однак уникнути такої атаки допоможе не якийсь дистанційно-обмежений протокол, що застосовується у випадку шахрайства, здійсненого мафією. Наприклад, протокол Ханке і Куна, згаданий вище, є вразливим для обману терористів. Доводячий учасник протоколу, що знаходиться далеко від належної сторони V, може просто передати зловмиснику, розташованому поблизу від V, обчислені послідовності $v^{\left({0}\right)}$ та $v^{\left({1}\right)}$. Тоді шахрай зможе коректно відповідати на запити перевіряючого учасника, вкладаючись при цьому в часові рамки. Варто відзначити, що навіть володіючи послідовностями бітів $v^{\left({0}\right)}$ та $v^{\left({1}\right)}$, зловмисник не зможе в майбутньому видавати себе за P, оскільки він не знає секретного ключа, а послідовності $N_{p}$ та $N_{v}$ є одноразовими. Одним із відомих дистанційно-обмежених протоколів, що застосовуються для запобігання обману, виконаного терористами, є, наприклад, протокол Рейда (Reid et al.'s protocol).

Існує ще кілька методів зловживання доказом з нульовим розголошенням, таких як обман із декількома особами і проблема гросмейстера.

Див. також

• Атака «людина посередині»

Література

• Desmedt Y. G., Goutier C., Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (extended abstract) // Advances in Cryptology — CRYPTO ’87: A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: Springer Berlin Heidelberg, 1988. — P. 21–39. — (Lecture Notes in Computer Science; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN 0302-9743 — doi:10.1007/3-540-48184-2_3
• Desmedt Y. G. Major Security Problems with the "Unforgeable" (Feige)-Fiat-Shamir Proofs of Identity and How to Overcome Them // SECURICOM 88: 6th Worldwide Cong.Computer and Communications Security and Protection — Groupe Blenheim-SEDEP, 1988. — P. 147–159.
• Feige U., Fiat A., Shamir A. Zero-Knowledge Proofs of Identity // Journal of Cryptology / I. Damgård — Springer Science+Business Media, 1988. — Vol. 1, Iss. 2. — P. 77–94. — ISSN 0933-2790 — doi:10.1007/BF02351717
• Beth T., Desmedt Y. G. Identification Tokens — or: Solving The Chess Grandmaster Problem // Advances in Cryptology — CRYPTO ’90: 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes, S. A. Vanstone — Springer Berlin Heidelberg, 1991. — P. 169–176. — (Lecture Notes in Computer Science; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN 0302-9743 — doi:10.1007/3-540-38424-3_12
• Bengio S., Brassard G., Desmedt Y. G. et al. Secure implementation of identification systems // Journal of Cryptology / I. Damgård — Springer Science+Business Media, 1991. — Vol. 4, Iss. 3. — P. 175–183. — ISSN 0933-2790 — doi:10.1007/BF00196726
• Alkassar A., Stüble C. Towards Secure IFF: Preventing Mafia Fraud Attacks // MILCOM 2002. Proceedings — IEEE, 2002. — Т. 2. — ISBN 978-0-7803-7625-0
• Singelee D., Preneel B. Location verification using secure distance bounding protocols // Mobile Adhoc and Sensor Systems Conference, 2005. IEEE International Conference on — IEEE, 2005. — ISBN 978-0-7803-9465-0
• Zhang Y., Kitsos P. Security in RFID and Sensor Networks — Boston: Auerbach Publications, 2009. — 560 p. — (Wireless Networks and Mobile Communications) — ISBN 978-1-4200-6839-9
• Stefan Brands, David Chaum Distance-Bounding Protocols // Advances in Cryptology — EUROCRYPT ’93. — Springer Berlin Heidelberg, 1994. — С. 344-359.
• 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.
• 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.
• Cas Cremers, Kasper B. Rasmussen, Benedikt Schmidt, Srdjan Capkun Distance Hijacking Attacks on Distance Bounding Protocols // Proceedings of the 2012 IEEE Symposium on Security and Privacy. — IEEE Computer Society Washington, DC, 2012. — С. 113-127.
• Брюс Шнайер. Развитые протоколы // Прикладная криптография. — 2-е изд. — Триумф, 2003. — С. 92-93. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Jason Reid, Juan M. Gonz ́alez Nieto, Tee Tang, Bouchra Senadji Detecting Relay Attacks with Timing-Based Protocols // Proceeding ASIACCS '07 Proceedings of the 2nd ACM symposium on Information, computer and communications security. — ACM New York, NY, USA, 2007. — С. 204-213.
• Thomas Beth, Yvo Desmedt Identification Tokens — or: Solving The Chess Grandmaster Problem. — Springer Berlin Heidelberg, 1991.
• Dave Singelee, Bart Preneel Distance bounding in noisy environments // Proceeding ESAS'07 Proceedings of the 4th European conference on Security and privacy in ad-hoc and sensor networks. — Springer Berlin Heidelberg, 2007.