nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks

verfasst von : Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter

Erschienen in: Advances in Cryptology – ASIACRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present the Balloon password-hashing algorithm. This is the first practical cryptographic hash function that: (i) has proven memory-hardness properties in the random-oracle model, (ii) uses a password-independent access pattern, and (iii) meets—and often exceeds—the performance of the best heuristically secure password-hashing algorithms. Memory-hard functions require a large amount of working space to evaluate efficiently and, when used for password hashing, they dramatically increase the cost of offline dictionary attacks. In this work, we leverage a previously unstudied property of a certain class of graphs (“random sandwich graphs”) to analyze the memory-hardness of the Balloon algorithm. The techniques we develop are general: we also use them to give a proof of security of the scrypt and Argon2i password-hashing functions, in the random-oracle model. Our security analysis uses a sequential model of computation, which essentially captures attacks that run on single-core machines. Recent work shows how to use massively parallel special-purpose machines (e.g., with hundreds of cores) to attack memory-hard functions, including Balloon. We discuss these important attacks, which are outside of our adversary model, and propose practical defenses against them. To motivate the need for security proofs in the area of password hashing, we demonstrate and implement a practical attack against Argon2i that successfully evaluates the function with less space than was previously claimed possible. Finally, we use experimental results to compare the performance of the Balloon hashing algorithm to other memory-hard functions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity

Nächstes Kapitel Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak

Nur mit Berechtigung zugänglich

The relatively poor performance of Argon2i here is due to the attack we present in Sect. 4. It allows an attacker to save space in computing Argon2i with no increase in computation time.

We are eliding important definitional questions about what it even means, in a formal sense, for a function to be collision resistant [16, 70].

This description is intentionally informal—see the full version of the paperor the precise statement.

We have notified the Argon2i designers of this attack and the latest version of the specification incorporates a design change that attempts to prevent the attack [19]. We describe the attack on the original Argon2i design, the winner of the password hashing competition [56].

On an FPGA or ASIC, this table can be stored in relatively cheap shared read-only memory and the storage cost can be amortized over a number of compute cores. Even on a general-purpose CPU, the table and memory buffer for the single-pass construction together will only require \(8n + 1024(n/4) = 8n + 256n\) bytes when using our small-space computation strategy. Argon2i normally requires 1024n bytes of buffer space, so our strategy still yields a significant space savings.

Bellare, Ristenpart, and Tessaro consider a different type of multi-instance security [12]: they are interested in key-derivation functions f with the property that finding \((x_1, \dots , x_m)\) given \((f(x_1), \dots , f(x_m))\) is roughly m times as costly as inverting f once. Stebila et al. [73] and Groza and Warinschi [40] investigate a similar multiple-instance notion of security for client puzzles [31] and Garay et al. [38] investigate related notions in the context of multi-party computation.

In the original scrypt paper, Percival [60] also discusses parallel attacks and makes an argument for the security of scrypt in the pROM.

There is no consensus on whether it would be feasible to implement this parallel attack in hardware for realistic parameter sizes. That said, the fact that such pROM attacks exist at all are absolutely a practical concern.

A recent addendum to the paper suggests that the combinatorial conjectures that underlie their proof of security may be false [7, Sect. 0].

Our argument here gives some theoretical justification for the Argon2id mode of operation proposed in some versions of the Argon2 specification [19, Appendix B]. That variant follows a hashing with a password-independent access pattern by hashing with a password-dependent access pattern.

We provide a proof of security for single-pass Argon2i in the full version of this paper.

As described in Sect. 4.2, the contents of block i in Argon2i are derived from the contents of block \(i-1\) and a block chosen at random from the set

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53887-6_8/435237_1_En_8_IEq114_HTML.gif

. Throughout our analysis, all probabilities are taken over the random choices of the \(r_i\) values.

Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately hard, memory-bound functions. ACM Trans. Internet Technol. 5(2), 299–327 (2005)CrossRef

Almeida, L.C., Andrade, E.R., Barreto, P.S.L.M., Simplicio Jr., M.A.: Lyra: password-based key derivation with tunable memory and processing costs. J. Cryptographic Eng. 4(2), 75–89 (2014)CrossRef

Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53008-5_9 CrossRef

