Cryptography-Digest Digest #321, Volume #9 Thu, 1 Apr 99 18:13:03 EST
Contents:
Re: North Korean A3 code (Jim Dunnett)
Re: True Randomness & The Law Of Large Numbers (Jim Felling)
Re: North Korean A3 code (Paul Koning)
Re: Is initial permutation in DES necessary? (Paul Koning)
Re: S/MIME interoperability: 40 bits only? (Ian Goldberg)
Re: True Randomness & The Law Of Large Numbers ([EMAIL PROTECTED])
Re: Is initial permutation in DES necessary? (Paul Koning)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: North Korean A3 code
Date: Thu, 01 Apr 1999 20:11:38 GMT
Reply-To: Jim Dunnett
On Thu, 01 Apr 1999 17:04:08 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>[EMAIL PROTECTED] (Jim Dunnett) wrote, in part:
>
>>The Chinese also have a system which codes a subset of the
>>ideograms of Mandarin into 5-figure (letter?) groups.
>
>I know there's a system that takes Chinese characters into four digit
>groups: and the book Codebreaker in the Far East shows that the system also
>has a three-letter version. There is also a conversion of Chinese telegraph
>code into two 8-bit characters, but it is seldom used in comparison to
>GuoBiao and Big 5.
Thanks for that. I stand corrected: as you say it was four
digits.
Presumably GuoBiao and Big-5 are expanded (popular) updates.
Incidentally, anyone know where I could obtain a copy of an
old-fashioned merchant-shipping code, either to buy in book form
or to download?
--
Regards, Jim. | The English are much more likely to be
olympus%jimdee.prestel.co.uk | hypocritical than the Scots. Scots are
dynastic%cwcom.net | often rude and blunt, but they are at
nordland%aol.com | at least truthful.
marula%zdnetmail.com | - Muriel Spark, Author & Loyal Scot.
Pgp key: pgpkeys.mit.edu:11371
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 01 Apr 1999 16:03:46 -0600
"R. Knauer" wrote:
> On Thu, 01 Apr 1999 09:58:42 -0600, Jim Felling
> <[EMAIL PROTECTED]> wrote:
>
> >> >Here n=1000000 p=q=0.5, so the standard deviation is
> >> >500 units. Very few particles will be 20 standard deviations
> >> >or more from the mean.
>
> >> But more than a negligible number of particles will be outside +- 5%
> >> of the mean
>
> >The mean is 500000 5% of that is 25000, so within 5% of the mean is
> >equivalent to between 475000 and 525000. The SD is 500
>
> Hmm.. I am growing suspicious that we are taking about two completely
> different things. Maybe there is a world of difference between
> probability theory and statistical theory.
>
Nope -- I think it is physics vs engineering -- same rules, same phenomena, very
different world views due to what is and is not taken as an axiom.
>
> I am talking about the distribution of sequence bias (measured by Sn)
> and you are talking about the distribution of the number of sequences.
> In my distribution, the mean is zero, since for every sequence of +
> bias, there is a bitwise complement with - bias. My distribution
> displays the spatial distribution of particles undergoing diffusion,
> which also is related to the bias Sn.
Axioms:
Sn(X) = Left count - right count ( for sequence X of length N).
N=10^6
1)As this is a binomial process the resultant data should assume the form of a
standard Gausian bell curve with the mean set at 0 and the Standard deviation
being equal to 500.
2) Thus for 99.9% of all X -1500<=Sn(X)<=1500. So 99.9% of all X are within
0.15% of the mean
3) and also -10000<=Sn(X)<=10000 for almost all sequences. The odds of this
not being true are astronomical.
Since the probability of Sn(X) being greater than K drops with increasing K
p(Sn(X)=10000) > p(Sn(X)=K)
if k>10000
and p(Sn(X) =10000) = ((10^6)! / ( (10^6-10^4)! *(10^4)!)) /2^N <
( (10^6)!/((10^6-10^4)!) /2^N
< (10^6)^(10^4) / 2^N <
10^ (6*10^4) / 10^(2.5*10^5) =10^(-1.9*10^5)
then p(Sn(X) >10000) < 10^6 *10^(-1.9*10^5) < 10^(-1.8* 10^5)
thus p(Sn(X) < -10000 OR Sn(X) >10000) <2*10^(-180000). I'll take those odds.
>
> I am at a complete loss to understand what you have just said. What
> are the random variables you are quantifying with that distribution?
>
> >In the ensemble view. A TRNG randomly 'picks' a sequence out of the pool of
> >all possible sequences.
>
> Yes, and it does it in a manner that is equiprobable too.
>
> >The odds of it picking such a biased sequence is so
> >vanishingly small that it would be much more likely that the device is bad
> >than that the sequence was legitimately produced by a working TRNG.( not
> >impossible, but vanishingly tiny odds)
>
> I do not see how your distribution above has anything to do with an
> assessment of bias.
>
remove biased from my above statement. A better phrasing of my assertion is that
random walks ending more than 1% of N from 0 are so vanishingly rare that it is
much more likely that what is being evaluated is not producing truly random
output.
>
> In the ensemble, there is a significant number of sequences with
> "abnormal" bias. Feller (op. cit.) spends whole chapters in his book
> on introductory probability theory exposing many of them. How you can
> claim that a biased sequence in general is vanishingly unlikely to be
> part of the total ensemble is beyond me.
>
> I suspect that you are claiming that the biased sequences are small in
> number when compared to the worst case of bias, namely a run. I will
> agree that most strings have small bias compared to the worst case.
> What I am unwilling to do is accept that such makes those "small
> biased" sequences have an insignificant amount of bias compared to the
> expected bias for the ensemble.
>
> Let's say that we are talking about a 1000 step random walk. There are
> 2^1000 possible paths, and two of them are at the extreme of +- 1000
> steps. Yes, it is true than compared to a bias of 100 steps, most
> sequences are "close to the origin". I have repeatedly said that the
> Gaussian is a very broad distribution.
>
> But just because most sequences are not near 1000 step extremes, does
> not mean that most sequences are very close to the expectation bias of
> zero. As Feller points out, a non-trivial number of sequences are a
> considerable distance from zero, although they are also a considerable
> distance from the maximum too. I agree that there are more near zeros,
> and that the fraction decreases as you move away from the origin, but
> it does not fall off dramatically - it falls off more gradually.
>
> Whatever is driving you to make that claim above is at the very heart
> of this issue. So if you can explain why you believe you can make such
> a determination, maybe we will get closer to understanding why people
> insist that statistical tests are valid in determining with reasonable
> certainty that a TRNG is not truly random.
>
> You correctly assert that most sequences are far away from the
> maximum. But does that imply that they are extremely close to the
> mean? If that were the case, then diffusion woud never occur (and I
> realize that diffusion works because the extremes are extremely far
> away from the mean, as Brian Olsen pointed out the other day).
>
> >I'd probably still kick it out. The odds of a TRNG picking such a sequence
> >'by chance' is roughly than 10^9 / 2^100 < 10^-27. It can happen, but I'll
> >still bet against it.
>
> I would use it as a very strong diagnostic indication of a very likely
> malfunctioning TRNG - but no more than that.
Either I have a 1)defective TRNG that just fooled me on my examination or
2) a working TRNG that generated statistically unlikely output.
Given those are the only 2 possible hypothesis Occams razor would make me choose
hypothesis 1 and I therefore would kick out.
>
>
> Bob Knauer
>
> "The laws in this city are clearly racist. All laws are racist.
> The law of gravity is racist."
> - Marion Barry, Mayor of Washington DC
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: North Korean A3 code
Date: Wed, 31 Mar 1999 18:03:06 -0500
Jim Dunnett wrote:
>
> On Wed, 31 Mar 1999 13:08:58 +0900, Eric Hildum
> <[EMAIL PROTECTED]> wrote:
>
> >In today's Japan Times, there was a discussion of a 1978 kidnapping of a
> >Japanese woman from Japan by North Korea [this is one of about a dozen suspected
> >cases over the last twentyfive years]. The article discussed a North Korean code
> >called "A3," described as a five digit number for each hangul (?) character.
> >Given the recent discussion on this newsgroup, it would seem to me that such a
> >code system would be relatively easy to break -- are there any references on the
> >internet to this system? I assume that as so much is known about this code that
> >it has in fact been broken....
>
> The Chinese also have a system which codes a subset of the
> ideograms of Mandarin into 5-figure (letter?) groups.
>
> It's hardly a cipher, merely a means of telegraphing ideograms!
>
> Perhaps the Korean system you refer to is no more than that.
That could be. Korean is a bit like Japanese, in that it has a syllable
writing system (Hangul, different from Kana in that you build the
character out of pieces to indicate the vowels and consonants of the
syllable) as well as ideograms like Chinese (or like Kanji). I think
they have gone further than Japanese in that the syllabic/alphabetic
system is used for almost everything, but nevertheless Koreans do learn
the other system and I think it is still used to some extent. Possibly
the usage patterns are different in the North.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Is initial permutation in DES necessary?
Date: Thu, 01 Apr 1999 09:33:44 -0500
Sundial Services wrote:
>
> Paul Koning wrote:
> >
> > "Douglas A. Gwyn" wrote:
> > >
> > > The key wasn't too short; it outlasted its design lifetime!
> >
> > I very much doubt that. Diffie and Hellman made a persuasive argument
> > that the EFF Cracker could have been built by a well-heeled
> > government agency right back when DES was first approved. Even
> > if they were slightly optimistic, it seems an excellent bet that
> > such a machine was built within 5 years or so from that date.
>
> In retrospect, DES probably =was= a cipher that was a great deal
> stronger than anyone at the time =could= have come up with. Techniques
> such as differential cryptanalysis did not come to the public's
> attention for many years thereafter. In retrospect, IBM and NSA did a
> hell of a job back then.
> ...
> Did they produce a very effective and long-lasting cipher that's more
> than enough for most commercial purposes (especially of that era?).
> Yes, I think they did. Your tax dollars at work?
Perhaps "good enough for the time". But "stronger than anyone could
have come up with"? Clearly not, because a system with the same
properties but a civilized key size would have been better. And
of course that was the original proposal; the key was shortened
later on.
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Xedia Corporation, 119 Russell Street, Littleton, MA 01460, USA
! phone: +1 978 952 6000 ext 115, fax: +1 978 952 6090
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "Be wary of strong drink. It can make you shoot at tax collectors
! -- and miss!"
! -- Robert A. Heinlein, "The Notebooks of Lazarus Long"
! in "Time Enough for Love"
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: S/MIME interoperability: 40 bits only?
Date: 1 Apr 1999 22:01:18 GMT
In article <[EMAIL PROTECTED]>,
Peter Pearson <[EMAIL PROTECTED]> wrote:
>I'm trying to use Netscape's 4.02 Communicator to
>exchange encrypted email with a correspondent who uses
>a Microsoft mail reader. I have deselected all ciphers
>except 168-bit 3DES, and my correspondent has specified
>168-bit 3DES for outgoing messages, but when I read
>email from him, Communicator says it was encrypted with
>40-bit RC2, and similarly when he reads email from me.
>
>Is this pathetic capability all we can expect from these
>products, or am I overlooking some important setting?
>Is there, at least, a way to tell Communicator that if
>it's going to encrypt an outgoing message with a joke
>cipher instead of the cipher I asked for, it should at
>least %$#$in warn me?
>
>Much thanks to any who can shed light for me.
Edit the Communicator binary. Find the table the looks like this (search for
"BITS:")
MAX-GEN-KEY-BITS: 2048
PKCS12-DES-EDE3: true
PKCS12-RC2-128: true
PKCS12-RC4-128: true
PKCS12-DES-56: true
PKCS12-RC2-40: true
PKCS12-RC4-40: true
PKCS12-NULL: true
SSL2-RC4-128-WITH-MD5: true
SSL2-RC2-128-CBC-WITH-MD5: true
SSL2-DES-168-EDE3-CBC-WITH-MD5: true
SSL2-DES-56-CBC-WITH-MD5: true
SSL2-RC4-128-EXPORT40-WITH-MD5: true
SSL2-RC2-128-CBC-EXPORT40-WITH-MD5: true
SSL3-FORTEZZA-DMS-WITH-FORTEZZA-CBC-SHA: true
SSL3-FORTEZZA-DMS-WITH-RC4-128-SHA: true
SSL3-RSA-WITH-RC4-128-MD5: true
SSL3-RSA-WITH-3DES-EDE-CBC-SHA: true
SSL3-RSA-WITH-DES-CBC-SHA: true
SSL3-RSA-WITH-RC4-40-MD5: true
SSL3-RSA-WITH-RC2-CBC-40-MD5: true
SSL3-FORTEZZA-DMS-WITH-NULL-SHA: true
SSL3-RSA-WITH-NULL-MD5: true
SMIME-FORTEZZA: true
SMIME-DES-EDE3: true
SMIME-RC2-CBC-128: true
SMIME-RC5PAD-64-16-128: true
SMIME-DES-CBC: true
SMIME-RC2-CBC-64: true
SMIME-RC5PAD-64-16-64: true
SMIME-RC2-CBC-40: true
SMIME-RC5PAD-64-16-40: true
(Your spacing may be different; 10 points to the first one that can figure out
why the above example is the way it is.)
Change the entries for crypto you don't want from " true" to "false". Note
that you'll need to keep the length the same, so change the last space before
the "true" to 'f', the 't' in "true" to 'a', etc.
That should probably do what you want (note: I haven't tested this, of course;
that would violate the License Agreement, probably) for Netscape <= 4.06
and maybe also 4.07 and 4.08.
- Ian
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 01 Apr 1999 22:38:43 GMT
rcktexas wrote:
> On 31 Mar 1999 21:22:47 GMT, [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
> wrote:
>
> >: Everyone knows that if I open a perfume bottle in the middle
> >: of the room, the odor will spread all over the room with time.
>
> >But by that time n units is far beyond the walls of the room.
>
> Yes, that is indeed correct. The Gaussian falls off very slowly. But
> not so slowly that the perfume odor stays next to the bottle forever.
Don't forget the issue - I had claimed,
>>> As n grows large, a greater and greater fraction of
>>> the ink molecules will be within 0.05*n of where they started.
and you responded,
>> That defies physical intuition, as well as the rules for mixing
>> entropy.
No one said the odor would stay next to the bottle. You claimed
a large portion would be farther than 0.05*n for large n, such as
a million. That claim is wrong. You say the odor will fill the
room. Maybe, but the walls of the room are not within 0.05*n at
that point, so the observation is irrelevant.
> >Again, you've forgotten what n units means. It's how far a particle
> >would have traveled if every step were leftward or every step
> >rightward. It has nothing to do with where drywall is hung.
>
> Yes, that is correct. n units measures the farthest extent of the
> random walk.
Good. Now do you see that reaching the walls of the room is not
at all the same as reaching 0.05*n ?
>
> >As others have pointed out, the two dimensional case yields
> >a binomial distribution, so the standard deviation is
> >sqrt(npq).
>
> The one dimensional case also yields a binomial distribution, because
> a UBP yields the binomial distribution.
In fact I had actually meant to write "two directional".
> >Here n=1000000 p=q=0.5, so the standard deviation is
> >500 units. Very few particles will be 20 standard deviations
> >or more from the mean.
>
> But more than a negligible number of particles will be outside +- 5%
> of the mean.
We could define the starting point as sitting at zero or at a
googol. Percent of the mean is a meaningless number - it's the
percent of the n trials that's important.
> >: 10,000 units is only 1% of 1,000,000 units, so the probability is very
> >: small.
>
> >You've misinterpreted the numbers.
>
> How?
Feller's point in no way implies that a large portion of molecules
will be farther than 10,000 units from the mean after a million
unbiased leftward/rightward events.
In fact 10,000 units at n=1000000 is 20 standard deviations; 0.05*n
is 100 standard deviations. Even with a gallon of perfume, we expect
_no_ particles that far out.
> >: But others here are attempting to equate the
> >: frequency with the probability for finite sequences. Therein lies the
> >: error.
>
> >The only one I saw doing that was you.
>
> I do not recall ever confusing frequency for a finite process with
> probability.
You wrote
>>>> Because the finite random walk points out that a significant
>>>> number of sequences have "abnormally" large bias as measured
>>>> by S
S measures the frequency. The bias is in the probability.
> >You don't measure bias, you measure frequency. And if what
> >you find looking at 100 bits is 100 zeros, we can safely
> >reject the candidate RNG based on that test alone.
>
> Are you saying that a run of 100 zeros conclusively demonstrates that
> a TRNG is malfunctioning? How about a run of 100 zeros in a sequence
> of 10^9 bits?
Yes. Reject the candidate TRNG.
> And how do you account for the fact that in a large uniform random
> walk in one dimension, most of the paths rarely end at or near the
> origin?
I account for it by working quantitatively. After a million steps I
don't expect most of them to end up within 100 of the origin. I do
expect them to end within 0.05*1000000 of the origin.
> >Look at your 100 zeros out of 100 bits.
>
> I do not recall using that exact expression. But never mind.
>
> >If we make any
> >reasonable estimate of the probability our candidate RNG is
> >defective in such a way as to produce this outcome, say one in
> >a trillion, then Bayes' theorem tells us there's no significant
> >chance the RNG is in fact unbiased.
>
> Can you elaborate on each key point in that analysis by giving
> specifics of how you go from the beginning assumptions to the final
> conclusion.
Yes, but let's solve one problem at a time. You want precise
quantitative arguments, I ask at least that you follow those
given. Under our binomial distribution with p=q=0.5 and
n=1000000, the number 0.05*n is 100 standard deviations. We
do not expect particles outside of 100, or even 20 standard
deviations from the mean. Your response to this quantitative
argument was an example of a room full of perfume smell, even
though you have no reason to equate the bounds on the room with
the actual distance in question. Do you now see why the
conclusion you drew from this example is wrong?
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Is initial permutation in DES necessary?
Date: Thu, 01 Apr 1999 09:34:48 -0500
Sam Simpson wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Paul,
>
> The paper "Cryptanalysis of the CFB mode of the DES with a
> reduced number of rounds" by B.Preneel, M. Nuttin, V. Rijmen, J.
> Buelens explains how the final permutation prevents some attacks
> against DES in CFB mode.
>
> Wouldn't the final permutation also prevent some attacks against
> 3DES in CFB mode?
I suppose so; I tend to forget about modes other than CBC...
paul
------------------------------
** 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
******************************
