Can PSRNG be made by block ciphers?

by Emmanuel Udofia / Monday, 05 August 2024 / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Applications of block ciphers, Modes of operation for block ciphers

The question of whether a Pseudorandom Number Generator (PSRNG or PRNG) can be constructed using block ciphers is one of significant interest within the field of cryptography. Block ciphers are fundamental cryptographic primitives that are widely used for securing data through encryption. A block cipher takes a fixed-size block of plaintext and a key as input and produces a fixed-size block of ciphertext as output. Some of the most well-known block ciphers include the Advanced Encryption Standard (AES), Data Encryption Standard (DES), and Triple DES (3DES).

To understand how a block cipher can be used to create a PSRNG, it is essential to first grasp the basic properties and functionality of both block ciphers and pseudorandom number generators.

A pseudorandom number generator is an algorithm that produces a sequence of numbers that only approximate the properties of random numbers. The sequence generated by a PSRNG should be deterministic, meaning that given the same initial seed, it will always produce the same sequence of numbers. This determinism is important for applications where reproducibility is necessary, such as in simulations and cryptographic protocols.

The security of a PSRNG depends on its ability to produce sequences that are indistinguishable from true random sequences to any polynomial-time adversary. This property is known as cryptographic security. Therefore, a cryptographically secure PSRNG (CSPRNG) must satisfy the following criteria:

1. Deterministic: The same seed will always produce the same sequence.
2. Unpredictability: Without knowledge of the seed, it should be computationally infeasible to predict any future output of the generator.
3. Indistinguishability: The output should be indistinguishable from a truly random sequence.

Block ciphers can be leveraged to create a PSRNG through various modes of operation. Modes of operation are techniques that extend the use of a block cipher to provide security for data of arbitrary length and can also be adapted to generate pseudorandom sequences. Some of the common modes of operation that can be utilized for this purpose include:

1. Counter (CTR) Mode: In CTR mode, a block cipher is used to encrypt a counter value. The counter is incremented for each block of output needed. This mode is particularly well-suited for generating pseudorandom numbers because it transforms a simple, linear counter into a complex, pseudorandom sequence using the block cipher.

2. Output Feedback (OFB) Mode: OFB mode uses the block cipher to generate a keystream that can be used to encrypt data. The keystream itself is generated by repeatedly encrypting an initialization vector (IV) and then using the output as the next input to the block cipher. This mode can be adapted to generate a pseudorandom sequence by using the block cipher output directly.

3. Cipher Feedback (CFB) Mode: Similar to OFB mode, CFB mode generates a keystream by encrypting an IV and then using portions of the output to generate the next input. The keystream can be used as a pseudorandom sequence.

4. Electronic Codebook (ECB) Mode: While ECB mode is not suitable for data encryption due to its lack of diffusion and susceptibility to pattern attacks, it can be used in a limited way to generate pseudorandom numbers by encrypting a sequence of counter values or other structured inputs.

Let us consider the specifics of how block ciphers can be used in these modes to create a pseudorandom number generator.

Counter (CTR) Mode

In CTR mode, the block cipher encrypts a counter value that is incremented for each block of output. The general process is as follows:

1. Initialization: Choose an initial counter value (CTR_0) and a secret key (K).
2. Encryption: For each block of output, increment the counter and encrypt it using the block cipher with the secret key:

$\text{Output}_i = \text{Encrypt}_{K}(\text{CTR}_i)$

where $\text{CTR}_i = \text{CTR}_0 + i$ .

3. Pseudorandom Sequence: The sequence of encrypted counter values forms the pseudorandom sequence.

CTR mode has several advantages for generating pseudorandom numbers. It is highly parallelizable, meaning that multiple blocks can be generated simultaneously, which is useful for high-performance applications. Additionally, the use of a counter ensures that the sequence is deterministic and repeatable, as required for a PSRNG.

Output Feedback (OFB) Mode

In OFB mode, the block cipher generates a keystream by repeatedly encrypting an initialization vector (IV). The process is as follows:

1. Initialization: Choose an initial IV and a secret key (K).
2. Keystream Generation: Encrypt the IV using the block cipher and use the output as the next input:

$\text{IV}_0 = \text{IV}$

