Skip to main content
SpringerLink
Log in

Design and Implementation of Fast and Cost-Effective FPGA-Based Fuzzy Rainbow Tradeoffs

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

Time/memory tradeoffs are techniques used in cryptanalysis to trade increased memory usage with decreased computation time. We consider the fuzzy-rainbow tradeoff, a powerful technique used in 2010 to attack the GSM A5/1 cipher. We extend the focus from the simple model that considers only the main memory usage, to a new, more realistic one that also includes the hierarchical (external) storage. Moreover, as far as we know, existing solutions are only theoretical and do not consider the performance level of real systems. In this paper, we propose a reference hardware and software design for the cryptanalysis of ciphers and one-way functions based on FPGAs, SSDs and the fuzzy rainbow tradeoff algorithm. We evaluate the performance of our design by extending an existing analytical model to account for the actual storage hierarchy, and we estimate an attack time for DES and A5/1 ciphers of less than one second, demonstrating that these ciphers can be cracked in real-time with a budget under 6000€. We finally discuss possible refinements to the model and to the hardware design that could be helpful in practice.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data availability

The data in the paper were computed using our tool available in [8].

Notes

  1. In a well-configured machine with no latencies, instead, the time will be close to the maximum between FPGA and disk time.

References

  1. Hellman ME. A cryptanalytic time-memory trade-off. IEEE Trans Inf Theory. 1980;26(4):401–6.

    Article  MathSciNet  MATH  Google Scholar 

  2. Oechslin P. Making a faster cryptanalytic time-memory trade-off. In: Boneh D, editor. Advances in cryptology (CRYPTO 2003). Santa Barbara: Springer; 2003. pp. 617–30.

  3. Nohl K. Attacking phone privacy. Black Hat USA; 2010. pp. 1–6.

  4. Kim B-I, Hong J. Analysis of the non-perfect table fuzzy rainbow tradeoff. In: Boyd C, Simpson L, editors. In: Information security and privacy. Berlin: Springer; 2013. pp. 347–62.

  5. Kim B-I, Hong J. Analysis of the perfect table fuzzy rainbow tradeoff. J Appl Math. 2014;2014: 765394. https://doi.org/10.1155/2014/765394.

    Article  MATH  Google Scholar 

  6. Kumar S, Paar C, Pelzl J, Pfeiffer G, Schimmler M. Breaking ciphers with copacobana—a cost-optimized parallel code breaker. In: Goubin L, Matsui M, editors. Cryptographic hardware and embedded systems (CHES 2006). Yokohama: Springer; 2006. pp. 101–18.

  7. Mentens N, Batina L, Preneel B, Verbauwhede I. Time-memory trade-off attack on FPGA platforms: UNIX password cracking. In: Bertels K, Cardoso JMP, Vassiliadis S, editors. Reconfigurable computing: architectures and applications. Delft: Springer; 2006. pp. 323–34.

  8. Veronese L, Palmarini F, Focardi R, Luccio FL. Parameter calculator and performance evaluator tool. 2021. https://github.com/secgroup/fuzzy-rainbow/.

  9. Veronese L, Palmarini F, Focardi R, Luccio FL. A fast and cost-effective design for fpga-based fuzzy rainbow tradeoffs. In: Proceedings of the 8th international conference on information systems security and privacy, ICISSP 2022, online streaming, February 9–11, 2022. SCITEPRESS, Online (2022). pp. 165–176. https://doi.org/10.5220/0010904300003120.

  10. Sr RHM, Thompson K. Password security—a case history. Commun ACM. 1979;22(11):594–7. https://doi.org/10.1145/359168.359172.

  11. Robling Denning DE. Cryptography and data security. Inc, USA: Addison-Wesley Longman Publishing Co.; 1982.

    MATH  Google Scholar 

  12. Barkan P. Cryptanalysis of ciphers and protocols. PhD thesis, Israel Institute of Technology. 2006.

  13. Quisquater J-J, Standaert F-X, Rouvroy G, David J-P, Legat J-D. A cryptanalytic time-memory tradeoff: first FPGA implementation; 2002. pp. 780–89 . https://doi.org/10.1007/3-540-46117-5_80.

  14. Quisquater J-J, Standaert F-X. Exhaustive key search of the des: updates and refinements. SHARCS 2005. 2005.

  15. Güneysu T, Kasper T, Novotný M, Paar C, Rupp A. Cryptanalysis with copacobana. IEEE Trans Comput. 2008;57(11):1498–513. https://doi.org/10.1109/TC.2008.80.

    Article  MathSciNet  MATH  Google Scholar 

  16. Theocharoulis K, Papaefstathiou I, Manifavas C. Implementing rainbow tables in high-end FPGAs for super-fast password cracking. In: 2010 international conference on field programmable logic and applications, 2010. pp. 145–50. https://doi.org/10.1109/FPL.2010.120.

  17. Golić JD. Cryptanalysis of alleged A5 stream cipher. In: Fumy W, editor. Advances in cryptology (EUROCRYPT ’97). Konstanz: Springer; 1997. pp. 239–55.

  18. Biryukov A, Shamir A, Wagner D. Real time cryptanalysis of A5/1 on a PC. In: Goos G, Hartmanis J, van Leeuwen J, Schneier B, editors. Fast software encryption. Yokohama: Springer; 2001. pp. 1–18.

  19. Barkan E, Biham E, Keller N. Instant ciphertext-only cryptanalysis of GSM encrypted communication. 2003;21:600–16. https://doi.org/10.1007/978-3-540-45146-4_35.

  20. Nohl K, Paget C. Gsm: Srsly. In: 26th Chaos communication congress, 2009. pp. 11–17:8.

  21. Kalenderi M, Pnevmatikatos D, Papaefstathiou I, Manifavas C. Breaking the GSM A5/1 cryptography algorithm with rainbow tables and high-end FPGAs. In: 22nd international conference on field programmable logic and applications (FPL). 2012. pp. 747–53. https://doi.org/10.1109/FPL.2012.6339146.

  22. Lu J, Li Z, Henricksen M. Time-memory trade-off attack on the GSM A5/1 stream cipher using commodity GPGPU. In: Malkin T, Kolesnikov V, Lewko AB, Polychronakis M, editors. Applied cryptography and network security. Cham: Springer; 2015. pp. 350–69.

  23. Verdult R, Garcia FD, Balasch J. Gone in 360 seconds: hijacking with Hitag2. In: Kohno T, editor. 21st USENIX security symposium (USENIX’12), 2012;237–252. USENIX Association, Washington, D.C. https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final95.pdf.

  24. Verdult R, Garcia FD, Ege B. Dismantling megamos crypto: wirelessly lockpicking a vehicle immobilizer. In: 24th USENIX security symposium (USENIX ’15). USENIX Association, Washington, D.C. 2015. https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/verdult-dnp.

  25. Kim JW, Hong J, Park K. Analysis of the rainbow tradeoff algorithm used in practice. Cryptology ePrint archive, report 2013/591.2013. https://eprint.iacr.org/2013/591.

  26. Haghighi M, Dakhilalian M. A practical time complexity analysis of fuzzy rainbow tradeoff. In: 2014 11th international ISC conference on information security and cryptology. 2014. pp. 39–43 . https://doi.org/10.1109/ISCISC.2014.6994019.

  27. Egorushkin M. Atomic queue. 2019. https://github.com/max0x7ba/atomic_queue.

  28. Nohl K. A5/1 decrypt—back clocking. 2010. https://opensource.srlabs.de/projects/a51-decrypt/wiki/Backclocking.

  29. Percival C. Stronger key derivation via sequential memory-hard functions. 2009.

  30. Percival C, Josefsson S. The scrypt password-based key derivation function. 2016. https://tools.ietf.org/html/rfc7914.

  31. Biryukov A, Dinu D, Khovratovich D. Argon2: new generation of memory-hard functions for password hashing and other applications. In: Proceedings of the 1st IEEE European symposium on security and privacy, EuroS &P 2016. 2016.

  32. Boneh D, Corrigan-Gibbs H, Schechter S. Balloon hashing: a memory-hard function providing provable protection against sequential attacks. In: Proceedings of the 22nd annual international conference on the theory and applications of cryptology and information security, ASIACRYPT 2016. 2016.

