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 <***@gmail.com>
Date: Thu, Jan 10, 2013 at 11:52 AM
Subject: Re: Password hashing competition
To: Marsh Ray <***@extendedsubset.com>, ***@openwall.com, Matthew
Green <***@gmail.com>, ***@gmail.com,
***@bindshell.nl, ***@tarsnap.com, Samuel Neves
<***@dei.uc.pt>, Zooko Wilcox-O'Hearn <***@zooko.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 ***@something. 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 ***@banana-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
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
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
On Mon, Jan 7, 2013 at 9:53 PM, Jean-Philippe Aumasson
Post by Jean-Philippe AumassonHello 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