Cryptography-Digest Digest #849, Volume #8 Tue, 5 Jan 99 13:13:03 EST
Contents:
Re: Help: a logical difficulty (Nicol So)
Re: Help: a logical difficulty (Mok-Kong Shen)
Re: Help: a logical difficulty ("Douglas A. Gwyn")
Re: On leaving the 56-bit key length limitation (Padgett 0sirius)
Re: Help: a logical difficulty (Mok-Kong Shen)
Re: Teaching Program (James Pate Williams, Jr.)
Re: U.S. Spying On Friend And Foe ("Douglas A. Gwyn")
On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: New Twofish Source Code Available (Bruce Schneier)
Re: Help: a logical difficulty (Jonah Thomas)
Re: New Twofish Source Code Available (Uri Blumenthal)
Re: Help (How long can a post be seen?) (Mok-Kong Shen)
Re: Help: a logical difficulty (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 08:27:18 -0500
Mok-Kong Shen wrote:
> Nicol So wrote:
>
> > Given a universal computer, an encoding of an algorithm, and a given
> > finite string, either the universal computer eventually halts, or it
> > doesn't. If the universal computer does halt, it either outputs the
> > string, or it doesn't. ...
>
> If the machine continues running, it may halt at some future time
> (perhaps shortly before the end of the universe) or it never halts
> (getting into a loop). You don't know which is which. So you don't
> know the second case indicated by your phrase 'or it does not'.
Something is well-defined if it has a definite meaning. Consider the predicate
H(A, x) which is true if and only if "algorithm A eventually terminates on input
x". For any particular A and x, the value of H(., .) is *some* definite value
(either 'true' or 'false'). We may or may not know the answer. We may or may
not have a proof for the answer. But that's immaterial. The answer has to be
*some* definite value. (Think about it, nothing in the definition makes the
value of H(., .) dependent on some person knowing the answer).
There are no contradictory statements in the definition of H(.,.) that may
sometimes require its value to be both true and false. At the same time, the
value of H(A, x) is *always* forced to a *particular* value once A and x are
specified. That's well-definedness.
I suspect that you are under the false impression that a predicate is
well-defined only if it is decidable. If that's what you thought, that could be
the source of your difficulty.
Nicol
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 16:06:54 +0100
Nicol So wrote:
>
> Something is well-defined if it has a definite meaning. Consider the predicate
> H(A, x) which is true if and only if "algorithm A eventually terminates on input
> x". For any particular A and x, the value of H(., .) is *some* definite value
> (either 'true' or 'false'). We may or may not know the answer. We may or may
> not have a proof for the answer. But that's immaterial. The answer has to be
> *some* definite value. (Think about it, nothing in the definition makes the
> value of H(., .) dependent on some person knowing the answer).
>
> There are no contradictory statements in the definition of H(.,.) that may
> sometimes require its value to be both true and false. At the same time, the
> value of H(A, x) is *always* forced to a *particular* value once A and x are
> specified. That's well-definedness.
>
> I suspect that you are under the false impression that a predicate is
> well-defined only if it is decidable. If that's what you thought, that could be
> the source of your difficulty.
As I pointed out in another follow-up, in the present context we
need comparisons of complexity. That a certain sequence has a
certain 'definite' but 'unknown' complexity is not of much use if
one wants to compare two sequences to see if one is superior to
the other for cryptological applications.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 15:08:36 GMT
Mok-Kong Shen wrote:
> Since there does not exist an algorithm to deliver the shortest
> string to describe an arbitrarily given random number sequence,
> couldn't one say that the problem of determining the shortest
> description of a sequence is undecidable?
No, because one can simply generate all possible descriptions in
increasing order of size until one is found that generates the
sequence. (This is obviously not a very efficient algorithm.)
It is clear that a suitably defined interpretation architecture
can guarantee that such a description won't exceed 2*N+2 bits,
where N is the length of the sequence, so the search will terminate
within 2^(2*N+2) iterations (of a finite process).
I don't know why you assert that there "does not exist" such an
algorithm, unless you're discussing an *infinite* sequence, which
is not practical.
------------------------------
From: [EMAIL PROTECTED] (Padgett 0sirius)
Subject: Re: On leaving the 56-bit key length limitation
Date: Tue, 5 Jan 1999 07:09:05
Really have not a clue what "unicity distance" actually means but would
assume from the context that it refers to an algorithm strength.
Traditionally, all that is important is whether it is "strong enough that
brute force is the easiest attack". This is essentially binary - it
either is or is not, the actual value would seem to be unimportant except to
a mathematician.
Of course the binary value IS relative to keylength. DES is essentially felt
to be "strong enough" for a 56 bit key and is not for longer keylengths.
Probably the proper way to express is that a given algorithm is "suitable
for keylengths of up to xxx bits" or have I missed something entirely ?
A. Padgett Peterson, P.E. Cybernetic Psychophysicist
http://www.freivald.org/~padgett/index.html
to avoid antispam use mailto:[EMAIL PROTECTED] PGP 6.0 Public Key Available
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 16:25:22 +0100
Douglas A. Gwyn wrote:
>
> Mok-Kong Shen wrote:
> > Since there does not exist an algorithm to deliver the shortest
> > string to describe an arbitrarily given random number sequence,
> > couldn't one say that the problem of determining the shortest
> > description of a sequence is undecidable?
>
> No, because one can simply generate all possible descriptions in
> increasing order of size until one is found that generates the
> sequence. (This is obviously not a very efficient algorithm.)
> It is clear that a suitably defined interpretation architecture
> can guarantee that such a description won't exceed 2*N+2 bits,
> where N is the length of the sequence, so the search will terminate
> within 2^(2*N+2) iterations (of a finite process).
>
> I don't know why you assert that there "does not exist" such an
> algorithm, unless you're discussing an *infinite* sequence, which
> is not practical.
Why should infinite sequences be excluded as non-practical?
Apparently Pi is a useful sequence. Now Pi may have an adequate simple
description in the present context (I don't know). But it is
at least very conceivable that there are other sequences for
which one has no (or not yet) ideas of adequate descriptions.
M. K. Shen
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Teaching Program
Date: Tue, 05 Jan 1999 15:45:54 GMT
Reply-To: [EMAIL PROTECTED]
"bill_wells" <[EMAIL PROTECTED]> wrote:
> Does anyone know of an encryption teaching program--that is, something
>that teaches about encryption through examples or games. My friend
>thought it would be stimulating for her history classes to think
>about the World Wars in terms of codes--maybe have a decoding contest
>where the message says something like "We're going to invade on June 6"
>or the like that and give the kids 24 hours to decipher. Does anyone
>know of any programs like that?
I don't know of any software that would be a suitable for such an
assignment. What sort of encryption algorithm did you have in
mind? I have a program that will assist in breaking a monoalphabetic
code, but you need more ciphertext than would be encoded by
your example. It seems that I remember there was some cryptanalytic
software for classical cipher systems on Bruce Schneier's disk set.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: U.S. Spying On Friend And Foe
Date: Tue, 05 Jan 1999 14:58:36 GMT
"Tony T. Warnock" wrote:
> The great problem of "friends" spying on the US is that the
> "friend" may not be able to keep secrets. Some of our allies may not
> mean harm to us, but they cannot keep secrets. Vice versa.
The British can keep secrets, and they have an Official Secrets Act to
enforce it.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: On the Generation of Pseudo-OTP
Date: Tue, 05 Jan 1999 16:13:23 +0100
In light of the forthcoming 56-bit key length restriction it appears
valuable to re-contemplate on all available techniques in cryptology
(independent of whether they are favoured in current practice) in order
to assess their value (even when employed as a minor 'adjuvant') in
contributing to (combined) encryption schemes that can offer adequate
security to confidential communications of innocent and law-abiding
people of the world despite the severe limitation posed by the 56-bit
key length upper bound. In this thread I propose therefore to discuss
on the topic of pseudo-OTP.
An ideal true OTP is by definition absolutely unpredictable and,
furthermore, used only once. This, as far as I understand, is
theoretical and not strictly obtainable in practice. Using physical
noise and taking care to avoid bias gives some near approximation to an
ideal true OTP. But, as is well known, such OTP is disadvantageous in
handling, since a copy has to be transported and securely kept by the
communication partners. Thus there is a place in practical encryption
of employing pseudo-OTP that does not have this management problem
though on the other hand may be (I like to argue for 'not necessarily')
of security that is inferior to OTP obtained through physical means.
What I actually like to have discussed here is a method of generating
pseudo-OTP that is given further below. But before doing that I want to
recall that a pseudo-OTP can be obtained trivially from a PRNG, if
the sequence is not longer than the period of the PRNG and each
subsequence is never reused. The problem is of course that most PRNGs
that are good for numerical computations are cryptologically very weak.
On the other hand, there are cryptologically strong PRNGs known in the
literature. Sometime ago I myself also made a humble attempt (in my
compound PRNG, see my Web page) to obtain pseudo-random number sequences
of arbitrarily huge periods that are (I believe) difficult to analyze
and that are generated through interleaving the outputs of an
arbitrarily large number of (weak) PRNGs and passing that multiplex
through a shuffling buffer and then post-processing the numbers
outgoing from the shuffling buffer through a pairwise addition mod 1.
(This is a special case of the device of Wichmann and Hill originally
designed for improving the statistical properties of PRNGs. The general
case of adding together more than two numbers mod 1 is employed in
the 56-bit EX-versions of my WEAK-series of algorithms.) Thus,
summarizing the above, obtaining pseudo-OTP from PRNG is one of the
viable ways in practice.
Now I want to describe another practical way of obtaining pseudo-OTP.
(Remark: the stuff is known, no novelty is claimed.) One may have
psychologically some natural reservations against PRNGs. For the
numbers are ultimately (despite transformations, shuffling, etc.)
originated from some simple mathematical equations. Hence the actual
sequences could have some auto-correlations in them, however minute.
(This is why physical random numbers are believed to be superior.)
This motivates us to look for sources other than mathematics for
obtaining pseudo-OTP. One simple and convenient such source suggests
itself: natural language texts. For these are abundant and easily
available everywhere, including regions of the globe outside of the
export-regulating countries. Of course, from the very beginning of
cryptology it has been known that natural language texts are highly
auto-correlated and some classical methods of analysis are in fact
mainly based on frequency distributions of single letters, bigrams,
trigrams, etc. However, we can attempt to remove, more exactly to
arbitrarily reduce, the auto-correlations in several ways and these
preferrably in combination (thus hopefully approaching white noise):
1. Apply (mono- or polyalphabetical) substitutions or homophones.
2. Apply permutations (transpositions), including reversal.
3. Combining different streams through:
a. bitwise XOR.
b. addition mod 2^32 (for example).
c. substitution, e.g. mapping a pair of bytes, one from each stream,
to a pair of bytes.
4. Compression through:
a. common compressin techniques (the Huffman encoding is a
substitution with a variable length code).
b. XORing groups of bits, e.g. 32 bits, i.e. taking their parity.
Note that for (3) an arbitrarily number of streams can be combined
and that all techniques can be applied recursively, for example
(3b) can be applied after (4b). Of course at this point one normally
tends to recall the efficiency issue. However, as I recently pointed
out, one practical and simple way of coping with the 56-bit limitation
is to make use of a new paradigm, namely 'security through
inefficiency', i.e. paying the price of some longer processing time.
This can at least be justified in a poorman's environment and appears
to be useful in a substantial part of civilian applications as well.
One remarkable advantage of using pseudo-OTP generated from natural
language texts as compared to OTP obtained from physical means is that
these need not be securely stored. In fact, the user may display the
natural language texts and read them for entertainment when he is not
doing encryption. Neither is it necessary or even advantageous to
pre-compute the pseudo-OTP once for all subsequent uses. For one
needs only to record the offsets of the different streams participating
in the pseudo-OTP that has been arrived at by the previously sent
messages. The 'key' of the pseudo-OTP consists of the names of the
texts and their very first starting offsets. (As a variety one could
introduce some amounts of skips after each message sent). Since one's
library (computerized to be quickly used) may contain a large number
of texts, each having the potential of participating in the pseudo-OTP,
the mere knowledge of the content of the library of the user is
virtually useless to the analyst. Further, an almost unlimited number
of pseudo-OTPs can be generated after some having been exhausted in
actual communications.
Some remarks to special cases: Some of the participating streams could
even be from the same text, i.e. differing only in offsets. In place of
natural language texts one could also use mathematical constants, e.g.
Pi. Further, since the sources are entirely public, these need not even
be stored at the user's place but downloaded as needed from some server
of the internet.
In the above I have made a humble attempt to sketch one possible way
of obtaining a pseudo-OTP. I should appreciate your opinions on that
and suggestions of other ways of advantageously generating such for
applications in the future 56-bit environment.
M. K. Shen
======================================================
M. K. Shen, Postfach 340238, D-80099 Muenchen, Germany (permanent)
+49 (89) 831939 (6:00 GMT)
[EMAIL PROTECTED] (subject to change)
http://www.stud.uni-muenchen.de/~mok-kong.shen/
(Last updated: 3rd January 1999. Origin site of
WEAK2-EX -- A Poorman's 56-bit Data Encryption Algorithm. (30 Dec 98)
WEAK3-EX -- A Layman's 56-bit Data Encryption Algorithm. (30 Dec 98)
WEAK4-EX -- Another Poorman's 56-bit Data Encryption Algorithm. (3 Jan
99)
Containing 2 mathematical problems with rewards totalling US$500.)
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: New Twofish Source Code Available
Date: Tue, 05 Jan 1999 16:10:55 GMT
On Tue, 05 Jan 1999 02:16:05 GMT, [EMAIL PROTECTED] (James Pate
Williams, Jr.) wrote:
>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>
>>As far as I know, the Twofish source archives outside the U.S. have
>>not yet been updated to the most recent source code.
>
>I hope you are not advocating that someone break our vaunted
>cryptographic regulations and export this "dangerous" code. Of
>course, you would never encourage someone to this.
Never. That would be wrong.
Even so, if someone finds the new code on ftp sites outside the U.S.,
please let me know so I can put the data up on the website.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Jonah Thomas <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 16:49:38 GMT
[EMAIL PROTECTED] (John Briggs) wrote:
>Jonah Thomas <[EMAIL PROTECTED]> writes:
>>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>Since you can find a program that produces the sequence, by
>>exhaustive search you could look at all the shorter programs to
>>find the shortest one that produces the sequence in question. You
>>could then call the length of that program the measure of
>>complexity of that sequence.
>You forgot the halting problem. You can't always tell the
>difference between a Turing machine that will produce the string
>that you're after and halt and a Turing machine that will loop
>forever.
>The approach you suggest is seductive, but wrong.
You're right. I was wrong.
Still, you can find a program that works, providing an upper bound
on the minimum length, and you can reduce the possible candidates
for shorter working programs to a finite list. And if they don't
produce the result you want (and only that result) in a reasonable
time, you can reject them on that ground. Who needs a program that
gives the right answer, but only after you're dead and gone?
------------------------------
From: Uri Blumenthal <[EMAIL PROTECTED]>
Subject: Re: New Twofish Source Code Available
Date: Tue, 05 Jan 1999 12:21:59 -0500
Reply-To: [EMAIL PROTECTED]
Bruce Schneier wrote:
> We have new Twofish source code--reference C, optimized C, and
> ASM--that reflects the improvements we've made.
But no Java code improvements yet?
And thanks for the C!
--
Regards,
Uri
-=-=-==-=-=-
<Disclaimer>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help (How long can a post be seen?)
Date: Tue, 05 Jan 1999 18:26:58 +0100
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> rosi <[EMAIL PROTECTED]> wrote:
> > I would like to know how often and when old posts are purged. It
> > seems to be used to staying longer than now (I can be very wrong).
>
> http://www.dejanews.com/getdoc.xp?AN=330634411.8 is the oldest post of yours I
> could find. I am posting this directly to give kudo for dejanews. Its great!
> Dejanews seems very underutilized. It is better than the FAQ and if more
Could you say what kinds of selection criteria are available for
the data base search?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 19:11:03 +0100
John Briggs wrote:
>
> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
><[EMAIL PROTECTED]> writes:
> >This is also an essential problem. If for two given sequences
> >one machine says the first is less complex than the other but
> >the second machine says the contrary, which result should one take?
>
> Algorithmic complexity is a function of the algorithm.
>
> If you want to know the complexity of "54" in an absolute sense,
> you're out of luck.
>
> Of course, any algorithm worth its salt is going to let you supply
> an arbitrary Turing machine in the input stream. And so you're looking
> at a "plus a constant" worst case on the difference between the
> algorithmic complexity of any two arbitrary input streams as
> measured against any particular pair of salt-worthy, Turing-computable
> algorithms.
>
> Am I missing something or should this have been obvious to everyone?
I wrote the above quoted based on what Jonah Thomas wrote on 04 Jan
23:15:28 in this thread:
'But a different machine will give different results.'
M. K. Shen
------------------------------
** 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
******************************
