On 25/08/17 09:46, Thomas Schmitt wrote: > Mario Castelán Castro wrote: >> In principle, yes, but in practice, not at all. File compressors [...] > > I wrote "estimate", "approximation", and "best possible compression". > Of course gzip is not a very good approximation even if one subtracts the > header bytes.
I know what you wrote. My point is that there is no way to make a reasonable approximation to the Kolmogorov complexity of a password. Also, again, file compressors are bad for small files, especially as small as passwords (less than 100 bytes). It makes little difference whether you discount the header and trailer, they are still bad. All contemporary practical compressorors (some research compressors do a little more than this, see e.g.: the ones in the Hutter prize compettion) are based on *verbatim* repetition and the biased distribution of bytes in the data. They are bad for your use case because there is little *verbatim* repetition in a password. They can not interpret the *meaning* of the information in any meaningful way, unlike an human. For example, for an human, a byte string “one, two, three...” (that goes to 10,000) is very simple to describe as “the numbers from 1 to 10,000 written in English and separated by “, ””. A compressor does not understand that these are consecutive numbers spelled in English and thus can not take advantage of this. The size of that data, compressed for example, with XZ, will be much longer than the phrase above that I used to describe it. To recap: Real-life file compressors can not be used to estimate the strength of passwords because they do not understand *meaning* as humans perceive it. > Better approximations are presented in the article. *What* article? Nobody has mentioned a scientific article in this thread. > Given the time spans > and computing powers which were mentioned, i'd say they performed less > than 2 exp 50 tries to crack the majority of good passwords. > I.e. the compression which is established by their enumeration can squeeze > those good passwords to less than 50 bits of size. Of course, as any lossles > compression, it has to inflate other better passwords by at least one bit. > > >>> The second password class and my knowledge about it gives me not more >>> than a reduction of text bit number by 25 percent (6 bit text -> 8 bit >>> binary) and a couple of bits which are harder to harvest. > >> This is a somewhat oversimplified analysis. > > Wasn't it you who said in > https://lists.debian.org/debian-user/2017/08/msg01260.html > “alias gen-password="head -c 16 /dev/urandom | base64 | head -c 22 && echo"” > > After exploiting the "base64" part to get my 25 percent,i'd go for > /dev/urandom. man 4 urandom says: > "[...] if there is not sufficient entropy in the > entropy pool, the returned values are theoretically vulnerable to a > cryptographic attack on the algorithms used by the driver." I already explained why my method is not a 25% reduction in entropy, but you ignored the argument. Also, the theoretical vulnerability described in that man page is far fetched. It would require a *practical* attack comparable to pre-image of SHA1. And one must note that not even the deprecated MD5 has a practical pre-image attack, to the best of my knowledge. Moreover, such a theoretical attack applies only when the attacker *already knows* some of the output of your /dev/urandom, you output some more bytes, and the attacker has to guess these additional bytes based on the previous ouptput. In the use being discussed here, which is password generation, the attacker does not know anything else about the output of the PRNG. In Linux (the kernel) the same algorithm used for /dev/urandom is used to mix /dev/random. So there is likewise a theoretical possibility of a vulnerability if you use /dev/random instead of /dev/urandom. Read “/drivers/char/random.c” if you are interested in possible vulnerabilities of the random virtual devices. ----- Also, you mentioned 64 bits, but I *never* suggested this (in)security level. -- Do not eat animals, respect them as you respect people. https://duckduckgo.com/?q=how+to+(become+OR+eat)+vegan
signature.asc
Description: OpenPGP digital signature
