The cost of false alarms in Hellman and rainbow tradeoffs | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

The cost of false alarms in Hellman and rainbow tradeoffs

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Cryptanalytic time memory tradeoff algorithms are generic one-way function inversion techniques that utilize pre-computation. Even though the online time complexity is known up to a small multiplicative factor for any tradeoff algorithm, false alarms pose a major obstacle in its accurate assessment. In this work, we study the expected pre-image size for an iteration of functions and use the result to analyze the cost incurred by false alarms. We are able to present the expected online time complexities for the Hellman tradeoff and the rainbow table method in a manner that takes false alarms into account. We also analyze the effects of the checkpoint method in reducing false alarm costs. The ability to accurately compute the online time complexities will allow one to choose their tradeoff parameters more optimally, before starting the expensive pre-computation process.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Avoine G., Junod P., Oechslin P.: Time-memory trade-offs: false alarm detection using checkpoints. Indocrypt 2005. LNCS, vol. 3797, pp. 183–196. Springer–Verlag, Heidelberg (2005).

  2. Avoine G., Junod P., Oechslin P.: Characterization and improvement of time-memory trade-off based on perfect tables. ACM Trans. Inform. Syst. Secur. 11(4), 17:1–17:22 (2008), (See also [1]).

    Google Scholar 

  3. Babbage S.H.: Improved exhaustive search attacks on stream ciphers. In: European Convention on Security and Detection, IEE conference publication no. 408, pp.161–166. IEE, (1995).

  4. Barkan E., Biham E., Shamir A.: Rigorous bounds on cryptanalytic time/memory tradeoffs. Crypto 2006. LNCS, vol. 4117, pp. 1–21, Springer-Verlag, Heidleberg (2006).

  5. Biryukov A., Mukhopadhyay S., Sarkar P.: Improved time-memory trade-offs with multiple data. SAC 2005. LNCS, vol. 3897, pp. 110–127. Springer-Verlag, Heidleberg (2006).

  6. Biryukov A., Shamir A.: Cryptanalytic time/memory/data tradeoffs for stream ciphers. Asiacrypt 2000. LNCS, vol. 1976, pp. 1–13. Springer-Verlag, Heidleberg (2000).

  7. Denning D.E.: Cryptography and data security. (p. 100, Ron Rivest’s distinguished points observation). Addison-Wesley, Menlo Park (1982).

  8. Fiat A., Naor M.: Rigorous time/space tradeoffs for invering functions. SIAM J. Comput. 29(3), 790–803 (1999).

    Article  MathSciNet  Google Scholar 

  9. Flajolet P., Odlyzko A.M.: Random mapping statistics. Eurocrypt 1989. LNCS, vol. 434, pp. 329–354. Springer-Verlag, Heidleberg (1990).

  10. Dj.Golić J.: Cryptanalysis of alleged A5 stream cipher. Eurocrypt 1997. LNCS, vol. 1233, pp. 239–255. Springer-Verlag, Heidleberg (1997).

  11. Hellman M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. on Inform. Theory 26, 401–406 (1980).

    Article  MATH  MathSciNet  Google Scholar 

  12. Hong J., Jeong K.C., Kwon E.Y., Lee I.-S., Ma D.: Variants of the distinguished point method for cryptanalytic time memory trade-offs. ISPEC 2008. LNCS, vol. 4991. Springer-Verlag, Heidleberg, pp. 131–145 (2008).

  13. Kim I.-J., Matsumoto T.: Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size. IEICE Trans. Fundament. E82-A, 123–129 (1999).

    Google Scholar 

  14. Ma D.: Studies on the cryptanalytic time memory trade-offs. Ph.D. Thesis, Seoul National University, Aug 2008.

  15. Menezes A.J., vanOorschot P.C., Vanstone S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997).

    MATH  Google Scholar 

  16. Oechslin P.: Making a faster cryptanalytic time-memory trade-off. Crypto 2003. LNCS, vol. 2729, pp. 617–630 (2003).

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences and ISaC, Seoul National University, Seoul, 151-747, Korea

    Jin Hong

Authors
  1. Jin Hong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jin Hong.

Additional information

Communicated by C. Boyd.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hong, J. The cost of false alarms in Hellman and rainbow tradeoffs. Des. Codes Cryptogr. 57, 293–327 (2010). https://doi.org/10.1007/s10623-010-9368-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-010-9368-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation