Cryptography-Digest Digest #582, Volume #10 Wed, 17 Nov 99 17:13:03 EST
Contents:
Questioning Lenstra's key size recommendations (lcs Mixmaster Remailer)
Re: AES cyphers leak information like sieves (Anton Stiglic)
Re: weak ciphers and their usage (James Felling)
Re: Identification in Smart Cards (Candelaria =?iso-8859-1?Q?Hern=E1ndez?= Goya)
Re: Questioning Lenstra's key size recommendations (DJohn37050)
Re: more about the random number generator (Anton Stiglic)
Re: AES cyphers leak information like sieves (Tom St Denis)
Re: more about the random number generator (William Rowden)
Re: more about the random number generator (Tom St Denis)
Re: more about the random number generator (Tom St Denis)
Re: weak ciphers and their usage (Tom St Denis)
Re: AES cyphers leak information like sieves (Tim Tyler)
Re: AES cyphers leak information like sieves (Jerry Coffin)
Re: AES cyphers leak information like sieves (Jerry Coffin)
----------------------------------------------------------------------------
Date: 17 Nov 1999 18:00:06 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Questioning Lenstra's key size recommendations
It was asked:
> I just browsed through the Lenstra paper about their research on key
> sizes ( http://www.cryptosavvy.com/ ) and ask myself whether I
> understand it correctly that they suggest to use today more than 1024 bits
> for the DSA prime group but keep the size of the subgroup at 160 bits.
>
> The old suggestion used to be that the 160 bit hash size matches the
> computional effort of the 1024 bit group and that there is no point in
> increasing the size of the group while not also increasing the size of
> the subgroup (and that of the hash of course).
>
> Given this paper, this cannot be held true anymore?
Lenstra and Verheul make several assumptions which make their results
somewhat questionable:
- They assume cryptanalytic progress at the rate of doubling every 18
months, when applied to the field size (1024 bit DSA "key size") but
they assume there will be no progress with respect to the subgroup size
(160 bits). Note, this is not hardware progress, it is improvement
in algorithms, theories, and ideas. This is in reasonable accordance
with recent history but it is difficult to extrapolate it forward.
- They base the field size estimates on RSA factoring results, but
discrete log systems have a much more difficult matrix reduction step,
and in fact there is little experience to judge how much more difficult
this part is.
- They do not use the fact that the matrix reduction step is thought to
be immune to parallel attacks, while the 160 bit subgroup attacks can
be applied in parallel.
They do attempt to compensate for some of these acknowledged shortcomings
by fudging their results one way or the other, intentionally adding
small biases here and there, but as a result it is difficult to know
how precisely their estimates can be taken.
In terms of DSA, to compare the 160 bit subgroup size with the field size
today, it is necessary to remove the assumed improvement in cryptanalysis.
Section 4.6 describes the rather involved numerology necessary to read
the results off of their table. There are two different models, depending
on whether one wants equivalent computational effort or equivalent costs.
Using their formulas for the equivalent-cost case, a symmetric key size of
88 bits corresponds today to a subgroup size of 159.5 bits, and a field
size (prime modulus size) of 1120 bits. This is roughly consistent with
the high end of the DSS recommendations (160 bits and 1024 bits).
Based on this, it would not appear to be appropriate to go to a
significantly higher prime size, keeping subgroup size the same, in the
hope of increasing security in today's world.
Looking forward, however, it might be reasonable to increase the prime
size with the expectation not of increased security, but if avoiding a
loss of security if algorithm improvements continue to occur in discrete
logs. Here one must judge whether the Lenstra assumption of a factor
of two improvement in theoretical DL attacks will continue to occur
every 18 months. One must also consider whether parallelization will
become increasingly important, which would increase the effectiveness
of attacks against the subgroup compared to the matrix-limited attacks
against the prime field.
Certainly, increasing the prime size will not harm your security.
The question is whether it buys you significantly more security. In the
short run the answer appears to be no, in the long run the answer is,
maybe, but it depends on your assumptions. It would be preferable to
increase all parameters associated with DSS (subgroup size, hash size,
and prime modulus size) in order to reliably increase the security in
the face of improved future attacks.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Date: Wed, 17 Nov 1999 13:20:04 -0500
Tim Tyler wrote:
>
> After reading the recent contributions to the "SCOTT16U SOLUTION ON THE
> WEB" thread in this forum, I was disturbed to find that a number of
> sci.crypt subscribers were /still/ towing the party line that the AES
> block cyphers might have some security value - *despite* the efforts of
> David Scott to explain exactly why they should be considered insecure.
>
> The problem is simple: the AES cyphers are fixed 128-bit block cyphers.
> The encode identical blocks in the same way. For certain types of
> message, this is a complete security disaster.
Duhhh!! This is why they have invented chainging modes of encryption.
I'm begining to think that Tim Tyler is in fact SCOOT16U, just using
an e-mail adress with a different name....
Anton
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: weak ciphers and their usage
Date: Wed, 17 Nov 1999 12:24:22 -0600
A wraped mode is Gary wrote:
> Wrapped modes effectively treat the whole ciphertext as a block (eg XTEA
> block version).
> The advantages are:
> Attacks (even parallel) require the memory of the whole ciphertext rather
> than a small block.
> Key stretching automatically occurs if the stretch required is divided by
> the whole plaintext size (in key size units) and added to the minimum
> recommended wrapped rounds
>
>
> The disadvantages are:
> Error propogation wiping out the whole plaintext.
slower, (2X min -- possibly more), requires more memory to implement(whole
message vs 2 blocks),
>
>
> Any other advantages or disadvantages?
------------------------------
Date: Wed, 17 Nov 1999 18:53:13 +0000
From: Candelaria =?iso-8859-1?Q?Hern=E1ndez?= Goya <[EMAIL PROTECTED]>
Subject: Re: Identification in Smart Cards
Thank you for your help.
I´m interested in zero-knowledge protocols used in smart cards. I know
the book of M. Alfred J. Menezes, Paul C. van Oorschot and Scott
A.Vanstone and the protocols show there.
Cande
Pascal Nourry escribió:
> > I´m new in this news group. I´m looking for information about
> > protocols for Identification in Smart Cards (on The Net).
>
> A good begin for smartcards should be
> http://www.gemplus.com/
> http://www.gemplus.com/smart/r_d/publications/index.htm
>
> For basic crypto algorithms, I recommand you
> http://www.cacr.math.uwaterloo.ca/hac/
> (thank you M. Alfred J. Menezes, Paul C. van Oorschot and Scott A.
> Vanstone)
>
> And also
> http://grouper.ieee.org/groups/1363/index.html
>
> Can you specify what your are exactly looking for?
>
> Yours,
> P.N. a new guy too
>
> --
> ********************************************************
> Pascal NOURRY
> email : [EMAIL PROTECTED]
> page personnelle : http://www.gmm.insa-tlse.fr/~nourry
> ********************************************************
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Questioning Lenstra's key size recommendations
Date: 17 Nov 1999 19:01:46 GMT
ANSI X9.30 DSA-2 will have increased keysizes. The subgroup keysizes (q) are
twice the AES keysizes. The field keysizes get large, over 15,000 bits for a
256 bit AES keysize. See my PKS '99 paper at www.certicom.com for the table.
Don Johnson
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Wed, 17 Nov 1999 14:03:54 -0500
Tom St Denis wrote:
>
> I got a program from http://www.fourmilab.ch/random/
>
> to perform pseudo-randomness tests on files. I made a file using my
> rng [based on the winrng] until I got bored... here are the results
> [and if dejanews messes up the following lines, I can re-email it in
> private].
>
> Entropy = 1.000000 bits per bit.
This is the entropy of a source spitting out bits that follow a
uniformaly
random distribution. So this would be the best you can get for *this*
result.
>
> Optimum compression would reduce the size
> of this 417792 bit file by 0 percent.
This comes directly from the entropy result.
>
> Chi square distribution for 417792 samples is 0.14, and randomly
> would exceed this value 50.00 percent of the times.
>
I don't remember my probability distributions well enough to comment
on this. Maybe someone else can give their input?
> Arithmetic mean value of data bits is 0.5003 (0.5 = random).
The arethmetic mean of a discret set A = {a1, a2, ..., aN}
is A(X) = 1/N Sum a_i, so if X comes from a uniform distribution
this should be close to 0.5. 0.5003 is a good result.
> Monte Carlo value for Pi is 3.136948529 (error 0.15 percent).
A Montre Carlo algorithm is an alogritm that uses randomness and always
gives a result with some error probability (contrary to a Los Vagas
algo.
which uses randomness but either gives the exact value or no value at
all).
There exists Monte Carlo algorithms for integration. So I'll take a
guess
and say the Monte Carlo algo for Pi, in question, is an algo that
computes
Pi = Integral[0,1] of 4*sqroot(1-x^2) dx.
This is but just one of many formulas that gives Pi, it's based on the
calculation of the area of a unit circle. Can someone confirm if this
is
in fact what is beeing used?
I guess this is a good result.
> Serial correlation coefficient is 0.001254 (totally uncorrelated = 0.0).
This looks like the test that checks the number of d-grams. Can someone
comment?
>
> Is this good or bad? From what I read at the site this is really good
> for a first pass at it...
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
Anton
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Date: Wed, 17 Nov 1999 19:13:58 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The use of block chaining certainly improves things. It is the
employment
> of methods of diffusing information over a large area of the
cyphertext
> that I am advocating.
>
> Block chaining strikes me as a crude hack, though. It only propagates
> information through the file in one direction, and will /still/ expose
> some weaknesses at random if repeated blocks and repeated data should
> coincide by chance.
>
> The use of a proper diffusion technique would avoid this ever
happening.
It's perfectly possible to encode ABBC to DEEF with ANY chaining mode
though. And assuming for example you have a random salt and IV, then
the first few blocks while perhaps containing the same info, will not
have the same bits xored before encryption with a different key
altogether.
Moral: Use a IV and salt your key!
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Wed, 17 Nov 1999 19:21:59 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> : William Rowden wrote:
>
> :> > Entropy = 1.000000 bits per bit.
> :> That's wonderful.
>
> : It's more that wonderful, it's fantastic (in the literal meaning
> : of the word).
>
> That's because it's false. "ENT" lies. It uses a simple formula
> to *estimate* the entropy on the basis of a statistical model,
Are you drawing a distinction between an unbiased estimator calculated
from a sample and a value calculated from a population? While that
distinction may have theoretical interest in this case, it's
probably irrelevant to the use of the entropy statistic that started
this thread.
> and then presents it to the user as the genuine article.
I sincerely doubt that anyone was misled by this "lie." If Tom read
that the average male is 175.5 cm tall in the USA and 182.5 cm in the
Netherlands, would he for a moment think that someone measured *every*
citizen?
> Calculating anything which remotely approaches the actual entropy is -
> of course - not computationally practical.
That is--of course--true if the set of possible messages or the number
of messages transmitted is large or infinite. Nevertheless, average
information calculations can *estimate*, for example, the efficiency of
a compression algorithm for a source of interest, or the disorder
produced by a RNG.
I don't see why the "genuine article" is relevant to the latter use of
entropy. Could someone please educate me on information theory? Where
is Claude Shannon when you need him?
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Wed, 17 Nov 1999 19:21:59 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> : William Rowden wrote:
>
> :> > Entropy = 1.000000 bits per bit.
> :> That's wonderful.
>
> : It's more that wonderful, it's fantastic (in the literal meaning
> : of the word).
>
> That's because it's false. "ENT" lies. It uses a simple formula
> to *estimate* the entropy on the basis of a statistical model, and
> then presents it to the user as the genuine article.
>
> Calculating anything which remotely approaches the actual entropy is -
of
> course - not computationally practical.
Not to mention impossible, but from a empiracle stand point any simple
order-n predictor is good enough.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Wed, 17 Nov 1999 19:20:43 GMT
In article <[EMAIL PROTECTED]>,
"Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
> You and I may not know the nooks and crannies of the task scheduler,
but
> others might. While I doubt even Microsoft(tm) would claim to know
all the
> aspects of their product they and others certainly know enough to
create a
> task environment that is predictable. This is not hard to envision
if you
> consider ways to simplify the process hierarchy into one with
predictable
> behavior.
However if you are actually using the computer [i.e say
winamp+icq+email open which I and many others do have going] then it's
random. Here are some ideas why:
1) Superscalar cpus. The loop which flips the bit probably takes about
30 cycles or so to complete [including the call to gettickcount()].
However stalls [caused by jumps, cache fills, agi faults ...] can
consume odd amounts of cycles here and there.
2) Multi-threads. While ICQ may resemble one task, it's probably 2 or
3 threads. Each thread probably works on some interrupt scheme [i.e
incomming packets etc...]. These are fairly irregular This includes
disk activity etc...
3) Human usage. Typing, moving the mouse all consume cycles as well..
These are just ideas... any other ideas please?
I would admit in SAFE MODE, with zero tasks open it's probably not very
random at all. But remember, a) we are called users cause we use the
computer, and b) I am only getting about 80 bits/sec out of this
thing... not a heck of a lot..
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: weak ciphers and their usage
Date: Wed, 17 Nov 1999 19:29:24 GMT
In article <80t03s$13co$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> Nonsense Dave just as you lack the ability to understand the
complexites
> of my code. You seem to lack a basic understand of what common
chaining does.
> Here is something you can do with a crappy AES type of encryption
with your
> secret IV. Take a long file and encrypt it. Cut off the front third
and last
> third of the file. Know if a good cryptographer like me or better in
case
> your not good enough to handle it. Is given the middle thrid of file
with the
> cipher and key but not the IV the center third of file can be
recovered easily
> but if you do the same thing with scott16u or scott19u or any AES
cipher
> using Wrapped PCBC the infromation can not be recovered. The fact is
with
> normal chaining the information is localized very close to where it
is in the
> original file.
'gimme the ciphertext and key ...' [sic], oh is that all. I think the
general understanding is that getting ciphertext is easier then getting
the key. People are not going to hand over the key [if they can
prevent it]. So your entire argument is moot. Worst of all is when I
try to bring a positive note to wpcbc [like when you lack rng
facilities] you completely ignore me.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Reply-To: [EMAIL PROTECTED]
Date: Wed, 17 Nov 1999 19:49:12 GMT
Jerry Coffin <[EMAIL PROTECTED]> wrote:
: Those who really believe that simply re-transmitting a message is
: reasonable if it doesn't come through intact should read _Between Silk
: and Cyanide_ continuously until they learn better.
What are you talking about? Retransmitting a cyphertext presents
practically no security risk at all.
The only risk is that the opponent gets a second chance at intercepting
the message - but it is fairly normal to assume that he's intercepting
everything anyway.
: IOW, advocating that "proper" security always requires pre-compression
: and a particular "all or nothing" chaining mode is simply nonsense.
Who's doing this?
: NIST (and others who have a clue) keep the chaining mode, the
: algorithm and possible pre-compression separate for an excellent
: reason: they bloody well NEED to be separate.
Keeping compression separate is a good idea. However, a "chaining mode"
is not a necessary component of a cypher. For one thing it necessarily
introduces a serial component to encyphering. If you have a parallel
machine available, introducing something like this may kill performance.
My code is mainly targetted at FPGAs. In such domains, "chaining modes"
are not really on the menu.
: There's more to secure communication than JUST ensuring against
: somebody else reading your message -- in many situations, being
: certain the intended recipient CAN read (at least as much as possible
: of) the message is JUST as important, and perhaps even MORE important.
This is a virtue of using error-correction technology. No matter /how/
noisy a channel you are faced with you can still get a 99.99% chance of
successful transmission if you throw bandwidth at the problem.
Under the *insanely*-infrequent conditions where you have limited
bandwidth, high error rates, no chance of resending a failed message, and
you /must/ get some fragments of your message across, this can /still/ be
done by splitting the message up. This reduces it to a cookbook-mode
block cypher. You can /still/ apply block chaining to consecutive
messages if you /really/ want.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The unauditioned chorus swells.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: AES cyphers leak information like sieves
Date: Wed, 17 Nov 1999 13:02:48 -0700
In article <80tfml$tg6$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> >What you've said is true if and only if the cipher is used in ECB
> >mode. If you run into the situationa you mention above, you'd
> >probably want to use CBC or CFB mode instead.
> I have showed how CBC and CFB are weak in some cases.
> Even Bruce had the balls in his book to say the the error correction
> should be handled in the transmission protocals. Hell even in the
> Navy they don't require radio operators to use morse code any more
> it is going to secure digital communications. But maybe that is over
> your head.
Morse code or otherwise isn't the question. If you have the luxury of
being able to verify each block and re-transmit as needed, then yes,
that's almost certainly better than depending upon recoverability of
errors using CBC. There are, however, still situations where people
use radios (for example) and can't wait around for the message to be
acknowledged and re-transmit whatever's needed. If you can do it,
great. If you can't, using a protocol that assumes you can isn't a
good idea.
The Navy using "secure digital communications" doesn't mean this no
longer matters. In fact, what we're discussing is exactly how you'd
design that secure digital communication channel. You, apparently,
would design it so it was highly prone to massive failures under the
slightest atmospheric problems. I, for one, prefer more robust
systems.
> >You're also apparently ignoring the fact that David Scott's choice of
> >chaining mode is a complete disaster in some situations as well. If,
> I admit that it is not the best for certain cituations. But I also
> realize that the AES methods are not the best for all situations either
> And that is something your afraid to admit.
You're simply putting words into my mouth: I've never said anything
stating or implying that a particular group of chaining modes being
sufficient for all possible situations.
> >Those who really believe that simply re-transmitting a message is
> >reasonable if it doesn't come through intact should read _Between Silk
> >and Cyanide_ continuously until they learn better.
> Bullshit.
I see your vocabulary remains as lacking in eloquence as ever. If you
honestly believe that nobody's life will ever be placed in danger
again, or something like that, you're simply an idiot.
> It is obvious your to don't bother to read my posts.
That's partly true -- I normally have you in the "Bozo bin" so nicely
provided by the newsreader I use. I'm responding to this only because
I saw another reply to your idiocy, and decided that this once it was
worth pointing out some of your lies.
> Like I said mine is for "all or nothing". If you want to use stuff
> where the recipent is not sure if the whole message is ther fine.
> I prefer stuff at this for my files and messages that is a the more
> secure than what the weak AES methods will be. I suppose you
> belive the NSA will not be able to break them. I think they might
> be able so I will continue to push for real secure crypto. Something
> you obviously don't care about.
As soon as you can break a message I've encrypted, you'll have some
room to talk about my not caring about security. Right now, you're
just doing your usual: claiming that anybody who doesn't follow your
recipe to the letter is an idiot or a fraud. It's simply not true.
It never has been and it never will be.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: AES cyphers leak information like sieves
Date: Wed, 17 Nov 1999 13:12:00 -0700
In article <80tg4o$tg6$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> You sir are ignoring reality. If you do the test I showed you.
> You will see that all you pet modes are an illusion. They do
> not spread the information though the file. But either you
> don't understand or are to lazy to test.
Quite the contrary: that's a well-known feature of (for example) CBC.
Its self-synchronizing property is well-known and useful. I don't
know what test you're talking about, but proving its existence is
roughly as useful as yet another proof of the Pythagorean theorem: it
might show that eventually, with sufficient tutoring, you'll learn
enough about cryptography to be worth listening to, but provides no
new information about the chaining mode at all.
> Think why are they are this way. Could it be of use to the NSA.
If you can show a practical attack due to the nature of CBC, feel free
to do so. Right now, you're apparently of the opinion that a purely
imaginary attack is more important than a very real error-recovery
ability.
> Look even
> PGP use a weak chaing mode with compression. Most
> people don't have the software to recover the real file
> if a change occurred in the middle of the compressed encrypted
> text. So what fuckin good does this error recovery do anyone
> who depends on PGP. It does them no fucking good it can
> only be of use to a dedicated attacker.
For those looking on, I'll translate this into understandable (and
civil) English: you're just as clueless as ever...
> That is also way intelligent people should have the option
> of using something like "wrapped PCBC" when they want
> a far higher degree of security than the NSA 3 letter blessed
> mods that you foolish think is safe.
If you want to claim that one thing is more secure than the other, you
need to quantify the security of each and then compare the two. Right
now you're just making your usual unsupported claims. Oh well, back
into the Bozo Bin with you...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
** 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
******************************
