Cryptography-Digest Digest #285, Volume #10 Tue, 21 Sep 99 09:13:04 EDT
Contents:
Re: Ritter's paper
Re: Linear and differential analysis
Re: crypto papers (Helger Lipmaa)
Re: Comments on ECC (Robert Harley)
Re: Comments on ECC ("Sam Simpson")
Re: Comments on ECC (Robert Harley)
Re: AES finalists AMD Athlon performance? (Tom St Denis)
Re: Yarrow: a problem -- am I imagining it? (Tom St Denis)
Re: AES finalists AMD Athlon performance? ([EMAIL PROTECTED])
Re: Yarrow: a problem -- am I imagining it? ("Richard Parker")
Re: Schrodinger's Cat and *really* good compression (Erwin Bolwidt)
Re: Yarrow: a problem -- am I imagining it? (Rochus Wessels)
Re: Yarrow: a problem -- am I imagining it? (Rochus Wessels)
Re: Comments on ECC (DJohn37050)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Ritter's paper
Date: 21 Sep 99 04:37:15 GMT
[EMAIL PROTECTED] wrote:
: At bottom, of course, a cipher generator is a cipher too, but there is
: an important shift in perspective. The designer now does not try to
: build one function C=f(K,T) that fulfils one difficult requirement
: (strength), but rather a group of functions C=f_K1(K2,T) that fulfil a
: different set of requirements (independence and opaqueness), which may
: be less difficult to achieve.
This is a very interesting suggestion.
I suspect that one can't really solve the analytic problem of establishing
strength in this way, even if it is useful pragmatically in producing
stronger ciphers (whose true strength remains as hard to prove as ever).
It *seems* that one can make a stream cipher strong at a smaller cost in
computational time than a block cipher. This is because a stream cipher
can have a large internal state, only a part of which is used in
enciphering a single element of the stream (however, the stream elements
should be larger than bits; straight-XOR PRNG stream ciphers have their
own limitations).
And thus, while I haven't looked at making members of a family of ciphers
provably independent or opaque, which is an intriguing idea, I have been
doing something else in some of my ciphers (i.e., Quadibloc III) which
suggests a way to take this idea even further.
Once one has a way to specify truly different ciphers based on extra key
bits, one could - by doubling the blocksize, and making the cipher used to
encipher one half depend on the contents of the other half of the block -
make the choice of cipher for a particular block data-dependent.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Linear and differential analysis
Date: 21 Sep 99 04:28:43 GMT
Sundial Services ([EMAIL PROTECTED]) wrote:
: There are a LOT of good cryptology pages out there on the web which
: detail topics like these. Try Dr. Savard's page at:
It's only Mr. Savard, M. Sc.
: http://fn2.freenet.edmonton.ab.ca/~jsavard/jscrypt.htm
: Now to briefly nutshell your question: both of these are attacks which
: try to feed a cipher known plaintexts with specific characteristics and
: to learn more about (to attack) the cipher by measuring the changes in
: the output produced.
: Equally fascinating reading, also in abundance on the web, is how
: various ciphers can be made resistant against these attacks.
I do explain differential and linear cryptanalysis on one of the pages of
my site, but the explanations are at a simple level. These things are, of
course, more thoroughly explained in Dr. Eli Biham's papers, many of which
are freely available at his web site.
John Savard
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: crypto papers
Date: Tue, 21 Sep 1999 11:39:14 +0300
jerome wrote:
> i think it is a very good idea but it will be more convenient to
> share them through a web or a ftp site.
Most of these papers (if not all) _are_ available from web.
> 1
>
> On Sat, 18 Sep 1999 01:06:52 GMT, Tom St Denis wrote:
> >In the spirit of sharing information here is a list of all the relevant
> >crypto papers and such I have... if you want any email me at
> >[EMAIL PROTECTED]
> >
> >16 round differential cryptanalysis of DES.ps 990414-mrobshaw.pdf
> >aes-comment-to-nist.ps AES ciphers on the 6805.pdf A faster attack on certain
> >stream ciphers.ps A fast new hash function - TIGER.ps All or Nothing
> >Disclosure of Secrets.ps Analysis of Splaying.ps Analysis of the sboxes in
> >DES.ps A new kind of stream cipher CHAMELEON.ps An Implementation of the
> >Number Field Sieve.ps asiacrypt98-slides-c.ps BellareRivest-translucent.ps
> >Blowfish Constants.pdf bsa-final-report.txt
> >BurmesterRivestShamir-geometric.ps card_cipher.ps CAST-256 AES Submission.ps
> >CFB_mode_of_DES.pdf chaffing-980701.txt chaotic.ps Chapter 6 - Stream Ciphers
> >(CRC press).ps Chapter 7 - Block Ciphers (CRC press).pdf Chapter 14 -
> >Efficient Implementations of Algorithms (CRC press).ps Chapter 2 - Math
> >Background (CRC press).ps Chapter 5 - Pseudo Random Bit Generators.ps Cipher
> >Block Chaining.ps clipper.txt Correlations in RC6.ps cramer-shoup public
> >key.pdf crc faq.pdf CRC Press (Applied Crypto) Block Ciphers.ps Cryptanalysis
> >of Blowfish.ps Cryptanalysis of FROG.pdf Cryptanalysis of MAGENTA.pdf
> >Cryptanalysis of loki89.ps Cryptanalysis of TWOPRIME.pdf Cryptanalysis of
> >loki91.ps Cryptanalysis of MD5.ps Cryptanalysis of ICE.ps Cryptanalysis of
> >RC5.ps Cryptanalysis of Lok97.ps Cryptanalysis of Lucifer.ps Cryptanalysis of
> >CMEA.ps crypto4n2.pdf Cryptographic File Systems.ps Crypton V1.0 AES
> >Submission.ps Cryptanalysis of SKIPJACK (impossible differentials).ps
> >Cryptanalysis of ORYX.ps DEAL AES Submission.pdf design-vulnerabilities.pdf
> >DFC AES Submission.ps DFC AES Submission (update).ps DFC for smartcards.ps
> >diehard.zip Differential Cryptanalysis of FEAL and N-HASH.ps Differential
> >Cryptanalysis of DES-like systems.ps Differential Cryptanalysis of IDEA.ps
> >Differential Cryptanalysis of Kafre, Loki, REDOC .ps Differential
> >Cryptanalysis of SAFER.ps diffusion in the AES candidates.pdf discrete
> >logratihms in finite fields and their cryptographic significance.pdf E2 AES
> >Submission.pdf Elements of Linear and Abstract Algebra.ps Elliptic Curve
> >Cryptography Faq.pdf encryption tutorial (part 1).pdf fast new des.ps
> >fast_software_encryption.pdf feistel networks.pdf fibonacci generators.ps
> >Formal Treatment of remote key encryption.ps FROG AES Submission.pdf
> >GoldmanRivest-MakingMaximumEntropyComputationsEasierByAddingExtraConstraints.
> >ps How to forge DES messages in {2^28} steps.ps How to protect DES against
> >exhaustive key search DESX.ps How to strengthen DES using existing
> >hardware.ps hpc-over.pdf hpc-spec.pdf hpc-subm.pdf IDEACrypt_Coprocessor.pdf
> >IDEACrypt_Kernel.pdf Key Schedule Cryptanalysis PART ONE.pdf Key Schedule
> >Cryptanalysis PART TWO.ps khufu.tar.gz Links between linear and differential
> >analysis.ps list.txt LOKI97 AES Submission.ps lottery.pdf Magenta AES
> >Submission.pdf MARS AES Submission.pdf Master Key Cryptosystems.ps mod n
> >analysis.pdf multi-permutations.ps observation of key schedule (TwoFish).pdf
> >On Modes of operations.ps on the construction of variable-input-length
> >ciphers.ps On the Number Field Sieve.ps On the security of the CS-Cipher.ps
> >On the security of Quantum Cryptography against Collective Attacks.ps
> >Parallel FFT-Hashing.ps pentum optimizations.txt personal-entropy.pdf
> >Proth.ini Provably secure one-way hash functions.ps Provable Security using
> >Decorrelatiion.ps provably secure and efficient block ciphers.ps pseudo1
> >(frobenius primes).ps pseudorandom_number.pdf quasi.ps r1report.pdf Random
> >Bit Generators using smoke_detectors.ps ranno.ps rc2-fse.ps rc4_revealed.txt
> >RC4_TEST.txt rc6-notes.txt RC6 AES Submission.ps realrandomnum.txt related
> >key cryptanalysis.ps Rijndael.pdf
> >Rivest-GameTreeSearchingByMinMaxApproximation.ps Rivest-MD5.pdf
> >RivestShamirWagner-timelock.ps Rivest-MD4.pdf rivest-factoring.txt rsa129.pdf
> >RSA Algorithm - A method for obtaining digital signatures and public key
> >cryptography.ps RSA evalutation of RC5.pdf RSALABS Faq.pdf rsa on MD
> >algorithms.pdf RSA ROUND ONE.pdf safer.pdf safer key schedule.pdf
> >SAFERPPT.pdf sbox generation for TIGER.ps schneier-talk.pdf sciam98.txt
> >seal.ps Searching for ultimate correlation (Stream Ciphers).ps sec2_1.ps
> >sec2_3.ps sec2_4.ps sec2_6.ps sec2_7.ps security.ps Security of MacGuffin
> >(Thesis).ps self-study course in cryptanalysis.pdf SERPENT AES Submission.ps
> >SHA-0 Collisions.ps simon_sh.ps skipjack-1.pdf snefru.c sol.c sol.exe Sorting
> >Out Zero Knowledge.ps speed-sac.pdf square.pdf ssl-challenge.txt
> >street_performer.pdf tests.txt The AKELARRE block cipher.ps The bit
> >extraction problem or t-Resilient functions.ps The BLOWFISH block cipher.pdf
> >The Boomerang Attack.ps The CAST-128 block cipher.pdf The CRISP block
> >cipher.ps The CS block cipher.pdf The ICE block cipher.ps The IDEA block
> >cipher.ps The LOKI91 block cipher.ps The LOKI89 block cipher.ps The MacGuffin
> >block cipher.ps The RC5 block cipher.ps The Security of Cryptographic
> >Primitives.ps The Slide Attack.ps The TEA block cipher.ps The XTEA block
> >cipher.ps Three Xor-Lemmas.ps tis_walker_export_101293_hr.txt turtle.ps
> >Twinkle RSA factoring device.ps Twofish AES Submission.pdf
> >twofish-reference-c.zip twofish-optimized-c.zip twofish-assem.zip vp.txt Why
> >Cryptosystems Fail.ps Word Autokey Cipher (WAKE).ps WS_FTP.LOG xmx a firmware
> >oriented block cipher.ps xormacs.ps xxtea.ps yarrow-full.pdf
> >
> >
> >Sent via Deja.com http://www.deja.com/
> >Share what you know. Learn what you don't.
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Comments on ECC
Date: 21 Sep 1999 11:26:16 +0200
"Sam Simpson" <[EMAIL PROTECTED]> writes:
> Specifically of interest to me were the comments by Adleman:
> "It is correct that I am suspicious of elliptic curve cryptosystems.
> [...]
Well if you let a marketing dude from RSA Data Security hand-pick
quotes from the inventors of RSA, then you are going to get something
so biased as to be useless.
Adleman's statement continues "I am fortified in this opinion by the
fact that [...there are subexponential algorithms for the Jacobians of
large-genus hyperelliptic curves...]" which is bogus. One might as
well claim that factoring 1000-bit numbers with similar sized factors
must be easy with two factors because it's easy with lots of factors.
Nobody knows whether ECDL will remain exponential or not, and I don't
think many people would bet a whole lot of money either way. But as
the quote from Claus Schnorr says, it is likely to remain more
difficult than factoring. I believe most number-theorists subscribe to
a view similar to his:
==============================================================================
>From what we know now, it looks as if the discrete logarithm problem
for elliptic curves is somewhat harder than the discrete logarithm
modulo primes p which itself looks a bit harder than factoring
integers. But it is unreasonable to assume that it has straight
exponential complexity.
A very particular case are elliptic curves in fields of powers of 2.
They have been proposed since there the arithmetic is quite efficient.
This particular choice seems to be risky. There are only a few fields
that can be used. If the discrete logarithm problem collapses for
these particular fields it nearly collapses for all elliptic curves of
this type.
==============================================================================
Bye,
Rob.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: Comments on ECC
Date: Tue, 21 Sep 1999 09:47:05 +0100
Thanks for the comments. I wasn't question anyone's views (I'm in no
position to do so...), but rather interested on peoples opinions on
the Adleman quote.
Regards,
--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because
he's kill filed. See http://www.openpgp.net/FUD for why!
DJohn37050 <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Certicom has had an ECC challenge out for a few years and has had
commercial
> implementations of ECC before that. So far, the best attacks on
the ECC
> challenges align with theory very well.
>
> The truth is that the known best attacks on IFP (RSA), DLP (DSA)
and ECDLP
> (ECDSA) involve sophisticated math. An expert in one area should
not
> necessarily be considered an expert in another, except that
Pollard's name
> comes up everywhere. Especially when one considers the source of
the quoted
> statement (the "A" in RSA), it should be taken with a grain of
salt, as ECC is
> an algorithmic competitor to RSA and is "stronger, shorter, faster,
etc."
>
> And there are rumors that some of the ECC naysayers are coming
around.
> Certainly NIST's endorsement of ECC for government use says a lot.
Watch this
> space.
> Don Johnson
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Comments on ECC
Date: 21 Sep 1999 11:49:57 +0200
[EMAIL PROTECTED] (DJohn37050) writes:
> Certicom has had an ECC challenge out for a few years
Good chance to plug my ECDL project:
http://pauillac.inria.fr/~harley/ecdl6/readMe.html
We're speeding along with hundreds of people and machines. Anybody
who wants to join better hurry up before it's too late!
>So far, the best attacks on the ECC challenges align with theory very well.
Sigh. As I already said here recently, this statement is only true
when the theory is updated to take into account new attacks found
during the lifetime of the challenge. Then it is vacuously true,
uninteresting and devoid of any information content.
> And there are rumors that some of the ECC naysayers are coming around.
There are also rumours that Certicom is finally recognising that
choosing curves defined over the boolean field is Probably Not Such A
Good Idea After All.
> Certainly NIST's endorsement of ECC for government use says a lot.
Yes. Being endorsed by basically the same crowd who endorsed 40-bit
DES and similar crapola, not so long ago, verges on being a liability.
Bye,
Rob.
PS: For readers who are wondering: I have no connection with any
crypto companies. I just tell it like it is.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: AES finalists AMD Athlon performance?
Date: Tue, 21 Sep 1999 11:32:45 GMT
In article <[EMAIL PROTECTED]>,
David Crick <[EMAIL PROTECTED]> wrote:
> Does anyone know of actual/predicted performance of the AES
> finalists on the AMD Athlon processor?
What about highend AMD k6-2 and MII? (Although cyrix is slowly dying so the
last may be moot)
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Tue, 21 Sep 1999 11:31:24 GMT
In article <7s6fgk$bgp$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Counter mode -- like OFB, CBC, and CFB mode -- has security problems
> after about 2^32 outputs (and not before), due to the non-random number
> of repeats. This is a well-known consequence of the birthday paradox.
>
> In practice, most well-designed cryptosystems change the key long before
> the birthday limit. So no, this should not be a problem in real life.
>
> Note that this is an artifact of a 64-bit block length, and is the reason
> that the AES will have a 128-bit block length.
Hence don't use DES for a Yarrow implementation?
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES finalists AMD Athlon performance?
Date: Tue, 21 Sep 1999 12:09:42 GMT
In article <[EMAIL PROTECTED]>,
David Crick <[EMAIL PROTECTED]> wrote:
> Does anyone know of actual/predicted performance of the AES
> finalists on the AMD Athlon processor?
>
The only thing I can say is that ciphers like RC6 and MARS will recieve
a significant boost. This is because the Athlon has a faster MUL
instruction. Rumor has it that it will only take 1 clock cycle. I'm
not 100% sure on this, but I do know it is a bit faster. Otherwise, I'd
say you'd receive your basic speed boost from the higher megahertz.
Casey
> David.
>
> --
> +-------------------------------------------------------------------+
> | David Crick [EMAIL PROTECTED] http://members.tripod.com/vidcad/ |
> | Damon Hill WC96 Tribute: http://www.geocities.com/MotorCity/4236/ |
> | M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
> | ICQ#: 46605825 PGP Public Keys: RSA 0x22D5C7A9 DH/DSS 0xBE63D7C7 |
> +-------------------------------------------------------------------+
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Tue, 21 Sep 1999 12:12:39 GMT
Okay, I understand your motives and I think I understand your
application. The relevant assumptions are:
1) Hash function and block cipher are secure.
2) Key size bits of entropy are available at initialization.
3) Little, if any, entropy available while the PRNG is in use.
4) Resistance to backtracking is important.
Your PRNG Ocotillo consists of a block cipher in counter mode, keyed
with a hash of the initial entropy. In order to resist backtracking
attacks you hash the output of the block cipher and you perturb the
counter using a hash that includes the scant additional entropy that
is available. Ocotillo is constructed as follows:
k = H(initial entropy)
c_i = H(c_{i-1}, i | a tiny bit of additional entropy)
R_i = H(R_{i-1}, E(k, c_{i-1}))
Given your design goals, I think the following PRNG construction is
both simpler and has superior resistance to attack:
k_0 = H(initial entropy)
R_i = E(k_{i-1}, 2i-1)
k_i = E(k_{i-1}, 2i)
Like Ocotillo, this PRNG consists of a block cipher in counter mode,
keyed with a hash of the initial entropy. However, to prevent
backtracking the block cipher is rekeyed as opposed to hashing the
output of the cipher. Also, the security of this PRNG does not depend
upon the hash function providing a cryptographically secure bit
stream. On the down side, this PRNG would almost certainly be slower
than Ocotillo since the block cipher's key schedule is invoked for
each block of pseudo-random output.
Despite the fact that this PRNG rekeys, it, like Ocotillo, lacks a
reseed mechanism. As you pointed out in your message, if additional
entropy is expected to be available the PRNG should include a
mechanism that uses the entropy to reseed.
-Richard
------------------------------
From: Erwin Bolwidt <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Tue, 21 Sep 1999 14:31:57 +0200
"Douglas A. Gwyn" wrote:
> [EMAIL PROTECTED] wrote:
> > And here we come to Schrodinger's cat. One of the interpretations of
> > quantum mechanics held that a superposed quantum state did not resolve
> > itself into one state until it was exposed to the gaze of a *human
> > observer*.
>
> The point of Schr�dinger's cat is that it points up the logical
> problem with that interpretation (which seems to have fooled
> Roger Penrose too) -- why can't the cat play the role of observer?
Isn't that the problem; who observes the observer?
If you checked on the cat and I haven't spoken with you, isn't the state of
the cat still undefined to me? And (let's not make this personal) if the
observer dies before having spoken to anyone, isn't the state of the cat
completely undefined again?
(At least until a technique is known to read memories out of human brain
tissue)
I guess what I'm wondering is, does nature take into account the
peculiarities of human consciousness; if you've seen something, spoke to me,
but didn't tell me what you saw, is that something still undefined to me, or
is it defined to me because we exchanged photons and my quantum state has
merged with yours?
>
> A self-consistent quantum theory of measurement has to be apply to
> the measuring device as well as to the object being measured.
> There *is* at least one such theory in general use today.
Erwin
------------------------------
From: Rochus Wessels <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: 21 Sep 1999 14:41:06 +0200
[EMAIL PROTECTED] (jerome) writes:
> On Mon, 20 Sep 1999 12:07:40 -0700, Eric Lee Green wrote:
> if the non-repeating property is mandatory, it makes the output
> more predictable, at least in theory.
After half of the possible outputs the advantage of the adversary is 1 bit.
I won't call this a problem, unless there is not enough entropy in the
real random sources to reseed the PRNG in the time until this happens.
------------------------------
From: Rochus Wessels <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: 21 Sep 1999 14:49:56 +0200
Rochus Wessels <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] (jerome) writes:
> > On Mon, 20 Sep 1999 12:07:40 -0700, Eric Lee Green wrote:
> > if the non-repeating property is mandatory, it makes the output
> > more predictable, at least in theory.
> After half of the possible outputs the advantage of the adversary is 1 bit.
> I won't call this a problem, unless there is not enough entropy in the
> real random sources to reseed the PRNG in the time until this happens.
^^^^^^ reKEY (sorry)
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Comments on ECC
Date: 21 Sep 1999 12:51:09 GMT
Regarding advances in theory since the challenges came out, I know of 3:
1) Smart attack, very rare curves, easily excluded.
2) negative of a point speedup, applies to all curves, reduction in ops by
dividing by SQROOT(2) ( very small reduction)
3) Koblitz speedup, applies to Koblitz curves only (small reduction).
None of these are tremendous breakthroughs, they are refinements to the
previous theory.
So, one point is that a challenge is SUPPOSED to generate interest. And theory
is evolving by filling in the details.
This is not vacuous.
Another point is that structure is being
factored into the attack complexity equations, I think this is good as it
allows a more precise analysis, as structure seems the best (only?) hope to
attack ECC.
Don Johnson
------------------------------
** 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
******************************
