Cryptographic boolean functions and applications

Cryptographic Boolean

Functions and

Applications

This page intentionally left blank

Cryptographic Boolean

Functions and

Applications

Thomas W. Cusick and Pantelimon Stănică

AMSTERDAM · BOSTON · HEIDELBERG · LONDON

NEW YORK · OXFORD · PARIS · SAN DIEGO

SAN FRANCISCO · SINGAPORE · SYDNEY · TOKYO

Academic Press is an imprint of Elsevier

Academic Press is an imprint of Elsevier

525 B Street, Suite 1900, San Diego, CA 92101-4495, USA

Linacre House, Jordan Hill, Oxford OX2 8DP, UK

First edition 2009

Copyright © 2009 Elsevier Inc. All rights reserved

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any

means electronic, mechanical, photocopying, recording or otherwise without the prior written permission of the

publisher

Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone

(+44) (0) 1865 843830; fax (+44) (0) 1865 853333; email: [email protected]. Alternatively visit the Science

and Technology website at www.elsevierdirect.com/rights for further information

Notice

No responsibility is assumed by the publisher for any injury and/or damage to persons or property as a matter of

products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions or

ideas contained in the material herein. Because of rapid advances in the medical sciences, in particular, independent

verification of diagnoses and drug dosages should be made

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

ISBN: 978-0-1237-4890-4

For information on all Academic Press publications visit our web site at

elsevierdirect.com

Printed and bound in United States of America

09 10 11 11 10 9 8 7 6 5 4 3 2 1

To my wife Beverly and my children Alan and Laura – T.W.C.

To my wife Nicoleta Gabriela and my daughter Maria Andreea – P.S.

This page intentionally left blank

Contents

Preface ....................................................................... xi

CHAPTER 1 A bit of history .............................................. 1

1.1 George Boole (1815–1864).............................................. 1

1.2 Claude Elwood Shannon (1916–2001)................................. 3

CHAPTER 2 Fourier analysis of Boolean functions ..................... 5

2.1 Basic Definitions on Boolean Functions .............................. 5

2.2 Walsh Transform ........................................................ 7

2.3 Autocorrelation Function .............................................. 8

2.4 Walsh Transform on Subspaces ........................................ 9

2.5 Linear Transformations and the Sign Function ...................... 10

2.6 Parseval Equation ....................................................... 12

2.7 Asymptotic Results on Walsh Coefficients ........................... 13

2.8 Probability Distributions............................................... 14

2.9 Hadamard Matrices and Nonlinearity Bounds ....................... 16

2.10 Fast Walsh Transform................................................... 18

2.11 LFSRs and Linear Complexity......................................... 19

2.12 The Berlekamp–Massey Algorithm ................................... 21

2.13 De Bruijn Sequence ..................................................... 22

CHAPTER 3 Avalanche and propagation criteria ....................... 25

3.1 Introduction ............................................................. 25

3.2 Counting SAC Functions .............................................. 26

3.3 Counting Balanced SAC Functions ................................... 28

3.4 Higher Order SAC ...................................................... 29

3.5 Propagation Criteria .................................................... 38

3.6 Higher Order PC(k) ................................................... 39

3.7 Construction of SAC(k) and PC(k) Functions...................... 41

CHAPTER 4 Correlation immune and resilient Boolean functions .... 49

4.1 Introduction ............................................................. 49

4.2 Basic Properties of Correlation Immunity............................ 50

4.3 LFSRs and Correlation Immunity..................................... 52

vii

viii Contents

4.4 Counting Correlation Immune Functions............................ 59

4.5 Resilient Functions...................................................... 60

4.6 Tradeoff Between Correlation Immunity and Degree ............... 61

4.7 Connections with Orthogonal Arrays ................................ 63

4.8 Constructing Correlation Immune Functions ....................... 65

4.9 Tradeoff Between Correlation Immunity and Nonlinearity ........ 68

CHAPTER 5 Bent Boolean functions ..................................... 73

5.1 Introduction ............................................................. 73

5.2 Definitions and Background ........................................... 74

5.3 Characterizations of the Bent Property ............................... 76

5.4 Meier and Staffelbach’s Approach ..................................... 79

5.5 Degree of a Bent Function ............................................. 80

5.6 New From Old Bent Functions........................................ 81

5.7 Rothaus’s Construction ................................................ 84

5.8 Maiorana and McFarland’s Construction ............................. 85

5.9 Dillon’s Construction .................................................. 86

5.10 Dobbertin’s Construction.............................................. 89

5.11 Carlet’s Construction ................................................... 90

5.12 Extended Maiorana–McFarland Class ................................. 90

5.13 Normal and Nonnormal Bent Functions ............................. 96

5.14 Counting Bent Functions .............................................. 97

