Further Theoretical Analysis of Key Mismatch Attacks —A Case Study of NTRU-HRSS

ZHANG Xiao-han; CHENG Chi; YU Tian-run

doi:10.12263/DZXB.20220447

您当前的位置：

首页 >

文章列表页 >

Further Theoretical Analysis of Key Mismatch Attacks —A Case Study of NTRU-HRSS

PAPERS | 更新时间：2025-12-08

- Further Theoretical Analysis of Key Mismatch Attacks —A Case Study of NTRU-HRSS
- ACTA ELECTRONICA SINICA Vol. 51, Issue 4, Pages: 1081-1092(2023)
- 作者机构：
  
  1.中国地质大学(武汉)计算机学院智能地学信息处理湖北省重点实验室,湖北武汉430074
  2.桂林电子科技大学广西可信软件重点实验室,广西桂林 541004
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62172374);Guangxi Key Laboratory of Trusted Software(KX202038);Open Research Project of Hubei Key Laboratory of Intelligent Geo-Information Processing(KLIGIP2022B06)
- DOI：10.12263/DZXB.20220447
  CLC： TN918
- Received：24 April 2022，
  
  Revised：2022-12-22，
  
  Published：25 April 2023
- 稿件说明：
移动端阅览
张晓涵,程池,余天润.对密钥不匹配攻击的进一步理论分析——以NTRU-HRSS为例[J].电子学报,2023,51(04):1081-1092.

ZHANG Xiao-han,CHENG Chi,YU Tian-run.Further Theoretical Analysis of Key Mismatch Attacks —A Case Study of NTRU-HRSS[J].ACTA ELECTRONICA SINICA,2023,51(04):1081-1092.
张晓涵,程池,余天润.对密钥不匹配攻击的进一步理论分析——以NTRU-HRSS为例[J].电子学报,2023,51(04):1081-1092. DOI： 10.12263/DZXB.20220447.

ZHANG Xiao-han,CHENG Chi,YU Tian-run.Further Theoretical Analysis of Key Mismatch Attacks —A Case Study of NTRU-HRSS[J].ACTA ELECTRONICA SINICA,2023,51(04):1081-1092. DOI： 10.12263/DZXB.20220447.

摘要

目前，由美国国家标准技术研究院发起的对抗量子密码算法标准化的进程已进入最后一轮，其中基于格上困难问题的方案备受青睐.已有研究表明，若公私钥对被重复使用，则可以对选择明文攻击安全的格密钥封装机制发起密钥不匹配攻击；甚至在侧信道信息的辅助下，相关攻击能对选择密文攻击安全的格KEM奏效.在现有的针对格KEM方案的密钥不匹配攻击中，大多数攻击方案假设敌手一次只能恢复一个私钥系数，然而一次性恢复多个私钥系数是更为合理的假设，并且也将进一步减少密钥不匹配攻击所需的平均问询次数.鉴于此，本文进一步分析了密钥不匹配攻击中恢复私钥系数所需的平均问询次数的理论值下界的问题.其基本思路是将该问题转化为寻找一棵最优二叉恢复树的问题，进而证明了平均问询次数的理论值下界十分接近香农熵.在此基础上，本文提出了一套计算模型，并将其应用于NTRU-HRSS KEM方案，得到了更为准确的理论值下界；进一步地，据此提出了一种成对恢复NIST第三轮入选方案NTRU-HRSS KEM私钥的密钥不匹配攻击方案.实验结果表明，与现有的攻击方案相比，在成功率基本持平的基础上，平均问询次数减少了35.3%，耗时减少了47.3%.此外，本文提出的攻击方案也能够用于优化现有的针对CCA安全的NTRU-HRSS KEM方案的侧信道攻击，并将所需的问询次数由2 447减少到1 193.

Abstract

Currently

the standardization process of post-quantum cryptographic algorithms initiated by the National Institute of Standards and Technology (NIST) has entered into the last round. Among them

lattice-based algorithms draw significant attention. Existing research shows that if the public-secret key pair is reused

key mismatch attacks can be launched on the chosen-plaintext attack (CPA)-secure or side-channel information assisted chosen-ciphertext attack (CCA)-secure lattice-based key encapsulation mechanisms (KEMs). Among the existing key mismatch attacks against NIST KEM algorithms

