One of the hardest challenges when implementing cryptographic functionality with well-defined mathematical properties is to avoid side-channel attacks, that is, security breaches exploiting physical effects dependent on secret data when performing a cryptographic operation. Such effects include variances in timing of execution, power consumption of the machine, or noise produced by voltage regulators of the CPU. C++ does not consider such effects as part of the observable behavior of the abstract machine (C++ 1.9 [intro.execution]), thereby allowing implementations to vary these properties in unspecified ways.
As an example, this fairly recent
patch for openssl
replaced some if
statements with open-coded operations
that leak no timing information about the true vs. false outcome. In
general, this is a sound approach, but it bears some risk in the
framework of C and C++, because future optimizations in compilers
might restore conditional branches under the as-if rule.
This paper proposes a small set of functions performing common tasks with physical execution properties that do not vary with (specified parts of) the input values. Such functions are called data-invariant functions. It is the responsibility of the implementation to ensure that they remain data-invariant even when optimizing.
This paper addresses parts of LEWG issue 15.
Similar to std::atomic<>
, we introduce a template
std::constant_time::value<>
whose (select few)
operations have the desired properties; see section 5 for details.
Useful algorithms can be built trivially on top of the building blocks provided; see below.
All values must be cv-unqualified scalar types.
This seems to be the most straightforward approach. The selection of standard-mandated operations and algorithms should be limited to the bare minimum, since they are only useful for a very narrow target audience.
A prototype implementation for Intel x86 and T = unsigned
int
is available at
data-invariant.tar.
It uses gcc inline assembly to guarantee branch-free operations.
Analysis of the resulting executable code shows that no abstraction
overhead of value<T>
over plain T
is
present when optimizing.
Using the facilities provided, some commonly-used data-invariant algorithms can be built on top:
template<class InputIterator1, class InputIterator2> value<bool> equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2) { value<bool> result(true); using T = typename std::iterator_traits<InputIterator1>::value_type; for ( ; first1 != last1; ++first1, ++first2) result = result && (value<T>(*first1) == value<T>(*first2)); return result; } template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator copy_conditional(value<bool> condition, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result) { using T = typename std::iterator_traits<InputIterator1>::value_type; for ( ; first1 != last1; ++first1, ++first2) *result++ = select(condition, value<T>(*first1), value<T>(*first2)).get(); } template<class InputIterator> value<typename std::iterator_traits<InputIterator>::value_type> lookup(InputIterator first, InputIterator last, std::size_t index) { using T = typename std::iterator_traits<InputIterator>::value_type; const value<std::size_t> idx(index); value<T> result(0); for (std::size_t i = 0; first != last; ++first, ++i) result = select(value<std::size_t>(i) == idx, value<T>(*first), result); return result; }However, some of these algorithms may have a faster implementation using fairly intricate bit operations, so it might be worthwhile to provide them in the standard library. For example,
equal
on a sequence of unsigned int
could be written like this:
template<class InputIterator1, class InputIterator2> value<bool> equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2) { unsigned int v = 0; for ( ; first1 != last1; ++first1, ++first2) v |= *first1 ^ *first2; return value<unsigned int>(v) == value<unsigned int>(0); }
equal
,
copy_conditional
, and lookup
in the
standard?x.y [datainv] Data-invariant functionsA data-invariant function is a function whose physical execution properties do not depend on the values of all or a subset of the argument values.
[ Note: In particular, the execution times and memory access patterns are independent of the argument values. Also, branches or loop counts do not depend on argument values. ]
namespace std { namespace constant_time { template<class T> struct value { explicit value(T); T get() const; }; template<class T> value<bool> operator==(value<T> x, value<T> y); template<class T> value<bool> operator!=(value<T> x, value<T> y); template<class T> value<bool> operator<(value<T> x, value<T> y); template<class T> value<bool> operator<=(value<T> x, value<T> y); template<class T> value<bool> operator>(value<T> x, value<T> y); template<class T> value<bool> operator>=(value<T> x, value<T> y); template<class T> value<T> select(value<bool> condition, value<T> x, value<T> y); value<bool> operator&&(value<bool> x, value<bool> y); value<bool> operator||(value<bool> x, value<bool> y); } }The template parameter
T
shall denote a cv-unqualified scalar type (3.9 basic.types).x.y.1 Member functions of value<T>
All member functions of
value<T>
are data-invariant with respect to the arguments and the value held by*this
.explicit value(T x)Effects: Constructs a
value
object holding valuex
.T get()Returns: The value this
value
object is holding.x.y.2 Operations on value<T>
template<class T> value<bool> operator==(value<T> x, value<T> y); template<class T> value<bool> operator!=(value<T> x, value<T> y); template<class T> value<bool> operator<(value<T> x, value<T> y); template<class T> value<bool> operator<=(value<T> x, value<T> y); template<class T> value<bool> operator>(value<T> x, value<T> y); template<class T> value<bool> operator>=(value<T> x, value<T> y);Returns: A
value<bool>
holding the boolean result of the corresponding comparison onx.get()
andy.get()
(5.9 [expr.rel], 5.10 [expr.eq]).Remarks: These functions are data-invariant with respect to the values of
x
andy
.template<class T> value<T> select(value<bool> condition, value<T> x, value<T> y);Returns:
(condition.get() ? x : y)
Remarks: This function is data-invariant with respect to the values of
condition
,x
, andy
.x.y.3 Operations on value<bool>
value<bool> operator&&(value<bool> x, value<bool> y); value<bool> operator||(value<bool> x, value<bool> y);Returns: A
value<bool>
holding the boolean result of the corresponding operation onx.get()
andy.get()
(5.14 [expr.log.and], 5.15 [expr.log.or]).Remarks: These functions are data-invariant with respect to the values of
x
andy
. [ Note: In contrast to the built-in operations, short-circuit evaluation is not performed. ]
x.y.4 Algorithms
template<class InputIterator1, class InputIterator2> value<bool> equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> value<bool> equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);Requires:
InputIterator1
andInputIterator2
have the same scalar and non-volatilevalue_type
.Returns: See 25.2.11 [alg.equal].
Remarks: This function is data-invariant with respect to the values, but not the length, of the input sequences.
Complexity: Exactly
last1-first1
applications of the corresponding predicate.template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator copy_conditional(value<bool> condition, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);Requires:
InputIterator1
andInputIterator2
have the same scalar and non-volatilevalue_type
.Remarks: This function is data-invariant with respect to the value of
condition
and the values of the input sequences, but not with respect to the length of the input sequences.Returns: If
condition.get()
istrue
,std::copy(first1, last1, result)
, otherwisestd::copy(first2, first2 + (last1-first1), result)
.Complexity: Exactly
last1-first1
increments of each ofInputIterator1
andInputIterator2
.template<class InputIterator> value</* see below */> lookup(InputIterator first, InputIterator last, std::size_t index);Requires:
InputIterator
has a scalar and non-volatilevalue_type
. The value ofindex
is less thanlast-first
.Returns:
*(first + index)
Remarks: The return type is
value<T>
, whereT
is thevalue_type
of theInputIterator
with any top-level cv-qualification removed. This function is data-invariant with respect to the values ofindex
and the input sequence, but not with respect to the length of the input sequence.Complexity: Exactly
last-first
increments ofInputIterator
.