Communications and Control Engineering Series Editors: A. Fettweis· 1. L. Massey· M. Thoma Rainer A. Rueppel Analysis and Design of Stream Ciphers With 53 Figures Springer-Verlag Berlin Heidelberg NewY ork London Paris Tokyo Dr. RAINER A. RUEPPEL Dept. of Electrical Engineering and Computer Science University of California, San Diego EECSC-014 La Jolla, CA 92093 USA lSBN-13 :978-3-642-82867-6 e-lSBN-13:978-3-642-82865-2 DOl: 10.1007/978-3-642-82865-2 Library of Congress Cataloging in Publication Data. Rueppel, Rainer, Analysis and design of stream ciphers. (Communications and control engineering series) 1. Ciphers. 2. Cryptography. I. Title. II. Series. Z104.R83 1986 652'.8 86-17663 ISBN-13:978-3-642-82867-6 (U.S.) This work is subject to copyright All rights are reserved, whether the whole orpart ofthe material is concerned, specifically those oftranslation, reprinting, re-use ofi llustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to "Verwertungsgesellschaft Wort", Munich. © Springer-Verlag Berlin, Heidelberg 1986 Sof tcover reprint of the hardcover I st edition 1986 The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific sratement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. 216113020-543210 Acknowledgments This book would not exist without Professor Jim Massey, my for mer thesis advisor at the Swiss Federal Institute of Technology in Zurich. Most of the research results presented here were de veloped during my time as research associate with Jim. Working wi th him provided both inspi ration and challenge at the same time. I can only hope that this book approaches the high stand ard of excellence exemplified by his own wor·k. I am indepted to Borer Electronics AG, Solothurn, Switzerland, supporting the preparation of this book. The cooperation origin ated in a joint project for the European Space Agency which was concerned about methods for encryption of spacecraft telemetry and telecommand links. Many of the new approaches presented here were inspired by the setup considered in this joint project. I wish to thank Hans-Peter Bader who worked with me on the ESA project for his thorough proof-reading of the manuscript. Spe cial thanks are due to Karin Beyeler who efficiently mastered every hurdle in the preparation of the final manuscript, from deciphering my hand-writing, over fighting with text-processors and printers, to drawing the figures. I also wish to thank Othmar Staffelbach, currently with Gretag, Regensdorf, for his detailed comments and helpful suggestions concerning my doctoral thesis. Last but not least, I wish to thank my wife Ursula who was awai ting our fi rst baby during the time I wrote my doctoral thesis und who is presently awaiting our second baby, for her continuing support and understanding. Foreword It is now a decade since the appearance of W. Diffie and M.E. Hellmann's startling paper, "New Directions in Cryptography". This paper not only established the new field of public-key cryptography but also awakened scientific interest in secret-key cryptography, a field that had been the almost exclusive domain of secret agencies and mathematical hobbyist. A number of ex cellent books on the science of cryptography have appeared since 1976. In the main, these books thoroughly treat both public-key systems and block ciphers (i.e. secret-key ciphers with no memo ry in the enciphering transformation) but give short shrift to stream ciphers (i. e. , secret-key ciphers wi th memory in the enciphering transformation). Yet, stream ciphers, such as those . implemented by rotor machines, have played a dominant role in past cryptographic practice, and, as far as I can determine, re main still the workhorses of commercial, military and diplomatic secrecy systems. My own research interest in stream ciphers found a natural re sonance in one of my doctoral students at the Swiss Federal Institute of Technology in Zurich, Rainer A. Rueppe1. As Rainer was completing his dissertation in late 1984, the question arose as to where he should publish the many new results on stream ciphers that had sprung from his research. Because his work had been starkly fundamental, had spanned a wide area, and had been described in his dissertation with remarkable clarity, it seemed a shame to publish this work in fragments as is the usual prac tice. I thus asked Rainer to prepare a book for this series, one that would expand his dissertation to a broad treatment of stream ciphers. In short, I asked him to fill the yawning gap for a book that would give stream ciphers the thorough attention that their importance merits. Rainer accepted the challenge and produced this book that manages to incorporate many new results into a unified study of stream ciphers. This is the first book in this Springer series devoted to cryp tography, but others are already underway. I hope to make this series into an outlet for significant new treatises on crypto graphy. Rainer's book has set a high standard for those to follow. James L. Massey List oflliustrations Fig. 2.1. The basic 2 enciphering principles ................... 5 Fig. 2.2. A decomposed synchronous stream cipher ............... 7 Fig. 2.3. Principle of one-time-pad ...•........................ 8 Fig. 2.4. The keystream generator as an autonomous finite state machine .............................................. 11 Fig. 2.5. The conceptual distinction between driving and non linear combining subsystem in a general key stream generator ......•........................•............ 12 Fig. 2.6. The state filter generator (a) explicitly showing the memory associated to the nonlinear combiner F, and (b) equivalent practical realizations .................... 13 Fig. 2.7. Principle of a self-synchronizing stream cipher 15 Fig. 3.1. A general linear feedback shift register ............. 24 Fig. 4.1. Linear complexity profiles of the swiss coin sequence (4.1) and the PM-sequence generated by <5,1+D2+D5> and initial state [0,0,0,0,1] ............................ 33 Fig. 4.2. Graphically illustration of the linear complexity growing process ...................................... 34 Fig. 4.3. A typical rando~walk segment of A(sn) ............... 43 Fig. 4.4. The perfect staircase profile associauddto the sequence (4.32) ...................................... 45 Fig. 5.1. Example of a nonlinear function of binary variables in algebraic normal form ................................ 55 Fig. 5.2. Description of integer sum of two binary va!iables over the integers (a) and over GF(2) (b) ............. 56 Fig. 5.3. An LFSR filtered by the general nonlinear function f . 59 Fig. 5.4. The <4,1+D+D4> maximal-length LFSR filtered by a non- linear function f .................................... 63 Fig. 5.5. The general decomposed linear equivalent of the pure cycl i ng shi ft regi s te r of length 15 .................. 66 Fig. 5.6. The decomposed linear equivalent associated to the "Swiss coin sequence" 2 given in (5.15) .............. 68 Fig. 5.7. Linear equivalent associated to the "Swiss coin sequence" (5.15) ..................................... 69 Fig. 5.8. The nonlinear generator associated to the "Swiss coin sequence" (5.15) ................•............... 70 VIII Fig. 5.9. The nonlinear generator simulating the LFSR 234 < 4 , 1 + D+ D + D + D > .................................... 7 2 Fig. 5.10. Reciprocal nonlinear generator pair, each one pro ducing the reversed version of the other's output sequence ............................................ 77 Fig. 5.1l. The LFSR <7,D7+D3+D2+D+1> driving two distinct 4th order products ...................................... 87 Fig. 5.12. A commonly used running-key generator structure ..... 92 Fig. 5.13. Product of 2 sequences of GF(2) and associated linear equivalents .................•....... ". ............... 102 Fig. 5.14. Product of 2 sequences over GF(3) and associated linear equivalents .................................. 104 Fig. 5.15. Information-theoretic model used to define correla- tion-immunity (BSS = Binary Symmetric Source) ....... 116 Fig. 5.16. Attainable region of k + m for (a) arbitrarily dis tributed Z (--), (b) uniformly distributed Z (--) ... 117 Fig. 5.17. The mapping F2 (known as "improved Geffe" or "thresh- old mapping for 3 input variables") and its Walsh transform ........................................... 119 Fig. 5.18. The same conversion procedure can be used for con version from ANF to table form of a boolean function as for conversion from table form to ANF. Each arrow indicates a GF(2) vector addition 132 Fig. 5.19. General analyzable nonlinear feedforward keystream generator ........................................... 135 Fig. 5.20. Possible realization of the example given at the be ginning of section 5.3 where A(Y1) = 15, A(Y2) = 21, A(Y3) = 28 and the resulting A(z) = 1323 ............ 141 Fig. 6.1. Conceptual configuration of a d-fold clocked LFSR with fixed feedback connections (a) and the mathe matically equivalent LSFR as observed from the outside ............................................. 143 Fig. 6.2. The original LFSR with c(X) = x4 + X + 1 shown in the box and the simulated LFSRs (1) - (5) as occurring by use of the corresponding speed factors .............. 148 Fig. 6.3. A perfect linear cipher system, using a conjectured minimum of two random key digits per plaintext digit 153 Fig. 6.4. The random sequence generator suggested by the linear cipher problem, employing multiple speed LSFRs 155 IX Fig. 7.1. The knapsack as nonlinear mapping between binary vector spaces •••....•••••..••••••••.••••••••••••••.. 169 Fig. 7.2. Flowgraph of weight determining algorithm .....•••••• 175 Fig. 7.3. Least significant bit function .....••••..........••. 184 Fig. 7.4. Second-least significant bit function •••.•..•••••••• 184 Fig. 7.5. Most significant bit function •.....•.•.•••..•••••••• 184 Fig. 7.6. GF(2)-description of the integer sum of two 3-bit intege r ••••••...••••••...•....................•..... 187 Fig. 7.7. Complete GF(2) description of an N=4 weight, modulus Q=16 knapsack .•.••••••....••......•••.....•••...•..• 189 Fig. 7.8. The maximum nonlinear order of s.=f. K(x) as function t ~· on 0 f th e pos~. t'~ on ~. n S = So + ) sl 2) , + .-. + s28 228 wh en N = 29 and Q = 229 .......••.....•••......••••...•••• 191 Fig. 8.1. Conceptual knapsack stream cipher ••........••••....• 193 Fig. 8.2. Theoretical upperbound Amax (according to (8.1),(8.2)) and experimental average Aavg for A(Sj) when L = 8 .. 196 Fig. 9.1. Information-theoretic model of an FSM-combiner used to define correlation-immunity (qSS = q-ary symmetric source) ..••.••................•••.....•••.........•• 210 Fig. 9.2. FSM-equivalent of a J-K Flip-Flop ....••••••....••••• 211 Fig. 9.3. walsh transform of the boolean mapping defined by (9.2a) ...•.•••.......••••..•••......••••.•.•..•••.•• 211 Fig. 9.4. 1-Bit memory FSM-combiner of maximum correlation- immunity N-1 allowing nonlinear order in f .......... 215 Fig. 9.5. Time-sharing of a 3-bit adder to produce bit-serially the real sum of two n-bit integers .••••••...•••••••• 217 Fig. 9.6. General running-key generator basing on the real summation principle •••...••..••••••••••••••••••••••• 228 Fig. 9.7. A structure equivalent to the knapsack stream cipher {see chapter 8) ...•.•....•••...••••••...•••••••••••• 229 x Table 4.1. Values of Nn(L) for n=1, ... ,10 ..•••••...•••••••....• 35 Table 5.1. The basis vector for the 15-dimensional vector space as generated by single product terms of the algebraic normal forn (ANF) of f (e.g. 124 corresponds to the product term ~1~2~4) •••••..••.••••.••••...••.••..••• 64 Table 5.2. The basis vectors ~1, ... ,~15 for the 15 dimensional vector space as generated by single state bits of 1 in the general decomposed linear equivalent ••••••••• 67 Table 5.3. The basis function ~i, .• ,~i5 for the 15-dimensional vector space, or equivalently, the matrix DP-l 71 Table 5.4. Greatest primitive factors of 2m_l for 1 < m < 50 and their factorization •••....••••...••••••...••.......• 111 Table 5.5. Greatest primitive factors of 3m_l for 1 < m < 50 and their factorization ....••.•...•.......••..••........ 112 Table 5.6. Mapping defined by the boolean function F2 = xOxl + xOx2 + xl x2 ...•....•••••...•.••••......• 115 Table 9.1. Small-scale simulations giving evidence that the bound (9.30) is very tight .......•...•...••••••.•••• 226