Download references

Funding

This study was funded by 10288513. European Regional Development Fund (ERDF), SAFE PLACE: “Sistemi IoT per ambienti di vita salubri e sicuri” project, and by project SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU.

Author information

Authors and Affiliations

  1. DAIS, Ca’ Foscari University, via Torino 155, Venice, 30174, Italy

    Leonardo Veronese, Francesco Palmarini, Riccardo Focardi & Flaminia L. Luccio

  2. 10Sec S.r.l., via delle Industrie 13, Venice, 30175, Italy

    Leonardo Veronese, Francesco Palmarini, Riccardo Focardi & Flaminia L. Luccio

Authors
  1. Leonardo Veronese
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francesco Palmarini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Riccardo Focardi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Flaminia L. Luccio
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Flaminia L. Luccio.

Ethics declarations

Conflict of interest

All authors declare that they have no conflict of interest.

Ethics approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Advances on Information Systems Security and Privacy” guest edited by Steven Furnell and Paolo Mori.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Veronese, L., Palmarini, F., Focardi, R. et al. Design and Implementation of Fast and Cost-Effective FPGA-Based Fuzzy Rainbow Tradeoffs. SN COMPUT. SCI. 4, 330 (2023). https://doi.org/10.1007/s42979-023-01762-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-023-01762-9

Keywords

Search

Navigation