Implementation Attacks and Their Countermeasures For Learning With Errors Based Key Encapsulation Mechanishms

Abstract

Encryption systems are built to protect shared secrets. Recently, several research projects conducted on the usability of quantum computers on the cryptanalysis of those systems. The general understanding is that the current public-key encryption systems can be broken when quantum computers with sufficient processing capacity produced. Because this endangers the security of the communication on the internet, NIST has started a standardization project to produce cryptosystems resistant to attacks from both classical and quantum computers. Many systems have been proposed in this project. Lattice-based systems, which are based on the difficulty of solving problems such as LWE defined on the lattices, have developed great attention as the most promising systems. However, information about the secret key can be obtained by collecting the side-channel information obtained during cryptographic systems are working. For this reason, NIST commented that proposals to its call for encryption systems that are resistant to quantum computers should require a small cost to make them resistant to side-channel attacks if they are not resistant by design. In 2016, Bindel et al. have proposed fault attacks targeting lattice-based schemes, which are classified as implementation attacks, and a type of side-channel attacks. In 2018, Han et al. showed that they were able to obtain the secret key in the Lizard protocol using the methods proposed in 2016 and proposed some countermeasures to prevent such attacks. In this study; the implementation of the Lizard protocol changed and the effects of these changes on the implementation are discussed with regards to the features suggested in the previous studies and the features that the cryptosystems should have. Not only the implementation security of the protocol has been increased and some countermeasures proposed to prevent fault attacks but also it was observed that the protocol’s performance accelerated.

Keywords

• Post-quantum Cryptography,Lattice-based Cryptography,Learning With Errors,Side-channel Attacks,Fault Attcaks

Hatalar ile Öğrenme Tabanlı Anahtar Kapsülleme Protokolleri İçin Uygulama Atakları ve Savunma Yöntemleri

Abstract

Şifreleme sistemleri gizli değerlerin korunmasını sağlamakta olan sistemlerdir. Bu sistemlere karşı son yıllarda kuantum bilgisayarlar üzerinde çok sayıda araştırmalar yapılmaktadır. Yeterli işlem kapasitesine sahip kuantum bilgisayarlar üretildiğinde günümüzde kullanılmakta olan açık anahtarlı şifreleme sistemlerinin güvensiz duruma geleceği düşünülmektedir. Bu durum internet üzerindeki haberleşmenin güvenliğini tehlikeye atmaktadır. Bu durumdan dolayı, kuantum bilgisayarlara karşı güvenli sistemlerin oluşturulması için kuantum bilgisayarların günlük hayata girmesinin beklenmemesi gerektiği düşünülmektedir. NIST bu doğrultuda hem günümüz hem de kuantum bilgisayarlardan gelecek ataklara karşı dayanıklı kriptosistemlerin üretilmesi için bir standartlaştırma proje başlatmıştır. Bu süreçte birçok sistem önerilmiştir. Kafes tabanlı sistemler en çok gelecek vadeden sistemler olarak ön plana çıkmıştır. Kafes tabanlı kriptosistemler kafes yapısı üzerinde tanımlı olan LWE gibi problemlerin çözümlerinin zorluğuna dayanarak önerilmiş olan sistemlerdir. Fakat yan kanal saldırıları ile kriptografik sistemler çalışırken çıkan bilgiler toplanarak gizli anahtar hakkında bilgi edinilebilmektedir. Bu durumdan dolayı NIST kuantum bilgisayarlara karşı dayanıklı şifreleme sistemleri için yaptığı çağrının yanı sıra, yapılacak sistemlerin minimum maliyetle yan kanal saldırılarına karşı dayanıklı olmasını gerektiğini söylemiştir. 2016 yılında Bindel ve arkadaşlarının yaptıkları bir çalışmada uygulama atağı olarak sınıflandırılan ve bir yan kanal saldırı çeşidi olan hata ataklarını önermişlerdir. 2018 yılında Han ve arkadaşları yaptıkları bir çalışmada, 2016 yılında önerilen yöntemleri kullanarak Lizard protokolünde gizli anahtarı elde edebildiklerini söylemişlerdir ve bu ataklara karşı alınabilecek önlemlerden bahsetmişlerdir. Bu çalışmada; önceden yapılan çalışmalarda önerilenler ve kriptosistemlerin uygulamalarında olması gereken özellikler doğrultusunda Lizard protokolünün uygulaması üzerinde yapılan değişikliklerden ve bu değişikliklerin uygulama üzerindeki etkilerinden bahsedilmiştir. Protokolün uygulamasının güvenliği artırılmış ve gerçekleştirilen bazı hata ataklarına karşı önlem alınmıştır. Yapılan değişikliklerden sonra protokolün çalışma süresinde hızlanma olduğu gözlemlenmiştir.

Keywords

• Kuantum Sonrası Kriptografi,Kafes Tabanlı Kriptografi,Hatalar ile Öğrenme,Yan Kanal Saldırıları,Hata Atakları

