Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
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.