对密钥不匹配攻击的进一步理论分析--以NTRU-HRSS为例

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

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

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 en-tropy.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 2447 to 1193.