most attacks assume that the adversary can recover one coefficient of the secret key each time. However

a more reasonable assumption is recovering multiple secret key coefficients each time

which will further reduce the average number of queries needed for key mismatch attacks. Therefore

we analyze the problem of lower bounds on the average number of queries for recovering multiple secret key coefficients each time in the key mismatch attack. The problem can be transformed into searching for an optimum binary recovery tree

and the lower bound is proved to be near the Shannon entropy. Then we propose a calculation model applied to NTRU-HRSS KEM and obtain a more accurate theoretical lower bound. Furthermore

we propose a full key mismatch attack for pairwise recovering the secret key of NTRU-HRSS KEM. Experiments demonstrate that compared to the existing attack

based on almost the same accuracy

the average number of queries is reduced by 35.3%

and the average time is also reduced by 47.3%. Moreover

our proposed method can also be used to improve the existing side-channel attack against CCA-secure NTRU-HRSS KEM and reduce the average number of queries from 2 447 to 1 193.

关键词

Keywords

references

SHOR P W . Polynomial-time algorithms for prime factorization and discrete logarithmson a quantum computer [J ] . Society for Industrial and Applied Mathematics Review (SIREV) , 1999 , 41 ( 2 ): 303 - 332 .

NIST , DHS . Preparing for Post-Quantum Cryptography [EB/OL ] . [ 2021-05-08 ] . https://www.dhs.gov/sites/default/files/publications/post-quantum_cryptography_infograph- ic_october_2021_508.pdf https://www.dhs.gov/sites/default/files/publications/post-quantum_cryptography_infograph-ic_october_2021_508.pdf .

MOODY D , ALAGIC G , APON DC , et al . Status report on the third round ofthe NIST post-quantum cryptography standardization process [R/OL ] . [ 2022-07-05 ] . https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf .

王小云 , 刘明洁 . 格密码学研究 [J ] . 密码学报 , 2014 , 1 ( 1 ): 13 - 27 .

WANG X Y , LIU M J . Survey of lattice-based cryptography [J ] . Journal of Cryptologic Research , 2014 , 1 ( 1 ): 13 - 27 . (in Chinese)

杨昊 , 刘哲 , 黄军浩 , 等 . AKCN-MLWE算法AVX2高效实现 [J ] . 计算机学报 , 2021 , 44 ( 12 ): 2560 - 2572 .

YANG H , LIU Z , HUANG J H , et al . High-speed AVX2 implementation of AKCN-MLWE [J ] . Chinese Journal of Computers , 2021 , 44 ( 12 ): 2560 - 2572 . (in Chinese)

李子臣 , 谢婷 , 张卷美 . 基于RLWE问题的后量子口令认证密钥交换协议 [J ] . 电子学报 , 2021 , 49 ( 2 ): 260 - 267 .

LI ZC , XIE T , ZHANG J M . Post quantum password-based authentication key exchange protocol based on ring learning with errors problem [J ] . Acta Electronica Sinica , 2021 , 49 ( 2 ): 260 - 267 . (in Chinese)

ALKIM E , AVANZI R , BOS J , et al . Newhope algorithm specification and supporting documentation [EB/OL ] . [ 2020-04-10 ] . https://newhopecrypto.org/data/NewHope_2020_04_10.pdf https://newhopecrypto.org/data/NewHope_2020_04_10.pdf .

ALKIM E , BOS J , DUCAS L , et al . Frodokem learning with errors key encapsulation: Algorithm specification and supporting documentation [EB/OL ] . [ 2019-07-02 ] . https://frodokem.org/files/FrodoKEM-specification-20190702.pdf https://frodokem.org/files/FrodoKEM-specification-20190702.pdf .

AVANZI R , BOS J , DUCAS L , et al . Crystals-kyber: Algorithm specification and supporting documentation (version 2.0) [EB/OL ] . [ 2019-04-01 ] . https://pq-crystals.org/kyber/data/kyber-specification-round2.pdf https://pq-crystals.org/kyber/data/kyber-specification-round2.pdf .

D'ANVERS J P , KARMAKAR A , et al . Saber: Mod-lwr based KEM algorithm specification and supporting documentation [EB/OL ] . [ 2021-10-12 ] . https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf .

