A Compact Implementation of Salsa20 and Its Power Analysis Vulnerabilities

Abstract

In this article, we present a compact implementation of the Salsa20 stream cipher that is targeted towards lightweight cryptographic devices such as radio-frequency identification (RFID) tags. The Salsa20 stream cipher, ann addition-rotation-XOR (ARX) cipher, is used for high-security cryptography in NEON instruction sets embedded in ARM Cortex A8 CPU core-based tablets and smartphones. The existing literature shows that although classical cryptanalysis has been effective on reduced rounds of Salsa20, the stream cipher is immune to software side-channel attacks such as branch timing and cache timing attacks. To the best of our knowledge, this work is the first to perform hardware power analysis attacks, where we evaluate the resistance of all eight keywords in the proposed compact implementation of Salsa20. Our technique targets the three subrounds of the first round of the implemented Salsa20. The correlation power analysis (CPA) attack has an attack complexity of 2¹⁹. Based on extensive experiments on a compact implementation of Salsa20, we demonstrate that all these keywords can be recovered within 20,000 queries on Salsa20. The attacks show a varying resilience of the key words against CPA that has not yet been observed in any stream or block cipher in the present literature. This makes the architecture of this stream cipher interesting from the side-channel analysis perspective. Also, we propose a lightweight countermeasure that mitigates the leakage in the power traces as shown in the results of Welch’s t-test statistics. The hardware area overhead of the proposed countermeasure is only 14% and is designed with compact implementation in mind.

References

