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]