A Block Cipher Is a Permutation

Edit a small three-bit cipher until two messages share one ciphertext. Then ask the page to decrypt that ciphertext.

Reversibilitydemo

Objectives

Decide whether a small mapping can be used as a block cipher.
Explain why two plaintexts sharing a ciphertext leaves decryption unable to recover the plaintext.
Distinguish a function on the block space from a permutation of it.
Compare the number of reversible mappings against the number of functions over the same block.
Estimate how many bits a key needs to identify one permutation.

33%

Edit a three-bit cipher until it stops being decryptable.

A 3-bit block has eight possible values, so one key gives one table of eight rows. Change any output and watch the verdict change with it.

One key, one table

The 3-bit mapping. Each row gives one plaintext and the ciphertext the current table sends it to.
Plaintext	Ciphertext	Status
000	101	one to one
001	010	one to one
010	111	one to one
011	000	one to one
100	110	one to one
101	011	one to one
110	001	one to one
111	100	one to one

verdict

Usable as a block cipher

Decryption asks the table backwards. Pick a ciphertext and see what the receiver, who holds the same key, is able to work out.

ciphertext to decrypt

Decrypt 101

101 came from 000

One plaintext, so the receiver recovers the message.

For a fixed key, the whole block cipher is a reversible mapping: every ciphertext comes from exactly one plaintext. A block cipher is therefore a keyed permutation of the n-bit block space.

An n-bit block has 2ⁿ possible values, and a block cipher is a permutation of those values. Over three bits there are 16,777,216 functions from block to block, and only 40,320 of them are permutations.

What a key would have to name

Block size against the number of possible permutations and the number of bits needed to identify one of them.
Block size	Possible permutations	Bits needed to identify one
2 bits	(2^2)! = 24	4.6 bits
3 bits	(2^3)! = 40,320	15.3 bits
8 bits	(2^8)!	1684.0 bits
16 bits	(2^16)!	954036.9 bits
64 bits	(2^64)!	1.15e+21 bits

A key that could identify any permutation would have to be as long as the last column says. Read the last row: at a 64-bit block that is about 10²¹ bits. A real cipher uses only a tiny structured subset of all possible permutations, chosen by a key of 128 or 256 bits.

step 1/3

CPE 645 / CS 685

A Block Cipher Is a Permutation

Presentation Order Draw

The Avalanche Effect