Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Ladder DES

140 views
Skip to first unread message

Terry Ritter

unread,
Feb 22, 1994, 3:33:53 AM2/22/94
to


Ritter Software Engineering
2609 Choctaw Trail
Austin, Texas 78745
(512) 892-0494, rit...@cactus.org

Ladder-DES: A Proposed Candidate to Replace DES

Terry Ritter
February 22, 1994


Introduction

Data enciphered by DES, the US Data Encryption Standard, has become
vulnerable to modern technical attacks. Currently, such attacks
require substantial capital and high-tech engineering development
to produce a special "DES breaking" machine. However, once such a
machine is built, attacks would become relatively fast and cheap.
Businesses which currently protect very expensive and marketable
secrets with DES should take immediate notice.

To maintain earlier levels of security, DES must be replaced with
a stronger cipher. The one obvious alternative to DES is a simple
construct built from DES called triple-DES. Triple-DES, while
generally being thought of as "strong enough," also carries the
baggage of requiring three times the processing of normal DES.

Because every security system is required to provide more benefit
than its cost, raising costs by a factor of three (when compared
to the alternative of normal DES) is a significant issue. Such
costs could dangerously delay the retirement of ordinary DES.


Requirements

The goal of this sequence of designs is to identify one or more
better candidates to replace DES. Obviously, the first requirement
is that each candidate be substantially "stronger" than normal DES.
One problem here is that we can only _argue_ strength, so it is
important that candidate designs be openly presented and reviewed.
We cannot expect that most proposals will withstand such review.

The second requirement is that each candidate design also be faster
than triple-DES; otherwise, we might just as well use triple-DES
and be done with it. Speed is a measurable design quantity.

My third requirement is to include operation on data blocks larger
than the 8-byte DES block. Although DES is not normally used in a
way which is conducive to "dictionary" attack, such attacks could be
effective on the bare cipher itself. This raises the possibility
that a "certificational" weakness may exist which we currently do
not know how to exploit, but which may be dangerous anyway. This
particular weakness depends upon small blocks.

At this point there is still some question as to whether it is
_possible_ to come up with candidate designs which meet these
three requirements.


Ladder Diagrams

DES itself is frequently shown in figures which are described as
"ladder diagrams" because of their appearance:

|
v
Initial Permutation
v
<-- SPLIT -->
| |
| k1 |
v v |
XOR <-- f -----|
| |
| k2 |
| v v
|----- f --> XOR
| |
. . .

| k16 |
| v v
|----- f --> XOR
| |
| |
--> COLLECT <--
v
Inv. Init. Perm.
|
v

This is the data-transformation part of DES. Not shown is the
key-schedule computation which produces k1 through k16, the 48-bit
"round" keys. Also not shown is the construction of function "f."

It will later be interesting to note that in DES each 32-bit data
rail value is expanded to 48 bits, the XOR occurs with a 48-bit key,
and the result contracted to 32 bits in 6-bit to 4-bit substitutions
known as "S-boxes."


Ladder-DES

Consider this simple construct which looks something like two
rungs or steps on a ladder:

A B
| k1 |
v v |
XOR <- DES1 ----|
| |
| k2 |
| v v
|---- DES2 -> XOR
| |
v v
C D

A, B, C and D represent 8-byte blocks; k1 and k2 represent 56-bit
DES keys. This enciphers two DES data blocks in two DES operations;
this is a data rate similar to normal DES. It can be described as
working on a single large block composed of A and B. Note that the
data paths are twice the size of those used in DES itself.

Also note that the design is asymmetric: While ciphertext block C
is a function of every bit in plaintext blocks A and B, as well as
every bit in key k1, ciphertext block D is _also_ a function of
key k2.


Known-Plaintext Attack on Two-Rung Ladder-DES

With known-plaintext, we essentially have a single-DES complexity:
Since A is known and C is known, the output of DES1 is known. Since
the input to DES1 is also known, to find k1 we just do a normal DES
search.

Alternately, since B is known and D is known, the output of DES2 is
known. Since the input to DES2 is also known, to find k2 we just do
a normal DES search.

Total complexity: twice DES; thus, hardly worth using.


Four-Rung Ladder-DES

Now consider a similar construct, twice as long:

