[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Sat, 19 Jan 2013 22:02:11 +0100
From: Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com>
To: crypt-dev@...ts.openwall.com
Subject: Re: password hashing competition?
I'm currently revising the call draft. If you have any
comment/suggestion, please send it here (or privately if you prefer).
Given the high entropy of candidate names, the competition will most
probably be "Password hashing competition". It may be fun to propose
submitters of an algorithm/method to also propose a name for the
objects considered.
Please also let me know if you would like to be in the committee that
will be responsible for the selection (which will be based on
consensus, rather than a formal vote), or if you'd like to suggest
someone. There's already a tentative list; I'll contact each one
individually to confirm that you're in (unless you contact me before).
I've also been told that NIST may have an interest in this. I don't
expect a formal sponsoring, but I'll still contact them to know
whether/how they want to contribute.
For those interested to learn how such competitions can work,
http://competitions.cr.yp.to/ lists all major previous crypto
competitions. In particular, you may wish to look at eSTREAM's call:
http://www.ecrypt.eu.org/stream/call/.
Thanks!
On Fri, Jan 11, 2013 at 8:57 AM, Jean-Philippe Aumasson
<jeanphilippe.aumasson@...il.com> wrote:
> 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.
