DES better than AES?

11 views
Skip to first unread message

Lenz

unread,
Sep 19, 1998, 3:00:00 AM9/19/98
to
DES has been the biggest target of analysis for the best experts for over 20
years. Still, as Douglas A. Gwyn pointed out recently, there is yet no attack
much better than brute-force. The problem of the short key is easily avoided by
using some DES variant.

That makes DES the best algorithm available, since it is has survived the
greatest amount of analysis. By the same reason DES will be better than the
successful AES candidate for the time it takes to accumulate the same amount of
analysis.

Karl-Friedrich Lenz :-)
www.toptext.com/cryoto/

W T Shaw

unread,
Sep 19, 1998, 3:00:00 AM9/19/98
to

Have not you missed the discussions of the last few years regarding
various attempts at using DES, as is, as a module? In short, just using it
buried inside an algorithm does not guarantee anything. Modified? maybe.
3DES? a stop gap measure already.

It does not matter how much information is collected regarding an
algorithm, it is the quality of it. One part of AES, a valuable part, is
to try to standardize testing for algorithm consideration, which might
yield quite different information than we have on DES. Another focus in
AES is to do things that are difficult for old DES to do. Yet, even DES is
a player in a variant form, for better or for worse.
--
----
Beauty is in the mind of the beholder, even ciphertext.
----
Decrypt with ROT13 to get correct email address.

jsa...@freenet.edmonton.ab.ca

unread,
Sep 20, 1998, 3:00:00 AM9/20/98
to
Lenz wrote:
: DES has been the biggest target of analysis for the best experts for over 20
: years. Still, as Douglas A. Gwyn pointed out recently, there is yet no attack
: much better than brute-force. The problem of the short key is easily avoided by
: using some DES variant.

: That makes DES the best algorithm available, since it is has survived the
: greatest amount of analysis. By the same reason DES will be better than the
: successful AES candidate for the time it takes to accumulate the same amount of
: analysis.

I thought linear cryptanalysis did allow an attack _slightly_ better than
brute-force against DES, although two sets of S-boxes are given in
Schneier that fix that (one a rearrangement of the original ones, another
a rearrangement of a proposed new set of S-boxes produced by a Korean
researcher).

Since DES with independent subkeys has a strength of 2^65, it is unclear
that a "DES variant" can be made which has a larger key, and also the full
measure of increased security that the size of the new key implies.

With the knowledge gained from the study of DES, it is possible to design
new block ciphers that are closely patterned after DES. One of the AES
candidates, DEAL, is built using DES as a primitive. Also, Blowfish
resists all the attacks that might be mounted against DES.

Except for Triple-DES, trying to make DES stronger by varying it slightly
has much the same risks as designing a new cipher.

John Savard

Douglas A. Gwyn

unread,
Sep 20, 1998, 3:00:00 AM9/20/98
to
Lenz wrote:
> That makes DES the best algorithm available, since it is has survived the
> greatest amount of analysis. By the same reason DES will be better than the
> successful AES candidate for the time it takes to accumulate the same amount of
> analysis.

Well, no, it depends on the application.
It is now evidently feasible to brute-force crack DES,
although probably not with a normal household budget.
If you don't need much security and have a high traffic volume,
DES may be adequate, but if those conditions aren't met,
you probably don't want DES (although 3DES seems okay).

As to the AES candidates, I assume the winner will have
been thoroughly investigated by skilled cryptanalysts
before it is declared the winner. At least I hope so!

Lenz

unread,
Sep 20, 1998, 3:00:00 AM9/20/98
to
In article , jsa...@freenet.edmonton.ab.ca says...

>
>Except for Triple-DES, trying to make DES stronger by varying it slightly
>has much the same risks as designing a new cipher.

Triple-DES in its several flavors is one simple answer to the brute-force
weakness. Using DES as a building block as in your recent proposal might be
another.

The point I am trying to make is that it will take until 2018 to accumulate as
much analysis against any AES candidate as DES already has today. The other
point is that since all modern ciphers are unbreakable, the only difference is
the amount of effort people have invested attacking. I doubt any AES candidate
can beat DES on that point.

Karl-Friedrich Lenz :-)
www.toptext.com/crypto/

karl-friedrich_lenz

