stdlib/tst-arc4random-stats.c

   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>