revision of N4314

Jens Maurer <Jens.Maurer@gmx.net>

2015-05-22

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 function*s in this paper. It is the
responsibility of the implementation to ensure that they remain
data-invariant even when optimizing.

C functions at this abstraction level have recently been added to OpenSSL and BoringSSL.

This paper is handled via LEWG issue 54 and addresses parts of LEWG issue 15.

The Library Evolution Working Group (LEWG) discussed this paper during the Urbana-Champaign (November 2014) meeting, with the following results:

- use
`equal`

algorithm with two ranges - consider whether the algorithms taking less than RandomAccessIterator will be data-invariant even for lists and hash tables
- await evidence of actual use of a library at the abstraction level presented [see above]

- code motion into / out of the constant-time block is not addressed
- enable aliasing existing data for constant-time operations

- basic algorithms are part of the proposal
- add a code motion barrier
- allow aliasing of T with value<T>

- rephrase definition of "data-invariant" in the wording (blue text)
- add pointers to existing library approaches in OpenSSL and BoringSSL
- change the
`equal`

algorithms so that it takes two ranges - add consideration of iterators that may not be data-invariant
- removed
`BinaryPredicate`

overload of`equal`

, since it increases the scope without apparent benefit

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.

Algorithms on lists or hash tables may be constant-time. However, the user must take care to ensure that iterator operations are data-invariant. For example, hash tables may have different element distributions depending on the actual values of the elements. For the user, it is best to limit use of data-invariant functions to RandomAccessIterators, but there is no strong reason to restrict the interface as provided by the standard.

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 InputIterator2 last2) { value<bool> result(true); using T = typename std::iterator_traits<InputIterator1>::value_type; for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) result = result && (value<T>(*first1) == value<T>(*first2)); if (first1 != last1 || first2 != last2) return value<bool>(false); 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, InputIterator2 last2) { unsigned int v = 0; for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) v |= *first1 ^ *first2; if (first1 != last1 || first2 != last2) return value<bool>(false); return value<unsigned int>(v) == value<unsigned int>(0); }

- Choose a header name
- Choose a shipment vehicle
- Choose names: namespace,
`value<T>`

, algorithms

Reading an object designated by a volatile glvalue (3.10 basic.lval), modifying an object, calling a library I/O function, calling the function`std::constant_time::barrier`

, or calling a function that does any of those operations are allside effects, which are changes in the state of the execution environment.

Add a new section, for example in clause 20 [utilities]:

- a type that is a (possibly cv-qualified) base class type of the dynamic type of the object,
- for an object of scalar type other than
`bool`

,`std::constant_time::value<T>`

, where T is the type of the object,- a
`char`

or`unsigned char`

type.

x.y [datainv] Data-invariant functionsA function is

data-invariantwith respect to its argument values or a subset thereof if the physical execution properties of the function do not depend on those 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); template<class InputIterator1, class InputIterator2> value<bool> equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator copy_conditional(value<bool> condition, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result); template<class InputIterator> value</* see below */> lookup(InputIterator first, InputIterator last, std::size_t index);void barrier();} }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 value`x`

.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 on`x.get()`

and`y.get()`

(5.9 [expr.rel], 5.10 [expr.eq]).

Remarks:These functions are data-invariant with respect to the values of`x`

and`y`

.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`

, and`y`

.

## 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 on`x.get()`

and`y.get()`

(5.14 [expr.log.and], 5.15 [expr.log.or]).

Remarks:These functions are data-invariant with respect to the values of`x`

and`y`

. [ Note: In contrast to the built-in operations, short-circuit evaluation is not performed. ]

x.y.4 Other functionsvoid barrier();

Effects:None

Remarks:This function is assumed to access and modify every memory location in the program, without inducing data races (1.10 [intro.multithread]). [ Note: The implementation may not speculatively move evaluations across the barrier. ]

## x.y.5 Algorithms

The functions in this section are data-invariant only if the required operations on the provided iterators are data-invariant.template<class InputIterator1, class InputIterator2> value<bool> equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

Requires:`InputIterator1`

and`InputIterator2`

have the same scalar and non-volatile`value_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`min(last1-first1, last2-first2)`

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`

and`InputIterator2`

have the same scalar and non-volatile`value_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()`

is`true`

,`std::copy(first1, last1, result)`

, otherwise`std::copy(first2, first2 + (last1-first1), result)`

.

Complexity:Exactly`last1-first1`

increments of each of`InputIterator1`

and`InputIterator2`

.template<class InputIterator> value</* see below */> lookup(InputIterator first, InputIterator last, std::size_t index);

Requires:`InputIterator`

has a scalar and non-volatile`value_type`

. The value of`index`

is less than`last-first`

.

Returns:`*(first + index)`

Remarks:The return type is`value<T>`

, where`T`

is the`value_type`

of the`InputIterator`

with any top-level cv-qualification removed. This function is data-invariant with respect to the values of`index`

and the input sequence, but not with respect to the length of the input sequence.

Complexity:Exactly`last-first`

increments of`InputIterator`

.

- coding rules for cryptography
- package crypto/suble of the Go language