unread,
Sep 20, 1998, 3:00:00 AM9/20/98
to
In article , "Douglas says...

>
>
>Well, no, it depends on the application.
>It is now evidently feasible to brute-force crack DES,
>although probably not with a normal household budget.

I mentioned in my first post that the brute-force weakness is easily avoided.
Schneiers book describes the common answers.

>As to the AES candidates, I assume the winner will have
>been thoroughly investigated by skilled cryptanalysts
>before it is declared the winner. At least I hope so!

It will however take quite some time to match the effort of over 20 years of
attacking DES.

Karl-Friedrich Lenz :-)
www.toptext.com/crypto/

Andi Kleen

unread,
Sep 20, 1998, 3:00:00 AM9/20/98
to
Karl-Friedrich Lenz writes:
>
> It will however take quite some time to match the effort of over 20 years of
> attacking DES.

A lot of these 20 years were spend in developing new techniques for these
attacks (differential cryptoanalysis etc.). You don't need 20 another years
to try published and well known attack methods on a AES algorithm.

"If it already has been done, repeating it is much easier."

-Andi


Solar Designer

unread,
Sep 20, 1998, 3:00:00 AM9/20/98
to
Lenz wrote:
> In article , jsa...@freenet.edmonton.ab.ca says...
>>
>>Except for Triple-DES, trying to make DES stronger by varying it slightly
>>has much the same risks as designing a new cipher.

> Triple-DES in its several flavors is one simple answer to the brute-force
> weakness. Using DES as a building block as in your recent proposal might be
> another.

BTW, what about using a bitslice implementation of 3DES for encrypting
large files, with a kind of CBC mode. For example, for an up to 64 bit
CPU, we can process the file in 512 byte chunks, effectively having 64
separate CBCs. If we prefix that with a 512 byte chunk of extra random
data (to be used as the IVs), this seems to be secure enough for me.

Such an implementation can be made to work very fast. The performance
can be much better than what's mentioned in the Eli Biham's paper, with
the new Matthew Kwan's optimized S-boxes and extra care about fitting
everything in the L1 cache.

I wonder how it would compare to the AES candidates performance-wise.
My guess is that it should be somewhat faster than many of them on
64-bit RISCs already, and that difference will grow for future CPUs.

--
/sd

Douglas A. Gwyn

unread,
Sep 22, 1998, 3:00:00 AM9/22/98
to
Lenz wrote:
> ... since all modern ciphers are unbreakable, ...

Where did you get that idea? It's not so.

Lenz

unread,
Sep 22, 1998, 3:00:00 AM9/22/98
to

Douglas A. Gwyn wrote in message <36072713...@null.net>...

>Lenz wrote:
>> ... since all modern ciphers are unbreakable, ...
>
>Where did you get that idea? It's not so.

You are right, I should have said all modern ciphers except Tristratas
miracle system and a few others you might want to name. :-)

I still think however that most modern ciphers and certainly most of the AES
candidates are unbreakable by anyone, so the difference in their security
level can only be described as a difference in the time people have invested
in attacking and failing. This value seems to be the largest for DES.

Karl-Friedrich Lenz :-)
www.toptext.com/crypto/


W T Shaw

unread,
Sep 22, 1998, 3:00:00 AM9/22/98
to
In article <6u7h3r$j...@enews2.newsguy.com>, "Lenz" <le...@als.aoyama.ac.jp>
wrote:

The tests against DES are not forgotten and all that experience can be
quickly aimed at a new foe. Time invested in DES looking for attacks is
not all wasted and need not be all replicated from scratch. The only
holdouts are the unknown weaknesses of particular algorithms via
unpredicted attacks.

Amount of experience might be greatly enlarged by a loosely concerted
effort to acquire it. Ultimately, Time alone will tell. But, it does not
scale too well as a restrictor of insight.
--
----
Clinton, more a gentleman than his attackers, the perpetrators of an organized hate crime. If Dole had been elected, the Republicans would claimed that it was the Viagra that caused the problem.

John Savard

unread,
Sep 22, 1998, 3:00:00 AM9/22/98
to
"Lenz" <le...@als.aoyama.ac.jp> wrote, in part:

