[Cryptography] Entropy is forever ...

[Ray Dillinger]

The use of "entropy" to denote unpredictability in CSPRNG's
and other cryptographic numbers has always been problematic.

It's a physics concept that isn't really all that well mapped
to what we're using the word for.

There is a comment in some code I'm working on that seems somehow
relevant:  It says,

MStart[0]=169;  // determined by dice roll, guaranteed random every time!
MStart[1]=74;  // "magic numbers" to distinguish our packets from
everybody else's

As the above comment points out, randomness isn't properly
a measurable or even meaningful quality.  The MStart bytes
are transmitted at the beginning of every message, and
they are the same in every message.  We do not think of
such things as "random" and yet, if the comment is accurate,
they were selected by a method well understood to give
"random" results.

Entropy in physics follows a different model from the
rather peculiar "physics" of how it is conserved and
distributed in cryptographic systems.

If you have a CSPRNG seeded with a 256-bit state unknown to
and unpredictable by an opponent, and an absolutely perfect
algorithm, and your opponent has infinite computing power
and an absolutely perfect algorithm, your oppponent can look
at 2^255 bits of output from the CSPRNG and derive sufficient
constraints on its state that he can eliminate half the
possibilities for your 256-bit state - meaning you now have
255 bits of unknown state as far as that opponent is concerned.

In practice we don't achieve that level of "unpredictability
physics" in real systems.  We have no guarantees that our
algorithms are good let alone perfect, and our opponents
certainly do not have infinite computing power.  And we
don't model anything like that kind of unpredictability
physics when we're tracking so-called "entropy" in
cryptographic systems.  More usually we use linear rather
than exponential models just because they're easier to
keep updated "accurately" and it's a conservative estimate
on the level of unpredictability both in our state and in
our algorithms.

Nevertheless, I trust a CSPRNG with a "good" algorithm
and 16Kbytes of state unknown to and unpredictable by
an attacker, to remain absolutely secure for any practical
length sequence of bits without further input.  Most
CSPRNG's are, IMO, misled by the linear entropy accounting
model they use: they often wind up with not enough state,
and having got enough state (or having been configured to
use enough) they do not trust it to remain secure.

In part what the designers distrust is the ability of the
system to keep the state unknown to an attacker, which is
probably a risk more linear-in-time than exponential-in-
state-size. In part they distrust their ability to get an
initial state unknown to and unpredictable by the attacker,
which can be mitigated by mixing in unpredictable bits in
big chunks.  But the linear-in-bits "entropy" model they
use is not a good model for either of these risks.

Anyway the conservation laws are very different for
cryptographic entropy than they are for physics entropy,
so probably using a different word such as "surprisal"
would be less misleading.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150422/6843b44d/attachment.sig>