References

1. Alwen, J., Krenn, S., Pietrzak, K., & Wichs, D. (2013, August). Learning with rounding, revisited. In Annual Cryptology Conference (pp. 57-74). Springer, Berlin, Heidelberg.
2. Banerjee, A., Peikert, C., & Rosen, A. (2012, April). Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 719-737). Springer, Berlin, Heidelberg.
3. Bernstein, D. J. (2009). Introduction to post-quantum cryptography. In Post-quantum cryptography (pp. 1-14). Springer, Berlin, Heidelberg.
4. Bindel, N., Buchmann, J., & Krämer, J. (2016, August). Lattice-based signature schemes and their sensitivity to fault attacks. In 2016 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC) (pp. 63-77). IEEE.
5. Chen, L., Jordan, S., Liu, Y. K., Moody, D., Peralta, R., Perlner, R., & Smith-Tone, D. (2016). Report on post-quantum cryptography," National Institute of Standards and Technology. US Department of Commerce.
6. Cheon, J. H., Kim, D., Lee, J., & Song, Y. (2018, September). Lizard: Cut off the tail! A practical post-quantum public-key encryption from LWE and LWR. In International Conference on Security and Cryptography for Networks (pp. 160-177). Springer, Cham.
7. Computer Security Division, I. T. L. (2017, February 3). Round 1 Submissions—Post-Quantum Cryptography | CSRC. CSRC | NIST. https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions
8. Ducas, L., Durmus, A., Lepoint, T., & Lyubashevsky, V. (2013, August). Lattice signatures and bimodal Gaussians. In Annual Cryptology Conference (pp. 40-56). Springer, Berlin, Heidelberg.

9. Eastlake, D., Schiller, J., & Crocker, S. (2005). Randomness requirements for security. RFC4086.
10. Farhady Ghalaty, N. (2016). Fault Attacks on Cryptosystems: Novel Threat Models, Countermeasures and Evaluation Metrics (Doctoral dissertation, Virginia Tech).
11. Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008, May). Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing (pp. 197-206).
12. Han, S., Choi, N., An, H., Choi, R., & Kim, K. (2018, January). Prey on Lizard: Mining Secret Key on Lattice-based Cryptosystem. In 2018 Symposium on Cryptography and Information Security (SCIS 2018). IEICE Technical Committee on Information Security.
13. Hoffstein, J., Howgrave-Graham, N., Pipher, J., & Whyte, W. (2009). Practical lattice-based cryptography: NTRUEncrypt and NTRUSign. In The LLL Algorithm (pp. 349-390). Springer, Berlin, Heidelberg.
14. Howe, J., Khalid, A., Rafferty, C., Regazzoni, F., & O’Neill, M. (2016). On practical discrete Gaussian samplers for lattice-based cryptography. IEEE Transactions on Computers, 67(3), 322-334.
15. Hughes, R., & Nordholt, J. (2016). Strengthening the security foundation of cryptography with Whitewood’s quantum-powered entropy engine.
16. Kamal, A. A., & Youssef, A. (2011). Fault analysis of the NTRUEncrypt cryptosystem. IEICE transactions on fundamentals of electronics, communications and computer sciences, 94(4), 1156-1158.
17. Kamal, A. A., & Youssef, A. M. (2012, August). A scan-based side channel attack on the NTRUEncrypt cryptosystem. In 2012 Seventh International Conference on Availability, Reliability and Security (pp. 402-409). IEEE.
18. Le Trieu Phong, T. H., Aono, Y., & Moriai, S. LOTUS: Algorithm Specifications and Supporting Documentation.
19. Lindner, R., & Peikert, C. (2011, February). Better key sizes (and attacks) for LWE-based encryption. In Cryptographers’ Track at the RSA Conference (pp. 319-339). Springer, Berlin, Heidelberg.
20. Naehrig, M., Alkim, E., Bos, J. W., Ducas, L., Easterbrook, K., LaMacchia, B., ... & Raghunathan, A. (2017). FrodoKEM: practical quantum-secure key encapsulation from generic lattices. NIST submissions.
21. Peikert, C. (2016). A decade of lattice cryptography. Foundations and Trends® in Theoretical Computer Science, 10(4), 283-424.
22. Regev, O. (2005). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, 84–93. https://doi.org/10.1145/1060590.1060603
23. Sampling: Rejection Sampling Explained. Erişim tarihi: 11 Şubat 2020, gönderen https://relguzman.blogspot.com/2018/04/rejection-sampling-explained.html
24. Seo, M., Park, J. H., Lee, D. H., Kim, S., & Lee, S. J. (2017). Emblem and r. EMBLEM. Technical Report. National Institute of Standards and Technology.
25. Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). Ieee.
26. Taha, M., & Eisenbarth, T. (2015). Implementation Attacks on Post-Quantum Cryptographic Schemes. IACR Cryptology ePrint Archive, 2015, 1083.