Preview

Математика и математическое моделирование

Расширенный поиск

Атака методом анализа сбоев на алгоритмы выработки имитовставок HMAC и NMAC

https://doi.org/10.24108/mathm.0420.0000235

Полный текст:

Аннотация

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

Атака методом анализа сбоев является одним из вариантов атаки на криптосистему по побочным каналам. Суть ее состоит в активном воздействии атакующим на физическое устройство, осуществляющее процесс вычислений (например, смарт-карту). Получаемые в результате воздействия искажения затем анализируются с целью восстановить секретную информацию, хранимую внутри устройства. Подобные атаки зачастую оказываются значительно эффективнее пассивных атак по побочным каналам.

Атаки методом анализа сбоев были предложены в более 20 лет назад. С тех пор были успешно построены атаки на реализации целого ряда симметричных и асимметричных криптоалгоритмов. Также был предложен ряд различных методов осуществления активного воздействия на процесс вычислений, с использованием конкретных физических эффектов и особенностей вычислительной среды. Также активно развиваются и подходы к противодействию такого рода атакам. Для этого используются как физические, так и чисто математические методы. Однако следует отметить, что криптографические хэш-функции, и более сложные криптосхемы, содержащие их в качестве компонент (например, некоторые имитовставки и цифровые подписи), в рамках этих работ представлены незначительно.

Важно отметить, что для практического применения конкретной атаки необходимо сочетание следующих факторов: наличия возможности конкретного физического воздействия на вычислительный процесс, адекватной математической модели данного физического воздействия и чисто математического компонента атаки --конкретного алгоритма внесения искажений и последующего анализа результатов. При этом решение каждой из этих задач по отдельности представляет самостоятельную теоретическую ценность.

Результаты настоящей работы не затрагивают физическую составляющую атаки, ограничиваясь лишь математикой. Иными словами, предложены конкретные алгоритмы внесения искажений и последующего анализа результатов. При этом конкретная модель сбоев считается известной и заданной. Рассмотрено несколько таких моделей, которые базируются на аналогах, ранее предложенных для других алгоритмов.

В качестве объекта исследований выбраны два стандарта формирования имитовставок: HMAC и NMAC. Указанные стандарты могут базироваться на любой криптографической хэш-функции, обеспечивающей нужный уровень стойкости. В данной работе исследованы четыре примера широкораспространенных хэшей: MD5, MD4, SHA-1, SHA-0.

Основными результатами данной работы являются следующие:

-     построены конкретные алгоритмы внесения искажений в вычислительный процесс, и их дальнейшего анализа, позволяющие извлечь секретную информацию (секретные ключи);

-     найдены и обоснованы оценки сложности таких атак (в терминах числа вносимых сбоев и трудоемкости последуюшего анализа) для различных сочетаний параметров(алгоритмов и моделей сбоев);

-     показано, что атаки могут быть проведены за разумное время.

Об авторе

А. А. Чиликов
МГТУ им. Н.Э. Баумана, Москва; Московский физико-технический институт, Долгопрудный
Россия

Чиликов Алексей Анатольевич

доцент, кафедра ИУ-8 (информационная безопасность), МГТУ им. Баумана, старший научный сотрудник, МФТИ, к.ф.-м.н.



Список литературы

1. Boneh D., DeMillo R.A., Lipton R.J. On the importance of checking cryptographic protocols for faults // Advances in cryptology – EUROCRYPT’ 97: 16th annual intern. conf. on theory and application of cryptographic techniques (Konstanz, Germany, May 11-15, 1997): Proc. B.; Hdbl.: Springer, 1997. Pp. 37-51. DOI: 10.1007/3-540-69053-0_4

2. Eli Biham, Adi Shamir. Differential fault analysis of secret key cryptosystems // Advances in cryptology - CRYPTO 1997: 17th annual intern. cryptology conf. (Santa Barbara, CA, USA, August 17-21, 1997): Proc. B.; Hdbl.: Springer, 1997. Pp. 513-525. DOI: 10.1007/BFb0052259

3. Blömer J., Seifert J.-P. Fault based cryptanalysis of the advanced encryption standard (AES) // Financial cryptography: 7th intern. conf. on financial cryptography: FC 2003 (Guadeloupe, French West Indies, January 27-30, 2003): Revised papers. B.; Hdbl.: Springer, 2003. Pp. 162-181. DOI: 10.1007/978-3-540-45126-6_12

