Master Thesis Defense - December 6, 2017: Secure Hardware Implementation of Post Quantum Cryptosystems

Mouna Nakkar

Wednesday, December 6, 2017 at 10:30 a.m.
Room EV003.309

You are invited to attend the following M.A.Sc. (Information Systems Security) thesis examination.

Examining Committee

Dr. A. Ben Hamza, Chair
Dr. A. Youssef, Supervisor
Dr. J. Bentahar, CIISE Examiner
Dr. K. Galal, External Examiner (BCEE)

Abstract

Solving a hard mathematical problem is the security basis of all current cryptographic systems. With the realization of a large scale quantum computer, hard mathematical problems such as integer factorization and discrete logarithmic problems will be easily solved with special algorithms implemented on such a computer. Indeed, only post-quantum cryptosystems which defy quantum attacks will survive in the post-quantum era. Each newly proposed post-quantum cryptosystem has to be scrutinized against all different types of attacks. Attacks can be classified into mathematical cryptanalysis and side channel attacks. In this thesis, we propose secure hardware implementations against side channel attacks for two of the most promising post-quantum algorithms: the lattice-based public key cryptosystem, NTRU, and the multivariate public key cryptosystem, Rainbow, against power analysis attacks and fault analysis attacks, respectively.

NTRUEncrypt is a family of public key cryptosystems that uses lattice-based cryptography. It has been accepted as an IEEE P1363 standard and as an X9.98 Standard. In addition to its small footprint compared to other number theory based public key systems, its resistance to quantum attacks makes it a very attractive candidate for post quantum cryptosystems. On the other hand, similar to other cryptographic schemes, unprotected hardware implementations of NTRUEncrypt are susceptible to side channel attacks such as timing and power analysis. In this thesis, we present an FPGA implementation of NTRUEncrypt which is resistant to first order differential power analysis (DPA) attacks. Our countermeasures are implemented at the architecture level. In particular, we split the ciphertext into two randomly generated shares. This guarantees that during the first step of the decryption process, the inputs to the convolution modules, which are convoluted with the secret key polynomial, are uniformly chosen random polynomials which are freshly generated for each convolution operation and are not under the control of the attacker. The two shares are then processed in parallel without explicitly combining them until the final stage of the decryption. Furthermore, during the final stage of the decryption, we also split the used secret key polynomial into two randomly generated shares which provides theoretical resistance against the considered class of power analysis attacks. The proposed architecture is implemented using Altera Cyclone IV FPGA and simulated on Quartus II in order to compare the non-masked architecture with the masked one. For the considered set of parameters, the area overhead of the protected implementation is about 60% while the latency overhead is between 1.4% to 6.9%.

Multivariate Public Key Cryptosystems (MPKCs) are cryptographic schemes based on the difficulty of solving a set of multivariate system of nonlinear equations over a finite field. MPKCs are considered to be secure against quantum attacks. Rainbow, an MPKC signature scheme, is among the leading MPKC candidates for post quantum cryptography. In this thesis, we propose and compare two fault analysis-resistant implementations for the Rainbow signature scheme. The hardware platform for our implementations is Xilinx FPGA Virtex 7 family. Our implementation for the Rainbow signature completes in 191 cycles using a 20ns clock period which is an improvement over the previously reported implementations. The verification completes in 141 cycles using the same clock period. The two proposed fault analysis-resistant schemes offer different levels of protections and increase the area overhead by a factor of 33% and 9%, respectively. The first protection scheme acquires a time overhead of about 72%, but the second one does not have any time overhead.