← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/lib/utils/ct_utils.h

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/utils/ct_utils.h
 
1
/*
 
2
* Functions for constant time operations on data and testing of
 
3
* constant time annotations using valgrind.
 
4
*
 
5
* For more information about constant time programming see
 
6
* Wagner, Molnar, et al "The Program Counter Security Model"
 
7
*
 
8
* (C) 2010 Falko Strenzke
 
9
* (C) 2015,2016 Jack Lloyd
 
10
*
 
11
* Botan is released under the Simplified BSD License (see license.txt)
 
12
*/
 
13
 
 
14
#ifndef BOTAN_TIMING_ATTACK_CM_H_
 
15
#define BOTAN_TIMING_ATTACK_CM_H_
 
16
 
 
17
#include <botan/secmem.h>
 
18
#include <vector>
 
19
 
 
20
#if defined(BOTAN_HAS_VALGRIND)
 
21
  #include <valgrind/memcheck.h>
 
22
#endif
 
23
 
 
24
namespace Botan {
 
25
 
 
26
namespace CT {
 
27
 
 
28
/**
 
29
* Use valgrind to mark the contents of memory as being undefined.
 
30
* Valgrind will accept operations which manipulate undefined values,
 
31
* but will warn if an undefined value is used to decided a conditional
 
32
* jump or a load/store address. So if we poison all of our inputs we
 
33
* can confirm that the operations in question are truly const time
 
34
* when compiled by whatever compiler is in use.
 
35
*
 
36
* Even better, the VALGRIND_MAKE_MEM_* macros work even when the
 
37
* program is not run under valgrind (though with a few cycles of
 
38
* overhead, which is unfortunate in final binaries as these
 
39
* annotations tend to be used in fairly important loops).
 
40
*
 
41
* This approach was first used in ctgrind (https://github.com/agl/ctgrind)
 
42
* but calling the valgrind mecheck API directly works just as well and
 
43
* doesn't require a custom patched valgrind.
 
44
*/
 
45
template<typename T>
 
46
inline void poison(const T* p, size_t n)
 
47
   {
 
48
#if defined(BOTAN_HAS_VALGRIND)
 
49
   VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T));
 
50
#else
 
51
   BOTAN_UNUSED(p);
 
52
   BOTAN_UNUSED(n);
 
53
#endif
 
54
   }
 
55
 
 
56
template<typename T>
 
57
inline void unpoison(const T* p, size_t n)
 
58
   {
 
59
#if defined(BOTAN_HAS_VALGRIND)
 
60
   VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T));
 
61
#else
 
62
   BOTAN_UNUSED(p);
 
63
   BOTAN_UNUSED(n);
 
64
#endif
 
65
   }
 
66
 
 
67
template<typename T>
 
68
inline void unpoison(T& p)
 
69
   {
 
70
#if defined(BOTAN_HAS_VALGRIND)
 
71
   VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
 
72
#else
 
73
   BOTAN_UNUSED(p);
 
74
#endif
 
75
   }
 
76
 
 
77
/*
 
78
* T should be an unsigned machine integer type
 
79
* Expand to a mask used for other operations
 
80
* @param in an integer
 
81
* @return If n is zero, returns zero. Otherwise
 
82
* returns a T with all bits set for use as a mask with
 
83
* select.
 
84
*/
 
85
template<typename T>
 
86
inline T expand_mask(T x)
 
87
   {
 
88
   T r = x;
 
89
   // First fold r down to a single bit
 
90
   for(size_t i = 1; i != sizeof(T)*8; i *= 2)
 
91
      {
 
92
      r = r | static_cast<T>(r >> i);
 
93
      }
 
94
   r &= 1;
 
95
   r = static_cast<T>(~(r - 1));
 
96
   return r;
 
97
   }
 
98
 
 
99
template<typename T>
 
100
inline T expand_top_bit(T a)
 
101
   {
 
102
   return expand_mask<T>(a >> (sizeof(T)*8-1));
 
103
   }
 
104
 
 
105
template<typename T>
 
106
inline T select(T mask, T from0, T from1)
 
107
   {
 
108
   return static_cast<T>((from0 & mask) | (from1 & ~mask));
 
109
   }
 
110
 
 
111
template<typename PredT, typename ValT>
 
112
inline ValT val_or_zero(PredT pred_val, ValT val)
 
113
   {
 
114
   return select(CT::expand_mask<ValT>(pred_val), val, static_cast<ValT>(0));
 
115
   }
 
116
 
 
117
template<typename T>
 
118
inline T is_zero(T x)
 
119
   {
 
120
   return static_cast<T>(~expand_mask(x));
 
121
   }
 
122
 
 
123
template<typename T>
 
124
inline T is_equal(T x, T y)
 
125
   {
 
126
   return is_zero<T>(x ^ y);
 
127
   }
 
128
 
 
129
template<typename T>
 
130
inline T is_less(T a, T b)
 
131
   {
 
132
   return expand_top_bit<T>(a ^ ((a^b) | ((a-b)^a)));
 
133
   }
 
134
 
 
135
template<typename T>
 
136
inline T is_lte(T a, T b)
 
137
   {
 
138
   return CT::is_less(a, b) | CT::is_equal(a, b);
 
139
   }
 
140
 
 
141
template<typename T>
 
142
inline void conditional_copy_mem(T value,
 
143
                                 T* to,
 
144
                                 const T* from0,
 
145
                                 const T* from1,
 
146
                                 size_t elems)
 
147
   {
 
148
   const T mask = CT::expand_mask(value);
 
149
 
 
150
   for(size_t i = 0; i != elems; ++i)
 
151
      {
 
152
      to[i] = CT::select(mask, from0[i], from1[i]);
 
153
      }
 
154
   }
 
155
 
 
156
template<typename T>
 
157
inline void cond_zero_mem(T cond,
 
158
                          T* array,
 
159
                          size_t elems)
 
160
   {
 
161
   const T mask = CT::expand_mask(cond);
 
162
   const T zero(0);
 
163
 
 
164
   for(size_t i = 0; i != elems; ++i)
 
165
      {
 
166
      array[i] = CT::select(mask, zero, array[i]);
 
167
      }
 
168
   }
 
169
 
 
170
inline secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length)
 
171
   {
 
172
   size_t leading_zeros = 0;
 
173
 
 
174
   uint8_t only_zeros = 0xFF;
 
175
 
 
176
   for(size_t i = 0; i != length; ++i)
 
177
      {
 
178
      only_zeros = only_zeros & CT::is_zero<uint8_t>(in[i]);
 
179
      leading_zeros += CT::select<uint8_t>(only_zeros, 1, 0);
 
180
      }
 
181
 
 
182
   return secure_vector<uint8_t>(in + leading_zeros, in + length);
 
183
   }
 
184
 
 
185
inline secure_vector<uint8_t> strip_leading_zeros(const secure_vector<uint8_t>& in)
 
186
   {
 
187
   return strip_leading_zeros(in.data(), in.size());
 
188
   }
 
189
 
 
190
}
 
191
 
 
192
}
 
193
 
 
194
#endif