Cryptography-Digest Digest #573, Volume #10 Tue, 16 Nov 99 04:13:04 EST
Contents:
Re: more about the random number generator (Scott Nelson)
Re: EncryptedChat V2 Dead ? (Jerry Coffin)
Re: RSA question (David A Molnar)
Re: more about the random number generator (William Rowden)
Re: RSA question (Scott Fluhrer)
Re: Nova program on cryptanalysis -- also cipher contest (William Rowden)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (john baez)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (john baez)
Re: Scientific Progress and the NSA
Re: Modified DH - ok? (Hideo Shimizu)
Re: Scientific Progress and the NSA (Bill Unruh)
Re: Proposal: Inexpensive Method of "True Random Data" Generation ("Trevor Jackson,
III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: more about the random number generator
Reply-To: [EMAIL PROTECTED]
Date: Tue, 16 Nov 1999 04:42:56 GMT
On Tue, 16 Nov 1999, Tom St Denis <[EMAIL PROTECTED]> wrote:
>I got a program from http://www.fourmilab.ch/random/
>
>to perform pseudo-randomness tests on files. I made a file using my
>rng [based on the winrng] until I got bored... here are the results
>[and if dejanews messes up the following lines, I can re-email it in
>private].
>
>Entropy = 1.000000 bits per bit.
>
>Optimum compression would reduce the size
>of this 417792 bit file by 0 percent.
>
>Chi square distribution for 417792 samples is 0.14, and randomly
>would exceed this value 50.00 percent of the times.
>
>Arithmetic mean value of data bits is 0.5003 (0.5 = random).
>Monte Carlo value for Pi is 3.136948529 (error 0.15 percent).
>Serial correlation coefficient is 0.001254 (totally uncorrelated = 0.0).
>
>
>
>Is this good or bad? From what I read at the site this is really good
>for a first pass at it...
>
These sorts of tests can't really be "good" only "not bad."
It's "not bad."
The issue I have with the RNG in question isn't "does it
perform well on some systems." It's "how well it works
on a variety of systems, and can you predict under what
conditions (if any) it will fail." I.e. If there are no
other tasks running, it's fails rather spectacularly.
Are there any other, more realistic, conditions which
would cause it to fail? Hi or low speed computers,
running in virtual mode, if a task consumes huge amounts
of processor time, etc.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: EncryptedChat V2 Dead ?
Date: Mon, 15 Nov 1999 22:32:26 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Can we use factor.exe to test the strength of PGP? In other words,
> can we make PGP output a composite number which it would typically use
>
> and then submit that number to factor.exe? If PGP refuse to output
> the number (even when asked), can the number be sucked out?
The number is part of the public key, so PGP has to be able to give it
out.
> Is there an upper limit to the numbers which factor.exe can handle?
At least as far as RSA goes the limit is a practical one, not a
theoretical one.
> I ask because factor.exe sometimes gave negative factors to a positive
> test number.
At least the program I'm talking about uses the MIRACL library for its
underlying math. This works correctly with numbers that are thousands
of digits long.
To factor numbers in that range, you'd want a more sophisticated
program using the GNFS algorithm (and wish for something a lot better
still, though AFAIK, such a thing doesn't exist right now) and a few
centuries of time on each of a few hundred of the fastest computers on
earth. Fortunately, during those centuries, computer technology would
still progress, since for the final matrix reduction step of GNFS,
you'd probably need more RAM than has been produced up 'til now on all
of planet earth in the entire history of computing...
I suspect if you ran into such a problem, it was either with an old
version of the program, or else with some other program entirely that
happens to have the same name (it's certainly an obvious name).
If there really IS a number that gives a negative result, I'm quite
certain the program's authors would like to know about it so they can
find and fix the problem.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA question
Date: 16 Nov 1999 05:49:33 GMT
Kentos Denvis <[EMAIL PROTECTED]> wrote:
> code. but being as there are only 256 positions in a byte, couldnt you just
> run a plaintext attack the the encryption equation to get the original
> plaintext?
You're assuming that we're encrypting byte by byte. In practice, you'd
use a multiprecision integer of the same length as the modulus. So that's
1024 bits or so. Now the guessed-plaintext attack you describe takes
2^1024 operations.
Then it's not a problem.
You *are* correct, and kudos for noticing it -- but it can be fixed.
-David
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Tue, 16 Nov 1999 05:56:17 GMT
I'll risk a response. Given the traffic on RNG and the current RFD, I'm
certain there are regulars who can correct my misconceptions and answer
my questions.
In article <80qh8s$46b$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I got a program from http://www.fourmilab.ch/random/
> to perform pseudo-randomness tests on files.
> I made a file using my rng [based on the winrng] until I got bored...
The *cryptographic* security of a PRNG is generally described in
complexity-theoretic terms. My first question is therefore "What's the
algorithm?" Security relies on the presumed intractability of an
underlying number-theoretic problem.
Nevertheless, statistical tests (e.g., FIPS 140-1) can be used in
security applications.
> here are the results
I assume these are the program's results with the bitstream option.
> Entropy = 1.000000 bits per bit.
That's wonderful.
> Optimum compression would reduce the size of this 417792 bit file by 0
> percent.
Since this compression is based upon a reading frame of one bit, it
doesn't mean much at all. You'd get better compression information by
not using the bitstream option, or by attempting to compress the file.
(Look out! The compression/randomness thread could begin again.)
> Arithmetic mean value of data bits is 0.5003 (0.5 = random).
With 208771 zeros and 209021 ones, it passes the monobit or frequency
test at a higher confidence level than my chi-square table shows (and
good enough for FIPS 140-1).
> Chi square distribution for 417792 samples is 0.14, and randomly
> would exceed this value 50.00 percent of the times.
Oops. Maybe it's 208776 zeros and 20916 ones. The table option should
show this.
> Serial correlation coefficient is 0.001254 (totally uncorrelated =
> 0.0).
This looks good. I assume this is equivalent to a two-bit test, though
I don't know how to calculate one statistic from the other.
Since PRNGs have a period, an autocorrelation test for shifts greater
than one (which should be the serial correlation above) would be useful.
> Is this good or bad? From what I read at the site this is really good
> for a first pass at it...
I think it's a good first pass. Since it's an easy option to change,
I'd also try a poker test with m = 8, using the 8-bit byte option of the
program.
What does a runs test show? You could calculate the number of blocks of
ones or gaps of zeros of various lengths, e.g., 1 to 6 (you're a C
programmer, after all). What's the longest run in the file?
--
-William
Damages claimed for unsolicited commercial email (RCW19.86 & 47USC227)
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: RSA question
Date: Tue, 16 Nov 1999 06:09:24 GMT
In article <80qpfg$4at$[EMAIL PROTECTED]>,
"Kentos Denvis" <[EMAIL PROTECTED]> wrote:
>I was wondering about the supposed high security of RSA encryption. I mean I
>looked over the math behind it. specificly C = (T^E) mod PG, where C is the
>output encrypted text, T is the Input plaintext, E is the exponent, and PG
>is the modulus.
Correct
>
>Now the description of the articile I've seen said that it would take a
>computer eons to calculate the primes making up the modulus or the decryptor
>code. but being as there are only 256 positions in a byte, couldnt you just
>run a plaintext attack the the encryption equation to get the original
>plaintext?
>
>On the idea that PG and E are public and anyone knows them. by running the
>equation as T = 0 to 255 eventually the output should match the first byte
>in the encrypted file. then run this sequence on each subsequent byte untill
>each match. copy each T into a new output file and you should end with the
>original file.
Well, this would work, if the encryptor was silly enough to encrypt (without
padding) each byte separately. Two things:
1. RSA is almost never used to encrypt the text itself. For one, it's far
too slow. What's far more common id to encrypt a random key to a
symmetric algorithm (such as DES), and send that RSA encrypted random
DES key, along with the DES encrypted plaintext. That way (at least,
if you are encrypting much data at all), you get the speed of DES along
with the 'encryptor doesn't need to know the receiver's private key'
property of RSA
2. If RSA (or any other public key encryption method) is used to encrypt
a short message, you have to add random padding, just so that an
attacker can't do the attack you describe.
In general, intelligent users of RSA are careful to make sure that there
are so many possible plaintexts that it would take at least as long to
trial-encrypt them all as it would to just factor the modulus.
>
>Is this correct or am I just lost in math loops?
Summary: the attack would work, if the users of the system do not take
steps to make it impossible, which they (in practice) always do
--
poncho
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: Nova program on cryptanalysis -- also cipher contest
Date: Tue, 16 Nov 1999 06:05:04 GMT
In article <[EMAIL PROTECTED]>, Jim Gillogly <[EMAIL PROTECTED]>
wrote:
> I prepared a cipher contest for them with a flavor of WW2 hand
> ciphers
I like the contest, but so far have found cryptanalysis by hand
frustrating. Is anyone else working on this? I assume teams are
permitted.
> There's a two-week time frame.
I don't think I'm going to finish in time unless I have help (or I quit
my non-cryptological day job :-)). Is anyone interested?
> I won't be able to discuss attacks and solutions until after the
> contest ends, but do send in your solutions and explanations, and Nova
> will forward them on to me for checking.
Ahh, but the rest of us can discuss them.
--
-William
Damages claimed for unsolicited commercial email (RCW19.86 & 47USC227)
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (john baez)
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: 15 Nov 1999 22:26:16 -0800
In article <[EMAIL PROTECTED]>,
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>OK, so you cannot give an effective description of an incompressible string.
>What makes you believe that there are any strings that meet your definition
>of incompressibility?
First of all, the proof is in any good introduction to algorithmic
information theory - try Chaitin's book, for example. There are also
some nice introductions online.
Second of all, the proof is not hard. The basic idea was already
described in this thread: there just aren't enough short descriptions
to go around to give *all* strings descriptions shorter than the
strings themselves.
------------------------------
From: [EMAIL PROTECTED] (john baez)
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: 15 Nov 1999 22:29:40 -0800
In article <[EMAIL PROTECTED]>,
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>Thus there are distinguishing characterisitics of incompressible sequences
>vs stochastic sequences. Claiming one type as a synonym for the other is
>fundamentally flawed.
Right. The fact that people use the word "random" for both (in different
contexts) does not make them true synonyms.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Scientific Progress and the NSA
Date: 16 Nov 99 06:53:09 GMT
Jim Gillogly ([EMAIL PROTECTED]) wrote:
: Tim Tyler wrote:
: > Certainly we now know that public key cryptography was invented in
: > secret independently of the public community some years before the
: > rest of the world heard about it.
: Do we? Although Ellis & Cocks did also invent public key crypto, Ellis
: told Diffie that "You did more with it than we did."
It makes sense that they would have thought of it first, since until quite
recently, cryptography was for hobbyists and bankers outside their
precincts.
But a mathematician *could* have invented PKC in 1890, or someone could
have had the idea after watching Colossus: The Forbin Project the first
time. This was nearly a chance event.
That the intelligence community didn't make use of it, though, is,
although disappointing, not surprising. Even the open community took time
to realize that PKC was best used to pass keys.
And for the intelligence agencies to adopt microchips in encryption
devices took time, despite the fact they have access to the most advanced
electronics technology. So it took time before PKC could be used by them
in the way someone with the opportunity to have shared secrets of
unlimited size can still use it: to have a key that's generated inside a
sealed box, and protected from compromise.
: Granted that the non-classified community didn't know about diff crypt
: for some years after the classified community (including the IBM people
: who evidently invented it at LUCIFER/DES time). However, I find it quite
: credible that recent academic cryppies have come up with other attacks
: before their counterparts inside the Black Chambers. I think it likely
: that in many areas the gap has narrowed considerably. In others we
: probably still don't have a clue about technologies they're using.
I suspect one of their major advantages is that they've had time to unify
their knowledge of cryptography. To relate the possible attacks against
paper and pencil ciphers, and rotor machines, to what can be done against
block ciphers.
Thus, a clever idea like David Wagner's boomerang attack probably was
"obvious" to them, as it probably embodies a general principle that is on
their short list.
Or take Gordon Welchman's comment about the diagonal board in "The Hut Six
Story". I have a hard time seeing what general principle is embodied in
the diagonal board that could be used against anything except an Enigma.
: Sure. But if you think of them as gods you'll find it paralyzing.
: There just aren't that many Turings in the world.
That is one advantage they won't have. Until there is another war, while
the NSA will have many fine minds working for it, they likely will not, in
general, be able to hire the very finest minds. Yet, they've been blessed
with a few; Dr. Golomb comes to mind.
But while the very finest minds will be working on the problems that are
more recognized, the NSA will still be able to hire some very fine minds.
Not every mathematical genius is suited to academe; some are fascinated by
codebreaking; and there is also love of country.
Hundreds of fine minds, working on a subject that continues to capture the
attention of only a handful of outside academics, with the benefit of a
corpus of knowledge to which they alone have access.
Some of what they know will come as a surprise to us when it is
declassified 50 years from now, I think.
But does that make them gods? Should we be paralyzed? No.
The battle to make a system secure is a very difficult one, and the
attacker has the advantage of being able to strike in unexpected ways.
But the battle between the codemaker and codebreaker, thanks to the
microchip, is also an unequal one - in the opposite direction.
I can't guarantee that the NSA doesn't have new factoring and discrete log
algorithms that make public-key obsolete, for the simple reason that I
can't guarantee that, three months from now, such an algorithm won't be
published in a mathematical journal somewhere.
But when it comes to secret-key algorithms, the microchip means that it's
pretty trivial to pile complexity on top of complexity. Alternate block
cipher encipherments with layers of stream ciphers, transpositions, and
the like. Use gigantic keys. And the whole thing can probably be made to
execute in acceptable time on a VIC-20, never mind a Pentium, at least for
text E-mail.
They _are_ giants; but they are in a contest so unequal that a VIC-20 in
the hands of a codemaker is mightier than the largest Cray in the hands of
a codebreaker. And they are *very* seldom anyone's opponents. Most
civilian users of cryptography have to worry about hackers and crooks.
The trouble is, though, that 40-bit or 56-bit keys still won't cut it,
because hardware speeds keep improving, and brute-force search is
something you don't need to be an expert cryptanalyst to carry out. It is
this threat that should give us pause. I think it is enough to scale up
our designs moderately, using keys and block sizes that are larger than
seem necessary, and to mix algorithms, and to use algorithms in which
parts are well hidden; others would advocate more elaborate precautions.
Allowing a generous fudge factor...is not what I'd call paralysis.
John Savard
------------------------------
From: Hideo Shimizu <[EMAIL PROTECTED]>
Subject: Re: Modified DH - ok?
Date: Tue, 16 Nov 1999 15:45:45 +0900
We can compute secret value P from PtoQ*N^(-1) mod M and Q similar.
There is no secret, so I think this is not secure at all.
Hideo Shimizu
TAO Japan
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Scientific Progress and the NSA
Date: 16 Nov 1999 07:25:07 GMT
In <8R3Y3.747$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>>Actually, intelligence agencies have a severe handicap, and that is
>>their secrecy. Things go much much faster if you have a bunch of equally
>>smart people constantly looking over your shoulders for your stupid
> But:
> (1) The information flow is unidirectional: Agencies can
>learn from the outside world, but little info flows back out.
Unfortunately, that secrecy does not just extend to the outside world,
but also is inside the system as well. It would hardly do in a top
secret organisation for everyone to know what everyone else is doing.
Ie, their paranoia extends also to each other. What if your collegue at
the next desk is another Aimes? Do you really want him finding our about
this great new idea you have? This makes it hard both to learn from each
other and from the outside world. Much discovery is serendipity.
> (2) Isn't the NSA the largest employer of math PhDs? If
Remember that research is not the only job NSA has. Much of their
manpower is taken up by their primaryjob which is monitoring information
from the outside political and military world. Not in devising new
cryptosystems, etc.
>so, it would suggest that they do have lots of "smart people
>looking over their shoulders". And don't forget that, as opposed
No, they cannot have people looking over their shoulders. That person
looking might be a spy.
>to the outside world, all those guys do is work on NSA problems.
>(whereas a real world scientist is busy teaching, working on
>a bunch of random projects, etc.)
See above.
------------------------------
Date: Tue, 16 Nov 1999 02:32:37 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
john baez wrote:
> In article <[EMAIL PROTECTED]>,
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>
> >OK, so you cannot give an effective description of an incompressible string.
> >What makes you believe that there are any strings that meet your definition
> >of incompressibility?
>
> First of all, the proof is in any good introduction to algorithmic
> information theory - try Chaitin's book, for example. There are also
> some nice introductions online.
Hardly. There is a difference between the claim that there is no universal
compressor that can compress all possible sequences, which leads to the
conclusion that some sequences cannot be compressed, and the claim that a
particular, single, individual sequence is incompressible, which is trivially
false.
When you take the former out of context you get the latter.
>
>
> Second of all, the proof is not hard. The basic idea was already
> described in this thread: there just aren't enough short descriptions
> to go around to give *all* strings descriptions shorter than the
> strings themselves.
Of course. This treats each string as a member of the set. It is the set's
property that not all elements can be compressed. But any individual string
within any given set can be compressed -- at the expense of the other members of
the set.
By this distinction one can determine the (in)validity of the claim that
incompressibility is an intrinsic attribute of the individual strings rather than
a collective attribute of the set. The set is extrinsic to the individual
strings.
------------------------------
** 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
******************************