A B
| k1 |
v v |
XOR <- DES1-----|
| |
| k2 |
| v v
|---- DES2 -> XOR
| |
| k3 |
v v |
XOR <- DES3 ----|
| |
| k4 |
| v v
|---- DES4 -> XOR
| |
v v
C D

A and B are 64-bit DES blocks; k1 through k4 are 56-bit DES keys.
A total of four DES operations process two DES blocks at double-DES
rates. We would expect this to be both stronger than normal DES
and faster than triple-DES.

In general, the left-leg of a ladder-DES structure is affected by
one fewer key than the right-leg.


Belief

Can we "believe" in this basic structure? Well, DES itself is
based on it. But we do need to remember that DES also includes
seriously nonlinear data expansions and contractions around each
XOR. Certainly expansion and contraction could be added to ladder-
DES, although this could be expensive. (To avoid specifying
particular S-box contents, we could specify a cryptographic RNG
which would be used to permute a base S-box arrangement; this
should also avoid normal differential attacks.) It is not clear
that the lack of expansion and contraction operations necessarily
negates the overall approach.


Key Reduction

The four-rung ladder-DES construct uses four 56-bit DES keys, but
certainly a cipher would be strong enough if it had "only" a real
two-key (112-bit) keyspace. Thus, we might consider making k3 = k1,
and k4 = k2, or perhaps, k3 = k1 and k4 = k1 XOR k2.

On the other hand, perhaps it would be worthwhile to support
additional keys simply to avoid the necessity of showing that a
reduced key approach could never reduce strength.


Known-Plaintext Attack on Four-Rung Ladder-DES

No longer do we have the advantage of knowing both the input to
and the output from XOR operations, so we can no longer gain access
to the output of particular DES operations. Thus, the obvious
search strategy is not available.


Divide-And-Conquer Attack on Four-Rung Ladder-DES

Normally we try to separate the effects of the different DES
operations, so we can "divide and conquer" each separately.
In this case, DES4 is the obvious first choice, since with the
keys k1..k3 fixed, only k4 affects the output, and then it only
affects block D. However, unless we know the values of k1 and k2,
we don't know the input to the bottom XOR, and so apparently
cannot separate DES4 to work on it.


Meet-In-The-Middle Attack on Four-Rung Ladder-DES

With four keys involved, and no obvious "middle," it is not clear
how this attack could be applied.


2x Four-Rung Ladder-DES

The basic Ladder-DES construct can be expanded to cipher four
blocks at once:

A B C D
| k1 | | k2 |
v v | v v |
XOR <- DES1 ----| XOR <- DES2 ----|
| | | |
| k3 | | k4 |
| v v | v v
|---- DES3 -> XOR |---- DES4 -> XOR
| | | |
v v v v
E F G H

Re-arrange Blocks

H E F G
| k5 | | k6 |
v v | | v |
XOR <- DES5 ----| XOR <- DES6 ----|
| | | |
| k7 | | k8 |
| v v | v v
|---- DES7 -> XOR |---- DES8 -> XOR
| | | |
v v v v
I J K L

This construct enciphers four DES data blocks in eight DES
operations; again, this is a speed comparable to double-DES, and
substantially faster than triple-DES.

Ciphertext block I is now a function of every bit in plaintext
blocks A, B, C, and D, as well as every bit in keys k1, k2, k4,
and k5. Every bit in the 64-bit I is a complex function of
480 bits.

We could certainly afford to reduce the number of keys in these
constructs, and this might be done in any number of ways. For
the 2x construct, for example:

k2 := k1 XOR k3; k4 := k3 XOR k5;
k6 := k5 XOR k7; k8 := k7 XOR k1;

leaving us with a need for four keys: k1, k3, k5 and k7. It is
also possible that the same two keys could be used in every two-
rung ladder-DES section, for a total of two keys.


Conclusion

DES operations can be arranged into a "ladder-DES" constructs which
are especially-clean and familiar and seem to resist known attacks.
These constructs seem potentially stronger than normal DES and are
demonstrably faster than triple-DES. Thus, ladder-DES could be a
reasonable candidate to replace DES.


Anonymous

unread,
Feb 22, 1994, 10:52:08 PM2/22/94
to
Terry Ritter (rit...@cactus.org) wrote:
: To maintain earlier levels of security, DES must be replaced with

: a stronger cipher. The one obvious alternative to DES is a simple
: construct built from DES called triple-DES. Triple-DES, while
: generally being thought of as "strong enough," also carries the
: baggage of requiring three times the processing of normal DES.

