How secure is a 128 bit ideal substitution cipher

Question

A 128 bit ideal substitution block cipher substitutes 128 bit blocks with randomly assigned 128 bit blocks using a key table.

How secure is this type of algorithm?

Is this practical?

Thanks!

Answer 1

A block cipher is a keyed permutation. The number of possible permutations is quite high. There are of course $2^{128}$ ways of mapping a single 128 bit plaintext block to a 128 bit ciphertext block. Actually, the number of ways of mapping all possible plaintext blocks to each and every ciphertext blocks is $2^n!$ where $n$ is the block size in bits.

The key is used to choose one of these possible permutations. That means that your key table would have more than $10^{10.000.000.000.000.000.000.000.000.000.000.000.000.000}$ entries. That's a gargantuan number; there are a lots of ways how to map $2^{128}$ values to $2^{128}$ after all.

Is a 128 bit ideal block cipher secure? Sure, it's ideal - so it is secure, by definition, for any block size.

Is a 128 bit ideal block cipher practical? No, the key space is ever so slightly too large for life.

---

An ideal block cipher is possible up to a block size of about 4 bits, however that block size is way too small to be usable in any block cipher mode of operation (such as CBC) for any kind of data. It's therefore a theoretical construction rather than a practical construction.