Cryptography-Digest Digest #31, Volume #11 Tue, 1 Feb 00 14:13:01 EST
Contents:
Re: Simple Equivalent keys in Serpent ([EMAIL PROTECTED])
Re: Sbox construction idea (Tim Tyler)
Re: Does the NSA have ALL Possible PGP keys? (cfm)
Re: NIST, AES at RSA conference (Shawn Willden)
Re: NIST, AES at RSA conference (Shawn Willden)
Re: How to annoy the NSA & break almost any code (wtshaw)
Re: Does the NSA have ALL Possible PGP keys? (Glenn Larsson)
Re: How to password protect files on distribution CD (Shawn Willden)
Re: Is there a practical guide to using crypto? (Shawn Willden)
Re: How to Annoy the NSA ([EMAIL PROTECTED])
Re: How to Annoy the NSA ([EMAIL PROTECTED])
Re: Does the NSA have ALL Possible PGP keys? (John Savard)
Re: NIST, AES at RSA conference (John Savard)
Re: Does the NSA have ALL Possible PGP keys? (John Savard)
Re: How to password protect files on distribution CD (Dave Howe)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Simple Equivalent keys in Serpent
Date: Tue, 01 Feb 2000 17:18:02 GMT
In article <874tcl$5b8$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <86cu20$752$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Hello All,
> >
> > First off, I don't think this is a weakness in Serpent. It is an
> > oddity however.
> >
> > From looking at the key schedule for Serpent, I believe each 128 and
> > 192 bit key has an equivalent 256 bit key.
> >
> > Quoting from 'Serpent: A Propsal for the Advanced Encryption
Standard'
> >
> > ...
> > short keys with less than 256 bits are mapped to full-length keys of
> > 256 bits by appending one '1' bit to the MSB end, followed by as
many
> > '0' bits as required to make up 256 bits.
> > ...
> >
> > Since the key schedule itself does -not- take into account the
length
> > of the input key and there is no restriction on the selection of 256
> > bits keys, it appears that each 128 and 192 bit key has a 256 bit
> > equivalent.
...
> >
> > --Matthew
>
> But the thing is not all 256 bit keys have bits 128-254 set to zero,
so
> these keys are not equivelant.
>
> Tom
>
Hello all,
Regarding Tom's comment, not all 256 bit keys have an equivalent. All
short keys have a 256 bit equivalent however.
I have spoken to one of the authors of Serpent. He said that the authors
where aware of the short key to 256 bit key equivalence. He pointed out
the my so called attack was nothing more than a brute force table
lookup.
I also noticed that Blowfish has the equivalence property. Bruce S.
actually mentions it in the original Blowfish paper. Blowfish has been
around for awhile and nobody has found a weakness due to equivalant
keys. This property is probably not a weakness of any sort.
To summarize, having different length keys that create an equivalent key
schedule does not appear to be a weakness.
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Sbox construction idea
Reply-To: [EMAIL PROTECTED]
Date: Tue, 1 Feb 2000 17:14:32 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: In safer they use 45^x mod 257 for the sbox in the cipher, what if you
: created a 4x8 parallel set of sboxes [four side by side] with different
: bases? So you end up with a 8x32 sbox?
: Has that idea ever been discussed before? [...]
I don't know. Would anyone care to offer me some sort of literature
reference that offers reasons why using a^x mod p is of interest as a
method of generating s-boxes?
I'm interested in the general question of how best to combine small
s-boxes to form larger s-boxes - with "security" and compactness of
hardware implementation being the criteria I'm most interested in.
A key question appears to be "what is the best size of s-box to use?"
I believe implementations exist using multiple 4x4 s-boxes.
It appears that use of even smaller s-boxes is a practical possibility.
Smaller programmable s-boxes are faster and more compact when implemented
in hardware and allow more iterations to be performed in the same period
of time - an effect which seems to compensate well for their reduced
non-linearity.
: I have source code that will make the sboxes given a matrix (4x4 in my
: case) of bases. Are there specific bases to avoid? [I know they have
: to be generators... or that x^128 mod 257 != 1] [...]
FWIW, I'm currently using a random number generator to generate the
s-boxes and then applying "a number of constraints" to reject
unsuitable ones.
I use the Walsh transform to test for non-linearity, for example, and
reject s-boxes which don't maximise this.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
SECRET VIPAR GAMMA GUPPY
------------------------------
From: cfm <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 01 Feb 2000 13:01:44 -0500
What's the big deal, any one of us who wishes to spend the time can
generate all possible PGP keys. So what, now if they can search them and
discover which one is in use in a particular message and then decrypt
it, that's news, but its also pretty far fetched that nsa is performing
a search across the key space for all PGP encrypted messages in the
internet. (Ignores question of how all traffic in the internet is
funneled to NSA!)
carl.
In article <8764db$vqo$[EMAIL PROTECTED]>, "Scott Fluhrer"
<[EMAIL PROTECTED]> wrote:
>Anonymous <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> There are a couple of interesting threads on talk.politics.crypto
>> originating from a cryptographer with www.filesafety.com. They
>> purport that the NSA has ALL POSSIBLE keys for PGP and that all PGP
>> encrypted netmail has been "transparent" for at least two years to
>> the NSA and certain elements of the military and FBI. The
>> cryptographic basis for this alleged total compromise of PGP is
>> discussed.
>>
>> This is a low-traffic NG and I should like to see serious analysis of
>> these claims by those who are more technically qualified to discuss
>> them.
>Summary: either he's nuts, he's trolling or he's deliberately lying about
>his competition (I rather suspect the latter, myself).
>
>Facts:
>
>- The source code for older versions of PGP is publicly available. In
>spite
>of repeated requests from other posters, he refuses to point out where in
>the source code the number of keys are limited, or where the random number
>generator is chilled
>
>- The number of distinct keys he lists (the exact number changes from post
>to post) is so small (such as one million), he could have demonstrated it
>by
>generating a few thousand keys and found duplicates. He refuses to do so.
>
>- He refuses to back up his claim in any other way. Instead, he just
>claims
>to have unrevealed wisdom that PGP is broken, but (of course) his own
>software is pristine.
>
>- When pressed, he usually launches into personal attacks. See the
>"Johnny
>Bravo is an FBI man" for an example -- the logic appears to be "Johnny
>Bravo
>disagrees with me, ergo he must be a government agent". Personally, I
>believe when people use ad homin attacks, it's usually because that's the
>only arrow left in their quiver.
>
>--
>poncho
>
>
>
------------------------------
Date: Tue, 01 Feb 2000 11:04:07 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Terry Ritter wrote:
> If cryptanalysis would be more effective by adding a cipher to the
> cipher being attacked, we would see that proposed as an attack
> technique. We do not see that.
We don't see that, but is it because it's not effective or because it's not
explored? It seems to me that to some degree this leads us back into the same
quandary. How do we know that layered ciphers are strong? Because no one has
published an attack that exploits layering.
It's possible (I think unlikely, but then I'm a clueless newbie) that the only
reason such attacks haven't been published is because no one has been trying,
and that the reason no one has been trying is because layering is not common.
Suppose someone did publish an attack that showed some considered-to-be-secure
algorithm to be weak if the ciphertext were further enciphered using some
other algorithm, but with the same key. Wouldn't the response be: "Why would
you do that?".
To summarize the point I'm trying (probably badly) to make: The claim of
added strength that may arise from layering ciphers seems indistinguishable
from the claim of added strength that may arise from creating more
sophisticated ciphers (with more layers, rounds, etc.). In both cases, the
*only* recourse we have to evaluate the security of the result is
cryptanalysis, which we know to be ultimately ineffective. Further, it seems
that even that ineffective evaluation has not been applied layered cipher
systems, because common wisdom says that it's unnecessary.
OTOH, I believe (without any justification whatsoever) that in nearly every
case a stack of ciphers is at least as strong as the strongest cipher in the
stack, and a dynamically changing stack would be stronger yet. It appears
that Mr. Ritter believes this as well.
However, I also believe (again without real justification) that our key
management practices are far weaker than our ciphers.
Shawn.
------------------------------
Date: Tue, 01 Feb 2000 11:19:31 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Serge Vaudenay wrote:
> The proof is quite obvious if you consider attacks as distinguishers. If you
> take MARS o RC6 o TWOFISH with three independent keys as a cipher, then
> any distinguisher between this and a truly random permutation can be
> transformed into a distinguisher between for instance RC6 and a random permutation
> by simulating MARS and TWOFISH.
>
> This way the product cipher is at least as secure as its strongest
> factor.
Given independent keys. What if the same key is used for all three?
Shawn.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: How to annoy the NSA & break almost any code
Date: Tue, 01 Feb 2000 11:39:27 -0600
In article <[EMAIL PROTECTED]>, "A [Temporary]
Dog" <[EMAIL PROTECTED]> wrote:
> On Mon, 31 Jan 2000 06:07:46 GMT, [EMAIL PROTECTED] wrote:
>
> >You can probably annoy the NSA by spreading
> >this news.
>
> Yea, but you can annoy them more by ringing the doorbell and running
> away before they answer. The NSA hates that.
>
>
I am reminded of the story of how to drown a blonde....just put a mirror
on the bottom of a swimming pool. I'm sure that there is some analogus
situation that can be used for NSA.
--
A big-endian and a little-endian have been spotted sitting at a
campfire nibling on bytes and pointing at each other as they
argued about who got hit with the most errors.
------------------------------
From: Glenn Larsson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 01 Feb 2000 19:13:34 +0100
Anonymous wrote:
<SOMETHING>
Have you read AC, page 258, Section 11.5, the 3'rd point about storing
all the 512 primenumber keys? (If you dont have it, get it..)
Quote:
"3. If someone creates a database of all primes, won't he be able to
use that database to break public-key algorithm? Yes, but he can't
do it. If you could store one gigabyte of information on a drive
weighing one gram, then a list of all 512-bit primes would weigh so
much that it would exceed the chandrasekhar limit and collapse into
a black hole... so you couldn't retrive the data anyway".
Kasluuuurrp! :o)
Glenn
Sweden
_________________________________________________
Spammers will be reported to their government and
Internet Service Provider along with possible legal
reprocussions of violating the Swedish "Personal
Information Act" of 1998. (PUL 1998:204)
------------------------------
Date: Tue, 01 Feb 2000 11:34:53 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: How to password protect files on distribution CD
Dave Mundt wrote:
> Seems to work for Microsoft well enough...
Apparently not. Scuttlebutt in the smart card community has
it
that one of the primary drivers behind Microsoft's recent
interest
in smart cards is to provide copy protection for their
applications
-- essentially a dongle, but one that goes in your smart
card
reader (what, you don't have one?) rather than your parallel
port.
Still crackable, of course...
Shawn.
------------------------------
Date: Mon, 31 Jan 2000 14:44:23 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Is there a practical guide to using crypto?
Jerry Coffin wrote:
> > One thing I really want to know is if VISA card number consists of
> > 16 digits with two digits for month and four digits for year, whats
> > to stop someone from attempting every possible 22 digits combination
> > until they find one which works?
>
> The fact that there are 10**22 possible combinations.
>
> Some quick figuring indicates that if 1,000,000,000 Visa cards have
> been issued, and you had enough credit card verification machines to
> try 1000 different numbers a second, you need to keep trying for
> around 160 years before you stand a reasonable chance of finding one
> that's in use.
Except that credit card numbers are not randomly chosen from the entire
space. They have some structure to them, including a checksum and
card-type and bank-specific prefixes.
> Of course, when you do, chances are that it's within
> $20 of its limit and it won't do you any good anyway.
Good point :-) Based on that point of view, I should probably just
publish my card numbers...
> In reality of course, the bank would probably notice something wrong
> well before you got this far.
Yep. Even in the restricted space of real CC numbers this is definitely
the case. It's much easier to dig numbers out of the garbage can at the
mall, or get a job as a clerk somewhere, or...
Shawn.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How to Annoy the NSA
Date: Tue, 01 Feb 2000 18:32:57 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
>
> : The paper I referred to is news because it is
> : the only proposal I know of that describes how
> : to go about building a quantum computer that
> : consists of BOTH linear and nonlinear gates.
>
> A universal computer can't possibly be built with just linear gates.
>
> It's hard to see what's new there.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> Strip mining helps prevent forest fires.
>
Before, it was only known theoretically that a
quantum computer based on linear quantum
mechanics and supplemented with non-linear
gates could solve in polynomial time NP-
complete and #P problems. The paper I
referred to describes a way to try making this
a practical reality via macroscopic quantum
coherence.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How to Annoy the NSA
Date: Tue, 01 Feb 2000 18:25:38 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > > [EMAIL PROTECTED] wrote:
> > > > ... Some or
> > > > many of the NSA's codes have depended on the
> > > > intractability of NP- Complete problems
> > > > which could become vulnerable to this type of
> > > > computer.
> > > I doubt that you have a clue about "NSA's codes".
> > You are wrong. For example, all RSA public-
> > key and lattice based cryptosystems depend on
> > the intractability of NP-Complete problems.
>
> No, they do not. RSA depends for its security on
> the difficulty of factoring products of large primes.
> That has nothing to do with NP-Completeness.
>
> Indeed, complexity theory has nothing to do with the
> security of any given instance of any cryptosystem;
> it's a theory of asymptotic behavior of classes of
> problems as the problem size becomes infinitely
> large, which has nothing to do with any actual
> cryptosystem implementation.
>
> > Meredith Gardner, the first great figure in the
> > history of the NSA, married into my family and
> > so I know a little bit about the organization.
>
> Whether or not Gardner was "great", as an NSA
> employee he would not have told his family what
> encryption methods NSA has devised.
>
> > If I were, say, the Chinese Government I would
> > hire scientists to try building one of these
> > computers.
>
> Just because Quantum Computing is news to you
> doesn't mean that the rest of the world is as
> ignorant. There is a *lot* of QC research going
> on around the world. One thing that is well known
> in this field is that it is premature to try
> constructing a large-scale Quantum Computer.
>
You are wrong again. According to Science
Magazine (vol. 275, page 1570, March 14,
1997) "hard" problems, or NP-Complete
problems "underlie nearly all cryptography and
computer security codes". If you don't believe
me then check out links like the RSAsecurity
link in my previous message and
www.cs.ccu.edu.tw/~ccc/student/dcl/dcl.htm
Despite the issue of NP-completeness, such a
quantum computer would have awesome power
for factoring. You are right, though, that
Gardner never told us about NSA encyrption.
However, the NSA has declassified his
project, VENONA, and others. Also, the NSA
has participated in math and comp sci
conferences, periodicals, etc. which makes it
possible to infer what they were doing in the
past. It is not too early for military related
organizations to begin trying to build a large-
scale quantum computer. When the military
conducts work on major break- through
technologies they are usually years ahead of
their civilian counterparts- for example, the
development of radar, rockets, computers,
satelites, biological weapons and stealth.
Everyone should know that Al Gore did not
invent the internet and that it was first
developed as a military project about 30 years
ago.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 01 Feb 2000 11:44:34 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote, in part:
>saying that everything out there is
>broken despite the fact he can't prove any of it.
Then there's that fellow who started out in this group by posting that
IDEA is fatally weak, and only his wonderful cipher with an S-box with
65,536 entries is any good. Now do you wonder why we have such an
attitude towards that other fellow?
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST, AES at RSA conference
Date: Tue, 01 Feb 2000 11:50:00 GMT
[EMAIL PROTECTED] (David Wagner) wrote, in part:
>If we consider one round of DES, one of Blowfish, plus one of Serpent,
>the result is extremely insecure,
But if one takes the most elementary precautions: i.e., two rounds of
DES plus two rounds of Blowfish, etc., does one get the same type of
problem?
While scaled down versions of ciphers can tell us much that is useful,
I'm not so sure we can learn from what appear to me to be contrived
examples.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 01 Feb 2000 11:52:48 GMT
[EMAIL PROTECTED] (John Savard) wrote, in part:
>Tom St Denis <[EMAIL PROTECTED]> wrote, in part:
>>saying that everything out there is
>>broken despite the fact he can't prove any of it.
>Then there's that fellow who started out in this group by posting that
>IDEA is fatally weak, and only his wonderful cipher with an S-box with
>65,536 entries is any good. Now do you wonder why we have such an
>attitude towards that other fellow?
Oops. I confused you with Tim Tyler.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To: alt.security.pgp,comp.security.unix,comp.security
Subject: Re: How to password protect files on distribution CD
Date: Tue, 01 Feb 2000 19:02:25 +0000
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Mon, 31 Jan 2000 10:51:37
-0700]), Eric Lee Green <[EMAIL PROTECTED]> said :
>As others have pointed out, the problem is that CD media is immutable -- it
>cannot be "personalized" to have a different key for each customer. Thus
>you'll only have one single key. Once that key is posted to a public "hacker"
>web site, you're fried. And the key WILL be posted.
It depends on how many you are shipping - if it is a low number, then
printed-face CDRs are more economical anyhow
------------------------------
** 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
******************************