4. Hoch J.J., Shamir A. Fault analysis of stream ciphers // Cryptographic hardware and embedded systems: 6th intern. workshop on cryptographic hardware and embedded systems: CHES 2004 (Camb., MA, USA, August 11-13, 2004): Proc. B.; Hdbl.: Springer, 2004. Pp. 240-253. DOI: 10.1007/978-3-540-28632-5_18

5. Armknecht F., Meier W. Fault attacks on combiners with memory // Selected areas in cryptography: 12th intern. workshop on selected areas in cryptography: SAC 2005 (Kingston, ON, Canada, August 11-12, 2005): Revised selected papers. B.; Hdbl.: Springer, 2006. Pp. 36-50. DOI: 10.1007/11693383_3

6. Biham E., Granboulan L., Phong Q. Nguyen. Impossible fault analysis of RC4 and differential fault analysis of RC4 // Fast software encryption: 12th intern. workshop on fast software encryption: FSE 2005 (Paris, France, February 21-23, 2005): Revised selected papers. B.; Hdbl.: Springer, 2005. Pp. 359-367. DOI: 10.1007/11502760_24

7. Breveglieri L., Koren I., Maistri P. A fault attack against the FOX cipher family // Fault diagnosis and tolerance in cryptography: 3rd intern. workshop on fault diagnosis and tolerance in cryptography: FDTC 2006 (Yokogama, Japan, October 10, 2006): Proc. B.; Hdbl.: Springer, 2006. Pp. 98-105. DOI: 10.1007/11889700_10

8. Clavier C., Gierlichs B., Verbauwhede I. Fault analysis study of IDEA // Topics in cryptology – CT-RSA 2008: The cryptographer’s track at the RSA conf. 2008 (San Francisco, CA, USA, April 8-11, 2008): Proc. B.; Hdbl.: Springer, 2008. Pp. 274-287. DOI: 10.1007/978-3-540-79263-5_17

9. Hojsik M., Rudolf B. Differential fault analysis of trivium // Fast software encryption: 15th intern. workshop on fast software encryption: FSE 2008 (Lausanne, Switzerland, February 10-13, 2008): Revised selected papers. B.; Hdbl.: Springer, 2008. Pp. 158-172. DOI: 10.1007/978-3-540-71039-4_10

10. Hojsik M., Rudolf B. Floating fault analysis of trivium // Progress in cryptology - INDOCRYPT 2008: 9th intern. conf. on cryptology in India (Kharagpur, India, December 14-17, 2008): Proc. B.; Hdbl.: Springer, 2008. Pp. 239-250. DOI: 10.1007/978-3-540-89754-5_19

11. Berzati A., Canovas-Dumas C., Goubin L. Fault analysis of rabbit: toward a secret key leakage // Progress in cryptology – INDOCRYPT 2009: 10th intern. conf. on cryptology in India (New Delhi, India, December 13-16, 2009): Proc. B.; Hdbl.: Springer, 2009. Pp. 72-87. DOI: 10.1007/978-3-642-10628-6_5

12. Kircanski A., Youssef A.M. Differential fault analysis of rabbit // Selected areas in cryptography: 16th annual intern. workshop on selected areas in cryptography: SAC 2009 (Calgary, Alberta, Canada, August 13-14, 2009): Revised selected papers. B.; Hdbl.: Springer, 2009. Pp. 197-214. DOI: 10.1007/978-3-642-05445-7_13

13. Kircanski A., Youssef A.M. Differential fault analysis of HC-128 // Progress in cryptology – AFRICACRYPT 2010: 3rd intern. conf. on cryptology in Africa (Stellenbosch, South Africa, May 3-6, 2010): Proc. B.; Hdbl.: Springer, 2010. Pp. 261-278. DOI: 10.1007/978-3-642-12678-9_16

14. Kenneth Koon-Ho Wong, Bartlett H., Simpson L., Dawson E. Differential random fault attacks on certain CAESAR stream ciphers // Information security and cryptology - ICISC 2019: 22nd intern. conf. on information security and cryptology (Seoul, South Korea, December 4-6, 2019): Revised selected papers. Cham: Springer, 2020. Pp. 297-315. DOI: 10.1007/978-3-030-40921-0_18

15. Климцов В.Е., Чиликов А.А. Локализация сбоев при дифференциальном криптоанализе по ошибкам вычислений поточных шифров, основанных на нелинейных регистрах сдвига // Безопасные информационные технологии: 10-я междунар. науч.-техн. конф. (Москва, Россия, 3-4 декабря 2019 г.): Сб. тр. М.: Изд-во МГТУ им. Н.Э. Баумана, 2019. С. 172-175.

