Cryptography-Digest Digest #828, Volume #11 Sun, 21 May 00 06:13:01 EDT
Contents:
Re: AES final comment deadline is May 15 (DJohn37050)
Re: More on Pi and randomness (Dave Seaman)
Re: QUESTIONS About ALGOS !! ("Scott Fluhrer")
Re: More on Pi and randomness ("r.e.s.")
Re: More on Pi and randomness ("r.e.s.")
Re: AES final comment deadline is May 15 (Scott Contini)
Re: Matrix reduction (Scott Contini)
Re: Compare 3DES's. (Jonathan Thornburg)
Re: Re: Who has got RSA simple program (sources on C/C++)? (Maxim L)
Re: Is OTP unbreakable? (Mok-Kong Shen)
Re: what is the status finite automata base cryptosystems? (Mok-Kong Shen)
Re: Interpretation of Hitachi patent claims (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: AES final comment deadline is May 15
Date: 21 May 2000 02:29:57 GMT
Not usually, just short messages that are changing keys frequently. This
happens in IPSEC, for example.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Dave Seaman)
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: 20 May 2000 22:06:03 -0500
In article <8g74kv$rf2$[EMAIL PROTECTED]>,
r.e.s. <[EMAIL PROTECTED]> wrote:
>"Clive Tooth" <[EMAIL PROTECTED]> wrote ...
>[...]
>| Some things are known about the decimal digits of pi
>| in general. For example, for no positive integer n
>| are the digits n thru 100*n all equal to zero.
>Some such things are known in general, but I think that
>that last sentence isn't one of them -- for if it's
>true, then pi is not normal in base 10.
I don't see how that follows. It still could be the case that
arbitrarily long sequences of zeroes appear somewhere in the digits of
pi. It's true that there are limits on how early they can appear, but
the definition of normality is only concerned with the limiting frequency
of each digit string, not with how early it can appear.
>(Last I heard, normality of pi was an open question,
>neither proved nor disproved. Have I missed something?)
No. Not as far as the normality of pi is concerned.
--
Dave Seaman [EMAIL PROTECTED]
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/mumia/021700amnesty.html>
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: QUESTIONS About ALGOS !!
Date: Sat, 20 May 2000 20:18:37 -0700
tomstd <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <8g78oq$fm2$[EMAIL PROTECTED]>, "Scott
> Fluhrer" <[EMAIL PROTECTED]> wrote:
> >
> >Jerry Coffin <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> In article <8fu3it$osb$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED]
> >> says...
> >>
> >> > I'm new in Encryption, and I've to implement an Encryption
> Algo
> >> > for an application.
> >> > But I have to make a choice between efficiency and speed !
> >> > Well I'd like to know if the DES / 3DES is a very fast
> algo ?
> >>
> >> No. Rather the opposite: DES is fairly slow and 3DES is
> about one
> >> third that speed.
> >
> >Actually, before we make the pronouncements "DES is fairly slow
> and 3DES is
> >slower", we need to ask the question: how fast does the OP need
> them to be?
> >His definition of "very fast" may be drasticly different then
> our definition
> >of "very fast". If 3DES is fast enough for the OP (and none of
> the rest of
> >us know enough to say), then 3DES may be a fine choice.
>
> 3des is not a bad choice, just not a good one for many tasks.
> It's cumbersome and slow.
3DES is sufficiently fast and sufficiently secure for many tasks. The OP
has not posted his definition of "fast enough", it might be "encrypt a short
message in less than 10 milliseconds. We would realize this to speed a
"speed is not important" situation, but the OP is not crypto-savvy, and may
not realize that.
For that matter, the same goes for the security requirement. Maybe he
really is hiding things from his kid sister. In that case, DES has plenty
of security.
And, in terms of security, I would, at the present state of the analysis,
trust 3DES over any of the AES candidates -- DES has had a *lot* of
analysis.
> >
> >> > I've been told that Blowfish algorithm was very fast and
> secure.
> >> > What do you think about it ?
> >I agree with Mr. Coffin: there is little reason to use Blowfish
> when Twofish
> >or the other AES finalists are available. You may want to
> avoid RC/6, for
> >intellectual property reasons as noted by others.
> >
> >If they aren't fast enough, then you probably need to look at a
> stream
> >cipher (they tend to be a bit faster), faster hardware, or
> figuring out how
> >to make your application work with encryption that isn't quite
> as fast as
> >you wanted it...
>
> I disagree, just as an example I have RC5 code with 12 rounsd
> [1] that runs at 135 cycles/block [2]. If this is not fast
> enough then tough...
Actually, 16 cycles/byte is fast for a block cipher, a stream cipher can go
much faster. If you can get the rights to Seal (a nontrivial prospect),
that can do 4 cycles/byte. IIRC, ARC4 can do about 7-8 cycles/byte. (And,
I don't remember the details of RC5: is 12 rounds a reduced round version?
That's not recommended unless you know exactly what you are doing).
Of course, if you use an additive stream cipher, you have a number of things
to be concerned about: you should never re-use keystream, and (unless
otherwise protected against), ciphertext modification attacks become much
more effective.
--
poncho
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Sat, 20 May 2000 21:27:16 -0700
"Dave Seaman" <[EMAIL PROTECTED]> wrote ...
| r.e.s. <[EMAIL PROTECTED]> wrote:
| >"Clive Tooth" <[EMAIL PROTECTED]> wrote ...
| >[...]
| >| Some things are known about the decimal digits of pi
| >| in general. For example, for no positive integer n
| >| are the digits n thru 100*n all equal to zero.
|
| >Some such things are known in general, but I think that
| >that last sentence isn't one of them -- for if it's
| >true, then pi is not normal in base 10.
|
| I don't see how that follows.
Take n=1.
If his last sentence is true, then there are no strings
of 100 consecutive zeros in the decimal digits of pi.
If pi is normal, then not only one, but infinitely many
such strings must occur. Ergo, if his last sentence were
true, then pi is not normal (in base 10).
| It still could be the case that arbitrarily long
| sequences of zeroes appear somewhere in the digits of
| pi.
As you note below, normality requires that *every*
finite string must occur with the appropriate limiting
frequency -- and therefore must occur infinitely often.
| It's true that there are limits on how early they can appear,
| but the definition of normality is only concerned with the
| limiting frequency of each digit string, not with how early
| it can appear.
As you say, the limiting frequencies must hold for *each*
(finite-length) digit string, inclusing strings of 100
zeros.
| >(Last I heard, normality of pi was an open question,
| >neither proved nor disproved. Have I missed something?)
|
| No. Not as far as the normality of pi is concerned.
Then you're agreeing with what I've said.
--r.e.s
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Sat, 20 May 2000 22:04:54 -0700
"Dave Seaman" <[EMAIL PROTECTED]> wrote ...
| r.e.s. <[EMAIL PROTECTED]> wrote:
| >"Clive Tooth" <[EMAIL PROTECTED]> wrote ...
| >[...]
| >| Some things are known about the decimal digits of pi
| >| in general. For example, for no positive integer n
| >| are the digits n thru 100*n all equal to zero.
|
| >Some such things are known in general, but I think that
| >that last sentence isn't one of them -- for if it's
| >true, then pi is not normal in base 10.
|
| I don't see how that follows.
Mea culpa ... it doesn't follow.
Please disregard my previous reply.
--r.e.s.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: AES final comment deadline is May 15
Date: 21 May 2000 05:14:19 GMT
In article <[EMAIL PROTECTED]>,
David Blackman <[EMAIL PROTECTED]> wrote:
>Scott Contini wrote:
>
>> RC6 can run on smart cards having as little as 128 bytes of RAM.
>> Keating showed this at the 2nd AES conference. Certainly it doesn't
>> perform great on such smart cards, but for many applications it is
>> good enough.
>>
>> Scott
>
>Serpent, Rijndael, and Twofish all run in under 64 bytes of RAM.
>Considering that the application might want a few bytes for other
>purposes, and that the cheapest MCUs have 128 bytes of RAM or less, i
>think that gives them a significant advantage for low end embedded
>applications. (Whether low end embedded crypto is a good idea is another
>question. But it was specifically mentioned in the AES rules, so it will
>certainly be considered in the judging.)
>
>Serpent, Twofish, and perhaps Rijndael, are looking best by other
>criterion as well. Lets look at it:
>
>Performance on high end custom hardware:
>1. Rijndael
>2. Serpent
>3. Twofish
>
>Key agility (on Pentium 2? I'd like to know for custom hardware where
>it's more important):
>1. Rijndael
>2. RC6
>
>"Security margin" (a dubious idea, but about all we have to go on for
>security)
>1. Serpent
>2. Twofish
>
>Speed on Pentium 2 and similar:
>1. RC6, Rijndael, Twofish about the same
>4. Mars
>5. Serpent
>
>Speed on anything else:
>Different to the above. Serpent often gets much better, RC6 and Mars
>usually get worse.
You are assuming single block encryption. RC6 seems to do quite
well on many modern 32/64-bit processors if you simulataneous encrypt
multiple blocks. You just get a lot more freedom on how to schedule
the multiplies, which makes the timings much better than single block
encryption. Rijndael, Serpent, and Twofish do not get nearly as much of
a benefit from this as RC6 does.
>
>Looking at the cryptanalysis attempts so far, it's clear that Rijndael
>and RC6 are very close to having theoretical breaks. Perhaps Mars as
>well, depending what you thing of the importance of the various
>different rounds. It's hard to imagine those breaks having much
>practical significance, since even if they are extended the extra few
>rounds required, they need ridiculous quantities of chosen or known
>plaintext. But in something you are going to commit to for decades, it
>would make you just a bit nervous.
>
>With Rijndael or RC6 adding a few rounds is easy and should help
>security. Maybe AES will do that if they like other aspects of those
>cyphers. (This is also true for Serpent and Twofish, but it isn't clear
>that they need more rounds.)
>
>It's not immediately obvious how to add rounds to Mars, and you'd
>probably want to put it through lots of analysis afterwards if you did,
>so i hope they don't try that.
>
>Mars has another minor security worry. They changed the key schedule
>after AES round 1 (to make smartcard implementations easier). This means
>that Mars in its current form has had less time for detailed scrutiny
>than the other 4.
>
>Quite a few experts have criticised various aspects of the Twofish
>design, but they've had remarkably little success turning these
>"weaknesses" into actual breaks, even theoretical ones. Even reduced
>round variants of 7 rounds have survived so far. (Twofish has 16
>rounds.)
There is a new attack sent into to NIST by Robshaw and Murphy which
suggests an attack on 8 rounds of Twofish. The complicated design
of Twofish makes it a bit difficult to test how well this attack
really works. Lars Knudsen also sent in some very interesting results
on Twofish which I have not had the time to study yet.
There is a lot to say for having a simple cipher that is easy to analyze,
like RC6. For example, consider this: when RC6 was submitted to the
AES, it was suggested that 16 rounds could be attacked using linear
cryptanalysis, and such an attack was described. Nobody has improved
on this result. The most significant new result is due to Knudsen and
Meier which is approximately the same in effectiveness to the attack
that the designers (and myself) originally outlined. How many of the
other AES finalists can say the same? Moreover, RC6 bases its security
on the data dependent rotation (which is "strengthened" through the
f(x) = 2*x^2 + x function) which has been well studied from 6 years
of public research on RC5. The talk on "high security margins" ignores
the amount of public research that the cipher is based upon. Complex
ciphers take more time to analyze.
I would argue that the cipher RC6 is more understood than any of the
other finalists. The simplicity of its structure allows us to verify
the accuracy of theoretical attacks by experimentation. These
experiments are essential for understanding a cipher because
theoretical attacks are based upon assumptions which may hide
unknown structure that the cipher holds. Finding such structure
can often be used to improve on the attacks, or even come up with
entirely new and more effective attacks.
When NIST suggested that simplicity of a cipher was important, it
was so that the cipher could be readily analyzed and people can get
a good feeling for the security the cipher offers. Many of the
comments I am reading on this newsgroup just seem to ignore the value
of this.
Scott
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Matrix reduction
Date: 21 May 2000 05:30:56 GMT
In article <[EMAIL PROTECTED]>,
Chris Card <[EMAIL PROTECTED]> wrote:
>I understand that the matrix reduction step of modern
>factorisation algorithms is usually done using the Block Lanczos
>algorithm (I don't understand the algorithm yet though ...).
>Has anyone looked at the possibility of using hillclimbing
>methods to find a linear dependency in the matrix? I haven't
>given it much thought, but on the face of it there is a large
>solution space with many possible solutions and an obvious metric
>(number of non-zero entries). Or is this complete rubbish? :-)
>
>Chris
>
>* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
>The fastest and easiest way to search and participate in Usenet - Free!
>
I'm not an expert on all the tricks that can be used for matrix
reduction, but I have quite a bit of experience implementing the
block Lanczos and Wiedemann algorithms and I can tell you the
benefits:
For a matrix that is (approximately) n by n with an average of
d nonzero entries per row, the running time is O(n^2 * d) . Factoring
matrices are pretty sparse - usually d ranges from approx 10 to
approx 65
(see http://www.maths.usyd.edu.au:8000/u/contini/factoring/FactorAnnouncements.html).
But you get one other nice benefit: there is a constant that the
big O notation hides, which is 1/w where w is the word size
of the computer. Thus, for a computer with 64-bit words, you
can expect to solve the matrix in about n^2 * d / 64 operations.
The main disadvantage of block Lanczos is that there isn't a great
way to parallelize it, or at least I'm not aware of one yet. I
know many people are thinking about this subject, however!
You also have to be careful of your memory usage if you want to
try a different technique. Factoring matrices are HUGE, and
even a space efficient algorithm like block Lanczos or block Wiedemann
can use up gigabytes of central memory.
Scott
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: Compare 3DES's.
Date: 21 May 2000 09:38:47 +0200
In article <8g6th8$lo6$[EMAIL PROTECTED]>,
[William Rowden <[EMAIL PROTECTED]> wrote:
[referring to meet-in-the-middle attacks against 3DES]]
>Where might I read documentation of the details of this attack?
Take a look at
Stefan Lucks,
"Attacking Triple Encryption,"
Fast Software Encryption '98, Volume 1372 of Lecture Notes in
Computer Science (S. Vaudenay, ed.), Springer-Verlag, 1998.
http://th.informatik.uni-mannheim.de/m/lucks/papers.html
Lucks' web page summarizes some of the key results as
about $2^{108}$ steps of computation are sufficient to break
three-key triple DES. If one concentrates on the number of single DES
operations and assumes the other operations to be much faster, $2^{90}$
of these are enough.
That said, 3DES is still very strong: 2^90 is still a *huge* number,
we're looking at attacks which are an absolute minimum of 1e10 or so
times more expensive than exhaustive-searching single-DES, not to
mention astronomical amounts of high-speed memory. In practice, 3DES
is likely to stay secure against exhaustive search for many decades.
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
"If security is set to none, everything just works."
quoted from http://msdn.microsoft.com/library/techart/msdn_signmark.htm
------------------------------
From: Maxim L <[EMAIL PROTECTED]>
Subject: Re: Re: Who has got RSA simple program (sources on C/C++)?
Date: Sun, 21 May 2000 11:42:34 +0300
Reply-To: Maxim L <[EMAIL PROTECTED]>
Hello tomstd,
Thank you VERY MUCH,
This sources files very useful for me. Your test-program works
properly.
Best regards,
Maxim mailto:[EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?
Date: Sun, 21 May 2000 12:01:05 +0200
Guy Macon schrieb:
> Paul Schlyter ([EMAIL PROTECTED]) wrote:
> >> Still, OTP has two weaknesses though:
> >>
> >> 1. An eavesdropper can figure out the length of the message. This
> >> can be countered by adding random garbage to your actual message.
> >>
> >> 2. An eavesdropper can figure out that a message has been sent.
> >> This can be countered in two ways: either by steganography (which
> >> hides the message somehow), or by sending many extra messages
> >> containing nothing but garbage.
> >>
> >3. An attacker can modify the message. If he knows the position of
> >some item within the plaintext, he can change it to any other string
> >with the same length.
>
> It seems to me that adding a random length of random garbage at the
> start and end of your message would counter 1 and 3.
A slight disadvantage could be that the receiver can't surely know
whether part of the random partions may be errors due to transmission
or manipulated, I guess. But generally it should work.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: what is the status finite automata base cryptosystems?
Date: Sun, 21 May 2000 12:01:37 +0200
Tim Tyler wrote:
> There's a significant sense in which all modern cryptosystems are "finite
> automata" - especially those designed for hardware implementation.
Could this be because what are treated as finite automata in the texts
and papers are only rather special cases of finite automata after all?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Interpretation of Hitachi patent claims
Date: Sun, 21 May 2000 12:01:12 +0200
[EMAIL PROTECTED] wrote:
> Has anyone compared the Hitachi patents to the two RC5 patents?
Those patent experts at RSA must have done that, but they seem to
prefer to keep silent for reasons that can only be plausibly
conjectured.
M. K. Shen
------------------------------
** 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
******************************
