# Is this an acceptable All-or-Nothing Transform?

I was thinking about AONTs, and designed the one below, I call it CHANT for Chained-Hash All-or-Nothing Transform; it's my very first shot at something of the sort, and was hoping I could get your opinions.

Suppose you have a hash function $H$ of block size (ie. the size of the generated hash) $b$, you'd like to "wrap" a message $m$; CHANT works as follows:

1. Break $m$ up into blocks of $b$ bits, call the resulting blocks $m_{1}$, $m_{2}$, $\ldots$, $m_{n}$.
2. Generate a random block of $b$ bits, call that block $m_{0}$.
3. Now, for each message block $m_{i}$ (with $1 \leq i \leq n$), calculate its wrapped block $w_{i}$ as $w_{i} = H^{i} (m_{0}) \oplus m_{i}$ (where $H^{i}$ denotes the $i$-th iteration of the hash function $H$).
4. Finally, calculate $w_{0} = H(w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n}) \oplus m_{0}$, the wrapping will then be $w = w_{0} \Vert w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n}$ (where $x \Vert y$ denotes concatenation).

Now in order to unwrap a CHANT-wrapped message $w$, one proceeds as follows:

1. Break $w$ up into blocks of $b$ bits, call the resulting blocks $w_{0}$, $w_{1}$, $w_{2}$, $\ldots$, $w_{n}$.
2. Calculate $m_{0} = w_{0} \oplus H(w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n})$.
3. Now for each wrapped block $w_{i}$ (with $1 \leq i \leq n$), calculate its unwrapping $m_{i}$ as $m_{i} = w_{i} \oplus H^{i} (m_{0})$.
4. Finally, discard $m_{0}$, the unwrapping will then be $m = m_{1} \Vert m_{2} \Vert \cdots \Vert m_{n}$.

If $w_{0}$ is missing, then there's simply not enough information to retrieve the original random $b$ bits, if $w_{i}$ with $i \neq 0$ is missing, then with high probability, the hash value needed to retrieve $w_{0}$ will be incorrect.

CHANT is basically a (very simple) stream cipher which discloses the (random) encryption key given the wrapped message's hash.

As some of its (in my eyes) pros, I'd mention the fact that it requires nothing more than a hash function and a (pseudo-)random source (but see question 4 below), and that it's very easy to understand (for a layman like myself at least).

As one of its cons, I'd point out the need to add an additional block (ie. $w_{0}$) to the output.

Now, my questions are:

1. Have I missed something? is this really an AONT?
2. I'm sure there are faster / better approaches to AONTs, but is this terribly bad? is it any better than others in any respect?
3. What should be asked of the hash function $H$? collision resistance? pre-image resistance?
4. Is it having a (pseudo-)random source a bad thing? would it be any better if the construction above were to replace $m_{0}$ (randomly generated) by $H(m)$? would it be any worse? (at the very least, it would make the wrappings of two identical messages the same).

Thank you in advance, and sorry if I overlooked something trivial, it's my first post in this SX site.

-
"from $G$" $\: \mapsto \:$ "from those blocks with $G$" $\;\;\;$ ? $\;\;\;\;\;\;\;$ –  Ricky Demer Jul 31 '14 at 0:43
I was thinking about $G$ as a random stream of bits you could take some out of, but I'd welcome a better way of putting it in the question proper, English is not my mother language :) –  mpr Jul 31 '14 at 0:47
@RickyDemer I don't quite understand your edit... what do you mean by "from those blocks with $G$"? which blocks do you refer to? –  mpr Jul 31 '14 at 1:58
"the resulting blocks $m_{1}$, $m_{2}$, $\ldots$, $m_{n}$" $\;$ –  Ricky Demer Jul 31 '14 at 2:17
Oh, I see! But the $b$ bits are not extracted from the $m_{i}$ blocks, but rather independently from them, actually, they're extracted from the $G$ generator. Sorry for the wording, I'm open to suggestions, but your edit makes it look like the message blocks are a "seed" of sorts and this is not the case: the $G$ "stream" may be seeded any way you want (and it may be preferable not to use $m$ at all in doing so). –  mpr Jul 31 '14 at 2:30

Have I missed something? is this really an AONT?

An iterated hash doesn't make a secure stream cipher. If the attacker can guess $m_i$, they can calculate $w_i \oplus m_i = H^i(m_0)$, then decrypt the rest of the message by taking hashes of that value.

An option would be to use the hash function like a block cipher in counter mode $w_i = H(m_0||i)$. That should be secure.

I'm sure there are faster / better approaches to AONTs, but is this terribly bad? is it any better than others in any respect?

If will likely be significantly slower than just using AES or a stream cipher for the encryption and a hash to make the key depend on the rest. Hash functions don't always produce a lot of output fast.

The advantage is that you only depend on one primitive. If you wanted that, you could use a hash function with a stream cipher mode, like Keccak (which SHA-3 is based on). That should be faster.

What should be asked of the hash function H? collision resistance? pre-image resistance?

The hash function should be (first) preimage resistant and a PRF. Collision resistance doesn't matter unless the attacker can control or at least predict the random $m_0$.

Is it having a (pseudo-)random source a bad thing? would it be any better if the construction above were to replace m0 (randomly generated) by H(m)? would it be any worse? (at the very least, it would make the wrappings of two identical messages the same).

No, it's a good thing. A deterministic $m_0 = H(m)$ would, for example, let an attacker verify any guess of the message $m$ with high likelihood from just a single $w_i$. Just transform the guess message and see if any block matches.

-
Great answer!, but I'm not clear on how I would use Keccak in this case... does it allow one to "input" $m_{i} \Vert i$ and then "extract" some bits from it? I know Keccak is a cryptographic sponge, but don't know how that would be practically applied here, do you care to explain? –  mpr Jul 31 '14 at 12:50
@mpr, the Keccak website links to a paper on an encryption mode. Note that I'm not really recommending that either, since it's relatively new and nonstandard. AES + SHA-2 would make a secure AONT from standard primitives. –  otus Jul 31 '14 at 13:05
Alright, so something along the lines of $w_{i} = AES(m_{0} \Vert i) \oplus m_{i}$ for $1 \leq i \leq n$ and $w_{0} = SHA2(m) \oplus m_{0}$? I really like the idea of depending on a single primitive... if one were to have two random values $m_{0}$ and $m_{n + 1}$, and do $w_{i} = H^{i} (m_{0}) \oplus H^{n - i + 1} (m_{n + 1}) \oplus m_{i}$ (ie. chaining one hash forwards and one backwards), would it still be vulnerable to the attack you mentioned (or any other)? PS: should I include this as an edit to the question above or is it fine here in the comments? –  mpr Jul 31 '14 at 13:23
@mpr, if you want to use just a hash and can live with whatever performance that gives you, you can use $w_i = H(m_0||i)$, like I mentioned in the answer. Can't say off the top of my head whether your alternative is secure, but it is slower. –  otus Jul 31 '14 at 14:28
Totally forgot about that one! Great answer all around, thanks a bunch! :) –  mpr Jul 31 '14 at 15:09