A TPRF-based pseudo-random number generator

1.1. Contributions

In this work, we present our new BKRNG (ButterKnife PRNG) construction. The design idea of BKRNG is based on the $$ \mathtt{FCRNG}$$^[5] and the NIST standardized $$ \rm{CTR\_DRBG}$$ constructions. The main difference is in the secure and efficient integration of a TPRF as an internal primitive. For our practical instantiation, we suggest the Butterknife TPRF. BKRNG conforms to the notion of a robust PRNG by Dodis et al. ^[2]; thus, it comprises a $$ \mathtt{set up}$$ function for the initial setup, a $$ \mathtt{refresh}$$ function for absorbing random inputs (to recover after a possible internal state compromise) and a $$ \mathtt{next}$$ function for producing pseudo-random outputs.

● Our BKRNG construction is similar to $$ \mathtt{FCRNG}$$. $$ \mathtt{FCRNG}$$ was specified with two variants, $$ \mathtt{FCRNG-c}$$ and $$ \mathtt{FCRNG-t}$$. $$ \mathtt{FCRNG-c}$$ gives the better performance, while $$ \mathtt{FCRNG-t}$$ offers better security. This improvement in security was achieved by changing the tweak for each output block. This was needed to allow for a specific output block to repeat within the same call to the randomness generation function $$ \mathtt{next}$$. While Butterknife does offer tweakability as well, changing the tweak is not required since the individual output blocks are independent by design. For this reason, we chose to design BKRNG similar to the more performant $$ \mathtt{FCRNG-c}$$. By not changing the tweak for each output block, we allow practical implementations to compute the tweakey schedule only once instead of repeatedly refreshing it for each block thus further pushing the performance improvement.

● We provide full security proof for BKRNG in the robustness security game by Dodis et al. ^[2]. The proof bears similarity to the proofs for $$ \mathtt{FCRNG}$$^[5] and $$ \rm{CTR\_DRBG}$$^[4]. Similar to the previous PRNG security proofs, we treat the internal TPRF primitive as ideal, which means that we consider it to be randomly drawn from all possible TPRFs with the same input, output, and tweakey size. Changing the internal primitive to a TPRF required new analysis since both forkciphers and blockciphers are invertible. This change allowed us to prove a security bound for BKRNG that is strictly better than those of $$ \rm{CTR\_DRBG}$$ and $$ \mathtt{FCRNG}$$ (both for $$ \mathtt{FCRNG-c}$$ and $$ \mathtt{FCRNG-t}$$). Compared to $$ \mathtt{FCRNG-c}$$ (with which we also compare the performance in the next paragraph), the security bound of BKRNG improves several constant factors and entirely removes the summand $$ \frac{12pq}{2^n} $$, where $$ p $$ is the number of queries to the $$ \mathtt{set up} $$ and $$ \mathtt{refresh} $$ algorithms and $$ q $$ the number of queries to $$ \mathtt{next} $$. Compared to the analysis of $$ \rm{CTR\_DRBG}$$ by Hoang and Shen ^[4], we additionally eliminated a summand related to the maximum length of each random input and a summand related to the maximum length of each pseudo-random output.

● We implement BKRNG and compare its performance to $$ \mathtt{FCRNG}$$ and $$ \rm{CTR\_DRBG}$$. Our results show that generating pseudo-random output with BKRNG is 30.0% faster than $$ \mathtt{FCRNG}$$ (in its performance-oriented variation $$ \mathtt{FCRNG-c}$$) and 49.2% faster than $$ \rm{CTR\_DRBG}$$. We also used our implementation to run the NIST PRNG test suite and the TestU01 suite and successfully passed all tests.

2.1. Preliminaries

2.1.8. Condensers

