Internet Draft W. Ladd Grad Student Category: Informational UC Berkeley Expires 9 July 2014 5 January 2014 Side-channel considerations for cryptographic implementors. Status of this Memo Distribution of this memo is unlimited. This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on date. Copyright Notice Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract This Internet-Draft explains what side-channels are, how implementors Ladd, Watson Expires 9 July 2014 [Page 1] Internet Draft ladd-sidechannel 5 January 2014 should avoid them, and how authors of standards should make it easy for implementors to avoid them. Ladd, Watson Expires 9 July 2014 [Page 2] Internet Draft ladd-sidechannel 5 January 2014 Table of Contents 1. Introduction ....................................................3 2. Side Channels ...................................................3 3. Countermeasures .................................................4 3. Security Considerations .........................................5 4. IANA Considerations .............................................5 5. References ......................................................5 1. Introduction This document attempts to summarize the methods currently in use and recommended for avoiding side channel attacks in software that implements cryptographic standards, as well as what the authors of standards should do to make this possible. 2. Side Channels When cryptographers design a cryptographic scheme, they analyze it assuming that the only information an adversary has is that transmitted over the mediums assummed to be open to manipulation. However, this assumption is not necessarily true. An attacker can determine the time it takes to evaluate a cryptographic primative, as well as the pattern of memory accesses involved in the evaluation if they have access to a process on the same CPU. Timing differences can be monitored across several LAN links without great difficulty. Attackers can also listen to a computer. All switching power supplies contain magnetic components, which change shape slightly as current goes through them. The result is a barely (or easily!) audible noise correlated with the power consumption of the CPU over longish periods, and hence with the code that is running. In certain scenarios the power generated by individual operations can be effectively measured. This is a very difficult setting to work in, and will not be considered further in this document. But if someone leaves a multimeter in your machine room, watch out! Standard algorithms for evaluating modular exponentiations, the AES, point powers on elliptic curves, modular additions, and reduction modulo a number are not designed to avoid leaking this information. Some CPUs take variable time for certain arithmetic instructions, and nearly all modern CPUs will take longer to retrive cold memory then hot memory. The standard multiply and square algorithm for instance, leaks the Ladd, Watson Expires 9 July 2014 [Page 3] Internet Draft ladd-sidechannel 5 January 2014 Hamming weight of the exponent: it is equal to the number of extra multiplications required, and these can roughly be assumed to take an equal and known amount of time. If this is not the case the adversary can average over multiple bases, and determine the most likely Hamming weight of the exponent. When the Hamming wieght is known, a modified Baby-step Giant-step algorithm achieves large speedups over naive attacks. The security of the scheme is thus substantially weakened by the addition of very little extra information. Related attacks are known against RSA, AES, elliptic curves, ECDSA and DSA. For those primatives with no such side-channel attack known, this is likely due to no-one bothering to look, rather than an absence of such attacks. Above the layer of the primative some impelmentations of the TLS 1.0/1.1/1.2 took slightly less time to verify padding than they did for a MAC. The result was the Lucky 13 attack, which resulted in several changes to the standard 13 years after the possibility of such issues was noted. OAEP padding for RSA has a similar issue: naive implementations reveal which of two checks failed, information which enables an attacker to decrypt arbitrary ciphertexts. 3. Countermeasures The best countermeasure is code that runs in constant time with a constant pattern of memory access and no data-dependent jumps. The second best countermeasure is to "blind" critical operations: in RSA rather than calculate M^(d) mod N to decrypt, one computes R^e (mod N) for random R and then calculates (R^eM)^d=RM mod N. This calculation permits a variable time mod-N reduction to be used, without leaking information about the values of temporary variables. Writing such code can be difficult: for the AES the best such code uses bitslicing techniques and is suitable primarily for counter mode. Implementing the GCM mode involves multiplications over GF(2^256), a field which most CPUs have trouble working over. Some Intel chips have characteristic 2 multipliers, as well as built in AES instructions, making this taks sigificantly easier. There is an implementation freely available in hand-written assembler that solves this thorny problem. As a result specifications would ideally specify constructions for which efficient constant-time, constant-memory access, constant- instruction-flow, code exists. For the rest of this section we will refer to that code as circuit code, given the similarity to arithmetic circuits. Ladd, Watson Expires 9 July 2014 [Page 4] Internet Draft ladd-sidechannel 5 January 2014 For elliptic curves over nicely shaped primes the arithmetic over the prime is easily executed by circuit code. The issue is the algorithm for addition on the curve. Brie-Joyce ladders are a potential solution for short Weierstrauss curves, but the Montgomery ladder on Montgomery curves performs better when only the x coordinate is needed. Alternatively one uses a standard radix-k multiplication, but to load an entry from the table one reads through the entire table, using the following conditional load code: c=c*bit+a*(1-bit) or some varation thereof. Freely usable implementations taking these precautions exist for P224, P256, Curve25519, Curve3617, and some GLS/GLV curves with endomorphisms. Modular inverses should always be computed through exponentiation: if this is not possible the binary Euclidean algorithm should be run for a constant number of steps, calculated as the number for the worst case. (For reference, the worst case is two consecutive Fibonacci numbers) Many libraries for number theoretic calculations do not take these precautions as they are designed for speed over all else. When using a library, determine if it takes these precautions, and if not do not use it for cryptographic code. Modern hash functions, including the SHA-3 have been designed to avoid these problems. Salsa20 and Poly1305 are a stream cipher and MAC designed to be easy to implement in a side-channel aware manner. Protocol designers should take care that if multiple conditions could lead to failure of a necessary validation that the consequences of leaking which condition occurred are not disasterous. Strings should not be compared with strlcmp, memcmp, or any other such function which reveals the position of the first difference between the two strings. Constant time versions are easy to write and use, and should be used instead. Strlcmp also has the issue of ending comparison at the first null, contrary to the definition of string as a sequence of all bytes in cryptography. This has enabled homebrew games to be run on the Nintendo Wii. Adding random delays is not a suitable countermeasure: it simply requires the attacker to average timing differences over a large number of measurements to recover the same signal. 3. Security Considerations This entire document discusses methods of implementing cryptography securely. Ladd, Watson Expires 9 July 2014 [Page 5] Internet Draft ladd-sidechannel 5 January 2014 4. IANA Considerations No IANA action is required. 5. References [TBD] Author Addresses Watson Ladd watsonbladd@gmail.com Berkeley, CA Ladd, Watson Expires 9 July 2014 [Page 6]