>Douglas A. Gwyn wrote in message <36072713...@null.net>...
>>Lenz wrote:
>>> ... since all modern ciphers are unbreakable, ...

>>Where did you get that idea? It's not so.

>You are right, I should have said all modern ciphers except Tristratas
>miracle system and a few others you might want to name. :-)

>I still think however that most modern ciphers and certainly most of the AES
>candidates are unbreakable by anyone, so the difference in their security
>level can only be described as a difference in the time people have invested
>in attacking and failing. This value seems to be the largest for DES.

If DES is considered a modern cipher, then since it is not
unbreakable, there is one counterexample.

It is believed that Blowfish, IDEA, and RC5 with an adequate key size,
as well as most of the AES candidates, are unbreakable in practice,
although, of course, not being absolutely unbreakable in theory the
way the one-time-pad is.

I assume that you were affirming this belief when you said "all modern
ciphers are unbreakable". If this belief is mistaken, that would be of
interest to know: if it is merely that your statement could be taken
in a broader sense, in which it would become incorrect, that is less
of a concern.

John Savard
http://members.xoom.com/quadibloc/index.html

karl-friedrich_lenz

unread,
Sep 22, 1998, 3:00:00 AM9/22/98
to
In article , jsa...@tenMAPSONeerf.edmonton.ab.ca says...

>If DES is considered a modern cipher, then since it is not
>unbreakable, there is one counterexample.

I was counting DES all the time as one in the rather large set of unbreakable
ciphers (of course with the necessary variant to prevent 56bit brute-force, as
3DES and many others).

The whole point I am trying to make is that in the set of unbreakable ciphers
DES is the _most definitily confirmed_ unbreakable cipher, since it has
attracted the most analysis without anybody coming up with an attack much better
than brute-force. It will be a long time before the first AES candidate has
accumulated as much analysis as DES has already today.

Karl-Friedrich Lenz :-)
www.toptext.com/crypto/

George Barwood

unread,
Sep 23, 1998, 3:00:00 AM9/23/98
to
On 22 Sep 1998 19:30:18 -0700, Karl-Friedrich Lenz wrote:

>The whole point I am trying to make is that in the set of unbreakable ciphers
>DES is the _most definitily confirmed_ unbreakable cipher, since it has
>attracted the most analysis without anybody coming up with an attack much better
>than brute-force. It will be a long time before the first AES candidate has
>accumulated as much analysis as DES has already today.

Not necessarily.

For one thing, I'm not convinced that DES has actually been analysed
that much. I think Biham did a good job, but I don't remember much
other work which applied only to DES (often DES is referenced as an
example). Maybe I have not been around for long enough.

Secondly, there is a larger cryptanalytic community now than when DES
emerged (and much more knowledge). Once the AES is chosen, any
academic would acquire quite a bit of kudos by being the first to
publish an attack (even on a weakened variant) - so I guess it will be
subject to a fair bit of scrutiny quite quickly.

I don't think that the length of time a cipher has existed is strongly
related to how much serious cryptanalytic work has been done on it. It
is even possible that say 2FISH has *already* been better analysed
than DES :)

George

John Savard

unread,
Sep 23, 1998, 3:00:00 AM9/23/98
to
Karl-Friedrich Lenz wrote, in part:

>The whole point I am trying to make is that in the set of unbreakable ciphers
>DES is the _most definitily confirmed_ unbreakable cipher, since it has
>attracted the most analysis without anybody coming up with an attack much better
>than brute-force.

That is a valid point. But since a brute-force attack on DES is now
feasible, one has to vary DES somewhat. Triple-DES is perhaps the
variation that is the most likely to have almost all the safety of the
original DES, but because it is composed of discrete parts, each of
which has a small key, the security is limited to 112 bits. Also,
there is DESX, but it depends on the DES stage in the middle making
the external XORs meaningful (there is some work that appears to prove
this).

Others have noted that what has been learned from DES has been applied
to other ciphers; although you could still counter that a completely
new cipher might be vulnerable to a new attack not applicable to DES.
(For example, it could be a weakness that Blowfish lacks anything
corresponding to the _expansion permutation_ of DES, although in all
other respects it seems like it is immensely stronger.)

