cracking Secrets of How federal Encryption Research agencies Wiretap Politics subuert & Chip Design priuacv e ELECTRONIC FRONTIER FOUNDATION Digitized by the Internet Archive 2013 in http://archive.org/details/crackingdessecreOOelec Cracking DES Cracking DES Secrets ofEncryption Research, Wiretap & Politics Chip Design Electronic Frontier Foundation CrackingDES: SecretsofEncryption Research, Wiretap Politics, andChipDesign by the Electronic Frontier Foundation With the exceptions noted, this book and all ofits contents are in the public domain. Published in 1998 by the Electronic Frontier Foundation. Printed in the United States of America. No rights reserved. Every part ofthis book, except as noted below, may be reproduced, in any form orby any means, without permission inwriting fromthe publisher. Because this material is in the public domain, permission to reproduce, use, copy, modify, and distribute this material for any purpose and without fee is hereby granted. Thetest-file, bootstrap, andbootstrap2 listings inChapter4 are Copyright © 1997 byNetwork Associates, Inc. These listings may be reproduced in whole or in part without payment of royalties. Chapter 10, Architectural Considerations for Cryptanalytic Hardware, is Copyright ©1996 bythe authors, Ian Goldberg and DavidWagner. Itmay notbe reproduced without the permission ofthe authors, who can be reached at [email protected] and [email protected]. Chapter 11, Efficient DES Key Search: An Update, is Copyright © 1997 by Entrust Technologies. It may be reproduced in whole or in part without payment of royalties. Chapter9, Breaking One Million DES Keys, is Copyright © 1986. Work done at the University ofLeuven, Belgium, and supported by the NFWO, Belgium. It may not be repro- duced without the permission ofthe author, who can be reached at [email protected]. Distributed by O'Reilly & Associates, Inc., 101 Morris Street, Sebastopol, CA 95472. PrintingHistory: May 1998: First Edition. Many ofthe designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear inthis book, and the publisherwas aware ofa trademark claim, the designations have been printed in caps or initial caps. While many precautions have been taken in the preparation ofthis book, the publisher and distributorassume no responsibilityforerrors oromissions, orfordamages resultingfromthe use ofthe information contained herein. Thisbookisprintedonacid-freepaperwith85%recycledcontent, 15%post-consumerwaste. O'Reilly&Associates is committedtousing paperwith the highestrecycled content available consistent with high quality. ISBN: 1-56592-520-3 [9/98] Table of Contents Foreword ix Preface xiii 1: Overview /-/ Politics ofDecryption 1-1 Goals 1-7 History ofDES Cracking 1-8 EFF's DES Cracker Project 1-8 Architecture 1-9 Who Else Is Cracking DES? 1-16 What To Do IfYou Depend On DES 1-17 Conclusion 1-18 2: DesignforDES Key SearchArray 2-1 On-Chip Registers 2-1 Commands 2-4 Search Unit Operation 2-4 Sample Programming Descriptions 2-5 Scalability and Performance 2-9 Host Computer Software 2-9 Glossary 2-10 vi TableofContents 3: DesignforDES Key Search Array Chip-Level Specification 3-1 ASIC Description 3-1 Board description 3-3 Read and Write Timing 3-5 Addressing Registers 3-7 All-active Signal 3-7 ASIC Register Allocation 3-8 4: Scanning the Source Code 4-1 The Politics of Cryptographic Source Code 4-1 The Paper Publishing Exception 4-2 Scanning 4-4 Bootstrapping 4-5 5: Software Source Code 5-1 6: Chip Source Code 6-1 7: Chip Simulator Source Code 7-1 8: Hardware Board Schematics 8-1 Board Schematics 8-1 Sun-4/470 backplane modifications 8-10 PC Interfaces 8-12 Errata 8-13 9: Breaking One Million DES Keys by Yvo Desmedt 9-1 Abstract 9-1 Introduction 9-1 The basic idea 9-2 Details of such a machine 9-2 Obtained results and remarks 9-4 Conclusion 9-4 Acknowledgement 9-5 TableofContents vii 10: Architectural Considerationsfor CryptanalyticHardware 10-1 .. Abstract 10-1 Introduction 10-1 Motivation 10-2 Related work 10-4 Technical Approach 10-6 Design and Analysis 10-8 Future work 10-23 Conclusions 10-23 Acknowledgements 10-24 Availability 10-24 References 10-24 — 11: EfficientDES Key Search An Update byMichael Wiener 11-1 J. Advancing Technology 11-2 Programmable Hardware 11-3 Conclusion 11-4 12: Authors 12-1 The Electronic Frontier Foundation 12-1 John Gilmore 12-2 Cryptography Research 12-2 Paul Kocher 12-3 Advanced Wireless Technologies 12-3