SpringerLink
Log in

Cold Boot Attacks on Bliss

  • Conference paper
  • First Online:
Progress in Cryptology – LATINCRYPT 2019 (LATINCRYPT 2019)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11774))

Abstract

In this paper, we examine the feasibility of cold boot attacks against the BLISS signature scheme. We believe this to be the first time that this has been attempted. Our work is the continuation of the trend to develop cold boot attacks for different schemes as revealed by the literature. But it is also the continuation of the evaluation of post-quantum cryptographic schemes against this class of attack. Particularly, we review the BLISS implementation provided by the strongSwan project. This implementation particularly stores its private key in memory in an interesting way therefore requiring novel approaches to key recovery. We present various approaches to key recovery. We first analyse the key recovery problem in this particular case via key enumeration algorithms, and so propose different techniques for key recovery. We then turn our attention to exploit further the algebraic relation among the components of the private key, and we thus establish a connection between the key recovery problem in this particular case and an instance of Learning with Errors Problem (LWE). We then explore various key recovery techniques to tackle this instance of LWE. In particular, we show a key recovery strategy combining lattice techniques and key enumeration. Finally, we report results from experimenting with one of the key recovery algorithms for a range of parameters, showing it is able to tolerate a noise level of \( \alpha = 0.001\) and \(\beta = 0.09\) for a parameter set when performing a \(2^{40}\) enumeration.

This work was supported by COLCIENCIAS and is part of my doctoral studies conducted under the supervision of Professor Kenneth G. Paterson, at Royal Holloway, University of London.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 74.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    See https://www.strongswan.org/ for details of this project.

  2. 2.

    See for example https://en.wikipedia.org/wiki/Maximum_likelihood_estimation.

  3. 3.

    This follows because of its form.