A condenser $$\mathtt{Cond}$$^[15] takes a bitstring that has low entropy (i.e., is not uniformly random) and outputs a value that is hard to predict. We follow ^[4] and ^[5] for the subsequent definitions. Let $$ S $$ be a $$ \lambda $$-source, meaning a stateless, probabilistic algorithm that outputs a random input $$ I $$ and some side information $$ z $$, such that $$ \mathrm{H}_{\infty}(I \mid z) \geq \lambda$$. For any adversary $$ \mathcal{A} $$, we define the guessing advantage of $$ \mathcal{A} $$ against condenser $$\mathtt{Cond}$$ with a source $$ S $$ as

$$ \mathtt{Adv}_{\mathtt{Cond }}^{\text{guess}}(\mathcal{A}, S) = \operatorname{Pr}\left[\mathbf{G}_{\mathtt{Cond }}^{\text {guess }}(\mathcal{A}, S)\right] $$

The corresponding game is described in Figure 1.

Figure 1. Security games for a condenser $$ \mathtt{Cond}$$

For any adversary $$ \mathcal{A} $$, the 1-block-guessing advantage of $$ \mathcal{A} $$ against condenser $$\mathtt{Cond}$$ with a source $$ S $$ is defined as

$$ \mathtt{Adv}_{\mathtt{Cond }}^{\text{1-blk-guess}}(\mathcal{A}, S) = \operatorname{Pr}\left[\mathbf{G}_{\mathtt{Cond }}^{\text {1-blk-guess }}(\mathcal{A}, S)\right] $$

The corresponding security game is also described in Figure 1.

2.1.10. Robustness

The game $$\mathbf{G}_{G, \lambda}^{\mathrm{rob}}(\mathcal{A}, \mathcal{D})$$ is defined in Figure 2. It is played for a PRNG $$ G = (\mathtt{set up}, \mathtt{refresh}, \mathtt{next}) $$, an adversary $$ \mathcal{A} $$, and a distribution sampler $$ \mathcal{D} $$, with respect to an entropy threshold $$ \lambda $$. The internal variable $$ c $$ counts the current amount of entropy. While it is too low, the oracle $$ \mathtt{RoR} $$ is designed to be useless to the adversary. Define

$$ \mathtt{Adv}_{G, \lambda}^{\mathrm{rob}}(\mathcal{A}, \mathcal{D}) = 2 * \operatorname{Pr}\left[\mathbf{G}_{G, \lambda}^{\mathrm{rob}}(\mathcal{A}, \mathcal{D})\right]-1 $$

Figure 2. Robustness game (see Fig. 1 in^[4])

2.2. Ideal TPRF

The ideal TPRF model is similar to the ideal cipher model: The TPRF $$ F $$ is modeled as being drawn uniformly randomly from $$ \mathtt{TPRF} (k, t, n, m)$$. In security games, the adversary can query $$ F $$ directly with full control over all parameters.

2.3. Constructions

We present $$\mathtt{BKCond}$$, our new condenser, and BKRNG, our new PRNG.

2.3.1. Condenser $$\mathtt{BKCond}$$

Our construction $$\mathtt{BKCond}$$ (Figure 3), a condenser, is based on $$ \mathtt{FCTRCond}$$^[5]. Instead of using a forkcipher as primitive, we use a TPRF $$ F \in \mathtt{TPRF} (k, t, n, m) $$ with $$ m = 2n $$.

Figure 3. The condenser $$ \mathtt{BKCond}$$ (see Figure 4 in ^[5]). $$ F $$ is a TPRF.

As the main practical instantiation, we will use Butterknife ^[8] (restricted to 2 branches). With this instantiation, we have $$ k + t = 2n $$; thus, the code in Figure 3 will not append any 0's at the end but discard the last bit instead.

2.3.2. Our PRNG BKRNG

In this section, we present our scheme $$ \text{BKRNG} = (\mathtt{set up}, \mathtt{refresh}, \mathtt{next}) $$ (Figure 4), which is designed as a robust PRNG. It is based on FCRNG ^[5] and the NIST standardized $$ \rm{CTR\_DRBG}$$ (see analysis by ^[4]). Our construction is based on a TPRF $$ F $$ instead of a forkcipher (FCRNG) or a blockcipher (CTR-DRBG). As the main practical instantiation, we will use Butterknife ^[8].

