Cryptography-Digest Digest #357, Volume #12 Fri, 4 Aug 00 12:13:00 EDT
Contents:
Re: New William Friedman Crypto Patent (filed in 1933) (John Savard)
Re: Q: Quantum dots (John Bailey)
Re: OTP using BBS generator? (Mark Wooding)
Get a free certificate that lasts 10 year at http://www.cryptomathic.dk (Pinhead)
Square/Rijndael/Crypton S-box question (Mack)
Re: Observation on MDS matrices (tomstd)
Re: Elliptic Curves encryption (Mark Wooding)
Re: What is the word on TC5? (tomstd)
Re: Observation on MDS matrices (Mark Wooding)
Re: Square/Rijndael/Crypton S-box question (Mark Wooding)
Re: Software in market(ECDSA) (DJohn37050)
Re: What is the word on TC5? (Mark Wooding)
Re: Elliptic Curves encryption (DJohn37050)
Re: counter as IV? (Bodo Moeller)
Re: Square/Rijndael/Crypton S-box question (John Myre)
Re: What is the word on TC5? (stanislav shalunov)
Digital Certificates and Key Lengths (Kashif Hassan)
Re: Cracking RC4-40 in FPGA hardware ("CMan")
Re: Proving continued possession of a file (David A. Wagner)
Re: What is the word on TC5? (David A. Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Fri, 04 Aug 2000 11:26:48 GMT
On Thu, 03 Aug 2000 17:47:11 -0500, Bruce Schneier
<[EMAIL PROTECTED]> wrote, in part:
>Here is what Whit Diffie said about the M-134 in _Privacy on the
>Line_:
>"
...
>In
>retrospect this can be seen to be merely an overly complicated way of
>achieving a one-time cryptosystem, but at the time the additional
>complexity must have seemed an advantage.
...
>"
That comment (p. 51-52 is where it is discussed) is quite fair.
Although even at the time, people knew what the one-time cryptosystem
was; Friedman would have been familiar with Vernam's invention.
The M-134 had the advantage that ciphertexts were more convenient to
handle, instead of being, essentially, confined to teletypewriter
circuits (links between 5-level-code machines) - and that may well
have been (in fact, is quite probably) the primary rationale behind
its initial design.
(But the additional complexity may well have offered the possibility
of getting away with things like using coherent keys, even if that
hadn't been explored, so it did have its uses.)
>He calls it one of the worst crypto machines ever designed.
I went looking at my copy to see something of that nature, but I
didn't find it, so I suppose you're referring to a verbal comment,
which, hopefully, doesn't reflect a considered opinion (it wasn't
_that_ bad, and there were a lot of stinkers out there).
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Q: Quantum dots
Date: Fri, 04 Aug 2000 12:30:44 GMT
On Thu, 03 Aug 2000 08:15:22 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Allow me to pose another layman's question: It seems that
>people are already storing information with quantum dots.
>The other day I learned that the record of quantum computer
>is 5 qubits, employing something with organic molecules,
>not silicon. How many qubits have been realized with quantum
>dots? Thanks.
I did a cursory search of sorts in a loca library (paper,
non-technical) yesterday.
1) Quantum dots seem to have potential uses over a much broader
spectrum of applications than quantum computing. The article (Science
News, April 2000) covered areas such as a replacement for solar cells
and such.
2) Experiments reported in March 2000 Science News using ion-trap
technology, achieved 4 qubits, but "which demonstrated the technique
could be extended"
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 4 Aug 2000 12:56:57 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> But I may be one of the few authors and designers who actively seeks
> negative comments and then publishes those on my pages, as readers can
> attest.
>
> My stuff is not intended to replace BB&S or PK, but if they have
> problems that I see, I'm going to say so, independent of whether I can
> profit from that or not.
True, and most praiseworthy.
> For free, I offer a 400K Crypto Glossary, plus a free Introduction to
> Cryptography, Literature Surveys also free, plus lots of other stuff.
> You don't have to buy a book to read my stuff, but if you want to read
> it in a library, you can do that too, on any Web terminal.
Indeed. This is excellent work, thoroughly worth reading. I honestly
don't wish to detract from your great contribution to cryptography in
general, and sci.crypt in particular, over the years.
I'll respond to your technical points in a separate article.
-- [mdw]
------------------------------
From: Pinhead <[EMAIL PROTECTED]>
Subject: Get a free certificate that lasts 10 year at http://www.cryptomathic.dk
Reply-To: [EMAIL PROTECTED]
Date: Fri, 04 Aug 2000 13:52:07 GMT
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Square/Rijndael/Crypton S-box question
Date: 04 Aug 2000 13:54:46 GMT
Does anyone know what field polynomial and
linear transformation were used to generate the
S-box in Square and Rijndael?
I am seeking the same info for Crypton.
Or was the involution of 257?
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Subject: Re: Observation on MDS matrices
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 04 Aug 2000 06:54:08 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>> Just wanted to know if this is right...
>
>No, 'fraid not.
>
>> With a 4x4 mds matrix applied to an input the different in the
>> input/output tuples is at least five right?
>>
>> Well if we consider two inputs (a, b) where b differs by four
>> from 'a' then the outptu (f(a), f(b)) must only differ by one
>> place at the most.
>
>Wrong here.
>
>Let M be a 4 x 4 MDS matrix; let x be a column vector of
inputs, and let
>d be a nonzero input difference. Then the output difference is
>
> M (x + d) - M x = M x + M d - M x = M d
>
>by distributivity of matrix multiplication.
>
>To see why your argument above is wrong, count the number of
vectors
>with zero, one, two and three zero entries. (Hint: 255^4,
255^3, 255^2
>and 255.) Noting that multiplication by M is a permutation on
vectors,
>count how many inputs with no zero elements can end up with
one, two or
>three zeros in the output...
When the two input vectors differ in all of their components the
output vectors must only differ in one component to be a MDS.
This is my point you get a max difference that causes a minimum
difference...
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Elliptic Curves encryption
Date: 4 Aug 2000 13:57:37 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> On 3 Aug 2000 14:21:16 GMT, in <[EMAIL PROTECTED]>,
> in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> >Terry Ritter <[EMAIL PROTECTED]> wrote:
> >>
> >> On Tue, 01 Aug 2000 13:26:12 -0500, in
> >> <[EMAIL PROTECTED]>, in sci.crypt Doug Kuhlman
> >> <[EMAIL PROTECTED]> wrote:
> >>
> >> >But knowing that "breaking" BBS (for example) is equivalent to
> >> >factoring is SOMEthing.
> >>
> >> No, it is not, and we just went through that a month ago.
> >
> >Yes, we did, and you're still wrong now.
>
> On the contrary, you seem to have difficulty understanding written
> English. Or perhaps you are simply too arrogant to take the effort to
> understand someone else's ideas.
>
>
> >> When the supposed "BB&S" construction is used, there is a possibility
> >> -- admittedly very remote -- of having selected a short cycle. When
> >> that happens, the system can be broken due to repetition of the cycle,
> >> and that of course also allows the composite to be factored. Now,
> >> exactly *how* has it helped us to know that the failure allowed
> >> factoring?
> >
> >Well, we know that finding cycles is at least as hard as factoring.
> |--------------------------^
> (That would be "finding *short* cycles." *Every* starting value finds
> a cycle.)
Talking about `short' cycles begs the question of how short `short'
cycles are. The answer is that any cycle you can find the end of is
`too short'. I call that `finding a cycle', in that you've found all of
it. Thus, finding a cycle, in this sense, is sufficient to factor the
modulus
> Whether finding short cycles is hard or not is hardly the point.
Yes it is. We know that finding a cycle is as hard (at least) as
factoring, and that factoring is as hard (at least) as deciding
quadratic residuosity. Hence, solving QRP is (possibly jointly) the
best attack against an x^2 mod n generator.
We don't know how to solve QRP without factoring. I agree that it would
be nicer if we could prove that QRP and IFP were equivalent, but we
can't. Anyway, currently, the best attack known against an x^2 mod n
generator involves factoring. And our experts tell us that moduli
formed by multiplying random primes of appropriate size is a fine way of
protecting against factoring attacks.
Of course, the question of whether QRP is easier than factoring is
irrelevant to this point. If there is way to decide quadratic
residuosity without factoring then that becomes the best attack against
x^2 mod n generators, and must be *easier* than finding cycles.
> Short cycles are a weakness we can prevent. We can choose not to.
> But then, when we do use a short cycle, we have only as much strength
> as it takes to identify a cycle repeat. Then our composite N can be
> factored. Then the guarantee does not apply.
>
> The math doesn't guarantee that factoring is easy if we deliberately
> make it easy because we are too lazy to do things right.
When you do RSA, do you choose `strong' primes? I do, but I acknowledge
that there's no particular point in doing so. I implemented the code
because it was interesting integrating it into my prime generation
system and it's still there because it doesn't cost anything much.
Strong RSA primes are plentiful and easy to find.
Finding `special' BBS primes is a total pain. It's very hard, it takes
ages and it's generally no fun at all. Special BBS primes are rare and
hard to find. I get nervous feelings about keyspace reduction and
special-purpose factoring algorithms when I think about them.
Think about that last point. Can you address a concern that, by
choosing primes of this form in order to prevent factoring by one
(probably suboptimal) method, you're actually making factoring *in
general* easier?
> >> >I still would like you to present something to me as a fact.
> >>
> >> How about this: That's a stupid request.
> >
> >Now prove that this is a fact. ;-)
>
> Self evident.
Are you asserting this as an axiom? Very well; I'll assume the opposite
and we can happily live in similar but different universes... ;-)
-- [mdw]
------------------------------
Subject: Re: What is the word on TC5?
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 04 Aug 2000 06:55:51 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> But in order to distinguish the cipher from random you have to
>> first pick d, d' and d'' values right?
>
>The impossible differential is (0, d) -/-> (?, d). That is,
for any
>input difference of the form (0, d) (d nonzero), the right hand
half of
>the output difference can *never* be d.
But in a perfect cipher (0,d) -> (d,0) should occur only once
anyways right?
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Observation on MDS matrices
Date: 4 Aug 2000 13:59:56 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> When the two input vectors differ in all of their components the
> output vectors must only differ in one component to be a MDS.
> This is my point you get a max difference that causes a minimum
> difference...
No! Do the sums! This can't *possibly* be true -- there aren't enough
output vectors with three elements zero for this to happen. You've
turned an inequality into an equation by accident.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Square/Rijndael/Crypton S-box question
Date: 4 Aug 2000 14:07:37 GMT
Mack <[EMAIL PROTECTED]> wrote:
> Does anyone know what field polynomial and linear transformation were
> used to generate the S-box in Square and Rijndael?
The S-box in Rijndael is inversion in the field GF(2^8) represented as
GF(2)[x]/(x^8 + x^4 + x^3 + x + 1), followed by the affine
transformation
[ 1 1 1 1 1 0 0 0 ] [ x_7 ] [ 0 ]
[ 0 1 1 1 1 1 0 0 ] [ x_6 ] [ 1 ]
[ 0 0 1 1 1 1 1 0 ] [ x_5 ] [ 1 ]
[ 0 0 0 1 1 1 1 1 ] [ x_4 ] [ 0 ]
[ 1 0 0 0 1 1 1 1 ] [ x_3 ] + [ 0 ]
[ 1 1 0 0 0 1 1 1 ] [ x_2 ] [ 0 ]
[ 1 1 1 0 0 0 1 1 ] [ x_1 ] [ 1 ]
[ 1 1 1 1 0 0 0 1 ] [ x_0 ] [ 1 ]
over GF(2).
The S-box in Square is inversion in the field GF(2^8) represented as
GF(2)[x]/(x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1), followed by the affine
transformation
[ 1 1 0 1 0 1 1 0 ] [ x_7 ] [ 1 ]
[ 0 1 1 1 1 0 1 1 ] [ x_6 ] [ 0 ]
[ 0 0 1 1 1 1 0 1 ] [ x_5 ] [ 1 ]
[ 0 0 0 1 1 1 1 1 ] [ x_4 ] [ 1 ]
[ 0 0 0 0 1 1 1 1 ] [ x_3 ] + [ 0 ]
[ 0 0 0 0 0 1 0 1 ] [ x_2 ] [ 0 ]
[ 0 0 0 0 0 0 1 1 ] [ x_1 ] [ 0 ]
[ 0 0 0 0 0 0 0 1 ] [ x_0 ] [ 1 ]
over GF(2).
The Square S-box isn't adequately described in the paper; the Rijndael
one is described very clearly.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Software in market(ECDSA)
Date: 04 Aug 2000 14:08:55 GMT
ECC I presume means Elliptic Curve Crypto. ECDSA is the elliptic curve analog
of NIST's DSA and is defined in ANSI X9.62, IEEE P1363, ISO 14888-3 and ISO
15946-2, each with some variation as to scope. Certicom does sell tool kits
which do ECDSA and other ECC opations like ECDH, etc.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: What is the word on TC5?
Date: 4 Aug 2000 14:11:39 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> But in a perfect cipher (0,d) -> (d,0) should occur only once anyways
> right?
Umm... possibly (can't be bothered to the maths on that). But not
relevant. Let me say it once more before I give up:
In a four-round Feistel network with a bijective F-function, if a
plaintext pair has a difference (0, d), for *any* nonzero XOR difference
d, then the output difference can *never*, under *any* circumstances, be
(?, d), for *any* value of `?'. And that's a big surprise.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Elliptic Curves encryption
Date: 04 Aug 2000 14:14:18 GMT
DL and EC use public primes, RSA uses secret primes. This means the prime code
for DL/EC can be OUTSIDE the security boundary and the primes can be audited in
a straightforward manner. The prime code for RSA must be INSIDE the security
boundary and auditing the generation of such primes is difficult.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Bodo Moeller)
Subject: Re: counter as IV?
Date: 4 Aug 2000 14:26:54 GMT
David A. Wagner <[EMAIL PROTECTED]>:
> If you use a counter as your IV (instead of using a truly random IV)
> with, say, CBC mode, some information about the plaintext can be leaked.
> To quote from an essay written in 1995 by Phil Rogaway:
> ``As an example, it is not true that CBC encryption
> can use an arbitrary nonce initialization vector: it is essential
> that the IV be unpredictable by the adversary. (To see this, suppose
> the IV is a sequence number: 0, 1, 2, ... . Then a (first) encryp-
> tion of 0x0000000000000000 followed by an encryption of
> 0x0000000000000001 is recognizably distinct from a (first) encryption
> of 0x0000000000000000 followed by an encryption of
> 0x0000000000000000. Clearly this violates violates the notion of a
> secure encryption sketched [earlier in the essay].)''
> http://www.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt
> If our plaintexts were truly random, this wouldn't be an issue. But
> in practice, we know that plaintexts are often patterned, and sometimes
> in a way which may lead -- with non-negligible probability -- to two
> consecutive plaintexts that differ by 1 mod 2^64, and in this latter
> case, information is leaked.
>
> Using a truly random IV eliminates this vulnerability. That's why I
> recommend to use an unpredictable, random IV, and not, e.g., a counter.
Does it really have to be a *truly* random, *unpredictable* IV?
What about applying a publicly known PRF to counter values?
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Square/Rijndael/Crypton S-box question
Date: Fri, 04 Aug 2000 08:41:02 -0600
Mark Wooding wrote:
[descriptions of Square and Rijndael S-boxes]
Why are they different?
The Rijndael paper does have some rationale for the cipher's
various parts. But I couldn't get from there to an answer of
the question above. Actually, I got the impression that the
choices were somewhat arbitrary, and therefore Rijndael and
Square are different because to do otherwise would be boring.
JM
(I wonder if I will ever get to where I can spell Rijndael
without looking it up first. I've given up on touch-typing
it.)
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: What is the word on TC5?
Date: 04 Aug 2000 11:31:11 -0400
[EMAIL PROTECTED] (Mark Wooding) writes:
> In a four-round Feistel network with a bijective F-function, [...]
How could a function from a set of 2^{2n} elements into a set of 2^n
elements be bijective?
--
Stanislav Shalunov Internet2
"Hatred won't work. We must use technology to solve problems." --Alex Chiu
http://www.alexchiu.com/affiliates/clickthru.cgi?id=shalunov
------------------------------
From: Kashif Hassan <[EMAIL PROTECTED]>
Subject: Digital Certificates and Key Lengths
Date: Fri, 04 Aug 2000 11:36:28 -0400
Hello all!
Here is the scenario, I am using ms certificate server on NT 4.0.
1. The CA cert has a public key of length 512 bits
2. I use the Key Manager and request a 1024 bit certificate and am to
successfully generate one.
Does it make sense to have a 512 CA issue 1024 certs? Is there a
relationship between the CA cert and
the cert that the CA issues?
I am really confused here, if someone could explain the relationship it
would be appreciated.
when I install the 1024 cert, I am able to get ssl enabled, but I am not
sure if its 1024 or 512...or what..
thanks in advance
Kashif H.
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: Fri, 4 Aug 2000 08:48:07 -0700
It is actually surprising how fast you can do a brute force MD5 hash and RC4
key schedule and Rc4 key generation to 40 bytes on an overclocked Celeron
300 (450 mhz) using optimized assembler (maybe 100,000 keys per second).
The cache demands are small so the Celeron actually out does the Pentium III
in this application (at equal clock speeds). The cost, even for a full PC
cluster setup with diskless Linux running ethernet is probably less than the
cost of designing, assembling, debugging and testing an array of hardware
FPGA's.
The thing is, if you could achieve really massive parallelism on a single
card setup like the DES cracker did, you could really crunch some numbers...
Of course if you spent $200,000 on a big PC cluster, you could probably hook
up five or six hundred PC motherboards...
Better wait until California gets over its power crisis :--))
JK
Anders Thulin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Paul Morris wrote:
>
> > Paul mentioned that RC4-40 is used in exportable web browsers
(presumably as
> > part of the SSLv3) and for password protected files in Microsoft Word.
>
> It's also used to protect Adobe Acrobat documents - .PDF files.
>
> > Although RSA's site states that RC4 is considered strong, Paul mentioned
> > that it could be broken in 'a few months' with a PIII.
>
> Hm. There's www.pwcrack.com who seems to do a brute force search for
the RC4 key
> in 25 days for .PDF files. But perhaps they're doing it in paralell, or
able to
> use some problem in the key generation.
>
> --
> Anders Thulin [EMAIL PROTECTED] 040-10 50 63
> Telia Prosoft AB, Hjälmaregatan 3B, 212 19 Malmö, Sweden
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Proving continued possession of a file
Date: 4 Aug 2000 08:48:55 -0700
Ah-hah! Yes, now I see why the standard heuristic doesn't work. Many
thanks for the gentle explanation. (And, I liked your clever tricks in
the non-interactive protocol...)
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: What is the word on TC5?
Date: 4 Aug 2000 08:59:20 -0700
stanislav shalunov <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Mark Wooding) writes:
> > In a four-round Feistel network with a bijective F-function, [...]
>
> How could a function from a set of 2^{2n} elements into a set of 2^n
> elements be bijective?
Er.. what? Mark Wooding's statement makes perfect sense.
If the block cipher has a 2n-bit block length, then the F
function will take n-bit inputs to n-bit outputs, and thus
it makes perfect sense to ask whether the F function is
bijective or not.
Remember, each round of a Feistel function is defined by
(L',R') := (R + F(K_i, L), L).
The function F(K_i, .) : {0,1}^n -> {0,1}^n can be either
bijective or non-bijective.
------------------------------
** 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
******************************