Alwen, J., Blocki, J.: Towards practical attacks on Argon2i and Balloon Hashing. Cryptology ePrint Archive, Report 2016/759 (2016). http://eprint.iacr.org/2016/759

Alwen, J., Blocki, J., Pietrzak, K.: The pebbling complexity of depth-robust graphs. Manuscript (Personal Communication) (2016)

Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 358–387. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49896-5_13 CrossRef

Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of scrypt and proofs of space in the parallel random oracle model. Cryptology ePrint Archive, Report 2016/100 (2016). http://eprint.iacr.org/

Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: STOC, pp. 595–603 (2015)

Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538–557. Springer, Heidelberg (2014). doi:10.1007/978-3-319-10879-7_31

10.

Aumasson, J.-P., Neves, S., Wilcox-O’Hearn, Z., Winnerlein, C.: BLAKE2: simpler, smaller, fast as MD5. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 119–135. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38980-1_8 CrossRef

11.

Back, A.: Hashcash-a denial of service counter-measure, May 1997. http://www.cypherspace.org/hashcash/. Accessed 9 Nov 2015

12.

Bellare, M., Ristenpart, T., Tessaro, S.: Multi-instance security and its application to password-based cryptography. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 312–329. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_19 CrossRef

13.

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS, pp. 62–73. ACM (1993)

14.

Benadjila, R., Billet, O., Gilbert, H., Macario-Rat, G., Peyrin, T., Robshaw, M., Seurin, Y.: SHA-3 proposal: ECHO. Submission to NIST (updated) (2009)

15.

Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766–776 (1989)MathSciNetCrossRefMATH

16.

Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: the power of free precomputation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 321–340. Springer, Heidelberg (2013). doi:10.1007/978-3-642-42045-0_17 CrossRef

17.

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Keccak sponge function family. Submission to NIST (Round 2) (2009)

18.

Biryukov, A., Dinu, D., Khovratovich, D.: Argon2 design document (version 1.2.1), October 2015

19.

Biryukov, A., Dinu, D., Khovratovich, D.: Argon2 design document (version 1.3), February 2016

20.

Biryukov, A., Khovratovich, D.: Tradeoff cryptanalysis of memory-hard functions. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 633–657. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48800-3_26 CrossRef

21.

Bitcoin wiki - mining comparison. https://en.bitcoin.it/wiki/Mining_hardware_comparison

22.

Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J.A., Felten, E.W.: SoK: research perspectives and challenges for Bitcoin and cryptocurrencies. In: Symposium on Security and Privacy. IEEE, May 2015

23.

Bonneau, J., Mironov, I.: Cache-collision timing attacks against AES. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 201–215. Springer, Heidelberg (2006). doi:10.1007/11894063_16 CrossRef

24.

Boyen, X.: Halting password puzzles. In: USENIX Security (2007)

25.

Canetti, R., Halevi, S., Steiner, M.: Mitigating dictionary attacks on password-protected local storage. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 160–179. Springer, Heidelberg (2006). doi:10.1007/11818175_10 CrossRef

26.

Chan, S.M.: Just a pebble game. In: IEEE Conference on Computational Complexity, pp. 133–143. IEEE (2013)

27.

CVE-2012-3287: md5crypt has insufficient algorithmic complexity (2012). http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2012-3287. Accessed 9 Nov 2015

28.

Di Crescenzo, G., Lipton, R., Walfish, S.: Perfectly secure password protocols in the bounded retrieval model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 225–244. Springer, Heidelberg (2006). doi:10.1007/11681878_12 CrossRef

29.

Dürmuth, M.: Useful password hashing: how to waste computing cycles with style. In: New Security Paradigms Workshop, pp. 31–40. ACM (2013)

30.

Dwork, C., Goldberg, A., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45146-4_25 CrossRef

31.

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). doi:10.1007/3-540-48071-4_10 CrossRef

32.

Dwork, C., Naor, M., Wee, H.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37–54. Springer, Heidelberg (2005). doi:10.1007/11535218_3 CrossRef

33.

Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585–605. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_29 CrossRef

34.

Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125–143. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19571-6_9 CrossRef

