passphrases with more than 160 bits of entropy

Victor Duchovni <Victor.DuchovniMorganStanley.com>
writes:
> Actually calculating the entropy for real-world
functions and generators
> may be intractable...

It is, in fact, generally intractable.

1) Kolmogorov-Chaitin entropy is just plain intractable --
finding the
   smallest possible Turing machine to generate a sequence
is not
   computable.
2) Shannon entropy requires a precise knowledge of the
probability of
   all symbols, and in any real world situation that, too,
is
   impossible.

Usually, the best you can do is produce (bad) bounds, and
sometimes
not even that.

One thing that can be done, of course, is that you can
prove, under
certain assumptions, that it would take an intractable
amount of
computation to distinguish a particular PRNG from a true
random
sequence with greater than 50% probability. However, this is
very much
NOT the same as showing that the PRNG sequence contains an
endless
stream of entropy -- in fact, the unicity distance very
clearly shows
you how much "real" entropy you have, and it
usually isn't
much. Merely because "too much" computation
would be needed does not
mean that you've created entropy -- you've just made it
hard for the
opponent to get at your PRNG seed.

"Anyone who considers arithmetical methods of
producing random digits
is, of course, in a state of sin." -- John von Neumann

Perry

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

On Mar 22, 2006, at 2:05 PM, Perry E. Metzger wrote:

> Victor Duchovni <Victor.DuchovniMorganStanley.com> writes:
>> Actually calculating the entropy for real-world
functions and  
>> generators
>> may be intractable...
>
> It is, in fact, generally intractable.
>
> 1) Kolmogorov-Chaitin entropy is just plain intractable
-- finding the
>    smallest possible Turing machine to generate a
sequence is not
>    computable.
> 2) Shannon entropy requires a precise knowledge of the
probability of
>    all symbols, and in any real world situation that,
too, is
>    impossible.

I'm not a cryptographer nor a mathematician, so I stand
duly  
corrected/chastised 

So, if you folks care to educate me, I have several
questions related  
to entropy and information security (apologies to any
physicists):

* How do you measure entropy? I was under the (false)
impression that  
Shannon gave a formula that measured the entropy of a
message (or  
information stream).
* Can you measure the entropy of a random oracle? Or is that
what  
both Victor and Perry are saying is intractable?
* Are there "units of entropy"?
* What is the relationship between randomness and entropy?
* (Apologies to the original poster) When the original
poster  
requested "passphrases with more than 160 bits of
entropy", what was  
he requesting?
* Does processing an 8 character password with a process
similar to  
PKCS#5 increase the entropy of the password?
* Can you add or increase entropy?

Thanks in advance,
Aram Perez

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

Aram Perez <aramperezmac.com> wrote:

> So, if you folks care to educate me, I have several
questions related
> to entropy and information security (apologies to any
physicists):
>
I'll answer the easier questions. I'll leave the harder
ones for someone
with a better grounding in information theory.

> * What is the relationship between randomness and
entropy?

Roughly, they both measure unpredictability. Something that
is hard
to predict is random, or has high entropy. There are
mathematical
formulations that make this a lot more precise, but that's
the basic
idea.

> * Does processing an 8 character password with a
process similar to
> PKCS#5 increase the entropy of the password?

Absolutely not!

At best, you preserve the original entropy, just
distributing it
differently. If you get the processing wrong, you can reduce
or
even entirely destroy it, but no amount of any kind of
processing
can increase it.

> * Can you add or increase entropy?
>
You can add more entropy, either from another source or more
from the same source. That is the only way to increase it.

--
Sandy Harris
Zhuhai, Guangdong, China

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

Aram Perez wrote:

> * How do you measure entropy? I was under the (false)
impression that  
> Shannon gave a formula that measured the entropy of a
message (or  
> information stream).

Entropy is defined in terms of probability.  It is a measure
of
how much you don't know about the situation.  If by
"message"
you mean a particular message that you are looking at, it
has
zero entropy.  It is what it is;  no probability required.

If by "stream" you mean a somewhat abstract
notion of an ensemble
of messages or symbols that you can only imperfectly
predict, then
it has some nonzero entropy.

> * Can you measure the entropy of a random oracle? Or is
that what  both 
> Victor and Perry are saying is intractable?

That is a tricky question for a couple of reasons.
  a) It will never be completely answerable because the
question hinges
   on the word "random", which means different
things to different people.
   Thoughtful experts use the word in multiple inconsistent
ways.
  b) It also depends on just what you mean by
