N4314
revision of N4145
Jens Maurer <Jens.Maurer@gmx.net>
2014-11-15

N4314: Data-Invariant Functions (revision 2)

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.

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

This paper 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]

1.1 Changes

The following changes were applied to this paper since N4145:

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

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.

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.

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

4 Open Issues

Should we provide the trivial algorithms equal, copy_conditional, and lookup in the standard?
Choose a header name
Choose a shipment vehicle
Choose names: namespace, value<T>, algorithms

5 Wording Changes

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

x.y [datainv] Data-invariant functions
A function is data-invariant with 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);
  }
}
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
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.

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