35.

Evans Jr., A., Kantrowitz, W., Weiss, E.: A user authentication scheme not requiring secrecy in the computer. Commun. ACM 17(8), 437–442 (1974)CrossRef

36.

Feldmeier, D.C., Karn, P.R.: UNIX password security - ten years later. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 44–63. Springer, Heidelberg (1990). doi:10.1007/0-387-34805-0_6 CrossRef

37.

Forler, C., Lucks, S., Wenzel, J.: Memory-demanding password scrambling. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 289–305. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45608-8_16

38.

Garay, J., Johnson, D., Kiayias, A., Yung, M.: Resource-based corruptions and the combinatorics of hidden diversity. In: ITCS, pp. 415–428. ACM (2013)

39.

Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)MathSciNetCrossRefMATH

40.

Groza, B., Warinschi, B.: Revisiting difficulty notions for client puzzles and DoS resilience. In: Gollmann, D., Freiling, F.C. (eds.) ISC 2012. LNCS, vol. 7483, pp. 39–54. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33383-5_3 CrossRef

41.

Ho, S.: Costco, Sam’s Club, others halt photo sites over possible breach, July 2015. http://www.reuters.com/article/2015/07/21/us-cyberattack-retail-idUSKCN0PV00520150721. Accessed 9 Nov 2015

42.

Hopcroft, J., Paul, W., Valiant, L.: On time versus space. J. ACM (JACM) 24(2), 332–337 (1977)MathSciNetCrossRefMATH

43.

Kaliski, B.: PKCS #5: Password-based cryptography specification, version 2.0. IETF Network Working Group, RFC 2898, September 2000

44.

Kelsey, J., Schneier, B., Hall, C., Wagner, D.: Secure applications of low-entropy keys. In: Okamoto, E., Davida, G., Mambo, M. (eds.) ISW 1997. LNCS, vol. 1396, pp. 121–134. Springer, Heidelberg (1998). doi:10.1007/BFb0030415 CrossRef

45.

Kirk, J.: Internet address overseer ICANN resets passwords after website breach, August 2015. http://www.pcworld.com/article/2960592/security/icann-resets-passwords-after-website-breach.html. Accessed 9 Nov 2015

46.

Klein, D.V.: Foiling the cracker: a survey of, and improvements to, password security. In: Proceedings of the 2nd USENIX Security Workshop, pp. 5–14 (1990)

47.

Krantz, L.: Harvard says data breach occurred in June, July 2015. http://www.bostonglobe.com/metro/2015/07/01/harvard-announces-data-breach/pqzk9IPWLMiCKBl3IijMUJ/story.html. Accessed 9 Nov 2015

48.

Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4), 1087–1130 (1982)MathSciNetCrossRefMATH

49.

Leong, P., Tham, C.: UNIX password encryption considered insecure. In: USENIX Winter, pp. 269–280 (1991)

50.

Malvoni, K., Designer, S., Knezovic, J.: Are your passwords safe: energy-efficient bcrypt cracking with low-cost parallel hardware. In: USENIX Workshop on Offensive Technologies (2014)

51.

Menezes, A.J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)CrossRefMATH

52.

Morris, R., Thompson, K.: Password security: a case history. Commun. ACM 22(11), 594–597 (1979)CrossRef

53.

Nordström, J.: New wine into old wineskins: a survey of some pebbling classics with supplemental results, March 2015. http://www.csc.kth.se/~jakobn/research/PebblingSurveyTMP.pdf. Accessed 9 Nov 2015

54.

Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 1–20. Springer, Heidelberg (2006). doi:10.1007/11605805_1 CrossRef

55.

Park, S., Pietrzak, K., Alwen, J., Fuchsbauer, G., Gazi, P.: Spacemint: a cryptocurrency based on proofs of space. Technical report, Cryptology ePrint Archive, Report 2015/528 (2015)

56.

Password hashing competition. https://password-hashing.net/

57.

Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119–127. ACM (1970)

58.

Paul, W.J., Tarjan, R.E.: Time-space trade-offs in a pebble game. Acta Informatica 10(2), 111–115 (1978)MathSciNetCrossRefMATH

