Internet DRAFT - draft-ladd-sidechannel

draft-ladd-sidechannel



 



Internet Draft                                                   W. Ladd
<draft-ladd-sidechannel-00.txt>                             Grad Student
Category: Informational                                      UC Berkeley
Expires 9 July 2014                                        5 January 2014

      Side-channel considerations for cryptographic implementors.
                    <draft-ladd-sidechannel-00.txt>

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]