Визначення впливу плаваючої точки на безпеку алгоритму електронного підпису Falcon
DOI:
https://doi.org/10.15587/1729-4061.2024.295160Ключові слова:
квантово-стійкі перетворення, криптографія на решітках, атака на реалізацію, NIST PQC, NTRUАнотація
Об’єктом дослідження є електронні підписи. Схема електронного підпису Falcon є одним з фіналістів конкурсу NIST з постквантової криптографії. Однією з її ключових особливостей є використання обчислень з плаваючою крапкою. Проте, обчислення з плаваючою крапкою мають так званий шум округлення, що накопичується під час обчислень і у деяких випадках може призводити до суттєвих змін в оброблюваних значеннях. Робота присвячена проблемі використання шуму округлення для побудови атак на реалізацію електронних підписів. Головним результатом роботи є нова атака на реалізацію, що дозволяє відтворити таємний ключ. Нова атака відрізняється від вже існуючих атак використанням двох окремо безпечних реалізацій з різним порядком обчислень. У результаті проведеного аналізу було виявлено умови, за яких відтворення таємного ключа є можливим. Атака потребує 300000 підписів та наявності двох реалізацій для відтворення ключа. Ймовірність вдалого завершення атаки складає від 70 % до 76 %. Така ймовірність пояснюється структурою алгоритму вибірки Гауса, що використовується в електронному підписі Falcon. При цьому необхідною умовою проведення атаки є однакові seed при виробленні підпису. Ця умова робить атаку скоріш теоретичною, ніж практичною, оскільки при правильному впровадженні ЕП Falcon ймовірність використання двох однакових seed є незначною. Проте, можливість використання шуму обчислень з плаваючою крапкою показує, що для ЕП Falcon існують додаткові вектори атак, що мають враховуватися в моделях безпеки та потребують детальних досліджень. Отримані результати можуть бути використані при побудові моделей безпеки електронних підписів та їх впровадженні в існуючі інформаційно-комунікаційні системи
Посилання
- Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. Available at: https://falcon-sign.info/
- Post-Quantum Cryptography. NIST. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography
- Tran, T., Liu, B. (1977). Accumulation of roundoff errors in floating point FFT. IEEE Transactions on Circuits and Systems, 24 (3), 132–143. https://doi.org/10.1109/tcs.1977.1084316
- Gentry, C., Peikert, C., Vaikuntanathan, V. (2008). How to Use a Short Basis:Trapdoors for hard lattices and new cryptographic constructions. Available at: https://eprint.iacr.org/2007/432.pdf
- Lyubashevsky, V., Prest, T. (2015). Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices. Lecture Notes in Computer Science, 789–815. https://doi.org/10.1007/978-3-662-46800-5_30
- Ducas, L., Nguyen, P. Q. (2012). Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic. Lecture Notes in Computer Science, 415–432. https://doi.org/10.1007/978-3-642-34961-4_26
- Prest, T. (2015). Gaussian Sampling in Lattice-Based Cryptography. Paris: ENS PARIS. Available at: https://theses.hal.science/tel-01245066
- Prest, T. (2017). Sharper Bounds in Lattice-Based Cryptography Using the Rényi Divergence. Lecture Notes in Computer Science, 347–374. https://doi.org/10.1007/978-3-319-70694-8_13
- Ducas, L., Prest, T. (2016). Fast Fourier Orthogonalization. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. https://doi.org/10.1145/2930889.2930923
- Karabulut, E., Aysu, A. (2021). FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks. 2021 58th ACM/IEEE Design Automation Conference (DAC). https://doi.org/10.1109/dac18074.2021.9586131
- Guerreau, M., Martinelli, A., Ricosset, T., Rossi, M. (2022). The Hidden Parallelepiped Is Back Again: Power Analysis Attacks on Falcon. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022 (3), 141–164. https://doi.org/10.46586/tches.v2022.i3.141-164
- Zhang, S., Lin, X., Yu, Y., Wang, W. (2023). Improved Power Analysis Attacks on Falcon. Lecture Notes in Computer Science, 565–595. https://doi.org/10.1007/978-3-031-30634-1_19
- Falcon source files (reference implementation). Available at: https://falcon-sign.info/impl/falcon.h.html
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Oleksandr Potii, Olena Kachko, Serhii Kandii, Yevhenii Kaptol
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
