Deck functions

A Deck function accepts as input one or more variable-length strings and returns as output a variable-length string. When instantiated appropriately, Deck functions behave like a random oracle: the output string has the property of being computationally indistinguishable from true randomness to an adversary who does not know the secret key. I thoroughly believe that the Deck function abstraction provides the ideal abstraction for building every keyed symmetric cryptographic mode.


Traditionally, cryptographic modes are built on top of a hermetic fixed-width block cipher primitive. I would argue that this model puts both the primitive designer and the mode designer at a disadvantage. The primitive designer creates a hermetic fixed-width block cipher and gives it to the mode designer. The mode designer must build an inevitably ad-hoc scheme for handling variable-length inputs and outputs on top of the block cipher. The primitive designer might architect a special tweak input to help alleviate this, but this complicates the key schedule (e.g., Tweakey). Worse yet, because the primitive is hermetic, the mode designer may have to resort to clever uses of the inverse direction of the primitive to maintain efficiency (e.g., OCB3, Deoxys-I), which in turn limits the primitive designer's freedom. Or, the mode designer must try to carefully cull rounds from the primitive (e.g., AEZ). Or, the mode designer must resort to special tricks to minimize the number of calls to the primitive (e.g., PMAC's handling of the last block).

Taking a step back, we see that more or less every keyed symmetric cryptographic mode requires variable-length input and/or output. What if we move this design requirement into the primitive? At first blush, it would seem that we are merely shifting responsibilities around without actually improving the situation. On the contrary, giving the primitive designer a view of the bigger picture improves the situation significantly. The primitive designer can now design an efficient variable-length input/output primitive on top of non-hermetic permutations. The mode designer no longer needs to resort to using the inverse direction of the primitive to be efficient, which means the primitive designer no longer needs to be concerned about the inverse direction of the permutation. This saves space in hardware and allows for additional design freedom in the permutation since the performance of the inverse direction is irrelevant.

How do we build a good Deck function? Farfalle is my favorite way for a number of reasons:


The cryptanalysis can occur at the Deck function level and the modes built on top of the Deck function can benefit from this immediately. The primitive designer can provide Deck functions with varying levels of security. For example, consider the Deck-WBC mode. This mode is a Feistel network composed of two potentially different Deck functions: the outer rounds need only be differentially uniform, while the inner rounds need to be pseudorandom.