Cryptography-Digest Digest #792, Volume #8 Wed, 23 Dec 98 18:13:02 EST
Contents:
Re: What is Randomness? (Dr. Yongge Wang)
Re: What is Randomness? (Frank Gifford)
Re: Cryptography FAQ (01/10: Overview) (John Savard)
Re: What is Randomness? (Dr. Yongge Wang)
Re: Cryptography FAQ (01/10: Overview) (John Savard)
Re: RC4 in 8-bit vs 16-bit (Paul Crowley)
Re: What is Randomness? (R. Knauer)
Re: On living with the 56-bit key length restriction (John Curtis)
Re: What is Randomness? ("John Feth")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Dr. Yongge Wang)
Subject: Re: What is Randomness?
Date: 23 Dec 1998 18:09:08 GMT
R. Knauer ([EMAIL PROTECTED]) wrote:
: On 23 Dec 1998 04:24:53 GMT, [EMAIL PROTECTED] (Dr. Yongge Wang) wrote:
: >Not exactly!!!!!!! generally, when people in this area speak
: >of Chaitin complexity, they refer to "prefix-free" Kolmogorov
: >complexiy. But in Kolmogorov complexity, we do not consider
: >the prefix-free property (or monotone property or
: >self-delimiting Turing machine).
: Then Chaitin needs to update his papers, because he makes no such
: distinction. But is that really crucial to an understanding of
: algorithmic complexity for purposes of randomness in crypto?
For crypto use, there may (or may not) be differences.
i
But for a mathematical analysis, the difference is crucial.
I think Solovay (when he visited IBM in 1971?) has a manuscript
(many people refer to this manusciript, but it has never
been published---120 pages) which has a detailed
study of the differences bewteen them for finite strings,
the notation for them
are K and H , thant K(x) is the Kolmogorov complexity,
and H(x) is the algorithmic complexity of Chaitin.
Also, if you use K(x), you can never get an equivalent
definition for Martin-Loef randomness of infinite strings.
(Note that Martin-Loef randomness --in: Information and Control 1966--
is still considered as the standard definition for
infinite strings by almost all researchers)
: Anyway the issue was about finite versus infinite random sequences,
: and it was my understanding that Chaitin's definition of randomness
: based on algorithmic complexity did not require infinitely sequences.
: >For other definitions of randomenss and \Omega numbers,
: >you may find more details in my PhD thesis in my homepage
: >(address below).
: I would if it were in a conventional format Windows PC format.
I am sorry, there is no Word format, it is only in
PostScript and PDF version.
: BTW, I have another thought about this method of determining
: randomness that I plan to post as a followup to this thread.
: Bob Knauer
: "Laws to suppress tend to strengthen what they would prohibit.
: This is the fine point on which all the legal professions of
: history have based their job security."
: --Frank Herbert
--
======================================================.
Yongge Wang | |
Dept. of EE & CS | |
Univ. of Wisconsin--Milwaukee | |
P.O.Box 784 |Yongge Wang |
Milwaukee, WI 53201 |2545 N.Frederick Ave. |
|Apt. 104 |
Tel: (414)229-5731 |Milwaukee, WI 53211 |
Fax: (414)229-2769 | |
[EMAIL PROTECTED] |Tel: (414)3324794 |
http://www.cs.uwm.edu/~wang |Fax: (414)3324794 |
======================================================'
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: What is Randomness?
Date: 23 Dec 1998 14:59:29 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>
>This just reinforces our belief that the only random sequence for
>crypto purposes is one produced by a TRNG. Any algorithmic procedure,
>even one which results in a sequence that passes Chatin's test for
>algorithmic complexity, is not good enough for crypto, no matter how
>sexy the underlying theory.
For a OTP, yes. But for everything else, no. RC4 is a stream cipher
which creates a stream of bytes used to encrypt the message. The bytes
are created from a completely deterministic process. And when used
correctly, RC4 appears to be a fairly good cipher. ["used correctly"
here means tossing out the first 256 generated values or so and not
re-using a stream. Alternatively, it means using a method like CipherSaber
which adds a random byte stream to the key before encryption.]
-Giff
--
[EMAIL PROTECTED] Too busy for a .sig
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cryptography FAQ (01/10: Overview)
Date: Wed, 23 Dec 1998 21:30:00 GMT
[EMAIL PROTECTED] (Bruce Schneier) wrote, in part:
>It seems reasonable to update it. Is there a cabal in charge of the
>FAQ, or has it been orphaned? Is anyone interested in working on an
>update?
I remember seeing one point in it - about 'can you encrypt software on
a CD-ROM', that I thought could be improved.
I'd be willing to try to maintain it, if the copyright holders are
willing.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (Dr. Yongge Wang)
Subject: Re: What is Randomness?
Date: 23 Dec 1998 18:26:50 GMT
Perhaps I have a wrong understanding of your idea.
But I think Chaitin complexity may have not direct application
in crypto. Also note that the Chaitin complexity of a string
is defined as the length of the shortest ciphertext which
can be fed to the Universal Turing machine to produce the
string. (O.K., here we may have the crucial difference of
Chaitin complexity and Kolmogorov complexity, for Kolmogorov
complexity, two different plain texts may have same
ciphertext. but for Chaitin complexity, different
plaintext have different ciphertext).
So if the adversary has the Universal Turing machine
also, he can find the plaintext directly by an enumeration
of all the plaintext. Of course, the problem for
Universal Turing is undecidable.
R. Knauer ([EMAIL PROTECTED]) wrote:
: On 23 Dec 1998 04:24:53 GMT, [EMAIL PROTECTED] (Dr. Yongge Wang) wrote:
: Picking up from below it seems that Chaitin's definition of randomness
: does no good for purposes of crypto. Consider the following procedure.
: Begin with a plaintext and compress it using the best compression
: procedure available. Call this sequence CP for Compressed Plaintext.
: The assumption is that CP is the minimal representation for the
: original plaintext based on compression.
: Now employ algorithmic complexity by finding the minimal algorithm
: that will reproduce CP. But that algorithm is just:
: print (CP)
: because there is no other algorithm that can reduce CP to a smaller
: size.
: Therefore CP is a random ciphertext which cannot be deciphered based
: on any discernable pattern, since it is "random" according to
: algorithmic complexity - that is the algorthm that porduces it cannot
: be made substantially smaller.
: IOW whatever algorithm that is employed to reproduce the sequence must
: conain the literal sequence without any reduction in size, since it is
: already as small as it can get by prior compression (se Chaitin). So
: the cryptanalyst faces an impossible task since there is no pattern
: for him to use to decipher the message.
: But we know better - the cipher can be broken by decompressing it.
: Therefore it would seem that randomness, based on algorithmic
: complexity, is not a suitable measure of crypto strength.
: Please restrict the discussion to conventional English so
: non-academics like me can follow it. Thanks.
: Bob Knauer
: >R. Knauer ([EMAIL PROTECTED]) wrote:
: >: One of the definitions of randomness given by Chaitin is based on
: >: algorithmic complexity for finite sequences. You may be thinking of
: >: another paper in which he discusses his "halting probability", Omega,
: >: which is an infinite sequence. But then that latter discussion is
: >: about undecideability rather than just randomness itself.
: >: In the former paper he defines randomness as a level of algorithmic
: >: complexity that is nearly the same as the size of the number under
: >: consideration. He works out the probability that a number of size N is
: >: more complex than N-10 and comes up with 0.999. He then takes that as
: >: the working definition of randomness.
: >: For those who may not be aware what algorithmic complexity is, it is
: >: the same essentially as Kolmogorov complexity, namely the size of the
: >: smallest algorithm which will output the number under consideration.
: >Not exactly!!!!!!! generally, when people in this area speak
: >of Chaitin complexity, they refer to "prefix-free" Kolmogorov
: >complexiy. But in Kolmogorov complexity, we do not consider
: >the prefix-free property (or monotone property or
: >slef-delimiting Turing machine).
: >For other definitions of randomenss and \Omega numbers,
: >you may find more details in my PhD thesis in my homepage
: >(address below).
: >: Randomness in that sense is a lack of irreducibility, since a random
: >: number cannot be output by an algorithm unless it contains the number
: >: in entirety.
: >: See http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
: >: Bob Knauer
: >
: >: "In the general course of human nature, a power over a man's
: >: subsistence amounts to a power over his will."
: >: --Alexander Hamilton
: >
: >
: >--
: >
: >------------------------------------------------------.
: >Yongge Wang | |
: >Dept. of EE & CS | |
: >Univ. of Wisconsin--Milwaukee | |
: >P.O.Box 784 |Yongge Wang |
: >Milwaukee, WI 53201 |2545 N.Frederick Ave. |
: > |Apt. 104 |
: >Tel: (414)229-5731 |Milwaukee, WI 53211 |
: >Fax: (414)229-2769 | |
: >[EMAIL PROTECTED] |Tel: (414)3324794 |
: >http://www.cs.uwm.edu/~wang |Fax: (414)3324794 |
: >------------------------------------------------------'
: "Laws to suppress tend to strengthen what they would prohibit.
: This is the fine point on which all the legal professions of
: history have based their job security."
: --Frank Herbert
--
======================================================.
Yongge Wang | |
Dept. of EE & CS | |
Univ. of Wisconsin--Milwaukee | |
P.O.Box 784 |Yongge Wang |
Milwaukee, WI 53201 |2545 N.Frederick Ave. |
|Apt. 104 |
Tel: (414)229-5731 |Milwaukee, WI 53211 |
Fax: (414)229-2769 | |
[EMAIL PROTECTED] |Tel: (414)3324794 |
http://www.cs.uwm.edu/~wang |Fax: (414)3324794 |
======================================================'
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cryptography FAQ (01/10: Overview)
Date: Wed, 23 Dec 1998 21:42:48 GMT
[EMAIL PROTECTED] (Bruce Schneier) wrote, in part:
>This FAQ is over four years old.
>It seems reasonable to update it. Is there a cabal in charge of the
>FAQ, or has it been orphaned? Is anyone interested in working on an
>update?
It occurs to me that since "[EMAIL PROTECTED]" is not only
identified in the text of the FAQ as the E-mail address of its editor,
to whom comments should be directed, but it is _also_ the E-mail
address by which the FAQ is posted, it can't have been *truly*
abandoned.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: RC4 in 8-bit vs 16-bit
Date: 23 Dec 1998 09:50:51 -0000
fungus <[EMAIL PROTECTED]> writes:
> Seriously though, the best known attack on RC4 is a brute force
> attack for the entire keyspace.
Not strictly so. The keyspace has 2^2048 members, but it's used to
initialise a permutation of the 256 bytes; you can ignore the key and
search all the permutations for, uh, just under 2^1684 effort.
Probably a more efficient algorithm would be to use a permutation with
all entries marked as "UNKNOWN", and use a recursive backtracking
algorithm to try every available possibility every time you encounter
an unknown quantity; this means that you can discard huge portions of
the keyspace as soon as you get a mismatch on the output. I don't
immediately know how to estimate the effort required for this
algorithm to run, but it's bound to be somewhat less than 2^1684
effort. Of course, I'm pretty sure it's far more than 2^256.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is Randomness?
Date: Wed, 23 Dec 1998 19:35:41 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 23 Dec 1998 16:14:05 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>But such high theories don't allow a practical implementation of any
>algorithm to actually test the 'randomness' of given sequences.
>Or do I miss something?
Chaitin maintains that there is no way to decide the randomness of a
sequence. It's part of the halting problem and incompleteness problem.
But that is not the point. Chaitin relates randomness to algorithmic
complexity and the minimal program that will reproduce the sequence.
It would seem at first glance that if the sequence is random by that
measure of algorithmic complexity, then it can be used for crypto
purposes. But there are seemingly random sequences that meet this
criterion for randomness yet are completely unsuitable for crypto
purposes.
I will try again to restate the argument I gave earlier. I start with
a thorough reading of Chaitin's works posted at:
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
Without having read his works it will be impossible to follow this
argument.
Pay special attention to the ones which discuss randomness and its
relationship to algorithmic complexity. In particular pay attention to
where he states that randomness is related to the property that a
sequence cannot be reproduced except by an algorithm of the same order
of complexity as the length of the sequence itself. And especially
note his conclusion that random sequences are produced by minimal
algorithms, that is algorithms that cannot be reduced in complexity
any further.
Then conisder a plaintext that has been compressed by the most
efficient compression algorithm known. Call that sequence CP for
"Compressed Plaintext". Now find the minimal algorithm that will
reproduce it. That algorithm must of necessity be of the same order of
complexity as the length of CP, since by assumption CP cannot be
compressed any further.
Therefore CP is a random sequence according to Chaitin's algorithmic
complexity criterion, and there is no pattern that a cryptanalyist can
discern from it that will permit him to decipher it analytically - it
leaks no information, being random in the sense of algorithmic
complexity.
But we know that it can be deciphered easily - just decompress it.
Therefore Chaitin's algorithmic complexity is useless for deciding
randomness for purposes of cryptography.
This just reinforces our belief that the only random sequence for
crypto purposes is one produced by a TRNG. Any algorithmic procedure,
even one which results in a sequence that passes Chatin's test for
algorithmic complexity, is not good enough for crypto, no matter how
sexy the underlying theory.
Bob Knauer
"Laws to suppress tend to strengthen what they would prohibit.
This is the fine point on which all the legal professions of
history have based their job security."
--Frank Herbert
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Crossposted-To: talk.politics.crypto
Subject: Re: On living with the 56-bit key length restriction
Date: 23 Dec 1998 22:18:32 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED]
(wtshaw) writes:
>
>It is becoming increasingly useless to try to be law abiding if laws are
>silly, contradictory, and perhaps, even unknown or ill-defined; this is
>what really undermines respect for the law. People come to not bother
>what it says any more; and, the cause for such an attitute is government's
>trivialization of its own power. Saying is it the law is insufficient for
>a majority of people these days, that is evident in recent headline
>events.
Moral people will distinquish between "malum per se" and
"malum prohibitum" (excuse the bad spelling).
Should silly or serious infringements on freedom be
promulgated as bad law, this really goes well beyond
any moral dictates.
If you want freedom, exercise it.
ciao,
jcurtis
------------------------------
From: "John Feth" <[EMAIL PROTECTED]>
Subject: Re: What is Randomness?
Date: 23 Dec 1998 22:25:16 GMT
Dr. Yongge Wang <[EMAIL PROTECTED]> wrote in article
<75rbk4$uuv$[EMAIL PROTECTED]>...
> R. Knauer ([EMAIL PROTECTED]) wrote:
> : On 23 Dec 1998 04:24:53 GMT, [EMAIL PROTECTED] (Dr. Yongge Wang) wrote:
>
> : >Not exactly!!!!!!! generally, when people in this area speak
> : >of Chaitin complexity, they refer to "prefix-free" Kolmogorov
> : >complexiy. But in Kolmogorov complexity, we do not consider
> : >the prefix-free property (or monotone property or
> : >self-delimiting Turing machine).
>
Snip
A useful and much less esoteric (read less intimidating) approach is to
create an Allan Variance plot of the set of numbers under consideration.
The Allan Variance is found for a set of n numbers (say the first thousand
digits of pi) simply by calculating the variance of all the individual
digits, the variance of the averages of the sums of contiguous pairs, the
variance of the averages of the sums of contiguous triplets,...and so on
all the way up to the variance of the averages of the first n/2 digits and
the last n/2 digits.
Then plot n (x-axis) vs variance (y-axis) on log-log paper. A random
sequence will have a slope of exactly -1/2. The lower right hand portion
of the plot will have a few bumps and turns which are equivalent to
truncation noise since the set is of a finite size, but increasing the size
of a random set will always straighten and extend the -1/2 sloped portion
of the line.
The Allan Variance has been used a long time in signal processing by NIST,
and there is a wealth of information on to how to interpret deviations from
a slope of -1/2 (viz. deterministic effects), and a commercially available
software package, Stable (Hamilton Technical Services, 195 Woodbury Street,
S. Hamilton, MA 01982) which takes the drudgery out of calculating the
Allan Variance.
By the way, I've looked at pi out to 128,000 digits using this program, and
found it to be (as is commonly known) quite random. I guess a purist would
call it pseudo random since anyone, given the inclination, can produce the
same digits in the same order.
Regards,
John Feth
------------------------------
** 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
******************************