Another, already somewhat widely used alternative is
RSA Data Security's "DESX", as implemented in their commercial
products MailSafe and BSAFE since 1986/87. DESX is ordinary
DES with pre- and post-processing to expand keysize and
security. Like Ladder DES, it is faster than triple-DES.

I have some reason to believe that RSA may be willing to
allow use of DESX free of licensing fees. Perhaps someone
from RSA would comment?

Mark R

David C. Barber

unread,
Feb 22, 1994, 11:00:37 PM2/22/94
to
An interesting post, but begs a question on why don't we want to
use IDEA to replace DES?


My worst problems *David Barber*
are other people's dba...@crash.cts.com
greatest dreams.

Owen Lewis

unread,
Feb 23, 1994, 5:51:09 AM2/23/94
to
In article <dbarber....@crash.cts.com>

dba...@crash.cts.com "David C. Barber" writes:

>An interesting post, but begs a question on why don't we want to
>use IDEA to replace DES?

Not entirely jokingly, I propose the following reasons:
1. The massive investment already made in DES technology and
equipment makes people reluctant to change.
2. For the US market, the NIH (Not Invented Here) syndrome.

My personal bet is that IDEA will beome a world market leader in the coming
years but that it will not lead in the US market, with or without USG tilting
the table.

Without wishing to introduce matter extraneous to this forum, I do also
believe that the development and spread of cryptologic technologies will be
influenced by the clear intention of the USG to retain control over what
algorithms may be used and by whom. This policy, currently spearheaded by the
SKIPPER/CLIPPER/ESCROW initiative, is not going to go away - at least for a
very long time. Other governments may, at present, be less vocal in their
approach but that does not make their intentions any the less determined.

It remains to be seen to what extent the development and spread of cryptologic
technology in other counties is dominated, if not by the USG directly then
at least by other governments adopting independent policies that are fully
consonant with that of the USG. The history of the last quarter century
indicates that there will be a remarkable degree of consonance between the US
and other first world nations - particularly among those that have strong
treaty ties with the US. I do not simply refer to NATO here.

Its going to be a great game and, at some level, all of us with sufficient
interest to read this group have a part to play. Let's play well.

Though I do not read it (because of the noise level :-)), I think any
follow-ups had better go to talk.politics.crypto. E-mail welcome though.

--

-= Owen Lewis =-
@
Tele/fax +44-(0)794-301731 ELOKA Consultancy & Project Management
o...@eloka.demon.co.uk
pgp 2.x public key on request

Mark C. Henderson

unread,
Feb 23, 1994, 1:23:25 PM2/23/94
to
In article <dbarber....@crash.cts.com>,

David C. Barber <dba...@crash.cts.com> wrote:
>An interesting post, but begs a question on why don't we want to
>use IDEA to replace DES?

For one, there is the issue of the patent on IDEA.

Mark
--
Mark Henderson, SoftQuad Inc., 108-10070 King George Hwy, Surrey, B.C. V3T 2W4
Internet: m...@sqwest.wimsey.bc.ca, ma...@wimsey.bc.ca Voice: +1 604 585 8394
Fax: +1 604 585 1926 RIPEM MD5OfPublicKey: F1F5F0C3984CBEAF3889ADAFA2437433
ViaCryptPGP Key fingerprint = C4 EC 2F 6C 1B ED F6 06 1D E9 08 E4 E5 F9 FA 16

Bryan Olson

unread,
Feb 25, 1994, 4:50:48 PM2/25/94
to

In article <1994Feb25....@cactus.org>, rit...@cactus.org
(Terry Ritter) writes:
|>
|> Speaking for myself, I have trouble *believing* that IDEA (or PES
|> or IPES) is strong. I am of course aware that my intuition of
|> strength has little to do with reality. ...
|>
|> As I reported on sci.crypt, I have performed some experiments on
|> automatically attacking complex combining mechanisms. I found
|> that some apparently complex mechanisms are attackable *provided*
|> their internal operations are linear.

Not a surprise.

|> When I look at IDEA I see a structure which seems complex, but
|> every operation is linear (with the possible exception of
|> multiplication mod 2^16+1).

This is misleading.

Addition mod 2^16 is linear.
Exclusive or is linear.
Multiplication in the multiplicative group mod 2^16+1 is well
approximated by multiplication in the field mod 2^16+1.