16. Ruilin Li, Jianxiong You, Bing Sun, Chao Li. Fault analysis study of the block cipher FOX64 // Multimedia Tools and Applications. 2013. Vol. 63. No. 3. Pp. 691-708. DOI: 10.1007/s11042-011-0895-x

17. Kenneth Koon-Ho Wong, Bartlett H., Simpson L., Dawson E. Differential random fault attacks on certain CAESAR stream ciphers (Supplementary material) // Cryptology ePrint Archive. 2020. Report 2020/022. Режим доступа: http://eprint.iacr.org/2020/022.pdf (дата обращения 16.09.2020).

18. Saha S., Bag A., Roy D.B., Patranabis S., Mukhopadhyay D. Fault template attacks on block ciphers exploiting fault propagation // Advances in cryptology - EUROCRYPT 2020: 39th annual intern. conf. on the theory and applications of cryptographic techniques (Zagreb, Croatia, May 10-14, 2020): Proc. Pt. 1. Cham: Springer, 2020. Pp. 612-643. DOI: 10.1007/978-3-030-45721-1_22

19. Biehl I., Meyer B., Muller V. Differential fault attacks on elliptic curve cryptosystems // Advances in cryptology - CRYPTO 2000: 20th annual intern. cryptology conf. (Santa Barbara, CA, USA, August 20-24, 2000): Proc. B.; Hdbl.: Springer, 2000. Pp. 131-146. DOI: 10.1007/3-540-44598-6_8

20. Boneh D., DeMillo R.A., Lipton R.J. On the importance of eliminating errors in cryptographic computations // J. of Cryptology. 2001. Vol. 14. No. 2. Pp. 101-119. DOI: 10.1007/s001450010016

21. Otto M. Fault attacks and countermeasures. Dissertation / Fakultat fur Elektrotechnik, Informatik und Mathematik; Institut fur Informatik; Universitat Paderborn. 2004. 189 s. Режим доступа: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.5710&rep=rep1&type=pdf (дата обращения 9.01.2021).

22. Ciet M., Joye M. Elliptic curve cryptosystems in the presence of permanent and transient faults // Designs, Codes and Cryptography. 2005. Vol. 36. No. 1. Pp. 33-43. DOI: 10.1007/s10623-003-1160-8

23. Blömer J., Otto M., Seifert J.-P. Sign change fault attacks on elliptic curve cryptosystems // Fault diagnosis and tolerance in cryptography: 3rd intern. workshop on fault diagnosis and tolerance in cryptography: FDTC 2006 (Yokogama, Japan, October 10, 2006): Proc. B.; Hdbl.: Springer, 2006. Pp. 36-52. DOI: 10.1007/11889700_4

24. Fouque P.-A., Lercier R., Real D., Valette F. Fault attack on elliptic curve Montgomery ladder implementation // Fault diagnosis and tolerance in cryptography: 5th workshop on fault diagnosis and tolerance in cryptography: FDTC 2008 (Wash., DC, USA, August 15, 2008): Proc. N.Y.: IEEE, 2008. Pp. 92-98. DOI: 10.1109/FDTC.2008.15

25. Chilikov A., Taraskin O. New fault attack on elliptic curve scalar multiplication // Cryptology ePrint Archive. 2009. Report 2009/528. Режим доступа: http://eprint.iacr.org/2009/528.pdf (дата обращения 16.09.2020).

26. Giraud C. DFA on AES // Advanced encryption standard – AES: 4th intern. conf. on advanced encryption standard (Bonn, Germany, May 10-12, 2004): Selected and invited papers. B.; Hdbl.: Springer, 2005. Pp. 27-41. DOI: 10.1007/11506447_4

27. Dusart P., Letourneux G., Vivolo O. Differential fault analysis on A.E.S. // Applied cryptography and network security: 1st intern. conf. on applied cryptography and network security: ACNS 2003 (Kunming, China, October 16-19, 2003): Proc. B.; Hdbl.: Springer, 2003. Pp. 293-306. DOI: 10.1007/978-3-540-45203-4_23

28. Chien-Ning Chen, Sung-Ming Yen. Differential fault analysis on AES key schedule and some countermeasures // Information security and privacy: 8th Australasian conf. on information security and privacy: ACISP 2003 (Wollogong, Australia, July 9-11, 2003): Proc. B.; Hdbl.: Springer, 2003. Pp. 118-129. DOI: 10.1007/3-540-45067-X_11

