Coverage Report

Created: 2025-06-13 06:36

/src/openssl/crypto/rand/rand_uniform.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
3
 *
4
 * Licensed under the Apache License 2.0 (the "License").  You may not use
5
 * this file except in compliance with the License.  You can obtain a copy
6
 * in the file LICENSE in the source distribution or at
7
 * https://www.openssl.org/source/license.html
8
 */
9
10
#include "crypto/rand.h"
11
#include "internal/common.h"
12
13
/*
14
 * Implementation an optimal random integer in a range function.
15
 *
16
 * Essentially it boils down to incrementally generating a fixed point
17
 * number on the interval [0, 1) and multiplying this number by the upper
18
 * range limit.  Once it is certain what the fractional part contributes to
19
 * the integral part of the product, the algorithm has produced a definitive
20
 * result.
21
 *
22
 * Refer: https://github.com/apple/swift/pull/39143 for a fuller description
23
 * of the algorithm.
24
 */
25
uint32_t ossl_rand_uniform_uint32(OSSL_LIB_CTX *ctx, uint32_t upper, int *err)
26
0
{
27
0
    uint32_t i, f;      /* integer and fractional parts */
28
0
    uint32_t f2, rand;  /* extra fractional part and random material */
29
0
    uint64_t prod;      /* temporary holding double width product */
30
0
    const int max_followup_iterations = 10;
31
0
    int j;
32
33
0
    if (!ossl_assert(upper > 0)) {
34
0
        *err = 0;
35
0
        return 0;
36
0
    }
37
0
    if (ossl_unlikely(upper == 1))
38
0
        return 0;
39
40
    /* Get 32 bits of entropy */
41
0
    if (RAND_bytes_ex(ctx, (unsigned char *)&rand, sizeof(rand), 0) <= 0) {
42
0
        *err = 1;
43
0
        return 0;
44
0
    }
45
46
    /*
47
     * We are generating a fixed point number on the interval [0, 1).
48
     * Multiplying this by the range gives us a number on [0, upper).
49
     * The high word of the multiplication result represents the integral
50
     * part we want.  The lower word is the fractional part.  We can early exit if
51
     * if the fractional part is small enough that no carry from the next lower
52
     * word can cause an overflow and carry into the integer part.  This
53
     * happens when the fractional part is bounded by 2^32 - upper which
54
     * can be simplified to just -upper (as an unsigned integer).
55
     */
56
0
    prod = (uint64_t)upper * rand;
57
0
    i = prod >> 32;
58
0
    f = prod & 0xffffffff;
59
0
    if (ossl_likely(f <= 1 + ~upper))    /* 1+~upper == -upper but compilers whine */
60
0
        return i;
61
62
    /*
63
     * We're in the position where the carry from the next word *might* cause
64
     * a carry to the integral part.  The process here is to generate the next
65
     * word, multiply it by the range and add that to the current word.  If
66
     * it overflows, the carry propagates to the integer part (return i+1).
67
     * If it can no longer overflow regardless of further lower order bits,
68
     * we are done (return i).  If there is still a chance of overflow, we
69
     * repeat the process with the next lower word.
70
     *
71
     * Each *bit* of randomness has a probability of one half of terminating
72
     * this process, so each each word beyond the first has a probability
73
     * of 2^-32 of not terminating the process.  That is, we're extremely
74
     * likely to stop very rapidly.
75
     */
76
0
    for (j = 0; j < max_followup_iterations; j++) {
77
0
        if (RAND_bytes_ex(ctx, (unsigned char *)&rand, sizeof(rand), 0) <= 0) {
78
0
            *err = 1;
79
0
            return 0;
80
0
        }
81
0
        prod = (uint64_t)upper * rand;
82
0
        f2 = prod >> 32;
83
0
        f += f2;
84
        /* On overflow, add the carry to our result */
85
0
        if (f < f2)
86
0
            return i + 1;
87
        /* For not all 1 bits, there is no carry so return the result */
88
0
        if (ossl_likely(f != 0xffffffff))
89
0
            return i;
90
        /* setup for the next word of randomness */
91
0
        f = prod & 0xffffffff;
92
0
    }
93
    /*
94
     * If we get here, we've consumed 32 * max_followup_iterations + 32 bits
95
     * with no firm decision, this gives a bias with probability < 2^-(32*n),
96
     * which is likely acceptable.
97
     */
98
0
    return i;
99
0
}
100
101
uint32_t ossl_rand_range_uint32(OSSL_LIB_CTX *ctx, uint32_t lower, uint32_t upper,
102
                                int *err)
103
0
{
104
0
    if (!ossl_assert(lower < upper)) {
105
0
        *err = 1;
106
0
        return 0;
107
0
    }
108
0
    return lower + ossl_rand_uniform_uint32(ctx, upper - lower, err);
109
0
}