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 PHC  
Open Source and information security mailing list archives
 

Date: Tue, 13 Mar 2018 04:30:11 0500
From: denis bider <denisbider.ietf@...il.com>
To: PoulHenning Kamp <phk@....freebsd.dk>
Cc: discussions@...swordhashing.net
Subject: Re: [PHC] How to: A superefficient cryptographic accumulator?
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=AOPs6
> Adq7frGmi1g@...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.
>
Content of type "text/html" skipped
Powered by blists  more mailing lists