References

  1. Albrecht, M., Cid, C.: Cold boot key recovery by solving polynomial systems with noise. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 57–72. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21554-4_4

    Chapter  Google Scholar 

  2. Albrecht, M.R., Deo, A., Paterson, K.G.: Cold boot attacks on ring and module lwe keys under the ntt. IACR Trans. Cryptogr. Hardw. Embed. Syst. (3), 173–213 (2018). https://doi.org/10.13154/tches.v2018.i3.173-213. https://tches.iacr.org/index.php/TCHES/article/view/7273

  3. Babai, L.: On lováz’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986). https://doi.org/10.1007/BF02579403

    Article  MathSciNet  MATH  Google Scholar 

  4. Bogdanov, A., Kizhvatov, I., Manzoor, K., Tischhauser, E., Witteman, M.: Fast and memory-efficient key recovery in side-channel attacks. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 310–327. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31301-6_19

    Chapter  MATH  Google Scholar 

  5. Buchmann, J., Göpfert, F., Player, R., Wunderer, T.: On the hardness of LWE with binary error: revisiting the hybrid lattice-reduction and meet-in-the-middle attack. In: Pointcheval, D., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 24–43. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31517-1_2

    Chapter  MATH  Google Scholar 

  6. David, L., Wool, A.: A bounded-space near-optimal key enumeration algorithm for multi-subkey side-channel attacks. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 311–327. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-52153-4_18

    Chapter  Google Scholar 

  7. Ducas, L.: Accelerating bliss: the geometry of ternary polynomials. Cryptology ePrint Archive, Report 2014/874 (2014). http://eprint.iacr.org/2014/874

  8. Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_3

    Chapter  Google Scholar 

  9. Espitau, T., Fouque, P.A., Gérard, B., Tibouchi, M.: Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security, 31 October–2 November 2017, pp. 1857–1874. ACM Press, Dallas (2017). https://doi.org/10.1145/3133956.3134028

  10. Halderman, J.A., et al.: Lest we remember: cold boot attacks on encryption keys. In: van Oorschot, P.C. (ed.) USENIX Security 2008: 17th USENIX Security Symposium, USENIX Association, San Jose, CA, USA, 28 July–1 August 2008, pp. 45–60 (2008)

    Google Scholar 

  11. Henecka, W., May, A., Meurer, A.: Correcting errors in rsa private keys. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 351–369. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_19

    Chapter  MATH  Google Scholar 

  12. Heninger, N., Shacham, H.: Reconstructing RSA private keys from random key bits. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 1–17. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_1

    Chapter  Google Scholar 

  13. Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_9

    Chapter  MATH  Google Scholar 

  14. Kamal, A.A., Youssef, A.M.: Applications of sat solvers to aes key recovery from decayed key schedule images. In: Proceedings of the 2010 Fourth International Conference on Emerging Security Information, Systems and Technologies, SECURWARE 2010, IEEE Computer Society, Washington, DC, USA, pp. 216–220 (2010). https://doi.org/10.1109/SECURWARE.2010.42. http://dx.doi.org/10.1109/SECURWARE.2010.42

  15. Lee, H.T., Kim, H.T., Baek, Y.-J., Cheon, J.H.: Correcting errors in private keys obtained from cold boot attacks. In: Kim, H. (ed.) ICISC 2011. LNCS, vol. 7259, pp. 74–87. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31912-9_6

    Chapter  Google Scholar 

  16. Martin, D.P., O’Connell, J.F., Oswald, E., Stam, M.: Counting keys in parallel after a side channel attack. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 313–337. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_13

    Chapter  MATH  Google Scholar 

  17. Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999). https://doi.org/10.1007/PL00003816

    Article  MathSciNet  MATH  Google Scholar 

  18. Paterson, K.G., Polychroniadou, A., Sibborn, D.L.: A coding-theoretic approach to recovering noisy RSA keys. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 386–403. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_24

    Chapter  Google Scholar 

  19. Paterson, K.G., Villanueva-Polanco, R.: Cold Boot attacks on NTRU. In: Patra, A., Smart, N.P. (eds.) INDOCRYPT 2017. LNCS, vol. 10698, pp. 107–125. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71667-1_6

    Chapter  Google Scholar 

  20. Pessl, P., Bruinderink, L.G., Yarom, Y.: To BLISS-B or not to be: attacking strongSwan’s implementation of post-quantum signatures. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security, 31 October–2 November 2017, pp. 1843–1855. ACM Press, Dallas (2017). https://doi.org/10.1145/3133956.3134023

  21. Poettering, B., Sibborn, D.L.: Cold boot attacks in the discrete logarithm setting. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 449–465. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16715-2_24

    Chapter  MATH  Google Scholar 

  22. Poussier, R., Standaert, F.-X., Grosso, V.: Simple key enumeration (and rank estimation) using histograms: an integrated approach. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 61–81. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53140-2_4

    Chapter  MATH  Google Scholar 

  23. Veyrat-Charvillon, N., Gérard, B., Renauld, M., Standaert, F.-X.: An optimal key enumeration algorithm and its application to side-channel attacks. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 390–406. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35999-6_25

    Chapter  Google Scholar 

  24. van Vredendaal, C.: Reduced memory meet-in-the-middle attack against the NTRU private key. LMS J. Comput. Math. 19(A), 43–57 (2016). https://doi.org/10.1112/S1461157016000206

    Article  MathSciNet  Google Scholar 

  25. Wunderer, T.: Revisiting the hybrid attack: improved analysis and refined security estimates. Cryptology ePrint Archive, Report 2016/733 (2016). http://eprint.iacr.org/2016/733

Download references

Author information

Authors and Affiliations

  1. Universidad del Norte, Barranquilla, Colombia

    Ricardo Villanueva-Polanco

Authors
  1. Ricardo Villanueva-Polanco
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ricardo Villanueva-Polanco .

Editor information

Editors and Affiliations

  1. Radboud University Nijmegen, Nijmegen, The Netherlands

    Peter Schwabe

  2. Universidad de Santiago de Chile, Santiago, Chile

    Nicolas Thériault

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Villanueva-Polanco, R. (2019). Cold Boot Attacks on Bliss. In: Schwabe, P., Thériault, N. (eds) Progress in Cryptology – LATINCRYPT 2019. LATINCRYPT 2019. Lecture Notes in Computer Science(), vol 11774. Springer, Cham. https://doi.org/10.1007/978-3-030-30530-7_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-30530-7_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-30529-1

  • Online ISBN: 978-3-030-30530-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation