Add a doc on side channel countermeasures and known issues

[ci skip]

1 files changed, 351 insertions, 0 deletions

diff --git a/doc/side_channels.rst b/doc/side_channels.rst
new file mode 100644
index 000000000..9391accf3
--- /dev/null
+++ b/doc/side_channels.rst
@@ -0,0 +1,351 @@
+Side Channels
+=========================
+
+Many cryptographic systems can be broken by side channels. This document notes
+side channel protections which are currently implemented, as well as areas of
+the code which are known to be vulnerable to side channels. The latter are
+obviously all open for future improvement.
+
+The following text assumes the reader is already familiar with cryptographic
+implementations, side channel attacks, and common countermeasures.
+
+RSA
+----------------------
+
+Blinding is always used to protect private key operations (there is no way to
+turn it off). As an optimization, instead of choosing a new random mask and
+inverse with each decryption, both the mask and its inverse are simply squared
+to choose the next blinding factor. This is much faster than computing a fresh
+value each time, and the additional relation is thought to provide only minimal
+useful information for an attacker. Every BOTAN_BLINDING_REINIT_INTERVAL
+(default 32) operations, a new starting point is chosen.
+
+RSA signing uses the CRT optimization, which is much faster but vulnerable to
+trivial fault attacks [RsaFault] which can result in the key being entirely
+compromised. To protect against this (or any other computational error which
+would have the same effect as a fault attack in this case), after every private
+key operation the result is checked for consistency with the public key. This
+introduces only slight additional overhead and blocks most fault attacks; it is
+possible to use a second fault attack to bypass this check but
+
+See blinding.cpp and rsa.cpp for details.
+
+If the OpenSSL provider is enabled, then no explicit blinding is done; we assume
+OpenSSL handles this. See openssl_rsa.cpp for details.
+
+OAEP
+----------------------
+
+OAEP decoding is vulnerable to a side channel attack. If an attacker can
+determine where in the decoding process an error occurred, they can use this to
+decrypt arbitrary RSA ciphertexts. See [OaepTiming] for details. This is avoided
+in Botan by making the decoding operation const time. This is verified using
+valgrind. See eme_oaep.cpp for details.
+
+PKCS #1 v1.5 Decryption
+-------------------------
+
+This padding scheme is used with RSA, and is very vulnerable to errors. In an
+scenario where an attacker can repeatedly present RSA ciphertexts, and a
+legitimate key holder will attempt to decrypt each ciphertext and simply
+indicates to the attacker if the PKCS padding was valid or not (without
+revealing any additional information), the attacker can use this behavior as an
+oracle to perform iterative decryption of arbitrary RSA ciphertexts encrypted
+under that key. This is the famous million message attack [MillionMsg]. For
+example, simply a difference in timing between a valid and invalid RSA
+ciphertext due to an early error exit may be enough to mount an attack.
+
+Preventing this issue in full requires some application level changes. In
+protocols which know the expected length of the encrypted key, PK_Decryptor
+provides the function `decrypt_or_random` which first generates a random fake
+key, then decrypts the presented ciphertext, then in constant time either copies
+out the random key or the decrypted plaintext depending on if the ciphertext was
+valid or not. Then, the protocol can carry on with a randomly chosen key, which
+will presumably cause total failure in a way that does not allow an attacker to
+distinguish (via any timing or other side channel, nor any error messages
+specific to the one situation vs the other) if it was the RSA decryption
+
+One very important user of PKCS #1 v1.5 encryption is the TLS protocol. In TLS,
+some extra versioning information is embedded in the plaintext message, along
+with the key. It turns out that this version information must be treated in an
+identical (constant-time) way with the PKCS padding, or again the system is
+broken. [VersionOracle]. This is supported by a special version of
+PK_Decryptor::decrypt_or_random that additionally allows verifying one or more
+content bytes, in addition to the PKCS padding.
+
+See eme_pkcs.cpp and pubkey.cpp for details.
+
+Modular Exponentiation
+------------------------
+
+Modular exponentiation uses a fixed window algorithm with Montgomery representation.
+In the current code, information about the exponent is leaked through the
+sequence of memory indexes; we currently rely on randomized blinding at higher
+levels of the cryptographic stack to hide this. A future project would be to
+change this to use either Montgomery ladder or use a side channel silent table
+lookup. See powm_mnt.cpp for details.
+
+The Karatsuba multiplication algorithm has some conditional branches that
+probably expose information through the branch predictor, but probably? does not
+expose a timing channel since the same amount of work is done on both sides of
+the conditional. There is certainly room for improvement here. See mp_karat.cpp
+for details.
+
+The Montgomery reduction is written (and tested) to run in constant time. See
+mp_monty.cpp for details.
+
+ECC point decoding
+----------------------
+
+The API function OS2ECP, which is used to convert byte strings to ECC points,
+verifies that all points satisfy the ECC curve equation. Points that do not
+satisfy the equation are invalid, and can sometimes be used to break
+protocols. See point_gfp.cpp for details.
+
+ECC scalar multiply
+----------------------
+
+There are two implementations of scalar multiply, PointGFp::operator* and the
+class Blinded_Point_Multiply. The default scalar multiply uses the Montgomery
+ladder. However it currently leaks the size of the scalar, because the loop
+iterations are bounded by the scalar size.
+
+Blinded_Point_Multiply (used by ECDH, ECDSA, etc) applies several additional
+side channel countermeasures. The scalar is masked by a small multiple of the
+group order (this is commonly called Coron's first countermeasure [CoronDpa]),
+the size of the scalar mask is currently controlled by build.h value
+BOTAN_POINTGFP_SCALAR_BLINDING_BITS which defaults to 20 bits.
+
+Botan stores all ECC points in Jacobian representation. This form allows faster
+computation by representing points (x,y) as (X,Y,Z) where x=X/Z^2 and
+y=Y/Z^3. As the representation is redundant, for any randomly chosen r,
+(X*r^2,Y*r^3,Z*r) is an equivalent point. Changing the point values prevents an
+attacker from mounting attacks based on the input point remaining unchanged over
+multiple executions. This is commonly called Coron's third countermeasure, see
+again [CoronDpa].
+
+Currently Blinded_Point_Multiply uses one of two different algorithms, depending
+on a build-time flag. If BOTAN_POINTGFP_BLINDED_MULTIPLY_USE_MONTGOMERY_LADDER
+is set in build.h (default is for it *not* to be set), then a randomized
+Montgomery ladder algorithm from [RandomMonty] is used. Otherwise, a simple
+fixed window exponentiation is used; the current version leaks exponent bits
+through memory index values. We rely on scalar blinding to reduce this
+leakage. It would obviously be better for Blinded_Point_Multiply to converge on
+a single side channel silent algorithm.
+
+See point_gfp.cpp for details.
+
+ECDH
+----------------------
+
+ECDH verifies (through its use of OS2ECP) that all input points
+received from the other party satisfy the curve equation. This
+prevents twist attacks. The same check is performed on the output
+point, which helps prevent fault attacks.
+
+ECDSA
+----------------------
+
+Inversion of the ECDSA nonce k must be done in constant time, as any
+leak of even a single bit of the nonce can be sufficient to allow
+recovering the private key. In Botan all inverses modulo an odd number
+are performed using a constant time algorithm due to Niels Möller.
+
+x25519
+----------------------
+
+The x25519 code is independent of the main Weiserstrass form ECC code, instead
+based on curve25519-donna-c64.c by Adam Langley. The code seems immune to cache
+based side channels. It does make use of integer multiplications; on some old
+CPUs these multiplications take variable time and might allow a side channel
+attack. This is not considered a problem on modern processors.
+
+TLS CBC ciphersuites
+----------------------
+
+The original TLS v1.0 CBC Mac-then-Encrypt mode is vulnerable to an oracle
+attack.  If an attacker can distinguish padding errors through different error
+messages [TlsCbcOracle] or via a side channel attack like [Lucky13], they can
+abuse the server as a decryption oracle.
+
+The side channel protection for Lucky13 follows the approach proposed in the
+Lucky13 paper. It is not perfectly constant time, but does hide the padding
+oracle in practice. Tools to test TLS CBC decoding are included in the timing
+tests. See https://github.com/randombit/botan/pull/675 for more information.
+
+The Encrypt-then-MAC extension, which completely avoids the side channel, is
+implemented and used by default for CBC ciphersuites.
+
+CBC mode padding
+----------------------
+
+In theory, any good protocol protects CBC ciphertexts with a MAC. But in
+practice, some protocols are not good and cannot be fixed immediately. To avoid
+making a bad problem worse, the code to handle decoding CBC ciphertext padding
+bytes runs in constant time, depending only on the block size of the cipher.
+
+AES
+----------------------
+
+The basic implementation uses table lookup, an approach known to be very
+vulnerable to side channels. Modifications to the first and last round increase
+the cost of some known attacks (by reducing the number of cache lines accessed),
+but these truly can only slightly increase the samples required to recover the
+AES key.
+
+For x86 processors with SSSE3 extension (most CPUs since Atom, Core2 Duo, and
+AMD Bulldozer), there is an AES implementation which is included that is both
+faster than the table lookup code, and immune to cache-based side channel
+attacks as it does not perform any memory lookups using secret data.
+
+A version of AES which is side channel silent on x86 processors with SSSE3
+extension is included.  This instruction set is available on many older or low
+end x86 processors that do not have AES-NI (including old Atom, Core2 Duo, and
+AMD Bobcat). On most processors it is significantly faster than the table lookup
+version. It is based on a design by Mike Hamburg [VectorAes]. See aes_ssse3.cpp
+for the code. This same technique could be applied with NEON or AltiVec, and the
+paper has some optimizations for the AltiVec shuffle.
+
+On x86 processors which support it, AES-NI instruction set is used, as it is
+fast and (presumed) side channel silent. There is no support at the moment for
+the similar ARMv8 or POWER AES instructions; patches would be welcome.
+
+GCM
+---------------------
+
+On x86 platforms which support the clmul instruction, GCM support is fast and
+constant time.
+
+On all other platforms, GCM is slow and constant time. It uses a simple bit at
+at time loop. It would be much faster using a table lookup,
+
+OCB
+-----------------------
+
+It is straightforward to implement OCB mode in a efficient way that does not
+depend on any secret branches or lookups. See ocb.cpp for the implementation.
+
+Poly1305
+----------------------
+
+The Poly1305 implementation does not have any secret lookups or conditionals.
+The code is based on the public domain version by Andrew Moon.
+
+DES/3DES
+----------------------
+
+The DES implementation uses table lookups, and is likely vulnerable to side
+channel attacks. DES or 3DES should be avoided in new systems. The proper fix
+would be a scalar bitsliced implementation, this is not seen as worth the
+engineering investment given these algorithms end of life status.
+
+Twofish
+------------------------
+
+This algorithm uses table lookups with secret sboxes. No cache-based side
+channel attack on Twofish has ever been published, but it is possible nobody
+sufficiently skilled has ever tried.
+
+ChaCha20, Serpent, Threefish, ...
+-----------------------------------
+
+Some algorithms including ChaCha, Salsa, Serpent and Threefish are 'naturally'
+silent to cache and timing side channels on all recent processors.
+
+IDEA
+---------------
+
+IDEA encryption, decryption, and key schedule are implemented to take constant
+time regardless of their inputs.
+
+Hash Functions
+-------------------------
+
+Most hash functions included in Botan such as MD5, SHA-1, SHA-2, SHA-3, Skein,
+and BLAKE2 do not require any input-dependent memory lookups, and so seem to not be
+affected by common CPU side channels.
+
+Memory comparisons
+----------------------
+
+The function same_mem in header mem_ops.h provides a constant-time comparison
+function. It is used when comparing MACs or other secret values. It is also
+exposed for application use.
+
+Memory zeroizing
+----------------------
+
+There is no way in portable C/C++ to zero out an array before freeing it, in
+such a way that it is guaranteed that the compiler will not elide the
+'additional' (seemingly unnecessary) writes to zero out the memory.
+
+The function secure_scrub_memory (in mem_ops.cpp) uses some system specific
+trick to zero out an array. On Windows it uses the directly supported API
+function RtlSecureZeroMemory.
+
+On other platforms, by default the trick of referencing memset through a
+volatile function pointer is used. This approach is not guaranteed to work on
+all platforms, and currently there is no systematic check of the resulting
+binary function that it is compiled as expected. But, it is the best approach
+currently known and has been verified to work as expected on common platforms.
+
+If BOTAN_USE_VOLATILE_MEMSET_FOR_ZERO is set to 0 in build.h (not the default) a
+byte at a time loop through a volatile pointer is used to overwrite the array.
+
+Botan's secure_vector type is a std::vector with a custom allocator. The
+allocator simply calls secure_scrub_memory before freeing memory.
+
+Memory allocation
+----------------------
+
+Some systems including Linux and FreeBSD support applications pinning a small
+amount (typically 64 KB, sometimes more) of virtual memory pages in RAM, such
+that they will not be paged to disk. If available, Botan uses such a region for
+storing key material. It is created in anonymous mapped memory (not disk
+backed), locked in memory, and zeroized before freeing.
+
+This memory pool is used by secure_vector when available. It can be disabled by
+setting the environment variable BOTAN_MLOCK_POOL_SIZE to 0.
+
+Automated Analysis
+---------------------
+
+Currently the main tool used by the Botan developers for testing for side
+channels at runtime is valgrind; valgrind's runtime API is used to taint memory
+values, and any jumps or indexes using data derived from these values will cause
+a valgrind warning. This technique was first used by Adam Langley in ctgrind.
+See the header ct_utils.h for details.
+
+To check, install valgrind, configure the build with --with-valgrind, and run
+the tests.
+
+References
+---------------
+
+[CoronDpa] Coron,
+"Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems"
+(http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.5695)
+
+[Lucky13] AlFardan, Paterson "Lucky Thirteen: Breaking the TLS and DTLS Record Protocols"
+(http://www.isg.rhul.ac.uk/tls/TLStiming.pdf)
+
+[MillionMsg] Bleichenbacher "Chosen Ciphertext Attacks Against Protocols Based
+on the RSA Encryption Standard PKCS1"
+(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8543)
+
+[OaepTiming] Manger, "A Chosen Ciphertext Attack on RSA Optimal Asymmetric
+Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0"
+(http://archiv.infsec.ethz.ch/education/fs08/secsem/Manger01.pdf)
+
+[RsaFault] Boneh, Demillo, Lipton
+"On the importance of checking cryptographic protocols for faults"
+(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.9764)
+
+[RandomMonty] Le, Tan, Tunstall "Randomizing the Montgomery Powering Ladder"
+(https://eprint.iacr.org/2015/657)
+
+[VectorAes] Hamburg, "Accelerating AES with Vector Permute Instructions"
+https://shiftleft.org/papers/vector_aes/vector_aes.pdf
+
+[VersionOracle] Klíma, Pokorný, Rosa "Attacking RSA-based Sessions in SSL/TLS"
+(https://eprint.iacr.org/2003/052)