The Design of Rijndael

by Daemen, Joan; Rijmen, Vincent

• ISBN13: 9783540425809
• ISBN10: 3540425802
• Format: Hardcover
• Copyright: 2002-04-01
• Publisher: Springer-Verlag New York Inc

Summary

This book, by the designers of the block cipher, presents Rijndael from scratch. The underlying mathematics and the wide trail strategy as the basic design idea are explained in detail and the basics of differential and linear cryptanalysis are reworked. Subsequent chapters review all known attacks against the Rijndael structure and deal with implementation and optimization issues. In addition, other ciphers related to Rijndael are presented.

Table of Contents

The Advanced Encryption Standard Process	1	(8)
In the Beginning	1	(1)
AES: Scope and Significance	1	(1)
Start of the AES Process	2	(1)
The First Round	3	(1)
Evaluation Criteria	4	(1)
Security	4	(1)
Costs	4	(1)
Algorithm and Implementation Characteristics	4	(1)
Selection of Five Finalists	5	(2)
The Second AES Conference	5	(1)
The Five Finalists	6	(1)
The Second Round	7	(1)
The Selection	7	(2)
Preliminaries	9	(22)
Finite Fields	10	(7)
Groups, Rings, and Fields	10	(1)
Vector Spaces	11	(2)
Fields with a Finite Number of Elements	13	(1)
Polynomials over a Field	13	(1)
Operations on Polynomials	14	(1)
Polynomials and Bytes	15	(1)
Polynomials and Columns	16	(1)
Linear Codes	17	(2)
Definitions	17	(2)
MDS codes	19	(1)
Boolean Functions	19	(4)
Bundle Partitions	20	(1)
Transpositions	21	(1)
Bricklayer Functions	22	(1)
Iterative Boolean Transformations	22	(1)
Block Ciphers	23	(4)
Iterative Block Ciphers	24	(1)
Key-Alternating Block Ciphers	25	(2)
Block Cipher Modes of Operation	27	(2)
Block Encryption Modes	27	(1)
Key-Stream Generation Modes	27	(1)
Message Authentication Modes	28	(1)
Cryptographic Hashing	29	(1)
Conclusions	29	(2)
Specification of Rijndael	31	(22)
Differences between Rijndael and the AES	31	(1)
Input and Output for Encryption and Decryption	31	(2)
Structure of Rijndael	33	(1)
The Round Transformation	33	(8)
The SubBytes Step	34	(3)
The ShiftRows Step	37	(1)
The MixColumns Step	38	(2)
The Key Addition	40	(1)
The Number of Rounds	41	(2)
Key Schedule	43	(2)
Design Criteria	43	(1)
Selection	43	(2)
Decryption	45	(5)
Decryption for a Two-Round Rijndael Variant	45	(1)
Algebraic Properties	46	(2)
The Equivalent Decryption Algorithm	48	(2)
Conclusions	50	(3)
Implementation Aspects	53	(10)
8-Bit Platforms	53	(3)
Finite Field Multiplication	53	(1)
Encryption	54	(1)
Decryption	55	(1)
32-Bit Platforms	56	(3)
Dedicated Hardware	59	(2)
Decomposition of SRD	60	(1)
Efficient Inversion in GF (28)	61	(1)
Multiprocessor Platforms	61	(1)
Performance Figures	62	(1)
Conclusions	62	(1)
Design Philosophy	63	(18)
Generic Criteria in Cipher Design	63	(2)
Security	63	(1)
Efficiency	64	(1)
Key Agility	64	(1)
Versatility	64	(1)
Discussion	64	(1)
Simplicity	65	(1)
Symmetry	65	(4)
Symmetry Across the Rounds	66	(1)
Symmetry Within the Round Transformation	66	(1)
Symmetry in the D-box	67	(1)
Symmetry and Simplicity in the S-box	68	(1)
Symmetry between Encryption and Decryption	68	(1)
Additional Benefits of Symmetry	68	(1)
Choice of Operations	69	(2)
Arithmetic Operations	70	(1)
Data-Dependent Shifts	70	(1)
Approach to Security	71	(2)
Security Goals	71	(1)
Unknown Attacks Versus Known Attacks	72	(1)
Provable Security Versus Provable Bounds	73	(1)
Approaches to Design	73	(3)
Non-Linearity and Diffusion Criteria	73	(1)
Resistance against Differential and Linear Cryptanalysis	73	(1)
Local Versus Global Optimization	74	(2)
Key-Alternating Cipher Structure	76	(1)
The Key Schedule	76	(3)
The Function of a Key Schedule	76	(1)
Key Expansion and Key Selection	77	(1)
The Cost of the Key Expansion	77	(1)
A Recursive Key Expansion	78	(1)
Conclusions	79	(2)
The Data Encryption Standard	81	(8)
The DES	81	(2)
Differential Cryptanalysis	83	(2)
Linear Cryptanalysis	85	(2)
Conclusions	87	(2)
Correlation Matrices	89	(24)
The Walsh-Hadamard Transform	89	(4)
Parities and Selection Patterns	89	(1)
Correlation	89	(1)
Real-valued Counterpart of a Binary Boolean Function	90	(1)
Orthogonality and Correlation	90	(1)
Spectrum of a Binary Boolean Function	91	(2)
Composing Binary Boolean Functions	93	(1)
Xor	93	(1)
And	93	(1)
Disjunct Boolean Functions	94	(1)
Correlation Matrices	94	(4)
Equivalence of a Boolean Function and its Correlation Matrix	95	(1)
Iterative Boolean Functions	96	(1)
Boolean Permutations	96	(2)
Special Boolean Functions	98	(1)
XOR with a Constant	98	(1)
Linear Functions	98	(1)
Bricklayer Functions	98	(1)
Derived Properties	99	(1)
Truncating Functions	100	(1)
Cross-correlation and Autocorrelation	101	(1)
Linear Trails	102	(1)
Ciphers	103	(5)
General Case	103	(1)
Key-Alternating Cipher	104	(1)
Averaging over all Round Keys	105	(1)
The Effect of the Key Schedule	106	(2)
Correlation Matrices and Linear Cryptanalysis Literature	108	(3)
Linear Cryptanalysis of the DES	108	(1)
Linear Hulls	109	(2)
Conclusions	111	(2)
Difference Propagation	113	(10)
Difference Propagation	113	(1)
Special Functions	114	(1)
Affine Functions	114	(1)
Bricklayer Functions	114	(1)
Truncating Functions	115	(1)
Difference Propagation Probabilities and Correlation	115	(2)
Differential Trails	117	(1)
General Case	117	(1)
Independence of Restrictions	117	(1)
Key-Alternating Cipher	118	(1)
The Effect of the Key Schedule	119	(1)
Differential Trails and Differential Cryptanalysis Literature	119	(3)
Differential Cryptanalysis of the DES Revisited	119	(1)
Markov Ciphers	120	(2)
Conclusions	122	(1)
The Wide Trail Strategy	123	(26)
Propagation in Key-alternating Block Ciphers	123	(3)
Linear Cryptanalysis	123	(2)
Differential Cryptanalysis	125	(1)
Differences between Linear Trails and Differential Trails	126	(1)
The Wide Trail Strategy	126	(5)
The γλ Round Structure in Block Ciphers	127	(2)
Weight of a Trail	129	(1)
Diffusion	130	(1)
Branch Numbers and Two-Round Trails	131	(3)
Derived Properties	133	(1)
A Two-Round Propagation Theorem	133	(1)
An Efficient Key-Alternating Structure	134	(4)
The Diffusion Step θ	134	(2)
The Linear Step Θ	136	(1)
A Lower Bound on the Bundle Weight of Four-Round Trails	136	(1)
An Efficient Construction for Θ	137	(1)
The Round Structure of Rijndael	138	(5)
A Key-Iterated Structure	138	(4)
Applying the Wide Trail Strategy to Rijndael	142	(1)
Constructions for θ	143	(2)
Choices for the Structure of I and π	145	(2)
The Hypercube Structure	145	(2)
The Rectangular Structure	147	(1)
Conclusions	147	(2)
Cryptanalysis	149	(12)
Truncated Differentials	149	(1)
Saturation Attacks	149	(5)
Preliminaries	150	(1)
The Basic Attack	150	(2)
Influence of the Final Round	152	(1)
Extension at the End	153	(1)
Extension at the Beginning	153	(1)
Attacks on Six Rounds	153	(1)
The Herds Attack	154	(1)
Gilbert-Minier Attack	154	(2)
The Four-Round Distinguisher	154	(1)
The Attack on Seven Rounds	155	(1)
Interpolation Attacks	156	(1)
Symmetry Properties and Weak Keys as in the DES	156	(1)
Weak keys as in IDEA	157	(1)
Related-Key Attacks	157	(1)
Implementation Attacks	157	(3)
Timing Attacks	157	(1)
Power Analysis	158	(2)
Conclusion	160	(1)
Related Block Ciphers	161	(68)
Overview	161	(2)
Evolution	161	(1)
The Round Transformation	162	(1)
SHARK	163	(2)
Square	165	(3)
BKSQ	168	(3)
Children of Rijndael	171	(2)
Crypton	171	(1)
Twofish	172	(1)
ANUBIS	172	(1)
GRAND CRU	173	(1)
Hierocrypt	173	(1)
Conclusion	173	(2)
Appendices
A. Propagation Analysis in Galois Fields	175	(20)
A.1 Functions over GF (2n)	176	(1)
A.1.1 Difference Propagation	177	(1)
A.1.2 Correlation	177	(2)
A.1.3 Functions that are Linear over GF (2n)	179	(1)
A.1.4 Functions that are Linear over GF (2)	180	(1)
A.2 Functions over (GF(2n))e	181	(1)
A.2.1 Difference Propagation	182	(1)
A.2.2 Correlation	182	(1)
A.2.3 Functions that are Linear over GF(2'')	182	(1)
A.2.4 Functions that are Linear over GF(2)	183	(1)
A.3 Representations of GF (pn)	184	(1)
A.3.1 Cyclic Representation of GF (pn)	184	(1)
A.3.2 Vector Space Representation of GF(pn)	184	(1)
A.3.3 Dual Bases	185	(1)
A.4 Boolean Functions and Functions in GF (2n)	186	(1)
A.4.1 Differences in GF(2)n and GF(2n)	186	(1)
A.4.2 Relationship Between Trace Patterns and Selection Patterns	187	(1)
A.4.3 Relationship Between Linear Functions in GF(p)n and GF(pn)	187	(3)
A.4.4 Illustration	190	(2)
A.5 Rijndael-GF	192	(3)
B. Trail Clustering	195	(16)
B.1 Transformations with Maximum Branch Number	196	(3)
B.2 Bounds for Two Rounds	199	(1)
B.2.1 Difference Propagation	200	(2)
B.2.2 Correlation	202	(2)
B.3 Bounds for Four Rounds	204	(1)
B.4 Two Case Studies	205	(1)
B.4.1 Differential Trails	205	(2)
B.4.2 Linear Trails	207	(4)
C. Substitution Tables	211	(4)
C.1 Srd	211	(1)
C.2 Other Tables	212	(1)
C.2.1 xtime	212	(1)
C.2.2 Round Constants	212	(3)
D. Test Vectors	215	(6)
D.1 KeyExpansion	215	(1)
D.2 Rijndael(128, 128)	215	(2)
D.3 Other Block Lengths and Key Lengths	217	(4)
E. Reference Code	221	(8)
Bibliography	229	(6)
Index	235