library/constant_time_internal.h

/**
 *  Constant-time functions
 *
 *  Copyright The Mbed TLS Contributors
 *  SPDX-License-Identifier: Apache-2.0
 *
 *  Licensed under the Apache License, Version 2.0 (the "License"); you may
 *  not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *  http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

#ifndef MBEDTLS_CONSTANT_TIME_INTERNAL_H
#define MBEDTLS_CONSTANT_TIME_INTERNAL_H

#include <stdint.h>
#include <stddef.h>

#include "common.h"

#if defined(MBEDTLS_BIGNUM_C)
#include "mbedtls/bignum.h"
#endif

#if defined(MBEDTLS_SSL_TLS_C)
#include "ssl_misc.h"
#endif


/** Turn a value into a mask:
 * - if \p value == 0, return the all-bits 0 mask, aka 0
 * - otherwise, return the all-bits 1 mask, aka (unsigned) -1
 *
 * This function can be used to write constant-time code by replacing branches
 * with bit operations using masks.
 *
 * \param value     The value to analyze.
 *
 * \return          Zero if \p value is zero, otherwise all-bits-one.
 */
unsigned mbedtls_ct_uint_mask(unsigned value);

#if defined(MBEDTLS_SSL_SOME_SUITES_USE_MAC)

/** Turn a value into a mask:
 * - if \p value == 0, return the all-bits 0 mask, aka 0
 * - otherwise, return the all-bits 1 mask, aka (size_t) -1
 *
 * This function can be used to write constant-time code by replacing branches
 * with bit operations using masks.
 *
 * \param value     The value to analyze.
 *
 * \return          Zero if \p value is zero, otherwise all-bits-one.
 */
size_t mbedtls_ct_size_mask(size_t value);

#endif /* MBEDTLS_SSL_SOME_SUITES_USE_MAC */

#if defined(MBEDTLS_BIGNUM_C)

/** Turn a value into a mask:
 * - if \p value == 0, return the all-bits 0 mask, aka 0
 * - otherwise, return the all-bits 1 mask, aka (mbedtls_mpi_uint) -1
 *
 * This function can be used to write constant-time code by replacing branches
 * with bit operations using masks.
 *
 * \param value     The value to analyze.
 *
 * \return          Zero if \p value is zero, otherwise all-bits-one.
 */
mbedtls_mpi_uint mbedtls_ct_mpi_uint_mask(mbedtls_mpi_uint value);

#endif /* MBEDTLS_BIGNUM_C */

#if defined(MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC)

/** Constant-flow mask generation for "greater or equal" comparison:
 * - if \p x >= \p y, return all-bits 1, that is (size_t) -1
 * - otherwise, return all bits 0, that is 0
 *
 * This function can be used to write constant-time code by replacing branches
 * with bit operations using masks.
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      All-bits-one if \p x is greater or equal than \p y,
 *              otherwise zero.
 */
size_t mbedtls_ct_size_mask_ge(size_t x,
                               size_t y);

#endif /* MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC */

/** Constant-flow boolean "equal" comparison:
 * return x == y
 *
 * This is equivalent to \p x == \p y, but is likely to be compiled
 * to code using bitwise operation rather than a branch.
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      1 if \p x equals to \p y, otherwise 0.
 */
unsigned mbedtls_ct_size_bool_eq(size_t x,
                                 size_t y);

#if defined(MBEDTLS_BIGNUM_C)

/** Decide if an integer is less than the other, without branches.
 *
 * This is equivalent to \p x < \p y, but is likely to be compiled
 * to code using bitwise operation rather than a branch.
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      1 if \p x is less than \p y, otherwise 0.
 */
unsigned mbedtls_ct_mpi_uint_lt(const mbedtls_mpi_uint x,
                                const mbedtls_mpi_uint y);

#endif /* MBEDTLS_BIGNUM_C */

/** Choose between two integer values without branches.
 *
 * This is equivalent to `condition ? if1 : if0`, but is likely to be compiled
 * to code using bitwise operation rather than a branch.
 *
 * \param condition     Condition to test.
 * \param if1           Value to use if \p condition is nonzero.
 * \param if0           Value to use if \p condition is zero.
 *
 * \return  \c if1 if \p condition is nonzero, otherwise \c if0.
 */
