1// Copyright 2017 The BoringSSL Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include <openssl/ctrdrbg.h>
16
17#include <assert.h>
18
19#include <openssl/mem.h>
20#include <algorithm>
21
22#include "../aes/internal.h"
23#include "../service_indicator/internal.h"
24#include "internal.h"
25
26
27// Section references in this file refer to SP 800-90Ar1:
28// http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
29
30// Also see table 3.
31constexpr uint64_t kMaxReseedCount = UINT64_C(1) << 48;
32
33// Implements the BCC function as described in Section 10.3.3.
34static void bcc(uint8_t out[AES_BLOCK_SIZE], const AES_KEY *aes_key,
35                const uint8_t *data, size_t data_len) {
36  // 1. chaining_value = 0^outlen.
37  uint8_t *chaining_value = out;
38  OPENSSL_memset(chaining_value, 0, AES_BLOCK_SIZE);
39
40  // 2. n = len (data)/outlen.
41  BSSL_CHECK(data_len % AES_BLOCK_SIZE == 0);
42  const size_t n = data_len / AES_BLOCK_SIZE;
43
44  for (size_t i = 0; i < n; i++) {
45    const uint8_t *block = data + (i * AES_BLOCK_SIZE);
46    uint8_t input_block[AES_BLOCK_SIZE];
47
48    // 4.1: input_block = chaining_value ⊕ block_i.
49    CRYPTO_xor16(input_block, chaining_value, block);
50
51    // 4.2: chaining_value = Block_Encrypt (Key, input_block).
52    BCM_aes_encrypt(input_block, chaining_value, aes_key);
53  }
54
55  // 5. output_block = chaining_value.
56}
57
58// Implements the derivation function as described in Section 10.3.2.
59static int block_cipher_df(uint8_t *out, size_t out_len, const uint8_t *input,
60                           size_t input_len) {
61  // Constants for AES-256
62  constexpr size_t kAESKeyLen = 32;
63  constexpr size_t kAESOutLen = AES_BLOCK_SIZE;
64  constexpr size_t kMaxNumBits = 512;
65
66  if (out_len > kMaxNumBits / 8 || input_len > (1u << 30)) {
67    return 0;
68  }
69
70  // 4. S = L || N || input_string || 0x80.
71  const size_t s_rawlen = sizeof(uint32_t) + sizeof(uint32_t) + input_len + 1;
72  // S is padded up to a block size.
73  const size_t s_len = (s_rawlen + kAESOutLen - 1) & ~(kAESOutLen - 1);
74  uint8_t iv_plus_s[/* space used below */ kAESOutLen + 4 + 4 +
75                    CTR_DRBG_MAX_ENTROPY_LEN + CTR_DRBG_NONCE_LEN +
76                    CTR_DRBG_SEED_LEN + 1 +
77                    /* padding */ 7];
78  if (kAESOutLen + s_len > sizeof(iv_plus_s)) {
79    return 0;
80  }
81  OPENSSL_memset(iv_plus_s, 0, sizeof(iv_plus_s));
82  uint8_t *s_ptr = iv_plus_s + kAESOutLen;
83  // 2. L = len (input_string)/8.
84  CRYPTO_store_u32_be(s_ptr, (uint32_t)input_len);
85  s_ptr += sizeof(uint32_t);
86  // 3. N = number_of_bits_to_return/8.
87  CRYPTO_store_u32_be(s_ptr, (uint32_t)out_len);
88  s_ptr += sizeof(uint32_t);
89  OPENSSL_memcpy(s_ptr, input, input_len);
90  s_ptr += input_len;
91  *s_ptr = 0x80;
92
93  uint8_t temp[kAESKeyLen + kAESOutLen];
94  size_t temp_len = 0;
95
96  // 8. K = leftmost (0x00010203...1D1E1F, keylen).
97  static const uint8_t kInitialKey[kAESKeyLen] = {
98      0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
99      0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
100      0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f};
101  AES_KEY aes_key;
102  bcm_status status =
103      BCM_aes_set_encrypt_key(kInitialKey, 8 * sizeof(kInitialKey), &aes_key);
104  BSSL_CHECK(status != bcm_status::failure);
105
106  // 7. i = 0.
107  uint32_t i = 0;
108  while (temp_len < sizeof(temp)) {
109    // 9.1 IV = i || 0^(outlen - len(i)).
110    CRYPTO_store_u32_be(iv_plus_s, i);
111
112    // 9.2 temp = temp || BCC (K, (IV || S)).
113    bcc(temp + temp_len, &aes_key, iv_plus_s, kAESOutLen + s_len);
114    temp_len += kAESOutLen;
115
116    // 9.3 i = i + 1.
117    i++;
118  }
119
120  // 10. K = leftmost (temp, keylen).
121  uint8_t *const k = temp;
122
123  // 11. X = select (temp, keylen+1, keylen+outlen).
124  uint8_t *const x = temp + kAESKeyLen;
125
126  // 12. temp = the Null string.
127  temp_len = 0;
128
129  // Create an AES key schedule for the final encryption steps.
130  status = BCM_aes_set_encrypt_key(k, kAESKeyLen * 8, &aes_key);
131  BSSL_CHECK(status != bcm_status::failure);
132
133  // 13. While len (temp) < number_of_bits_to_return, do:
134  while (temp_len < out_len) {
135    // 13.1 X = Block_Encrypt (K, X).
136    BCM_aes_encrypt(x, x, &aes_key);
137
138    // 13.2 temp = temp || X.
139    size_t to_copy = std::min(kAESOutLen, out_len - temp_len);
140    OPENSSL_memcpy(out + temp_len, x, to_copy);
141    temp_len += to_copy;
142  }
143
144  return 1;
145}
146
147CTR_DRBG_STATE *CTR_DRBG_new(const uint8_t entropy[CTR_DRBG_ENTROPY_LEN],
148                             const uint8_t *personalization,
149                             size_t personalization_len) {
150  CTR_DRBG_STATE *drbg = reinterpret_cast<CTR_DRBG_STATE *>(
151      OPENSSL_malloc(sizeof(CTR_DRBG_STATE)));
152  if (drbg == NULL ||
153      !CTR_DRBG_init(drbg, /*df=*/false, entropy, CTR_DRBG_ENTROPY_LEN,
154                     /*nonce=*/nullptr, personalization, personalization_len)) {
155    CTR_DRBG_free(drbg);
156    return NULL;
157  }
158
159  return drbg;
160}
161
162CTR_DRBG_STATE *CTR_DRBG_new_df(const uint8_t *entropy, size_t entropy_len,
163                                const uint8_t nonce[CTR_DRBG_NONCE_LEN],
164                                const uint8_t *personalization,
165                                size_t personalization_len) {
166  CTR_DRBG_STATE *drbg = reinterpret_cast<CTR_DRBG_STATE *>(
167      OPENSSL_malloc(sizeof(CTR_DRBG_STATE)));
168  if (drbg == NULL ||
169      !CTR_DRBG_init(drbg, /*df=*/true, entropy, entropy_len, nonce,
170                     personalization, personalization_len)) {
171    CTR_DRBG_free(drbg);
172    return NULL;
173  }
174
175  return drbg;
176}
177
178void CTR_DRBG_free(CTR_DRBG_STATE *state) { OPENSSL_free(state); }
179
180int CTR_DRBG_init(CTR_DRBG_STATE *drbg, int df, const uint8_t *entropy,
181                  size_t entropy_len, const uint8_t nonce[CTR_DRBG_NONCE_LEN],
182                  const uint8_t *personalization, size_t personalization_len) {
183  // Section 10.2.1.3.1 and 10.2.1.3.2
184  if (personalization_len > CTR_DRBG_SEED_LEN ||
185      (!df && entropy_len != CTR_DRBG_ENTROPY_LEN) ||
186      (df && (entropy_len < CTR_DRBG_MIN_ENTROPY_LEN ||
187              entropy_len > CTR_DRBG_MAX_ENTROPY_LEN)) ||  //
188      (df != (nonce != nullptr))) {
189    return 0;
190  }
191
192  uint8_t seed_material[CTR_DRBG_SEED_LEN];
193  if (df) {
194    uint8_t pre_seed_material[CTR_DRBG_MAX_ENTROPY_LEN + CTR_DRBG_NONCE_LEN +
195                              CTR_DRBG_SEED_LEN];
196    OPENSSL_memcpy(pre_seed_material, entropy, entropy_len);
197    OPENSSL_memcpy(pre_seed_material + entropy_len, nonce, CTR_DRBG_NONCE_LEN);
198    OPENSSL_memcpy(pre_seed_material + entropy_len + CTR_DRBG_NONCE_LEN,
199                   personalization, personalization_len);
200    const size_t pre_seed_material_length =
201        entropy_len + CTR_DRBG_NONCE_LEN + personalization_len;
202
203    if (!block_cipher_df(seed_material, sizeof(seed_material),
204                         pre_seed_material, pre_seed_material_length)) {
205      return 0;
206    }
207  } else {
208    OPENSSL_memcpy(seed_material, entropy, CTR_DRBG_ENTROPY_LEN);
209    for (size_t i = 0; i < personalization_len; i++) {
210      seed_material[i] ^= personalization[i];
211    }
212  }
213
214  // Section 10.2.1.2
215
216  // kInitMask is the result of encrypting blocks with big-endian value 1, 2
217  // and 3 with the all-zero AES-256 key.
218  static const uint8_t kInitMask[CTR_DRBG_SEED_LEN] = {
219      0x53, 0x0f, 0x8a, 0xfb, 0xc7, 0x45, 0x36, 0xb9, 0xa9, 0x63, 0xb4, 0xf1,
220      0xc4, 0xcb, 0x73, 0x8b, 0xce, 0xa7, 0x40, 0x3d, 0x4d, 0x60, 0x6b, 0x6e,
221      0x07, 0x4e, 0xc5, 0xd3, 0xba, 0xf3, 0x9d, 0x18, 0x72, 0x60, 0x03, 0xca,
222      0x37, 0xa6, 0x2a, 0x74, 0xd1, 0xa2, 0xf5, 0x8e, 0x75, 0x06, 0x35, 0x8e,
223  };
224
225  for (size_t i = 0; i < sizeof(kInitMask); i++) {
226    seed_material[i] ^= kInitMask[i];
227  }
228
229  drbg->df = df;
230  drbg->ctr = aes_ctr_set_key(&drbg->ks, NULL, &drbg->block, seed_material, 32);
231  OPENSSL_memcpy(drbg->counter, seed_material + 32, 16);
232  drbg->reseed_counter = 1;
233
234  return 1;
235}
236
237static_assert(CTR_DRBG_SEED_LEN % AES_BLOCK_SIZE == 0,
238              "not a multiple of AES block size");
239
240// ctr_inc adds |n| to the last four bytes of |drbg->counter|, treated as a
241// big-endian number.
242static void ctr32_add(CTR_DRBG_STATE *drbg, uint32_t n) {
243  uint32_t ctr = CRYPTO_load_u32_be(drbg->counter + 12);
244  CRYPTO_store_u32_be(drbg->counter + 12, ctr + n);
245}
246
247static int ctr_drbg_update(CTR_DRBG_STATE *drbg,
248                           const uint8_t data[CTR_DRBG_SEED_LEN]) {
249  uint8_t temp[CTR_DRBG_SEED_LEN];
250  for (size_t i = 0; i < CTR_DRBG_SEED_LEN; i += AES_BLOCK_SIZE) {
251    ctr32_add(drbg, 1);
252    drbg->block(drbg->counter, temp + i, &drbg->ks);
253  }
254
255  for (size_t i = 0; i < CTR_DRBG_SEED_LEN; i++) {
256    temp[i] ^= data[i];
257  }
258
259  drbg->ctr = aes_ctr_set_key(&drbg->ks, NULL, &drbg->block, temp, 32);
260  OPENSSL_memcpy(drbg->counter, temp + 32, 16);
261
262  return 1;
263}
264
265int CTR_DRBG_reseed(CTR_DRBG_STATE *drbg,
266                    const uint8_t entropy[CTR_DRBG_ENTROPY_LEN],
267                    const uint8_t *additional_data,
268                    size_t additional_data_len) {
269  return CTR_DRBG_reseed_ex(drbg, entropy, CTR_DRBG_ENTROPY_LEN,
270                            additional_data, additional_data_len);
271}
272
273int CTR_DRBG_reseed_ex(CTR_DRBG_STATE *drbg, const uint8_t *entropy,
274                       size_t entropy_len, const uint8_t *additional_data,
275                       size_t additional_data_len) {
276  if (additional_data_len > CTR_DRBG_SEED_LEN ||
277      (drbg->df && (entropy_len > CTR_DRBG_MAX_ENTROPY_LEN ||
278                    entropy_len < CTR_DRBG_MIN_ENTROPY_LEN)) ||
279      (!drbg->df && entropy_len != CTR_DRBG_ENTROPY_LEN)) {
280    return 0;
281  }
282
283  uint8_t seed_material[CTR_DRBG_SEED_LEN];
284  if (drbg->df) {
285    // Section 10.2.1.4.2
286    uint8_t pre_seed_material[CTR_DRBG_MAX_ENTROPY_LEN + CTR_DRBG_SEED_LEN];
287    static_assert(CTR_DRBG_MAX_ENTROPY_LEN <= sizeof(pre_seed_material));
288    OPENSSL_memcpy(pre_seed_material, entropy, entropy_len);
289    OPENSSL_memcpy(pre_seed_material + entropy_len, additional_data,
290                   additional_data_len);
291    const size_t pre_seed_material_len = entropy_len + additional_data_len;
292
293    if (!block_cipher_df(seed_material, sizeof(seed_material),
294                         pre_seed_material, pre_seed_material_len)) {
295      return 0;
296    }
297  } else {
298    // Section 10.2.1.4
299    static_assert(CTR_DRBG_ENTROPY_LEN == sizeof(seed_material));
300    OPENSSL_memcpy(seed_material, entropy, CTR_DRBG_ENTROPY_LEN);
301    if (additional_data_len > 0) {
302      for (size_t i = 0; i < additional_data_len; i++) {
303        seed_material[i] ^= additional_data[i];
304      }
305    }
306  }
307
308  if (!ctr_drbg_update(drbg, seed_material)) {
309    return 0;
310  }
311
312  drbg->reseed_counter = 1;
313
314  return 1;
315}
316
317int CTR_DRBG_generate(CTR_DRBG_STATE *drbg, uint8_t *out, size_t out_len,
318                      const uint8_t *additional_data,
319                      size_t additional_data_len) {
320  // See 9.3.1
321  if (out_len > CTR_DRBG_MAX_GENERATE_LENGTH) {
322    return 0;
323  }
324
325  // See 10.2.1.5.1
326  if (drbg->reseed_counter > kMaxReseedCount) {
327    return 0;
328  }
329
330  uint8_t processed_additional_data[CTR_DRBG_SEED_LEN];
331  OPENSSL_memset(processed_additional_data, 0,
332                 sizeof(processed_additional_data));
333  if (additional_data_len != 0) {
334    if (drbg->df) {
335      if (!block_cipher_df(processed_additional_data,
336                           sizeof(processed_additional_data), additional_data,
337                           additional_data_len)) {
338        return 0;
339      }
340    } else {
341      if (additional_data_len > sizeof(processed_additional_data)) {
342        return 0;
343      }
344      OPENSSL_memcpy(processed_additional_data, additional_data,
345                     additional_data_len);
346    }
347    if (!ctr_drbg_update(drbg, processed_additional_data)) {
348      return 0;
349    }
350  }
351
352  // kChunkSize is used to interact better with the cache. Since the AES-CTR
353  // code assumes that it's encrypting rather than just writing keystream, the
354  // buffer has to be zeroed first. Without chunking, large reads would zero
355  // the whole buffer, flushing the L1 cache, and then do another pass (missing
356  // the cache every time) to “encrypt” it. The code can avoid this by
357  // chunking.
358  constexpr size_t kChunkSize = 8 * 1024;
359
360  while (out_len >= AES_BLOCK_SIZE) {
361    size_t todo = kChunkSize;
362    if (todo > out_len) {
363      todo = out_len;
364    }
365
366    todo &= ~(AES_BLOCK_SIZE - 1);
367    const size_t num_blocks = todo / AES_BLOCK_SIZE;
368
369    OPENSSL_memset(out, 0, todo);
370    ctr32_add(drbg, 1);
371    drbg->ctr(out, out, num_blocks, &drbg->ks, drbg->counter);
372    ctr32_add(drbg, (uint32_t)(num_blocks - 1));
373
374    out += todo;
375    out_len -= todo;
376  }
377
378  if (out_len > 0) {
379    uint8_t block[AES_BLOCK_SIZE];
380    ctr32_add(drbg, 1);
381    drbg->block(drbg->counter, block, &drbg->ks);
382
383    OPENSSL_memcpy(out, block, out_len);
384  }
385
386  if (!ctr_drbg_update(drbg, processed_additional_data)) {
387    return 0;
388  }
389
390  drbg->reseed_counter++;
391  FIPS_service_indicator_update_state();
392  return 1;
393}
394
395void CTR_DRBG_clear(CTR_DRBG_STATE *drbg) {
396  OPENSSL_cleanse(drbg, sizeof(CTR_DRBG_STATE));
397}
398