Design a cryptographically-secure PRP on a 64-bit block, based on a PRP or PRF that uses…
- User
Design a cryptographically-secure PRP on a 64-bit block, based on a PRP or PRF that uses a 128-bit block.
- Assistant
Designing a cryptographically-secure Pseudo-Random Permutation (PRP) on a 64-bit block based on a PRP or Pseudo-Random Function (PRF) that uses a 128-bit block can be achieved using well-established techniques. One common approach is to use Feistel networks. Here, I'll outline a design using a 128-bit block cipher (like AES) to construct a secure 64-bit block PRP.
Design: Feistel Network using a 128-bit Block Cipher
A Feistel network is a well-known structure for building PRPs. It operates on half of the block size at a time, which makes it suitable for reducing a 128-bit block cipher to a 64-bit PRP
Here's the step-by-step design:
Components:
- 128-bit Block Cipher (E): This could be AES-128 or any other secure 128-bit block cipher.
- Key Derivation Function (KDF): To derive round keys from the main key.
- Number of Rounds (r): Typically, 8 to 16 rounds are used to ensure security.
Construction:
-
Key Scheduling:
- Input: A 128-bit key (K).
- Use a Key Derivation Function (KDF) to derive (r) round keys (K_1, K_2, \ldots, K_r) from the main key (K). Each (K_i) should be 128 bits to match the block size of the 128-bit block cipher.
- A simple KDF could be to encrypt a counter with the main key using the 128-bit block cipher. I.e. (K_i = E_K(\text{counter} || i))
-
Feistel Function (F):
- The Feistel function (F) takes a 64-bit input and a 128-bit round key and produces a 64-bit output.
- Define (F(L, K_i)) as follows:
- Pad the 64-bit input (L) to 128 bits by appending 64 zeros: (L'||0^{64})
- Encrypt the padded input using the 128-bit block cipher with the round key (K_i): (E_{K_i}(L'||0^{64}))
- Take the first 64 bits of the ciphertext as the output of (F).
- (F(L, K_i) = \text{MSB}{64}(E{K_i}(L'||0^{64})))
-
Feistel Network:
- Input: A 64-bit plaintext block (P).
- Split (P) into two 32-bit halves: (L_0) and (R_0).
- For (i) from 1 to (r):
- Compute (L_i = R_{i-1}).
- Compute (R_i = L_{i-1} \oplus F(R_{i-1}, K_i)).
- After (r) rounds, the output is (R_r || L_r).
- To decrypt, reverse the order of the round keys.
Security Considerations:
-
Number of Rounds:
- Choose at least 8 rounds to resist differential and linear cryptanalysis. More rounds (up to 16) can be used for higher security margins.
-
Key Derivation:
- Ensure the KDF is secure and produces sufficiently random and independent round keys.
-
Block Cipher Choice:
- Use a well-established and thoroughly vetted 128-bit block cipher like AES.
-
Feistel Function:
- By only taking the first 64 bits of the ciphertext we are effectively using the 128-bit block cipher as a PRF. This is secure under the PRF-PRP switching lemma, assuming the underyling block cipher is a secure PRP.
Example Implementation:
Here is a pseudo-code representation of the design:
def KDF(K, r): keys = [] for i in range(1, r + 1): counter = i.to_bytes(8, 'little') # 64-bit counter keys.append(AES.encrypt(K, counter + b'\x00'*8)) # 128-bit key return keys def F(L, K_i, E): # Pad L to 128 bits L_padded = L + b'\x00'*8 # Encrypt with the 128-bit block cipher ciphertext = E.encrypt(K_i, L_padded) # Return the first 64 bits return ciphertext[:8] def feistel_network(P, keys, E, rounds): L = P[:8] # First 64 bits R = P[8:] # Second 64 bits for i in range(1, rounds + 1): L_new = R R_new = xor(L, F(R, keys[i-1], E)) L, R = L_new, R_new return R + L # Swap L and R for the final output def encrypt(P, K, E, rounds=16): keys = KDF(K, rounds) return feistel_network(P, keys, E, rounds) def decrypt(C, K, E, rounds=16): keys = KDF(K, rounds) keys.reverse() # Reverse the keys for decryption return feistel_network(C, keys, E, rounds) # Example usage with AES as the 128-bit block cipher from Crypto.Cipher import AES E = AES # Assume AES is imported and can be used directly K = b'\x00'*16 # 128-bit key P = b'\x00'*8 # 64-bit plaintext C = encrypt(P, K, E) P_dec = decrypt(C, K, E)Conclusion
This design leverages a 128-bit block cipher to create a secure 64-bit PRP using a Feistel network. By carefully choosing the number of rounds, ensuring a secure KDF, and using a well-vetted block cipher, this construction can achieve cryptographic security.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.