Cryptography-Digest Digest #901, Volume #8 Wed, 13 Jan 99 19:13:03 EST
Contents:
AU Crypto Redact leak (David Lesher)
Re: On the Generation of Pseudo-OTP (Jim Felling)
Re: On the Generation of Pseudo-OTP (Terry Ritter)
Re: On the Generation of Pseudo-OTP (Terry Ritter)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (John Briggs)
Re: RSA-Modulus decomposition (Ralf Muschall)
Re: Encrypted WordPerfect 5.1-files (DOS) (JPeschel)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Irish school kid encryption ("Jay")
Re: RSA-Modulus decomposition (Jim Felling)
Re: On the Generation of Pseudo-OTP (Darren New)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Lesher)
Subject: AU Crypto Redact leak
Reply-To: [EMAIL PROTECTED] (David Lesher)
Date: Wed, 13 Jan 1999 20:13:42 GMT
A previously redacted Australian crypto policy paper turns out to
not be ALL that secret:
http://www.efa.org.au/Issues/Crypto/Walsh/index.htm
a) followups set,
b) comment -- "oops!"
--
A host is a host from coast to [EMAIL PROTECTED]
& no one will talk to a host that's close........[v].(301) 56-LINUX
Unless the host (that isn't close).........................pob 1433
is busy, hung or dead....................................20915-1433
------------------------------
Date: Wed, 13 Jan 1999 15:09:50 -0600
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: On the Generation of Pseudo-OTP
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> Tony T. Warnock <[EMAIL PROTECTED]> wrote:
> >
> >
> >Patrick Juola wrote:
> >
> >> In article <[EMAIL PROTECTED]>,
> >> R. Knauer <[EMAIL PROTECTED]> wrote:
> >> >On 11 Jan 1999 16:41:29 -0500, [EMAIL PROTECTED] (Patrick Juola)
> >> >wrote:
> >> >
> >> >>>How about specific constants like ln(c) or c^1/2, etc.? Can these be
> >> >>>show to be random like pi on a case by case basis?
> >> >
> >> >>Yes. But on a case-by-case basis. It's *NOT* the case that
> >> >>all transcendental numbers are "random" in a cryptographic
> >> >>sense.
> >> >
> >> >But how does one do the characterization? What are the criteria for
> >> >deciding that a given transcendental constant produces a crypto-grade
> >> >random sequence? For that matter, how do we know that pi is random?
> >>
> >> Arcane and heavy mathematics, which I won't bore you with -- especially
> >> as I don't know the details myself. I don't even own the necessary
> >> textbooks to cite from any more, it was sufficiently long ago.
> >>
> >> But, as my half-assed remembrance tells me, the proof is actually
> >> expressed in terms like "pi is 'normal' to every base", where
> >> 'normal' means that every (finite) digit stream appears *somewhere*
> >> in the decimal expansion of pi.
> >>
> >> This is necessary, but not sufficient, for producing a cryptologically
> >> random stream.... for example, the stream
> >>
> >> 0.123456789101112131415161718192021...
> >>
> >> is also 'normal' to base 10, but is pretty pathetic as an OTP.
> >
> >You're on the right track here. Some clarifications:
> >
> >"Normal to base b" means that every finite digit stream occurs with the
> >proper frequency, that is 001 occurs (base 2) 1/8 of the time, etc. Borel
> >(1909) showed that with probability 1, all real numbers are normal to every
> >base. I do not believe that there is a proof that Pi is normal to any base.
> >
> >The only normal numbers that I am aware of are those constructed like your
> >example.[...]
>
> Excellent. Glad to have a real real analyst join the discussion.
>
> I could have sworn that such a proof existed for pi, but I will
> of course defer to your superior knowledge. This does, however,
> raise two rather fundamental questions
Such a proof does exist for pi. In fact I have (in the course of a long and
varied math education) had to prove it as part of my homework for a graduate
level topology class.
>
>
> 1) how does one prove that an arbitrary real number is normal?
For an arbitrary number this is a very hard thing to do. The problem being
establishing an appropriate (topological) basis by which to analyze it. And then
demonstrating that given that basis the distribution properties of the number
are appropriate. (usually by contradiction -- assume the distribution is bad
then show that this leads to a contradiction of known properties for the number.
>
>
> 2) what other properties besides normality would make an arbitary
> real useful for cryptographic purposes?
>
1) Easy to compute arbitrary digits
2) proper statistical behavior in a local (not an absolute sense) -- e.g. given
a number t which is normal to all bases this still does not mean that in the
first 2^256 digits even a single 7 (base 10) occurs - since the normality is
over the entire (infinite) set of digits of the number and the accessible digits
to us may well not be well behaved for our purposes.
3) Compact representation of the number.( so one can transmit the key
conveniently and unambiguously)
Of those #2 is the most difficult to achieve and the hardest to document
appropriately.( The number, since it is normal is well behaved as to randomness
in a global sense, but this does not mean any local set of values (however
large) is cryptographicly appropriate.)
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 21:25:30 GMT
On Wed, 13 Jan 1999 19:32:14 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>On Wed, 13 Jan 1999 16:38:06 +0100, Mok-Kong Shen
><[EMAIL PROTECTED]> wrote:
>>[...]
>>That's the best you can do even with your hardware devices.
>
>Not true. The radioactive decay TRNG is based on a fundamentally
>random physical process, not some characterization of the bitstream
>that it outputs.
One could say similar things about many noise sources: Thermal noise
in a resistance is "fundamentally random." Reverse-biased junctions
in breakdown seem to be fundamentally random. Nuclear events may be
random, but that does not make up for "quench time" delays in Geiger
tube detectors. A great deal of effort has been spent in making
really random generators, and we have many satisfactory designs, butt
none that one might call "theoretically proven random."
I have several literature surveys on randomness topics, one of which
is "Random Number Machines: A Literature Survey":
http://www.io.com/~ritter/RES/RNGMACH.HTM
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 20:59:48 GMT
On Wed, 13 Jan 1999 15:57:54 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>[...]
>I prefer Maurer's universal test.
I find this odd, considering that the author himself disclaimed its
use on PRNG sequences. And I have not found Maurer's test to be very
revealing, which is something I want from a good test.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 21:44:13 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 14:22:25 -0500, Mark Ingram <[EMAIL PROTECTED]>
wrote:
>> HINT: Chaitin constructed Omega deliberately so it could not be
>> algorithmically reduced.
>I would respectfully suggest that "Chaitin's Omega" is fairly well
>compressed just like that.
I respectfully ask why you think I did not say exactly that.
Chaitin constructed Omega to be irreducible, and therefore it is
irreducible by design - that is, it cannot be algorithmically reduced
at all. The reason is that each bit of Omega is completely
indeterminant, which means each bit can be either a 1 or a 0
equiprobably.
How could THAT kind of number ever be algorithmically reduced - when
you don't even know what it is you are trying to reduce to begin with.
How can you reduce a number whose every bits could be either a 1 or 0,
and you have no way of knowing formally which they are?
That would be like trying to algorithmically reduce the result of
series of coin tosses. Impossible.
>Is there something I am missing?
I do not understand the difficulty you are expressing.
>Is it another paradox,
Paradoxes like the Epimenides, Russell and Berry paradoxes are
intimately involved.
>much like "the
>smallest number not expressible in eight words"?
Chaitin uses the Berry Paradox you just alluded to in his discussions.
>I am absolutely riveted by this (these) thread(s), this is the most
>enjoyable sci.crypt has ever been ...
You should have been here a year ago when we were discussing
randomness in a different light.
Since then I took the time to read Chaitin's work carefully and
reflect on it, at least the part which applies to randomness and
indeterminancy that is on the Web.
Although he claims his work has no application to crypto (private
communication), I think it does in some respects - at least in terms
of randomness in general. The part that I do not think applies to
crypto is using complexity as a formal measure of randomness.
But that all remains to be seen as this topic unfolds.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 13 Jan 1999 21:13:55 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 20:03:45 +0000, "Douglas E.Denny."
<[EMAIL PROTECTED]> wrote:
>If your proposition above about any random number generated is not a true
>random number, (for whatever reason)
I never said that. On the contrary, I have said many times that a
proveable source of crypto-grade random numbers suitable for use in
the OTP cryptosystem is a hardware TRNG.
>then the OTP _cannot_ be an
>exception as its (random) key is normally derived from an algorithm.
Wrong! The key pad for an OTP is always generated from a hardware
TRNG, or else it is not proveably secure.
Furthermore, unless someone can show otherwise, numbers generated
algorithmically are not truly random, because the generator is not a
TRNG - that is, there is no formal reason to believe that the output
of an algorithmic generator constitutes all possible sequences of a
given length equiprobably (IOW, an upredictable output).
For a seeded PRNG, you know right away that it doesn't come even close
to the specification for a TRNG, since it is not capable of generating
all the microstates for a given macrostate representing the pad. It
can only generate those microstates that are consistent with its
limited macrostate representating the algorithm and the seed.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 22:17:59 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 20:59:42 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>Are you reading the same FIPS 140-1 that I am? That would be:
>"SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC MODULES," 1994 January 11.
>I find no instance of "strong mixing" or even "mixing" in that text.
Dammit! I mixed that up (no pun intended) with RFC 1750, which is
where strong mixing is mentioned.
>Well, "correlation attacks" may be *the* major topic in stream cipher
>design over the last two decades; see "The Story of Combiner
>Correlation: A Literature Survey":
Why didn't someone tell me about this before!
> http://www.io.com/~ritter/RES/COMBCORR.HTM
>These attacks address the production of stream cipher confusion
>streams by *combining* multiple sources, and the combiners allow
>information from the original sources to leak to the output. We see
>attack after attack, and subsequent attempts to avoid the attacks.
That seems to imply that the recommendations in RFC 1750 are
inadequate for purposes of practically secure crypto.
>But I am unaware of a general theory of "decorrelation" that could
>avoid any such attack, or transform a sequence with internal
>correlations into a sequence with no correlations.
Could that be because trying to remove correlations with an
algortihmic procedure is counterproductive, since such procedure
itself can introduce correlations because it is algorithmic?
After all, if one can compute the nth and n+1th state of an algorithm,
there is a strong correlation between the two outputs.
>The lack of such
>a theory might make the topic somewhat difficult to discuss.
Maybe that is the theory - that algorithmic decorrelation is
impossible.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: On the Generation of Pseudo-OTP
Date: 13 Jan 1999 21:34:47 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
writes:
>On 13 Jan 1999 13:29:28 GMT, [EMAIL PROTECTED] (John Briggs)
>wrote:
>
>>If you pick the number first, then the compression algorithm then
>>you can compress down to arbitrarily small sizes.
>
>Not if you must use that algorithm to reproduce the number, as is
>required in Chaitin's algorithmic complexity theory. Reduction is one
>criterion and reproducibliity is another.
A compression algorithm is the piece that converts plaintext to
compressed text. A _decompression_ algorithm reproduces the
original number.
>>Note that the Chaitin's notion of algorithmic complexity is equivalent
>>to choosing the _decompression_ algorithm first. Then the number.
>>And then finding the minimum string that decompresses to that number.
>
>I surely did not get that from a reading of his papers.
Fix a decompression algorithm. Select the minimum input string
that produces a specified output string. Voila. A complexity measure.
The specified decompression algorithm: A universal TM.
>He states clearly that the complexity of a number can be reduced if
>the algorithm accomplishes two things simultaneously:
>
>1) It compresses the number.
>
>2) It reproduces the number.
>
>For example, let's say the number is 111...1, of N bits in length. If
>I employ the following algorithm:
>
>for(i=0;i<N; i++) fprintf("1");
OK. You've got an algorithm. (Actually, a class of algorithms).
Its description is short. It can produce a large output.
Note well, this is not a compression algorithm. It is a compressed text.
The decompression algorithm in this case is a C interpreter.
The compression algorithm was you coming up with the C code.
>I have significantly reduced the complexity of the number - that is, I
>have "compressed" it or algorithmic reduced it - while providing an
>algorithm to reproduce it at the same time.
>
>The reason is that this algorithm reduces the complexity of the number
>is that it only takes log2(N) bits to represent the coding of N in the
>for( ) loop. The additional bits of overhead for the rest of the code
>become negligible as N gets larger.
>
>Therefore I have:
>
>1) algorithmically "compressed" a number of size N to a number (the
>code fragment itself) of size log2(N) + C, and
You have not exhibited an algorithm to do the compression. You
have exhibited an algorithm that is the compression. Two different
things.
>2) I have reproduced the number.
>
That you have.
Of course you do have one niggling problem: How big is your C
compiler? Your run time libraries? Your microcode? Your circuit
board drawings?
>Calculating the bit parity of a number is not relevant here.
If you say so.
>>No. For any number, there is an algorithm that compresses it down
>>to a length of (at most) one. That's any number. Not just some
>>numbers. Not just a trivial minority. Not just an overwhelming
>>majority. Any number.
>
>You cannot do that to the uncomputable real numbers, of which there
>are an infinite count in any finite interval.
You are correct.
You can't compress all the reals. You can compress all the integers.
You can't compress all the infinite bit strings. You can compress the
finite ones.
>But if you don't believe that, try compressing Chaitin's Omega and
>show us what you get. We await your result with great anticipation.
>
>HINT: Chaitin constructed Omega deliberately so it could not be
>algorithmically reduced.
HINT: Compressed != Algorithmically reduced.
You give me all the digits of Chaitin's Omega and I'll give you an
algorithm that can reproduce them from arbitrarily little input.
Note well, I don't claim my algorithm will be smaller than Chaitin's
Omega.
John Briggs [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Ralf Muschall)
Subject: Re: RSA-Modulus decomposition
Date: Wed, 13 Jan 1999 23:40:18 +0100
Robert I. Eachus wrote:
> about this on the way home Friday... The two solutions must be (1,0)
> and (0,1) in Chinese Remainder notation. There are four numbers such
> that m^2 = m mod n, where n is the product of two primes. (0,0) = 0
> and (1,1) = 1 are the trivial solutions. So you can find these
> solutions by applying the Extended Euclidian Algorithm to p and q.
Even simpler: They are p^(q-1) and q^(p-1)
(Fermat ensures that they are solutions, and CRT says that
they are unique (together with 0,1)).
Ralf
PS: everything but sci.crypt removed from the header.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Encrypted WordPerfect 5.1-files (DOS)
Date: 13 Jan 1999 22:52:37 GMT
>"K&G" <[EMAIL PROTECTED]>writes, in part:
>I'd like to know if someone who could help me to decrypt
>some (DOS) WordPerfect 5.1-files
use a word perfect cracker.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 22:33:18 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 21:25:30 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>>The radioactive decay TRNG is based on a fundamentally
>>random physical process, not some characterization of the bitstream
>>that it outputs.
>One could say similar things about many noise sources:
Yes, that is true. Wherever there is quantum behavior, there is the
potential for total randomness.
>Thermal noise in a resistance is "fundamentally random."
Yes, but is it crypto-grade random, since there a 1/f white noise
spectrum associated with it?
>Reverse-biased junctions
>in breakdown seem to be fundamentally random. Nuclear events may be
>random, but that does not make up for "quench time" delays in Geiger
>tube detectors.
Who would use a Geiger-Mueller tube these days - assuming a serious
design?
But yes, there is a latency (dead time) associated with all avalanche
detectors, even proportional counters which have a quench gas present.
That has to be taken in account when designing the TRNG.
>A great deal of effort has been spent in making
>really random generators, and we have many satisfactory designs, butt
>none that one might call "theoretically proven random."
I disagree. A radioisotope TRNG of proper design is proveably random
to an arbitrary practical level of precision (which recognizes that
nothing in the real world is truly "perfect").
It might be slow as all hell, but the output meets the specification
for a TRNG, namely that it is capable of generating all possible
sequences of a given length equiprobably (to within an arbitrary level
of precision).
>I have several literature surveys on randomness topics, one of which
>is "Random Number Machines: A Literature Survey":
> http://www.io.com/~ritter/RES/RNGMACH.HTM
Why didn't someone tell me about this before!
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: "Jay" <[EMAIL PROTECTED]>
Subject: Re: Irish school kid encryption
Date: Wed, 13 Jan 1999 18:28:34 -0500
Imagine that, just 16 years old with her own NSA file. So much for childhood
innocence.
Jay
Anthony Lineham wrote in message
<[EMAIL PROTECTED]>...
>I read a brief news article today about a 16 year
>old Irish school girl who recently won a prize at
>a science fair for designing an encryption
>algorithm for internet use that is reported to be
>10 times faster than algorithms currently in use.
>she is apparently being hailed as a mathematical
>genius.
>
>Does anyone have any more specific details about
>this or know where they may be found?
>
>Thanks
>
>Anthony.
>
------------------------------
Date: Wed, 13 Jan 1999 17:43:20 -0600
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To:
alt.privacy,alt.security,alt.security.pgp,comp.security.pgp.discuss,talk.politics.crypto
Subject: Re: RSA-Modulus decomposition
David Hamilton wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Jim Felling <[EMAIL PROTECTED]> wrote:
>
> >I hate to say this, but -- aernst331 does not make silly, untrue claims.
(snip very well reasoned refutation of my statement)
His mathematics is true, but what he says he can do with it is totally wrong. I
concede the point.
>
> >He makes very, very silly/useless true claims.
>
> This is also true of course.
>
> (snip remainder)
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 23:00:09 GMT
> I would respectfully suggest that "Chaitin's Omega" is fairly well
> compressed just like that.
Except for those of us who do not already posess the decompression
algorithm.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
** 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
******************************