Thus all the operations are linear or have good linear approximations.

Linear methods will NOT solve the resulting system because the
operations are linear over different fields.

|> There is no substitution. There is
|> no selection. The innermost four-operation transformation is the
|> same (albeit with different keys) for each round, and it is the
|> rounds which appear to build strength.

Find the best linear approximation you can for that four-operation
transformation. You see my point ?

That doesn't show IDEA is strong, but criticizing it for linearity
is nonsense.

|> Thus, my intuition is to not trust IDEA.

I think your intuition is baseless.


--Bryan Olson

Terry Ritter

unread,
Feb 25, 1994, 12:52:56 PM2/25/94
to

In <2kejt8$13...@msuinfo.cl.msu.edu> m...@scss3.cl.msu.edu
(Anonymous) writes:

>Another, already somewhat widely used alternative is
>RSA Data Security's "DESX", as implemented in their commercial
>products MailSafe and BSAFE since 1986/87. DESX is ordinary
>DES with pre- and post-processing to expand keysize and
>security. Like Ladder DES, it is faster than triple-DES.

I don't find it in the RSA FAQ. Where was this design published
openly for comment? What were the comments?


>I have some reason to believe that RSA may be willing to
>allow use of DESX free of licensing fees. Perhaps someone
>from RSA would comment?

What is the patent number? Without a patent, there is no need to
ask permission.

Terry


David Mitchell

unread,
Feb 25, 1994, 3:44:41 PM2/25/94
to
In article <1994Feb25....@cactus.org> Terry Ritter,

rit...@cactus.org writes:
> >An interesting post, but begs a question on why don't we want to
> >use IDEA to replace DES?
>
> Speaking for myself, I have trouble *believing* that IDEA (or PES
> or IPES) is strong. I am of course aware that my intuition of
> strength has little to do with reality. However, since we cannot
> *test* or *prove* strength, the mere *feeling* of weakness is what
> every formal attack must be before it is born.

The question is one of how to measure the complexity of a given binary
function. I recently asked on comp.theory about methods for manipulating
binary/boolean functions and was given a pointer to the following article
which I highly recommend.

"Graph-Based Algorithms for Boolean Function Manipulation"
Randal E. Bryant
IEEE Trans. on Computers
1986
Vol C-35
Num 8
pp 677-691

The paper talks about representing a given boolean function as a directed
acyclic graph (a tree), refered to as a Binary Deceision Diagram (BDD for
short.) Any crypto function can be represented as a number of these
graphs. For example, DES would require 64 graphs, one for each output
bit (actually, it's possible to combine a number of functions into one
graph, but I'm simplifying for clarity.) Each tree would have a height
of 64 (data bits) + 56 (key bits) + 1 (terminal nodes, one each for 1 and
0) = 121.

The complexity of the function can be related to the number of nodes in
the BDD. In the worst case, the BDD blows up to the size of a full
binary tree of the given height. Often times, the graph is actually much
smaller. However, there is a complication. The size of the tree also
depends on the ordering of the variables, and it can be expensive to find
the optimal ordering. In most applications though, there are good
heuristics for finding pretty good orderings. With addition, for
example, you would want to start with the low order bits, not the high
order bits. Well, with that out of the way, I'll discuss the
relationship to IDEA.

One of the interesting points that Bryant makes in the paper is that
multiplication will always blow up into a very large tree for at least
one output bit, irrespective of the order of the variables. This seems
to me to indicate that the complexity of IDEA may be very high, since it
relies on 32-bit multiplications. Of course, it is possible that some of
the complexity cancels out somewhere else in the algorithm. I haven't
checked it out yet. Either way, it should be difficult to impossible to
compute the BDD's for IDEA because of the explosive growth of
multiplications. This is, IMHO, a good thing, as having access to the
BDD's for a cryptosystem would make cryptanalysis relativly easy. For
example, with the BDD's, any type of known-plaintext attack should be
very fast. Probably as fast as any method other than a complete lookup
table.

Anyway, there's a little food for thought for everyone. I do highly
recommend that you try and get your hands on a copy of Bryant's article.

-David Mitchell

Terry Ritter

unread,
Feb 25, 1994, 12:51:46 PM2/25/94
to

In <dbarber....@crash.cts.com> dba...@crash.cts.com
(David C. Barber) writes:

>An interesting post, but begs a question on why don't we want to
>use IDEA to replace DES?

Speaking for myself, I have trouble *believing* that IDEA (or PES


or IPES) is strong. I am of course aware that my intuition of
strength has little to do with reality. However, since we cannot
*test* or *prove* strength, the mere *feeling* of weakness is what
every formal attack must be before it is born.

As I reported on sci.crypt, I have performed some experiments on


automatically attacking complex combining mechanisms. I found
that some apparently complex mechanisms are attackable *provided*

their internal operations are linear. For example, it is fairly
easy to break PKZIP encryption which has had the output nonlinear
operation removed. I have yet to find a way around that section.
Occasionally I issue a call for any literature anyone has seen
on the solution of large systems of Boolean equations. Surely,
with sufficient information, even a system with nonlinear elements
must be directly solvable.

When I look at IDEA I see a structure which seems complex, but
every operation is linear (with the possible exception of

multiplication mod 2^16+1). There is no substitution. There is


no selection. The innermost four-operation transformation is the
same (albeit with different keys) for each round, and it is the

rounds which appear to build strength. Thus, my intuition is to
not trust IDEA.

I don't know what the current results are (I think IDEA became
PES, and weakness in PES resulted in IPES), but I have read the
comments in:

