Cryptography-Digest Digest #577, Volume #12 Thu, 31 Aug 00 03:13:01 EDT
Contents:
Re: blowfish problem ("Douglas A. Gwyn")
Re: Idea for creating primes ("Scott Fluhrer")
Re: PGP 6.5.8 test: That's NOT enough !!! (Philip Stromer)
Re: PRNG Test Theory (Benjamin Goldberg)
Re: PGP 6.5.8 test: That's NOT enough !!! (Rich Wales)
Re: Serious PGP v5 & v6 bug! (Shawn Willden)
Re: Serious PGP v5 & v6 bug! (Shawn Willden)
Re: Looking for site regarding RSA patent (S. T. L.)
Re: RSA public exponent (Bill Unruh)
Re: Looking for site regarding RSA patent (Bill Unruh)
Re: Remark on practical predictability of sequences ("John A. Malley")
Re: RSA public exponent (David A Molnar)
Re: 96-bit LFSR needed (Mack)
Security in RSA 'e' (Michael Brown)
Re: Serpent S-boxes (Mack)
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed (Mack)
Re: Future computing power (Michael Brown)
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed (Sundial
Services)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: Wed, 30 Aug 2000 23:41:33 -0400
"Trevor L. Jackson, III" wrote:
> Kaz Kylheku wrote:
> > The type char is only suitable for manipulating characters in the translation
> > character set and for communicating with standard library interfaces which use
> > char.
> I take it that this means you religiously use '\0' and '\1' when storing boolean
> values in a char data element?
That doesn't even make sense, since '\0' means (code) value 0
and '\1' means (code) value 1. You should have said '0' and '1',
which would be a valid counterargument against Kaz's assertion.
In fact Kaz has confused the source character set with the
corresponding characters that are required to be supported in
the execution character set; assuming he means the latter, he's
still wrong, since "char" is an integer type that can be used
in arithmetic so long as one is careful to avoid unwanted
overflow (which I think was your real point).
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
Date: Wed, 30 Aug 2000 20:23:17 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Scott Fluhrer wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote
>
> > > O.k. This shows that the order of g is p-1 and hence p is
> > > prime. But in a book of mine where this is proved it is
> > > said that finding primes this way for large p is too slow
> > > compared to modern methods.
> >
> > Actually, it's about as fast as a few passes with the Miller-Rabin test.
In
> > both cases, you pick a g, determine g^k mod p, where k is about as large
as
> > p, and then run quick tests on the results. With Tom's test, you run it
> > once for every prime dividing p-1 (plus a few times to find an
appropriate
> > g). With Miller-Rabin's test, you run it until you get error
probability
> > "small enough". And, in both cases, when p is not prime, then almost
all
> > the time, you'll find it out the very first time you compute g^k mod p.
> > And, of course, with both methods, you do some quick composite checks
(eg.
> > checking for small factors) first.
> >
> > What I suspect your book says that it's a slow way to prove a number p
prime
> > assuming you don't know a priori the factorization of p-1, because
factoring
> > p-1 is a bear. With Tom's approach, that isn't a problem.
>
> Sorry for my poor knowledge. But if p is not prime, how
> do I know the very first time that I compute g^k mod p?
> I can't exclude the case that p is prime but I have picked
> the wrong g, can I?
Simple: 2 is a factor of p-1, so start there, at k=(p-1)/2. And, with that
k, if g^k mod p is anything other than 1 or -1, we know (Fermat's Little
Theorem) that p wasn't prime. Most composites will fail that test, and that
test is approximately as expensive as running a single iteration of
Miller-Rabin.
--
poncho
------------------------------
From: Philip Stromer <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP 6.5.8 test: That's NOT enough !!!
Date: Thu, 31 Aug 2000 04:01:35 GMT
In article <8oe9gi$n89$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Aye, for once we agree. PGP have handled this problem extremely
> poorly from both a technical and PR perspective.
>
> I can't see a "pretty" way forward...
I spoke to some PGP "spin doctor" yesterday and he said if I have PGP
Personal Privacy 6.5.3, I'm safe since it doesn't even have a back door
for any corporate types. Is this accurate, or baloney?
I still don't understand the ADK issue; I installed the Hotfix, ran the
PGPRepair command line utility (it said none of my keys were tampered
with), so now I'm fully safe once again. Right...or wrong?
--
Philip Stromer, Esq.
San Jose, CA
Send me email at [EMAIL PROTECTED]
(delete big cat spam avoider).
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: PRNG Test Theory
Date: Thu, 31 Aug 2000 04:51:16 GMT
Trevor L. Jackson, III wrote:
>
> Paul Pires wrote:
>
> > Yes but there is an interesting question here. Can rejecting
> > Non-random (determined by any means) ever result in random? My Knee
> > jerk reaction is no but I never thought of it that way before.
>
> The answer is clearly no for finite rejection tests. Consider that a
> set of tests that deals only with the most recent N bits of output
> must enter a cycle with length < 2^N.
>
> For rejection systems that deal with all of the output (finite in each
> instance, but ever-increasing), but have a description of "random" of
> finite size must also enter a cycle (*) because a finite description
> of "random" permits only a finite criteria for choosing the next bit.
> The N-bit definition of "random" provides only 2^N fitness values. So
> as the output sequence grows the collisions among the fitness results
> will increase in frequency until they dominate the generator.
>
> I have not spent the time to prove that the increasing collision
> frequency actually forces a cycle, but I believe this can be shown.
>
> (*) this assumes that when the fitness of the prefix+'0' sequence is
> identical to the fitness of the prefix+'1' sequence a deterministic
> selection is made; say alternation.
What if, when prefix+'0' and prefix+'1' are equally fit, the generator
then selects from among prefix+'00', prefix+'01', prefix+'10',
prefix+'11'. If there is no clear best suffix, or no best first bit for
the suffix, look at length 3 suffixes, etc.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP 6.5.8 test: That's NOT enough !!!
Date: 30 Aug 2000 22:09:54 -0700
Philip Stromer wrote:
> I still don't understand the ADK issue; I installed the
> Hotfix, ran the PGPRepair command line utility (it said
> none of my keys were tampered with), so now I'm fully
> safe once again. Right...or wrong?
Fully safe? No. Partly safe? Yes.
There are two sides to the "rogue ADK" problem, namely:
(1) Are you encrypting to rogue ADK's planted on other people's
keys?
and
(2) Are other people, encrypting messages intended for you,
also encrypting to a rogue ADK planted on your key?
You can deal with the first issue all by yourself -- by making sure
you're using encryption software which doesn't use unauthorized ADK's
(or, perhaps, software which doesn't recognize ADK's at all).
You can NOT deal with the second issue all by yourself. You would
need to make sure that EVERYONE sending encrypted messages to you is
using encryption software which won't be fooled by unauthorized ADK's.
Even if you, yourself, are running a bug-free PGP, you could still
get victimized by the ADK bug if someone else with a buggy PGP sends
you an encrypted message.
This means, in particular, that even people using encryption software
that doesn't recognize ADK's at all -- such as PGP 5.0 or GnuPG --
are still vulnerable to the bug if users of susceptible PGP versions
send them encrypted material.
The only truly foolproof way to avoid the effect of unauthorized
ADK's -- coming or going -- would seem to be to use a pre-5.0 PGP
(i.e., one of the 2.6.x versions). The older (version-3) key packet
format used by 2.6.x has no provision for ADK information -- legit-
imate or not -- so no attacker can slip bogus ADK info into your
key, and so no one can inadvertently copy a message for you to an
ADK (even if they use a later PGP to encrypt to your 2.6.x key).
You could, of course, carefully analyse each encrypted message you
receive for unexplained recipient info (which might represent an
unauthorized ADK). This is, however, not easy to do -- and even if
you manage to do it, the best you can hope for is to discover an
intrusion after at least one message sent to you has been compromised.
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
PGP 2.6+ key generated 2000-08-26; all previous encryption keys REVOKED.
RSA, 2048 bits, ID 0xFDF8FC65, print 2A67F410 0C740867 3EF13F41 528512FA
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Serious PGP v5 & v6 bug!
Date: 30 Aug 2000 23:12:36 -0600
"Nathan Williams" <[EMAIL PROTECTED]> writes:
> No it doesn't. Reread my post Shawn. The "master" KEY is SPLIT!!!
> Nolliams" <[EMAIL PROTECTED]> writes:
> No it doesn't. Reread my post Shawn. The "master" KEY is SPLIT!!!
> Nocts are compromised. If users divulge their private keys then
you have to figure out how to protect them, which is a bigger and more
complex job than just getting the ADK implementation right.
Shawn.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Serious PGP v5 & v6 bug!
Date: 30 Aug 2000 23:12:39 -0600
"Nathan Williams" <[EMAIL PROTECTED]> writes:
> No it doesn't. Reread my post Shawn. The "master" KEY is SPLIT!!!
> No one person could decrypt and use the stored keys.
So the first time the master key is reassembled, all of the keys it
protects are compromised. If users divulge their private keys then
you have to figure out how to protect them, which is a bigger and more
complex job than just getting the ADK implementation right.
Shawn.
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: Looking for site regarding RSA patent
Date: 31 Aug 2000 05:16:05 GMT
<<"what may or may not happen" when the patent on RSA expires?>>
What will happen: patent expires, anyone can do any RSA anything they want
without talking to the damned company (although you'll still need to talk to
the gov't about exporting). I don't see any other variability here.
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
My upgraded Book Reviews Page: * http://sciencebook.cjb.net *
Optimized pngcrush executable now on my Download page!
Long live pngcrush! :->
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA public exponent
Date: 31 Aug 2000 05:33:43 GMT
In <8ojdc5$lpo$[EMAIL PROTECTED]> David A Molnar <[EMAIL PROTECTED]> writes:
>There isn't a disparity, really. Consider that q-1 and p-1 are both even,
>thus their product is even. So gcd( (p-1)*(q-1), 3) = 1 always.
p=7, q=19, GCD[ (p-1)(q-1), 3] =3.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Looking for site regarding RSA patent
Date: 31 Aug 2000 05:39:06 GMT
In <8ok1vc$hj0$[EMAIL PROTECTED]> John C. King <[EMAIL PROTECTED]> writes:
>Is there a discussion group or a link to a good site that
>discusses "what may or may not happen" when the patent on RSA expires?
"may or may not happen"? What will happen is that the RSA patent will
have expired. This means anyone can use it without paying royalties to
anyone ( as has been true everywhere in the world except in the USA for
20 years now I believe).
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Remark on practical predictability of sequences
Date: Wed, 30 Aug 2000 22:58:50 -0700
"David A. Wagner" wrote:
>
> In article <[EMAIL PROTECTED]>,
> John A. Malley <[EMAIL PROTECTED]> wrote:
> > Perhaps PRNGs employing mathematical operations not in common with the
> > operations employed by the cipher prove more resistant to cryptanalysis
> > and result in output sequences "practically" unpredictable.
> >
> > For example, consider enciphering the output of a LCG with known
> > coefficients a, b and M, with a block cipher. (Choose M < 2^block size.)
>
> If the cipher is secure, there is no need to worry about using
> incompatible mathematical operations -- enciphering any sequence of
> non-repeating blocks is secure up to about O(2^{n/2}) blocks, where n
> is the blocksize.
>
> Thus, if the cipher is secure, enciphering a counter, a LFSR, or a LCG
> should all provide good security regardless of what the internals of
> the cipher look like.
>
Does enciphering the output of a fast and predictable PRNG always
generate an unpredictable output sequence if the applied cipher is
secure? A draft paper considering a specific example is now available
for the group's review and comment at
http://www.homeworlds.com/papers/SECLCG.doc
The attacks presented in this paper show enciphering the output of a
fast and predictable PRNG with a secure cipher does not always generate
an unpredictable PRNG output sequence. Mathematical operations common
to the PRNG and the secure cipher can permit the prediction of the
enciphered sequence without knowledge of the cipher’s secret key or of
the PRNG’s parameters and without "brute-forcing" the secure cipher. The
predictability of the enciphered PRNG output sequence depends on the
internals of the cipher applied to the predictable PRNG. These attacks
are not guaranteed to succeed for any known subset of the output of the
encrypted PRNG but the probability of success increases with the volume
of known encrypted PRNG output.
The paper uses the IEEE Paper template. It is a MS Word for Windows 95,
Version 7.0c document - I have no converter for pdf. It's a draft, not
all of the references are included yet and given your responses to it I
may pursue publication in a journal (suggestions welcome.)
I found it personally exciting work, fun to write, it's the first
analysis I've done along these lines. I very much look forward to your
feedback.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: 31 Aug 2000 06:16:06 GMT
Bill Unruh <[EMAIL PROTECTED]> wrote:
> In <8ojdc5$lpo$[EMAIL PROTECTED]> David A Molnar <[EMAIL PROTECTED]>
>writes:
>>There isn't a disparity, really. Consider that q-1 and p-1 are both even,
>>thus their product is even. So gcd( (p-1)*(q-1), 3) = 1 always.
> p=7, q=19, GCD[ (p-1)(q-1), 3] =3.
yes, thanks. I was wrong. :-(
-David
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 31 Aug 2000 06:32:50 GMT
Subject: Re: 96-bit LFSR needed
Half of it is indeed from that
source. The other half is from
Dr. Mike's polynomial program
I cobbled the two together.
Dr. mikes determines the
irreducibility very quickly.
Then Nelson scotts Matrix routine
determines the order of the
equation.
I also added another search
method that was more 'Natural'
to me.
It is several orders of magnitude
faster than Nelsons original program
because it only checks the
irreducibles.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Michael Brown <[EMAIL PROTECTED]>
Subject: Security in RSA 'e'
Date: Thu, 31 Aug 2000 18:40:07 +1200
Hi there,
Just a quick question: does the size of 'e' in the RSA method have any
impact on the security of the key?
Thanks,
Michael
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 31 Aug 2000 06:46:01 GMT
Subject: Re: Serpent S-boxes
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Mack) wrote:
>> Let me see if I understand the S-box criteria properly
>>
>> 1) The S-boxes are invertible
>
>Yes.
>
>> 2) The S-boxes have 3 boolean equations of order 3 and one of order 2
>
>It means you cannot combine upto three of the output bits via xor for
>all inputs to create a linear function. In other words the output bits
>are linearly independent of each other. This is also known as the BIC
>or Bit Independence Criterion.
>From the Serpent paper -
the nonlinear order of the output bits as a function of the input bits is
the
maximum, namely three.
I believe they mean the equations of the s-boxes have ANF terms of order
3. What you are refering to is the linear approximation table (see 5).
>
>> 3) No equation can have a hamming weight closer to a single input
>> or the inverse of an input than 6
>
>Or a WT of -4/4. Which is a distance of 12 from the closest linear
>function.
The Serpent paper sights a more strigent bound if I understand it
correctly. Rutppel's terminology is clearer.
>
>> 4) The XOR table has no entries greater than 4
>
>Yes.
>
>> 5) The LAT table has all entries between 4 and 12 (inclusive)
>
>LAT?
Linear Approximation Table reference Fast Software Encryption 95
Properties of Linear Approximation Tables by Luke O'Conner
>
>> 6) Any one bit change changes at least two bits
>
>To clarify. No single bit difference causes a single bit difference.
Yes
>
>> Some other criteria that appear to be redundant
>> 7) All of the boolean equations have a non-linearity of 4
>
>Well you want all boolean equations of the input/output bits to be
>nonlinear to make the sbox secure.
>
But if my understanding is correct this is a nessessary result
of the above six criteria.
>> 8) The inverse of the s-box has the same properties.
>
>The inverse sboxes must be used to decrypt, and we want decryption to
>be just as secure.
This criteria also appears to be automatically satisfied if the above criteria
are met. It is possible to define criteria where the S-box and its inverse
do not share the same properties.
>
>Tom
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 31 Aug 2000 06:48:56 GMT
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
>
>There are 2 more patents:
>
Two identical patents????
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Michael Brown <[EMAIL PROTECTED]>
Subject: Re: Future computing power
Date: Thu, 31 Aug 2000 18:56:11 +1200
Guy Macon wrote:
>
> CMan wrote:
> >
> >Don't forget Linux. You can have multiple copies of the operating system
> >running and be totally legal.
> >
> >Remember, Linux can be rigged for diskless booting which can save a lot of
> >dollars on disk driveds(although these days disk drives are sort of a dime a
> >dozen - amazing. I bought that Apple II and ran it without a hard drive for
> >a long time. Gees. I wonder where the cost per gigaflop will finally
> >stabilize?
> >
>
> In my job (toy designer), I use what amounts to a 6502 running at 3 to 10
> Mhz and costing well under a dollar for everything - CPU, RAM, ROM, clock
> circuit, PWB - the whole computing subsystem. A Dallas DS80C320 is an
> 8051 that does 10 MIPs if you overclock it from 33 Mhz to 40 Mhz
> (see [ http://www.systronix.com/home.htm ].) With the right software,
> you could put together a quite powerful specialized crypto computer at
> a very low cost using large numbers of cheap processors.
What I'm building up at the moment is a cluster of 486/100s, which I can
get (motherboard,cpu ~32mb ram, no HDD or screen or keyboard) for about
$NZ15 (about 5-6 dollars US). Plug 20 of these together and you'll have
a nice cluster for less than the cost of a singe P3 chip. Plus a few
hundred together, and you know the rest.
I think using big things such as P3 600's is a waste as mor smaller
chips can do the job cheaper.
Just my 2 cents worth (~0.8c US :)
Michael
PS: I'm using the partially built system for raytracing. Goes nicely ...
------------------------------
Date: Wed, 30 Aug 2000 23:56:06 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
Terry, I tend to think that cryptography is one of those areas where
"gosh darn it, this idea really might BE patentable." Because the ideas
in crypto really might qualify as "not obvious to someone schooled in
the art." In the realm of some of your patents in particular, I do tend
to think that "yes, what Terry came up with really is worth protecting."
But part of the problem is that so many of the patents that have been
issued are specious -- nothing more than lawyer-bait -- but nonetheless
on the books. For example, IBM patented the idea of using a
compare-and-swap instruction to modify the header-pointer of a linked
list! Now, I read several textbooks, including some OS texts from the
1960's, that described exactly the same notion -- many years before the
patent was issued -- but there it is nonetheless, on the books. Very
typical of the noise that is produced when companies feel obligated to
try to patent "anything and everything" and the patent-examiners can
hardly be expected to know the difference.
The patent examiners are, of course, extremely hard-working people who
have an unbelievable(!) workload ahead of them every single day ... but
I really do feel that in far too many cases, patent-law as presently
applied to computer software in the United States causes far more
pointless lawyering than it does provide real protection. This is
certainly not agreeing with the phrase "all software patent should not
be allowed," but it does agree with "Patent, Patent is a nightmare."
Right now -- it is!
>Terry Ritter wrote:
>
> >>Well, either the improvement is worthy of the cost of a license or it
> >>is not. If not, one can continue to use the previous work. If the
> >>new work is that much better, one can license it.
> >
> >Don't worry, I'm not going to ask you to explain, in detail, the
> >concept of 'patent interference'. I think that does, however, answer
> >some of the concerns raised by the previous poster - where someone,
> >instead of patenting a genuine improvement on something someone else
> >has patented, attempts to patent trivial additions to it so as to
> >prevent it from being used.
>
> In the last sentence, the word "it" seems to be used in two different
> ways: Yes, trivial additions can be patented. But such patents would
> not at all affect the original patent.
>
> If the addition is indeed trivial, there would be no desire for the
> original patentee to license it. But the trivial addition probably
> does need a license from the original patentee simply to be able to
> practice the trivial addition. In general, such a patent is not a
> license to practice the described invention without licensing the
> original patent. I suppose their market could consist of those who
> have previously licensed the original patent, however.
>
> Certainly that is not the "patent interference" that I know.
>
> Patent interference occurs when two different applications describe
> the same invention, and it is necessary for the PTO to decide which
> applicant gets the patent. In the USA, we retain a "first to invent"
> system, where the inventor who can show legal proof of the earliest
> invention date should win. That is conditional, however, on "moving
> toward" a patent; the first inventor can lose by appearing to have
> chosen trade secrecy over patent exposure. I am unaware that trivial
> addition patents have anything to do with this.
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
--
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
** 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
******************************