Frankly, I'm not terribly worried that something like my Quadibloc II
design would have a bizarre hidden weakness; the problem with
Quadibloc II is that it's way too slow. But if you're looking for
something secure that is DES-based, I might recommend my "large-key"
brainstorm, described on the end of the page at

http://www.freenet.edmonton.ab.ca/~jsavard/co0412.html

where independent-subkey DES is used with constantly changing subkeys.

John Savard
http://members.xoom.com/quadibloc/index.html

Douglas A. Gwyn

unread,
Sep 24, 1998, 3:00:00 AM9/24/98
to
Karl-Friedrich, Lenz wrote:
> The whole point I am trying to make is that in the set of unbreakable ciphers
> DES is the _most definitily confirmed_ unbreakable cipher, since it has
> attracted the most analysis without anybody coming up with an attack much better
> than brute-force.

Please, let's try to use terms in accordance with established practice.
An "unbreakable" cryptosystem means one whose messages are expected to
not likely be read by *anyone* with an affordable investment of
resources unless the decryption key is known, in practical applications.
Some systems are breakable via an affordable brute-force attack in
capable hands, as was DES (eventually).
Some theoretically unbreakable systems are breakable in practice.
Some systems not known publicly to be breakable are breakable by people
who know how.
That's why it is essential to have knowledgable insiders (the extreme
case of "anyone") evaluate the proposed AES candidates.

dian...@tecapro.com

unread,
Sep 24, 1998, 3:00:00 AM9/24/98
to
In article <jgfunj-2209...@207.22.198.204>,
jgf...@EnqvbSerrGrknf.pbz (W T Shaw) wrote:

> [...]


> The tests against DES are not forgotten and all that experience can be
> quickly aimed at a new foe. Time invested in DES looking for attacks is
> not all wasted and need not be all replicated from scratch. The only
> holdouts are the unknown weaknesses of particular algorithms via
> unpredicted attacks.

I agree, but beware: As Schneier explained in another post,
applying a known attack is not like applying a recipe. The risk is
not only with unknown attacks but also with innovative ways to
apply a known attack, such as differential cryptanalysis, against
a particular cipher. I suppose you would say that this last case is
also an "unpredicted" attack.

On the whole I believe the original poster to be correct - it is
not quite clear why the AES will be more secure than a good
variant of DES. DESX is good choice, even when speed is important
(bit-spliced DESX on a 64 bit CPU may indeed compare favorably
with the speed of the fastest AES candidates). In the rather large
class of applications where speed is not important 3DESX (3DES
with pre and post-whitening) is surely an excellent choice. In both
cases combining a DES variant with the AES itself could be a
better choice still.

I wonder if there is any accepted way to produce keys for two
ciphers in series. (I know that integrating two ciphers is series
does not *necessarily* increase security, on the other hand the
probability that there will be subtle interactions between 3DESX
and the AES winner that decrease instead of increasing security is
extremely small - let me quantify this: if we asked the best
cryptographers in the world whether, if their life depended on it,
they would rather trust AES alone or AES in series with 3DESX, all
of them would choose the second alternative - I think).

For the sake of argument let us suppose that we do want to
integrate ciphers A and B in series, and need to compute their
keys KeyA and KeyB as a function of a user passphrase P. I can
imagine many ways to do this, for example:

KeyA = hash( P )
KeyB = KeyA

or

KeyA = hash( P )
KeyB = hash( P xor KeyA )

or

KeyA = hash( first half of P )
KeyB = hash( second half of P )

or

(* first hash P up or down to a fixed length, e.g. 256 bits *)
P = hash( P )
KeyA = hash( first three quarters of P )
KeyB = hash( last three quarters of P )

Which method is better? Any other method you care to suggest?

--
http://www.tecapro.com
email: dian...@tecapro.com

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum

Mark Ingram

unread,
Sep 24, 1998, 3:00:00 AM9/24/98
to

Douglas A. Gwyn wrote:

> Please, let's try to use terms in accordance with established practice.
> An "unbreakable" cryptosystem means one whose messages are expected to
> not likely be read by *anyone* with an affordable investment of
> resources unless the decryption key is known, in practical applications.

With the appropriate definition of "affordable", this means that no cryptosystems are
unbreakable.

> Some systems are breakable via an affordable brute-force attack in
> capable hands, as was DES (eventually).
> Some theoretically unbreakable systems are breakable in practice.

