Next Page

Prev. page

Next Page Next Chapter

CHAPTER 15 ................................................ 356

Combining Block Ciphers ....................... 356

DOUBLE ENCRYPTION .......................... 356

TRIPLE ENCRYPTION ............................ 357

Triple Encryption Two Keys .......................... 357

Triple Encryption with Three Keys ................ 359

Triple Encryption with Minimum Key .............. 359

Triple-Encryption Modes ............................... 359

Figure 15.1 Triple encryption in CBC ............. 360

Variants on Triple Encryption ........................ 361

Figure 15.2 Triple encryption with padding. ... 361

DOUBLING THE BLOCK LENGTH .......... 362

OTHER MULTIPLE ENCRYPTION ........... 362

Double OFB/Counter ..................................... 362

Figure 15.3 Doubling the block length. ........... 363

ECB + OFB ................................................... 363

xDES ............................................................ 364

Figure 15.4 One round of xLIES. .................. 364

Quintuple Encryption ..................................... 365

KEY SHORTENING ................................. 365

WHITENING ............................................. 365

CASCADINGMULTIPLEBLOCKALGORI .. 366

COMBINING MULTIPLE BLOCK .............. 367

Page 356

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

15

CHAPTER

Combining

Block Ciphers

There are many ways to combine block algorithms to get new algorithms. The

impetus behind these schemes is to try to increase security without going through

the trouble of designing a new algorithm. DES is a secure algorithm; it has been

cryptanalyzed for a good 20 years and the most practical way to break it is still brute

force. However, the key is too short. Wouldnâ€™t it be nice to use DES as a building

block for another algorithm with a longer key? Weâ€™d have the best of both worlds:

the assurance of two decades of cryptanalysis plus a long key.

Multiple encryption is one combination technique: using an algorithm to encrypt

the same plaintext block multiple times with multiple keys. Cascading is like mul-

tiple encryption, but uses different algorithms. There are other techniques.

Encrypting a plaintext block twice with the same key, whether with the same

algorithm or a different one, is not smart. For the same algorithm, it does not affect

the complexity of a brute-force search. [Remember, you assume a cryptanalyst

knows the algorithm including the number of encryptions used.) For different algo-

rithms, it may or may not. If you are going to use any of the techniques in this chap-

ter, make sure the multiple keys are different and independent.

15.1 DOUBLE ENCRYPTION

A naive way of improving the security of a block algorithm is to encrypt a block

twice with two different keys. First encrypt a block with the first key, then encrypt

the resulting ciphertext with the second key. Decryption is the reverse process.

C = EK˜(-&#â€˜))

lJ = QqPz&))

