phc-discussions - Re: [PHC] Re: New password hashing entry: PolyPassHash

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Tue, 25 Mar 2014 13:35:28 -0700 (PDT)
From: "Stephen Touset" <stephen@...set.org>
To: discussions@...sword-hashing.net
Cc: "santiago torres" <sat417@...dents.poly.edu>,
 discussions@...sword-hashing.net
Subject: Re: [PHC] Re: New password hashing entry: PolyPassHash

Given a database that requires n shares to start validating passwords, what stops an attacker from creating n - 1 accounts with passwords under his control?-- 
Stephen Touset
stephen@...set.org

On Tue, Mar 25, 2014 at 6:03 AM, Justin Cappos <jcappos@....edu> wrote:

> The TLDR version of the scheme is as follows:
> Today password databases store: "username:salt: securehash(salt, password)"
>   An attacker can crack passwords individually by guessing the password and
> computing the salted secure hash.
> PolyPassHash stores: "username:salt:sharenumber: (share(sharenumber) XOR
> securehash(salt, password))"   So a correct password allows the server to
> obtain a share in a Shamir Secret store.   The only way to know if the
> share is valid (and the password is correct) is to have a threshold of
> shares.   Since a valid server gets many correct login attempts, it can
> trivially do this.   The attacker needs to simultaneously guess many
> accounts which increases the needed time exponentially.
> Thanks,
> Justin
> On Mon, Mar 24, 2014 at 5:34 PM, Justin Cappos <jcappos@....edu> wrote:
>> I would like to solicit the community's feedback about an submission to
>> the PHC called PolyPassHash.
>>
>> This scheme is different than most PHC entries in that it uses a
>> threshold-based storage technique to prevent passwords from being
>> individually cracked.   To validate a password, one must recover a share in
>> a Shamir Secret Store, which necessitates knowing a threshold of correct
>> passwords.   (There are extensions to allow passwords to be securely
>> validated by a server upon setup and also to support accounts that do not
>> count toward the threshold.)
>>
>> PolyPassHash gives an exponential increase in the search space an attacker
>> needs to explore while only increasing the server's time by a small linear
>> factor.   If you take the three passwords that are composed of six random
>> characters each and protect them with PolyPassHash, to search the key space
>> would take every computer on the planet working together longer than the
>> universe is estimated to have existed.   PolyPassHash is about as efficient
>> in terms of memory, disk, and CPU time as existing salted secure hash
>> techniques.   In fact, PolyPassHash is orthogonal to the secure hashing
>> technique and should integrate with (any?) other submission.
>>
>> More information about the scheme (including both technical documentation
>> and information for a more general audience) is available at:
>> https://github.com/JustinCappos/PolyPassHash
>>
>> There is also a Python implementation available in that repository and a
>> link to the C implementation (by Santiago Torres) which will be submitted
>> to the contest.
>>
>> I welcome any comments or feedback.
>>
>> Thanks,
>> Justin
>>
Content of type "text/html" skipped