59.

Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theor. 10(1), 239–251 (1976)MathSciNetCrossRefMATH

60.

Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan, May 2009

61.

Peslyak, A.: yescrypt, October 2015. https://password-hashing.net/submissions/specs/yescrypt-v2.pdf. Accessed 13 Nov 2015

62.

Peterson, A.: E-Trade notifies 31,000 customers that their contact info may have been breached in 2013 hack, October 2015. https://www.washingtonpost.com/news/the-switch/wp/2015/10/09/e-trade-notifies-31000-customers-that-their-contact-info-may-have-been-breached-in-2013-hack/. Accessed 9 Nov 2015

63.

Pippenger, N.: A time-space trade-off. J. ACM (JACM) 25(3), 509–515 (1978)MathSciNetCrossRefMATH

64.

Pornin, T.: The Makwa password hashing function, April 2015. http://www.bolet.org/makwa/. Accessed 13 Nov 2015

65.

Privacy Rights Clearinghouse: Chronology of data breaches. http://www.privacyrights.org/data-breach. Accessed 9 Nov 2015

66.

Provos, N., Mazières, D.: A future-adaptable password scheme. In: USENIX Annual Technical Conference, pp. 81–91 (1999)

67.

Reinhold, A.: HEKS: a family of key stretching algorithms (Draft G), July 2001. http://world.std.com/~reinhold/HEKSproposal.html. Accessed 13 Nov 2015

68.

Ren, L., Devadas, S.: Proof of space from stacked expanders. Cryptology ePrint Archive, Report 2016/333 (2016). http://eprint.iacr.org/

69.

Ristenpart, T., Tromer, E., Shacham, H., Savage, S.: Hey, you, get off of my cloud: exploring information leakage in third-party compute clouds. In: CCS, pp. 199–212. ACM (2009)

70.

Rogaway, P.: Formalizing human ignorance. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 211–228. Springer, Heidelberg (2006). doi:10.1007/11958239_14 CrossRef

71.

Savage, J.E.: Models of Computation: Exploring the Power of Computing. Addison-Wesley, New York (1998)MATH

72.

Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4(3), 226–248 (1975)MathSciNetCrossRefMATH

73.

Stebila, D., Kuppusamy, L., Rangasamy, J., Boyd, C., Gonzalez Nieto, J.: Stronger difficulty notions for client puzzles and denial-of-service-resistant protocols. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 284–301. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19074-2_19 CrossRef

74.

Takala, R.: UVA site back online after chinese hack, August 2015. http://www.washingtonexaminer.com/uva-site-back-online-after-chinese-hack/article/2570383. Accessed 9 Nov 2015

75.

Tompa, M.: Time-space tradeoffs for computing functions, using connectivity properties of their circuits. In: STOC, pp. 196–204. ACM (1978)

76.

Tracy, A.: In wake of T-Mobile and Experian data breach, John Legere did what all CEOs should do after a hack, October 2015. http://www.forbes.com/sites/abigailtracy/2015/10/02/in-wake-of-t-mobile-and-experian-data-breach-john-legere-did-what-all-ceos-should-do-after-a-hack/. Accessed 9 Nov 2015

77.

Tromer, E., Osvik, D.A., Shamir, A.: Efficient cache attacks on AES, and countermeasures. J. Cryptology 23(1), 37–71 (2010)MathSciNetCrossRefMATH

78.

Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol. 53, pp. 162–176. Springer, Heidelberg (1977). doi:10.1007/3-540-08353-7_135 CrossRef

79.

Vaughan-Nichols, S.J.: Password site LastPass warns of data breach, June 2015. http://www.zdnet.com/article/lastpass-password-security-site-hacked/. Accessed 9 Nov 2015

80.

Wagner, D., Goldberg, I.: Proofs of security for the unix password hashing algorithm. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 560–572. Springer, Heidelberg (2000). doi:10.1007/3-540-44448-3_43 CrossRef

Titel: Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks
verfasst von: Dan Boneh
Henry Corrigan-Gibbs
Stuart Schechter
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – ASIACRYPT 2016
Print ISBN: 978-3-662-53886-9

Electronic ISBN: 978-3-662-53887-6

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53887-6_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner