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 11:30:52 0400 (EDT) From: Ken T Takusagawa <kenta@....edu> To: discussions@...swordhashing.net Subject: Re: [PHC] How to: A superefficient cryptographic accumulator? For rejecting previously revealed passwords, the hashbased Bloom Filter data structure will do the trick. Your hash function does not need to be cryptographically secure. I feel that tuning the data structure to allow the false positive rate to be as high as 10% would be acceptable, but that's a subjective user experience issue. https://en.wikipedia.org/wiki/Bloom_filter ken On Tue, 13 Mar 2018, denis bider wrote: > Actually... I think with the hash function construction, I’ve actually shown one of > two things: > > (a) The recognizer function, F(x) => word32, can be as small as the size of the > hash function and its internal state. > > (b) Alternately, F(x) => word32 cannot be implemented using a hash function . > > The reasoning: > > Yes, if the number of passwords is N, then X would be expected to be 32*N bits in > size. But in order to calculate SHA256(X  Pcandidate), we do not need X. We just > need the last internal state of SHA256, which is much smaller. > > Therefore, if we have infinite computing power to generate it, a recognizer > function F(x) can either be implemented in a compact size that is both fast and > small to use, OR we can never find X for a large enough number of passwords because > the internal state of a hash function is too small. > > > On Tue, Mar 13, 2018 at 4:30 AM, denis bider <denisbider.ietf@...il.com> wrote: > Yeah, but... I'm still not so sure. :) People said we couldn't have a > digital currency either! The coins would be GIGABYTES in length! :D > This is not fractal compression because we do not intend to decompress. We > are definitely throwing away data. What we want is a compressed oracle, > however. > The size of X I estimated if using a hash function (8 bytes?!) was clearly > ridiculous. What I proposed was to generate X by bruteforcing it as a > counter input to a pseudorandom function that generates a string 32*N bits > in size. If N is the number of passwords we are encoding, then to encode 1 > billion passwords, the random string needs to have 32 billion bits  and they > all must be zero. Clearly, an X that we arrive at this way must be about 32 > billion bits in size. So, uh... 4 gigabytes. > > But what if... say... instead of a hash function  mod N arithmetic? > > Suppose we represent the passwords we want to store using primes P1, P2, ... > Pn. We generate: > > X = P1 * P2 * ... * Pn mod N > > Of course, when we do "mod N", we are losing information. But how fast? > > Are you sure that arguments against fractal compression also apply to highly > lossy compression like this? ZIP won't compress a PNG, but JPG will ;) > > > On Tue, Mar 13, 2018 at 3:56 AM, PoulHenning Kamp <phk@....freebsd.dk> > wrote: >  > In message > <CADPMZDBq_CsD2ztxBX4J0FZLyf8Stm+Bz=AOPs6Adq7frGmi1g@...l.gmail.com>, > denis bider writ > es: > > >For example, 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: > >[...] > >Now. I sort of have this intuition that it=E2=80=99s possible to > compress this crap > >into 20 bytes. > > This is basically the old "fractal compression" idea all over > again. > > It always goes more or less like this: > > 1. Look at the digits of PI or E, they look awfully random and > are > very hard to compress. > > 2. Yet, we have this incredibly simple formula for generating > them > (insert favourite PI or E expression here). > > 3. What an amazing compression ratio! > > 4. There must be some function which similarly emits the MPG > stream > of Lord Of The Rings > > 5. Profit! > > This thinking suffers both from logical fallacies and factual > misunderstandings. > > Ad 1: While it is generally a good indicator of entropy that you > cannot compress some data, it is not a proof that the data is > random, > you may simply be using the wrong compression algorithm. > > Ad 2: Deterministically generated data, no matter what its > entropy > might be, is never random, even when you do not know the formula > which generated the data. > > Ad 3: The reason the compression ratio is so amazing is that PI > or E has infinite length. Normally we use only about 816 digits > of either and it's way more compact than your formula to just > write down those digits. (Footnote: 355/113) > > Ad 4: Yes, there is undoubtedly such a function, but there is no > reason to think that it is significantly smaller than the > *finite* > length bitstream you are trying to produce with it. > > Ad 5: No, because finding the magic LOTR function has complexity > far exceeding the size of the known universe. > > PoulHenning > >  > PoulHenning Kamp  UNIX since Zilog Zeus 3.20 > phk@...eBSD.ORG  TCP/IP since RFC 956 > FreeBSD committer  BSD since 4.3tahoe > Never attribute to malice what can adequately be explained by > incompetence. > > > > >
Powered by blists  more mailing lists