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
Below is a “recipe” for a 64-bit, key-dependent, strong pseudorandom permutation (PRP) that only calls a well-established 128-bit PRP/PRF such as AES-128. The design is deliberately simple, analyzable, and easy to program on any platform that already has AES. (You can of course drop in any other 128-bit primitive that you trust.)
- High-level idea
• Turn the 128-bit primitive into a 32→32-bit PRF by truncating
its output.
• Plug that truncated PRF into a 4-round balanced Feistel network
over 64 bits (32-bit left and right halves).Thanks to the Luby–Rackoff theorem, 4 rounds already give a strong-PRP (SPRP) on 64 bits as long as the round functions are (independent) PRFs. With AES there is ample security margin, but adding more rounds is trivial if you want extra comfort.
- Notation
AES_K(X) — AES-128 encryption of 128-bit string X under 128-bit key K
⊕ — bitwise XOR
MSB_k(X) — the k most significant bits of X
LSB_k(X) — the k least significant bits of X
- Key schedule
Input master key K_master ∈ {0,1}^128.
Derive four independent AES keys K₁ … K₄ with a very cheap KDF so that the derivation itself does not need any other primitive:for i = 1..4
Kᵢ = AES_{K_master}( i || 0¹¹⁹ ) // i encoded on 8 bitsIf you already have a preferred KDF or wish to use four completely independent random keys, feel free — the security proof only requires the four AES instantiations to be independent or look independent to the adversary.
- Round function Fᵢ : {0,1}³² → {0,1}³²
Fᵢ(x) = MSB₃₂( AES_{Kᵢ}( (x || i || 0⁶³) ) )
• x is the 32-bit round input.
• We embed the round number i (encoded on 1 byte) so that each round definitely sees a different constant, even if K₁ = K₂ = … by bad luck.
• The 63 zero bits merely pad the message to 128 bits.Because AES is a strong PRP on 128 bits, its output is computationally uniform. Truncating it to 32 bits still gives a computationally uniform 32-bit string, hence
Fᵢis a secure 32→32 PRF.
- Encryption: E64_K (L₀ || R₀) → L₄ || R₄
Split the 64-bit plaintext into two 32-bit halves
L₀ = MSB₃₂(P), R₀ = LSB₃₂(P)For i = 1 … 4
Lᵢ = R_{i-1} Rᵢ = L_{i-1} ⊕ Fᵢ( R_{i-1} )Return C = L₄ || R₄.
- Decryption
for i = 4 down to 1
R_{i-1} = Lᵢ L_{i-1} = Rᵢ ⊕ Fᵢ( Lᵢ )Return P = L₀ || R₀.
(The proof that this is a permutation is the usual Feistel argument: each round is invertible, hence the composition of four rounds is.)
- Security bound
Let q be the total number of chosen-plaintext + chosen-ciphertext queries the adversary makes and let Adv_AES^{prp}(t',q') be the PRP advantage of breaking AES with time t' and q' chosen-plaintext queries. Then the distinguishing advantage of attacking our 64-bit scheme is
Adv_64^{sprp}(t,q) ≤ 4 · Adv_AES^{prp}(t+δ, q) + (2 q²) / 2⁶⁴
where δ is the tiny overhead for key derivation and truncation. • The first term comes from the need to replace each Fᵢ by a random function (hybrid argument, 4 such replacements).
• The second term (2 q² / 2⁶⁴) is the classical Luby–Rackoff bound for a 4-round Feistel network on 64 bits.Hence with q ≪ 2³² the birthday term is still < 2⁻³², and with AES the first term is assumed to be negligible.
- Implementation tips
• The input to AES is mostly constant except for the low 32 bits, so you can pre-compute the AES “whitening” on the high 96 bits for speed, or use AES-NI aesenc/vaesenc in parallel.
• If you want more throughput, process 4 or 8 blocks in parallel and use AES in counter mode just to generate raw pseudorandom bits that populate the Fᵢ outputs.
• Constant-time coding is trivial: XOR, shifts, AES — no data-dependent branches or table lookups (assuming hardware AES or constant-time software AES).
- Optional bells & whistles
• Extra rounds: add 2 or 4 rounds if you like; the analysis extends straightforwardly.
• Wider half-blocks: You could instead split the 64-bit input into two 64-bit halves and use an unbalanced Feistel with a 64→64 PRF derived from AES (use the full AES output) — but that would call AES once per half round instead of once per full round, so the design above is cheaper while retaining proven security.
• Tweakable variant: XOR a public tweak into the high 64 bits of the AES input before the parity bits. Security is inherited from the tweakable Luby–Rackoff framework in exactly the same way.
- Summary
- Derive four AES keys from the master key.
- Build a 32→32 PRF by feeding the 32-bit argument (plus padding) to AES and truncating to 32 bits.
- Feed that PRF into a 4-round balanced Feistel over the 64-bit plaintext.
- Enjoy a strong 64-bit PRP whose security reduces directly to AES and the generic 2⁻³² birthday bound on 64-bit domains.
All you need is a single well-vetted 128-bit block cipher; everything else is “free.”
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.