Lai, X. and J. Massey. 1991. Markov Ciphers and Differential
Cryptanalysis. Advances in Cryptology--Eurocrypt '91. 17-38.

In the conclusions (p. 38) we find:

". . . the true strength of the standard PES algorithm is of
the order of 2^64 encryptions, a considerable reduction from
the work that a cryptanalyst would expected (sic) in an
exhaustive key search for the 128-bit key."

I note that this is comparable to realizing that double-DES, with
a putative 112-bit key, actually has a strength similar to a
57-bit key. Since double-DES has twice the expense of normal 56-bit
DES, this was sufficient to make double-DES essentially useless.

The improved IPES apparently does not fall to the same
(differential) attack, so maybe it is better. But maybe we can fix
up double-DES without changing the internals of the proven cipher.

If we believe that strong ciphers are possible, then we already
recognize the ability to build a strong large cipher out of less-
strong components. If we can limit the intellectual distance in
a cipher (from the base exclusive-OR and the final result), we
might understand ciphers better, even at their lowest levels.

If we can take a structure of known strength that we do believe in,
and use it as a building-block in a relatively-simple construct
which we can build a belief in, we can hope to avoid the need for
the terrible depth of analysis required to certify an entire cipher.
We have no public institutions set up to fund or organize such a
certification.

If it eventually comes down to the need for the banking industry
to set up and fund a cipher certification facility, we may get to
see just how badly the banks want to avoid government-designed
secret cipher systems.

Terry

Mark Riordan

unread,
Feb 25, 1994, 8:08:15 PM2/25/94
to
Terry Ritter (rit...@cactus.org) wrote:

: >Another, already somewhat widely used alternative is


: >RSA Data Security's "DESX", as implemented in their commercial
: >products MailSafe and BSAFE since 1986/87.

: I don't find it in the RSA FAQ. Where was this design published


: openly for comment? What were the comments?

Probably nowhere.

However, the president of RSA DSI, Jim Bidzos, has given me the
source code to their implementation of DESX and the following statement:

"We claim no intellectual property ownership of DESX except for a
copyright on our own implementation and a trademark on DESX. If
someone wanted to use our spec for DESX, they could call it DESX if it
were an accurate implementation. In any case, no money is involved."

[However, there is no actual specification document.]

: What is the patent number? Without a patent, there is no need to
: ask permission.

So, no patent--just the copyright.
I will prepare a description of the algorithm and have
someone who has not seen RSA DSI's code reimplement it
in C. (RSA's implementation is about 150 lines of C,
so it shouldn't be too hard.) Then we'll have a public
domain implementation of a stronger-than-DES cipher
designed by recognized experts.

Mark R

Thor Oddleif Kristoffersen

unread,
Feb 27, 1994, 9:03:28 AM2/27/94
to

In article <1994Feb25....@cactus.org>, rit...@cactus.org (Terry Ritter) writes:
[...]

> I don't know what the current results are (I think IDEA became
> PES, and weakness in PES resulted in IPES), but I have read the

PES came first. Then came IPES, which was later renamed IDEA, and
has been shown to be invulnerable to differential cryptanalysis.