unsigned mbedtls_ct_uint_if(unsigned condition,
                            unsigned if1,
                            unsigned if0);

#if defined(MBEDTLS_SSL_SOME_SUITES_USE_MAC)

/** Conditional memcpy without branches.
 *
 * This is equivalent to `if ( c1 == c2 ) memcpy(dest, src, len)`, but is likely
 * to be compiled to code using bitwise operation rather than a branch.
 *
 * \param dest      The pointer to conditionally copy to.
 * \param src       The pointer to copy from. Shouldn't overlap with \p dest.
 * \param len       The number of bytes to copy.
 * \param c1        The first value to analyze in the condition.
 * \param c2        The second value to analyze in the condition.
 */
void mbedtls_ct_memcpy_if_eq(unsigned char *dest,
                             const unsigned char *src,
                             size_t len,
                             size_t c1, size_t c2);

/** Copy data from a secret position with constant flow.
 *
 * This function copies \p len bytes from \p src_base + \p offset_secret to \p
 * dst, with a code flow and memory access pattern that does not depend on \p
 * offset_secret, but only on \p offset_min, \p offset_max and \p len.
 * Functionally equivalent to `memcpy(dst, src + offset_secret, len)`.
 *
 * \note                This function reads from \p dest, but the value that
 *                      is read does not influence the result and this
 *                      function's behavior is well-defined regardless of the
 *                      contents of the buffers. This may result in false
 *                      positives from static or dynamic analyzers, especially
 *                      if \p dest is not initialized.
 *
 * \param dest          The destination buffer. This must point to a writable
 *                      buffer of at least \p len bytes.
 * \param src           The base of the source buffer. This must point to a
 *                      readable buffer of at least \p offset_max + \p len
 *                      bytes. Shouldn't overlap with \p dest.
 * \param offset        The offset in the source buffer from which to copy.
 *                      This must be no less than \p offset_min and no greater
 *                      than \p offset_max.
 * \param offset_min    The minimal value of \p offset.
 * \param offset_max    The maximal value of \p offset.
 * \param len           The number of bytes to copy.
 */
void mbedtls_ct_memcpy_offset(unsigned char *dest,
                              const unsigned char *src,
                              size_t offset,
                              size_t offset_min,
                              size_t offset_max,
                              size_t len);

#endif /* MBEDTLS_SSL_SOME_SUITES_USE_MAC */

#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)

/** Constant-flow "greater than" comparison:
 * return x > y
 *
 * This is equivalent to \p x > \p y, but is likely to be compiled
 * to code using bitwise operation rather than a branch.
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      1 if \p x greater than \p y, otherwise 0.
 */
unsigned mbedtls_ct_size_gt(size_t x, size_t y);

#endif /* defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT) */



/* The constant-time interface provides various operations that are likely
 * to result in constant-time code that does not branch or use conditional
 * instructions for secret data (for secret pointers, this also applies to
 * the data pointed to).
 *
 * It has three main parts:
 *
 * - boolean operations (and a few non-boolean operations)
 *   These are all named mbedtls_ct_bool_<operation>, and operate over
 *   mbedtls_ct_condition_t.
 *   All arguments to these operations are considered secret.
 *   example: bool x = y | z          =>    x = mbedtls_ct_bool_or(y, z)
 *
 * - conditional data selection
 *   These are all named mbedtls_ct_<type>_if and mbedtls_ct_<type>_if0
 *   All arguments are considered secret.
 *   example: size_t a = x ? b : c    =>    a = mbedtls_ct_size_if(x, b, c)
 *   example: unsigned a = x ? b : 0  =>    a = mbedtls_ct_uint_if0(x, b)
 *
 * - block memory operations
 *   Only some arguments are considered secret, as documented for each
 *   function.
 *   example: if (x) memcpy(...)      =>    mbedtls_ct_memcpy_if(x, ...)
 *
 * mbedtls_ct_condition_t should be treated as opaque and only manipulated
 * via the functions in this header.
 *
 * mbedtls_ct_uint_t is an unsigned integer type over which constant time
 * operations may be performed via the functions in this header. It is as big
 * as the larger of size_t and mbedtls_mpi_uint, i.e. it is safe to cast
 * to/from "unsigned int", "size_t", and "mbedtls_mpi_uint" (and any other
 * not-larger integer types).
 *
 * For Arm (32-bit, 64-bit and Thumb), assembly implementations are used
 * to ensure that the generated code is constant time. For other architectures,
 * a plain C fallback designed to yield constant-time code (this has been
 * observed to be constant-time on latest gcc, clang and MSVC as of May 2023).
 */

