The Twofish Encryption Algorithm: A 128-Bit Block Cipher

by Bruce Schneier; John Kelsey; Doug Whiting; David Wagner; Chris Hall; Niels Ferguson

• ISBN13: 9780471353812
• ISBN10: 0471353817
• Edition: 1st
• Format: Hardcover
• Copyright: 1999-01-01
• Publisher: Wiley

Summary

The first and only guide to one of today's most important new cryptography algorithms The Twofish Encryption Algorithm A symmetric block cipher that accepts keys of any length, up to 256 bits, Twofish is among the new encryption algorithms being considered by the National Institute of Science and Technology (NIST) as a replacement for the DES algorithm. Highly secure and flexible, Twofish works extremely well with large microprocessors, 8-bit smart card microprocessors, and dedicated hardware. Now from the team who developed Twofish, this book provides you with your first detailed look at: * All aspects of Twofish's design and anatomy * Twofish performance and testing results * Step-by-step instructions on how to use it in your systems * Complete source code, in C, for implementing Twofish On the companion Web site you'll find: * A direct link to Counterpane Systems for updates on Twofish * A link to the National Institute of Science and Technology (NIST) for ongoing information about the competing technologies being considered for the Advanced Encryption Standard (AES) for the next millennium For updates on Twofish and the AES process, visit these sites: * www.wiley.com/compbooks/schneier * www.counterpane.com * www.nist.gov/aes Wiley Computer Publishing Timely.Practical.Reliable Visit our Web site at www.wiley.com/compbooks/ Visit the companion Web site at www.wiley.com/compbooks/schneier

Author Biography

BRUCE SCHNEIER is President of Counterpane Systems, a worldwide cryptography and information security consulting firm. A world-renowned expert on computer cryptography, Mr. Schneier is the inventor of Blowfish, a cryptography method built into more than 100 commercial products which continues unbroken. He is also the author of the bestselling Applied Cryptography (also available from Wiley). JOHN KELSEY, DAVID WAGNER, CHRIS HALL, and NIELS FERGUSON are well-known cryptographers and Counterpane consultants. DOUG WHITING is a security scientist with Hi/fn, a company specializing in compression technology.

Table of Contents