Figure 4. The construction $$ \rm{BKRNG}$$. $$ \mathtt{Cond}$$ denotes a condenser, and $$ F $$ is a TPRF. PRFCTR is described in Figure 5.

Figure 5. Algorithm PRFCTR (tPRF CounTeR mode). $$ F $$ is a TPRF. The tweak starts with the 0 bit for domain separation with respect to calls in $$ \mathtt{BKCond}$$.

2.4. Security Proofs

We now give a security proof for $$\mathtt{BKCond}$$, a generic proof for BKRNG, and the security when instantiated with $$\mathtt{BKCond}$$.

2.5. Security of $$\mathtt{BKCond}$$

Theorem 1.Let $$ F $$ be a TPRF that we model as an ideal TPRF. Let $$\mathtt{BKCond}$$ be as described in Figure 3. Let $$ S $$ be a $$ \lambda $$-source that does not have access to $$ F $$. Then, for any adversary $$ \mathcal{A} $$ against $$ \mathtt{BKCond} $$ in the 1-block-guessing game, making at most $$ q $$ guesses has an advantage at most.

To prove this theorem, we will show that $$\mathtt{BKCond}$$ is a good AU-hash. Let $$ \mathtt{BKCond}^* $$ the construction that always returns the first block $$\mathtt{BKCond}$$, i.e., $$ \mathtt{BKCond}^*(I) = \mathtt{BKCond}(I)_{[1:n]} $$.

Lemma 3.Let $$ F $$ be a TPRF that we model as an ideal TPRF. Let $$ \mathtt{BKCond}^* $$ be as described above. Let $$ I_1, I_2 $$ be arbitrary strings s.t. $$ I_1 \neq I_2 $$. Then, $$ \Pr[ \mathtt{BKCond}^*(I_1) = \mathtt{BKCond}^*(I_2) ] \leq \frac{1}{2^n} $$ where the randomness is taken over the choices of $$ F $$.

Proof. Let $$ Y_1, \dots, Y_y $$ be the random variables corresponding to the first blocks of the outputs of the $$ F $$-calls when computing $$ \mathtt{BKCond}^*(I_1) $$. (Thus, $$ \mathtt{BKCond}^*(I_1) = Y_1 \oplus \dots \oplus Y_y $$.) Analogously, let $$ Z_1, \dots, Z_z $$ correspond to the blocks for computing $$ \mathtt{BKCond}^*(I_2) $$. Since $$ I_1 \neq I_2 $$, there is at least one block in $$ I_1 $$ or $$ I_2 $$, which is not present in the other string at that position. Without loss of generality, assume it is the first block of $$ I_1 $$. Let $$ \alpha_{y_2, \dots, y_y, z_1, \dots, z_z} $$ denote $$ Y_2 = y_2, \dots, Y_y = y_y, Z_1 = z_1, \dots, Z_z = z_z $$.

The first equality is due to the law of total probability. The second one follows from the fact that $$ F $$ is called only once with the inputs corresponding to $$ Y_1 $$ (due to the counter value in the tweak, and the two strings being different), and thus an independently randomly sampled value. □

As was done in previous works (e.g., ^{[4, 5]}), we treat the full description of the ideal $$ F $$ as equivalent to a seed. Therefore, Lemma 3 means that $$ \mathtt{BKCond}^* $$ can be viewed as an $$ \delta $$-almost universal hash function, with $$ \delta(l) = 1 $$ for all $$ l \in \mathbb{N} $$.

Lemma 4.Let $$ F $$ be a TPRF that we model as an ideal TPRF. Let $$ \mathtt{BKCond}^* $$ be as described above. Let $$ S $$ be a $$ \lambda $$-source that does not have access to $$ F $$. Then, for any adversary $$ \mathcal{A} $$ against $$ \mathtt{BKCond}^* $$ in the guessing game, making at most $$ q $$ guesses has an advantage at most.

