What is the easiest encryption/cipher to brute force?

Question

This is just a casual exploration of what could be effectively the worst possible block cipher, but I think it has some educational value on how ciphers work.

I've been reading about unicity distance and I am interested in a block cipher that has a decent-sized keyspace (2^8 or more?) that has the smallest unicity distance possible. If the plaintext effectively looks random such that no frequency analysis or plaintext knowledge would be useful, then it would seem like finding the key would be impossible using brute force for most ciphers with a large enough keyspace and a small enough ciphertext.

I am less interested in trivial ciphers with a very small key space such as Atbash or Caesar, and want to learn about perhaps novel ciphers whose key length is near the block size but has some flaw or cryptoanalysis property which makes them very weak to being brute-forced (or finding the key easily).

Can a block cipher exist such that there are zero spurious keys, and as soon as the correct key is used in decryption there is an obvious sign it's the correct one? If not, what is the best (worst?) we can hope for?

PS: When I mentioned "easiest" I mean in terms of spurious keys, ignoring required computation power. If for example there is a block cipher that has zero spurious keys but its block and key size are both 256 bits, then I would still consider it "easy" in this context and want to know about it despite being impractical to brute force.

Answer 1

I am interested in a block cipher that has a decent-sized keyspace (2^8 or more?) that has the smallest unicity distance possible

How about any AEAD cipher with a tag length longer than the key size?

If we model the tag computation as random, then for a random key, we would expect that the tag would authenticate with probability $2^{-t}$ (where $t$ is the tag length); there are a total of $2^k$ keys (where $k$ is the key length), and so there would be approximately an expected $2^{k-t}$ incorrect keys where the tag would verify; if $k < t$, this is less than one, and that means we've achieved 'unicity distance' (even if the plaintext length was, say, 1 byte)