Stream Ciphers: Cryptography for CTFs

Stream ciphers operate on each bit of data in the message rather than on a chunk of data at a time. Encryption and decryption are straightforward with stream ciphers, which use the same keystream for both processes. Stream ciphers are inherently simple, involving only XOR operations for both encryption and decryption, using the same keystream each time.

OTP (One Time Pad)

The One Time Pad (OTP) is a type of stream cipher, but it has been deemed impractical for long-term use. In OTP, a user encrypts a message by XORing it with a secret key message.

The vulnerability of OTP lies in its XOR operations and properties. It has been observed that if multiple ciphertexts are generated using the same key, an attacker could potentially reverse engineer the ciphertext to recover the plaintext.

The above code demonstrates how the XOR operation can be used to obtain the plaintext from ciphertext, with the help of a key. If the same key is used multiple times, and the attacker possesses any pair of ciphertext and plaintext, they can deduce the key and use it to decrypt other ciphertexts.

Issues with mitigation of the OTP

To mitigate the above vulnerability, we would need to generate a new key every time we encrypt data. However, constantly generating a new key with the same number of bits as the message would be labour-intensive. If a new keystream is used each time, then OTP becomes unconditionally secure. Its keystream is generated from a truly random number generator (TRNG). Therefore, this necessitates the adoption of newer encryption techniques.

Use of PRNG

The key part of a Stream Cipher is generating the keystream, which should consist of random numbers. A PRNG (Pseudo-Random Number Generator) can be utilized for this purpose. It is designed to generate pseudo-random numbers using an algorithm and an initial seed (initial number sequence), approximating truly random numbers.

In the diagram below, we denote the keystream as S to illustrate the operation of the Stream Cipher. Modulo 2 arithmetic is employed to obtain either 0 or 1 for each bit of the message. Modulo 2 addition refers to the XOR operation.

The diagram below represents the generation of the key stream.

Modular arithmetic and Rings are important concepts required to understand the formation of equations.

LCG (Linear Congruential Generators)

The above code shows the encryption process, which involves generating keys using LCG (Linear Congruential Generators), an example of PRNG.

The above code shows the decryption process of ciphertext text with keys generated using LCG.

The above code demonstrates an attack on LCG, where A and B (which are parts of the keys) are calculated using only the first few characters of the plaintext and ciphertext. The attack utilizes the Extended Euclidean algorithm to determine the modular inverse of a number.

The code comments depict the calculation of A and B values. This underscores the necessity of finding the modular inverse of (S1 – S2), where S1, S2, and S3 represent initial segments of the keystream.

If the attacker knows the first three values of the plaintext stream, they can compute the corresponding first three values of the keystream using XOR operations with the ciphertext stream. This approach would unveil the constant values of the encryption equation (A and B), enabling the computation of all subsequent keystream values.

LFSR (Linear Feedback Shift Register)

It employs a Stream Cipher that can operate on small hardware, specifically with low power consumption. This cipher generates pseudo-random numbers that are even more difficult to crack.

Below is a diagram illustrating a general LFSR (Linear Feedback Shift Register).

For the attack on LFSR to succeed, the attacker needs the complete encrypted text, the degree of the LFSR (denoted by ‘m’), and the first ‘2m’ plaintext values, which might include the header part. From these values, the attacker can derive the LFSR configuration.

The keystream Si can be computed from 0 to 2m-1 using this information. To calculate S2m, an algebraic equation can be formulated using the following equation, where Pi can be either 0 or 1.

The Gaussian elimination technique can be utilized to determine all the values of P0 to Pm-1. This enables us to subsequently compute the key values S2m, S2m+1, and so on.

Encryption

The code below demonstrates the encryption process, generating the keystream from an LFSR (Linear Feedback Shift Register) pseudo-random number generator.

Attack on LFSR

The code below demonstrates the attack technique to deduce the remaining values of the keystream by acquiring the values of P (as illustrated in the diagram above). It assumes the attacker has access to the ciphertext and the first 2m bits of the plaintext.

Here, the degree of the LFSR (m) is 3, so 2m bits equals 6. The first 6 bits of the secret keystream, generated in the previous code, are used and provided in the comments of the current code. The ciphertext generated from the previous encryption process is input for this attack scenario. The attacker also knows the plaintext’s first 6 (2m) bits.

If the first 6 bits of the plaintext are known, a straightforward XOR operation between the plaintext bits and ciphertext bits reveals the first 6 bits of the keystream (denoted as Si, from S0 to S5).

The code below outputs the value of P, which was initially used in the previous code to generate the keystream. By determining the P value, the attacker can subsequently compute the entire keystream using the equations detailed in the code comments below.

The matrix (2D array / List) depicted in the code is computed using the Si values for application in the Gaussian elimination method.

‍

References

1. https://tailcall.net/posts/cracking-rngs-lcgs/
2. https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
3. https://www.geeksforgeeks.org/gaussian-elimination/
4. Introduction to Cryptography by Christof Paar

‍