Proof. We use Lemma 2 and apply the result of Lemma 3 (thus $$ \delta(l) = 1 $$). □

From the above lemma, we can immediately derive Theorem 1.

2.6. Security of BKRNG

We will now prove the security of BKRNG. Specifically, we will show that it is a robust PRNG. Our proof strategy is similar to that of Andreeva and Weninger ^[5] and Hoang and Shen ^[4], with the main difference being that the internal primitive is a TPRF in our case (instead of a forkcipher or blockcipher). This means we can avoid classifying a certain set of transcripts as bad in terms of the H-coefficient technique, thus improving security.

First, we define some parameters. We model the TPRF $$ F $$ underlying our construction as ideal. The adversary $$ \mathcal{A} $$ is allowed to make at most $$ q $$ oracle queries, for which they can query $$ F $$ and $$\mathtt{REF, RoR, Get, Set}$$ (see Figure 2). Let $$ \mathcal{D} $$ be a $$ \lambda $$-simple distribution sampler. The number $$ p $$ denotes the maximum number of random inputs $$ I $$ that are produced by $$ \mathcal{D} $$. (Such random inputs are produced in the initial setup of the game $$ \mathtt{Adv}_{G, \lambda}^{\mathrm{rob}}(\mathcal{A}, \mathcal{D}) $$ and the calls to $$ \mathtt{REF} $$.) $$ l_i $$ denotes the maximum block length of the $$ i $$-th random input produced by $$ \mathcal{D} $$.

Theorem 2.Let $$ F $$ be a TPRF that we model as an ideal TPRF. Let $$\mathtt{Cond}$$ be a condenser without access to $$ F $$ and let $$ \mathrm{Adv}_{\mathtt{Cond }}^{1 \text {-blk-guess }}(q', l') $$ denote the maximum advantage against $$ \mathtt{Cond} $$ of any adversary making at most $$ q' $$ queries, where $$ l' $$ is the maximum block length of the random inputs to $$ \mathtt{Cond} $$. Let BKRNG be the construction as defined in Figure 4. Let $$ \mathcal{D} $$ be a $$ \lambda $$-simple distribution sampler and $$ \mathcal{A} $$ be an attacker against the robustness of BKRNG whose accounting of queries is given above. Then

Proof. In our model, we consider computationally unbounded adversaries. For this reason, we are able to treat the adversary $$ \mathcal{A} $$ as deterministic without loss of generality. Let $$\mathtt {S}_{\mathtt {ideal }}$$ and $$\mathtt {S}_{\mathtt {real }}$$ be the systems that model the oracles accessed by $$ \mathcal{A} $$ in $$\mathbf{G}_{G, \lambda}^{\mathrm{rob}}(\mathcal{A}, \mathcal{D})$$ with challenge bit $$ b = 0 $$ and $$ b = 1 $$, respectively.

For our hybrid argument, we create an intermediate game, $$\mathtt {S}_{\mathtt {hybrid }}$$. It behaves similarly to $$\mathtt {S}_{\mathtt {real }}$$ but with some changes. Firstly, when running PRFCTR, instead of using the underlying TPRF $$ F $$, it produces uniformly random bitstrings of length $$ m $$ (i.e., the output length of $$ F $$). Thus, the output of such a PRFCTR call is also uniformly random. However, when the min-entropy level $$ c $$ is lower than the threshold $$ \lambda $$, $$\mathtt {S}_{\mathtt {hybrid }}$$ will still run the original PRFCTR. This is done to prevent trivial attacks. As another change, $$\mathtt {S}_{\mathtt {hybrid }}$$ will keep track of the keys that occur in a list called $$\mathtt {Keys}$$. The resulting pseudocode is shown in Figure 6, together with a similar modification that we apply to $$\mathtt {S}_{\mathtt {real }}$$ (the algorithm is functionally unchanged). We write $$ \mathtt {Keys}(S) $$ with $$ S \in \{\mathtt {S}_{\mathtt {real }}, \mathtt {S}_{\mathtt {hybrid }}\} $$ to denote the corresponding list of system $$ S $$.

