# A TPRF-based pseudo-random number generator

*J Surveill Secur Saf*2024;5:36-51.

## Abstract

Most cryptographic applications use randomness that is generated by pseudo-random number generators (PRNGs). A popular PRNG practical choice is the NIST standardized

Furthermore, we show the *multi-branch* expanding nature of Butterknife contributes to a significant speed-up in the efficiency of BKRNG compared to

## Keywords

*,*pseudo-random number generation

*,*tweakable PRF

## 1. INTRODUCTION

Good randomness is needed for almost all cryptographic protocols. Physical true randomness sampling devices usually do not produce perfectly uniform outputs, but more importantly, they are too slow for many practical applications. For this reason, pseudo-random number generators (PRNGs) are used. They expand high entropy bitstrings into longer bitstrings that are indistinguishable from uniform random. PRNGs are of high practical and theoretical interest.

Barak and Halevi ^{[1]} are the first to propose a theoretical model that defines how a PRNG recovers from a state compromise when it is given good randomness in the so-called refresh algorithm. Prior to that, PRNGs were treated as single functions that take a uniformly random seed as input to produce a single (long) output. In 2013, Dodis *et al*. ^{[2]} extended the model of Barak and Halevi so as to not require the PRNG to fully recover in a single call to the refresh algorithm. Instead, their model allows the PRNG to slowly accumulate randomness over the course of many calls to the refresh algorithm, which is the commonly accepted security model at present.

In terms of practical PRNGs, NIST recommends several PRNGs in their SP 800-90A standard. Among these, the AES-based *et al*. ^{[3]} noted that 67.8% of all certified implementations from NIST's Cryptographic Module Validation Program (CMVP) in 2019 supported ^{[4]}. The ^{[4]}), without a clear justification for its provable security.

In 2023, Andreeva and Weninger ^{[5]} proposed a new PRNG called *et al*. ^{[6]}). ^{[6]}, are based on existing tweakable blockciphers, such as Skinny ^{[7]}. A forkcipher produces the output more efficiently than two evaluations of the corresponding tweakable block cipher. The expanding nature of forkciphers makes them a natural fit for PRNGs. Similar to PRNGs which expand by designing a short high entropy string into a longer pseudo-random output, forkciphers expand their input. As a result, the ^{[5]}.

