Understanding Security APIs Michael K. Bond University of Cambridge Computer Laboratory Emmanuel College Jan 2004 This dissertation is submitted for the degree of Doctor of Philosophy Declaration This dissertation is the result of my own work and includes nothing which is the outcome of work done in collaboration except where speci(cid:12)cally indicated in the text. This dissertation does not exceed the regulation length of 60000 words, including tables and footnotes. 2 Dedication To Philip Barnes, who could have stopped me exercising my talent at breaking things, but didn’t; and to Clive Spencer-Bentley, who changed my life both in presence and absence. 3 4 Acknowledgements I am indebted to a whole host of people who have inspired, conspired, cooperated, and supported me and this research since it all started back in 2000. First, I want to thank my supervisor Ross Anderson who started it all, spotted the signi(cid:12)cance of the results I was getting, and has backed me up at every twist and turn of my journey. Many thanks are also due to Larry Paulson who supervised me for the (cid:12)rst year and a half, and lent a balance and perspective to the work which was invaluable when I was immersed in the technical details of a problem. I would like to thank my comrades from TG1 { George (\What are we going to do today George? Same thing do we do every day Mike { try to take over the world!"), Richard, and Markus: countless conversations, remonstrations, arguments, andeven sword-(cid:12)ghts have helped me settle the truths of this topic. In more recent times Steven, Stephen, Piotr, Andrei and Sergei have all lent their advice, skills and senses of humour to aid my work. Outinthebigwideworldofindustry, specialthanksgotoNickoVanSomeren, Peter Landrock and Leendert Van Doorn, who have all been very generous to me. Ernie Cohen gave me some useful pointers and feedback on my crude e(cid:11)orts in formal analysis. Particular thanks in recent times are also due to Todd Arnold and Dave Ritten. I must thank my mysterious and generally invisible funding bodies, the EPSRC and Marconi { I hope the discoveries in this thesis return at least some of the investment you have made in me. I should also thank my former director of studies, Neil Dodgson, for (presumably) not writing a damning reference for me just after discovering about the ‘vodka in exam’ incident! In my personal struggle to survive this Ph.D. experience I am lost for superlatives to describe the unshaking support I’ve had from Marianne and from my family. My father in particular put up the money until my funding came through, and has read or heard about (and completely understood) every idea as it arrived hot o(cid:11) the press. Thanks also to numerous friends who have watched with interest and kept me sane: Martin, Mary, Matt, Joe, Steve to mention but a few. A special thank you to Sheila, who I swear is more interested in my work than I am, and who has been a continual source of support and a great friend. Finally I must thank Jol { I might have quit academic Security API research had the size of the research community in this (cid:12)eld not suddenly doubled. Onwards to the future! 5 Understanding Security APIs Michael K. Bond Summary This thesis introduces the newly-born (cid:12)eld of Security API research, and lays the foundations for future analysis, study, and construction of APIs. Security APIs are application programmer interfaces which use cryptography to enforce a security policy on the users of the API, governing the way in which they manipulate sensitive data and key material. The thesis begins by examining the origins and history of Security APIs, and that of Hardware Security Modules { tamper-resistant cryptographic processors which implement the APIs, the study of which goes hand-in-hand with this research. The major manufacturers and their products are covered, and commentaries draw to- gether a few of the more important themes that explain why Security APIs are the way they are today. The signi(cid:12)cant original contribution at the heart of the thesis is a catalogue of new attacks and attack techniques for Security APIs. These attacks have had substan- tial impact on the Security API design community since their original publication. For example, the related-key \meet-in-the-middle" attack compromised every HSM analysed, and di(cid:11)erential protocol analysis compromised all (cid:12)nancial Security APIs. Historic attacks and brief explanations of very new unpublished attacks are also included. The thesis goes on to provide a body of advice for Security API design, consisting of heuristics and discussions of key issues, including those most pertinent to modern HSMs such as authorisation and trusted paths. The advice is linked in with the cautionary tales of Security API failures from the previous chapters. As the thesis is opening a new (cid:12)eld of academic research, its main objective is to buildunderstanding aboutSecurityAPIs, andtheconclusionsdrawnareopen-ended and speculative. The di(cid:11)erent driving forces shaping the development of Security APIs are considered, and Trusted Computing is identi(cid:12)ed as central to the shaping of Security APIs and to the future relevance of this thesis. 6 Contents 1 Introduction 12 1.1 How to Read this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2 Schedule of Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Origins of Security APIs 17 2.1 Beginnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 The ‘Killer App’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 The Present . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Key Dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Origins of Security API Attacks 21 3.1 Early Security API Failures . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 A Second Look at the Visa Security Module . . . . . . . . . . . . . . 22 3.2.1 XOR to Null Key Attack . . . . . . . . . . . . . . . . . . . . . 23 3.2.2 Type System Attack . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Development of the Attack Toolkit . . . . . . . . . . . . . . . . . . . 26 3.3.1 Meet-in-the-Middle Attack . . . . . . . . . . . . . . . . . . . . 26 3.3.2 3DES Key Binding Attack . . . . . . . . . . . . . . . . . . . . 27 3.3.3 Decimalisation Table Attack . . . . . . . . . . . . . . . . . . . 28 3.4 Attacks on Modern APIs . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 Applications of Security APIs 30 4.1 Automated Teller Machine Security . . . . . . . . . . . . . . . . . . . 30 4.1.1 Targets of Attack . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1.2 Threat Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Electronic Payment Schemes . . . . . . . . . . . . . . . . . . . . . . . 33 7 4.3 Certi(cid:12)cation Authorities . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3.1 Public Key Infrastructures . . . . . . . . . . . . . . . . . . . . 34 4.3.2 Threat Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.4 Prepayment Electricity Meters . . . . . . . . . . . . . . . . . . . . . . 37 4.5 SSL Security and Acceleration . . . . . . . . . . . . . . . . . . . . . . 38 4.6 Digital Rights Management . . . . . . . . . . . . . . . . . . . . . . . 38 4.7 Military Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.8 Specialist Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 The Security API Industry 42 5.1 People and Organisations using Security APIs . . . . . . . . . . . . . 42 5.2 Corporate Timeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2.1 1970 to 1990 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2.2 1990 to 2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2.3 2000 to Present . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.3 Summary of HSM Manufacturers . . . . . . . . . . . . . . . . . . . . 48 5.3.1 IBM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3.2 Thales / Zaxus / Racal . . . . . . . . . . . . . . . . . . . . . . 48 5.3.3 nCipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3.4 HP Atalla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.3.5 Chrysalis-ITS . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.3.6 Prism Payment Technologies . . . . . . . . . . . . . . . . . . . 51 5.3.7 Eracom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3.8 Baltimore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.3.9 Jones-Futurex . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.3.10 Other Security API Vendors . . . . . . . . . . . . . . . . . . . 52 5.3.11 Odds and Ends . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.4 Interacting with Vendors . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.4.1 Buying from Vendors . . . . . . . . . . . . . . . . . . . . . . . 54 5.4.2 Reporting Faults to Vendors . . . . . . . . . . . . . . . . . . . 56 8 6 Hardware Security Modules 58 6.1 A Brief History of HSMs . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.2 Physical Tamper-resistance . . . . . . . . . . . . . . . . . . . . . . . . 61 6.2.1 Tamper-Evidence . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.3 HSM Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.3.1 IBM 4758-001 . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.3.2 IBM 4758-002 . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.3.3 nCipher nForce . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6.3.4 nCipher nShield . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.3.5 nCipher netHSM . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.3.6 Prism TSM200 . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.3.7 Thales RG7000 . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.3.8 Atalla NSP10000 . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.3.9 Chrysalis-ITS Luna CA3 . . . . . . . . . . . . . . . . . . . . . 76 6.3.10 Visa Security Module . . . . . . . . . . . . . . . . . . . . . . . 77 7 Analysis of Security APIs 78 7.1 Abstractions of Security APIs . . . . . . . . . . . . . . . . . . . . . . 78 7.1.1 Describing API Commands with Protocol Notation . . . . . . 78 7.1.2 Key Typing Systems . . . . . . . . . . . . . . . . . . . . . . . 81 7.1.3 Key Hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7.1.4 Monotonicity and Security APIs . . . . . . . . . . . . . . . . . 84 7.2 The Attacker’s Toolkit . . . . . . . . . . . . . . . . . . . . . . . . . . 86 7.2.1 Unauthorised Type-casting . . . . . . . . . . . . . . . . . . . . 86 7.2.2 The Meet-in-the-Middle Attack . . . . . . . . . . . . . . . . . 86 7.2.3 Key Conjuring . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.2.4 Related Key Attacks . . . . . . . . . . . . . . . . . . . . . . . 88 7.2.5 Poor Key-half Binding . . . . . . . . . . . . . . . . . . . . . . 89 7.2.6 Di(cid:11)erential Protocol Analysis . . . . . . . . . . . . . . . . . . 89 7.2.7 Timing Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.2.8 Check Value Attacks . . . . . . . . . . . . . . . . . . . . . . . 92 7.3 An Abundance of Attacks . . . . . . . . . . . . . . . . . . . . . . . . 93 9 7.3.1 VSM Compatibles { XOR to Null Key Attack . . . . . . . . . 93 7.3.2 VSM Compatibles { A Key Separation Attack . . . . . . . . . 94 7.3.3 VSM Compatibles { Meet-in-the-Middle Attack . . . . . . . . 95 7.3.4 4758 CCA { Key Import Attack . . . . . . . . . . . . . . . . . 96 7.3.5 4758 CCA { Import/Export Loop Attack . . . . . . . . . . . . 97 7.3.6 4758 CCA { 3DES Key Binding Attack . . . . . . . . . . . . . 98 7.3.7 4758 CCA { Key Part Import Descrack Attack . . . . . . . . 99 7.3.8 4758 CCA { Weak Key Timing Attack . . . . . . . . . . . . . 106 7.3.9 4758 CCA { Check Value Attack . . . . . . . . . . . . . . . . 106 7.3.10 VSM Compatibles { Decimalisation Table Attack . . . . . . . 107 7.3.11 Prism TSM200 { Master Key Attack . . . . . . . . . . . . . . 114 7.3.12 Other Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.4 Formal Analysis of Security APIs . . . . . . . . . . . . . . . . . . . . 119 7.4.1 Foundations of Formal Analysis . . . . . . . . . . . . . . . . . 119 7.4.2 Tools Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.4.3 Case Study: SPASS . . . . . . . . . . . . . . . . . . . . . . . . 122 7.4.4 MIMsearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8 Designing Security APIs 133 8.1 Can Security APIs Solve Your Problem? . . . . . . . . . . . . . . . . 133 8.2 Design Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 8.2.1 General Heuristics . . . . . . . . . . . . . . . . . . . . . . . . 135 8.2.2 Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8.2.3 Transaction Design . . . . . . . . . . . . . . . . . . . . . . . . 138 8.2.4 Type System Design . . . . . . . . . . . . . . . . . . . . . . . 139 8.2.5 Legacy Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 8.3 Access Control and Trusted Paths . . . . . . . . . . . . . . . . . . . . 141 8.3.1 How much should we trust the host? . . . . . . . . . . . . . . 142 8.3.2 Communicating: Key Material . . . . . . . . . . . . . . . . . . 143 8.3.3 Communicating: Authorisation Information . . . . . . . . . . 144 8.3.4 Providing Feedback: Display Information . . . . . . . . . . . . 148 8.3.5 Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . 149 10