Is this an acceptable All-or-Nothing Transform?

Question

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.

Answer 1

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.