1                 : /*
       2                 :  * Copyright 2008 The Native Client Authors. All rights reserved.
       3                 :  * Use of this source code is governed by a BSD-style license that can be
       4                 :  * found in the LICENSE file.
       5                 :  */
       6                 : 
       7                 : /*
       8                 :  * NaCl Service Runtime.  Secure RNG implementation.
       9                 :  */
      10                 : 
      11                 : #include "native_client/src/shared/platform/nacl_log.h"
      12                 : #include "native_client/src/shared/platform/nacl_secure_random.h"
      13                 : 
      14               3 : uint32_t NaClSecureRngDefaultGenUint32(struct NaClSecureRngIf *self) {
      15                 :   uint32_t rv;
      16                 : 
      17               3 :   rv  = (*self->vtbl->GenByte)(self);
      18               3 :   rv <<= 8;
      19               3 :   rv |= (*self->vtbl->GenByte)(self);
      20               3 :   rv <<= 8;
      21               3 :   rv |= (*self->vtbl->GenByte)(self);
      22               3 :   rv <<= 8;
      23               3 :   rv |= (*self->vtbl->GenByte)(self);
      24               3 :   return rv;
      25               3 : }
      26                 : 
      27                 : void NaClSecureRngDefaultGenBytes(struct NaClSecureRngIf  *self,
      28                 :                                   uint8_t                 *buf,
      29               0 :                                   size_t                  nbytes) {
      30                 :   size_t i;
      31                 : 
      32               0 :   for (i = 0; i < nbytes; ++i) {
      33               0 :     buf[i] = (*self->vtbl->GenByte)(self);
      34               0 :   }
      35               0 : }
      36                 : 
      37                 : uint32_t NaClSecureRngDefaultUniform(struct NaClSecureRngIf *self,
      38               3 :                                      uint32_t               range_max) {
      39                 :   uint32_t bias;
      40                 :   uint32_t v;
      41                 : 
      42                 :   /*
      43                 :    * First, is range_max a power of 2?  If so, we can just keep the
      44                 :    * low order bits.
      45                 :    */
      46               3 :   if (0 == (range_max & (range_max - 1))) {
      47               0 :     return (*self->vtbl->GenUint32)(self) & (range_max - 1);
      48                 :   }
      49                 :   /* post condition: range_max is not a power of 2 */
      50                 : 
      51                 :   /*
      52                 :    * Generator output range is uniform in [0, ~(uint32_t) 0] or [0, 2^{32}).
      53                 :    *
      54                 :    * NB: Number of integer values in the range [0, n) is n,
      55                 :    * and number of integer values in the range [m, n) is n-m,
      56                 :    * (n and m are integers).
      57                 :    */
      58               3 :   bias = ((~(uint32_t) 0) % range_max) + 1;
      59                 :   /*
      60                 :    * bias = (2^{32}-1 \bmod range_max) + 1
      61                 :    *
      62                 :    * 1 <= bias <= range_max.
      63                 :    *
      64                 :    * Aside: bias = range_max is impossible.  Here's why:
      65                 :    *
      66                 :    * Suppose bias = range_max.  Then,
      67                 :    *
      68                 :    * 2^{32}-1 \bmod range_max + 1 = range_max
      69                 :    * 2^{32}-1 \bmod range_max = range_max - 1
      70                 :    * 2^{32}-1 = k range_max + range_max - 1 for some k \in Z.
      71                 :    * 2^{32}-1 = (k+1) range_max - 1
      72                 :    * 2^{32} = (k+1) range_max
      73                 :    *
      74                 :    * Since range_max evenly divides the right hand side, it must
      75                 :    * divide the left.  However, the only divisors of 2^{32} are powers
      76                 :    * of 2.  Thus, range_max must also be a power of 2.  =><=
      77                 :    *
      78                 :    * Therefore, bias \ne range_max.  QED.
      79                 :    *
      80                 :    * post condition:  1 <= bias < range_max.
      81                 :    */
      82                 : 
      83                 : 
      84                 :   do {
      85               3 :     v = (*self->vtbl->GenUint32)(self);
      86                 :     /* v is uniform in [0, 2^{32}) */
      87               3 :   } while (v < bias);
      88                 :   /*
      89                 :    * v is uniform in [bias, 2^{32}).
      90                 :    *
      91                 :    * the number of integers in the half-open interval is
      92                 :    *
      93                 :    *   2^{32} - bias = 2^{32} - ((2^{32}-1 \bmod range_max + 1))
      94                 :    *                 = 2^{32}-1 - (2^{32}-1 \bmod range_max)
      95                 :    *                 = range_max * \lfloor (2^{32}-1)/range_max \rfloor
      96                 :    *
      97                 :    * and range_max clearly divides the size of the range.
      98                 :    *
      99                 :    * The mapping v \rightarrow v % range_max takes values from [bias,
     100                 :    * 2^{32}) to [0, range_max).  Each integer in the range interval
     101                 :    * [0, range_max) will have exactly \lfloor (2^{32}-1)/range_max
     102                 :    * \rfloor preimages from the domain interval.
     103                 :    *
     104                 :    * Therefore, v % range_max is uniform over [0, range_max).  QED.
     105                 :    */
     106                 : 
     107               3 :   return v % range_max;
     108               3 : }