Skip to content
The Chat Archive
amazon-nova-experimental-chat-05-14· Amazon LMArena Human Preference 140K

Design a cryptographically-secure PRP on a 64-bit block, based on a PRP or PRF that uses…

  1. User

    Design a cryptographically-secure PRP on a 64-bit block, based on a PRP or PRF that uses a 128-bit block.

  2. 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:

    1. 128-bit Block Cipher (E): This could be AES-128 or any other secure 128-bit block cipher.
    2. Key Derivation Function (KDF): To derive round keys from the main key.
    3. Number of Rounds (r): Typically, 8 to 16 rounds are used to ensure security.

    Construction:

    1. 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))
    2. 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:
        1. Pad the 64-bit input (L) to 128 bits by appending 64 zeros: (L'||0^{64})
        2. Encrypt the padded input using the 128-bit block cipher with the round key (K_i): (E_{K_i}(L'||0^{64}))
        3. 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})))
    3. 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):
        1. Compute (L_i = R_{i-1}).
        2. 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:

    1. 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.
    2. Key Derivation:

      • Ensure the KDF is secure and produces sufficiently random and independent round keys.
    3. Block Cipher Choice:

      • Use a well-established and thoroughly vetted 128-bit block cipher like AES.
    4. 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.