2
$\begingroup$

The purpose of a block cipher is to act like a random permutation, and indeed a common security definition is one in which the block cipher is taken to be indistinguishable from a random permutation (see Wikipedia). So then why not use a random permutation as a block cipher? That is, the secret key could just be a list of $2^n$ random pairings (for $n$ bit block) between input (plaintext) and output (ciphertext). Indeed, this would trivially satisfy the security definition.

$\endgroup$
6
  • 2
    $\begingroup$ Contradict to definition; What (precisely) is a block cipher? and besides this is well-written in textbooks. $\endgroup$
    – kelalaka
    May 19 at 16:34
  • 2
    $\begingroup$ Does this answer your question? How are keys mapped to cipher texts in block ciphers with large block sizes? $\endgroup$
    – kelalaka
    May 19 at 18:01
  • $\begingroup$ @kelalaka I think so mostly, however I suppose I am still a little unclear as to whether a random permutation as defined above still satisfies the definition of a block cipher, or whether we do not use it as one due to practical issues. $\endgroup$
    – user918212
    May 19 at 18:06
  • $\begingroup$ It seems you did not see this section. Lindell&Katz 3.5.1 Pseudorandom Functions and Permutations This is dealt in there. $\endgroup$
    – kelalaka
    May 19 at 18:35
  • $\begingroup$ A block cipher is a family of permutations where each key selects one permutation ( you already see that representing all possible permutations is out of the question due to the size of representation and computation). Instead, we took subset with hoping that they are indistinguishable from a random permutation $\endgroup$
    – kelalaka
    May 19 at 18:40

1 Answer 1

9
$\begingroup$

The issue is the lack of a compact representation. Assume you wanted to specify a 128-bit block cipher this way. A naive representation of a permutation on such blocks would consist of a sequence of $2^{128}$ elements of $128$ bits each - that's around $5.4 \cdot 10^{27}$ TB. That is impossible to store, let alone to securely exchange.

Compare this with usual candidates for things which are indistinguishable from a truly random permutation, where the size of the secret information to be exchanged is normally linear in the security parameter.

Using smaller permutations is not an option either, as they must be large enough to resist a brute-force attack. Plus once your block size gets too small, the overhead cost of whatever mode of operation you use is likely to become significant.

$\endgroup$
2
  • $\begingroup$ Alright, but consider a 16 bit block: then there are $2^{16}!$ keys, which is far larger than $2^{256}$ for example, so in this case the key could not be brute forced, no? $\endgroup$
    – user918212
    May 19 at 17:49
  • 4
    $\begingroup$ A 16 bit blocksize will fall victim directly to a dictionary attack $\endgroup$
    – kodlu
    May 19 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.