Figure 6. Updated $$ \rm{PRFCTR}$$ Algorithm in security proof of $$ \rm{BKRNG}$$.

When looking at $$\mathtt {S}_{\mathtt {hybrid }}$$ and $$\mathtt {S}_{\mathtt {ideal }}$$, one might assume that they are trivially indistinguishable. This is not necessarily the case since $$\mathtt {S}_{\mathtt {ideal }}$$ only idealizes the output of $$\mathtt{next}$$ through the $$\mathtt {RoR}$$ oracle, whereas the updated PRFCTR in $$\mathtt {S}_{\mathtt {hybrid }}$$ influences the other algorithms of the PRNG as well ($$ \mathtt{set up}$$ and $$ \mathtt{refresh}$$). (Recall that $$ \mathcal{A} $$ can obtain the internal state with $$ \mathtt {Get} $$.)

Proof argument. We define four main steps as propositions and prove them afterward.

1. There is an adversary $$ \mathcal{A}^* $$ s.t.

2.

3.

4.

From the above arguments, it follows that

Proof of Item 1. We define $$ \mathcal{A}^* $$ as follows. $$\mathcal{A}^*$$ runs $$ \mathcal{A} $$ and uses its own oracles to answer $$ \mathcal{A} $$'s oracle queries. Whenever $$ \mathcal{A} $$ queries $$\mathtt {RoR}$$, $$\mathcal{A}^*$$ responds with a uniformly random string if $$ c \geq \lambda $$. When $$ \mathcal{A} $$ outputs its final guess $$ b' $$, $$\mathcal{A}^*$$ also outputs $$ b' $$. As a result, if $$\mathcal{A}^*$$ is in the real world, then it perfectly simulates $$\mathtt {S}_{\mathtt {ideal }}$$ for $$ \mathcal{A} $$. On the other hand, if $$\mathcal{A}^*$$ interacts with $$\mathtt {S}_{\mathtt {hybrid }}$$, then $$\mathcal{A}^*$$ perfectly simulates $$\mathtt {S}_{\mathtt {hybrid }}$$ for $$ \mathcal{A} $$.

Proof of bound on$${\mathit{\Delta}_{\mathcal{A}}({\mathtt {S}_{\mathtt {real }}, \mathtt {S}_{\mathtt {hybrid }}})}$$(Item 2): Defining bad transcripts. We will prove this proposition by using the H-coefficient technique.

A transcript is called bad if one of the following conditions happens:

1. The transcript contains a query of $$ \mathcal{A} $$ to $$ F $$ or $$ F^{-1} $$ using some key $$ K \in \mathtt {Keys(S)} $$. In other words, $$ \mathcal{A} $$ was able to guess or derive $$ K $$.

2. There are two identical keys in $$\mathtt {Keys(S)} $$.

We do not need a $$ \mathtt {Bad} $$ event that relates keys used in PRFCTR with keys used by $$\mathtt{Cond}$$ since $$\mathtt{Cond}$$ is required to be independent of $$ F $$. In comparison to the security analysis for similar constructions ^{[4, 5]}, we were able to avoid several bad cases since our real construction is more similar to the ideal one. The reason is that we use the TPRF primitive that gives us general functions instead of permutations (as would be the case for blockciphers/forkciphers^{[4, 5]}).

If a transcript is not bad, then we say that it is good. Let $$\mathcal{T}_{\text {real }}$$ and $$\mathcal{T}_{\text {hybrid}}$$ be the random variable of the transcript for $$\mathtt {S}_{\mathtt {real }}$$ and $$\mathtt {S}_{\mathtt {hybrid }}$$, respectively.