On the other hand, tweakable Pseudo-Random Functions (TPRF) are a type of expandable primitives that have only forward evaluating functionality. A recent instance of a TPRF is the Butterknife ^{[8]} construction. Butterknife offers eight-fold (^{[9]} and thus reuses internally the AES structure. Hence, it can utilize existing implementation optimizations, such as the Intel AES-NI. All these Butterknife features can be advantageous when it comes to generating pseudo-random outputs. Butterknife is already used for efficient key derivation in the Signal protocol^{[10]}. Another natural Butterknife application is in generalized CTR mode encryption ^{[11]}.

### 1.1. Contributions

In this work, we present our new BKRNG (ButterKnife PRNG) construction. The design idea of BKRNG is based on the ^{[5]} and the NIST standardized *et al*. ^{[2]}; thus, it comprises a

● Our BKRNG construction is similar to

● 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 ^{[5]} and ^{[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 ^{[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

## 2. METHODS

### 2.1. Preliminaries

#### 2.1.1. Notation

Let

#### 2.1.2. Blockciphers and Forkciphers

A blockcipher

Following ^{[6]}, a forkcipher is a pair of deterministic algorithms, the forward encrypting and inverse algorithms, respectively:

Note that we use *correctness condition* if for every

1.

2.

3.

4.

For each pair of a key and a tweak, the forkcipher applies two independent permutations to the input to produce the two output blocks. We use the shorthand

#### 2.1.3. Almost Universal (AU) Hash

Let *block length* to be *almost universal* hash if for every distinct strings

#### 2.1.4. Conditional Min-Entropy and Statistical Distance

For two random variables *(average-case) conditional min-entropy* of

The *statistical distance* between two random variables

#### 2.1.5. Systems, Transcripts and the H-coefficient Proof Technique

Following ^{[4, 12]}, we consider the interactions of a distinguisher

For any systems

Following ^{[4]}, we now describe the H-coefficient technique of Patarin ^{[13, 14]}. Generically, it considers a deterministic distinguisher

**Lemma 1** (see ^{[13, 14]}). *Suppose we can partition the set of valid transcripts for the ideal system into good and bad ones. Further, suppose that there exists *

#### 2.1.6. Pseudo-Random Functions

A TPRF is a keyed function

Let

#### 2.1.7. PRNG

We recall the security definition by Dodis *et al*. ^{[2]}. A PRNG with input

●

●

●

For our constructions, we will not have an explicit seed but rather treat the full description of the idealized primitives (in our case, an ideal TPRF ^{[4, 5]}).

#### 2.1.8. Condensers

A condenser ^{[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

The corresponding game is described in Figure 1.

For any adversary

The corresponding security game is also described in Figure 1.

#### 2.1.9. Distribution Samplers

Distribution samplers are similar to

We say that sampler *legitimate* if ^{[4]}, in this work, we will only consider simple samplers for a sufficiently large min-entropy threshold

#### 2.1.10. Robustness

The game

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

#### 2.1.11. Generalized Leftover Hash Lemma

**Lemma 2** (Generalized Leftover Hash Lemma^{[4]}). *Let *

Lemma 2 was first stated this way by Hoang and Shen ^{[4]} and was originally proven by Barak *et al*. ^{[16]}. We use the same security game ^{[4]}; thus, we can adopt this version of the notion.

### 2.2. Ideal TPRF

The ideal TPRF model is similar to the ideal cipher model: The TPRF

### 2.3. Constructions

We present

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

Our construction ^{[5]}. Instead of using a forkcipher as primitive, we use a TPRF

Figure 3. The condenser ^{[5]}).

As the main practical instantiation, we will use Butterknife ^{[8]} (restricted to 2 branches). With this instantiation, we have

#### 2.3.2. Our PRNG BKRNG

In this section, we present our scheme ^{[5]} and the NIST standardized ^{[4]}). Our construction is based on a TPRF ^{[8]}.

Figure 4. The construction

### 2.4. Security Proofs

We now give a security proof for

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

**Theorem 1.***Let *

To prove this theorem, we will show that

**Lemma 3.***Let *

*Proof.* Let

The first equality is due to the law of total probability. The second one follows from the fact that

As was done in previous works (e.g., ^{[4, 5]}), we treat the full description of the ideal

**Lemma 4.***Let *

*Proof.* We use Lemma 2 and apply the result of Lemma 3 (thus

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

**Theorem 2.***Let *

*Proof.* In our model, we consider computationally unbounded adversaries. For this reason, we are able to treat the adversary

For our hybrid argument, we create an intermediate game,

When looking at

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

1. There is an adversary

2.

3.

4.

From the above arguments, it follows that

**Proof of Item 1.** We define

**Proof of bound on****(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

2. There are two identical keys in

We do not need a ^{[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

**Proof of bound on****: Probability of bad transcripts.** We continue by establishing a bound on the chance that

We will start by giving a bound on

● **Idealized Keys:** The key was picked uniformly at random. (This is the case if there was enough entropy

● **Normal Keys:** This key is the result of

(Indeed, all keys in

For the idealized keys, the adversary has a probability of

For each

For all

Thus, the only information available to

Therefore, by summing up overall

We continue by analyzing the probability of

Summing up, we have

**Proof of bound on****: Transcript ratio.** Let

Note that both the adversary

Thus, we can characterize the relevant probabilities as follows:

where

●

●

●

●

It follows

Let

Next, we examine

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

**Proof of Item 4.** By the triangle inequality,

**Theorem 3.***Let *

**Proof sketch.** This theorem can be proven in the same way as Theorem 2. Even though BKRNG and

## 3. RESULTS AND DISCUSSION

### 3.1. Security

The security bound for BKRNG is strictly better than the designs it is based on, i.e., ^{[4]} and ^{[5]} (both for ^{[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, ^{[17]}. For AES in ^{[18]}, and for ^{[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

Runtimes of different PRNG implementations in CPU cycles. Setup and refresh were called with 24 bytes; next was called to produce 1000000 bytes. The final column lists the cycles per produced byte

setup | refresh | next | next (c/b) | |

BKRNG | 89372 | 82166 | 277957107 | 277.96 |

FCRNG-c | 44668 | 34646 | 396987185 | 396.99 |

CTR_DRBG | 134121 | 126986 | 546715525 | 546.72 |

### 3.3. Example Output

When initializing the PRNG using the

Example input and output (all values given in hexadecimal format)

Input | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | ||

Output | 70 | af | ef | e9 | 6f | d4 | 03 | ee | 10 | 78 |

## DECLARATIONS

### 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.

## REFERENCES

1. Barak B, Halevi S. A model and architecture for pseudo-random generation with applications to /dev/random. In: Atluri V, Meadows C, Juels A, editors. CCS '05: Proceedings of the 12th ACM conference on Computer and communications security. New York, NY, USA: ACM Press; 2005. pp. 203-12.

2. Dodis Y, Pointcheval D, Ruhault S, Vergnaud D, Wichs D. Security analysis of pseudo-random number generators with input: /dev/random is not robust. In: Sadeghi AR, Gligor V, Yung M, editors. CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. Berlin, Germany: ACM Press; 2013. pp. 647-58.

3. Cohney S, Kwong A, Paz S, et al. Pseudorandom black swans: cache attacks on CTR_DRBG. In: 2020 IEEE Symposium on Security and Privacy (SP); 2020 May 18-21; San Francisco, CA, USA. IEEE; 2020. pp. 1241-58.

4. Hoang VT, Shen Y. Security analysis of NIST CTR-DRBG. In: Micciancio D, Ristenpart T, editors. Advances in cryptology - CRYPTO 2020, Part I. Lecture notes in computer science. Cham: Springer; 2020. pp. 218-47.

5. Andreeva E, Weninger A. A forkcipher-based pseudo-random number generator. In: Tibouchi M, Wang X, editors. Applied cryptography and network security. ACNS 2023. Lecture notes in computer science, vol 13906. Cham: Springer; 2023. pp. 3-31.

6. Andreeva E, Lallemand V, Purnal A, Reyhanitabar R, Roy A, Vizár D. Forkcipher: a new primitive for authenticated encryption of very short messages. In: Galbraith SD, Moriai S, editors. Advances in cryptology - ASIACRYPT 2019. Lecture notes in computer science, vol 11922. Cham: Springer; 2019. pp. 153-82.

7. Beierle C, Jean J, Kölbl S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw M, Katz J, editors. Advances in cryptology - CRYPTO 2016, Part Ⅱ. Lecture notes in computer science, vol. 9815. Heidelberg, Germany: Springer; 2016. pp. 123-53.

8. Andreeva E, Cogliati B, Lallemand V, Minier M, Purnal A, Roy A. Masked iterate-fork-iterate: a new design paradigm for tweakable expanding pseudorandom function. 2022. Available from: https://eprint.iacr.org/2022/1534.[Last accessed on 22 Jan 2024].

10. Bhati AS, Dufka A, Andreeva E, Roy A, Preneel B. Skye: an expanding PRF based fast KDF and its applications. 2023. Available from: https://eprint.iacr.org/2023/781.[Last accessed on 22 Jan 2024].

11. Andreeva E, Bhati AS, Preneel B, Vizár D. 1, 2, 3, Fork: counter mode variants based on a generalized forkcipher. *IACR Trans Symmetric Cryptol* 2021;2021:1-35.

12. Hoang VT, Tessaro S. Key-alternating ciphers and key-length extension: exact bounds and multi-user security. In: Robshaw M, Katz J, editors. Advances in cryptology - CRYPTO 2016. Lecture notes in computer science, vol. 9814. Berlin, Heidelberg: Springer; 2016. pp. 3-32.

13. Chen S, Steinberger J. Tight security bounds for key-alternating ciphers. In: Nguyen PQ, Oswald E, editors. Advances in cryptology - EUROCRYPT 2014. Lecture Notes in Computer Science, vol. 8441. Berlin, Heidelberg: Springer; 2014. pp. 327-50.

14. Patarin J. The "Coefficients H" technique. In: Avanzi RM, Keliher L, Sica F, editors. Selected areas in cryptography. Berlin, Heidelberg: Springer; 2009. pp. 328-45.

15. Raz R, Reingold O. On recycling the randomness of states in space bounded computation. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing. Atlanta, GA, USA: ACM Press; 1999. pp. 159-68.

16. Barak B, Dodis Y, Krawczyk H, et al. Leftover Hash Lemma, revisited. In: Rogaway P, editor. Advances in cryptology - CRYPTO 2011. Lecture notes in computer science, vol. 6841. Berlin, Heidelberg: Springer; 2011. pp. 1-20.

17. Müller S. Butterknife;. Accessed: 2023-10-12. Available from: https://github.com/n0900/BC__Butterknife.

18. kokke. Tiny AES in C. https://github.com/kokke/tiny-AES-c.[Last accessed on 22 Jan 2024].

19. Pohle E. ForkSkinny-C. https://github.com/ErikP0/forkskinny-c.[Last accessed on 22 Jan 2024].

## Cite This Article

## How to Cite

Andreeva, E.; Weninger A. A TPRF-based pseudo-random number generator. *J. Surveill. Secur. Saf.* **2024**, *5*, 36-51. http://dx.doi.org/10.20517/jsss.2023.45

## Download Citation

## Export Citation File:

## Type of Import

### Tips on Downloading Citation

### Citation Manager File Format

### Type of Import

**Direct Import:**When the Direct Import option is selected (the default state), a dialogue box will give you the option to Save or Open the downloaded citation data. Choosing Open will either launch your citation manager or give you a choice of applications with which to use the metadata. The Save option saves the file locally for later use.

**Indirect Import:**When the Indirect Import option is selected, the metadata is displayed and may be copied and pasted as needed.

## About This Article

### Special Issue

### Copyright

**Open Access**This article is licensed under a Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, sharing, adaptation, distribution and reproduction in any medium or format, for any purpose, even commercially, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

## Data & Comments

### Data

**Views**

**Downloads**

**Citations**

**Comments**

**15**

### Comments

Comments must be written in English. Spam, offensive content, impersonation, and private information will not be permitted. If any comment is reported and identified as inappropriate content by OAE staff, the comment will be removed without notice. If you have any queries or need any help, please contact us at support@oaepublish.com.

^{0}