#if (SIZE_MAX > 0xffffffffffffffffULL)
/* Pointer size > 64-bit */
typedef size_t    mbedtls_ct_condition_t;
typedef size_t    mbedtls_ct_uint_t;
typedef ptrdiff_t mbedtls_ct_int_t;
#define MBEDTLS_CT_TRUE  ((mbedtls_ct_condition_t) SIZE_MAX)
#elif (SIZE_MAX > 0xffffffff) || defined(MBEDTLS_HAVE_INT64)
/* 32-bit < pointer size < 64-bit, or 64-bit MPI */
typedef uint64_t  mbedtls_ct_condition_t;
typedef uint64_t  mbedtls_ct_uint_t;
typedef int64_t   mbedtls_ct_int_t;
#define MBEDTLS_CT_TRUE  ((mbedtls_ct_condition_t) UINT64_MAX)
#else
/* Pointer size < 32-bit, and no 64-bit MPIs */
typedef uint32_t  mbedtls_ct_condition_t;
typedef uint32_t  mbedtls_ct_uint_t;
typedef int32_t   mbedtls_ct_int_t;
#define MBEDTLS_CT_TRUE  ((mbedtls_ct_condition_t) UINT32_MAX)
#endif
#define MBEDTLS_CT_FALSE ((mbedtls_ct_condition_t) 0)

/* constant_time_impl.h contains all the static inline implementations,
 * so that constant_time_internal.h is more readable.
 */
#include "constant_time_impl.h"


/* ============================================================================
 * Boolean operations
 */

/** Convert a number into a mbedtls_ct_condition_t.
 *
 * \param x Number to convert.
 *
 * \return MBEDTLS_CT_TRUE if \p x != 0, or MBEDTLS_CT_FALSE if \p x == 0
 *
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool(mbedtls_ct_uint_t x);

/** Boolean "not equal" operation.
 *
 * Functionally equivalent to:
 *
 * \p x != \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x != \p y, otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_ne(mbedtls_ct_uint_t x, mbedtls_ct_uint_t y);

/** Boolean "equals" operation.
 *
 * Functionally equivalent to:
 *
 * \p x == \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x == \p y, otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_eq(mbedtls_ct_uint_t x,
                                                        mbedtls_ct_uint_t y);

/** Boolean "less than" operation.
 *
 * Functionally equivalent to:
 *
 * \p x < \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x < \p y, otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_lt(mbedtls_ct_uint_t x, mbedtls_ct_uint_t y);

/** Boolean "greater than" operation.
 *
 * Functionally equivalent to:
 *
 * \p x > \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x > \p y, otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_gt(mbedtls_ct_uint_t x,
                                                        mbedtls_ct_uint_t y);

/** Boolean "greater or equal" operation.
 *
 * Functionally equivalent to:
 *
 * \p x >= \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x >= \p y,
 *              otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_ge(mbedtls_ct_uint_t x,
                                                        mbedtls_ct_uint_t y);

/** Boolean "less than or equal" operation.
 *
 * Functionally equivalent to:
 *
 * \p x <= \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x <= \p y,
 *              otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_le(mbedtls_ct_uint_t x,
                                                        mbedtls_ct_uint_t y);

/** Boolean "xor" operation.
 *
 * Functionally equivalent to:
 *
 * \p x ^ \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \note        This is more efficient than mbedtls_ct_bool_ne if both arguments are
 *              mbedtls_ct_condition_t.
 *
 * \return      MBEDTLS_CT_TRUE if \p x ^ \p y,
 *              otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_xor(mbedtls_ct_condition_t x,
                                                         mbedtls_ct_condition_t y);

/** Boolean "and" operation.
 *
 * Functionally equivalent to:
 *
 * \p x && \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x && \p y,
 *              otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_and(mbedtls_ct_condition_t x,
                                                         mbedtls_ct_condition_t y);

/** Boolean "or" operation.
 *
 * Functionally equivalent to:
 *
 * \p x || \p y
 *
 * \param x     The first value to analyze.
 * \param y     The second value to analyze.
 *
 * \return      MBEDTLS_CT_TRUE if \p x || \p y,
 *              otherwise MBEDTLS_CT_FALSE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_or(mbedtls_ct_condition_t x,
                                                        mbedtls_ct_condition_t y);

/** Boolean "not" operation.
 *
 * Functionally equivalent to:
 *
 * ! \p x
 *
 * \param x     The value to invert
 *
 * \return      MBEDTLS_CT_FALSE if \p x, otherwise MBEDTLS_CT_TRUE.
 */
