lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Tue, 13 Mar 2018 04:41:07 0500
From: denis bider <denisbider.ietf@...il.com>
To: discussions@...swordhashing.net
Subject: Re: [PHC] How to: A superefficient cryptographic accumulator?
Stefan  you are definitely right. My hash function construction was bad. :)
Still, I wonder.
On Tue, Mar 13, 2018 at 4:31 AM, <Stefan.Lucks@...weimar.de> wrote:
> Hey Denis,
>
> you have a nice idea, but it won't work for informationtheoretical
> reasons. I'll explain below.
>
> [...] the best measure for password safety is probably to prevent users
>> from using any of billions of known revealed passwords, but the compressed
>> database is 5 GB in size:
>>
>> https://github.com/berzerk0/ProbableWordlists/blob/master/Downloads.md
>>
>
> Let us denote this list of bad passwords as "L", and the universe of
> passwords not in L (up to a fixed length) as "U".
>
> Now. I sort of have this intuition that it’s possible to compress this crap
>> into 20 bytes. That's not a typo – 20 bytes, not megabytes or something.
>> But I don’t know how.
>>
>> If we have an infinitely fast computer, then we can simply find X such
>> that:
>>
>> TruncateTo32Bits ( SHA256 ( X  P1 ) ) == 0x00000000
>> TruncateTo32Bits ( SHA256 ( X  P2 ) ) == 0x00000000
>> TruncateTo32Bits ( SHA256 ( X  anything else ) ) == whatever
>>
>
> What you mean is
>
> (1) Trunc32 ( SHA256 ( X  P ) ) == 0x00000000
> for all P in L
>
> and ideally
>
> (2) Trunc32 ( SHA256 ( X  Q ) ) != 0x00000000
> for all Q in U
>
> or, for a
>
> (2') Pr [Trunc32 ( SHA256 ( X  Q ) ) == 0x00000000] < 0.01
> for Q in U chosen at random
>
> If we crank the infinitely fast computer long enough, we should be able to
>> find this X,
>>
>
> If we consider SHA256 as a "random oracle", such an X exists, and,
> assuming an unlimited amount of computer power, we can find it.
>
> and it should be small in size.
>>
>
> Why do you think it would be small in size? That is the whole point: X
> will be HUGE! If we want to meet both (1) and (2), then we can
> statistically expect X to be as big as L. The reason is simple: Whenever we
> change L, we need another X.
>
> Changing from (2) to (2') doesn't safe the day: X can be slightly smaller,
> but only by a few bits.
>
> The only reason we should not be able to find this X is if SHA256 has some
>> structural issue that prohibits an X like that from existing.
>>
>
> Yes, the iterated structure of SHA256 (and essentially all other hash
> functions ever published) makes the existence of X extremely unlikely.
> Neither SHA512 nor SHA3 will do, nor Blake, JH, Groestl, Skein, ...
>
> BTW, if X where actually small in size, the iterated structure would not
> pose a problem, and even SHA256 would do.
>
> In that case we use a better hash function.
>>
>
> Good luck with designing an entirely new type of cryptographic hash
> function!
>
> Now, the reason we can’t do that is, the way SHA256 is designed, it
>> requires us to have an infinitely fast computer.
>>
>
> There are three obstacles to doing that:
>
> 1. The way SHA256 and essentially all other hash functions are designed,
> such an X is unlikely to exist.
>
> 2. Given an ideal hash function (a "random oracle") X should exist, but we
> would need an absurdly fast computer to find X.
>
> 3. Given an ideal hash function and an absurdly fast computer, X would
> still be about as large as L. So even then, there is not much of an
> advantage over using L directly.
>
> Finally, you asked about a quantum computer. If s is the expected size of
> X (in bits), the search for X will take about 2^(2^s) steps on a classical
> computer. Using a quantum computer, we can apply Grover's algorithm to
> reduce this value to its squareroot: 2^((2^s)1). If L is a few Gigabytes,
> then s is 30 or larger. Even using a quantum computer, the sun will long be
> cold before your quantum computer can output X.
>
>
> Stefan
>
>  I love the taste of Cryptanalysis in the morning!
> 
> www.uniweimar.de/de/medien/professuren/mediensicherheit/peo
> ple/stefanlucks
> Stefan.Lucks (at) uniweimar.de, BauhausUniversität Weimar,
> Germany
>
Content of type "text/html" skipped
Powered by blists  more mailing lists