Proof of bound on$${\mathit{\Delta}_{\mathcal{A}}({\mathtt {S}_{\mathtt {real }}, \mathtt {S}_{\mathtt {hybrid }}})}$$: Probability of bad transcripts. We continue by establishing a bound on the chance that $$\mathcal{T}_{\text {hybrid}}$$ is bad. Let $$ \mathtt {Bad}_i $$ be the event that $$\mathcal{T}_{\text {hybrid}}$$ violates the $$ i $$-th condition. By the union bound,

We will start by giving a bound on $$ \Pr[\mathtt {Bad}_1] $$. The keys in $$ \mathtt {Keys}(\mathtt {S}_{\mathtt {hybrid }}) $$ were put there during a call to PRFCTR. They can be categorized as follows:

● Idealized Keys: The key was picked uniformly at random. (This is the case if there was enough entropy $$ c $$ during the previous call to PRFCTR.)

● Normal Keys: This key is the result of

(Indeed, all keys in $$ \mathtt {Keys}(\mathtt {S}_{\mathtt {hybrid }}) $$ that are not idealized must have been derived as described, and in particular, cannot be the result of a call to $$ \mathtt{next} $$. Since $$ K_i \in \mathtt {Keys}(\mathtt {S}_{\mathtt {hybrid }}) $$, we know that $$ c \geq \lambda $$ in the $$ {\rm PRFCTR} $$ call that had $$ K_i $$ as key. Furthermore, we know that in the PRFCTR call before that $$ c < \lambda $$, since $$ K_i $$ is not uniformly random. Because of the fact that $$ c $$ increased, there must have been a call to $$ \mathtt {REF} $$ and, hence, $$ \mathtt{Cond} $$.)

For the idealized keys, the adversary has a probability of $$ q / 2^k $$ to guess a key with a single attempt. The adversary queries $$ F $$ at most $$ q $$ times (in other words $$ q $$ guesses), thus resulting in the probability of less than $$ q^2 / 2^k $$ for the adversary to guess an idealized key.

For each $$ j \leq p $$, let $$ \mathtt {Hit}_1(j) $$ be the event that the key derived from the random input $$ I_j $$ is a normal key, and causes $$ \mathtt {Bad}_1 $$ to happen. From the union bound

For all $$ \mathtt {Hit}_1(j) $$, we know $$ K_j $$ was derived during a $$\mathtt {REF}$$ query, which does not provide any information to $$ \mathcal{A} $$ besides $$ \gamma $$ and $$ z $$ from $$ \mathcal{D} $$. Then, the adversary has the following options for the next query: (a) corrupt the state using $$\mathtt {Get}$$ or $$\mathtt {Set}$$, or (b) use $$\mathtt {\mathtt {REF}}$$ or $$\mathtt {RoR}$$. If (a) is used, then $$ c \gets 0 $$. We can rule out this possibility since $$ K_j $$ is only added to $$\mathtt {Keys}$$ if $$ c \geq \lambda $$. Attempting to use $$\mathtt {REF}$$ to increase $$ c $$ also overrides $$ K_j $$ before it is added to the list. In case (b), note that $$ c \geq \lambda $$ during this next query since we only consider $$ \lambda $$-simple distribution samplers. Hence, $$ K_j $$ is not being used at all and is immediately replaced with a new uniformly random key.

Thus, the only information available to $$ \mathcal{A} $$ for guessing $$ K_j $$ is $$ (\gamma, z) $$. Guessing $$ K_j $$ implies guessing the first block of $$ K_j $$, which is exactly the setting of $$\mathbf{G}_{\mathtt {Cond }}^{1 \text {-blk-guess }}(\mathcal{A}, S)$$.

Therefore, by summing up overall $$ \mathtt {Hit}_1(j) $$, we obtain

