[Cryptography] Zero Knowledge: Have I Been Pwned?

[Bill Frantz]

On 9/10/17 at 11:25 AM, hbaker1 at pipeline.com (Henry Baker) wrote:

>FYI --
>
>https://www.troyhunt.com/introducing-306-million-freely-downloadable-pwned-passwords/
>
>Introducing 306 Million Freely Downloadable Pwned Passwords
>
>03 August 2017
>
>"The entire collection of 306 million hashed passwords can be 
>directly downloaded from the Pwned Passwords page.  It's a 
>single 7-Zip file that's 5.3GB which you can then download and 
>extract into whatever data structure you want to work with 
>(it's 11.9GB once expanded)."
>
>https://haveibeenpwned.com/Passwords
>
>--------
>
>Ok, all you crypto wizards: here's a real-world problem that needs to be solved.
>
>I don't think that it is safe to type a password into the HIBP 
>(Have I Been Pwned) page in order to check it.  Why?  Because 
>even if it was safe *before* I typed it in, it won't be *after* 
>I typed it in.
>
>I also don't think that it is safe to type a SHA1 hash of a 
>password into the HIBP either.  Why?  Because the database 
>contains the complete list of pairs (password,SHA1(password)), 
>so inverting these particular hashes is trivial, so this is 
>equivalent to simply typing in the unhashed password.
>
>Yes, I could download 5.3GB of data & decompress it to 11.9GB & 
>search it myself, and never reveal what password(s) I'd like to 
>check.  But I'd rather not download 5.3GB of data.
>
>Soooooo...
>
>What would be a good protocol for the HIBP site itself, and a 
>good protocol for anyone who wants to query it?
>
>Some desiderata for the protocol:
>
>* All I learn from my query is whether or not the password is the database -- i.e., exactly 1 bit.
>* All the HIBP database learns is that there *has* been a 
>query, but can't determine what the query was, or whether it 
>was successful.
>* The total number of bits transmitted in both directions 
>should be a number of orders of magnitude less than 5.3GB.
>
>Any suggestions?

My suggestion is that you, or the Pawned Password Database make 
a Bloom filter <https://en.wikipedia.org/wiki/Bloom_filter> from 
the the passwords. It will be small enough to store on your disk 
-- my quick calculation says about 750 MB for a filter with a 
0.1% probability of a false positive.

If they make the filter, then the cost of downloading it will be 
smaller, but it should not compress very much. If you make the 
filter, then you can be sure it was made correctly. Note that 
the 5.3 GM of data is about 5 times the size of an Apple iPhone 
update, so downloading it is tedious but still practical.

Note that a Bloom filter needs good, but not cryptographically 
secure hashes. SHA1 is more than good enough for this use.

I think, for most uses, the possibility of false positives is 
OK. If you get a positive answer, you recourse is to change that password.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | Re: Hardware Management Modes: | Periwinkle
(408)356-8506      | If there's a mode, there's a   | 16345 
Englewood Ave
www.pwpconsult.com | failure mode. - Jerry Leichter | Los Gatos, 
CA 95032