Update side channel doc

1 files changed, 34 insertions, 30 deletions

diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index 32be498e7..8f8067004 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -9,6 +9,34 @@ obviously all open for future improvement.
 The following text assumes the reader is already familiar with cryptographic
 implementations, side channel attacks, and common countermeasures.
 
+Modular Exponentiation
+------------------------
+
+Modular exponentiation uses a fixed window algorithm with Montgomery
+representation. A side channel silent table lookup is used to access the
+precomputed powers. The caller provides the maximum possible bit length of the
+exponent, and the exponent is zero-padded as required. For example, in a DSA
+signature with 256-bit q, the caller will specify a maximum length of exponent
+of 256 bits, even if the k that was generated was 250 bits. This avoids leaking
+the length of the exponent through the number of loop iterations.
+See monty_exp.cpp and monty.cpp
+
+Karatsuba multiplication algorithm avoids any conditional branches; in
+cases where different operations must be performed it instead uses masked
+operations. See mp_karat.cpp for details.
+
+The Montgomery reduction is written to run in constant time.
+The final reduction is handled with a masked subtraction. See mp_monty.cpp.
+
+Barrett Reduction
+--------------------
+
+The Barrett reduction code is written to avoid input dependent branches. The
+Barrett algorithm only works for inputs that are most the square of the modulus;
+larger values fall back on a different (slower) division algorithm. This
+algorithm is also const time, but the branch allows detecting when a value
+larger than the square of the modulus was reduced.
+
 RSA
 ----------------------
 
@@ -105,33 +133,6 @@ coming from the length of the RSA key (which is public information).
 
 See eme_oaep.cpp.
 
-Modular Exponentiation
-------------------------
-
-Modular exponentiation uses a fixed window algorithm with Montgomery
-representation. A side channel silent table lookup is used to access the
-precomputed powers. The caller provides the maximum possible bit length of the
-exponent, and the exponent is zero-padded as required. For example, in a DSA
-signature with 256-bit q, the caller will specify a maximum length of exponent
-of 256 bits, even if the k that was generated was 250 bits. This avoids leaking
-the length of the exponent through the number of loop iterations.
-See monty_exp.cpp and monty.cpp
-
-Karatsuba multiplication algorithm avoids any conditional branches; in
-cases where different operations must be performed it instead uses masked
-operations. See mp_karat.cpp for details.
-
-The Montgomery reduction is written (and tested) to run in constant time.
-The final reduction is handled with a masked subtraction. See mp_monty.cpp.
-
-Barrett Reduction
---------------------
-
-The Barrett reduction code is written to avoid input dependent branches.
-However the Barrett algorithm only works for inputs that are most the
-square of the modulus; larger values fall back to the schoolbook
-division algorithm which is not const time.
-
 ECC point decoding
 ----------------------
 
@@ -170,9 +171,12 @@ The base point multiplication algorithm is a comb-like technique which
 precomputes ``P^i,(2*P)^i,(3*P)^i`` for all ``i`` in the range of valid scalars.
 This means the scalar multiplication involves only point additions and no
 doublings, which may help against attacks which rely on distinguishing between
-point doublings and point additions. The elements of the table are accessed
-by masked lookups, so as not to leak information about bits of the scalar
-via a cache side channel.
+point doublings and point additions. The elements of the table are accessed by
+masked lookups, so as not to leak information about bits of the scalar via a
+cache side channel. However, whenever 3 sequential bits of the scalar are all 0,
+no operation is performed in that iteration of the loop. This exposes the scalar
+multiply to a cache-based side channel attack; scalar blinding is necessary to
+prevent this attack from leaking information about the scalar.
 
 The variable point multiplication algorithm uses a fixed-window algorithm. Since
 this is normally invoked using untrusted points (eg during ECDH key exchange) it