CHEN C , DANBA O , HOFFSTEIN J , et al . NTRUa-logarithm specifications and supporting documentation [EB/OL ] . [ 2019-03-30 ] . https://ntru.org/f/ntru-20190330.pdf https://ntru.org/f/ntru-20190330.pdf .

BERNSTEIN D J , CHUENGSATIANSUP C , LANGE T , et al . NTRU prime: Round 2 [EB/OL ] . [ 2019-03-30 ] . https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf .

DING J , FLUHRER S , RV S . Complete attack on rlwe key exchange with reusedkeys, without signal leakage [C ] // Australasian Conference on Information Security and Privacy (ACISP) . Wollongong, Australia : Springer , 2018 : 467 - 486 .

BAUER A , GILBERT H , RENAULT G , et al . Assessment of the key-reuse resilience of newhope [C ] // Cryptographers' Track at the RSA Conference (CT-RSA) . San Francisco, USA : Springer , 2019 : 272 - 292 .

QIN Y , CHENG C , DING J . A complete and optimized key mismatch attack on nist candidate newhope [C ] // European Symposium on Research in Computer Security (ESORICS) . Luxembourg : Springer , 2019 : 504 - 520 .

OKADA S , WANG Y , TAKAGI T . Improving key mismatch attack on new hope with fewer queries [C ] // Australasian Conference on Information Security and Privacy (ACISP) . Cham, Switzerland : Springer , 2020 : 505 - 524 .

QIN Y , CHENG C , ZHANG X , et al . A systematic a-pproach and analysis of key mismatch attacks on CPA-secure lattice-based NIST candidate KEMs [C ] // International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) . Singapore : Springer , 2021 : 92 - 121 .

DING J , DEATON J , SCHMIDT K , et al . A simple and practical key reuse attack on NTRU cryptosystem [J ] . IACR Cryptology EPrint Archive , 2019 .

ZHANG X , CHENG C , DING R . Small leaks sink a great ship: An evaluation of key reuse resilience of PQC third round finalist NTRU-HRSS [C ] // International Conference on Information and Communications Security (ICICS) . Chongqing, China : Springer , 2021 : 283 - 300 .

RAVI P , EZERMAN MF , et al . Will you cross the threshold for me? Generic side-channel assisted chosen-ciphertext attacks on NTRU-based kems [C ] // IACR Transactions on Cryptographic Hardware and Embedded Systems (CHES) . Leuven, Belgium : Springer , 2022 : 722 - 761 .

HOFFSTEIN J , PIPHER J , SILVERMAN J H . NTRU: A ring-based public key cryptosystem [C ] // International Algorithmic Number Theory Symposium (ANTS) . Portland : Springer , 1998 : 267 - 288 .

SHANNON C E . A mathematical theory of communication [J ] . The Bell System Technical Journal , 1948 , 27 ( 3 ): 379 - 423 .

COVER T M . Elements of Information Theory [M ] . 1st Edition . New York : John Wiley & Sons , 1999 .

WEISS M A . Data Structures and Algorithm Analysis in C++ [M ] . 4th Edition . New York : Pearson , 2014 .

XAGAWA K , ITO A , UENO R , et al . Fault-injection attacks against NIST's post-quantum cryptography round 3 KEM candidates [C ] // International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) . Singapore : Springer , 2021 : 33 - 61 .

RAJENDRAN G , RAVI P , D'ANVERS JP , et al . Pushing the limits of generic side-channel attacks on LWE-based KEMs-parallel PC oracle attacks on Kyber KEM and beyond [J ] . IACR Cryptology EPrint Archive , 2022 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Design and Challenges of Lattice-Based DH Like Key Exchange Protocols

Related Author

WANG Ke

HAN Jiang

XIE Hui-qin

JIANG Hao-dong

CHEN Long

ZHANG Zhen-feng

WANG Ke

Related Institution

Department of Cryptography Science and Technology, Beijing Electronic Science and Technology Institute

State Key Laboratory of Public Big Data, Guizhou University

University of Chinese Academy of Sciences

Trusted Computing and Information Security Laboratory, Institute of Software, Chinese Academy of Sciences

Henan Key Laboratory of Network Cryptography Technology

⁰