N4145
Jens Maurer <[email protected]>
2014-09-26

N4145: Data-Invariant Functions

1 Introduction

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.

2 Design

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.

3 Discussion

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);
}

4 Open Issues

Should we provide the trivial algorithms equal, copy_conditional, and lookup in the standard?
Choose a header name

5 Wording Changes

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

x.y [datainv] Data-invariant functions
A 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 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. ]

6 Backup wording for algorithms

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

7 Acknowledgements

Thanks to Adam Langley (Google) for reviewing an earlier version of this paper.

8 References

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