5.15 Highly Nonlinear Balanced Functions ................................ 100

5.16 Partially Bent Functions................................................ 104

5.17 Semi-bent Functions .................................................... 106

5.18 Symmetric Bent Functions ............................................. 107

5.19 Rotation Symmetric Functions ........................................ 108

5.20 Enumeration of Rotation Symmetric Functions ..................... 113

CHAPTER 6 Stream cipher design.......................................119

6.1 Introduction ............................................................. 119

6.2 Boolean Functions in Pseudorandom Bit Generators................ 120

6.3 Nonlinear Combination Generators .................................. 124

6.4 Nonlinear Filter Generators ........................................... 128

6.5 Multiplexer Generator.................................................. 132

6.6 Irregularly Clocked LFSRs in Generators ............................ 140

6.7 Algebraic and Linearization Attacks .................................. 147

6.8 The eSTREAM Project ................................................ 155

CHAPTER 7 Block ciphers ...............................................157

7.1 Some History............................................................ 157

7.2 Introduction ............................................................. 158

Contents ix

7.3 Block Ciphers’ Modes of Operation .................................. 159

7.3.1 Confidentiality modes ........................................... 159

7.3.2 Authentication modes ........................................... 162

7.4 Design Approaches...................................................... 163

7.4.1 Feistel ciphers..................................................... 163

7.4.2 Substitution permutation networks ............................ 164

7.5 Notable Symmetric Ciphers ........................................... 165

7.5.1 Data Encryption Standard....................................... 166

7.5.2 Advanced Encryption Standard ................................. 173

7.6 Periods of Rijndael Transformations .................................. 180

7.7 Algebraic Representations of Rijndael/AES .......................... 181

7.8 Embedding AES in BES ................................................ 185

7.9 Further Embeddings of AES ........................................... 190

CHAPTER 8 Boolean Cayley graphs .....................................193

8.1 Introduction ............................................................. 193

8.2 Spectra of Boolean Cayley Graphs .................................... 195

8.3 Few Spectral Coefficients of Boolean Functions ..................... 196

8.4 Bent Boolean Cayley Graphs .......................................... 197

8.5 Coloring the Boolean Cayley Graph .................................. 200

8.6 Avalanche Features of the Cayley Graphs ............................ 201

8.7 Sensitivity of Hamming Weight of f to Spec(Γf

).................... 204

8.8 Boolean Cayley Graphs Under Affine Transformations............. 205

References ...................................................................209

Index .........................................................................229

This page intentionally left blank

Preface

Boolean functions have been an object of study in cryptography for over 50 years,

beginning with their use in linear feedback shift registers. It was in the late 1940s that

Shannon published the concepts of confusion and diffusion as fundamental concepts for

achieving security in cryptosystems. Confusion is reflected in the nonlinearity of parts

of the cryptosystem; linear systems are generally easy to break. Diffusion is achieved by

ensuring that a small change in the input is spread out to make a large change in the

output. Boolean functions can easily provide both confusion and diffusion. One goal of

this book is to show how to choose good Boolean functions for this purpose.

The book is designed to serve as a reference for various applications of Boolean

functions in modern cryptography, which we can say is about 35 years old. The relevant

material in the literature is scattered over hundreds of journal articles, conference

proceedings, books, reports and notes (some of them only available online). Until this

book, there has been no attempt to gather the gist of this material in one place. Our goal

is to present the major concepts and associated theorems, with proofs, except in those

cases where the proofs would be too long or too technical. The book is expository and

we have attempted to be accurate in assigning credit for the many results quoted here.

There is some original research in the book, and we have made quite a few corrections

and improvements to earlier work.

The bibliography is extensive, but is not intended to be all-inclusive. In particular, it is

common in cryptography for research which has been first published in the proceedings

of a conference (‘conference version’) to be published later (perhaps with refinements or

improvements) in a journal (‘journal version’). Many authors seem to fear that publishing

only a conference version will lead to their results not being as widely read or referred

to. In some cases where a more complete journal version of an article is available, we

have not listed the earlier, less polished, conference version. Of course this justifies the

fear that some of the authors had! We have not hesitated to give online references where

these are the only possible ones. We believe that the problem of long-term archiving of

online materials will be solved.

We have tried to avoid any errors, but in a book of this size it is likely that some

remain. The authors at first thought to resolve this issue by having each one blame the

other for any mistakes, but then decided instead to request that readers notify at least

one of us of any errors. We will then correct them in later editions, or via a posting of

online errata.

We would like to thank our institutions, the State University of New York at Buffalo

(T.W.C.), and Naval Postgraduate School and Institute of Mathematics of the Romanian

xi

xii Preface

Academy (P.S.), for their excellent working conditions, and for allowing us to take some

time off, while this book was written.

