Cryptography-Digest Digest #261, Volume #9 Sun, 21 Mar 99 17:13:03 EST
Contents:
Re: Random Walk (R. Knauer)
Re: Requesting Opinions, Clarifications and Comments on Schneier's Statements
(Herman Rubin)
Re: Does PGP use salt when hashing passphrases?
idea ([EMAIL PROTECTED])
Re: Random Walk (R. Knauer)
Re: Newbie, what a stupid term...
Re: Requesting Opinions, Clarifications and Comments on Schneier's Statements
Re: To break 40-bit DES (Vladimir Beker)
Re: Random Walk ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sun, 21 Mar 1999 20:22:01 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 21 Mar 1999 19:44:42 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>I have to comment that one doesn't cryptanalyze random numbers!
We all know that. That is one very good reason that statistical tests
are worthless.
>One cryptanalyzes traffic generated by one or more cryptosystems.
An analysis of the "traffic" constitutes a consideration of whether
the underlying keystream is truly random or not. If it is truly
random, then there is no way to know with reasonable certainty that a
given decryption is the intended message. If the keystream is not
truly random, the cryptanalyst has clues that may lead him to a
reasonable certainty that he has decrypted the intended message.
>All this discussion of "randomness" is off-topic.
Then avail yourself of your prerogative not to read any more of these
posts. If you want to imbibe the snake oil of statistical testing, be
our guest. You will make cryptanalysts very happy indeed.
For those of us who know that randomness is at the heart of
cryptography, we shall continue the quest for an understanding of its
true meaning even in your absense.
Bob Knauer
"If you think health care is expensive now, wait until it's FREE!"
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Requesting Opinions, Clarifications and Comments on Schneier's Statements
Date: 21 Mar 1999 15:24:55 -0500
In article <7d3b18$rul$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>sb5309 <[EMAIL PROTECTED]> wrote:
>> "A one-time pad might be suitable for a few short messages, but it will
>> never work for a 1.54 Mbps communication channel".
>> Questions :
>> (b) From what I can understand from Mr. Scheier passages that, where
>> there is heavy traffic, one-time pad is not practical because it is very
>> expensice to generate and deliver message keys (and that is why one-time
>> pad is unsuitable for long messages). How does this point relate to
>> "1.54 Mbps communication channel" ?
>It becomes much clearer when you find out that "Mbps" stands for
>"million bits per second." Then we're talking about a stream of
>1.54 million bits per second every second. By my standards 1.54
>million bits is a long message. Long enough to make generating
>a pad for it highly annoying.
>The HotBits random number generator at http://www.fourmilab.ch/hotbits/
>generates 30 bytes (240 bits) of padstuff per second. Not nearly enough
>to keep up with the link, much less save enough to account for transportation
>time.
A radioactive generator can run at such speeds; using the parity of
the number of counts of a type 1 counter with an arrival rate of
.28 per dead time (yes, that fast; see my technical report) for
about 12 dead times per bit generated, can come at least close.
But there still is the problem of getting than many bits across.
The OTP does not have to get there at the same time as the message.
But how do you get it there at a comparable rate? Quantum authentication
is about the only way it could be done, and it does have the advantage
that the sender knows which bits are known to the recipient.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: comp.security.pgp.discuss
Subject: Re: Does PGP use salt when hashing passphrases?
Date: 21 Mar 99 20:19:32 GMT
Lincoln Yeoh ([EMAIL PROTECTED]) wrote:
: Heh I know I should look at the source myself, but does anyone know?
: Was wondering if using salt for hashing/encrypting passphrases be a good
: idea.
Maybe it would be for some purposes. But it isn't used by PGP, because it
couldn't be used the way it is set up.
In PGP, you want to be able to decode a key file or a conventionally
encrypted file knowing ONLY the passphrase. If salt were used to produce
the key from the passphrase, you would have to know the salt value too.
For passwords, the computer keeps both the hash and the salt, so it can
check that the two match by repeating the hash. Maybe salt would be useful
to protect a "sanity check" in an encryption program (and even PGP has
one, although that is dangerous, but it does it well enough to be
reasonably safe).
John Savard
------------------------------
From: [EMAIL PROTECTED]
Subject: idea
Date: Sun, 21 Mar 1999 19:35:24 GMT
Don't you just divide in IDEA as the inverse?
For example if your plain text p1 -> p4 = 1 -> 4, and the first 4 s-boxes are
1 -> 4. You would have
encode:
d1 = p1 * s1 = 1
d2 = p2 + s2 = 2
d3 = p3 + s3 = 6
d4 = p4 * s4 = 16
decode
p1 = d1 / s1 = 1
p2 = d2 - s2 = 2
p3 = d3 - s3 = 3
p4 = d4 / s4 = 4
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sun, 21 Mar 1999 20:43:47 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 21 Mar 1999 19:53:51 GMT, karl malbrain <[EMAIL PROTECTED]>
wrote:
>> "If you think health care is expensive now, wait until it's FREE!"
>If you'll allow me to answer from the bottom, up: You're missing the omni-
>present ASSIGNMENT of PRIORITIES from your logic. Current health care is
>prioritized for those who have PRIVATE COVERAGE -- it's directly related to
>the amount of MONEY you can spend.
If you have to get health care, you should become indigent so you will
not be make more ill just to get all of your money. Also, the best
health care is at the teaching hospitals and they are usually run by
county govt and are free if you are indigent.
The surest way to contract a major illness or get into a condition
poor health is to have lots of money from insurance. If you are not
ill before you get treatment, you sure as hell will be afterwards.
>If you'll take the same ANALOGY to the OTP distribution problem, you'll get
>the same results.
So what? What is your point - that we should not use the OTP as a
platform for discussing crypto-grade randomness? Perhaps so, because
there is another serious problem with the classical OTP, namely the
very weak mixing of plaintext and keystream. No cipher should ever be
as susceptible to a known/given plaintext attack as the OTP
ciphersystem.
But what would you propose in its place, if the purpose is to serve as
a platform for discussion of crypto-grade randomness? No matter which
platform you chose, people are going to think there is some weakness
with the platform - yet that is not the issue.
The main reason for which I use the OTP in discussions of randomness
is that it is a proveably secure system. But that is only because of
two things other than the randomness of the keypad: 1) the fact that
the keypad is used only once; 2) the fact that the keypad is the same
length as the plaintext.
Maybe the term "one time equal length truly random pad" (OTELTRP)
would be more appropriate. You decide - I don't think it really makes
any difference for those who have been following these discussions of
crypto-grade randomness.
>And again to the CAESARS -- not everyone was GIVEN the GIFT of learning to
>read in the first place. TENSOR CALCULUS was as applicable then as now.
Yes, but it was not known at that time.
Bob Knauer
"If you think health care is expensive now, wait until it's FREE!"
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Newbie, what a stupid term...
Date: 21 Mar 99 20:14:47 GMT
Brandt ([EMAIL PROTECTED]) wrote:
: Also
: where to learn the concept of Unix password encryption. I do not
: understand if there are random characters introduced, how does it
: come out the same when the server compares the resulting hash? I
: know two of the same passwords will not look the same.
This question I can answer.
What you are referring to works like this:
A user types in a new password, and the computer produces a random number
called the "salt". Then it scrambles the two items together, by a method
that doesn't have a corresponding decoding method.
For example, if you encipher a block in DES with a key, it is easy to
decipher it with that key. But given the block and the enciphered version,
it is hard to find out what the key was. So if you start with a block, and
encipher it using itself as the key, the result can't be reversed in any
known easy way to find the block.
The next time the password is typed in, the computer can check that it is
right, because in the password file the computer has kept both a copy of
the one-way-scrambled password and salt combination and a copy of the salt
value.
Hence, with the salt and the password, it just does the scrambling over
again, to see that it gets the same scrambled result as before. It doesn't
try to unscramble, because that can't be done.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Requesting Opinions, Clarifications and Comments on Schneier's Statements
Date: 21 Mar 99 20:08:27 GMT
sb5309 ([EMAIL PROTECTED]) wrote:
: (a) What One-time pad has got to do with the high-bandwidth
: communication channel, given in Mr. Schneier's opinion, that it is
: unsuitable for long messages ?
: or
: (b) From what I can understand from Mr. Scheier passages that, where
: there is heavy traffic, one-time pad is not practical because it is very
: expensice to generate and deliver message keys (and that is why one-time
: pad is unsuitable for long messages). How does this point relate to
: "1.54 Mbps communication channel" ?
Well, a communications channel with a bandwidth of 1.54 Mbps - 1,540,000
bits per second - that is in continuous use for the transmission of
messages all of which are to be encrypted, would consume an enormous
volume of key material.
"High bandwidth" is just another way of saying "long messages, very
often".
John Savard
------------------------------
Date: Sun, 21 Mar 1999 10:43:47 +0200
From: Vladimir Beker <[EMAIL PROTECTED]>
Subject: Re: To break 40-bit DES
Not exactly. Export law restricts DES to have effective key length
40-bit. That is, the key size is 56-bit (of course), but only 40 are
secret (random), the rest are zeroed of filled with other non-secret
salt data.
Vladimir
Keith Brodie wrote:
> There is no 40 bit DES - It is defined to have a 56 bit key.
>
> --
> Keith Brodie KF6QEK
> [EMAIL PROTECTED]
> Gustavo wrote in message <7criij$79j$[EMAIL PROTECTED]>...
> >Hi all,
> >It is well known that any algorithm with
> >key's variability of 40 bits can be easily
> >broken.
> >Does anyone know how long
> >does the fastest software attack to
> >40-bit DES take to find the correct key
> >(for instance on a Pentium 300)?
> >Thank you.
> >Gustavo
> >
> >
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Sun, 21 Mar 1999 22:08:49 GMT
"R. Knauer" wrote:
> For those who missed those posts, I suggest searching the Usenet
> archives for key words such as "TRNG", "crypto-graderandom", etc.
Note that those terms are not used by professional statisticians
nor practicing cryptologists, and for good reason.
> BTW, when I used the term "a priori probability" above I meant the
> probability model. Statistical tests assume a particular model against
> which to test the numbers, and the validity of those tests are based
> on the limit of large numbers - the so-called frequency interpretation
> of probability.
> But as you should know, finite sequences are notorious for failing
> such neat little tests. Putting "confidence limits" on the statisitcal
> tests, based on the assumption that the tests are being applied to
> infinite sequences, is simply a falacy of the first order. Kolmogorov
> himself made that point very clear.
Kolmogorov, generally speaking, understood statistics quite well.
Therefore I think you must be taking some point of his out of context
and misinterpreting it. *All* statistical tests are of necessity
applied to finite data sets. In the hands of a skilled statistician,
such tests *do* work, and work very well. Actual cryptanalysts use
them continually in the process of cracking real cryptosystems.
*No* statistical test is based on the frequency interpretation of
probability; perhaps your *idea* of what a test means might be
related to such an interpretation.
> For example, in the (uniform one-dimensional) random walk, the
> particle is expected to visit the origin an infinite number of times,
> thereby swamping those paths that do not visit the origin. But that
> only happens in the infinite limit, where all sorts of things happen
> that never happen in finite walks. For sequences that are finite, the
> particle rarely visits the origin.
Every finite number is "rare" compared to an infinitude.
As I pointed out in a posting a few weeks back, P�lya long ago
proved that the probability of an infinitely long random walk
returning to the origin is 1 for both the 1- and 2-dimensional
square lattices. (It's less that 1 for higher dimensions.)
> As I quoted Feller the other day, in one particular random walk of
> 10,000 steps the particle visited the origin only 87 times, which
> defies any statistical measure based on the law of large numbers you
> can come up with.
It might be surprising to some people that it returned to the origin
as *often* as that. The only way to have a valid expectation is to
compute it.. What is the expected number of zero-crossings for
10,000 steps (when P(L)=P(R)=0.5)? Unfortunately this is a tricky
combinatorial problem, but I suspect it has been performed before by
somebody, who will now chime in with the answer.
Statistical tests are not based on the law of large numbers.
For a statistical test, you need a hypothesis -- what would it be
in this case? That the probability of a step to the right equals
that of a step to the left? That's too narrow, since no matter
what is observed it could not distinguish between that hypothesis
and another wherein there is a *very slight* imbalance in the
probabilities. So what you adopt as a hypothesis would be
something like: The imbalance in P(L) and P(R) does not exceed
alpha>0 (e.g. alpha = 0.01). Then by standard methods you compute
the likelihood ratio of this hypothesis over the complementary
hypothesis, given the observed data. The log-likelihood ratio
is the amount of information present in the data supporting the
hypothesis over its complement; this is on an absolute scale and
can be combined additively with independent information from
other data. (The corresponding d.f. are also additive, in case
you want to relate it to a chi-square table to produce an overall
estimate of the confidence one has in the hypothesis.)
> Put another way, if you had applied statistical
> tests to that particular random walk, you would have rejected it as
> random - yet it was a true random walk based on the Rand Tables.
Sorry, I would have done no such thing.
> >To take one of the simplest examples of a statistical test used in
> >randomness testing, Pearson's chi-squared, no a priori probabilities
> >are involved. The test is for independence of distributions.
> >(An improved but less well-known version, based entirely on
> >information theory, was developed by Kullback. The tests approach
> >each other for large samples, but Kullback's works down to the
> >smallest sample.)
> There is an a priori assumption regarding the nature of the
> distribution inherent in such statistical tests - that assumption is
> based on the probability model that is chosen for the process being
> tested, and gains its validity only in the infinite limit.
Wrong.
> ... But nowhere is it *certain* that finite sequences must obey
> some a priori probability model and the statistical tests that result
> from it.
I don't know what you're saying and I doubt you do either --
a statistical test of this general nature is a test of a hypothesis,
which you might presume to call a model, but *that* is what is being
tested: the degree to which the data support the hypothesis/model.
Otherwise it wouldn't be a test, just a meaningless computation.
> >Such tests are never "for" randomness, but rather "against"
> >randomness. I.e. if you formulate a hypothesis about uniformity
> >of the distribution(s), the tests can cast doubt on the hypothesis,
> >if the observed data doesn't match the hypothesis very well.
> >The degree of doubt is quantified, in the ensemble sense.
> That is only true in the limit of "large numbers".
Wrong.
> How many steps in the random walk are necessary before the paths begin
> to behave the staitistics expected from some postulated ad hoc
> probabilistic model - when the strong law of large numbers starts to
> kick in a significant way?
There is no such thing as the law of large numbers "kicking in".
If a random-walk process is in fact generated in accordance with
a specific stochastic model, then there is a certain chance that
an arbitrarily chosen run of the process "passes" an appropriate
test and a complementary chance that it doesn't. If the actual
data doesn't support the model very well, then we have reason to
disbelieve the hypothesis that the data is generated according
to the model. If repeated runs continue to contribute to our
disbelief (adding information against rapdily in comaprison with
added d.f.), we may become almost certain (with a quantifiable
degree of confidence) that the data is *not* generated in
accordance with the model. Properly conducted statistical
testing of putative random number sequences *is* informative.
> If we (correctly) expect an infinite number
> of visits to the origin in the infinite limit, how many steps would
> cause that probability frequency to begin to diverge? Can you safely
> say that a random walk of 10^12 steps obeys statistical expectations,
> or would it take 10^20 steps or perhaps 10^128 steps?
Unraveling the misuse of terminology, I guess you're asking what
relevance the asymptotic behavior has in the finite case.
The answer is, very little (in some cases it establishes a limit).
But that has nothing to do with the issue of statistical testing
of observed data.
> The problem with both probabilistic models based on the law of large
> numbers is that they can only assign a probability that the process is
> modelled correctly. As Kolmogorov pointed out, that is highly circular
> reasoning.
I guess your citation of Kolmogorv dates back to when many
statisticians were still arguing about the foundations of
probability theory. In fact, probability theory does not depend
on any law of large numbers nor frequency interpretation,
although those do have their uses. Testing whether a model
is "correct" (more accurately, how well it fits the observed
phenomena) is entirely reasonable and is a large part of science.
. And that probability of confidence tells you nothing about
> the behavior of the process for finite sequences. All it tells you is
> that in the infinite limit things will happen that way - that is, the
> assigned probability has validity only in the limit of infinite
> sequences.
Completely wrong. Strictly speaking, probabilities apply a priori
to only a single experiment, after which one has additional
information that should be used to adjust one's assessment of the
probabilities.
Same thing in elementary game theory, which despite appearance
(use of probability measures) strictly applies only to a single
iteration of the game.
> Such a statement is nevertheless true - and maybe professional
> statiticians need to be insulted, judging from the fact that they
> didn't get the random walk axis crossing problem anywhere near correct
> when Feller conducted his survey.
I think that was back in the Fisher-dominated era.
Anyway, it was a stupid experiment in that (apparently) the subjects
were required to make wild impromptu guesses rather than work out the
right expectations.
If you pulled the same sort of experiment on any professional class,
you'd very likely get poor guesses from them too.
> All three works give numerous examples of how finite random numbers
> disobey statistical models.
That's not even a meaningful thing to say -- if the numbers are in
fact generated in accordance with some model, then how do they
"disobey" that model?
> ... Remember that I am quoting the comments of the experts - I
> am not relying on any expertise on my part.
That's too bad, because if you bothered to gain the expertise
you would presumably better understand these issues.
> Was von Neumann full of BS when he made his famous pronouncements
> about the futility of attemtping to generate random numbers
> algorithmically? If so, then what makes you think that a given random
> number can be characterized by an algorithmic procedure such as a
> statisitcal test?
What makes you think that I said "that a given random number can be
characterized by an algorithmic procedure such as a statistical test"?
You were (incorrectly) claiming that statistical tests could not be
meaningfully applied to finite "random number" sequences, and I was
disputing that claim. There is no "characterizing" going on.
> If you could characterize random numbers by an algorithmic procedure
> like statistical testing, then you could use that very algorithmic
> procedure to generate random numbers - which would violate what anyone
> with any experience in crypto knows is not the case.
Since it's a moot point anyway, I won't bother to respond to the
additional errors in that argument.
> Just how do you propose to remove this bias? And when you do, how do
> you know it results in crypto-grade randomness? After all, if the
> proposed method of removing bias is algorithmic then you run the risk
> that its operation will destroy any true randomness that was present
> before the operation was performed.
Only if one doesn't know what he is doing.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
