Cryptography-Digest Digest #455, Volume #9 Fri, 23 Apr 99 20:13:02 EDT
Contents:
Re: PGP=NSA (what is it about crypto?) (Medical Electronics Lab)
Re: choosing g in DH (Doug Stell)
Re: Adequacy of FIPS-140 (John Briggs)
Re: Adequacy of FIPS-140 (R. Knauer)
Re: RSA-Myth (SCOTT19U.ZIP_GUY)
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: about analysis (let's see if I can explain this better...) (David Wagner)
Re: How long for export application? ("Douglas A. Gwyn")
Re: SHA-1 as f-function in Feistel construction (Paul Rubin)
Re: SHA-1 as f-function in Feistel construction (Paul Rubin)
Re: 128 bit DES ("Douglas A. Gwyn")
Re: Common Passowrds (Paul Rubin)
Re: RSA-Myth (Matthew Skala)
Re: Rijndael (Paul Koning)
Re: Can a Java or Active-x program get your keys?????? (Paul Koning)
Re: Block Cipher Question (Paul Koning)
Re: How long for export application? (Paul Koning)
Re: Question on confidence derived from cryptanalysis. ("Douglas A. Gwyn")
Rijndael ("Michael Scott")
----------------------------------------------------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: PGP=NSA (what is it about crypto?)
Date: Fri, 23 Apr 1999 12:31:42 -0500
[EMAIL PROTECTED] wrote:
> Bored enough to tilt at a windmill, maybe...
I heard a good one on the radio during the impeachment crap:
"Tilting at wind bags". Seems appropriate here sometimes...
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: choosing g in DH
Date: Fri, 23 Apr 1999 15:35:27 GMT
On 23 Apr 1999 01:33:49 GMT, Michael J. Fromberger
<[EMAIL PROTECTED]> wrote:
>Actually, the value of g should be chosen to be a primitive element
>(also known as a "generator") modulo p. A value g is a generator
>modulo p if the smallest value x such that g^x = 1 (mod p) is (p - 1).
G doesn't have to be the smallest such value, although it often is for
D-H.
If you look at the DSS/KEA parameter generation techniques, they
choose g to be "of order q" where q is a 160-bit prime. This is
considered to be of sufficiently large order to make attacks
unfeasible. The resulting g is a p-size number, rather than a small
number.
>Choosing your prime p so that (p - 1) / 2 is also prime has two
>advantages. First, it helps to thwart a couple of methods for
>increasing the efficiency of computing discrete logarithms when the
>value (p - 1) has several small prime factors. And second, it gives
>you a quick way to test whether some value g is a generator.
Correct. The best way to determine the order of g is to know the
factorization of p-1, as described below by the previous author You
will want to build up p-1 such that it contains one large prime
factor, as this will dominate the work-factor calculation for an
attack. Making (p-1)/2 a prime, gives you the largest possible prime
factor. Some will argue that this is overkill, that the choice of
primes becomes more sparse and that simply having one sufficiently
large prime is good enough.
>In particular, if (p - 1) / 2 is prime, then the factors of (p - 1)
>are q1 = 2 and q2 = (p - 1) / 2. To determine if some value g is
>primitive, compute:
>
> x1 = g^q1 (mod p)
> x2 = g^q2 (mod p)
>
>If either or both of x1 and x2 is congruent to 1 (mod p), then g is
>NOT primitive. Otherwise, it is.
Obviously, if p-1 has more than two factors, say q3 ... qn, then the
above method extends to include all the factors.
>There is some discussion of these matters in Menezes's _Handbook of
>Applied Cryptography_, and in Stinson's _Cryptography in Theory and
>Practise_, which also discusses some of the mathematics behind
>computing discrete logarithms.
And several chapters of HAC are available on-line. Two more on-line
chapters were announced by Menezes yesterday.
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: Adequacy of FIPS-140
Date: 23 Apr 99 11:45:01 -0400
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
writes:
> The algorithm can select any possible text using any possible offset.
Which leads (under any reasonable assumptions) to a non-uniform
distribution of possible outputs. Which is, using the terminology you
favor, non-random.
John Briggs [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Adequacy of FIPS-140
Date: Fri, 23 Apr 1999 18:34:44 GMT
Reply-To: [EMAIL PROTECTED]
On 23 Apr 99 11:45:01 -0400, [EMAIL PROTECTED] (John Briggs)
wrote:
>> The algorithm can select any possible text using any possible offset.
>Which leads (under any reasonable assumptions) to a non-uniform
>distribution of possible outputs. Which is, using the terminology you
>favor, non-random.
The underlying assumption is that hashing and strong mixing procedures
will flatten the distribution satisfactorily. I have tried to find
justification for that, but have not succeeded.
The only proof of the efficacy of anti-skewing was for the von Neumann
procedure where you cull out certain dibit groups, thereby leaving the
sequence unbiased.
Perhaps you can offer an analysis of why hashing and strong mixing
will not lead to a satisfactory flattening of the distribution.
BTW, in my original proposal a long time ago, I also suggested that
you use only the least significant bit of the text characters. Some
have suggested that such is not necessary.
Bob Knauer
"As nightfall does not come at once, neither does oppression. In both
instances, there's a twilight where everything remains seemingly unchanged,
and it is in such twilight that we must be aware of change in the air,
however slight, lest we become unwitting victims of the darkness."
-- Supreme Court Justice William O. Douglas
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: RSA-Myth
Date: Fri, 23 Apr 1999 19:54:50 GMT
In article <7fqhuv$eke$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> What is RSA approach?
> All you know, what is RSA encryption. Let us think about
> implementations. All known quick prime numbers generator
> algorithms deal with a probability, that a candidate is a
> prime number. The low is: how much time is needed to generate
> quasi primes used for business RSA encryption, the same order
> of time using same algorithms is needed for RSA modulus
> decomposition. This provides us with security with proportion
> of null to billion. Would an RSA-PGP vendor spend billion of
> years for generating of huge primes, it would take the same
> order of time for Brute Force decomposition attacks. But this
> is not the case. All RSA and RSA-PGP approach are mystification.
> From nothing goes nothing. Due to my opinion RSA and RSA-PGP are
> security spam.
>
> Na, Bob Silverman was kannst du jtzt sagen?
>
> Alex
>
> www.online.de/home/aernst
>
Alex
I to think RSA via PGP or similar is weak. But I think
just because the generators are fast that does not make it
weak. It is weak either because there is a mathematical
break in the whole method or the Generators that are used
are such that the NSA can take advantage of the weaknesses
that they themselves may have been put in them.
PGP program should come with source code and an interface
that allows a user to build his own Public Key from the
primes of his choice. But this would not happen for two
reasons. One the Spooks may have to guess harder when
breaking a key. Two the public will be told that they are
to stupid to create good keys on there own and that we
should all stay stupid and trust corparate america.
David Scott
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
to email me use address on WEB PAGE
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Fri, 23 Apr 1999 22:34:08 GMT
Mok-Kong Shen wrote:
> > I said you need to read the book, because that is the only way to get
> > the answer to your question.
> That clearly means that you also don't know the answer. Hence
> we have to drop that out of our current discussion!
In this instance I'll support R. Knauer: If you want to know what
Feller said, the only reliable way to know is to read Feller's book.
> In the previous post I have taken much time to write long paragraphs
> to stress that IF you consider the currently available statistical
> tests are 'simplistic', no good, error-prone, or having whatever
> other defects/disadvantages you discern, THEN please be kind and
> good enough ... to formulate your arguments in a way that
> researchers in statistics could well and unambigiously understand ...
A very long sentence! I think much more simply: If R. Knauer does
not like the FIPS-140 monobit test for RNG testing, what test *would*
he like? Experience has shown that we can weed out a large number
of defective RNGs using such tests as those in FIPS-140. I'd rather
have a battery of such tests than nothing at all.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: about analysis (let's see if I can explain this better...)
Date: 23 Apr 1999 08:18:56 -0700
In article <7fpl9r$j07$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
> Let's say I had an algorithm (A to D = input)
>
> for r = 0 to rounds
> A = A + ((B xor (D * S[2 * r])) <<< B)
> C = C + ((D xor (B * S[2 * r + 1])) <<< D)
>
> (B,C,D,A) = (A,B,C,D)
> next r
Look at differential cryptanalysis.
For instance, if every S[i] is odd, then flipping the high bit
of B and D gives a differential characteristic of probability 1.
This gives a class of weak keys (1 in 2^{2*rounds} is weak).
Here's another example of a differential characteristic.
Look at low 5 bits of each register. If A = B = C = D = 0 mod 32,
then the rotation amounts in the first round are zero. In fact,
if you trace it out, this will remain true for all rounds. So in
this case you can flip any of the high 27 bits of each register
and get a differential characteristic that stays confined to the
high 27 bits of the registers and propagates nicely.
The key weakness is in the multiplication. If D is even, the
low bit of the subkey S[2r] doesn't matter. If S[2r] is even,
the low bit of D doesn't matter. etc.
If you follow these types of clues, you'll find that the cipher
is very weak.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How long for export application?
Date: Fri, 23 Apr 1999 22:55:26 GMT
Phil Howard wrote:
> I guess is that the way the bureaucracy works there, is that no one
> person has the authority to actually approve anything.
Assuming there is a relevant regulation, the request is actually
processed by a readily-determinable staffer. Since I don't know
what requires the "classification request", I don't know how it
should be processed. I think all he's seeking is export
permission.
> Either that, or they're still waiting for your 3rd grade teacher to
> return the form asking about your private life.
No background investigation is run for such requests.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: SHA-1 as f-function in Feistel construction
Date: Fri, 23 Apr 1999 15:27:09 GMT
In article <[EMAIL PROTECTED]>, RDJ <> wrote:
>I'm wondering how effective the scheme described in the subject might
>be? For instance: using 256 bit blocks, the f-function would return
>the first 128 bits of the hash of the right-half of the data block
>and a subkey.
>
>just a thought I'm just learning about cryptography, so please pardon
>my naive musings.
Yes this is a good scheme if you run it for four rounds ("Luby-
Rackoff construction"). Doing it for just 2 or 3 rounds has some
weaknesses that might or might not be important depending on your
application. Look in Applied Cryptography under "Karn" or "Luby-
Rackoff".
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: SHA-1 as f-function in Feistel construction
Date: Fri, 23 Apr 1999 15:32:37 GMT
In article <7fptst$r0u$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
>> I'm wondering how effective the scheme described in the subject
>> might be? For instance: using 256 bit blocks, the f-function would
>> return the first 128 bits of the hash of the right-half of the data
>> block and a subkey.
>>
>I think it would be too slow to be practical.
Well, for each block of Luby-Rackoff you're doing 4*80=320 SHA rounds,
each of which is maybe comparable to a DES round in speed; and you're
encrypting 5x as large a block (320 bits instead of 64 bits), so
it's like doing 64 rounds of DES per 64 bits of data. By comparison,
in triple-DES you do 48 rounds per 64 bits. So you're looking at
something roughly comparable to 3DES. That's fast enough for most
purposes.
>Also, if I may ask: How would you invert the Hash to decrypt?
In a Feistel cipher you don't need to invert the F function.
That's not how they work. (See DES, for example).
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 128 bit DES
Date: Fri, 23 Apr 1999 23:07:10 GMT
[EMAIL PROTECTED] wrote:
> DES only has a 56 bit key, so double des is 112. 3DES or triple
> des is considered secure but there are better ciphers check out ...
"Better" how?
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Common Passowrds
Date: Fri, 23 Apr 1999 15:58:44 GMT
Nathan Christiansen <[EMAIL PROTECTED]> wrote:
>What I am looking for is a list that contains what they use as their password.
>For Example:
>
>1. Spouse's name.
>2. Spouse's name backwards.
>3. Social Security Number.
>
>I'm helping a friend in the middle of a messy court case to view some
>password protected Word 97 files so that they can be admitted as
>evidence (instead of just hearsay).
I think some studies have shown that maybe 50% of carelessly chosen
paswords fall into these types of categories. If the opponent was
careful at all, you'll never guess the password. If s/he was careless,
your chances are still not that great.
Word 97 uses RC4 encryption with a 40 bit key. You're probably better
off attacking that directly.
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: RSA-Myth
Date: 23 Apr 1999 14:43:08 -0700
In article <7fqhuv$eke$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>implementations. All known quick prime numbers generator
>algorithms deal with a probability, that a candidate is a
>prime number. The low is: how much time is needed to generate
You seem to be suggesting that since we only have probabilistic primality
tests, and to *prove* a number prime we would have to spend as much time
as we'd spend to factor it, therefore algorithms that depend upon our
numbers being prime, aren't secure.
There are several flaws with that analysis.
First of all, what is "security"? Even if you could guarantee that an RSA
modulus had exactly two prime factors, both large the way they're supposed
to be, there would still be a probability of the key failing every time
it's used: there's some chance that the given message or whatever happens
to have a common factor with the modulus. Then the key is broken. This
chance is very small, but we can make our probabilistic primality test
strong enough that the key itself is likely to fall to random chance much
more often than the primality test.
Second, we *don't* only have probabilistic primality tests. We have proof
algorithms as well. We can find large numbers that we're certain are
prime, in much less time than the time to factor similar-sized numbers.
It may take a few minutes rather than a fraction of a second to prove
primality for a crypto-sized number instead of doing a probabilistic test,
but it's still a lot faster than attempting to factor the number.
Third, even if we did have to do factoring to test numbers for primality,
with RSA at least it'd still be faster: with, say a 1024-bit key, you'd
have to do two 512-bit factorizations. That's a lot easier than doing one
1024-bit factorization, and as the numbers get bigger the gap between two
half-size factorizations and one full-size factorization can be made as
large as you want.
--
Matthew Skala Ansuz BBS (250) 472-3169 http://www.islandnet.com/~mskala/
GOD HATES SPAM
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Rijndael
Date: Thu, 22 Apr 1999 12:06:39 -0400
Paul Gover wrote:
>
> Paul Koning wrote:
> > It's two syllables. The first one requires a sound not found in
> > most languages. For a reasonable approximation, try "rhine-dahl".
>
> Am I right in vaguely recalling that "ij" actually came about as a
> typesetter's approximation to "y" with a dieresis (") over it, so
> the sound is a modified "y"?
More the other way around.
Back in the days before typewriters in Holland came with a key for
the letter ij, people would sometimes write i then j but that looked
ugly, and sometimes they would put a dieresis on y. But neither is
really right.
Sometimes ij is called a ligature. That doesn't make any sense
because ligatures are visual things, they sound the same as the
component letters. And ij does not sound like i then j!
It's best to think it as just a letter that just happens
to look a bit odd. Certainly that matches how kids learn it
(it's the letter just before z in the alphabet. And y is viewed as
ij with the dots left off...).
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: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Can a Java or Active-x program get your keys??????
Date: Thu, 22 Apr 1999 14:23:37 -0400
THOMAS wrote:
>
> x-no-archive:yes
>
> Can a Java or Active-x program get your keys??????
> Most people store the PGP keys and passpharse on their harddisk.
> Can a person or government fetch those keyrings using a smart Java or
> Active-X script downloaded from the net or maybe something hidden in
> your operating system?
I think the answers are: Java *supposedly* not; activeX yes. So avoid
the latter.
Also, anyone who stores the passphrase on their hard drive needs to
have his head examined.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Block Cipher Question
Date: Fri, 23 Apr 1999 14:05:01 -0400
[EMAIL PROTECTED] wrote:
>
> In article <7fjbud$ubk$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >
> > > Is there a block cipher algorithm that can be implemented using a 16-bit
> > block
> > > size?
> >
> > It could be done, but probably only securely as a OFB or stream cipher.
> >
> > What is the goal? Maybe we could help better, if you explained the situation.
>
> I've been looking into devices that fully encrypt computer hard drives.
> Since the IDE bus is only 16-bits wide, I was wondering if there was a block
> cipher algorithm that could be implemented using a 16-bit block size. If
> there's not, and the device buffers the data is buffered during transmission,
> then this would generate a degredation in performance.
Not in any way that matters. There's plenty of buffering going on in
disks,
in amounts far larger than a few bytes.
I'd suggest using a standard cypher (3DES or some other strong block
cypher) with standard 64 bit block size. Buffer 4 cycles at a time and
do the crypto. The fifo latency added by that is going to be entirely
irrelevant.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: How long for export application?
Date: Thu, 22 Apr 1999 12:10:30 -0400
Dale Mosby wrote:
>
> Does anyone have a recent data point for the time required
> to get a classification request run though the system? (A question
> for USA readers of course.)
>
> Feb 2nd an application for "Classification Request" went to the
> Bureau of Export Administration. It has been with the NSA since
> February 26th. As of April 12 BXA can't tell me anything other
> than "it's with NSA". All I'm trying to do is get approval to change
> a 40 bit DES algorithm to 56 bit DES. This has to be the most
> straightforward request that could be submitted. Has anyone
> run something through recently? I'd love to know what sort
> of turn-around time people have experienced.
8 weeks is the spec, if I remember right. We just had a few
go through in that or a few weeks longer.
It's not clear that straightforwardness is a big help, unfortunately.
paul
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Fri, 23 Apr 1999 22:46:33 GMT
Earth Wolf wrote:
> Remember Pearl Harbour, where warning of the impending attack
> arrived by messenger amid the smoking aftermath?
That's not what happened. The Japanese cleverly misled our
intelligence analysts into believing that their fleet was still
in home waters. What indication we had was that hostilities were
about to commence, *not* that Pearl would be the actual target.
That's the "executive summary" of the outcome of a massive
Congressional investigation, record of which are available in
the National Archives II (Modern Military History branch).
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Rijndael
Date: Fri, 23 Apr 1999 18:00:13 +0100
The world may not need another free implemention of the Rijndael cipher (one
of the AES favourites), but here is one at
ftp://ftp.compapp.dcu.ie/pub/crypto/rijndael.c
This is a full implementation, and is written for clarity rather than speed.
It may be a good starting point for anyone who wants to implement it in
assembly language for a particular architecture in conjunction with the
official documentation. It is self-contained - simply compile and run. A
small driver main program is included.
--
Mike Scott
=========================================
Fastest is best. MIRACL multiprecision C/C++ library for big number
cryptography
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip
------------------------------
** 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
******************************