> comments in:
>
> Lai, X. and J. Massey. 1991. Markov Ciphers and Differential
> Cryptanalysis. Advances in Cryptology--Eurocrypt '91. 17-38.
>
> In the conclusions (p. 38) we find:
>
> ". . . the true strength of the standard PES algorithm is of
> the order of 2^64 encryptions, a considerable reduction from
> the work that a cryptanalyst would expected (sic) in an
> exhaustive key search for the 128-bit key."
>
> I note that this is comparable to realizing that double-DES, with
> a putative 112-bit key, actually has a strength similar to a
> 57-bit key. Since double-DES has twice the expense of normal 56-bit
> DES, this was sufficient to make double-DES essentially useless.

I'd rather say it's comparable to realizing that DES with a 56-bit
key has a strength of only 47 bits. Both are due to differential
cryptanalysis. The problem with double-DES is of a totally different
nature.

At one level, double-DES can be seen as a 32-round DES with a weak
key-schedule, composed of two ordinary key schedules. The weakness
comes from the fact that it is split into two halves, which
facilitates a meet-in-the-middle attack. If we remove this two-block
scedule and design a new 32-round schedule according to the same
principles as the 16-round, we should be able to get a lot more
security out of each round.

> (differential) attack, so maybe it is better. But maybe we can fix
> up double-DES without changing the internals of the proven cipher.

How about changing only the key schedule, and leaving the
rounds intact?

>
>
> Terry
>
>
>

--
Thor Kristoffersen - Oslo, Norway - th...@ifi.uio.no

Paul C Leyland

unread,
Feb 28, 1994, 9:09:24 AM2/28/94
to
In article <2km7dv$j...@msuinfo.cl.msu.edu> m...@scss3.cl.msu.edu (Mark Riordan) writes:

