layers interleaving substitutions and permuta- LFSR 1

tions to build strong block ciphers. Such design

is called a substitution“permutation sandwich or LFSR 2

a substitution-permutation network (SPN). Al-

though weak on its own, a line of substitutions

followed by a permutation has good “mixing” prop-

output

erties: substitutions add to local confusion and per- LFSR n

sequence

mutation “glues” them together and spreads (dif-

fuses) the local confusion to the more distant sub-

Powerful attacks exist in the case n = 2 [1, 4].

blocks (see also substitutions and permutations).

Hence, it is better to use several LFSRs, with mod-

If one considers ¬‚ipping a single bit at the input

erate lengths, than just a few large ones. But it has

of such a network, it effects the m output bits of

also been shown that this scheme is vulnerable

particular S-box which in turn are sent to different

if all the LFSRs are short [3]. A Fast Correlation

S-boxes by a permutation. Thus inputs/outputs of

Attack has recently been presented in [2]. (See also

up to m S-boxes would be effected by the avalanche

combination generator.)

of change. These are again permuted into different

S-boxes, covering almost all the S-boxes of the net-

Caroline Fontaine

work. On the output of such network about half of

the bits are effected by change and are ¬‚ipped and References

about half of the bits are not ¬‚ipped. This makes

an outcome of a single bit change at the input hard [1] Dawson, E. (1993). “Cryptanalysis of sum-

to predict, especially if secret key bits are mixed mation generator.” Advances in Cryptology”

into the block between the layers of encryption. ASIACRYPT™92, Lecture Notes in Computer

Without a secret key the SPN performs a complex Science, vol. 718, eds. J. Seberry and Y. Zheng.

but fully deterministic function of its inputs. Mod- Springer-Verlag, Berlin, 209“215.

[2] Golic, J., M. Salmasizadeh, and E. Dawson (2000).

ern ciphers tend to use linear or af¬ne mappings

“Fast correlation attacks on the summation genera-

instead of permutations, which allows them to

tor.” Journal of Cryptology, 13, 245“262.

achieve better diffusion in fewer iterations. Such

[3] Klapper, A. and M. Goresky (1995). “Cryptanaly-

networks are called substitution-linear (SLN) or

sis based on 2-adic rational approximation.” Ad-

substitution-af¬ne networks (SAN). The current

vances in Cryptology”CRYPTO™95, Lecture Notes

block encryption standard Rijndael/AES is a SLN in Computer Science, vol. 963, ed. D. Coppersmith.

cipher. Springer-Verlag, Berlin, 262“273.

[4] Meier, W. and O. Staffelbach (1992). “Correlation

Alex Biryukov

properties of combiners with memory in stream ci-

phers.” Journal of Cryptology, 5, 67“86.

Reference

[5] Rueppel, R.A. (1986). Analysis and Design of Stream

Ciphers. Springer-Verlag, Berlin.

[1] Shannon, C.E. (1949). “Communication theory of se- [6] Rueppel, R.A. (1986). “Correlation immunity and

crecy system.” Bell System Technical Journal, 28, the summation generator.” Advances in Crypto-

656“715. logy”CRYPTO™85, Lecture Notes in Computer Sci-

ence, vol. 218, ed. H.C. Williams. Springer-Verlag,

Berlin, 260“272.

SUMMATION GENERATOR

SYMMETRIC

The summation generator is based on a combina-

CRYPTOSYSTEM

tion of n Linear Feedback Shift Registers (LFSRs)

and was ¬rst proposed in [5, 6]. The combining

function is an addition over the set of integers. The type of cryptography in which the same key

From a binary point of view, it is a nonlinear func- is employed for each of the operations in the

tion, with maximum correlation immunity. The cryptosystem (e.g., encryption and decryption),

Synchronous stream cipher 603

and thus that same key, typically a secret, must techniques (through reinitialization, or by putting

some marks in the message, . . .).

be shared by the parties performing the various

operations. See also block cipher, stream cipher, Nevertheless, there is an advantage, in terms of

MAC algorithms, and (for the contrasting notion) errors of transmission. If the ciphertext is altered

asymmetric cryptosystem. by some errors, then this will only affect the de-

Equivalent names are conventional cryptosys- cryption of the wrong bits, but this will have no

tem, secret key cryptosystem, classical cryptosys- effect on the others.

tem, and private key cryptosystem. These two properties (perfect synchronization

needed, no propagation of errors) lead to some ac-

Burt Kaliski tive attacks: the ¬rst one could be to modify the

ciphertext in order to desynchronize the message

and the keystream during decryption (this can

easily be achieved by deleting or inserting some

SYNCHRONOUS STREAM

bits, for example); the second one consists in mod-

CIPHER ifying the values of some bits, in order to modify

the plaintext obtained after decryption (this can

A synchronous stream cipher consists of a cipher, be powerful if the attacker knows suf¬cient in-

in which the keystream is generated indepen- formation about the message in order to choose

dently of the plaintext and of the ciphertext. It the meaning of the modi¬ed plaintext). This im-

can be depicted as follows: plies that it is important to use, at the same time

as encryption, some integrity/authentication tech-

keystream keystream

niques in order to avoid such attacks.

key key

Most of the stream ciphers used nowadays (see

ciphertext

for example E0 and SEAL) are binary additive

plaintext plaintext

ENCRYPTION DECRYPTION stream ciphers; they are synchronous stream ci-

phers, in which all the data (plaintext, keystream,

The keystream is usually produced by a pseudo- and ciphertext) are binary, and that simply add

random generator, parameterized by a key, which (through the XOR function) the message (plain-

is the secret key of the whole scheme. text/ciphertext) to the keystream.

This means that it is impossible to dynamically A good reference on the topic is [1].

check the synchronization between the keystream

Caroline Fontaine

and the message. The keystreams generated by

the sender (encryption), and by the receiver

Reference

(decryption) must be perfectly synchronized. If

synchronization is lost, then decryption fails

immediately. If we want to be able to resyn- [1] Rueppel, R.A. (1986). Analysis and Design of Stream

chronize both signals, we need some additional Ciphers. Springer-Verlag, Berlin.

604