All cryptosystems can be broken by poor practice.

> Some systems not known publicly to be breakable are breakable by people
> who know how.

The know-how doesn't even have to be cryptanalytic.

It therefore seems to me that you spend a lot of time saying the simple fact that
"there are no unbreakable cryptosystems". As I have shown, by your terms not only are
there none, there can never be any. I think that there is room in established
practice, if not the science of cryptology, for "unbreakable" to have a meaning.

As to whether that meaning is or should be either practical or theoretical, that's
another bunny. Personally, I think "practically unbreakable" has a nice ring to it
:-)

TTFN,
--mi.


Richard Outerbridge

unread,
Sep 24, 1998, 3:00:00 AM9/24/98
to
1998-09-24 10:47:55 EDT
Of course, if what he is looking for is something like an AES candidate
algorithm based on the DES he should take a look at AES candidate DEAL.

In article <3609394f...@news.prosurfr.com>,
jsa...@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote:

> Karl-Friedrich Lenz wrote, in part:
>

> >The whole point I am trying to make is that in the set of unbreakable ciphers
> >DES is the _most definitily confirmed_ unbreakable cipher, since it has
> >attracted the most analysis without anybody coming up with an attack
> >much better than brute-force.
>

> That is a valid point. But since a brute-force attack on DES is now
> feasible, one has to vary DES somewhat.

outer

--
"Just an eccentric soul with a curiosity for the bizarre."
PGPpubkey 1024/0EEAAF21 1994/07/23 <ou...@interlog.com>
Fingerprint = 6A89 D49F D3DA 12E4 040A 273B F383 0127

Douglas A. Gwyn

unread,
Sep 24, 1998, 3:00:00 AM9/24/98
to
Mark Ingram wrote:
> With the appropriate definition of "affordable", this means that no cryptosystems are
> unbreakable.

That's sophomoric; "affordable" has a real meaning.
I gave a carefully worded definition of "unbreakable" with all
the caveats in order to forestall "But you forgot ..." arguments.
Don't focus on the caveats and forget the essence of the definition.

> > Some theoretically unbreakable systems are breakable in practice.
> All cryptosystems can be broken by poor practice.

I'm not talking about extreme examples, but just routine usage.

jack lloyd

unread,
Sep 24, 1998, 3:00:00 AM9/24/98
to

Response to Andi Kleen:

I disagree with your assesment. While it is true that new techniques have
been developed that are powerful attacks, any AES will be have been
designed to be highly resistant to any such attack. IDEA, for example, has
design elements within it that make it virtually immune to differential
cryptanalysis. The reason for it is becuase Lai and Massey _knew about it
when the wrote the algorithm. So the only effective attacks against an AES
cipher will be brute force and attacks which are not yet publicly known
(eg, the NSA).

***************************************
* Jack Lloyd * llo...@ece.orst.edu *
***************************************

Paul Crowley

unread,
Sep 26, 1998, 3:00:00 AM9/26/98
to
jack lloyd <llo...@ece.orst.edu> writes:
> IDEA, for example, has design elements within it that make it
> virtually immune to differential cryptanalysis. The reason for it is
> becuase Lai and Massey _knew about it when the wrote the algorithm.

However, IIRC, IDEA is only very slightly different from its
predecessor PES, designed before DC was announced in the open
literature, and while the differences are all about improving its
strength against the attack PES turned out to be pretty good already.
--
__
\/ o\ pa...@hedonism.demon.co.uk Edinburgh fetish club Permission \ /
/\__/ Paul Crowley Oct 11 http://www.hedonism.demon.co.uk/permission /~\

Bruce Schneier

unread,
Sep 26, 1998, 3:00:00 AM9/26/98
to
On Thu, 24 Sep 1998 11:55:46 GMT, dian...@tecapro.com wrote:

> On the whole I believe the original poster to be correct - it is
> not quite clear why the AES will be more secure than a good
> variant of DES.

Certainly triple-DES is a better chose than AES, in some applications.
Triple-DES will probably be the aglorithm of choice for many banking
applications even after AES is approves as a standard.