static inline mbedtls_ct_condition_t mbedtls_ct_bool_not(mbedtls_ct_condition_t x);


/* ============================================================================
 * Data selection operations
 */

/** Choose between two size_t values.
 *
 * Functionally equivalent to:
 *
 * condition ? if1 : if0.
 *
 * \param condition     Condition to test.
 * \param if1           Value to use if \p condition == MBEDTLS_CT_TRUE.
 * \param if0           Value to use if \p condition == MBEDTLS_CT_FALSE.
 *
 * \return  \c if1 if \p condition == MBEDTLS_CT_TRUE, otherwise \c if0.
 */
static inline size_t mbedtls_ct_size_if(mbedtls_ct_condition_t condition,
                                        size_t if1,
                                        size_t if0);

/** Choose between two unsigned values.
 *
 * Functionally equivalent to:
 *
 * condition ? if1 : if0.
 *
 * \param condition     Condition to test.
 * \param if1           Value to use if \p condition == MBEDTLS_CT_TRUE.
 * \param if0           Value to use if \p condition == MBEDTLS_CT_FALSE.
 *
 * \return  \c if1 if \p condition == MBEDTLS_CT_TRUE, otherwise \c if0.
 */
static inline unsigned mbedtls_ct_uint_if_new(mbedtls_ct_condition_t condition,
                                          unsigned if1,
                                          unsigned if0);

#if defined(MBEDTLS_BIGNUM_C)

/** Choose between two mbedtls_mpi_uint values.
 *
 * Functionally equivalent to:
 *
 * condition ? if1 : if0.
 *
 * \param condition     Condition to test.
 * \param if1           Value to use if \p condition == MBEDTLS_CT_TRUE.
 * \param if0           Value to use if \p condition == MBEDTLS_CT_FALSE.
 *
 * \return  \c if1 if \p condition == MBEDTLS_CT_TRUE, otherwise \c if0.
 */
static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if(mbedtls_ct_condition_t condition, \
                                                      mbedtls_mpi_uint if1, \
                                                      mbedtls_mpi_uint if0);

#endif

/** Choose between an unsigned value and 0.
 *
 * Functionally equivalent to:
 *
 * condition ? if1 : 0.
 *
 * Functionally equivalent tombedtls_ct_uint_if(condition, if1, 0) but
 * results in smaller code size.
 *
 * \param condition     Condition to test.
 * \param if1           Value to use if \p condition == MBEDTLS_CT_TRUE.
 *
 * \return  \c if1 if \p condition == MBEDTLS_CT_TRUE, otherwise 0.
 */
static inline unsigned mbedtls_ct_uint_if0(mbedtls_ct_condition_t condition, unsigned if1);

#if defined(MBEDTLS_BIGNUM_C)

/** Choose between an mbedtls_mpi_uint value and 0.
 *
 * Functionally equivalent to:
 *
 * condition ? if1 : 0.
 *
 * Functionally equivalent tombedtls_ct_mpi_uint_if(condition, if1, 0) but
 * results in smaller code size.
 *
 * \param condition     Condition to test.
 * \param if1           Value to use if \p condition == MBEDTLS_CT_TRUE.
 *
 * \return  \c if1 if \p condition == MBEDTLS_CT_TRUE, otherwise 0.
 */
static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if0(mbedtls_ct_condition_t condition,
                                                       mbedtls_mpi_uint if1);

#endif

/** Constant-flow char selection
 *
 * \param low   Secret. Bottom of range
 * \param high  Secret. Top of range
 * \param c     Secret. Value to compare to range
 * \param t     Secret. Value to return, if in range
 *
 * \return      \p t if \p low <= \p c <= \p high, 0 otherwise.
 */
