6
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ I'm thinking something like the following. Given some $i$-block message $m = m_{0} || m_{1} || \cdots || m_{i - 2} || m_{i - 1}$, let $c' = E_{CBC}(k, 0, m_{0} || m_{1} || \cdots || m_{i - 2} || m_{i - 1} || m_{i - 1} || m_{i - 2} || \cdots || m_{1} || m_{0})$. The ciphertext is $c = c'_{i} || c'_{i + 1} \cdots || c'_{i * 2 - 2} || c'_{i * 2 - 1}$. $\endgroup$
    – Stephen Touset
    Commented Jun 17, 2014 at 22:19
  • 1
    $\begingroup$ @StephenTouset - CBC always has the issue of being slightly error-tolerant, which as I understand it means this wouldn't be All-or-Nothing? If part of a ciphertext block is missing, it will only affect the decryption of a couple of plaintext blocks. $\endgroup$
    – Cryptographeur
    Commented Jun 17, 2014 at 23:17
  • 1
    $\begingroup$ @StephenTouset: your construction is not AoN. For example, we can recover $m_0$ from the last two blocks of cihertext. $\endgroup$
    – fgrieu ♦
    Commented Jun 18, 2014 at 5:54
  • 1
    $\begingroup$ how is this different from crypto.stackexchange.com/questions/6098/… $\endgroup$
    – sashank
    Commented Jun 18, 2014 at 10:19
  • 1
    $\begingroup$ @fgrieu You're right. I'd originally conceived it as doing CBC a second time over the reversal of the ciphertext, but as D.W. explains in his answer, the entire construct is unnecessary in the first place. Oh well. $\endgroup$
    – Stephen Touset
    Commented Jun 18, 2014 at 17:25

2 Answers 2

Reset to default
3
$\begingroup$

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:

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Yes; but your answer does not explicitly construct a public random permutation of arbitrary size, from fixed-size primitives. For large size it is not trivial, as shown by the comment proposing a construction using CBC (which is not AoN). $\;$ In fact, a AoNT would be an ideal building block in RSA signature schemes (especially those with message recovery and deterministic), but ISO/IEC 9796-2 scheme 3 seems to uses something lesser, perhaps because a simple yet efficient AoNT is not so easy to build. $\endgroup$
    – fgrieu ♦
    Commented Jun 18, 2014 at 6:02
  • 1
    $\begingroup$ "we can probably take any block cipher E of the desired block width" - Can you propose a scheme of optimally secure and arbitrarily sized block ciphers then? $\endgroup$
    – Cryptographeur
    Commented Jun 18, 2014 at 9:17
  • $\begingroup$ @fgrieu, actually, I think you have it backwards. For large size, it is straightforward (in the random oracle), as explained in the section "Theoretical perspective": use a cryptographic hash function as the F-function of a 6-round Feistel network. I actually think the more challenging case is to do it for small block size, not large block size. $\endgroup$
    – D.W.
    Commented Jun 18, 2014 at 13:00
  • 1
    $\begingroup$ @D.W.: The construction that you describe requires 6 hashes, and can at most operate on twice the hash size. In the context I was considering, of formatting the message representative for a 2048-bit RSA signature, and SHA-256, it does not cut it. It is easy to make a 1024-bit wide hash from SHA-256, but the resulting 2047-bit AoNT has 6 rounds, 4 hashes per round, 3 compression functions per hash, for 72 compression functions total. That's non-trivial overhead. And things are worse with AES as a building block. I still think we lack simple and efficient AoNT for wide (>1000 bit) blocks. $\endgroup$
    – fgrieu ♦
    Commented Jun 18, 2014 at 17:18
  • $\begingroup$ Interesting mismatch between 6 rounds from that paper and the 4 rounds to build a strong PRP from the Luby-Rackoff paper. $\endgroup$
    – CodesInChaos
    Commented Mar 23, 2016 at 15:00
0
$\begingroup$

Use a block cipher in Cipher block chaining (CBC) mode with a public or all-0 key. Twice.

There need not be a change in CBC direction on the second round. Xor the last block into the first on the second round.

Every block will depend on all previous and all successive blocks. Any corruption in any block will corrupt all the rest.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.