"measure".  Often it
   is possible to _ascertain_ the entropy of a source ...
but direct
   empirical measurements of the output are usually not the
best way.

> * Are there "units of entropy"?

Yes.  It is naturally _dimensionless_, but dimensionless
quantities
often have nontrivial units.  Commonly used units for
entropy
include
  ++ bits
  ++ joules per kelvin.  One J/K equals 1.04×10^23 bits
For more on this, see
   http://www.av8n.com/physics/thermo-laws.htm#sec-s-units

> * What is the relationship between randomness and
entropy?

They are neither exactly the same nor completely unrelated.
A pseudorandom sequence may be "random enough"
for many
applications, yet has asymptotically zero entropy density.
A sequence of _odd_ bytes is obviously not entirely random,
yet may have considerable entropy density.

> * (Apologies to the original poster) When the original
poster  requested 
> "passphrases with more than 160 bits of
entropy", what was he requesting?

When you apply a mathematical function to an ensemble of
inputs, it
is common to find that the ensemble of outputs has less
entropy than
the ensemble of inputs. A simple pigeonhole argument
suffices to show
that a function whose output is represented in 160 bits
cannot possibly
represent more than 160 bits of entropy per output.  So if
you want
the ensemble of outputs to have more than 160 bits of
entropy, it is
necessary to do something fancier than a single instance of
SHA-1.

> * Does processing an 8 character password with a
process similar to  
> PKCS#5 increase the entropy of the password?

No.

> * Can you add or increase entropy?

Shuffling a deck of cards increases the entropy of the deck.

For more on this, see
   http://www.av8n.com/physics/thermo-laws.htm#sec-entropy

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

On Wed, Mar 22, 2006 at 03:29:07PM -0800, Aram Perez wrote:

> * How do you measure entropy? I was under the (false)
impression that  
> Shannon gave a formula that measured the entropy of a
message (or  
> information stream).

He did give a formula for the entropy of a source; however
the caculation is
based on the probabilties of each symbol appearing. Unless
you know those, you
can't actually apply the formula. So it is computable in
theory, just not in
pratice for any source that is at all interesting.

> * Can you measure the entropy of a random oracle? Or is
that what  
> both Victor and Perry are saying is intractable?

A random oracle, by definition, produces a completely random
output. However,
since random oracles don't actually exist that does not
seem to be a terribly
interesting thing to be measuring the entropy of.

> * Are there "units of entropy"?

Bits are usually the most intuitive/useful unit.

> * What is the relationship between randomness and
entropy?

I have a vague feeling this question requires a deeper
answer than I'm able to
provide.

> * Does processing an 8 character password with a
process similar to  
> PKCS#5 increase the entropy of the password?

No, because there are no additional secrets. Knowledge of
the password is all
you need to rederive the final output, thus clearly there is
no additional
information (ie, entropy) in the output that was not in the
original password.

This ignores the salt, iteration count, and the
specification of the algorithm
itself, but those are all (usually) public. So they
contribute to the entropy,
they do not contribute to the conditional entropy, which is
what we are usually
interested in when thinking about entropy and crypto.

> * Can you add or increase entropy?

Yes. Let's say the contents of tommorrow's NY Times has n
bits of entropy (we
probably can't actually calculate n, but we know it is a
finite and fixed
value). And the LA Times from the same day will also have
some amount of
entropy (call it n'). However, the entropy of the two
papers combined would
(probably) not be n+n', but some number x st min(n,n')
<= x <= n+n', because
the two papers will report on many of the same issues, carry
some of the same
AP stories, and so forth. This redundant information
doesn't increase the
entropy (reading the same AP story in a second newspaper
wouldn't give you any
new information).

A book you may find interesting is "Elements of
Information Theory" by Cover &
Thomas.

-Jack

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

At 22:09  -0500 2006/03/22, John Denker wrote:
>Aram Perez wrote:
>
>>* Can you add or increase entropy?
>
>Shuffling a deck of cards increases the entropy of the
deck.

As a minor nit, shuffling *in an unpredictable manner* adds
entropy, 
because there is extra randomness being brought into the
process. If 
I was one of those people who can do a perfect riffle
shuffle, 
reordering the cards in this entirely predictable manner
does not 
increase or decrease the existing entropy.

So in one sense, the answer is a simple "no"...
nothing you can do to 
a passphrase can increase its (that is, the passphrase's)
entropy. 
You can add randomness from another source, and increase the
total 
entropy, but I don't think that is relevant to the original
question.

Greg.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com