idnits 2.17.1 draft-ladd-sidechannel-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The "Author's Address" (or "Authors' Addresses") section title is misspelled. -- The document date (5 January 2014) is 3764 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'TBD' is defined on line 205, but no explicit reference was found in the text Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft W. Ladd 3 Grad Student 4 Category: Informational UC Berkeley 5 Expires 9 July 2014 5 January 2014 7 Side-channel considerations for cryptographic implementors. 8 10 Status of this Memo 12 Distribution of this memo is unlimited. 14 This Internet-Draft is submitted in full conformance with the 15 provisions of BCP 78 and BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on date. 35 Copyright Notice 37 Copyright (c) 2014 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. 47 Abstract 49 This Internet-Draft explains what side-channels are, how implementors 50 should avoid them, and how authors of standards should make it easy 51 for implementors to avoid them. 53 Table of Contents 55 1. Introduction ....................................................3 56 2. Side Channels ...................................................3 57 3. Countermeasures .................................................4 58 3. Security Considerations .........................................5 59 4. IANA Considerations .............................................5 60 5. References ......................................................5 62 1. Introduction 64 This document attempts to summarize the methods currently in use and 65 recommended for avoiding side channel attacks in software that 66 implements cryptographic standards, as well as what the authors of 67 standards should do to make this possible. 69 2. Side Channels 71 When cryptographers design a cryptographic scheme, they analyze it 72 assuming that the only information an adversary has is that 73 transmitted over the mediums assummed to be open to manipulation. 74 However, this assumption is not necessarily true. 76 An attacker can determine the time it takes to evaluate a 77 cryptographic primative, as well as the pattern of memory accesses 78 involved in the evaluation if they have access to a process on the 79 same CPU. Timing differences can be monitored across several LAN 80 links without great difficulty. 82 Attackers can also listen to a computer. All switching power supplies 83 contain magnetic components, which change shape slightly as current 84 goes through them. The result is a barely (or easily!) audible noise 85 correlated with the power consumption of the CPU over longish 86 periods, and hence with the code that is running. 88 In certain scenarios the power generated by individual operations can 89 be effectively measured. This is a very difficult setting to work in, 90 and will not be considered further in this document. But if someone 91 leaves a multimeter in your machine room, watch out! 93 Standard algorithms for evaluating modular exponentiations, the AES, 94 point powers on elliptic curves, modular additions, and reduction 95 modulo a number are not designed to avoid leaking this information. 96 Some CPUs take variable time for certain arithmetic instructions, and 97 nearly all modern CPUs will take longer to retrive cold memory then 98 hot memory. 100 The standard multiply and square algorithm for instance, leaks the 101 Hamming weight of the exponent: it is equal to the number of extra 102 multiplications required, and these can roughly be assumed to take an 103 equal and known amount of time. If this is not the case the adversary 104 can average over multiple bases, and determine the most likely 105 Hamming weight of the exponent. 107 When the Hamming wieght is known, a modified Baby-step Giant-step 108 algorithm achieves large speedups over naive attacks. The security of 109 the scheme is thus substantially weakened by the addition of very 110 little extra information. 112 Related attacks are known against RSA, AES, elliptic curves, ECDSA 113 and DSA. For those primatives with no such side-channel attack known, 114 this is likely due to no-one bothering to look, rather than an 115 absence of such attacks. 117 Above the layer of the primative some impelmentations of the TLS 118 1.0/1.1/1.2 took slightly less time to verify padding than they did 119 for a MAC. The result was the Lucky 13 attack, which resulted in 120 several changes to the standard 13 years after the possibility of 121 such issues was noted. OAEP padding for RSA has a similar issue: 122 naive implementations reveal which of two checks failed, information 123 which enables an attacker to decrypt arbitrary ciphertexts. 125 3. Countermeasures 127 The best countermeasure is code that runs in constant time with a 128 constant pattern of memory access and no data-dependent jumps. The 129 second best countermeasure is to "blind" critical operations: in RSA 130 rather than calculate M^(d) mod N to decrypt, one computes R^e (mod 131 N) for random R and then calculates (R^eM)^d=RM mod N. This 132 calculation permits a variable time mod-N reduction to be used, 133 without leaking information about the values of temporary variables. 135 Writing such code can be difficult: for the AES the best such code 136 uses bitslicing techniques and is suitable primarily for counter 137 mode. Implementing the GCM mode involves multiplications over 138 GF(2^256), a field which most CPUs have trouble working over. Some 139 Intel chips have characteristic 2 multipliers, as well as built in 140 AES instructions, making this taks sigificantly easier. There is an 141 implementation freely available in hand-written assembler that solves 142 this thorny problem. 144 As a result specifications would ideally specify constructions for 145 which efficient constant-time, constant-memory access, constant- 146 instruction-flow, code exists. For the rest of this section we will 147 refer to that code as circuit code, given the similarity to 148 arithmetic circuits. 150 For elliptic curves over nicely shaped primes the arithmetic over the 151 prime is easily executed by circuit code. The issue is the algorithm 152 for addition on the curve. Brie-Joyce ladders are a potential 153 solution for short Weierstrauss curves, but the Montgomery ladder on 154 Montgomery curves performs better when only the x coordinate is 155 needed. Alternatively one uses a standard radix-k multiplication, but 156 to load an entry from the table one reads through the entire table, 157 using the following conditional load code: 159 c=c*bit+a*(1-bit) 161 or some varation thereof. Freely usable implementations taking these 162 precautions exist for P224, P256, Curve25519, Curve3617, and some 163 GLS/GLV curves with endomorphisms. Modular inverses should always be 164 computed through exponentiation: if this is not possible the binary 165 Euclidean algorithm should be run for a constant number of steps, 166 calculated as the number for the worst case. (For reference, the 167 worst case is two consecutive Fibonacci numbers) 169 Many libraries for number theoretic calculations do not take these 170 precautions as they are designed for speed over all else. When using 171 a library, determine if it takes these precautions, and if not do not 172 use it for cryptographic code. 174 Modern hash functions, including the SHA-3 have been designed to 175 avoid these problems. Salsa20 and Poly1305 are a stream cipher and 176 MAC designed to be easy to implement in a side-channel aware manner. 178 Protocol designers should take care that if multiple conditions could 179 lead to failure of a necessary validation that the consequences of 180 leaking which condition occurred are not disasterous. 182 Strings should not be compared with strlcmp, memcmp, or any other 183 such function which reveals the position of the first difference 184 between the two strings. Constant time versions are easy to write and 185 use, and should be used instead. Strlcmp also has the issue of ending 186 comparison at the first null, contrary to the definition of string as 187 a sequence of all bytes in cryptography. This has enabled homebrew 188 games to be run on the Nintendo Wii. 190 Adding random delays is not a suitable countermeasure: it simply 191 requires the attacker to average timing differences over a large 192 number of measurements to recover the same signal. 194 3. Security Considerations 196 This entire document discusses methods of implementing cryptography 197 securely. 199 4. IANA Considerations 201 No IANA action is required. 203 5. References 205 [TBD] 207 Author Addresses 208 Watson Ladd 209 watsonbladd@gmail.com 210 Berkeley, CA