If the block algorithm is a group (see Section 11.31, then there is always a K3

such that

C = EY˜˜J˜+I = EK#â€˜)

Page 357

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER15 Combining Block Ciphers

If this is not the case, the resultant doubly-encrypted ciphertext block should be

much harder to break using an exhaustive search. Instead of 2â€ť attempts (where n is

the bit length of the key), it would require 22â€ť attempts. If the algorithm is a 64-bit algo-

rithm, the doubly-encrypted ciphertext would require 212*attempts to find the key.

This turns out not to be true for a known-plaintext attack. Merkle and Hellman

[ 107.51developed a time-memory trade-off that could break this double-encryption

scheme in 2â€ť + l encryptions, not in 22nencryptions. (They showed this for DES, but

the result can be generalized to any block algorithm.) The attack is called a meet-in-

the-middle attack; it works by encrypting from one end, decrypting from the other,

and matching the results in the middle.

In this attack, the cryptanalyst knows Pi, C1, Pz, and CZ, such that

Cl = EK˜L&#â€˜J)

G = J%˜(J%,Pz˜I

For each possible K, he computes EK(PI)and stores the result in memory. After col-

lecting them all, he computes DK(CI) for each K and looks for the same result in

memory. If he finds it, it is possible that the current key is K2 and the key in mem-

ory is K,. He tries encrypting PI with K1 and KZi if he gets C2 he can be pretty sure

(with a probability of success of 1 in 22m- 2n,where m is the block size) that he has

both K1 and K2. If not, he keeps looking. The maximum number of encryption trials

he will probably have to run is 2*2â€ť, or 2â€ť + â€˜. If the probability of error is too large,

he can use a third ciphertext block to get a probability of success of 1 in 23m- â€śâ€˜.

There are still other optimizations [912].

This attack requires a lot of memory: 2â€ť blocks. For a 56-bit algorithm, this trans-

lates to 25664-bit blocks, or 10â€ť bytes. This is still considerably more memory stor-

age than one could comfortably comprehend, but itâ€™s enough to convince the most

paranoid of cryptographers that double encryption is not worth anything.

For a 128-bit key, the amount of memory required is an enormous 103â€™ bytes. If we

assume that a way exists to store a bit of information on a single atom of aluminum,

the memory device required to launch this attack would be a cube of solid alu-

minum over a kilometer on a side. And then you need some place to put it! The

meet-in-the middle attack seems infeasible for keys this size.

Another double-encryption method, sometimes called Davies-Price, is a variant

of CBC [435].

Cl = EKI(Pi @EK˜(C˜- 11)

pi = DKl(Ci) @E,(Ci - 1)

They claim â€śno special virtue of this mode, â€ť but it seems to be vulnerable to the

same meet-in-the-middle attacks as other double-encryption modes.

15.2 TRIPLE ENCRYPTION

with Two Keys

Triple Encryption

A better idea, proposed by Tuchman in [ 155 11,operates on a block three times with

two keys: with the first key, then with the second key, and finally with the first key

Page 358

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

again. He suggested that the sender first encrypt with the first key, then decrypt with

the second key, and finally encrypt with the first key. The receiver decrypts with the

first key, then encrypts with the second key, and finally decrypts with the first key.

C = G+&#ll)

p = PK˜(EK˜PI&)))

This is sometimes called encrypt-decrypt-encrypt (EDE) mode [55]. If the block

algorithm has an n-bit key, then this scheme has a 2n-bit key. The curious encrypt-

decrypt-encrypt pattern was designed by IBM to preserve compatibility with con-

ventional implementations of the algorithm: Setting the two keys equal to each

other is identical to encrypting once with the key. There is no security inherent in

the encrypt-decrypt-encrypt pattern, but this mode has been adopted to improve the

DES algorithm in the X9.17 and IS0 8732 standards [55,761].

K1 and Kz alternate to prevent the meet-in-the-middle attack previously described.

If C = EKZ(EK1(EK1(P))), a cryptanalyst could precompute EK1(EK1(P))) every

then for

possible K1 and then proceed with the attack. It only requires 2â€ť +â€™ encryptions.

Triple encryption with two keys is not susceptible to the same meet-in-the-

middle attack described earlier. But Merkle and Hellman developed another time-

memory trade-off that could break this technique in 2â€ť - â€™ steps using 2â€ť blocks of

memory [ 10751.

For each possible K,, decrypt 0 and store the result in memory. Then, decrypt 0

with each possible K1 to get P. Triple-encrypt P to get C, and then decrypt C with K1.

If that decryption is a decryption of 0 with a Kz (stored in memory), the K1 Kz pair is

a possible candidate. Check if it is right. If itâ€™s not, keep looking.

This is a chosen-plaintext attack, requiring an enormous amount of chosen plain-

text to mount. It requires 2â€ť time and memory, and 2â€ť chosen plaintexts. It is not

very practical, but it is a weakness.

Paul van Oorschot and Michael Wiener converted this to a known-plaintext

attack, requiring p known plaintexts. This example assumes EDE mode.

(1) Guess the first intermediate value, a.

(2) Tabulate, for each possible K1, the second intermediate value, b, when the

first intermediate value is a, using known plaintext:

b = GJC)

where C is the resulting ciphertext from a known plaintext.

(3) Look up in the table, for each possible K,, elements with a matching sec-

ond intermediate value, b:

b = &,b)

(4) The probability of success is p/m, where p is the number of known plaintexts

and m is the block size. If there is no match, try another a and start again.

The attack requires 2â€ť +m time and p memory. For DES, this is 2120/p[ 1558). For

/p

p greater than 256, this attack is faster than exhaustive search.

Page 359

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER15 Combining Block Ciphers

Triple Encryption with Three Keys

If you are going to use triple encryption, I recommend three different keys. The

key length is longer, but key storage is usually not a problem. Bits are cheap.

C = EK˜(QY˜(EK#â€˜I))

JJ= ˜K˜˜-&PK˜(C˜)I

The best time-memory trade-off attack takes 2â€™â€ť steps and requires 2â€ť blocks of

memory; itâ€™s a meet-in-the-middle attack [ 10751.Triple encryption, with three inde-

pendent keys, is as secure as one might naively expect double encryption to be.

Triple Encryption with Minimum Key (TEMK)

There is a secure way of using triple encryption with two keys that prevents the

previous attack, called Triple Encryption with Minimum Key (TEMK) [858]. The

trick is to derive three keys from two: X1 and Xz:

KI = &,Px,(&,(T,)))

Kz = Ex,Px2Px,(Tz)))

= &,Px2(&,(W)

K3

Ti, T,, and T3 are constants, which do not have to be secret. This is a special con-

struction that guarantees that for any particular pair of keys, the best attack is a

known-plaintext attack.

Triple-Encryption Modes

Itâ€™s not enough to just specify triple encryption; there are several ways to do it.

The decision of which to use affects both security and efficiency.

Here are two possible triple-encryption modes:

Inner-CBC: Encrypt the entire file in CBC mode three different times

(see Figure 15. la). This requires three different TVs.

Cl = EK,(Si0 Ci - 1);S, = DK2(Ti 0 Si - 1); Tl= EK1(Pi Ti - 1)

0

Pi = Ti - 1 0 DK1( Ti = Si - 1 0 EK2( Si = Ci - 1 0 DK3(

Tl); Si); Ci)

Co, So,and To are IVs.

Outer-CBC: Triple-encrypt the entire file in CBC mode (see Figure 15.lb). This

requires one IV.

Ci = EK3(DKZ(EK1(Pi Cl - I)))

@

I: = Ci - 1 @ DK1(EKZ(DK3(Ci)))

Both modes require more resources than single encryption: more hardware or

more time. However, given three encryption chips, the throughput of inner-CBC is

no slower than single encryption. Since the three CBC encryptions are independent,

three chips can be kept busy all the time, each feeding back into itself.

On the other hand, outer-CBC feedback is outside the three encryptions. This

means that even with three chips, the throughput is only one-third that of single

Page 360

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

15.2 Triple Encryption

(a) Inner CBC (b) Outer CBC

Figure 15.1 Triple encryption in CBC mode.

encryption. To get the same throughput with outer-CBC, you need to interleave IVs

(see Section 9.12):

Ci = EK3(DK2(EK1(Jâ€™i Cl - 3)))

@

In this case CO,C-r, and C-2 are IVs. This doesnâ€™t help software implementations

any, unless you have a parallel machine.

Unfortunately, the simpler mode is also the least secure. Biham analyzed various

modes with respect to chosen-ciphertext differential cryptanalysis and found that

inner-CBC is only slightly more secure than single encryption against a differential

attack. If you think of triple encryption as a single larger algorithm, then inner feed-

backs allow the introduction of external and known information into the inner

workings of the algorithm; this facilitates cryptanalysis. The differential attacks

require enormous amounts of chosen ciphertext to mount and are not very practi-

cal, but the results should be enough to give the most paranoid pause. Another anal-

ysis against meet-in-the-middle and brute-force attacks concludes that they are all

equally secure [8061.

There are other modes, as well. You can encrypt the entire file once in ECB, then

twice in CBC; or once in CBC, once in ECB, and once in CBC; or twice in CBC and

once in ECB. Biham showed that these variants are no more secure than single DES

against a chosen-plaintext differential cryptanalysis attack [ 1621. And he doesnâ€™t

Page 361

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

15 Combining Block Ciphers

CHAPTER

have high hopes for any other variants. If you are going to use triple encryption, use

modes with outer feedback.

Variants on Triple Encryption

Before there were proofs that DES does not form a group, several schemes were

proposed for multiple encryption. One way to guarantee that triple encryption

doesnâ€™t reduce to single encryption is to change the effective block size. One simple

method is to add a bit of padding. Pad the text with a string of random bits, half a

block in length, between the first and second and between the second and third

encryptions (see Figure 15.2). If p is the padding function, then:

C = E,,(p(E,,(p(E,,(P)))))

This padding not only disrupts patterns, but also overlaps encrypted blocks like

bricks. It only adds one block to the length of the message.

Another technique, proposed by Carl Ellison, is to use some kind of keyless per-

mutation function between the three encryptions. The permutation could work on

large blocks-8 kilobytes or so-and would effectively give this variant a block size

of 8 kilobytes. Assuming that the permutation is fast, this variant is not much

slower than basic triple encryption.

C = E,,(T(E,,(T(E,,(P)))))

T collects a block of input (up to 8 kilobytes in length) and uses a pseudo-random-

number generator to transpose it. A l-bit change in the input causes 8 changed out-

put bytes after the first encryption, up to 64 changed output bytes after the second

encryption, and up to 512 changed output bytes after the third encryption. If each

block algorithm is in CBC mode, as originally proposed, then the effect of a single

Plaintext

....

b=Ad

bd

Ciohertext

Figure 15.2 Triple encryption with padding.

Page 362

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

changed input bit is likely to be the entire 8 kilobyte block, even in blocks other

than the first.

The most recent variant of this scheme responded to Bihamâ€™s attack on inner-

CBC by including a whitening pass to hide plaintext patterns. That pass is a stream

XOR with a cryptographically secure random-number generator called R below. The

Ton either side of it prevents the cryptanalyst from knowing a priori which key was

used to encrypt any given byte on input to the last encryption. The second encryp-

tion is labelled nE (encryption with one of n different keys, used cyclically):

C = E,,(R(T(nEK,(T(EK,(R))))))

All encryptions are in ECB mode and keys are provided at least for the n + 2

encryption keys and the cryptographically secure random-number generator.

This scheme was proposed with DES, but works with any block algorithm. I know

of no analysis of the security of this scheme.

15.3 DOUBLING THE BLOCK LENGTH

There is some argument in the academic community whether a 64-bit block is long

enough. On the one hand, a 64-bit block length only diffuses plaintext over 8 bytes

of ciphertext. On the other hand, a longer block length makes it harder to hide pat-

terns securely; there is more room to make mistakes.

Some propose doubling the block length of an algorithm using multiple encryp-

tions [299]. Before implementing any of these, look for the possibility of meet-in-

the-middle attacks. Richard Outerbridgeâ€™s scheme [300], illustrated in Figure 15.3, is

no more secure than single-block, two-key triple encryption 18591.

However, I advise against this sort of thing. It isnâ€™t faster than conventional triple

encryption: six encryptions are still required to encrypt two blocks of data. We

know the characteristics of triple encryption; constructions like this often have hid-

den problems.

15.4 OTHER MULTIPLE ENCRYPTION SCHEMES

The problem with two-key triple encryption is that it only doubles the size of the

keyspace, but it requires three encryptions per block of plaintext. Wouldnâ€™t it be

nice to find some clever way of combining two encryptions that would double the

size of the keyspace?

Double OFB/Counter

This method uses a block algorithm to generate two keystreams, which are then

used to encrypt the plaintext.

S, = EKl(Si - 1 CD II = II + 1

II);

Tl = EK,(Ti - 1 0 Iz)j 12= I2 + 1

Ci = Iâ€™, 8 Si 8 Ti

Page 363

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER15 Combining Block Ciphers

+

+

E

1

5 EK

Right

Left

Right

Left

Half Half

Half Half

7

7

EK EK

2

2

Len Right

Right

Left

Half Half

Half Half

7

7

EK

EK

1

1

I

I

Figure 15.3 Doubling the block length.

Si and Ti are internal variables, and 1i and I2 are counters. Two copies of the block

algorithm run in a kind of hybrid OFB/counter mode, and the plaintext, St and Ti are

XORed together. The two keys, K1 and K,, are independent. I know of no cryptanal-

ysis of this variant.

ECB + OFB

This method was designed for encrypting multiple messages of a fixed length, for

example, disk blocks [186,188]. Use two keys: K1 and K2. First, use the algorithm and

K1 to generate a mask of the required block length. This mask will be used repeat-

edly to encrypt messages with the same keys. Then, XOR the plaintext message

with the mask. Finally, encrypt the XORed plaintext with the algorithm and K2 in

ECB mode.

This mode has not been analyzed outside the paper in which it was proposed.

Clearly it is at least as strong as a single ECB encryption and may be as strong as two

passes with the algorithm. Possibly, a cryptanalyst could search for the two keys

independently, if several known plaintext files are encrypted with the same key.

To thwart analysis of identical blocks in the same positions of different messages,

you can add an IV. Unlike an IV in any other mode, here the IV is XORed with every

block of the message before ECB encryption.

Matt Blaze designed this mode for his UNIX Cryptographic File System (CFS). It

is a nice mode because the latency is only one encryption in ECB mode; the mask

can be generated once and stored. In CFS, DES is the block algorithm.

Page 364

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

15.4 Other Multiple Encryption Schemes

xDESâ€™

In [ 1644,1645], DES is used as a building block for a series of block algorithms

with both larger key sizes and larger block sizes. These constructions do not depend

on DES in any way and can be used with any block algorithm.

The first, xDESâ€™, is simply a Luby-Rackoff construction with the block cipher as

the underlying function (see Section 14.11). The block size is twice the size of the

underlying block cipher and the key size is three times the size of the underlying

block cipher. In each of 3 rounds, encrypt the right half with the block algorithm

and one of the keys, XOR the result with the left half, and swap the two halves.

This is faster than conventional triple encryption, since three encryptions encrypt

a block twice as large as the underlying algorithm. But there is also a simple meet-

in-the-middle attack that finds the key with a table the size of 2k, where k is the key

size of the underlying algorithm. Encrypt the right half of a plaintext block with all

possible values of K1, XOR the left half of the plaintext, and store these values in a

table. Then, encrypt the right half of the ciphertext with all possible values of K3 and

look for a match in the table. If you find one, the key pair K1 and K3 are possible can-

didates for the right key. Repeat the attack a few times, and only one candidate will

remain. This shows that xDESâ€™ is not an ideal solution. Even worse, there is a cho-

sen plaintext attack that proves xDESâ€™ is not much stronger than the underlying

block cipher [858].

xDES2 extends this idea to a 5-round algorithm with a block size 4 times that of

the underlying block cipher and a key size 10 times that of the underlying block

cipher. Figure 15.4 is one round of xDES2; each of the four sub-blocks are the size of

the underlying block ciphers and all 10 keys are independent.

This scheme is also faster than triple encryption: Ten encryptions are used to

encrypt a block four times the size of the underlying block cipher. However, it is

vulnerable to differential cryptanalysis [858] and should not be used. The scheme is

even vulnerable if DES with independent round keys is used.

Figure 15.4 One round of xLIESâ€™.

Page 365

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER15 Combining Block Ciphers

For i 2 3, xDESâ€™ is probably too big to be useful as a block algorithm. For example,

the block size for xDES3 is 6 times that of the underlying cipher, the key size is 21

times, and 21 encryptions are required to encrypt a block 6 times that of the under-

lying block cipher. Triple encryption is faster.

Quintuple Encryption

If triple encryption isnâ€™t secure enough-perhaps you need to encrypt triple-

encryption keys using an even stronger algorithm-then higher multiples might be

in order. Quintuple encryption is very strong against meet-in-the-middle attacks.

(Similar arguments to the ones used with double encryption can show that quadru-

ple encryption provides minimal security improvements over triple encryption.)

C = EK,(DK,(EK,(DK,(EK,(P)))))

P = DK,(EK,(DK˜˜EK,(DK,IC)))))

This construction is backwards compatible with triple encryption if K2 = KS, and

is backwards compatible with single encryption if K1 = K2 = K3. Of course, it would

be even stronger if all five keys were independent.

15.5 CDMF KEY SHORTENING

This method was designed by IBM for their Commercial Data Masking Facility or

CDMF (see Section 24.8) to shrink a 56-bit DES key to a 40-bit key suitable for

export [785]. It assumes that the original DES key includes the parity bits.

(1) Zero the parity bits: bits 8, 16, 24, 32, 40, 48, 56, 64.

(2) Encrypt the output of step (1) with DES and the key Oxc408b0540baleOae,

and XOR the result with the output of step (1).

(3) Take the output of step (2) and zero the following bits: 1, 2, 3, 4, 8, 16, 17,

18, 19, 20, 24, 32, 33, 34, 35, 36, 40, 48, 49, 50, 51, 52, 56, 64.

(4) Encrypt the output of step (3) with DES and the following key:

Oxef2c041ce6382feb. This key is then used for message encryption.

Remember that this method shortens the key length, and thereby weakens the

algorithm.

15.6 WHITENING

Whitening is the name given to the technique of XORing some key material with

the input to a block algorithm, and XORing some other key material with the out-

put. This was first done in the DESX variant developed by RSA Data Security, Inc.,

and then (presumably independently) in Khufu and Khafre. (Rivest named this tech-

nique; itâ€™s a nonstandard usage of the word.)

Page 366

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

15.7 Cascading Multiple Block Algorithms

The idea is to prevent a cryptanalyst from obtaining a plaintext/ciphertext pair for

the underlying algorithm. The technique forces a cryptanalyst to guess not only the

algorithm key, but also one of the whitening values. Since there is an XOR both

before and after the block algorithm, this technique is not susceptible to a meet-in-

the-middle attack.

C = K3 @ E,(P 0 K,)

P = K, @ D,(C 0 K,)

If K, = KS, then a brute-force attack requires 2n + m/poperations, where n is the key

size, m is the block size, and p is the number of known plaintexts. If K, and K3 are

different, then a brute-force attack requires 2â€ť +m+ i operations with three known

plaintexts. Against differential and linear cryptanalysis, these measures only pro-

vide a few key bits of protection. But computationally this is a very cheap way to

increase the security of a block algorithm.

15.7 CASCADINGMULTIPLEBLOCKALGORITHMS

What about encrypting a message once with Algorithm A and key KA, then again

with Algorithm B and key KB. Maybe Alice and Bob have different ideas about

2

which algorithms are secure: Alice wants to use Algorithm A and Bob wants to use

Algorithm B. This technique is sometimes called cascading, and can be extended far

beyond only two algorithms and keys.

Pessimists have said that there is no guarantee that the two algorithms will work

together to increase security. There may be subtle interactions between the two

algorithms that actually decrease security. Even triple encryption with three differ-

ent algorithms may not be as secure as you think. Cryptography is a black art; if you

donâ€™t know what you are doing, you can easily get into trouble.

Reality is much rosier. The previous warnings are true only if the different keys

are related to each other. If all of the multiple keys are independent, then the resul-

tant cascade is at least as difficult to break as the first algorithm in the cascade

[ 1033). If the second algorithm is vulnerable to a chosen-plaintext attack, then the

first algorithm might facilitate that attack and make the second algorithm vulnera-

ble to a known-plaintext attack when used in a cascade. This potential attack is not

limited to encryption algorithms: If you let someone else specify any algorithm

which is used on your message before encryption, then you had better be sure that

your encryption will withstand a chosen-plaintext attack. (Note that the most com-

mon algorithm used for compressing and digitizing speech to modem speeds, used

before any encryption, is CELP-designed by the NSA.)

This can be better phrased: Using a chosen-plaintext attack, a cascade of ciphers

is at least as hard to break as any of its component ciphers [858]. A previous result

showed that the cascade is at least as difficult to break as the strongest algorithm,

but that result is based on some unstated assumptions [528]. Only if the algorithms

commute, as they do in the case of cascaded stream ciphers (or block ciphers in OFB

mode), is the cascade at least as strong as the strongest algorithm.

Page 367

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER15 Combining Block Ciphers

If Alice and Bob do not trust each otherâ€™s algorithms, they can use a cascade. If

these are stream algorithms, the order doesnâ€™t matter. If they are block algorithms,

Alice can first use Algorithm A and then use Algorithm B. Bob, who trusts Algo-

rithm B more, can use Algorithm B followed by Algorithm A. They might even add

a good stream cipher between the two algorithms; it canâ€™t hurt and could very well

increase security.

Remember that the keys for each algorithm in the cascade must be independent.

If Algorithm A has a 64-bit key and Algorithm B has a 128-bit key, then the resul-

tant cascade must have a 192-bit key. If you donâ€™t use independent keys, then the

pessimists are much more likely to be right.

15.8 COMBINING MULTIPLE BLOCK ALGORITHMS

Hereâ€™s another way to combine multiple block algorithms, one that is guaranteed to

be at least as secure as both algorithms. With two algorithms (and two independent

keys):

(1) Generate a random-bit string, R, the same size as the message M.

(2) Encrypt R with the first algorithm.

(3) Encrypt M 0 R with the second algorithm.

(4) The ciphertext message is the results of steps (2) and (3).

Assuming the random-bit string is indeed random, this method encrypts M with

a one-time pad and then encrypts both the pad and the encrypted message with each

of the two algorithms. Since both are required to reconstruct M, a cryptanalyst must

break both algorithms. The drawback is that the ciphertext is twice the size of the

plaintext.

This method can be extended to multiple algorithms, but the ciphertext expands

with each additional algorithm. Itâ€™s a good idea, but I donâ€™t think itâ€™s very practical.