针对AKCN-MLWE算法的故障攻击

Fault Attack on AKCN-MLWE

随着量子计算技术的飞速发展以及Shor算法的提出,未来成型的量子计算机将轻易求解大整数分解问题以及离散对数求解问题.由于传统公钥算法如RSA、椭圆曲线问题等其安全性均基于这些数学问题,因此该类算法面临的安全威胁也日益突出.后量子密码算法是为对抗量子计算破解而设计的一类加密算法,在近年来成为密码学研究热点.其中,基于格的后量子密码算法最为学术界广泛研究与评估.目前,密码学已经达成共识,密码算法不仅仅需要考虑算法理论安全性,同时需要考虑实现安全性,包括旁路攻击和故障攻击安全性.本文针对中国密码学会征集的第二轮后量子密码算法AKCN-MLWE提出了一种嵌入式环境下的故障攻击方法.AKCN-MLWE算法是一种基于格的公钥密码算法.本文提出的故障攻击向该算法中使用的数论转换模块(NTT)中的旋转因子注入故障并影响其输出结果.在分别针对密钥生成环节和加密环节进行故障注入后,利用有效的错误输出结果可以分别进行私钥的还原以及密文的解密.同时该故障注入并不会影响生成的公私钥对在后续通信中的使用.但是在对加密环节进行故障注入后,攻击者需要使用中间人攻击方法来维持该次通信.本文也对如何在真实环境下进行故障注入进行了讨论与实用性评估.本文所提出的故障攻击方法,在算法执行过程中仅需一次故障注入即可恢复整体私钥.最后,本文同时提出一种针对性的防御方法,在不影响实现效率的情况下可有效防止该类故障攻击的生效.

With the development of quantum computing and the proposal of the Shor’s algorithm,quantum computers will easily solve the large integer factorization problem and the discrete logarithm problem in the future.Since the traditional public key algorithms such as RSA and elliptic curve cryptography are based on these mathematical problems,the threats to these algorithms are severe.To protect the information security,new cryptographic algorithms need to be designed and evaluated.Post-Quantum Cryptography(PQC)is a kind of algorithms designed to resist quantum computing cracking.The algorithms and implementations of PQC have been widely investigated in recent years.The U.S.National Institute of Standards and Technology(NIST)called a competitive submission in 2016.Then in 2022,the NIST proposed a finalist for the PQC schemes to be standardized.Among the PQC algorithms,the lattice-based post-quantum cryptography algorithm is the most widely studied and evaluated scheme,because of its speed of running,and size of a public key,etc.The PQC schemes not only need to be evaluated about the theoretical security under Quantum Computing,they also need to be considered for the implementation security,like the security under Side Channel Attack and Fault Attack.The implementation security indicates that the cryptographic algorithms running on the physical device need to be secure under different physical attacks.The Fault Attack means the attacker can inject a fault into the algorithms when programs are running on a physical chip.The attacker can use the faulted output to deduce the secret information that the algorithms are encrypting.This paper proposes a fault attack method under the embedded environment on AKCN-MLWE.We use the ARM Cortex-M4 as the experimental device.This scheme is a post-quantum cryptography algorithm proposed in the Round 2 competition called by the Chinese Association for Cryptologic Research(CACR).The AKCN-MLWE is also a lattice-based public key scheme.This proposed attack injects fault into the Number Theory Transform(NTT)module used in the algorithm.The NTT is commonly used for accelerating the polynomial multiplication in lattice-based algorithms.We mainly target the twiddle factors used in NTT.The twiddle factors are pre-computed and saved in the memory.With the fault injection in key generation,the informative error results can be used to recover the secret key.Meanwhile,the generated error key-pair(public key and secret key)can still be used to build a normal communication successfully.When the attacker injects the fault into encryption function,the secret message can be directly deduced from the error output.While the attacker needs to use the Man-In-The-Middle(MITM)Attack to maintain the communication,because of the Fujisaki-Okamoto Transformation used in decryption for security checks.This paper also discusses and evaluates the practicability of the fault injection in the real world.Two fault injection scenarios are evaluated and discussed with the different fault injection methods.Our attack could recover the whole secret key or message with only one fault injection during the algorithm running.At the same time,this paper proposes a specific countermeasure method to prevent this kind of fault attack without affecting the implementation efficiency.