Length-preserving all-or-nothing transform Is there any known way to construct a length-preserving all-or-nothing transform?  In other words, a secure all-or-nothing transform where the length of the output is the same as the length of the input.

My thanks to @Ricky Demer for suggesting this question.
Yes.  Any public random permutation should suffice.  (A public random permutation is like a random oracle, except it is a random permutation rather than a random function.)  A public random permutation is automatically length-preserving, and it meets the requirements for an all-or-nothing transform.

And, a public random permutation can be constructed in a number of ways.  The best construction depends upon whether we care more about theoretical concern or engineering concerns.

Theoretical perspective

From a theoretical perspective, the question of how to build a public random permutation has been answered by the following paper, at least for sufficiently long messages:


The Random Oracle Model and the Ideal Cipher Model are Equivalent.   Jean-Sebastien Coron and Jacques Patarin and Yannick Seurin.  CRYPTO 2008.  IACR ePrint 2008/246.


That paper shows that one can construct a public random permutation by using 6 rounds of a Feistel network, using a random oracle for the F function in each round.  They prove that this is secure in the random oracle model.  Replacing the random oracle with a cryptographic hash function then gives a reasonable construction.

Their construction will work as long as the message length is not too short.  If we want a public random permutation on $n$-bit messages, then their construction yields $k$-bit security as long as $n \ge 48 + 34k$.  For instance, if you want a 80-bit security level, their construction is proven secure for $n$-bit messages, as long as $n \ge 2768$ bits (i.e., $\ge 346$ bytes).  Thus, their construction is not useful in practice for short messages, but it is useful for long messages.  Their proof might be conservative, and it is possible that the actual security level is better than what their proof promises (so the scheme can actually be used securely on shorter messages than what I list here), but that's just speculation.

In summary, their construction yields a public random permutation on $n$-bit blocks, which in turn provides a length-preserving all-or-nothing transform on $n$-bit messages.

Engineering perspective

From a practical/engineering perspective, if we don't care about provable security, we can probably take any block cipher $E$ of the desired block width, choose a random key $K_0$, make $K_0$ public, and use $E_{K_0}(\cdot)$ as the all-or-nothing transform.  This is likely secure for typical block cipher constructions, though there is no proof.

From a theoretical perspective this can be shown secure assuming the block cipher can be modelled as an ideal cipher (e.g., it is free of related-key attacks, etc.), though that is a strong assumption that not all block ciphers may satisfy.

If the length $n$ of the message is very short, then we may need to use a special short-block cipher (e.g., with techniques for format-preserving encryption) as our block cipher.