29. Piret G., Quisquater J.-J. A differential fault attack technique against SPN structures, with application to the AES and KHAZAD // Cryptographic hardware and embedded systems: 5th intern. workshop on cryptographic hardware and embedded systems: CHES 2003 (Cologne, Germany, September 8-10, 2003): Proc. B.; Hdbl.: Springer, 2003. Pp. 77-88. DOI: 10.1007/978-3-540-45238-6_7

30. Moradi A., Manzuri Shalmani M.T., Salmasizadeh M. A generalized method of differential fault attack against AES cryptosystem // Cryptographic hardware and embedded systems: 8th intern. workshop on cryptographic hardware and embedded systems: CHES 2006 (Yokogama, Japan, October 10-13, 2006): Proc. B.; Hdbl.: Springer, 2006. Pp. 91-100. DOI: 10.1007/11894063_8

31. Chong Hee Kim, Quisquater J.-J. New differential fault analysis on AES key schedule: Two faults are enough // Smart card research and advanced applications: 8th IFIP WG 8.8/11.2 intern. conf. on smart card research and advanced applications: CARDIS 2008 (London, UK, September 8-11, 2008): Proc. B.; Hdbl.: Springer, 2008. Pp. 48-60. DOI: 10.1007/978-3-540-85893-5_4

32. Mukhopadhyay D. An improved fault based attack of the advanced encryption standard // Progress in cryptology – AFRICACRYPT 2009: 2nd intern. conf. on cryptology in Africa (Gammarth, Tunisia, June 21-25, 2009): Proc. B.; Hdbl.: Springer, 2009. Pp. 421-434. DOI: 10.1007/978-3-642-02384-2_26

33. Ali S., Mukhopadhyay D., Tunstall M. Differential fault analysis of AES using a single multiple-byte fault. Режим доступа: http://eprint.iacr.org/2010/636.pdf (дата обращения 16.09.2020).

34. Roche T., Lomne V., Khalfallah K. Combined fault and side-channel attack on protected implementations of AES // Smart card research and advanced applications: 10th intern. conf. on smart card research and advanced applications: CARDIS 2011 (Leuven, Belgium, September 14-16, 2011): Revised selected papers. B.; Hdbl.: Springer, 2011. Pp. 65-83. DOI: 10.1007/978-3-642-27257-8_5

35. Skorobogatov S.P., Anderson R.J. Optical fault induction attacks // Cryptographic hardware and embedded systems - CHES 2002: 4th intern. workshop on cryptographic hardware and embedded systems (Redwood Shores, CA, USA, August 13-15, 2002): Revised papers. B.; Hdbl.: Springer, 2003. Pp. 2-12. DOI: 10.1007/3-540-36400-5_2

36. Krawczyk H., Bellare M., Canetti R. HMAC: Keyed-hashing for message authentication. Режим доступа: http://www.ietf.org/rfc/rfc2104.txt (дата обращения 17.09.2020).

37. Fouque P.-A., Leurent G., Real D., Valette F. Practical electromagnetic template attack on HMAC // Cryptographic hardware and embedded systems - CHES 2009: 11th intern. workshop on cryptographic hardware and embedded systems (Lausanne, Switzerland, September 6-9, 2009): Proc. B.; Hdbl.: Springer, 2009. Pp. 66-80. DOI: 10.1007/978-3-642-04138-9_6

38. Чиликов А.А. Fault-атаки на алгоритм HMAC: Доклад // РусКрипто’2010: науч.-практич. конф. (Подмосковье, 1-4 апреля 2010 г.). Режим доступа: http://www.ruscrypto.ru/resource/archive/rc2010/files/06_chilikov.pdf (дата обращения 17.09.2020).

39. Чиликов А.А. Fault-атаки на алгоритмы HMAC и NMAC // Актуальные проблемы организации и технологии защиты информации: 1-я межвуз. науч.-практич. конф. (С.-Петербург, 30 ноября - 1 декабря 2011 г.): Тр. СПб.: ИТМО, 2011.


Для цитирования:


Чиликов А.А. Атака методом анализа сбоев на алгоритмы выработки имитовставок HMAC и NMAC. Математика и математическое моделирование. 2020;(4):65-92. https://doi.org/10.24108/mathm.0420.0000235

For citation:


Chilikov A.A. Fault Attack on Message Authentication Codes HMAC and NMAC. Mathematics and Mathematical Modeling. 2020;(4):65-92. (In Russ.) https://doi.org/10.24108/mathm.0420.0000235

Просмотров: 384


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)