[Cryptography] Entropy is forever ...

[Florian Weimer]

* R. Hirschfeld:

> On the other hand, there is a notion of algorithmic complexity of an
> individual string, i.e., the length of the shortest program that
> produces it in some universal programming language.  In this sense,
> most strings are (Kolmogorov) random but those easy to generate (e.g.,
> all nines, or the digits of pi) are not.

When just talking about the a single password, the universal
programming language might have (among other things) just a special
instruction to output it.  This may not be as preposterous as it
sounds—password crackers solve a similar problem (they try to probe
passwords of encreasing complexity), and they come with dictionaries
of common words.

More importantly, the relative ordering of password complexity will
depend a *lot* on accidents such as choices of instruction encodings
for the compleixty-measuring machine.  I also find it difficult to
believe that for these three strings,

Abreisetag
bien3ba7Ie
N4QbQrcnWQ

there is a more efficient encoding than just output the characters one
by one, but the first one is a regular German word, the second one is
insecure (pronounceable) output from pwgen, and the third one is
supposed to be purely random.