We continue by analyzing the probability of $$ \mathtt {Bad}_2 $$. First, consider any idealized key colliding with any other key. The probability for the idealized key to collide with any of the other $$ q $$ keys in the system is at most $$ q/2^k $$. Since there are at most $$ q $$ such keys, the probability of this happening is at most $$ q^2/2^k $$. What remains is the case of two normal keys colliding. For any given normal key, the probability that another normal key is the same is bounded by $$\mathtt{Adv}_{\mathtt {Cond }}{ }^{1 \text {-blk-guess }}(\mathcal{A}, S)$$, similar to the argument regarding $$ \mathtt {Bad}_1 $$. The only difference is that instead of the adversary directly guessing the outcome of $$ \mathtt{Cond}(I) $$, the environment “guesses” the outcome. This results in the same bound;

Summing up, we have

Proof of bound on$$ {\mathit{\Delta}_{\mathcal{A}}({\mathtt {S}_{\mathtt {real }}, \mathtt {S}_{\mathtt {hybrid }}})} $$: Transcript ratio. Let $$ \tau $$ be a good transcript s.t. $$ \Pr[\mathcal{T}_{\text {hybrid}} = \tau] \geq 0 $$. We now prove that

Note that both the adversary $$ \mathcal{A} $$ and the original game environment are deterministic. As such, all randomness of the transcript is determined by the randomness of the distribution sampler $$ \mathcal{D} $$, the random instantiation of $$ F $$, and the random values that $$\mathtt {S}_{\mathtt {hybrid }}$$ produces in the modified PRFCTR (instead of querying $$ F $$).

Thus, we can characterize the relevant probabilities as follows:

where

● $$ \mathtt {Inputs} $$ denote the event that the distribution sampler samples the same values as was done for $$ \tau $$.

● $$\mathtt {Prim}$$ denotes the event that the primitive $$ F $$ agrees with the result of any direct query to $$ F $$ and that it produces the correct values for $$ {\rm PRFCTR} $$ calls where $$ c < \lambda $$.

● $$\mathtt {Coll}_{\mathtt {real }}$$ denotes the event that, in $$ \mathtt {S}_{\mathtt {real }} $$, the randomly chosen $$ F $$ produces the correct values for $$ {\rm PRFCTR} $$ calls where $$ c \geq \lambda $$.

● $$\mathtt {Coll}_{\mathtt {hybrid }}$$ denotes the event that, in $$ \mathtt {S}_{\mathtt {hybrid }} $$, the randomly chosen values in the modified $$ {\rm PRFCTR} $$ comply with the transcript (i.e., when $$ c \geq \lambda $$).

It follows

Let $$ Q $$ be the total number of calls to $$ F $$ of queries for which $$ c \geq \lambda $$ was the case. In $$\mathtt {S}_{\mathtt {hybrid }}$$, these queries are answered in a uniformly (and independently) random way. Thus

Next, we examine $$\mathtt {Coll}_{\mathtt {real }}$$. Due to the definition of a good transcript, we know that there are no two calls to $$ F $$ with the same key and message. Hence

This proves Equation (3).

Wrapping it up. Finally, from Lemma 1, together with Equation (2) and Equation (3), it follows that

Proof of Item 3. This follows immediately from Item 2 since the latter applies to all adversaries, and hence, it applies to adversary $$ \mathcal{A}^* $$ as well.

Proof of Item 4. By the triangle inequality,

□

Theorem 3.Let $$ F $$ be a TPRF that we model as an ideal TPRF. Let $$ ({BKRNG}, \mathtt{BKCond}) $$ denote BKRNG where $$ \mathtt{Cond} $$ is instantiated with $$\mathtt{BKCond}$$. Let $$ \mathcal{D} $$ be a $$ \lambda $$-simple distribution sampler and $$ \mathcal{A} $$ be an adversary attacking this construction whose accounting of queries is given above. Then

Proof sketch. This theorem can be proven in the same way as Theorem 2. Even though BKRNG and $$\mathtt{BKCond}$$ use the same TPRF $$ F $$, the domain separation (i.e., prepending all tweaks with 0 or 1) makes it effectively two independent TPRFs. Thus, we can use the result from Theorem 1.

3.1. Security

