[Cryptography] Random permutation model for encryption as a teaching tool?

[John Denker]

On 10/15/2018 07:38 AM, Stephan Neuhaus wrote:

> I'm teaching a class on IT security generally, and crypto plays not a
> small part in it. The original lecture had a lot of historical
> context and explained monalphabetic ciphers, simple polyalphabetic
> ciphers and transposition ciphers in great detail, and then went
> rather abruptly to AES, which could not be explained on that level
> any more.
> 
> Since the students only need to understand the *properties* of modern
> ciphers but not the details of their *construction*, and also since
> the detailed treatment of historical ciphers and their cryptanalysis
> had some students derive wrong ideas (e.g., being able to break AES
> by frequency analysis), I was looking for another way to explain
> modern ciphers to students in a way that would give them a useful
> mental model.
> 
> I came upon the random permutation model of ciphers. In this model,
> given a set P of possible plaintexts, and a set C of possible
> ciphertexts, a key selects a random permutation from P to C (and
> therefore |P| = |C|). This model is of course not an invention of
> mine; it's present in the Wikipedia page on block ciphers for
> example.
> 
> However, the set of possible n-bit keys contains only 2^n elements,
> whereas there are (2^b)! possible permutations of b-bit blocks, which
> is obviously vastly more if b is of the same order as n. Furthermore,
> not all permutations are good for block ciphers; e.g. those that have
> many fixed points (and most random permutations will have at least
> one) are evidently not well suited.
> 
> So the question is, is this a good model *for teaching*? It doesn't
> have to lead to theorems, and it may even be slightly inaccurate, as
> long as it prevents students from getting entirely wrong ideas à la
> breaking AES with frequency analysis. I personally find it useful,
> but I have no idea what the students will think. Do you use other
> models?

Just as a point of terminology, I suggest not talking about
"permutations of b-bit blocks".  I know what you mean, but
some students will hear that as a permutation of the bits
within the block.  It might work better to speak explicitly
of permutation of blocks within the space of all possible
b-bit blocks.

At a deeper level, I think you're partially barking up the
wrong tree.  A permutation with a fixed point is harmless,
so long as the adversary doesn't know what the fixed point
is.  Forsooth, the fact that Enigma could never have a
fixed point was a terrible weakness.

Also the fact that the key-space is tiny compared to the
permutation-space is irrelevant, so long as the key-space
is large enough.

Any crypto *system* worthy of the name doesn't just substitute
blocks according to a fixed permutation, but uses a different
permutation for each block in the message.  This is where IVs
and chaining modes come in.  If you didn't do that, and used
ECB mode instead, AES *could* be partially broken by frequency
analysis.  So your students aren't entirely wrong.  For an
unforgettable reminder of this fact, see the penguin diagram
in the wikipedia article:
  https://en.wikipedia.org/wiki/Block_cipher#Modes_of_operation

I've often said you really want a new key for each block.
ChaCha can be very cheaply rekeyed from scratch, which is a
virtue.  Typical chaining modes are a quick-and-dirty way
of getting approximately what you want, without the cost of
fully rekeying the underlying block cipher component, but
I've never been completely happy with this.

Modern block ciphers are bijective mappings, which is not
surprising if you want the ciphertext to be uniquely
decipherable.  Whether you want to sell the bijective mapping
as a "permutation" is a judgment call, based on the level of
mathematical sophistication of your students.  You know your
students, and I don't, so I leave that call up to you.

FWIW there is no law that says a block cipher has to be a
permutation.  If code-block-space is larger than plain-block-
space, you can have one-to-many encryption and many-to-one
decryption.  To one way of looking at it, this is what an
IV or session key does for you.  Back in the olden days,
random nulls were used to accomplish more-or-less the same
purpose.