Preface	iii
AES	iii
This Book	v
Introduction	1	(2)
Twofish Design Goals	3	(2)
Twofish Building Blocks	5	(4)
Feistel Networks	5	(1)
Whitening	5	(1)
S-boxes	6	(1)
MDS Matrices	6	(1)
Pseudo-Hadamard Transforms	7	(1)
Key Schedule	7	(2)
Twofish	9	(10)
The Function F	11	(1)
The Function g	11	(1)
The Key Schedule	12	(5)
Additional Key Lengths	13	(1)
The Function h	14	(2)
The Key-dependent S-boxes	16	(1)
The Expanded Key Words Kj	16	(1)
The Permutations q0 and q1	16	(1)
Round Function Overview	17	(2)
Performance of Twofish	19	(14)
Performance on Large Microprocessors	19	(7)
Keying Options	21	(1)
Code and Data Size	22	(1)
Large Memory Implementations	22	(1)
Total Encryption Times	23	(1)
Hash Function Performance	23	(1)
Language, Compiler, and Processor Choice	24	(2)
Performance on Smart Cards	26	(3)
RAM Usage	27	(1)
Encryption Speed and Key Agility	28	(1)
Code Size	29	(1)
Performance on the Alpha	29	(1)
Performance on Future Microprocessors	29	(1)
Hardware Performance	30	(3)
Twofish Design Philosophy	33	(10)
Performance-driven Design	33	(2)
Performance-Driven Tradeoffs	34	(1)
Conservative Design	35	(1)
Simple Design	36	(2)
Reusing Primitives	37	(1)
Reversibility	37	(1)
S-boxes	38	(2)
Large S-boxes	38	(1)
Algorithmic S-boxes	39	(1)
Key-depndent S-boxes	39	(1)
The Key Schedule	40	(3)
Performance Issues	42	(1)
The Design of Twofish	43	(20)
The Round Structure	43	(4)
Common Block Cipher Structures	44	(3)
The Key-dependent S-boxes	47	(7)
The Fixed Permutations q0 and q1	48	(1)
The S-boxes	49	(1)
Exhaustive and Statistical Analysis	50	(4)
MDS Matrix	54	(3)
Non-key-dependent Coefficients	54	(1)
Implementation Issues	54	(1)
Preserving Diffusion Properties after Rotation	54	(2)
Rotational Uniqueness of Output Vectors	56	(1)
Maximizing the Minimal Hamming Distance	56	(1)
PHT	57	(1)
Eliminating the PHT	57	(1)
Diffusion and the Least Significant Bit	57	(1)
Key Addition	58	(1)
Feistel Combining Operation	58	(1)
Use of Different Groups	58	(1)
Diffusion in the Round Function	59	(1)
Changes Induced by F	59	(1)
One-bit Rotation	59	(2)
Reason for Rotations	60	(1)
Downsides to Rotations	60	(1)
Converting to a Pure Feistel Structure	60	(1)
The Number of Rounds	61	(2)
Design of the Twofish Key Schedule	63	(16)
Round Subkeys	64	(3)
Equivalence of Round Subkeys	64	(1)
Equivalent keys	65	(2)
Controlling Changes in Round Subkeys	67	(5)
XOR Difference Sequences in A and B	68	(1)
Byte Sequences with Given Difference	68	(1)
Identical Byte Sequences	69	(1)
The A and B Sequences	70	(1)
The Sequence (K2i, K2i+1)	70	(1)
Difference Sequences in the Subkeys	71	(1)
The Round Function	72	(2)
Properties of the Key Schedule and Cipher	74	(1)
Equivalent Keys	74	(1)
Self-Inverse Keys	74	(1)
Pairs of Inverse Keys	74	(1)
Simple Relations	75	(1)
Key-dependent Characteristics and Weak Keys	75	(1)
Reed-Solomon Code	76	(3)
Cryptanalysis of Twofish	79	(40)
A Meet-in-the-Middle Attack on Twofish	80	(2)
Results of the Attack	80	(1)
Overview of the Attack	80	(1)
Attacking Twofish with Fixed S and no Whitening	81	(1)
Attacking Twofish with Fixed S	81	(1)
Attacking Normal Twofish	81	(1)
Differential Cryptanalysis	82	(8)
Results of the Attack	82	(1)
Overview of the Attack	82	(2)
Building the Batches	84	(3)
Mounting the Attack	87	(2)
Lessons from the Analysis	89	(1)
Extensions to Differential Cryptanalysis	90	(1)
Higher-Order Differential Cryptanalysis	90	(1)
Truncated Differentials	90	(1)
Search for the Best Differential Characteristic	90	(11)
Differentials of the S-boxes	91	(1)
Differentials of F	92	(4)
Differentials of the Round Function	96	(1)
Multi-round Patterns	96	(1)
Results	97	(1)
Other Problems for the Attacker	97	(1)
Best S-box Differential	98	(1)
Other Variants	99	(1)
Further Work	99	(1)
Conclusion	100	(1)
Linear Cryptanalysis	101	(2)
Multiple Linear Approximations	102	(1)
Non-linear Cryptanalysis	102	(1)
Generalized Linear Cryptanalysis	102	(1)
Partitioning Cryptanalysis	102	(1)
Differential-linear Cryptanalysis	103	(1)
Interpolation Attack	103	(1)
Partial Key Guessing Attacks	104	(1)
Related-key Cryptanalysis	104	(4)
Resistance to Related-Key Slide Attacks	104	(1)
Resistance to Related-key Differential Attacks	105	(1)
The Zero Difference Case	106	(1)
Other Difference Sequences	107	(1)
Probability of a successful Attack with One Related-key Query	107	(1)
Conclusions	108	(1)
A Chosen-key Attack	108	(3)
Overview of the Attack	109	(1)
Finding a Key Pair	109	(1)
Choosing the Plaintexts to Request	110	(1)
Extracting the Key Material	110	(1)
Side-Channel Cryptanalysis and Fault Analysis	111	(1)
Attacking Simplified Twofish	112	(3)
Twofish with Known S-boxes	112	(1)
Twofish without Round Subkeys	112	(2)
Twofish with Non-bijective S-boxes	114	(1)
Trap Doors in Twofish	115	(4)
Using Twofish	119	(6)
Chaining Modes	119	(1)
One-Way Hash Functions	119	(1)
Message Authentication Codes	120	(1)
Pseudorandom Number Generators	120	(1)
Larger Keys	120	(1)
Additional Block Sizes	120	(1)
More or Fewer Rounds	120	(2)
Family Key Variant: Twofish-FK	122	(3)
Analysis	123	(2)
Historical Remarks	125	(4)
Conclusions and Further Work	129	(2)
References	131	(52)
A. Overview of Symbols	143	(4)
B. Twofish Test Vectors	147	(10)
B.1 Intermediate Values	147	(5)
B.2 Full Encryptions	152	(5)
C. Code	157	(26)
C.1 C Code	157	(26)
Index	183