The security bound for BKRNG is strictly better than the designs it is based on, i.e., $$ \rm{CTR\_DRBG}$$^[4] and $$ \mathtt{FCRNG}$$^[5] (both for $$ \mathtt{FCRNG-c}$$ and $$ \mathtt{FCRNG-t}$$). Compared to $$ \mathtt{FCRNG-c}$$ (with which we also compare the performance in the next paragraph), the security bound of BKRNG improves several constant factors and entirely removes the summand $$ \frac{12pq}{2^n} $$, where $$ p $$ is the number of queries to the $$ \mathtt{set up} $$ and $$ \mathtt{refresh} $$ algorithms, and $$ q $$ is the number of queries to $$ \mathtt{next} $$. Compared to the analysis of $$ \rm{CTR\_DRBG}$$ by Hoang and Shen ^[4], we additionally eliminated a summand related to the maximum length of each random input and a summand related to the maximum length of each pseudo-random output. We also empirically verified the security of BKRNG using the NIST PRNG test suite as well as the TestU01 suite. BKRNG passed all tests.

3.2. Performance

We implemented BKRNG, $$ \mathtt{FCRNG}$$, and $$ \rm{CTR\_DRBG}$$ in C (without any platform-specific optimizations) and compared their performance. For the TPRF in BKRNG, we chose the Butterknife implementation by Simon Müller ^[17]. For AES in $$ \rm{CTR\_DRBG}$$, we used the TinyAES implementation ^[18], and for $$\mathtt{ForkSkinny}$$ in $$ \mathtt{FCRNG}$$, we used an implementation by Erik Pohle ^[19]. The benchmarks were performed on a 64-bit machine with four CPUs (AMD EPYC 7713 64-Core Processor) and 4 GB of memory that runs Ubuntu 22.04 LTS. Table 1 shows that BKRNG, when generating pseudo-random numbers, performs $$\mathtt{SpeedFork}$$ better than $$ \mathtt{FCRNG}$$ and $$\mathtt{SpeedAES}$$ better than $$ \rm{CTR\_DRBG}$$ (see also Figure 7). The $$ \mathtt{set up}$$ and $$ \mathtt{refresh}$$ algorithms are the fastest for $$ \mathtt{FCRNG-c}$$, followed by BKRNG and then $$ \rm{CTR\_DRBG}$$. These algorithms have little impact on the overall performance of the algorithm since they can be executed during idle times. Even if this is not done, their impact is negligible compared to the cost of $$ \mathtt{next}$$ for most applications (How often an application should refresh depends on the threat model, in particular how often an adversary is assumed to learn something about the internal state, e.g., through side-channels. If this is not a concern, one finds that the NIST SP 800-90A specification allows $$ q = 2^{45} $$$$ \mathtt{next} $$ queries without reseeding for $$ \rm{CTR\_DRBG}$$. For our construction with improved security, each of these queries can even be done for the maximum possible amount of requested bits, i.e., around $$ 2^n $$ blocks of $$ m = 8n $$ bits.).

Figure 7. Comparison of PRNG performances. The requested output size ranged from 100000 to 1000000 bytes (depicted in the $$ x $$-axis).

3.3. Example Output

When initializing the PRNG using the $$ \mathtt{set up}$$ function on the following input, and then calling $$ \mathtt{next}$$ to produce ten bytes of output results in the value given in Table 2.

Acknowledgments

The authors thank the reviewers and the editors for their comments towards improving the article.

Authors’ contributions

Designed the scheme, provided the proof and performed the experimental and theoretical evaluations: Weninger A

Started the project with the initial idea, gave technical feedback at all stages and improved the article's text in terms of editorial quality and structure: Andreeva E

Availability of data and materials

Not applicable.

Financial support and sponsorship

This research was funded in part by the Austrian Science Fund (FWF) project SpyCoDe (No. 10.55776/F85).

Conflicts of interest

All authors declared that there are no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

This manuscript is based on the previous conference paper “A Forkcipher-Based Pseudo-Random Number Generator”^[5]. All authors have approved and agreed on its submission to the journal.

Copyright

© The Author(s) 2024.