Score:2

Why not use a random permutation as a block cipher?

lu flag

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.

kelalaka avatar
in flag
Contradict to definition; [What (precisely) is a block cipher?](https://crypto.stackexchange.com/q/10980/18298) and besides this is well-written in textbooks.
kelalaka avatar
in flag
Does this answer your question? [How are keys mapped to cipher texts in block ciphers with large block sizes?](https://crypto.stackexchange.com/questions/87622/how-are-keys-mapped-to-cipher-texts-in-block-ciphers-with-large-block-sizes)
Generic avatar
lu flag
@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.
kelalaka avatar
in flag
It seems you did not see this section. _Lindell&Katz 3.5.1 Pseudorandom Functions and Permutations_ This is dealt in there.
kelalaka avatar
in flag
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
kelalaka avatar
in flag
Related [How secure is a 128 bit ideal substitution cipher](https://crypto.stackexchange.com/q/61782/18298) and [Is there a theoretical maximum useful keysize given the block-size?](https://crypto.stackexchange.com/q/10287/18298) and maybe some more.
Score:9
ng flag

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.

Generic avatar
lu flag
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?
kodlu avatar
sa flag
A 16 bit blocksize will fall victim directly to a dictionary attack
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.