1  /* Statistical tests for arc4random-related functions.
       2     Copyright (C) 2022-2023 Free Software Foundation, Inc.
       3     This file is part of the GNU C Library.
       4  
       5     The GNU C Library is free software; you can redistribute it and/or
       6     modify it under the terms of the GNU Lesser General Public
       7     License as published by the Free Software Foundation; either
       8     version 2.1 of the License, or (at your option) any later version.
       9  
      10     The GNU C Library is distributed in the hope that it will be useful,
      11     but WITHOUT ANY WARRANTY; without even the implied warranty of
      12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      13     Lesser General Public License for more details.
      14  
      15     You should have received a copy of the GNU Lesser General Public
      16     License along with the GNU C Library; if not, see
      17     <https://www.gnu.org/licenses/>.  */
      18  
      19  #include <array_length.h>
      20  #include <stdbool.h>
      21  #include <stdio.h>
      22  #include <stdlib.h>
      23  #include <stdint.h>
      24  #include <string.h>
      25  #include <support/check.h>
      26  
      27  enum
      28  {
      29    arc4random_key_size = 32
      30  };
      31  
      32  struct key
      33  {
      34    unsigned char data[arc4random_key_size];
      35  };
      36  
      37  /* With 12,000 keys, the probability that a byte in a predetermined
      38     position does not have a predetermined value in all generated keys
      39     is about 4e-21.  The probability that this happens with any of the
      40     16 * 256 possible byte position/values is 1.6e-17.  This results in
      41     an acceptably low false-positive rate.  */
      42  enum { key_count = 12000 };
      43  
      44  static struct key keys[key_count];
      45  
      46  /* Used to perform the distribution check.  */
      47  static int byte_counts[arc4random_key_size][256];
      48  
      49  /* Bail out after this many failures.  */
      50  enum { failure_limit = 100 };
      51  
      52  static void
      53  find_stuck_bytes (bool (*func) (unsigned char *key))
      54  {
      55    memset (&keys, 0xcc, sizeof (keys));
      56  
      57    int failures = 0;
      58    for (int key = 0; key < key_count; ++key)
      59      {
      60        while (true)
      61          {
      62            if (func (keys[key].data))
      63              break;
      64            ++failures;
      65            if (failures >= failure_limit)
      66              {
      67                printf ("warning: bailing out after %d failures\n", failures);
      68                return;
      69              }
      70          }
      71      }
      72    printf ("info: key generation finished with %d failures\n", failures);
      73  
      74    memset (&byte_counts, 0, sizeof (byte_counts));
      75    for (int key = 0; key < key_count; ++key)
      76      for (int pos = 0; pos < arc4random_key_size; ++pos)
      77        ++byte_counts[pos][keys[key].data[pos]];
      78  
      79    for (int pos = 0; pos < arc4random_key_size; ++pos)
      80      for (int byte = 0; byte < 256; ++byte)
      81        if (byte_counts[pos][byte] == 0)
      82          {
      83            support_record_failure ();
      84            printf ("error: byte %d never appeared at position %d\n", byte, pos);
      85          }
      86  }
      87  
      88  /* Test adapter for arc4random.  */
      89  static bool
      90  generate_arc4random (unsigned char *key)
      91  {
      92    uint32_t words[arc4random_key_size / 4];
      93    _Static_assert (sizeof (words) == arc4random_key_size, "sizeof (words)");
      94  
      95    for (int i = 0; i < array_length (words); ++i)
      96      words[i] = arc4random ();
      97    memcpy (key, &words, arc4random_key_size);
      98    return true;
      99  }
     100  
     101  /* Test adapter for arc4random_buf.  */
     102  static bool
     103  generate_arc4random_buf (unsigned char *key)
     104  {
     105    arc4random_buf (key, arc4random_key_size);
     106    return true;
     107  }
     108  
     109  /* Test adapter for arc4random_uniform.  */
     110  static bool
     111  generate_arc4random_uniform (unsigned char *key)
     112  {
     113    for (int i = 0; i < arc4random_key_size; ++i)
     114      key[i] = arc4random_uniform (256);
     115    return true;
     116  }
     117  
     118  /* Test adapter for arc4random_uniform with argument 257.  This means
     119     that byte 0 happens more often, but we do not perform such a
     120     statistical check, so the test will still pass */
     121  static bool
     122  generate_arc4random_uniform_257 (unsigned char *key)
     123  {
     124    for (int i = 0; i < arc4random_key_size; ++i)
     125      key[i] = arc4random_uniform (257);
     126    return true;
     127  }
     128  
     129  static int
     130  do_test (void)
     131  {
     132    puts ("info: arc4random implementation test");
     133    find_stuck_bytes (generate_arc4random);
     134  
     135    puts ("info: arc4random_buf implementation test");
     136    find_stuck_bytes (generate_arc4random_buf);
     137  
     138    puts ("info: arc4random_uniform implementation test");
     139    find_stuck_bytes (generate_arc4random_uniform);
     140  
     141    puts ("info: arc4random_uniform implementation test (257 variant)");
     142    find_stuck_bytes (generate_arc4random_uniform_257);
     143  
     144    return 0;
     145  }
     146  
     147  #include <support/test-driver.c>