This is why AES was not designed as a simple replacement for DES.
It has a 128-bit block, for applications where a 64-bit block won't
do. It will be much faster than triple-DES (18 clock cycles per byte
for Twofish versus over 100 clock cycles per byte, for example),
require less hardware, be better suited for 32-bit CPUs, etc etc etc.

The conservative users can still use triple-DES, and I expect that
they will.

> I wonder if there is any accepted way to produce keys for two
> ciphers in series. (I know that integrating two ciphers is series
> does not *necessarily* increase security, on the other hand the
> probability that there will be subtle interactions between 3DESX
> and the AES winner that decrease instead of increasing security is
> extremely small - let me quantify this: if we asked the best
> cryptographers in the world whether, if their life depended on it,
> they would rather trust AES alone or AES in series with 3DESX, all
> of them would choose the second alternative - I think).

There are been some theoretical work in this, but there are no good
results.

Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com

Bruce Schneier

unread,
Sep 26, 1998, 3:00:00 AM9/26/98
to
On Thu, 24 Sep 1998 10:55:07 -0700, jack lloyd <llo...@ece.orst.edu>
wrote:

>Response to Andi Kleen:
>I disagree with your assesment. While it is true that new techniques have
>been developed that are powerful attacks, any AES will be have been
>designed to be highly resistant to any such attack. IDEA, for example, has

>design elements within it that make it virtually immune to differential
>cryptanalysis. The reason for it is becuase Lai and Massey _knew about it
>when the wrote the algorithm. So the only effective attacks against an AES
>cipher will be brute force and attacks which are not yet publicly known
>(eg, the NSA).

Or variants of differential cryptanalysis. Biham and Shamir's
"impossible cryptanalysis," which uses differentials but in a
different way, is more effective against IDEA than any other attack.

Solar Designer

unread,
Sep 26, 1998, 3:00:00 AM9/26/98
to
Bruce Schneier <schn...@counterpane.com> wrote:

> This is why AES was not designed as a simple replacement for DES.
> It has a 128-bit block, for applications where a 64-bit block won't
> do. It will be much faster than triple-DES (18 clock cycles per byte
> for Twofish versus over 100 clock cycles per byte, for example),

100+ cycles per byte for 3DES? This is kind of arguable. In my opinion,
it should be possible to achieve a significantly better performance on
many modern general-purpose CPUs, in applications with enough natural
parallelism (such as encrypting large files, or network traffic with
each packet being large enough). I'm talking bitslice DES implementations.

For example, doing the math for an Alpha 21164-600 CPU gets us:

600000000/(215000*25*1.1/3)/(64/8) = 38.05

