Cryptography-Digest Digest #254, Volume #9 Fri, 19 Mar 99 17:13:02 EST
Contents:
What is MAC ? -2nd ("ZinHa")
Re: DIE HARD and Crypto Grade RNGs. (Patrick Juola)
PGP Protocol question (Jeffrey Haas)
Re: To break 40-bit DES (Thomas Pornin)
Re: To break 40-bit DES ([EMAIL PROTECTED])
Test Vectors (Dominik Werder)
Random Walk (R. Knauer)
a little math please ([EMAIL PROTECTED])
Re: a little math please (Jon Haugsand)
Re: What is MAC ? -2nd (Medical Electronics Lab)
Re: a little math please (Paul Rubin)
Re: Random Walk ("Tony T. Warnock")
Re: Random Walk (R. Knauer)
Re: a little math please ([EMAIL PROTECTED])
Re: Random Walk ("hapticz")
Re: a little math please ([EMAIL PROTECTED])
Re: One-Time-Pad program for Win85/98 or DOS (Jim Dunnett)
Re: Random Walk ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "ZinHa" <[EMAIL PROTECTED]>
Subject: What is MAC ? -2nd
Date: Fri, 19 Mar 1999 22:07:14 +0900
Really thanks.. but I still can't solve my problem.
Of course, I didn't know about Message Auth. Code.
I think it is not that I have to get.
I read the MAC in smart card site.
It is for higt speed modulation(?) and operation.
It makes processing de/crypt speed.
what is that? -.-;;
I want advices......
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: DIE HARD and Crypto Grade RNGs.
Date: 19 Mar 1999 08:53:45 -0500
In article <7cr7s5$881$[EMAIL PROTECTED]>,
Coen Visser <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Patrick Juola) writes:
>
>>Secondly, we *can* measure Kolmogorov complexity to arbitrary degrees
>>of precision for some types of strings.
>
>Could you explain this. I thought that the Kolmogorov complexity
>was semi-computable, you can approximate it only from above. So you
>will never know how close you are. This is something different than
>"measuring to an arbitrary degree".
The same way that we know that some progams will halt, despite the
formal undecidability of the halting problem. If you have a string
of a specified form -- for various different specifications, of course --
then the specific case of that string or that *class* of strings
may be exactly solvable.
It's easy enough for me to prove that a single-function assembly
language program with only forward branches will halt. This doesn't
mean that I've solved the halting problem, but it does mean that *IF*
my problem of interest can be expressed as such a program, I can
prove something of interest.
-kitten
------------------------------
From: Jeffrey Haas <[EMAIL PROTECTED]>
Subject: PGP Protocol question
Date: 17 Mar 1999 17:19:19 GMT
This question has more to do with methodology than algorithms.
To the best of my understanding, when encrypting a given plaintext
in PGP for multiple recipients, PGP does the following:
[many steps elided]
Creates a session key
Encrypts the plaintext with the session key (classical encryption).
Encrypts the session key with the public key of each recipient.
Creates a message that has all of the above in it.
Here's what I'm considering:
If you have mail list software, and you want to send to hundreds
of recipients their messages to each other encrypted using PGP
it is computationally expensive to individually encrypt the same
plaintext with different session keys.
To spread the load, the plaintext could be encrypted with
the same session key and the session key could, in a distributed
fashion, be encrypted with each of the subscriber's public keys.
The maillist software could then assemble a valid PGP message
for each subscriber from the above components.
Ignoring the security of the list software's secret key and
the security of the end-user's private keys (you have to trust
people to keep their own secret's secure, and thats usually a bad
assumption), what are the problems with the above scenario?
If this is a case of RTFM, please point out the particular TFM. :-)
If my understanding of how PGP normally does this is flawed,
all of the above is, of course, balderdash. Additionally, I may
be over-estimating the relative cost of encrypting individual
plaintexts with different session keys versus the cost of encrypting
the session key. (Assume IDEA and RSA, e.g.)
(I am not a cryptographer, nor do I play one on TV. I'm just
looking for a way to solve a particular problem.)
--
Jeffrey Haas
[EMAIL PROTECTED] "Place all beliefs in proper receptacle"
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: To break 40-bit DES
Date: 19 Mar 1999 15:34:01 GMT
According to <[EMAIL PROTECTED]>:
> BTW, you can use DES with a 40-bit key, if you expand it with zeros.
There is also a thing called CDMF which is a DES, with a key
pre-scheduling, which is in fact some hash (unsing two fixed-key DES)
where the datum is reduced to 40 bits in the middle of the hash, thus
giving only 2^40 really different keys.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: To break 40-bit DES
Date: Fri, 19 Mar 1999 14:58:35 GMT
> > 40-bit key, if you expand it with zeros. (but why?)
>
> One reason for that might be if you want to export it from USA :-)) Like, for
> example, exported versions of SSL.
Good example, bad idea.
Thanks for the info,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Dominik Werder)
Subject: Test Vectors
Date: Fri, 19 Mar 1999 16:50:57 GMT
Hello!
Is there a test vector libary on the web for the most common
algorithms? espacially for IDEA, RC4, SHA(-1), ...
thank you!
DoMiNik
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Random Walk
Date: Fri, 19 Mar 1999 18:04:37 GMT
Reply-To: [EMAIL PROTECTED]
For all of those who worship at the altar of statistical testing to
demonstrate the strength of keystreams for cryptography, I recommend
you read the book entitled "An Introduction to Probability Theory and
Its Applications" by William Feller. It is a two volume set and you
must get the 3rd edition if you request it from the library.
This book was heavily cited in Li & Vitanyi's book on Kolmogorov
Complexity, and can be considered a companion work. The reason I bring
it up here is that it demonstrates the utter futility of using
statistical tests to characterize cryptographically strong ciphers.
You can skip to Chapter III for the discussion of the uniform random
walk in one dimension, which is based on the uniform Bernoulli
process, viz., the so-called "Fair Coin Toss". As everyone knows, this
is used as the operative model for analyzing the behavior of
randomness in crypto and other applications.
To stimulate discussions in this thread I quote some of the comments
Feller makes about the counter-intuitive facts that emerge from a
rigorous mathematical analysis of the random walk (from now on, the
term "random walk" in this context refers to a uniform one-dimensional
random walk). In fact, both volumes of Feller's book are an exposition
of the almost paradoxical statistical properties of this process.
>From p. 81, regarding the Arc Sine Law:
"We saw that, contrary to popular notions, it is quite likely that in
a long coin-tossing game one of the players remains practically the
whole game on the winning side, the other on the losing side. The next
theorem elucidates the same phenomenon by an analysis of the fraction
of the total time that the particle spends on the positive side. One
feels intuitively that this fraction is most likely to be close to
1/2, but the opposite is true: The possible values close to 1/2 sre
least probable, whereas the extremes k = 0 and k = n have the greatest
probability."
>From p. 88, regarding axis crossing:
"Sampling of expert opinion revealed that even trained statisticians
expect much more than 78 changes in sign [axis crossing] in 10,000
trials, and nobody counted on the possibility of only 8 changes of
sign. Actually the probability of not more than 8 changes of sign
exceeds 0.14, whereas the probability of more than 78 changes of sign
is about 0.12. As far as the number of changes in sign is concerned
the two records stand on a par and, theoretically, neither should
cause surprise. If they seem startling, this is due to our faulty
intuition and to having been exposed to too many vague references to a
mysterious 'law of averages'."
>From p. 94, maximal accumulated gain:
"Contrary to intuition the maximal accumulated gain is much more
likely to occur towards the very beginning or the very end of a
coin-tossing game than somewhere in the middle."
So, there you have it - not only do statistical tests fail in general
for true random number generation processes, such as the uniform
one-dimensional random walk, which is based on a uniform Bernoulli
process, but they pass processes that are not even crypto-grade
random, such as the digit expansion of pi.
Such statistical tests are based on some vague "law of averages",
which is correct only in the limit of infinitely long sequences. It is
not obeyed, even probabilitically, for sequences of finite length.
IOW, such a "law of averages" fails miserably for even very long, but
finite, sequences generated by a random walk.
I remind you of Feller's comment above: "If they [the failure of
statistical measures of randomness for finite sequences] seems
startling, this is due to our faulty intuition and to having been
exposed to too many vague references to a mysterious 'law of
averages'."
IOW, statistical testing is the essence of Snake Oil in crypto - and
only the most naive rely on them, to the delight of cryptanalysts.
Bob Knauer
"Every government always exercises the maximum amount of power its
rulers feel the people will stand for without revolting."
-- Alongside Night
------------------------------
From: [EMAIL PROTECTED]
Subject: a little math please
Date: Fri, 19 Mar 1999 17:55:29 GMT
What I would like to know, given a grid of 16x16, filled with an even number
of 0 and 1 bits, how many combinations are there?
Not 2^256, because remember that they have to be even.
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Jon Haugsand <[EMAIL PROTECTED]>
Subject: Re: a little math please
Date: 19 Mar 1999 19:16:24 +0100
* [EMAIL PROTECTED]
> What I would like to know, given a grid of 16x16, filled with an even number
> of 0 and 1 bits, how many combinations are there?
>
> Not 2^256, because remember that they have to be even.
If I understand your question correctly it has to be 2^255.
To see this, remove one square, fill the remaining 255 squares as you
wish. No there are even 0 bits and odd 1 bits _or_ odd 0 bits and even
1 bits. Fill the last square so that your restriction is satisfied.
--
Jon Haugsand
Norsk Regnesentral, <mailto:[EMAIL PROTECTED]> <http://www.nr.no/>
Tlf: 22852608/22852500, Fax: 22697660, Pb 114 Blindern, 0314 OSLO
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: What is MAC ? -2nd
Date: Fri, 19 Mar 1999 12:16:51 -0600
ZinHa wrote:
>
> Really thanks.. but I still can't solve my problem.
> Of course, I didn't know about Message Auth. Code.
> I think it is not that I have to get.
> I read the MAC in smart card site.
> It is for higt speed modulation(?) and operation.
> It makes processing de/crypt speed.
> what is that? -.-;;
>
> I want advices......
In DSP circles a mac == multiply-accumulate in single cycle.
So you can perform the operation y = a*x + b in one step. That
might help compute a MAC (= message auth. code) or other
crypto algorithms. Can you pull out the paragraph that mentions
it and tell from the context if it refers to the processor
abilities or to the operations it performs.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: a little math please
Date: Fri, 19 Mar 1999 18:22:16 GMT
In article <7cu326$ami$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>What I would like to know, given a grid of 16x16, filled with an even number
>of 0 and 1 bits, how many combinations are there?
>
>Not 2^256, because remember that they have to be even.
Try 2^255... half the combinations are even, the other half odd. ;-)
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Fri, 19 Mar 1999 11:59:36 -0700
Reply-To: [EMAIL PROTECTED]
"R. Knauer" wrote:
> For all of those who worship at the altar of statistical testing to
> demonstrate the strength of keystreams for cryptography, I recommend
> you read the book entitled "An Introduction to Probability Theory and
> Its Applications" by William Feller. It is a two volume set and you
> must get the 3rd edition if you request it from the library.
>
> This book was heavily cited in Li & Vitanyi's book on Kolmogorov
> Complexity, and can be considered a companion work. The reason I bring
> it up here is that it demonstrates the utter futility of using
> statistical tests to characterize cryptographically strong ciphers.
>
>
> From p. 81, regarding the Arc Sine Law:
>
> "From p. 88, regarding axis crossing:
>
> From p. 94, maximal accumulated gain:
>
> So, there you have it - not only do statistical tests fail in general
> for true random number generation processes, such as the uniform
> one-dimensional random walk, which is based on a uniform Bernoulli
> process, but they pass processes that are not even crypto-grade
> random, such as the digit expansion of pi.
>
> Such statistical tests are based on some vague "law of averages",
> which is correct only in the limit of infinitely long sequences. It is
> not obeyed, even probabilitically, for sequences of finite length.
> IOW, such a "law of averages" fails miserably for even very long, but
> finite, sequences generated by a random walk.
>
> I remind you of Feller's comment above: "If they [the failure of
> statistical measures of randomness for finite sequences] seems
> startling, this is due to our faulty intuition and to having been
> exposed to too many vague references to a mysterious 'law of
> averages'."
>
> IOW, statistical testing is the essence of Snake Oil in crypto - and
> only the most naive rely on them, to the delight of cryptanalysts.
>
The failure of naive intuition has little to do with the validity of
statistical tests. The arcsine law is a statistical test in itself. What
is of interest is that in a bernoulli sequence, the properties of an
ensemble of steps (for example 100 walks of lenght 10000) is not the same
as that of a single long walk (for example of 1000000.) The random walk
has infinite memory. It remembers everything that has gone before. If the
first step corresponds to a 1, then the rest of the walk can be thought of
as a walk starting at 1, etc. It's amusing to simlulate such a walk on a
one-dimensional grid with eight steps (1,8 are absorbing) The walk seems
to spend all of its time between steps 4 and 5.
Tony
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Fri, 19 Mar 1999 19:55:21 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 19 Mar 1999 11:59:36 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>The failure of naive intuition has little to do with the validity of
>statistical tests. The arcsine law is a statistical test in itself.
Authors like Li & Vitanyi, and Feller, make an important distinction
between statistics and probability.
Statistical tests gain their validity from the law of large numbers,
and they are not valid in general for finite sequences. The fact that
statistical measures are violated for finite sequences in general is
the point that the above referenced authors are attempting to
communicate. That is why the arc sine law is not considered a
statistical measure in the usual sense of statistics, because it
addresses the properties of finite sequences.
The standard argument to circumvent that problem is to attach
probabilistic measures to statistical tests, and rely on the 'law of
averages' to "smooth things out". But even that does not work
properly, even for very large but finite sequences, as can bee seen by
reading Feller's book.
For example, in the limit of infinite sequences all random walk paths
arrive back at the origin, so there has to have been many axis
crossings leading up to that. Yet for large but finite sequences, that
is not the case - which defies not only statistical measures but also
intuition based on the underlying 'law of averages'.
As Feller comments, most of the paths in the random walk are nothing
like what you would expect from statistical measures. He, like Li &
Vitanyi, even state that most of those sequences are "bizarre" and
"abnormal". IOW, sequences that obey statistical measures are rare
(except in the infinite limit).
Even though all paths return to the origin in the infinite limit does
not mean that they do so many times on the approach to infinity. In
fact, exactly the opposite happens - which is the essence of the arc
sine law.
Using statistical tests, even those doctored with probabilistic
notions such as "confidence levels", to characterize randomness in
crypto constitutes snake oil of the first order. But don't take my
word for it - read Feller's book.
Bob Knauer
"Every government always exercises the maximum amount of power its
rulers feel the people will stand for without revolting."
-- Alongside Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Fri, 19 Mar 1999 20:34:16 GMT
[EMAIL PROTECTED] wrote:
> What I would like to know, given a grid of 16x16, filled with an even number
> of 0 and 1 bits, how many combinations are there?
Sigh. One of the problems with dejanews is that I can't immediately nuke
an erroneous message. In my 2^128 answer, I obviously divided the wrong
number by 2. The correct answer is 2^256/2 == 2^255.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Fri, 19 Mar 1999 15:44:36 -0500
bXkgc2VudGltZW50cyBhZ3JlZSwgaWYgaXQgd2VyZSBub3QgZm9yIGJpYXNlZCByZXN1bHRzIGlu
IHRoaXMgcGl0aWZ1bCB1bml2ZXJzZSwgd2Ugd291bGQgYWxsIHN0aWxsIGJlIGV4cGFuZGluZyBl
dmVubHkgYXMgYSBtYXNzaXZlIGdhc2VvdXMgY2xvdWQgb2YgZGVicmlzLiANCg0KdW5mb3J0dW5h
dGVseSB0aGVyZSBpcyBpbmhlcmVudCBiaWFzIGRlc3BpdGUgb3VyIHdpbGRlc3QgZHJlYW1zIG9m
IHVuZGVyc3RhbmRpbmcgd2hhdCBpdCBhbGwgbWVhbnMuDQoNCi0tIA0KYmVzdCByZWdhcmRzDQpo
YXB0aWN6QGVtYWlsLm1zbi5jb20NCg0KDQo=
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Fri, 19 Mar 1999 19:41:49 GMT
[EMAIL PROTECTED] wrote:
> What I would like to know, given a grid of 16x16, filled with an even number
> of 0 and 1 bits, how many combinations are there?
2^128, because half of the patterns will have even parity and half will
have odd.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Crossposted-To: alt.security,alt.privacy
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Date: Fri, 19 Mar 1999 21:33:13 GMT
Reply-To: Jim Dunnett
On Thu, 18 Mar 1999 20:50:14 GMT, [EMAIL PROTECTED] (R.
Knauer) wrote:
>On Thu, 18 Mar 1999 20:40:25 GMT, [EMAIL PROTECTED] (Jim
>Dunnett) wrote:
>
>>>>Is that possible? Given a large block of data you're bound to be
>>>>able to predict the next number quite a few times.
>
>>>Please tell us how you are able to do that.
>
>>Law of averages I suppose. In a million or so bytes it would
>>be easy to predict, i.e. guess the next byte more than just
>>a few times.
>
>It is true that a given sequence that you guess will occur sometime in
>a long enough string - but the problem is that you don't know where it
>will happen, so your guess is ineffective.
I know! Hehe. It was something of a leg-pull.
>
>Anyway guessing does not count for the OTP system. Do you know why?
No. But with OTP systems, the bytes only need to be sufficiently
random, not 100% random.
--
Regards, Jim. | Der Staat wird nicht 'abgeschaft',
olympus%jimdee.prestel.co.uk | er stirbt ab.
dynastic%cwcom.net |
nordland%aol.com | - Friedrich Engels, 1820-1895.
marula%zdnetmail.com |
Pgp key: pgpkeys.mit.edu:11371
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random Walk
Date: Fri, 19 Mar 1999 21:34:29 GMT
<snip>
Pretty deep stuff man. Too bad I don't understand half of it. Seems like
something I should look into later (say when I finish high school..)
Tom :)
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