I will prepare a description of the algorithm and have
someone who has not seen RSA DSI's code reimplement it
in C. (RSA's implementation is about 150 lines of C,
so it shouldn't be too hard.) Then we'll have a public
domain implementation of a stronger-than-DES cipher
designed by recognized experts.

Could you ask someone outside the US&Canada please? The reason for this
request should be clear.

Paul
--
Paul Leyland <p...@black.ox.ac.uk> | Hanging on in quiet desperation is
Oxford University Computing Services | the English way.
13 Banbury Road, Oxford, OX2 6NN, UK | The time is gone, the song is over.
Tel: +44-865-273200 Fax: +44-865-273275 | Thought I'd something more to say.
Finger p...@black.ox.ac.uk for PGP key |

Mark Riordan

unread,
Feb 28, 1994, 9:40:12 PM2/28/94
to
Mark Riordan (m...@scss3.cl.msu.edu) wrote:
: I will prepare a description of the algorithm and have

: someone who has not seen RSA DSI's code reimplement it
: in C. (RSA's implementation is about 150 lines of C,
: so it shouldn't be too hard.) Then we'll have a public
: domain implementation of a stronger-than-DES cipher
: designed by recognized experts.

So, here it is:

DESX is an encryption algorithm that extends the famous DES
(Data Encryption Standard) algorithm to a keysize of 120 bits.
It does this by simply XORing the input block with a bit pattern
(pre-Whitening), encrypting with standard DES, and then XORing
the result with another bit pattern (post-Whitening).

DESX was designed by RSA Data Security, and has been in use
in its MailSafe and BSafe encryption products since 1986/87.


RSA DSI says:
"We claim no intellectual property ownership of DESX except for a
copyright on our own implementation and a trademark on DESX. If
someone wanted to use our spec for DESX, they could call it DESX if it
were an accurate implementation. In any case, no money is involved."

The algorithm is quite simple, and is described below. Nearly all
of the steps in the algorithm are at key setup time.

DESX encrypts 64 bits (8 bytes) at a time, just like DES.

DESX takes two keys: a DES key (represented as 8 bytes, but
of course only 56 bits are used, as per DES specs), and a
"Whitening" key of length 8 bytes, of which all 64 bits are significant.

The Whitening key is expanded into two 64-bit bit patterns, the
pre-Whitening pattern, and the post-Whitening pattern.

Because DESX uses absolutely off-the-shelf DES as one of its
pieces, a particular DES implementation is not included as part
of the specification of DESX. It is assumed that you have your
own favorite DES implementation with its own peculiarities in
terms of procedure calling sequences, key data structures, and
so on.

Let's assume the following data structures and procedures.
(I am deliberately using something other than pseudo-C
to help demonstrate that I am not simply publishing RSA's C
source code. I admit that the result is not completely clear,
but I am trying to avoid writing actual code, for various reasons.)

TypDESXKey has members:
DESKey64 -- 8-byte DES key supplied by user
Whitening64 -- 8-byte secondary key supplied by user

TypDESXContext has members:
DESContext -- Processed version of DESKey64. Length and
other details depend upon which DES implementation
you use.
PreWhitening64 -- 8-byte XOR pattern computed by key setup
PostWhitening64 -- Another 8-byte XOR pattern computed by key setup

Assume the following functions:

DESXKeySetup(output: TypDESXContext, input: TypDESXKey)
DESXEncryptBlock(input: DESXContext, output: OutData64, input: InData64)
DESXDecryptBlock(input: DESXContext, output: OutData64, input: InData64)

Assume the following lookup table, based in the digits of PI:

DESXSubstTable[0:255] =
189, 86,234,242,162,241,172, 42,176,147,209,156, 27, 51,253,208,
48, 4,182,220,125,223, 50, 75,247,203, 69,155, 49,187, 33, 90,
65,159,225,217, 74, 77,158,218,160,104, 44,195, 39, 95,128, 54,
62,238,251,149, 26,254,206,168, 52,169, 19,240,166, 63,216, 12,
120, 36,175, 35, 82,193,103, 23,245,102,144,231,232, 7,184, 96,
72,230, 30, 83,243,146,164,114,140, 8, 21,110,134, 0,132,250,
244,127,138, 66, 25,246,219,205, 20,141, 80, 18,186, 60, 6, 78,
236,179, 53, 17,161,136,142, 43,148,153,183,113,116,211,228,191,
58,222,150, 14,188, 10,237,119,252, 55,107, 3,121,137, 98,198,
215,192,210,124,106,139, 34,163, 91, 5, 93, 2,117,213, 97,227,
24,143, 85, 81,173, 31, 11, 94,133,229,194, 87, 99,202, 61,108,
180,197,204,112,178,145, 89, 13, 71, 32,200, 79, 88,224, 1,226,
22, 56,196,111, 59, 15,101, 70,190,126, 45,123,130,249, 64,181,
29,115,248,235, 38,199,135,151, 37, 84,177, 40,170,152,157,165,
100,109,122,212, 16,129, 68,239, 73,214,174, 46,221,118, 92, 47,
167, 28,201, 9,105,154,131,207, 41, 57,185,233, 76,255, 67,171


==> DESXKeySetup works as follows:

Compute DESContext from DESKey64 using the key setup procedures
that come with whatever DES implementation you are using.

Set PreWhitening64 to the input key Whitening64.

Compute PostWhitening64 as:

PostWhitening64 := 0
Run Hash procedure with Input := DESKey64
Run Hash procedure with Input := Whitening64

Hash procedure:
For each Ibyte of the 8 bytes of Input, left to right:
tableindex := left 8 bits of PostWhitening64 XOR
next 8 bits (just to right of above) of PostWhitening64
lastbyte := DESXSubstTable[tableindex]
Shift PostWhitening64 left 8 bits
last (right) 8 bits of PostWhitening64 := lastbyte XOR Ibyte

==> DESXEncryptBlock does this:

OutData64 := InData64 XOR PreWhitening64
OutData64 := DESEncrypt(DESContext,OutData64)
OutData64 := OutData64 XOR PostWhitening64

==> DESXDecryptBlock does this:

OutData64 := InData64 XOR PostWhitening64
OutData64 := DESDecrypt(DESContext,OutData64)
OutData64 := OutData64 XOR PreWhitening64


Mark Riordan 28 February 1994 m...@ripem.msu.edu

Andrew Haley

unread,
Mar 1, 1994, 2:15:23 PM3/1/94
to
Terry Ritter (rit...@cactus.org) wrote:

: Ritter Software Engineering


: 2609 Choctaw Trail
: Austin, Texas 78745
: (512) 892-0494, rit...@cactus.org

: Ladder-DES: A Proposed Candidate to Replace DES

: Terry Ritter
: February 22, 1994

[ ...deleted... ]

: A B


: | k1 |
: v v |
: XOR <- DES1 ----|
: | |
: | k2 |
: | v v
: |---- DES2 -> XOR
: | |
: v v
: C D

It's worth pointing out that when used this way DES is always carried
out in the "forward" direction, even during decryption. Because of
this, the "scrambling" function used in the "ladder" only needs to be
a pseudorandom function; it does not have to be a pseudorandom
permutation like DES. A hash function with a 128-bit input and a 64
bit output could be used for this purpose.

[ ...deleted... ]

: Conclusion

: DES operations can be arranged into a "ladder-DES" constructs which
: are especially-clean and familiar and seem to resist known attacks.
: These constructs seem potentially stronger than normal DES and are
: demonstrably faster than triple-DES. Thus, ladder-DES could be a
: reasonable candidate to replace DES.

These schemes have been the subject of much research in recent years.
The classic paper is [1], in which it is shown that three rounds in
the structure above are sufficient to prove perfectness (polynomial
time indistinguishability from a truly random permutation), provided
that the random functions are themselves perfect.

There have been many papers on schemes to reduce the key space by
using one of the pseudorandom functions more than once; a few examples
are given here.

Andrew.

[1] M. Luby and C. Rackoff, "How to construct pseudorandom
permutations from pseudorandom functions," SIAM J. Comput. vol 17,
pp. 373-386, 1988.

[2] Ulei M. Maurer, "A Simplified and Generalized Treatment of
Luby-Rackoff Pseudorandom Permutation Generators," Proc. EUROCRYPT
'92, pp. 239-255, 1993.

[3] Jacques Patarin, "How to construct pseudorandom and super
pseudorandom permutations from one single pseudorandom function,"
Proc. EUROCRYPT '92, pp. 256-266, 1993.

[4] Jacques Patarin, "New results on pseudorandom permutation
generators based on the DES scheme," Proc. CRYPTO '91, pp. 301-312,
1992.

[5] Josef Pieprzyk,, "How to construct Pseudorandom Permutations from
Single Pseudorandom Functions," Proc. EUROCRYPT '90, pp. 140-150,
1991.


--
"Always keep an open mind, but not so open that your brain falls out."

Dave Sparks

unread,
Mar 4, 1994, 9:07:34 PM3/4/94
to
Terry Ritter wrote:

>> This raises the possibility
>> that a "certificational" weakness may exist which we currently do
>> not know how to exploit, but which may be dangerous anyway. This
>> particular weakness depends upon small blocks.

What is a "certificational weakness"?

/--------------+------------------------------------\
| | Internet: daves...@delphi.com |
| Dave Sparks | Fidonet: Dave Sparks @ 1:207/212 |
| | Famnet: Dave Sparks @ 77:500/1 |
| | BBS: (909) 353-9821 - 14.4K |
\--------------+------------------------------------/

Andrew Haley

unread,
Mar 6, 1994, 12:26:59 PM3/6/94
to
Andrew Haley (a...@cam-orl.co.uk) wrote:
: Terry Ritter (rit...@cactus.org) wrote:

: : DES operations can be arranged into a "ladder-DES" constructs which


: : are especially-clean and familiar and seem to resist known attacks.
: : These constructs seem potentially stronger than normal DES and are
: : demonstrably faster than triple-DES. Thus, ladder-DES could be a
: : reasonable candidate to replace DES.

: These schemes have been the subject of much research in recent years.
: The classic paper is [1], in which it is shown that three rounds in
: the structure above are sufficient to prove perfectness (polynomial
: time indistinguishability from a truly random permutation), provided
: that the random functions are themselves perfect.

: There have been many papers on schemes to reduce the key space by
: using one of the pseudorandom functions more than once; a few examples
: are given here.

I've been doing a bit more reading on this subject.

It turns out that the three round scheme (f1, f1, f2), where f1 and f2
are random functions, was proved by Ohnishi in his Master's thesis to
be indistinguishable from a random permutation. This means that if
DES were a truly random function, three rounds of ladder DES with the
first two rounds having identical keys would be adequate. The trouble
is that DES isn't a truly random function, so Ohnishi's result doesn't
necessarily apply. However, it's a good starting point.

Andrew.

Reference:

Zheng, Matsumoto, and Imai, "On the Construction of Block Ciphers
Provably Secure and Not Relying on Any Unproved Hypotheses,"
Proc. CRYPTO '89, pp 461-480.


0 new messages