static inline unsigned char mbedtls_ct_uchar_in_range_if(unsigned char low,
                                                         unsigned char high,
                                                         unsigned char c,
                                                         unsigned char t);


/* ============================================================================
 * Block memory operations
 */

#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)

/** Conditionally set a block of memory to zero.
 *
 * Regardless of the condition, every byte will be read once and written to
 * once.
 *
 * \param condition     Secret. Condition to test.
 * \param buf           Secret. Pointer to the start of the buffer.
 * \param len           Number of bytes to set to zero.
 *
 * \warning Unlike mbedtls_platform_zeroize, this does not have the same guarantees
 * about not being optimised away if the memory is never read again.
 */
void mbedtls_ct_zeroize_if(mbedtls_ct_condition_t condition, void *buf, size_t len);

/** Shift some data towards the left inside a buffer.
 *
 * Functionally equivalent to:
 *
 * memmove(start, start + offset, total - offset);
 * memset(start + (total - offset), 0, offset);
 *
 * Timing independence comes at the expense of performance.
 *
 * \param start     Secret. Pointer to the start of the buffer.
 * \param total     Total size of the buffer.
 * \param offset    Secret. Offset from which to copy \p total - \p offset bytes.
 */
void mbedtls_ct_memmove_left(void *start,
                             size_t total,
                             size_t offset);

#endif /* defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT) */

/** Conditional memcpy.
 *
 * Functionally equivalent to:
 *
 * if (condition) {
 *      memcpy(dest, src1, len);
 * } else {
 *      if (src2 != NULL)
 *          memcpy(dest, src2, len);
 * }
 *
 * It will always read len bytes from src1.
 * If src2 != NULL, it will always read len bytes from src2.
 * If src2 == NULL, it will instead read len bytes from dest (as if src2 == dest).
 *
 * \param condition The condition
 * \param dest      Secret. Destination pointer.
 * \param src1      Secret. Pointer to copy from (if \p condition == MBEDTLS_CT_TRUE). Shouldn't overlap with \p dest.
 * \param src2      Secret (contents only - may branch to test if src2 == NULL).
 *                  Pointer to copy from (if \p condition == MBEDTLS_CT_FALSE and \p src2 is not NULL). Shouldn't overlap with \p dest. May be NULL.
 * \param len       Number of bytes to copy.
 */
void mbedtls_ct_memcpy_if(mbedtls_ct_condition_t condition,
                          unsigned char *dest,
                          const unsigned char *src1,
                          const unsigned char *src2,
                          size_t len
                          );

/** Copy data from a secret position.
 *
 * Functionally equivalent to:
 *
 * memcpy(dst, src + offset, len)
 *
 * This function copies \p len bytes from \p src_base + \p offset to \p
 * dst, with a code flow and memory access pattern that does not depend on
 * \p offset, but only on \p offset_min, \p offset_max and \p len.
 *
 * \note                This function reads from \p dest, but the value that
 *                      is read does not influence the result and this
 *                      function's behavior is well-defined regardless of the
 *                      contents of the buffers. This may result in false
 *                      positives from static or dynamic analyzers, especially
 *                      if \p dest is not initialized.
 *
 * \param dest          Secret. The destination buffer. This must point to a writable
 *                      buffer of at least \p len bytes.
 * \param src           Secret. The base of the source buffer. This must point to a
 *                      readable buffer of at least \p offset_max + \p len
 *                      bytes. Shouldn't overlap with \p dest.
 * \param offset        Secret. The offset in the source buffer from which to copy.
 *                      This must be no less than \p offset_min and no greater
 *                      than \p offset_max.
 * \param offset_min    The minimal value of \p offset.
 * \param offset_max    The maximal value of \p offset.
 * \param len           The number of bytes to copy.
 */
void mbedtls_ct_memcpy_offset(unsigned char *dest,
                              const unsigned char *src,
                              size_t offset,
                              size_t offset_min,
                              size_t offset_max,
                              size_t len);

/* Documented in include/mbedtls/constant_time.h. a and b are secret. */
int mbedtls_ct_memcmp(const void *a,
                      const void *b,
                      size_t n);

#endif /* MBEDTLS_CONSTANT_TIME_INTERNAL_H */