$\text{Output}_i = \text{Encrypt}_{K}(\text{IV}_{i-1})$

$\text{IV}_i = \text{Output}_i$

3. Pseudorandom Sequence: The sequence of outputs forms the pseudorandom sequence.

OFB mode is advantageous for generating pseudorandom numbers because it ensures that the same IV and key will always produce the same sequence, fulfilling the determinism requirement. Additionally, the feedback mechanism ensures that the output sequence is complex and difficult to predict.

Cipher Feedback (CFB) Mode

CFB mode is similar to OFB mode but with a slight variation in how the input to the block cipher is generated. The process is as follows:

1. Initialization: Choose an initial IV and a secret key (K).
2. Keystream Generation: Encrypt the IV using the block cipher and use a portion of the output as the next input:

$\text{IV}_0 = \text{IV}$

$\text{Output}_i = \text{Encrypt}_{K}(\text{IV}_{i-1})$

$\text{IV}_i = \text{Output}_i \text{ (truncated)}$

3. Pseudorandom Sequence: The sequence of outputs forms the pseudorandom sequence.

CFB mode can be used to generate pseudorandom numbers, but it is generally less efficient than CTR and OFB modes due to the feedback mechanism, which can introduce dependencies between blocks.

Electronic Codebook (ECB) Mode

ECB mode is the simplest mode of operation for a block cipher. In ECB mode, each block of plaintext is encrypted independently using the same key. While ECB mode is not suitable for encrypting data due to its lack of diffusion and susceptibility to pattern attacks, it can be used to generate pseudorandom numbers by encrypting a sequence of structured inputs, such as counter values or other deterministic sequences.

The process is as follows:

1. Initialization: Choose a secret key (K).
2. Encryption: For each block of output, encrypt a structured input using the block cipher with the secret key:

$\text{Input}_i = \text{structured value (e.g., counter)}$

$\text{Output}_i = \text{Encrypt}_{K}(\text{Input}_i)$

3. Pseudorandom Sequence: The sequence of encrypted inputs forms the pseudorandom sequence.

While ECB mode can be used to generate pseudorandom numbers, it is generally not recommended due to its lack of security properties compared to other modes of operation.

Security Considerations

When using block ciphers to generate pseudorandom numbers, it is important to consider the security properties of the chosen mode of operation. The generated sequence must be indistinguishable from a truly random sequence and unpredictable without knowledge of the secret key and initial parameters (e.g., IV or counter).

1. Key Management: The security of the pseudorandom sequence depends on the secrecy of the key. If the key is compromised, the entire sequence can be predicted.

2. Initialization Vector (IV) or Counter: The choice of IV or counter is critical. Reusing the same IV or counter with the same key can lead to security vulnerabilities. It is essential to ensure that the IV or counter is unique for each session or instance of the PSRNG.

3. Block Cipher Security: The underlying block cipher must be secure. Weaknesses in the block cipher can compromise the security of the pseudorandom sequence. It is recommended to use well-established and widely analyzed block ciphers such as AES.

Example: Using AES in CTR Mode to Create a PSRNG

To illustrate how a block cipher can be used to create a PSRNG, consider the example of using AES in CTR mode:

1. Initialization: Choose a 128-bit secret key (K) and an initial counter value (CTR_0).

2. Encryption: For each block of output, increment the counter and encrypt it using AES with the secret key:

$\text{Output}_i = \text{AES}_{K}(\text{CTR}_i)$

where $\text{CTR}_i = \text{CTR}_0 + i$ .

3. Pseudorandom Sequence: The sequence of encrypted counter values forms the pseudorandom sequence.

The resulting sequence will be a series of 128-bit blocks that are pseudorandom and suitable for use in cryptographic applications. The security of the sequence relies on the secrecy of the key and the uniqueness of the counter values.

Block ciphers can indeed be used to create pseudorandom number generators through various modes of operation. CTR, OFB, and CFB modes are particularly well-suited for this purpose, as they provide the necessary properties of determinism, unpredictability, and indistinguishability. The choice of mode and the management of keys and initialization parameters are critical to ensure the security of the generated pseudorandom sequence. By leveraging the strength of well-established block ciphers such as AES, it is possible to construct a robust and secure PSRNG suitable for a wide range of cryptographic applications.

EITCA Academy