Cryptography-Digest Digest #133, Volume #9 Wed, 24 Feb 99 17:13:03 EST
Contents:
Re: Take my hand, PLEASE ([EMAIL PROTECTED])
Re: Testing Algorithms (Bauerda)
Re: Block cipher in the smallest PIC (Robert Scott)
Re: Pentium III Hardware Random Numbers (Robert Scott)
Re: Block cipher in the smallest PIC (Paul Rubin)
Re: What do you all think about the new cipher devised by a 16 year old? (Terry
Ritter)
Where to post crypto... ("D")
Re: Where to post crypto... ("D")
Re: Define Randomness (Terry Ritter)
Re: Define Randomness ("Trevor Jackson, III")
Re: Define Randomness ("Trevor Jackson, III")
Re: Define Randomness (R. Knauer)
Re: Define Randomness (R. Knauer)
Re: Define Randomness ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Take my hand, PLEASE
Date: Wed, 24 Feb 1999 20:00:17 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JUzarek) wrote:
>
> In an e-mail dated 2/22/99 8:57:21 AM EST, [EMAIL PROTECTED] writes:
>
> > What makes it so difficult? I am not saying I think it is easy, all I am
> > saying is I am a newbie here and it seems like it is a substitution except
> > more than one charter of plain text is represented by more than one
ciphered
> > text.
>
> Your are probably correct that a monoalphabetic substitution with variants has
> been used similar to that in the three part message that was successfully
> deciphered. The variants obscure word patterns and make frequency counts
> unreliable. This doesn't make it impossible to recover, just more difficult.
>
> >Have you attempted it?
>
> Yes and so did a number of qualified cryptanalysts when the messages first
> appeared.
>
> The supposed decrypt of the 340 character message does not make any sense.
> The method for decrypting the text was not disclosed. Matching the decrypt
> to the cipher produces numerous incongruities suggesting the decrypt is not
> kosher. I keep going back to it as time permits - have made little or no
> progress.
>
> The 13 character "signature" may never be recovered. It is just too short.
> Even if a name could be fitted to the cipher letter pattern, there would be
> no way to conclusively prove that the resulting key was the correct one.
>
> >....what should I read to get some knowledge?
>
> For classic ciphers, "Cryptanalysis" by Helen Fouche Gaines is an
> excellent start although, I'm not sure where you can get a copy
>
> "Military Cryptanalysis Part I" by William Friedman and Lambros Calimahos,
> originally an NSA manual, is very good for beginners and
> can be obtained from Agean Park Press.
>
> >Is it possibly some military algorithm, or variant thereof?
>
> Although substitutions with variants have been used by military organizations,
> this type has more of an amateur ring to it.
>
> Note: The URL I posted for the Zodiac Homepage is no longer active.
> Check out this one instead - it was valid as of two days ago.
> It provides background info as well as copies of all his messages.
>
> http://www.redacted.com/zodix.htm
>
> The more people taking stabs at this one the more likely that a valid solution
> will eventually be found and, again, I wish you the best of luck.
>
>
Hi-
The best web pages on the Zodiac--hands down--are :
http://members.aol.com/jakewark ; www.zodiackiller.net and
www.glasscity.net/users/zychow
These are the ones to start with for primers if you are unfamiliar with the
case. They are all A-1. The dead link which had been provided from Humboldt
University was also excellent but, alas, is no more...
This is one of the most incredibly complex cases of crime-- and the
cryptography just scratches the surface of it-- you'll ever see in your
lifetime. Don't think it is complex simply because of the crypts. Get into
some of the threads in Dejanews which are dedicated to it and you'll see what
I mean. I've been interested in the on-line aspects of the case since last
August and it is incredibly mind-twisting and thought-provoking.
MRR
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Bauerda)
Subject: Re: Testing Algorithms
Date: 24 Feb 1999 19:55:20 GMT
>On the other hand, if you specify any length of technology less than
>divine, you run a grave risk of finding technology outstripping
>your specifications.
Then why don't we throw in another variable. What is the probablitity that a
short, randomly generated string will make a readable and probable message? Or
that a randomly generated message will correctly decompress using a standard
(or specified) compression algorithm? And if an enemy has that much computing
power, maybe they should see if they can get Asimov's psycho-history to work
and simply predict what your message said.
David Bauer
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: Re: Block cipher in the smallest PIC
Reply-To: see text
Date: Wed, 24 Feb 1999 20:31:23 GMT
On Wed, 24 Feb 1999 17:12:42 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>
>I'm skeptical of whether your cipher is as secure as DES, because
>of its slow rate of diffusion.
DES is actually slower (relative the the number of rounds).
DES takes 5 of the 16 rounds to completely diffuse every input
bit to potentially every bit in the left and right 32-bit halves.
My cipher takes 7 rounds of the 32 total rounds for complete
diffusion. 7/32 < 5/16.
BTW, as David Wagner pointed out to me, the key expansion algorithm
that I proposed would be much better if I didn't use the
all-zeroes DES key, since that key results in a repeat in my key
schedule every 16 bytes, using recursive DES encryption of the
raw key. So assume any other fixed DES key.
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: Re: Pentium III Hardware Random Numbers
Reply-To: see text
Date: Wed, 24 Feb 1999 19:11:40 GMT
On 24 Feb 1999 10:38:33 -0500, [EMAIL PROTECTED] (Herman Rubin)
wrote:
>
>I cannot see thermal noise as a good source for randomness. The
>problem is that the physical parameters are not constant, and thus
>there is a moderate amount of variation. This may be low enough
>for cryptographic uses, but I would not trust it for the large
>simulations in various fields, where a small amount of bias or
>dependence can be important.
Given a source of randomness that exhibits some bias, it is
always possible to reduce the bias as much as you like provided
you are willing to sacrifice speed. For example, take 100 biased
bits and produce a single output bit depending on the parity of
the 100-bit number.
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Block cipher in the smallest PIC
Date: Wed, 24 Feb 1999 20:51:55 GMT
In article <[EMAIL PROTECTED]>, Robert Scott <see text> wrote:
>On Wed, 24 Feb 1999 17:12:42 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>>I'm skeptical of whether your cipher is as secure as DES, because
>>of its slow rate of diffusion.
>
>DES is actually slower (relative the the number of rounds).
>DES takes 5 of the 16 rounds to completely diffuse every input
>bit to potentially every bit in the left and right 32-bit halves.
>My cipher takes 7 rounds of the 32 total rounds for complete
>diffusion. 7/32 < 5/16.
Look what happens in your cipher if two inputs differ only
in the 2nd-to-highest bit in some byte. I think you should
change your F function to depend on all the bits in the byte.
>BTW, as David Wagner pointed out to me, the key expansion algorithm
>that I proposed would be much better if I didn't use the
>all-zeroes DES key, since that key results in a repeat in my key
>schedule every 16 bytes, using recursive DES encryption of the
>raw key. So assume any other fixed DES key.
Yes, the all-zero and all-one DES keys are weak in this sense.
There are some other semiweak keys as well.
Better IMO would be to DES-encrypt a fixed string using your cipher
key as the DES key, rather than encrypting your cipher key with a
fixed DES key. That way, figuring out some bits of the F table
doesn't give you as big a foothold toward figuring out the rest
as your current scheme does.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: What do you all think about the new cipher devised by a 16 year old?
Date: Wed, 24 Feb 1999 20:53:07 GMT
On 24 Feb 1999 08:47:56 -0500, in <7b0vuc$q4e$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>[...]
>I believe post-application publication is legitimate anywhere in the
>world.
Although I personally do *not* keep my development secret beyond
application, this creates some uproar from my attorneys. It is not at
all unheard of for prior art to be found to the patent as written,
leading to the realization that the originality was really in other
parts of the development. But if those parts already have been
disclosed, then in most countries a patent is no longer available. So
the wise thing to do is to keep quiet until the patent is granted, or
at least allowed.
My personal policy was intended to get people working with and
surpassing the new idea. I now suspect, however, that the best way to
do that would be to let the tension build for as long as possible,
which is precisely what the "keep quiet" policy will do.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "D" <[EMAIL PROTECTED]>
Subject: Where to post crypto...
Date: Wed, 24 Feb 1999 16:00:08 -0500
I have a working crypto program that could be used to very securely
encrypt small messages such as e-mail. I intend to make the source freely
available (for no charge). I would like to know where I can post it.
note: it will include a complete description of the algorithm, and
perhaps some stenography tools, etc.
------------------------------
From: "D" <[EMAIL PROTECTED]>
Subject: Re: Where to post crypto...
Date: Wed, 24 Feb 1999 16:08:13 -0500
Oh, yeah, I live in America, the great EEUU
Free Kevin:
http://www.kevinmitnick.com/
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 20:54:51 GMT
On Wed, 24 Feb 1999 17:26:37 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>On 24 Feb 1999 11:02:38 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>[...]
>>The point of the original poster being, of course, that a "random"
>>stream need not be an "unbiased random" stream.
>
>You need an unbiased generator for it to be crypto-grade random.
But that can be understood in misleading ways. In particular, the
original "generator" *can* have bias in its output, and yet *can* be
used for crypto, *provided* the output is "processed" to remove the
bias.
It would not be correct, for example, to say that a crypto-grade
generator must *inherently* produce an unbiased output. While that
might be convenient, I doubt that any physical machine -- even
measuring the ideal flat source -- could produce a sufficiently flat
distribution in practice. So the output from physical generators
generally must be post-processed before use.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Wed, 24 Feb 1999 16:31:56 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
R. Knauer wrote:
> On 24 Feb 1999 09:23:07 -0500, [EMAIL PROTECTED] (Patrick Juola)
> wrote:
>
> >You're confusing generator skew with sequence skew again.
>
> I do not believe so, not in the context of crypto-grade random
> numbers.
>
> >The point is that a *generator* can be skewed (I prefer the term
> >'bias', but they're largely equivalent) and still be random.
>
> >As an example : suppose I have a bit-generator that works like this :
> >I roll a die ("randomly") and output a zero if the result is a six,
> >a one otherwise.
>
> >This isn't a very good generator (it's biased), but it's still
> >random. And the entropy of this generator is less than the entropy
> >of a generator consisting of a fair coin.
>
> That generator is not crypto-grade random. If you used keystreams from
> that RNG you would leak significant amounts of information.
Not true. There are simple transforms that will remove the bias without
imposing any additional order (bias) on the sequence. The biasless
transformed sequence will not leak any information.
------------------------------
Date: Wed, 24 Feb 1999 16:25:58 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
R. Knauer wrote:
> On 24 Feb 1999 09:49:32 -0500, [EMAIL PROTECTED] (Alan
> DeKok) wrote:
>
> > As a physicist, I'll have to call you on this topic.
>
> How about that - I am a physicist too. Small world, eh.
>
> >Q: When is an algorithmic PRNG identical to a TRNG?
>
> >A: They're identical when you are unable to distinguish the two.
>
> I remind you that obscurity does not produce security. The digit
> expansion of pi might *appear* random, but that does not necessaruly
> make it secure.
>
> The crucial test is whether the keystreams are crypto-grade secure.
> That can only be determined analytically by using them to produce test
> ciphers and then try to break those test ciphers by some sort of
> inferential attack, like the Bayesian method. If the ciphers do not
> leak signifcant amounts of information, then you have an
> (experimentally) proveably secure system to within the limits of
> experimental error.
This is a false analogy. The flaw is the contained within the idea that
an analysis is an experiment. There is no exhaustive
examination/inspection/analysis that can prove a keystream secure. Thus
there is no way to measure the security of a cipher experimentally. Since
there is no unit of measure, repeatability is not possible, so the
scientific method is compromised.
There are proofs that identify keystream weaknesses. But failure to find
such a proof can be attributed to the analytic horizon effect among
others. The inability to describe 'the limits of experimental error" due
to lack of a metric for security means that the concept of experiment is
not useful in this context. So a failure to find a proof of weakness does
not constitute a proof of security.
People do rely on the fact that peer review and long, intensive analysis
have failed to find flaws in cipher systems. But characterizing these
atempts to find weakness as experiments is an error.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 21:29:43 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 24 Feb 1999 20:54:51 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>>You need an unbiased generator for it to be crypto-grade random.
>But that can be understood in misleading ways. In particular, the
>original "generator" *can* have bias in its output, and yet *can* be
>used for crypto, *provided* the output is "processed" to remove the
>bias.
Two comments:
1) Such anti-skewing processing must be included in the overall
specification of the TRNG for it to be a genuine TRNG, so we are back
where we started, namely:
"You need an unbiased generator for it to be crypto-grade random".
2) I have not been convinced that anti-skewing does not introduce
correlations, which would make the output unsuitable for crypto-grade
ciphers. After all, the anti-skewing procedure is algorithmic, so
there is always the opportunity to introduce correlation(s).
The von Neumann method looks innocent on the surface since the
probability of dibits 01 and 10 are the same, namely p*(1-p). But that
says nothing about the correlations inherent in their appearance. If
you start throwing out bits like in the von Neumann method, who knows
what patterns are left behind.
>It would not be correct, for example, to say that a crypto-grade
>generator must *inherently* produce an unbiased output. While that
>might be convenient, I doubt that any physical machine -- even
>measuring the ideal flat source -- could produce a sufficiently flat
>distribution in practice. So the output from physical generators
>generally must be post-processed before use.
I fully agree. A bias-free TRNG is an idealization, just like a
(perfect) circle is an idealization. But that does not imply that
algorithmic anti-skewing procedures should be used to fix a poorly
implemented TRNG design.
You don't run eccentric wheels on axles that are shaped like a crank,
just to compensate for the eccentricity.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 22:00:03 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 24 Feb 1999 16:31:56 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>> That generator is not crypto-grade random. If you used keystreams from
>> that RNG you would leak significant amounts of information.
>Not true. There are simple transforms that will remove the bias without
>imposing any additional order (bias) on the sequence. The biasless
>transformed sequence will not leak any information.
As I commented earlier, such anti-skewing procedures must be included
into the specification for the TRNG.
Now here's the question for you - do these anti-skewing procedures
introduce correlations into the keystream? After all, they are
algorithmic, which means they produce a pattern.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
Date: Wed, 24 Feb 1999 16:38:52 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
R. Knauer wrote:
> On 24 Feb 1999 11:02:38 -0500, [EMAIL PROTECTED] (Patrick Juola)
> wrote:
>
> >No, but it's "random." The von Neumann/Knuth pairwise transform would
> >remove the bias and make it acceptable.
>
> I never said it was not random in some sense other than crypto-grade.
>
> Kolmogorov Complex strings are Kolmogorov random, but they are not
> crypto-grade random. A TRNG can output any number, including those
> that fail the criterion of Kolmogorov prefix complexity.
>
> >The point of the original poster being, of course, that a "random"
> >stream need not be an "unbiased random" stream.
>
> You need an unbiased generator for it to be crypto-grade random.
Not quite. Any biased generator that captures entropy can be transformed
by the addition of a post filter into an unbiased generator. The
generation cost goes up as the inverse of the filtration ratio. In essence
we can retain the entropy of the output and discard the redundancy in the
output.
>
>
> BTW, what happens to the randomness of your number generator as the
> bias approaches unity? You started out with a bias of 5:1 with a
> standard die. How random is your number generator if the die has 1,000
> sides, and you use only one of the faces of that die for the 1 bit and
> all the rest for the 0 bit?
The entropy density goes down as the bias goes up. So the data rate
(bits/time)of a derived unboased generator will be 1/999 of the biased data
rate, but the information rate (entropy/time) will be the same.
>
>
> In the limit as the number of sides grows unboundedly large, the bias
> approaches unity, which means that your generator puts out all zeros.
> Yet the claim is that it is still a random number generator, albeit
> not for purposes of crypto.
>
> Li & Vitanyi make the point that any true random number must be normal
> in the Borel sense, which means that there can be no bias whatsoever.
> Of course, Borel normality is a property of infinite numbers, but we
> can handle that by applying it to the generator itself for finite
> strings.
>
> Therefore in order for a TRNG to be *capable* of outputting a normal
> number, it cannot have any bias in its implementation.
No. This conclusion is unwarranted.
>
>
> Bob Knauer
>
> "Democracy is the theory that the common people know what they
> want, and deserve to get it good and hard."
> --H.L. Mencken
------------------------------
** 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
******************************
