Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
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 [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
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 [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
Aram Perez [EMAIL PROTECTED] 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 [EMAIL PROTECTED]
Re: Linux RNG paper
I have examined the LRNG paper and have a few comments. CC'd to the authors so mind the followups. 1) In the paper, he mentions that the state file could be altered by an attacker, and then he'd know the state when it first came up. Of course, if he could do that, he could simply install a trojan in the OS itself, so this is not really that much of a concern. If your hard drives might be altered by malicious parties, you should be using some kind of cryptographic integrity check on the contents before using them. This often comes for free when encrypting the contents. 2) His objection against using keyboard data is perhaps just an indication that reseeding of the pool should occur with sufficient entropy that the values cannot efficiently be guessed via brute force search and forward operation of the PRNG. If the reseeding is of insufficient to deter brute force input space search, other bad things can happen. For example, in the next paragraph the author mentions that random events may reseed the secondary pool directly if the primary pool is full. If an attacker were to learn the contents of the secondary pool, he could guess the incremental updates to its contents and compare results with the real PRNG, resulting in an incremental state-tracking attack breaking backward security until a reseed from the primary is generated (which appears to have a minimum of 8 bytes, also perhaps too low). The answer is more input, not less. It's annoying that the random number generator code calls the unpredictable stuff entropy. It's unpredictability that we're concerned with, and Shannon entropy is just an upper bound on the predictability. Unpredictability cannot be measured based on outputs of sources, it must be based on models of the source and attacker themselves. But we all know that. Maybe we should invent a term? Untropy? And now a random(3) tangent: While we're on the subject of randomness, I was hoping that random(3) used the old (TYPE_0) implementation by default... lots of DoS tools use it to fill spoofed packet fields, and one 32-bit output defines the entire state of the generator --- meaning that I could distinguish DoS packets which had at least 32 bits of state in them from other packets. However, it appears that Linux and BSD both use a TYPE_3 pool, which makes such simple techniques invalid, and would probably require identification of a packet stream, instead of testing packets one by one. Since use of a real pool has put it beyond my interest and perhaps my ability, I'm giving the idea away. Email me if you find a really good use for PRNG analysis of this sort. For a TYPE_0 generator, the equation is: i' = (i * 1103515245 + 12345) 0x7fff As far as low-hanging fruit goes, the higher generator types still never set the highest order bit (RAND_MAX is 0x7fff), and the outputs are unaltered pool contents. -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Greek officials were tapped using law enforcement back door
On Thu, Mar 23, 2006 at 09:30:30AM -0500, Perry E. Metzger wrote: A while ago, you may recall that members of the Greek government were wiretapped, and at the time, I speculated that the bad guys may have abused the built in CALEA software in the switch to do it. Well, it now appears that that was precisely what happened. Unfortunately, the article below is short on detail -- anyone have access to primary sources? (I know there are at least a couple of Greek cryptographers on this list...) http://www.deccanherald.com/deccanherald/mar162006/update71652006316.asp Schneier posted this a few weeks ago: http://www.schneier.com/blog/archives/2006/03/more_on_greek_w.html -- - Adam ** Expert Technical Project and Business Management System Performance Analysis and Architecture ** [ http://www.adamfields.com ] [ http://www.aquick.org/blog ] Blog [ http://www.adamfields.com/resume.html ].. Experience [ http://www.flickr.com/photos/fields ] ... Photos [ http://www.aquicki.com/wiki ].Wiki - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
From: Jack Lloyd [EMAIL PROTECTED]
Sent: Mar 22, 2006 11:30 PM
To: cryptography@metzdowd.com
Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits
of entropy)
...
As an aside, this whole discussion is confused by the fact that there
are a bunch of different domains in which entropy is defined. The
algorithmic information theory sense of entropy (how long is the
shortest program that produces this sequence?) is miles away from the
information theory sense of entropy, and even that has a bunch of
different flavors.
For the information theory meanings of entropy, what you're really
talking about is a property of a probability distribution. You can do
that in terms of Shannon entropy if you want to know about bounds on
average bandwidth requirements for transmitting symbols from that
distribution. You can look at guessing entropy if you want to know
the -lg(expected work to guess the next symbol). You can look at
min-entropy if you want a hard bound on how many symbols you need to
sample to derive a 128-bit key that won't ever expose you to
weaknesses based on how you selected it. And so on.
Shannon entropy is the one most people know, but it's all wrong for
deciding how many samples you need to derive a key. The kind of
classic illustration of this is the probability distirbution:
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with probability
2^{-161}.
The Shannon entropy on this distribution is 81.5 bits. But if you
tried to sample it once to generate an 80-bit Skipjack key, half the
time, I'd guess your key on my first try.
...
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).
Right. If the probabilities are independent, you can add the
entropies. That's why they're defined in log terms.
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Greek officials were tapped using law enforcement back door
On Thu 23 Mar 2006 15:30, Perry E. Metzger wrote: A while ago, you may recall that members of the Greek government were wiretapped, and at the time, I speculated that the bad guys may have abused the built in CALEA software in the switch to do it. Well, it now appears that that was precisely what happened. Unfortunately, the article below is short on detail -- anyone have access to primary sources? (I know there are at least a couple of Greek cryptographers on this list...) http://www.deccanherald.com/deccanherald/mar162006/update71652006316. asp Hello, The article above is good summary of what had happened so far. If you are asking for technical details, I'm not sure if there have been released any (although I only have access to online material since I don't live in greece any more). Some links to articles that summarize the testimonies of vodafone's and ericsson's CEO's to the greek pariament follow. vodafone's position: http://www.athensnews.gr/athweb/nathens.print_unique?e=Cf=13173m=A03aa=1eidos=A ericsson's: http://www.athensnews.gr/athweb/nathens.prnt_article?e=Cf=13174t=01m=A03aa=1 regards, Nikos - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Creativity and security
Olle Mulmo wrote: On Mar 20, 2006, at 21:51, [EMAIL PROTECTED] wrote: I was tearing up some old credit card receipts recently - after all these years, enough vendors continue to print full CC numbers on receipts that I'm hesitant to just toss them as is, though I doubt there are many dumpster divers looking for this stuff any more - when I found a great example of why you don't want people applying their creativity to security problems, at least not without a great deal of review. You see, most vendors these days replace all but the last 4 digits of the CC number on a receipt with X's. But it must be boring to do the same as everyone else, so some bright person at one vendor(*) decided they were going to do it differently: They X'd out *just the last four digits*. After all, who could guess the number from the 10,000 possibilities? Ahem. -- Jerry (*) It was Build-A-Bear. The receipt was at least a year old, so for all I know they've long since fixed this. Unfortunately, they haven't. In Europe I get receipts with different crossing-out patterns almost every week. And, with they I mean the builders of point-of-sale terminals: I don't think individual store owners are given a choice. Though I believe I have noticed a good trend in that I get receipts where *all but four* digits are crossed out more and more often nowadays. In the UK, that is now the almost universal practice. And it's equally almost universally the /last/ four digits across all retailers. Which is good. What is not so good, however, is another example of not-as-clever-as-it-thinks-it-is clever new idea for addressing the problem of receipts. As we all know, when you pay with a credit or debit card at a store, it's important to take the receipt with you, because it contains vital information - even when most of the card number is starred out, the expiry date is generally shown in full. So we're all encouraged to take them with us, take them home, and shred or otherwise securely dispose of them under our own control. Of course, this is a) a nuisance and b) wasteful of paper. And obviously enough, someone's been trying to come up with a 'bright idea' to solve these issues. So what they've been doing at my local branch of Marks Spencer for the past few weeks is, at the end of the transaction after the (now always chip'n'pin-based) card reader finishes authorizing your transaction, the cashier at the till asks you whether you actually /want/ the receipt or not; if you say yes, they press a little button and the till prints out the receipt same as ever and they hand it to you, but if you say no they don't press the button, the machine doesn't even bother to print a receipt, and you wander away home, safe in the knowledge that there is no wasted paper and no leak of security information ... ... Of course, three seconds after your back is turned, the cashier can still go ahead and press the button anyway, and then /they/ can have your receipt. With the expiry date on it. And the last four digits of the card number. And the name of the card issuer, which allows you to narrow the first four digits down to maybe three or four possible combinations. OK, 10^8 still aint easy, but it's a lot easier than what we started with. The risk could perhaps be fixed with an interlock which makes it impossible to print the receipt out after the card has been withdrawn from the reader, but I think the better solution would still be for the receipt to be printed out every single time and the staff trained in the importance of not letting customers leave without taking their receipts with them. cheers, DaveK -- Can't think of a witty .sigline today - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Linux RNG paper
On Thu, Mar 23, 2006 at 01:55:30AM -0600, Travis H. wrote: It's annoying that the random number generator code calls the unpredictable stuff entropy. It's unpredictability that we're concerned with, and Shannon entropy is just an upper bound on the predictability. Unpredictability cannot be measured based on outputs of sources, it must be based on models of the source and attacker themselves. But we all know that. Maybe we should invent a term? Untropy? The problem is that we have to decide what out metric is before we can give it a name. Shannon entropy is about the asympitic amount of data needed to encode an average message. Kolmorogrov's entropy (which got a mention here today) is about the shortest program that can produce this string. These things aren't often important for a PRNG or /dev/random like device. One metric might be guessability (mean number of guesses required or moments there of). As you point out, Arikan and Massey have shown that Shannon entropy are not particularly good estimates of guessability. Generalisations of entropy, like Reni entropy do seem to have meaning. The min-entropy mentioned in RFC 4086 seems reasonable, though I don't think the rational given in the RFC is actually correct. David. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
John Kelsey wrote:
As an aside, this whole discussion is confused by the fact that there
are a bunch of different domains in which entropy is defined. The
algorithmic information theory sense of entropy (how long is the
shortest program that produces this sequence?) is miles away from the
information theory sense of entropy, and even that has a bunch of
different flavors.
I would have said almost the opposite. The great power and beauty
of the entropy idea is that it has the *same* meaning across many
domains. Entropy is defined in terms of probability, period. Any
other definition is either
a) exactly equivalent,
b) an approximation, valid under this-or-that restrictive conditions, or
c) wrong.
With some slight fiddling to get the normalization right, 1/2
raised to the power of (program length) defines a probability
measure. This may not be the probability you want, but it
is a probability, and you can plug it into the entropy definition.
The problem is almost never understanding the definition of
entropy. The problem is almost always ascertaining what is
the correct probability measure applicable to the problem
at hand.
Don't get me started about universal probability measures.
That has an arcane narrow technical meaning that is verrry widely
misunderstood.
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with probability
2^{-161}.
The Shannon entropy on this distribution is 81.5 bits.
I think it is very close to 81 bits, not 81.5, but that is a minor
point that doesn't change the conclusion:
But if you
tried to sample it once to generate an 80-bit Skipjack key, half the
time, I'd guess your key on my first try.
Yeah, but if I sample it N times, with high probability I can generate
a large number of very good keys. This problem is faced by (and solved
by) any decent TRNG.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Creativity and security
On Thu, Mar 23, 2006 at 08:15:50PM -, Dave Korn wrote: So what they've been doing at my local branch of Marks Spencer for the past few weeks is, at the end of the transaction after the (now always chip'n'pin-based) card reader finishes authorizing your transaction, the cashier at the till asks you whether you actually /want/ the receipt or not; if you say yes, they press a little button and the till prints out the receipt same as ever and they hand it to you, but if you say no they don't press the button, the machine doesn't even bother to print a receipt, and you wander away home, safe in the knowledge that there is no wasted paper and no leak of security information ... ... Of course, three seconds after your back is turned, the cashier can still go ahead and press the button anyway, and then /they/ can have your receipt. With the expiry date on it. And the last four digits of the card number. And the name of the card issuer, which allows you to narrow the first four digits down to maybe three or four possible combinations. OK, 10^8 still aint easy, but it's a lot easier than what we started with. If all that information's printed on the outside of the card, then isn't this battle kind of lost the moment you hand the card to them? --b. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
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 [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
From: John Denker [EMAIL PROTECTED]
Sent: Mar 23, 2006 1:44 PM
To: John Kelsey [EMAIL PROTECTED], cryptography@metzdowd.com
Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits
of entropy)
...
With some slight fiddling to get the normalization right, 1/2
raised to the power of (program length) defines a probability
measure. This may not be the probability you want, but it
is a probability, and you can plug it into the entropy definition.
No, this isn't right for the algorithmic information theory meaning at
all. For that measure, we can intelligently discuss the entropy of a
specific random string, without reference to a probability model.
Indeed, what's the probability distribution of the sequence of bits
defined by Chaitin's Omega?
You can certainly complain that they should have used a different term
than entropy here, but you're not going to get these to be the same.
The problem is almost never understanding the definition of
entropy. The problem is almost always ascertaining what is
the correct probability measure applicable to the problem
at hand.
Well, you need to decide which of the probability distribution kinds
of entropy measures to use, and that differs in different
applications. If you use min-entropy or guessing entropy to estimate
the limits on how well some sequence of symbols will compress, you'll
get a pretty lousy answer. The same goes for using Shannon entropy to
determine whether you have collected enough entropy in your pool to
generate a 128-bit AES key.
...
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with probability
2^{-161}.
The Shannon entropy on this distribution is 81.5 bits.
I think it is very close to 81 bits, not 81.5, but that is a minor
point that doesn't change the conclusion:
But if you
tried to sample it once to generate an 80-bit Skipjack key, half the
time, I'd guess your key on my first try.
Yeah, but if I sample it N times, with high probability I can generate
a large number of very good keys. This problem is faced by (and solved
by) any decent TRNG.
Hmmm. I've seen plenty of people get this wrong. If you use Shannon
entropy as your measure, and then say when I have collected 128 bits
of Shannon entropy in my pool, I can generate a 128-bit AES key, you
will generate keys that aren't as secure as you think they are. Now,
most TRNGs seem to evade this and many other problems by designing the
hardware to give a relatively simple probability model. If your
probability model is close to uniform, then all these probability
distribution based entropy measurements converge (with a constant
difference).
In the case above, we had better specify N. If you sample it 16
times, then you have a 2^{-16} chance of still being in a weak state.
Once you get enough samples that the probability of being in the
pathological worst case is negligible (whatever that means in your
application), then you can start generating output bits. That's
probably somewhere between N=32 and N=64.
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Creativity and security
Blanking out all but the last 4 digits is foolish. The last is a checksum and the first four are determined by the merchant. This greatly reduces the possibilities for the other 8 digits. I'd rather just Bank Name or even the first 4 digits. (I know that amex use only 15, even worse.) brucee - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Linux RNG paper
From: David Malone [EMAIL PROTECTED]
Sent: Mar 23, 2006 3:43 PM
To: Travis H. [EMAIL PROTECTED]
Cc: Heyman, Michael [EMAIL PROTECTED], cryptography@metzdowd.com, [EMAIL
PROTECTED], [EMAIL PROTECTED]
Subject: Re: Linux RNG paper
...
One metric might be guessability (mean number of guesses required
or moments there of). As you point out, Arikan and Massey have
shown that Shannon entropy are not particularly good estimates of
guessability. Generalisations of entropy, like Reni entropy do seem
to have meaning. The min-entropy mentioned in RFC 4086 seems
reasonable, though I don't think the rational given in the RFC is
actually correct.
Starting clarification:
Min-entropy of a probability distribution is
-lg ( P[max] ),
minus the base-two log of the maximum probability.
The nice thing about min-entropy in the PRNG world is that it leads to
a really clean relationship between how many bits of entropy we need
to seed the PRNG, and how many bits of security (in terms of
resistance to brute force guessing attack) we can get.
Suppose I have a string S with 128 bits of min-entropy. That means
that the highest probablity guess of S has probability 2^{-128}. I
somehow hash S to derive a 128-bit key. The question to ask is, could
you guess S more cheaply than you guess the key? When the min-entropy
is 128, it can't be any cheaper to guess S than to guess the key.
That's true whether we're making one guess, two guesses, ten guesses,
or 2^{127} guesses.
To see why this is so, consider the best case for an attacker: S is a
128-bit uniform random string. Now, all possible values have the same
probability, and guessing S is exactly the same problem as guessing
the key. (I'm ignoring any bad things that happen when we hash down
to a key, but those can be important to think about in a different
context.)
Now, why is this the best case for an attacker? Because it gives the
highest probability of guessing right on the nth guess. If the
min-entropy is 128, then the highest probability symbol must have
prob. 2^{-128}. If the next highest probability symbol has lower than
2^{-128} probability, then his second guess has lower probability.
And then the next highest probability symbol is constrained in the
same way.
This makes it really easy, once you're working in min-entropy terms,
to answer questions like do I have enough entropy in this string to
initialize a PRNG based on running AES-128 in counter mode?
David.
--John Kelsey, NIST
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
I wrote: With some slight fiddling to get the normalization right, 1/2 raised to the power of (program length) defines a probability measure. This may not be the probability you want, but it is a probability, and you can plug it into the entropy definition. John Kelsey wrote: No, this isn't right for the algorithmic information theory meaning at all. OK, in a moment we will have gone through four plies of no-it-isn't yes-it-is no-it-isn't yes-it-is. Let's get serious. The axiomatic definition of a measure is -- a mapping from sets to numbers -- positive -- additive on the countable union of disjoint sets And a probability measure has the further property of being -- bounded above I have checked that -- with due attention to trivial details -- .5 ^ (program length) satisfies this definition. If you wish to renew the assertion that there is no such probability measure, please explain which of the axiomatic requirements is not met. Please be specific. For that measure, we can intelligently discuss the entropy of a specific random string, without reference to a probability model. That's like saying we can talk about three-dimensional force, velocity, and acceleration without reference to vectors. Measure theory is the tried-and-true formalism for dealing with random strings. It would be spectacularly contrary to ignore the formalism, and just plain wrong to say the formalism is inapplicable. Indeed, what's the probability distribution of the sequence of bits defined by Chaitin's Omega? Huh? Omega is so obviously a probability that usually the word probability is used in its definition. See e.g. http://mathworld.wolfram.com/ChaitinsConstant.html I suppose a masochistic nitpicker could demand to see a proof that this word is justified, but I'm not going to bother, for reasons given above. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
ECC Wit and Wisdom (Fwd)
Pithy wit and wisdom from New Zealand. lol. _Vin -Original Message- From: Peter Gutmann [EMAIL PROTECTED] Sent: Thursday, 23 March 2006 12:41 PM To: [EMAIL PROTECTED]; [EMAIL PROTECTED] Subject: RE: [Cfrg] Defining inter operable ECC keys in for IETF protocols Blumenthal, Uri [EMAIL PROTECTED] writes: I would MUCH prefer ECC - but my lawyers (yuk!) are telling me that there are licensing problems, and supposed NSA contacts don't call them back. Anybody knows anything useful about licensing of ECC GF(p), that he can share with me? Certicom have done such a good job of creating FUD about ECC legal issues that, unless you're a Certicom licensee, it's easier to not use it at all. So far every time I've been asked about ECC support (which admittedly is once a blue moon anyway), I've asked the organisation who want it to come back to me with either proof of a Certicom license or a clear statement of which non- infringing mechanisms they want me to implement. In every case, after looking at what's involved, they've decided they didn't need ECC that much anyway. It's like the conclusion from Wargames, the only way to win is not to play. Peter. ___ Cfrg mailing list [EMAIL PROTECTED] https://www1.ietf.org/mailman/listinfo/cfrg - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
This is getting pretty far afield from cryptography but it is a topic I find very interesting so I can't resist jumping in. John Denker writes: OK, in a moment we will have gone through four plies of no-it-isn't yes-it-is no-it-isn't yes-it-is. Let's get serious. The axiomatic definition of a measure is -- a mapping from sets to numbers -- positive -- additive on the countable union of disjoint sets And a probability measure has the further property of being -- bounded above I have checked that -- with due attention to trivial details -- .5 ^ (program length) satisfies this definition. If you wish to renew the assertion that there is no such probability measure, please explain which of the axiomatic requirements is not met. Please be specific. This is true, in fact it is sometimes called the universal distribution or universal measure. In more detail, it is a distribution over all finite-length strings. The measure for a particular string X is defined as the sum over all programs that output X of 1/2^L_i, where L_i is the length of each such program. Often the algorithmic complexity of a string is defined as the length of the shortest program to output the string. The universal measure is based on the same idea, but takes into consideration that there may be multiple programs that output the same string. Each program of length L_i contributes 1/2^L_i to the string's measure. If there is only one short program and all others are much longer, then the probability measure is essentially 1/2^C where C is the length of this shortest program, i.e. the algorithmic complexity. The universal measure for a string can also be thought of as the probability that, given a fixed Universal Turing Machine (UTM), a randomly chosen input program will output that string. So this is clearly a probability distribution (with some technicalities regarding issues of program lengths being glossed over here) as John Denker says. However to go from this to a notion of entropy is more questionable. There are a countably infinite number of finite strings, and all of them have non-zero probabilities under this distribution. This means that for most strings, the probability must be very low, asymptotically approaching zero. In fact you can show that for most strings of length n, their measure is 1/2^n; this is equivalent to saying that most strings are effectively random and have no shorter program to output them. Shannon entropy is defined over a probability distribution. That is, given a probability distribution we can find its Shannon entropy by summing -p_i / log2(p_i) over all members of the distribution. If we approximate the universal distribution by 1/2^n for strings of length n, this sum is clearly divergent. So there is not really a meaningful Shannon entropy for this probability distribution, or in other words the entropy is infinite. John Kelsey asked: Indeed, what's the probability distribution of the sequence of bits defined by Chaitin's Omega? This probability distribution is defined only over finite strings and so Omega is not within the universe of this distribution. It should also be noted that it is impossible for an n bit program to output more than n bits of Omega (plus or minus an additive constant specific to the UTM). Hence even if we consider successive approximations to Omega of ever increasing length, their measures would tend asymptotically to zero. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
