Date: Fri, 11 Jan 2013 08:57:32 +0100 From: Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com> To: crypt-dev@...ts.openwall.com Subject: Re: password hashing competition? The emails below have been sent to a group of people that showed interest in the project. As Alex suggested we're now moving the discussion to this list. As promised in my initial message below, I've also established a preliminary (and very high-level) list of tasks for the future committee of the competition (if you wish to be part of it, let me know): logistics: -website -public mailing list -private mailing list -share repo -meet-up/workshop? submissions review: -check compliance with requirements -test code compilation -test test vectors evaluation: -security (are the claims correct?) -performance (are the claims correct?) -discuss relative merits -select winner(s) ---------- Forwarded message ---------- From: Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com> Date: Thu, Jan 10, 2013 at 11:52 AM Subject: Re: Password hashing competition To: Marsh Ray <marsh@...endedsubset.com>, solar@...nwall.com, Matthew Green <matthewdgreen@...il.com>, bascule@...il.com, epixoip@...dshell.nl, cperciva@...snap.com, Samuel Neves <sneves@....uc.pt>, Zooko Wilcox-O'Hearn <zooko@...ko.com> OK, here's a draft call. As we don't have a name yet for the competition I just called it "Banana": " ======================================================================= Banana Competition Call for Submissions ======================================================================= Background ======================================================================= Secure storage of passwords is critical to internet users' security: too often "password dumps" are published, sometimes exposing the security of millions of users. For example, in June 2012 about 6 million weak password hashes of a major networking service were leaked. Where does the problem come from? Most websites that authenticate their users (webmails, social network services, etc.) do it with pair username/password: to login in the website, you send your username and your password to the web server, which checks in its database that the given username is already registered and that the password is identical to the password set by that user. But how is this last step performed? Some web servers store your password in clear in their database (these are the services that send you your password by email when you hit "I forgot my password"), therefore password verification is just a comparison of two strings. This is an extremely risky and irresponsible approach, because an attacker who gains access to the database directly gets the password of each user. Such an attacker may then impersonate a user on the website attacked, or on another website where this user is registered (most people reuse a same password accross several services). Some other web servers store a *hash* of your password. Such a hash is computed by applying a function that transforms a string of arbitrary length to a random-looking string of fixed length (for example, 16 bytes). The goal of this approach to prevent an attacker to read your passwords if she gains access to the database. However, if the attacker knows the hash function used, she can try many candidate passwords until one matches the hash value observed (for example, using a "dictionary" of the most commonly used passwords). The degree of protection against such bruteforce attacks varies greatly with the hash function used: - Cryptographic hash functions, such as MD5, SHA-1, or SHA-256: these functions are typically very fast (several hundreds of megabytes per second on a desktop CPU), which is undesirable against bruteforce attacks. Furthermore, a given password is always hashed to the same value regardless of the user; this exposes the system to time-memory trade-off attacks (for example, using "rainbow tables"), which are much faster than a dictionary attack. - Cryptographic hash functions with a *salt*: a salt is an auxiliary input to the hash function that is selected randomly when a user sets his password. A same password hashed with two different salts will have two different hash values. This prevents time-memory trade-off attacks, because an attacker does not know in advance the salt used. However bruteforce attacks remain as fast as with unsalted hash functions. - Password-hashing functions, also called password-based key derivation functions: these functions mitigate bruteforce attacks by being significantly slower, and sometimes requiring a significant amount of memory (to increase the cost of bruteforce on technologies such as GPUs or FPGAs). Such functions thus provide a much greater protection. However, password-hashing function are not well understood, and only a handful of constructions have been proposed (PBKDF2, bcrypt, and scrypt are the most common). The security and cryptography communities now have a much better understanding of password hashing than a few years ago. It is thus time to develop a mature design for protecting passwords, that will provide enhance security compared to previous proposals and that will be easy to deploy across platforms and systems. Indeed, password-based authentication is used more broadly than for just websites: mobile devices, operating systems, etc. The development of the new password-hashing function will be performed through a public competition, a model that has proved effective to select cryptographic algorithms (see the AES, eSTREAM, or SHA-3 competitions). The Banana competition ======================================================================= The Banana competition is organized by a panel of experts consising of Jean-Philippe Aumasson (Kudelski Security, Switzerland) ... ... These experts will be responsible for the final selection of one or more algorithms, based on the public contribution and on their assessment of the submissions. The Banana competition will rely on contributions from the public: discussions of the relative merits of submitted algorithms, performance and security evaluations, etc. Discussions will take place on the mailing list banana@...ething. All submissions will be made available on the website of the project, www.banana-competition.net. The Banana competition is organized by a group of individuals, not by a standardization body. A provisional roadmap is: 2012 Q1 call for submissions 2013 Jan 1 submission deadline 2013 Q2 selection of finalists 2013 Q4 selection of an algorithm Technical guidelines ======================================================================= The submitted algorithm should satisfy the following requirements: * Functional - take as input at least -- a string of bytes of any length betwen 0 and 128 bytes (inclusive) -- a salt of length between 0 and 128 bytes -- one or more cost parameters, to tune time and/or space usage - produce an output of any length between 16 and 64 bytes (inclusive) * Security - behave as a random function (random-looking output, no length extension, no preimage, etc.) * Performance - be usable on common desktop, server, and mobile CPUs regardless of the manufacturer (that is, should not require any particular hardware) Additional evaluation criteria are: * Security: - speed-up when implemented on ASIC, FPGA, or GPU compared to single-CPU software (the lower, the better) - resilience to physical attacks (timing attacks, leakages, etc.) - effectiveness of the cost parameter (can the time and space expected requirements be bypassed?) * Simplicity - overall clarity of the algorithm (design symmetries, modularity, etc.) - ease of implementation, testing, and debugging - use of other primitives or constructions internally (the fewer, the better) Submission requirements ======================================================================= The following are to be provided with any submission: * Cover sheet - name of the submitted algorithm - name and email address of the submitter(s) * Specification - a complete and unambiguous description of the algorithm; however if the algorithm reuses an existing primitive, this primitive need not be described (for example, if the algorithm uses AES, it is not necessary to copy the specification of AES) - a statement that there are no hidden weaknesses (backdoor, etc.) * Efficiency analysis - a discussion of the performance of the algorithm on the target platforms (that is, mainstream software): expected speed of an optimized implementation, ability to exploit modern CPUs features (SIMD or multicore), etc. - a discussion of the performance of the algorithm on platforms that may be used for high-speed password cracking (ASIC, FPGAs, GPUs) * Code - a reference implementation in *portable C* - a comprehensive set of test vectors - optionally, implementations in other languages or specific to a given CPU/GPU, microarchitecture, etc. * Intellectual property statement - a statement that the algorithm is and will remain available worldwide on a royalty free basis, and that the designer is unaware of any patent of patent application that covers the use or implementation of the submitted algorithm. Submissions should be sent to submissions@...ana-competition.net on or before 32 Feb 3030 as a compressed archive, along with its sha256sum digest. " On Wed, Jan 9, 2013 at 10:17 PM, Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com> wrote: > Dear all, > > I'm contacting you because you showed interest in my idea of a > competition for a new password hashing scheme---and hopefully the > future de facto standard that will eliminate MD5 and pastebin dumps of > clear passwords. > > To get things started I'm writing a draft call for submissions that > will include background and motivations, state of the art, as well as > tentative requirements.I am also drawing a list of tasks for the > organization of the project, to assess its feasability and whether > we'll need external sponsors (I hope, and believe that, not). > > As discussed with the organizers of another cryptographic competition > that is starting soon, the most challenging will probably be to > establish a "core team" or "committee" to get the work done, namely: > preparing the call, receiving submissions, managing their evaluation, > and eventually selecting one or more winners. This is a big > responsibility! It's especially challenging when committee members > happen to have a submission in the competition (as it was the case in > eSTREAM). > > I proposed to call the competition something like "Secure Password > Hashing", or "Password Hashing Standard", because it's short and > people will directly know what it's about. Some of you don't like it, > arguing that "password hashing" is misleading, and proposed more > inventive names. I don't think the actual name is extremely important, > but we should agree on something. For example Marsh proposed "PASH", > for PAsh iS not a Hash, Password Authentication Secure Hash, and half > a dozen other meanings. We should just check that the name doesn't > mean or sound like anything silly/dirty in any language... > > I'll get back to you soon with drafts of the two aforementioned > deliverables. Meanwhile please refrain from discussing requirements > (it's better to start this when we've already a draft, even if it's to > rewrite it from scratch). Also let me know if you don't wish to be > part of this, of if you'd like to suggest other people. > > > Cheers, > > JP > > > PS: Below is a copy of the email I sent to the list > crypt-dev@...ts.openwall.com. > > > On Mon, Jan 7, 2013 at 9:53 PM, Jean-Philippe Aumasson > <jeanphilippe.aumasson@...il.com> wrote: >> Hello crypt-dev, >> >> this is a follow-up to >> https://twitter.com/aumasson/status/288289065311293440 >> and in particular to Solar Designer's suggestion to join this list (thanks!). >> >> As I'm new to the list, let me briefly introduce myself: I've done >> some research in cryptanalysis and (co-)designed the SHA3 finalist >> BLAKE, and more recently SipHash and BLAKE2 (more on >> https://131002.net/ and https://blake2.net). >> >> So what about this (naive?) idea of a competition? Well we've already >> had block ciphers (AES), stream ciphers (eSTREAM), hash functions >> (SHA-3), and very soon authenticated ciphers (TBD). Although I'm far >> from an expert when it comes to password hashing schemes, my feeling >> is that it's the most understudied cryptographic object, and at the >> same time the most needed today. There's just been only a handful of >> proposals, it's mostly ignored by academic research, and a number of >> people seems to have promising idea to do better. Perfect context for >> starting a new competition! >> >> "But we already have scrypt!": well, IMHO scrypt was quite a >> revolutionary design, but I tend to see it rather as a first step in >> the right direction rather than as the end of the road. >> >> Obviously organizing such a competition---or however we call >> it---creates a number of challenges: who decides of the winner(s), how >> should the call for submissions look like, what's the right time >> frame, etc. But these issues can be solved as long as there's a >> critical mass of commited people. >> >> Is this a silly idea? >> >> >> JP
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.