The numbers used are: 600 MHz, 215K crypt(3) passwords per second with
my cracker, 25 iterations in crypt(3), 10% overhead because of the salt
pointers (which we won't have when not dealing with UNIX passwords),
the 3 encryptions in 3DES, 64 bit block size, and 8 bits per byte. If
I haven't made a mistake, this gives us 38 cycles per byte. And that's
with pure C code, no assembly.

These numbers are going to be pretty much similar for Intel Merced when
it comes out.

> require less hardware, be better suited for 32-bit CPUs, etc etc etc.

Why make new ciphers for current 32-bit CPUs now, rather than optimize
them for future processors?

Here's what we see happening in the CPU world: word size increases,
issue rate increases, instruction latencies increase. Unfortunately,
we're not seeing new ciphers trying to fit this situation better as
the time goes, are we?

The availability of parallelism inside of a cipher is considered to
be a bad sign about its security (and often it really is). However,
it doesn't mean we should always avoid parallelism; on the opposite,
in my opinion, it would be good to try designing ciphers in such a
way that we could put more parallelism in without affecting the security.

--
/sd

Bruce Schneier

unread,
Sep 26, 1998, 3:00:00 AM9/26/98
to
On 26 Sep 1998 21:55:44 GMT, Solar Designer
<so...@cannabis.dataforce.net> wrote:

>Bruce Schneier <schn...@counterpane.com> wrote:
>
>> This is why AES was not designed as a simple replacement for DES.
>> It has a 128-bit block, for applications where a 64-bit block won't
>> do. It will be much faster than triple-DES (18 clock cycles per byte
>> for Twofish versus over 100 clock cycles per byte, for example),
>
>100+ cycles per byte for 3DES? This is kind of arguable. In my opinion,
>it should be possible to achieve a significantly better performance on
>many modern general-purpose CPUs, in applications with enough natural
>parallelism (such as encrypting large files, or network traffic with
>each packet being large enough). I'm talking bitslice DES implementations.

Sorry. I was talking Pentium, and I was talking normal (not bitslice)
implementation. If you know better, please let me know. That's the
fastest DES I've seen.

Solar Designer

unread,
Sep 27, 1998, 3:00:00 AM9/27/98
to
Bruce Schneier <schn...@counterpane.com> wrote:

>>100+ cycles per byte for 3DES? This is kind of arguable. In my opinion,
>>it should be possible to achieve a significantly better performance on
>>many modern general-purpose CPUs, in applications with enough natural
>>parallelism (such as encrypting large files, or network traffic with
>>each packet being large enough). I'm talking bitslice DES implementations.

> Sorry. I was talking Pentium, and I was talking normal (not bitslice)

Yes, and I must admit that there're cases where bitslice implementations
are impossible. However, in most cases where the performance is critical
this seems possible to me, with a non-standard mode of operation though.

> implementation. If you know better, please let me know. That's the
> fastest DES I've seen.

For a Pentium, the fastest non-bitslice DES is really Eric Young's libdes,
and it has the performance similar to what you've said.

However, in cases where bitslice is possible to implement efficiently
(this depends on the application), it can be made to work faster than
that. For a Pentium, I wasn't able to get things any faster though,
because of the lack of registers. However, already for a Pentium MMX,
it might be possible to get bitslice DES to work faster than libdes
(once again, it will only be usable in some applications). There're
two ways to do so: (1) use the 64-bit MMX registers for 64 encryptions
at a time; (2) use both the MMX and non-MMX registers for 32 at a time
(but we'll have less memory accesses then). I haven't tried that yet
though, as I was mainly interested in crypt(3) cracking performance
(I'm using the MMX operations a different way because of that).

Anyway, the above "optimizing DES on Pentium" stuff wasn't my point.
My point was that when designing new ciphers, we should probably care
about future processors more than about current ones (especially not
"broken" architectures such as x86).

Finally, my UNIX password cracker with bitslice DES support you can
find at: http://www.false.com/security/john/

For this application, bitslice DES turned out to be faster than heavily
optimized non-bitslice assembly code on all RISCs (2 to 3 times faster
in most cases) and also on AMD K6 (50% faster).

(BTW, the cracker also has support for the Blowfish-based passwords which
are used on OpenBSD, with some optimizations in the code...)

Now, if anyone is interested, I might try to spend a day and adjust my
code from John along with the Matthew Kwan's bitslice DES S-box code,
to create a fast file encryption program that would use a kind of 3DES.
Then we could actually benchmark it and talk about the speed in Mbps.

It is going to be fairly close to optimal on RISCs with 32 registers,
but will not tell us much about the potential performance we could get
out of an x86 with MMX. It would take much more than a day to create
an efficient bitslice S-box code generator for MMX.

--
/sd

Douglas A. Gwyn

unread,
Sep 27, 1998, 3:00:00 AM9/27/98
to
Bruce Schneier wrote:
> ... Biham and Shamir's "impossible cryptanalysis,"
> which uses differentials but in a different way, ...

To the limited extent that I understand it,
the so-called "impossible cryptanalysis" uses a technique
the essential aspect of which was used against the Enigma
in WWII. The idea was to quickly prune bad guesses by
setting things up so that they would almost certainly
produce contradictions.

Not knocking the recent work, just finding it interesting
how good ideas come around again and again.

W T Shaw

unread,
Sep 27, 1998, 3:00:00 AM9/27/98
to
In article <360DE4FF...@null.net>, "Douglas A. Gwyn"
<DAG...@null.net> wrote:

The protection is to make the keys on the soft side, hard to pin down, it
it can be done at all, without prohibitive amounts of data.
--
----
Are you tired, rundown, can't find a corner in the office to hide in?

Then, try Jimmy Carter's Little Pills, which are apt to cause you to
want to get out your frustrations *constructively*, but might tend
to make you fear rabbits.

Reply all
Reply to author
Forward
0 new messages