1. Security in Silicon by Helion. http://www.heliontech.com/. Accessed: 2015-012-17.
2. Alex Arbit, Yoel Livne, Yossef Oren, and Avishai Wool. 2015. Implementing public-key cryptography on passive RFID tags is practical. Int. J. Inform. Sec. 14, 1 (2015), 85--99.
3. Frederik Armknecht, Matthias Hamann, and Vasily Mikhalev. 2014. Lightweight authentication protocols on ultra-constrained RFIDs - Myths and facts. In RFIDSec. 1--18.
4. Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger. 2008. New features of Latin dances: Analysis of Salsa, ChaCha, and Rumba. In Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10--13, 2008, Revised Selected Papers. 470--488.
5. Daniel J. Bernstein. 2008. The Salsa20 family of stream ciphers. In New Stream Cipher Designs—The eSTREAM Finalists. 84--97.
6. Daniel J. Bernstein and Peter Schwabe. 2012. NEON crypto. In Cryptographic Hardware and Embedded Systems—CHES 2012, 14th International Workshop, Leuven, Belgium, September 9--12, 2012. Proceedings. 320--339.
7. Guido Bertoni, Luca Breveglieri, Israel Koren, Paolo Maistri, and Vincenzo Piuri. 2003. Error analysis and detection procedures for a hardware implementation of the advanced encryption standard. IEEE Trans. Comput. 52, 4 (2003), 492--505.
8. Shivam Bhasin, Jean-Luc Danger, Sylvain Guilley, and Wei He. 2015. Exploiting FPGA block memories for protected cryptographic implementations. ACM Trans. Reconfig. Technol. Syst. 8, 3 (2015), 16.
9. Eric Brier, Christophe Clavier, and Francis Olivier. 2004. Correlation power analysis with a leakage model. In Cryptographic Hardware and Embedded Systems—CHES 2004: 6th International Workshop Cambridge, MA, USA, August 11--13, 2004. Proceedings. 16--29.
10. Paul Crowley. 2006. Truncated differential cryptanalysis of five rounds of Salsa20. SASC 2006--Stream Ciphers Revisited (2006).
11. Joan Daemen and Vincent Rijmen. 2002. Security of a wide trail design. In Progress in Cryptology - INDOCRYPT 2002, Third International Conference on Cryptology in India, Hyderabad, India, December 16--18, 2002. 1--11.
12. Thomas Eisenbarth, Zheng Gong, Tim Güneysu, Stefan Heyse, Sebastiaan Indesteege, Stéphanie Kerckhof, François Koeune, Tomislav Nad, Thomas Plos, Francesco Regazzoni, François-Xavier Standaert, and Loïc van Oldeneel tot Oldenzeel. 2012. Compact implementation and performance evaluation of block ciphers in ATtiny devices. In Progress in Cryptology—AFRICACRYPT 2012, 5th International Conference on Cryptology in Africa, Ifrance, Morocco, July 10--12, 2012. Proceedings. 172--187.
13. Thomas Eisenbarth, Sandeep Kumar, Christof Paar, Axel Poschmann, and Leif Uhsadel. 2007. A survey of lightweight-cryptography implementations. IEEE Des. Test Comput. 6 (2007), 522--533.
14. Daniel W. Engels, Markku-Juhani O. Saarinen, Peter Schweitzer, and Eric M. Smith. 2011. The Hummingbird-2 lightweight authenticated encryption algorithm. In RFID. Security and Privacy, 7th International Workshop, RFIDSec 2011, Amherst, USA, June 26--28, 2011, Revised Selected Papers. 19--31.
15. Martin Feldhofer. 2007. Comparison of low-power implementations of Trivium and Grain. In Workshop on The State of the Art of Stream Ciphers (SASC2007). 236--246.
16. Martin Feldhofer, Sandra Dominikus, and Johannes Wolkerstorfer. 2004. Strong authentication for RFID systems using the AES algorithm. In Cryptographic Hardware and Embedded Systems—CHES 2004. Springer, 357--370.
17. Martin Feldhofer, Johannes Wolkerstorfer, and Vincent Rijmen. 2005. AES implementation on a grain of sand. IEEE Proc. Inform. Sec. 152, 1 (2005), 13--20.
18. Simon Fischer, Willi Meier, Côme Berbain, Jean-François Biasse, and Matthew J. B. Robshaw. 2006. Non-randomness in eSTREAM candidates Salsa20 and TSC-4. In Progress in Cryptology - INDOCRYPT 2006, 7th International Conference on Cryptology in India, Kolkata, India, December 11--13, 2006, Proceedings. 2--16.
19. Benjamin Jun Gilbert Goodwill, Josh Jaffe, Pankaj Rohatgi, and others. 2011. A testing methodology for side-channel resistance validation. In NIST Non-Invasive Attack Testing Workshop.
20. Solomon W. Golomb. 1980. On the classification of balanced binary sequences of period 2^n-1(Corresp.). IEEE Trans. Inform Theory 26, 6 (1980), 730--732.
21. Tim Good and Mohammed Benaissa. 2005. AES on FPGA from the fastest to the smallest. In Cryptographic Hardware and Embedded Systems—CHES 2005, 7th International Workshop, Edinburgh, UK, August 29--September 1, 2005, Proceedings. 427--440.
22. G. Goodwill, B. Jun, J. Jaffe, and P. Rohatgi. 2011. A testing methodology for side channel resistance validation. In NIST Non-Invasive Attack Testing Workshop. http://csrc.nist.gov/newsevents/non-invasive-attack-testing-workshop/papers/08_Goodwill.pdf.
23. Xiaofei Guo, Debdeep Mukhopadhyay, Chenglu Jin, and Ramesh Karri. 2015. Security analysis of concurrent error detection against differential fault analysis. J. Cryptogr. Eng. 5, 3 (2015), 153--169.
24. L. Henzen, F. Carbognani, N. Felber, and W. Fichtner. 2008. VLSI hardware evaluation of the stream ciphers Salsa20 and ChaCha, and the compression function rumba. In 2nd IEEE International Conference on Signals, Circuits and Systems, 2008. IEEE, 1--5. DOI:http://dx.doi.org/10.1109/ICSCS.2008.4746906
25. Ari Juels. 2006. RFID security and privacy: A research survey. IEEE J. Select. Areas Commun. 24, 2 (2006), 381--394.
26. Ramesh Karri, Kaijie Wu, Piyush Mishra, and Yongkook Kim. 2001. Fault-based side-channel cryptanalysis tolerant Rijndael symmetric block cipher architecture. In Defect and Fault Tolerance in VLSI Systems, 2001. Proceedings. 2001 IEEE International Symposium on. IEEE, 427--435.
27. Thomas Kern and Martin Feldhofer. 2010. Low-resource ECDSA implementation for passive RFID tags. In 17th IEEE International Conference on Electronics, Circuits, and Systems, ICECS 2010, Athens, Greece, 12--15 December, 2010. 1236--1239.
28. Dmitry Khovratovich and Ivica Nikolic. 2010. Rotational cryptanalysis of ARX. In Fast Software Encryption, 17th International Workshop, FSE 2010, Seoul, Korea, February 7--10, 2010, Revised Selected Papers. 333--346.
29. Paris Kitsos and Yan Zhang. 2008. RFID Security: Techniques, Protocols and System-On-Chip Design. Springer.
30. Paul Kocher, Joshua Jaffe, Benjamin Jun, and Pankaj Rohatgi. 2011. Introduction to differential power analysis. J. Cryptogr. Eng. 1, 1 (2011), 5--27.
31. Ian Kuon and Jonathan Rose. 2009. Quantifying and Exploring the Gap Between FPGAs and ASICs (1st ed.). Springer Publishing Company, Incorporated.
32. Y. K. Lee, K. Sakiyama, L. Batina, and I. Verbauwhede. 2008. Elliptic-curve-based security processor for RFID. IEEE Trans. Comput. 57, 11 (2008), 1514--1527.
33. Stefan Mangard, Elisabeth Oswald, and Thomas Popp. 2007. Power Analysis Attacks: Revealing the Secrets of Smart Cards (Advances in Information Security). Springer-Verlag New York, NY.
34. Luke Mather, Elisabeth Oswald, Joe Bandenburg, and Marcin Wójcik. 2013. Does my device leak information? An a priori statistical power analysis of leakage detection tests. In Advances in Cryptology—ASIACRYPT 2013, 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1--5, 2013, Proceedings, Part I. 486--505. DOI:http://dx.doi.org/10.1007/978-3-642-42033-7_25
35. Marcel Medwed, François-Xavier Standaert, Johann Großschädl, and Francesco Regazzoni. 2010. Fresh re-keying: Security against side-channel and fault attacks for low-cost devices. In Progress in Cryptology--AFRICACRYPT 2010. Springer, 279--296.
36. Mehran Mozaffari-Kermani and Reza Azarderakhsh. 2015. Reliable hash trees for post-quantum stateless cryptographic hash-based signatures. In Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFTS), 2015 IEEE International Symposium on. IEEE, 103--108.
37. Axel Poschmann, Gregor Leander, Kai Schramm, and Christof Paar. 2007. New light-weight crypto algorithms for RFID. In Circuits and Systems, 2007. ISCAS 2007. IEEE International Symposium on. IEEE, 1843--1846.
38. Matthew J. B. Robshaw and Olivier Billet (Eds.). 2008. New Stream Cipher Designs - The eSTREAM Finalists. Lecture Notes in Computer Science, Vol. 4986. Springer.
39. Carsten Rolfes, Axel Poschmann, Gregor Leander, and Christof Paar. 2008. Ultra-lightweight implementations for smart devices - Security for 1000 gate equivalents. In Smart Card Research and Advanced Applications, 8th IFIP WG 8.8/11.2 International Conference, CARDIS 2008, London, UK, September 8-11, 2008. Proceedings. 89--103.
40. Markku-Juhani O. Saarinen. 2012. The BlueJay ultra-lightweight hybrid cryptosystem. In 2012 IEEE Symposium on Security and Privacy Workshops, San Francisco, CA, USA, May 24--25, 2012. 27--32.
41. Tobias Schneider and Amir Moradi. 2015. Leakage assessment methodology—A clear roadmap for side-channel evaluations. In Cryptographic Hardware and Embedded Systems, CHES 2015, 17th International Workshop, Saint-Malo, France, September 13--16, 2015, Proceedings. 495--513.
42. Tobias Schneider, Amir Moradi, and Tim Güneysu. 2015. Arithmetic addition over boolean masking - Towards first- and second-order resistance in hardware. IACR Cryptology ePrint Archive 2015 (2015), 66.
43. Khawar Shahzad, Ayesha Khalid, Zoltán Endre Rákossy, Goutam Paul, and Anupam Chattopadhyay. 2013. CoARX: A coprocessor for ARX-based cryptographic algorithms. In The 50th Annual Design Automation Conference 2013, DAC ’13, Austin, TX, USA, May 29--June 07, 2013. 133:1--133:10.
44. François-Xavier Standaert, Tal G. Malkin, and Moti Yung. 2009. A unified framework for the analysis of side-channel key recovery attacks. In Advances in Cryptology-EUROCRYPT 2009. Springer, 443--461.
45. Jarosław Sugier. 2013. Implementing Salsa20 vs. AES and serpent ciphers in popular-grade FPGA devices. In New Results in Dependability and Computer Systems. Springer, 431--438.
46. Stefan Tillich, Martin Feldhofer, and Johann Großschädl. 2006. Area, delay, and power characteristics of standard-cell implementations of the AES S-box. In Embedded Computer Systems: Architectures, Modeling, and Simulation. Springer, 457--466.
47. Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki, and Hiroki Nakashima. 2007. Differential cryptanalysis of Salsa20/8. In Workshop Record of SASC.
48. Rajesh Velegalati and Jens-Peter Kaps. 2009. DPA resistance for light-weight implementations of cryptographic algorithms on FPGAs. In 19th International Conference on Field Programmable Logic and Applications, FPL 2009, August 31--September 2, 2009, Prague, Czech Republic. 385--390.
49. Wentao Zhang, Zhenzhen Bao, Dongdai Lin, Vincent Rijmen, Bohan Yang, and Ingrid Verbauwhede. 2015. RECTANGLE: A bit-slice lightweight block cipher suitable for multiple platforms. SCIENCE CHINA Information Sciences 58, 12 (2015), 1--15.
50. Y. Zhang and P. Kitsos. 2009. Security in RFID and Sensor Networks. CRC Press.

Index Terms

• Security and privacy

  • Security in hardware

    • Hardware attacks and countermeasures

      • Side-channel analysis and countermeasures