对密钥不匹配攻击的进一步理论分析--以NTRU-HRSS为例
Further Theoretical Analysis of Key Mismatch Attacks -A Case Study of NTRU-HRSS
查看参考文献26篇
|
文摘
|
目前,由美国国家标准技术研究院发起的对抗量子密码算法标准化的进程已进入最后一轮,其中基于格上困难问题的方案备受青睐.已有研究表明,若公私钥对被重复使用,则可以对选择明文攻击安全的格密钥封装机制发起密钥不匹配攻击;甚至在侧信道信息的辅助下,相关攻击能对选择密文攻击安全的格KEM奏效.在现有的针对格KEM方案的密钥不匹配攻击中,大多数攻击方案假设敌手一次只能恢复一个私钥系数,然而一次性恢复多个私钥系数是更为合理的假设,并且也将进一步减少密钥不匹配攻击所需的平均问询次数.鉴于此,本文进一步分析了密钥不匹配攻击中恢复私钥系数所需的平均问询次数的理论值下界的问题.其基本思路是将该问题转化为寻找一棵最优二叉恢复树的问题,进而证明了平均问询次数的理论值下界十分接近香农熵.在此基础上,本文提出了一套计算模型,并将其应用于NTRU-HRSS KEM方案,得到了更为准确的理论值下界;进一步地,据此提出了一种成对恢复NIST第三轮入选方案NTRU-HRSS KEM私钥的密钥不匹配攻击方案.实验结果表明,与现有的攻击方案相比,在成功率基本持平的基础上,平均问询次数减少了35.3%,耗时减少了47.3%.此外,本文提出的攻击方案也能够用于优化现有的针对CCA安全的NTRU-HRSS KEM方案的侧信道攻击,并将所需的问询次数由2 447减少到1 193. |
|
其他语种文摘
|
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. |
|
来源
|
电子学报
,2023,51(4):1081-1092 【核心库】
|
|
DOI
|
10.12263/DZXB.20220447
|
|
关键词
|
抗量子密码算法
;
格密码学
;
NTRU-HRSS KEM
;
密钥重用
;
密钥不匹配攻击
|
|
地址
|
1.
中国地质大学(武汉)计算机学院, 智能地学信息处理湖北省重点实验室, 湖北, 武汉, 430074
2.
桂林电子科技大学, 广西可信软件重点实验室, 广西, 桂林, 541004
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
0372-2112 |
|
学科
|
电子技术、通信技术 |
|
基金
|
国家自然科学基金
;
广西可信软件重点实验室研究课题
;
智能地学信息处理湖北省重点实验室开放基金
|
|
文献收藏号
|
CSCD:7492666
|
参考文献 共
26
共2页
|
|
1.
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithmson a quantum computer.
Society for Industrial and Applied Mathematics Review (SIREV),1999,41(2):303-332
|
CSCD被引
162
次
|
|
|
|
|
2.
NIST.
Preparing for Post-Quantum Cryptography,2021
|
CSCD被引
1
次
|
|
|
|
|
3.
Moody D.
Status report on the third round ofthe NIST post-quantum cryptography standardization process,2022
|
CSCD被引
1
次
|
|
|
|
|
4.
王小云. 格密码学研究.
密码学报,2014,1(1):13-27
|
CSCD被引
33
次
|
|
|
|
|
5.
杨昊. AKCN-MLWE算法AVX2高效实现.
计算机学报,2021,44(12):2560-2572
|
CSCD被引
3
次
|
|
|
|
|
6.
李子臣. 基于RLWE问题的后量子口令认证密钥交换协议.
电子学报,2021,49(2):260-267
|
CSCD被引
9
次
|
|
|
|
|
7.
Alkim E.
Newhope algorithm specification and supporting documentation,2020
|
CSCD被引
1
次
|
|
|
|
|
8.
Alkim E.
Frodokem learning with errors key encapsulation: Algorithm specification and supporting documentation,2019
|
CSCD被引
1
次
|
|
|
|
|
9.
Avanzi R.
Crystals-kyber: Algorithm specification and supporting documentation (version 2.0),2019
|
CSCD被引
1
次
|
|
|
|
|
10.
D'Anvers J P.
Saber: Mod-lwr based KEM algorithm specification and supporting documentation,2021
|
CSCD被引
1
次
|
|
|
|
|
11.
Chen C.
NTRUa-logarithm specifications and supporting documentation,2019
|
CSCD被引
1
次
|
|
|
|
|
12.
Bernstein D J.
NTRU prime: Round 2,2019
|
CSCD被引
1
次
|
|
|
|
|
13.
Ding J. Complete attack on rlwe key exchange with reusedkeys, without signal leakage.
Australasian Conference on Information Security and Privacy (ACISP),2018:467-486
|
CSCD被引
1
次
|
|
|
|
|
14.
Bauer A. Assessment of the key-reuse resilience of newhope.
Cryptographers' Track at the RSA Conference (CT-RSA),2019:272-292
|
CSCD被引
1
次
|
|
|
|
|
15.
Qin Y. A complete and optimized key mismatch attack on nist candidate newhope.
European Symposium on Research in Computer Security (ES-ORICS),2019:504-520
|
CSCD被引
1
次
|
|
|
|
|
16.
Okada S. Improving key mismatch attack on new hope with fewer queries.
Australasian Conference on Information Security and Privacy (ACISP),2020:505-524
|
CSCD被引
1
次
|
|
|
|
|
17.
Qin Y. A systematic approach and analysis of key mismatch attacks on CPA-secure lattice-based NIST candidate KEMs.
International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT),2021:92-121
|
CSCD被引
1
次
|
|
|
|
|
18.
Ding J. A simple and practical key reuse attack on NTRU cryptosystem.
IACR Cryptology EPrint Archive,2019
|
CSCD被引
1
次
|
|
|
|
|
19.
Zhang X. Small leaks sink a great ship: An evaluation of key reuse resilience of PQC third round finalist NTRU-HRSS.
International Conference on Information and Communications Security (ICICS),2021:283-300
|
CSCD被引
1
次
|
|
|
|
|
20.
Ravi P. Will you cross the threshold for me? Generic side-channel assisted chosen-ciphertext attacks on NTRU-based kems.
IACR Transactions on Cryptographic Hardware and Embedded Systems (CHES),2022:722-761
|
CSCD被引
1
次
|
|
|
|
|
了解气象卫星更多信息，请访问