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:
- Break $m$ up into blocks of $b$ bits, call the resulting blocks $m_{1}$, $m_{2}$, $\ldots$, $m_{n}$.
- Generate a random block of $b$ bits, call that block $m_{0}$.
- 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$).
- 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:
- Break $w$ up into blocks of $b$ bits, call the resulting blocks $w_{0}$, $w_{1}$, $w_{2}$, $\ldots$, $w_{n}$.
- Calculate $m_{0} = w_{0} \oplus H(w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n})$.
- 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})$.
- 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:
- Have I missed something? is this really an AONT?
- I'm sure there are faster / better approaches to AONTs, but is this terribly bad? is it any better than others in any respect?
- What should be asked of the hash function $H$? collision resistance? pre-image resistance?
- 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.