The authors express their gratitude to the following people who undertook the task

of going through the various parts of this book in its incipient form: Anna Bernasconi,

David Canright, Claude Carlet, Bruno Codenotti, Ed Dawson, Hal Fredricksen,

Subhamoy Maitra, and Yuliang Zheng. The second author also thanks the group of stu￾dents in the ‘Cryptographic Boolean Functions’ course at Naval Postgraduate School

who diligently went through the manuscript in the Fall of 2008.

Thomas W. Cusick

Buffalo, NY

Pantelimon St˘anic˘a

Monterey, CA

September 2008

CHAPTER

1

A bit of history

1.1 GEORGE BOOLE (1815---1864)

FIGURE 1.1

Picture reprinted from MacTutor History of

Mathematics:

http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Boole.html

The definitive biography of Boole is George Boole: His Life and Work, by Desmond

MacHale (Boole Press, 1985) [286]. We shall be using both this book [286] and the biog￾raphy written by O’Connor and Robertson for the MacTutor History of Mathematics

archive [351].

George Boole, the son of a lower class tradesman, was born in Lincoln, England, at the

end of November 1815. His father gave him his first mathematics lessons and instilled

in him the love of learning. A family friend (a local bookseller) helped teach him basic

Latin. Boole was translating Latin poetry by the age of 12. By 14, the adolescent Boole

was fluent in German, Italian and French, as well. He especially liked novels and poetry.

Cryptographic Boolean Functions and Applications 1

2 CHAPTER 1 A bit of history

His powers in higher mathematics did not show until he was 17 years old (he read his

first advanced mathematics book, namely Lacroix’s Differential and Integral Calculus).

Because his father’s business failed, he was forced to work to support his family. At 16 he

became an assistant master in a private school at Doncaster, and before he was 20 years

old he opened his own school.

In 1838, Boole was offered to take over Hall’s Academy in Waddington, after its

founder, Robert Hall, died. His family moved to Waddington and helped him run

the school. Using mathematical journals borrowed from the local Mechanic’s Institute,

Boole read Principia of Isaac Newton and the works of French mathematicians Pierre￾Simon Laplace (1749–1827) and Joseph Louis Lagrange (1736–1813). After learning what

these authors previously wrote, Boole, at 24, published his first paper (Researches on

the theory of analytical transformations) in the Cambridge Mathematical Journal (CMJ). It

sparked a friendship between George Boole and the editor of CMJ, Duncan F. Gregory,

which lasted until the premature death of Gregory in 1844. Gregory influenced Boole

to study algebra. Because of his family’s financial situation, Boole was unable to take

Gregory’s advice and audit courses at Cambridge. In fact, in the summer of 1840 he

opened a boarding school in Lincoln and again the whole family moved back with him.

After his father died, Boole took up, in 1849, a Mathematics Professorship position at

Queen’s College in Cork, where he remained and taught for the rest of his life. There,

he met a niece of Sir George Everest (of Everest mountain fame), by the name of Mary

Everest. She was 17 years younger than him, but they became friends instantly. George

began to give Mary lessons on the differential calculus, and in 1855, after her father died,

Mary married George Boole. They were quite happy together and five daughters were

born: Mary Ellen (b. 1856), Margaret (b. 1858), Alicia (later Alicia Stott) (b. 1860), Lucy

Everest (b. 1862), and Ethel Lilian (b. 1864).

The works of Boole are contained in about 50 articles and a few other publications.

A list of Boole’s memoirs and papers, on logical and mathematical topics, is found in

the Catalogue of Scientific Memoirs published by the Royal Society, and in a volume on

differential equations (edited by I. Todhunter). Boole wrote 22 articles in the Cambridge

Mathematical Journal and its successor, the Cambridge and Dublin Mathematical Journal,

16 papers in the Philosophical Magazine, six memoirs in the Philosophical Transactions (The

Royal Society), and a few others in the Transactions of the Royal Society of Edinburgh and

of the Royal Irish Academy, in the Bulletin de l’Academie de St-Petersbourg (in 1862, under

the pseudonym G. Boldt), and in Crelle’s Journal, and a paper on the mathematical basis

of logic published in the Mechanics Magazine (1848).

In 1844, the Royal Society gave him a medal for his contributions to analysis, because

of his work on using algebra and calculus to analyze infinitely small and large figures.

Calculus of reasoning, which Boole was preoccupied with, found its way into his

1847 work, The Mathematical Analysis of Logic, that expanded on the work of the

German mathematician Gottfried Wilhelm Leibniz (1646–1716) and pushed the idea

that logic was a mathematical discipline, rather than philosophy. This paper won him

the admiration of the distinguished logician Augustus de Morgan, and a place among the

faculty of Ireland’s Queen’s College.