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.
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Contradict to definition; What (precisely) is a block cipher? and besides this is well-written in textbooks. $\endgroup$– kelalakaCommented May 19, 2022 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$– kelalakaCommented May 19, 2022 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$– user918212Commented May 19, 2022 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$– kelalakaCommented May 19, 2022 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$– kelalakaCommented May 19, 2022 at 18:40
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\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$ Commented May 19, 2022 at 17:49
-
5$\begingroup$ A 16 bit blocksize will fall victim directly to a dictionary attack $\endgroup$– kodluCommented May 19, 2022 at 18:10