Block-Cipher-Based Tree Hashing

Aldo Gunsing

Digital Security Group, Radboud University, Nijmegen, The Netherlands

[email protected]

Abstract. First of all we take a thorough look at an error in a paper

by Daemen et al. (ToSC 2018) which looks at minimal requirements for
tree-based hashing based on multiple primitives, including block ciphers.
This reveals that the error is more fundamental than previously shown
by Gunsing et al. (ToSC 2020), which is mainly interested in its effect on
the security bounds. It turns out that the cause for the error is due to an
essential oversight in the interaction between the different oracles used
in the indifferentiability proofs. As a matter of fact, this error appeared
in multiple earlier indifferentiability papers, including the optimal indif-
ferentiability of the sum of permutations (EUROCRYPT 2018) and the
recent ABR+ construction (EUROCRYPT 2021). We discuss in detail
how this oversight is caused and how it can be avoided.
We next demonstrate how the negative effects on the security bound of
the construction by Daemen et al. can be resolved. Instead of only allow-
ing a truncated output, we generalize the construction to allow for any
finalization function and investigate the security of this for five different
types of finalization. Our findings, among others, show that the security
of the SHA-2 mode does not degrade if the feed-forward is dropped and
that the modern BLAKE3 construction is secure in principle but that its
use of the extendable output requires its counter used for random access
to be public. Finally, we introduce the tree sponge, a generalization of the
sequential sponge construction with parallel absorbing and squeezing.

Keywords: Hash Functions, Block Ciphers, Tree Hashing, Indifferen-

tiability

1 Introduction
1.1 Hash Functions
Hash functions, which are functions H : {0, 1}∗ → {0, 1}n that compress an
arbitrarily-sized message M to a fixed sized output h, form a fundamental part
of many cryptographic constructions. In practice they are not built directly,
but from a smaller compression function that only takes a fixed sized input,
for example f : {0, 1}2n → {0, 1}n . A popular and simple method for this is the
Merkle-Damgård construction [Mer89,Dam89], which uses a fixed-sized compres-
sion function in a sequential manner to obtain the hash digest. This construction
is sometimes ‘strengthened’ by appending an encoding of the length of the mes-
sage to the end, giving a collision resistant hash function as long as the internal
compression function is collision resistant, a fact proven by Merkle and Damgård
independently.
However, it turned out that collision resistance is not strong enough for some
situations. For example, strengthened Merkle-Damgård is susceptible to another
attack, called the length extension attack: given the hash digest H(M ) of a
message M and its length |M | it is possible to compute H(pad(M ) ∥ M ′ ) for
any M ′ , without knowing the original message M . This is possible as the digest
H(M ) leaks the internal state of the hash function when the blocks of pad(M )
are processed. By using this state as the initial value, it is straightforward to
compute H(pad(M ) ∥ M ′ ) for any M ′ . This is especially troublesome when the
function is used in the keyed fashion as H(K ∥ M ), noting it should be possible
to build a MAC in this way, as the output of the hash should be unpredictable
when K is unknown. The attack above shows that this construction is insecure
when the hash function is instantiated with (strengthened) Merkle-Damgård,
even when the internal compression function is secure. A remedy for this is the
HMAC construction [KBC97, Bel06], but this is less efficient and unsatisfying.
This weakness asks for a more sophisticated security analysis for hash func-
tions, namely one that guarantees that the hash function behaves like a random
oracle, which gives an randomly generated and independent output for every
input. The most general security notion we have is the one of indifferentiability
introduced by Maurer et al. [MRH04], which is further applied to hash functions
by Coron et al. [CDMP05].

1.2 Previous Work

Using this stronger security notion of indifferentiability, multiple constructions

have been shown indifferentiable. For example, prefix-free Merkle-Damgård [CDMP05,
LGD+ 09,LLG11] and Merkle-Damgård with truncation [CDMP05,CN08,LGD+ 09,
LLG11] have been shown indifferentiable, all assuming that the underlying com-
pression function is an ideal compression function. However, this is a very strong
and unrealistic assumption: most constructions use a block-cipher-based design
with commonly the Davies-Meyer transformation [PGV93] on top. This trans-
formation defines the compression function f : {0, 1}κ × {0, 1}b → {0, 1}b as
f (k, x) = Ek (x) ⊕ x for a block cipher E : {0, 1}κ × {0, 1}b → {0, 1}b . This trans-
formation does make it hard to find collisions or an inverse, but it is not indiffer-
entiable from an ideal compression function and has some undesirable properties.
For example, the computation of Ek−1 (0b ) = x for an arbitrary k ∈ {0, 1}κ im-
mediately gives a fixed point x where f (k, x) = Ek (x) ⊕ x = 0b ⊕ x = x, while
finding such fixed point is very difficult for an ideal compression function. This
means that one cannot directly use this compression function in a construction
that expects an ideal compression function; additional analysis is required. In
short, we cannot use constructions based on an ideal compression function to
argue security of block-cipher-based constructions.
There have been some constructions shown to be indifferentiable from an
ideal compression function [Men13,LMN16,GBK16], but these are very complex

2
and inefficient. There is some work that have dedicated analysis of block-cipher-
based constructions: for example, prefix-free Merkle-Damgård with Davies-Meyer
[CLNY06,GLC08] or Merkle-Damgård with Davies-Meyer with truncation [GLC08],
etc. Another approach for creating a hash function is by processing the message
in parallel by using a tree hash, a direction looked at by for example Dodis et
al. [DRRS09], where an ideal compression function is used as a primitive. They
also show that one can use a truncated permutation to create a compression
function that is indifferentiable from a random function, which is later improved
upon [CLL19], however, this gives an unoptimized construction and inferior se-
curity bounds as the abstraction to an ideal compression function requires extra
overhead.
The most promising work for this approach was by Daemen et al. [DMA18]
who looked at general tree hashing based on, among others, block ciphers. This
paper defined very general properties that a tree hash should satisfy in order
to be indifferentiable from a random oracle. Importantly, it supposedly proved
that truncation nor a feed-forward is not one of the required properties. However,
Samuel Neves pointed out a critical error in the paper indicating that truncation
should be required, which was also the formal fix used in the errata by Gunsing
et al. [GDM20]. This still leaves us with an unsatisfactory situation as truncation
is not always a desirable option when the size of the block cipher is small.

1.3 Our Contribution

1.3.1 Identification of the Flaw In Section 3 we will discuss the nature

of the error in more depth. It turns out that there is more to the error than
the superficial correction of the bound in [GDM20] indicates. The original pa-
per implicitly ignores some fundamental interaction between the primitive and
construction oracles that appear in the definition of indifferentiability as they,
after a transformation, incorrectly discard all queries made to the construction
oracle. This is an essential part of indifferentiability and the same error occurs in
other papers as well [CN08, MPN10, MP15, Lee17, BN18, ABR21]. One [CN08] is
about hash functions as well, but it does not make use of any invalid properties,
which means that the bounds are not influenced at all and that the proof could be
fixed in a straightforward manner. Most other ones [MPN10,MP15,Lee17,BN18]
are about the indifferentiability of the sum of permutations and are all based
on [MPN10] which contains the same error and the other papers copy the same
faulty reasoning. At least the proof of the most recent work [BN18], claiming
optimal indifferentiability of the sum of permutations, is significantly impacted.
More recent work with the ABR+ construction [ABR21] also contains the same
error, although it should not influence its result.

1.3.2 Block-Cipher-Based Tree Hashing with General Finalization

We improve the state of the art by generalizing the the construction of Daemen
et al. [DMA18], which only considers a truncated output. We generalize the
construction to allow for any finalization function and analyze the security of

3
this for five different types of finalization. These constructions and their security
properties are summarized in Table 1. Section 4 contains the full security bounds.

Normal Truncation. First of all we re-prove the same construction as in [DMA18]

but with more care where we take the error into account. This proves that the
original properties are indeed sufficient when truncation is properly account for,
as is also shown in the fixed version. Additionally, we generalize some properties
slightly, allowing for a more flexible length of the initial value and digest size.

Truncation Without Subtree-Freeness. The most natural way to prevent the

length extension attack is by requiring subtree-freeness, where the result of a
hash can never be part of another hash. However, in order to prevent this situ-
ation, the mode has to use extra bits to mark, for example, the final node. This
introduces extra overhead compared to a simpler mode. A different solution is
to require more truncation, which was already done previously for the Merkle-
Damgård mode specifically. We generalize this solution to tree hashes. It turns
out that one can drop the subtree-freeness property by truncating to an even
smaller digest, where the exact cost depends on the specific mode. In Section 5.1
we use this to prove the security of the mode used in truncated SHA-2 [SHA08],
without requiring any feed-forward. This is a significant efficiency improvement,
as SHA-2 uses a feed-forward in every compression call.

Chopping. Thirdly we look at chopping instead of truncating. Truncation keeps

the first few bits of a string and drops the other bits, while chopping does the
inverse: it drops the first few bits and keeps the remaining ones. At a first glance
this should not make a difference, as the operations are symmetrical. However,
as in our definition of tree hashes we assume that the chaining values are al-
ways the result of truncated outputs, it turns out that chopping the final value
instead of truncating gives a superior security bound. It essentially voids the
stronger requirement with respect to the digest size that the previous mode
lost. In short, by using chopping as the finalization instead of truncation, we
can drop the subtree-freeness requirement without compromising any security.
In Section 5.3 we introduce the tree sponge, a generalization of the sponge con-
struction allowing for parallel absorbing and squeezing, making full use of this
result.

Enveloped. Fourthly we look at a generalized enveloped mode. This mode uses

a fixed value in the data path of the final compression call, generalizing the
Enveloped Merkle-Damgård construction [BR06]. Compared to normal Merkle-
Damgård this switches the position of the chaining value from the data input to
the key input. This simple change allows for a secure mode that does not require
much overhead. We show that this approach generalizes from the sequential
Merkle-Damgård mode to general tree-based hashes.

Feed-Forward. Fifthly we look at a feed-forward. We show that by having a

feed-forward in the final compression call we do not need any truncation. The

4
conventional approach, which has also been adopted in SHA-2, is that all com-
pression calls use a feed-forward. However, we show that only the final one is
required. More importantly, its use does not negate other conditions. For ex-
ample, subtree-freeness is still required, which is not satisfied in SHA-2 and
truncation is still required. In Section 5.2 we use this to analyze the security
of the mode used in BLAKE3 [OANW20] when based on a block cipher. We
show that the mode is secure in principle, but there is a non-negligible factor in
the complexity of the simulator. As a consequence, the extendable output mode
becomes insecure when a secret value is used for its offset.

mode MD+LA+RD SF FA finalization bits of security proof

✓ ✓ — ⌊y⌋n min(m, c/2, b − n) Section A
truncation
✓ — — ⌊y⌋n min(m, c/2, c − n) Section A.6
chopping ✓ — — ⌈y⌉n min(m, c/2, b − n) Section A.7
enveloped ✓ ✓ full y min(m, c/2) Section B
feed-forward ✓ ✓ partial x⊕y min(m, c/2) Section C

Table 1: Summary of the indifferentiability bounds. The conditions MD, LA, RD,
SF and FA stand for message-decodability, leaf-anchoring, radical-decodability,
subtree-freeness and final-anchoring, respectively. The bits of security are with
respect to the number of primitive queries either direct or indirect, where con-
stant and logarithmic terms are ignored. b is the length of the data input of the
block cipher, c ⩽ b the capacity of the chaining values, n ⩽ b the digest length
and m ⩽ c the length of IV1 which is used for leaf-anchoring. For the finaliza-
tion, x denotes the data input to the final block cipher call and y the output.
The notations ⌊y⌋n and ⌈y⌉n denote truncation and chopping respectively (i.e.
x = ⌊x⌋n ∥ ⌈x⌉|x|−n for all n). Note that all chaining values are truncated block
cipher outputs, hence the asymmetry between truncation and chopping.

1.3.3 Comparison of the Variants The different modes above all come
with different trade-offs:
– Truncation/Chopping is useful when the block length b is sufficiently large.
This is often the case for permutations (which is simply the special case κ =
0) or large block ciphers. The results show that chopping is basically superior
to truncation, when the chaining values are constructed using truncation.
If this is the other way around the same result holds by symmetry. The
important observation is that dropping a different part of the output in the
finalization compared to the internal chaining values is superior to doing the
same operation twice. This is shown by the fact that an extra condition in
the form of subtree-freeness can be dropped, or that the efficiency can be
significantly improved: the change in the security term from c − n to b − n
allows for a larger n with the same security level.

5
 – If a large block size is not available, the enveloped mode is useful. This mode
does not have any extra security terms and can achieve b/2 bits of security.
The biggest disadvantage is that it requires one full extra block cipher call.
– The feed-forward mode is commonly used, but it does not reduce the re-
quired conditions compared to the other finalizations. For example, radical-
decodability and subtree-freeness are still necessary. Its advantage compared
to the enveloped mode is that it only requires partial final-anchoring, making
it possible to process a larger message block in the final compression call,
increasing its efficiency slightly.

2 Preliminaries

2.1 Notation

In our setup we assume random primitives. In particular, we denote E : {0, 1}κ ×

{0, 1}b → {0, 1}b for a block cipher with key length κ and block length b that
is uniformly drawn from the set of all such block ciphers. For a bit string x of
size at least n bits, we denote ⌊x⌋n for the first n bits of x (truncation) and
⌈x⌉n for the last n bits of x (chopping). Note that for any such x we have that
x = ⌊x⌋n ∥ ⌈x⌉|x|−n , where |x| denotes the length of a string x in bits and ·∥·
concatenation. The uniform random drawing of an element x from a finite set
$
X is denoted by x ← − X.

2.2 Tree Hashing

We follow the same tree hashing paradigm as in [DMA18], but specialized for
block ciphers and with some small generalizations.
A block-cipher-based tree hash is a function T [E] : {0, 1}∗ × A → {0, 1}n
based on the block cipher E : {0, 1}κ × {0, 1}b → {0, 1}b , where κ is the length of
the key input and b the length of the data input. We use an explicit intermediate
step of template generation in order to be able to reason about the hashing mode.
The mode computes the hash digest of a message M ∈ {0, 1}∗ with parameters
A ∈ A in multiple steps:

– First it computes the tree template Z = Z(|M |, A) based on the message

length |M | and the parameters A. This step is elaborated on in Section 2.2.1.
– Then it executes the template to get the in- and output of the final node
(x, y) = Y[E](M, Z). This step is elaborated on in Section 2.2.2.
– As the last step it applies a finalization function ζ : {0, 1}b ×{0, 1}b → {0, 1}n
to the in- and output to get the digest h = ζx (y). If the input x is not used
we simply write ζ(y). This is a generalization compared to [DMA18], where
only ζ(y) = ⌊y⌋n is considered. It has to be possible to randomly compute
$
an inverse given some input x and digest h as y ← − ζx−1 (h).

6
2.2.1 Template Construction Based on the message length µ ∈ N and the
parameters A ∈ A a tree template is constructed. The template consists of a
number of block cipher calls called nodes, where the inputs of the block ciphers
are already determined as virtual bits. These come in three flavors:
– Frame bits: these are fixed bits that are determined solely on the message
length µ and the parameters A. For example, these can be used for domain
separation or can encode the length of the message.
– Message pointer bits: these bits reference specific bits in M . For example, a
bit can reference the ‘fifth bit of M ’, but this bit is currently unknown.
– Chaining pointer bits: these bits refer to the result of another compression
call. We require that all first c bits of every compression call are used exactly
once (except the final one which is special) and consecutively, where c ⩽ b
is the capacity. For example, if c consecutive bits refer to the result of (k, x)
it will equal ⌊Ek (x)⌋c when instantiated.
There is one special block cipher call whose output is not used in the tree. This
is called the final node and is denoted by final(S) for an instantiation S. A leaf
node is a node that does not contain any chaining pointer bits.

M0−2 ∥ 0 M3−5 ∥ 0

IV1 E E 1

E y
M6 ∥10 ∥ 0 |M | ∥ 0

IV1 E E

Fig. 1: Basic example of a block-cipher-based tree hashing mode with key size
κ = 4, block size b = 3, capacity c = 3 and message length µ = 7.

A basic example of a block-cipher-based tree hash is displayed in Figure 1.

The different kind of virtual bits in the example are:
– Frame bits: the two IV1 ’s, the 10 (padding), the four 0’s, the 1 and the
encoding of the message length |M |.
– Message pointer bits: the three blocks of M0−2 , M3−5 and M6 .
– Chaining pointer bits: the four outputs of a call to E that are fed into another
block cipher call.
Note that the output of the final node is denoted by y, which is not necessarily
the hash digest; there is an additional finalization function ζ applied to get the
hash digest. In other words, h = ζx (y), with h the hash digest and x and y the

7
in- and outputs of the final node. Furthermore, it is possible to have a capacity
c < b, in which case the chaining values are truncated.

2.2.2 Template Execution The procedure Y[E](M, Z) executes the tree

template Z on a message M with compatible length to get the hash digest
h ∈ {0, 1}n . It uses the following procedure:

– It instantiates the template to get the corresponding tree S. This means

that all message pointer bits are instantiated with their respective value of
M and similarly for all chaining pointer bits, whose values depend on the
block cipher E.
– It gets the inputs of the final node (k, x) = final(S).
– It computes the output of the final node y = Ek (x).
– It returns the data input and output of the final node (x, y).

The tree S is represented as a list composed of values of the form (k, x, α), each
representing one node. k and x are the key and data inputs to the block cipher
and α denotes a different location in the tree. This value means that there is a
block cipher call of the form y = Ek (x) and that the output ⌊y⌋c is used in the
position α. The output of the final node is not used in the tree, which is denoted
by α = ⊥. An example is displayed in Table 2.

node k x α node k x α
0 10−2 ∥ 1 20 ⊥ 0 1101 101 ⊥
1 M3−5 ∥ 0 30 0k0 1 0010 100 0k0
2 |M | ∥ 0 40 0x0 2 1110 010 0x0
3 M0−2 ∥ 0 IV1 1x0 3 0110 000 1x0
4 M6 ∥01 ∥ 0 IV1 2x0 4 1010 000 2x0
(a) List representation of the template (b) List representation of the instanti-
of the example mode. ation of the example mode, with IV1 =
000, M = 011 001 1 and random block
cipher outputs.

Table 2: List representation of the example mode displayed in Figure 1. The

nodes are numbered 0 to 4, with the key input denoted by 0k0 and data input
denoted by 0x0 (for node 0), where the subscript denotes the offset. The k, x and
α denote the key input, the data input and the location the output is used (⊥
for the final node), respectively.

2.2.3 Definitions Now we define a few terms that allow us to reason about
hashing modes. First of all we define the tree template set ZT as the set of all
possible tree templates.

8
Definition 1 (tree template set [DMA18,BDPV14]). For a mode of oper-
ation T we define tree template set ZT as the range of the template construction
function Z:
ZT = { Z(µ, A) | µ ∈ N, A ∈ A } ,
where µ covers all message lengths and A all parameters.
Next, we define some useful subsets of trees that correspond to the tree tem-
plates.
Definition 2 ((sub)tree set [DMA18, BDPV14]). We say that a tree S
complies with a template Z if it has the same tree topology and the frame bits in
Z match those in S.
For a mode of operation T we define the following sets:
– ST is the set of all trees S such that there exists a Z ∈ ZT such that S
complies with Z.
– STsub is the set of trees S such that there exists a S ′ ∈ ST such that S is a
proper subtree of S ′ .
– STleaf is the subset of trees S ∈ STsub such that there exists a S ′ ∈ ST such
that S is a proper subtree of S ′ and S contains all its descendants in S ′ .
– STfinal is the subset of trees S ∈ STsub such that there exists a S ′ ∈ ST such
that S is a proper subtree of S ′ and S contains the root node of S ′ .
Intuitively, ST denotes the set of all possible trees, STsub the set of all their proper
subtrees, STleaf the set of trees that cannot be extended backwards, i.e. ones that
contain all necessary leafs and STfinal the set of proper subtrees that contain the
final node. Now we define the notion of a radical, which is an essential part of
our requirements. Intuitively, a radical identifies bit positions which can only
refer to a chaining value, but has no such value associated yet.
Definition 3 (radical [DMA18]). A radical α in a tree instance S ∈ STsub
identifies c bit positions such that no node is attached to α in S, but in any
S ′ ∈ ST , with S a subtree of S ′ , the value located by α is a CV. This value is
called the radical CV and is denoted as S[α].
For example, take a Merkle-Damgård mode with the domain separation on the
leaf node. That is, all templates are of the form displayed in Figure 2. Given
just the final two nodes (which is 0 : (1, M4 ∥0, ⊥); 1 : (x, M3 ∥0, 0x ) in the list
representation) with arbitrary M3 , M4 and data input x for the node with key
M3 ∥0, this x will always be a chaining value. Only for leaf nodes the data input
is not a chaining value, but we know that this is not a leaf node by the domain
separation. This means that this position (1x ) is a radical.
Another example is displayed in Figure 3. This mode is similar, but with
domain separation on the final node instead of the leaf node. However, this does
mean that the similar final two nodes as before (which is 0 : (1, M4 ∥1, ⊥); 1 :
(x, M3 ∥0, 0x ) in the list representation) with arbitrary M3 , M4 and data input
x for the node with key M3 ∥0 do not have a radical. The data input x could be
a chaining value, but it could also represent a message block, in which case the
message would be x∥M3 ∥M4 . As the role of this x is ambiguous its position (1x )
is not a radical, nor is any other position.

9
 M2 ∥ 1 M3 ∥ 0 M4 ∥ 0

M1 E E E y

Fig. 2: A Merkle-Damgård mode with leaf-node separation. This means that data
inputs are unambiguously either a chaining value or a message block, hence non-
leaf subtrees have radicals.

M2 ∥ 0 M3 ∥ 0 M4 ∥ 1

M1 E E E y

Fig. 3: A Merkle-Damgård mode with final-node separation. This means that

data inputs are ambiguous and no radicals exist.

2.2.4 Conditions We look at the conditions that a tree hashing mode has
to satisfy in order to be secure. Message-decodability states that a message
can be successfully extracted from a full tree, leaf-anchoring requires the first
few bits of every node to either denote a fixed value or a chaining value and
radical-decodability states that the previously defined radicals can efficiently
be identified from chosen set STrad . In general, message-decodability is trivially
satisfied and leaf-anchoring is a straightforward property. Radical-decodability
is a more tricky definition and sometimes requires more work to show.
Definition 4 (message-decodability [DMA18]). A mode of operation T is
message-decodable if there is an efficient function extract() that on input of
S ∈ ST returns the template Z it complies with and the message M , and on
input of S ∈
/ ST returns ⊥.
Definition 5 (leaf-anchoring [DMA18]). A mode of operation T is leaf-
anchored if for every template Z ∈ ZT , the first m ⩽ c of every leaf node
encode IV1 ∈ {0, 1}m as frame bits and the first c bits of every non-leaf node are
chaining pointer bits.
Definition 5 is a minor generalization of the original definition in [DMA18] as it
allows for a more flexible length of IV1 .
Definition 6 (radical-decodability [DMA18]). A mode of operation T is
radical-decodable if there exists a set STrad such that all trees S ∈ STrad have a
radical, and there exists an efficient deterministic function radical() that returns
a radical upon presentation of an S ∈ STrad , and ⊥ otherwise. The set STrad must
satisfy STfinal ⊆ STrad ⊆ STsub \ STleaf .
In essence, radical-decodability requires the existence of an efficient function
radical() that finds chaining values in a tree such that:

10
 1. it only finds radicals (so they are chaining values in every possible tree),
2. it always reconstructs the full tree when starting at the final node and ex-
tending the tree based on the found radicals.

As a first example we take a Merkle-Damgård mode with leaf-anchoring, depicted

in Figure 4. We take STrad = STsub \ STleaf , the largest possible set. This means
that we have to identify a radical for any subtree that is not in STleaf . We do
this by identifying radicals by the absence of IV1 . Our function radical() works
as follows: first we identify the leftmost node (which exists as it is a sequential
mode), then we return its data input if it is not equal to IV1 and return ⊥
otherwise. An implementation of radical() is illustrated in Algorithm 2. We check
the two requirements for radical-decodability.

1. Radicals: indeed, by definition of the mode any data input that is not IV1
has to be a chaining value.
2. Reconstruction: strictly speaking, it does not satisfy this property. If a chain-
ing value is equal to IV1 the function will stop too soon. However, this has a
negligible probability of occurring and in fact our proof already takes it into
account. This means that we can assume that no chaining value hits IV1 ,
hence our function will always reconstruct the message.

An implementation of extract() is also illustrated in Algorithm 3. It is similar

to the procedure radical(), but it extracts the message instead of the radicals.

M1 M2 M3

IV1 E E E y

Fig. 4: A Merkle-Damgård mode with leaf-anchoring. Radical-decodability can

be achieved by identifying radicals by the absence of IV1 in the data input.

Algorithm 1 Helper function to lookup the node pointing to a location

Interface: lookup(S, α′ )
for all i : (k, x, α) ∈ S do
if α = α′ then
return i : (k, x, α)
end if
end for
return ⊥

11
Algorithm 2 Implementation of radical() for the mode pictured in Figure 4
Interface: radical(S)
α′ ← ⊥ ▷ initialize with the final node
while lookup[S](α′ ) ̸= ⊥ do
i : (k, x, α) ← lookup(S, α′ ) ▷ lookup the chaining value
if x = IV1 then ▷ apply leaf-anchoring
return ⊥ ▷ full tree
end if
α′ ← ix0 ▷ the data input contains the next potential radical
end while
return α′ ▷ radical found

Algorithm 3 Implementation of extract() for the mode pictured in Figure 4

Interface: extract(S)
M′ ← ε ▷ initialize with the empty string
α′ ← ⊥
while lookup[S](α′ ) ̸= ⊥ do
i : (k, x, α) ← lookup(S, α′ )
M′ ← k ∥ M′ ▷ the key input contains a message block
if x = IV1 then
return (M ′ , ∅) ▷ return the message and no parameters
end if
α′ ← ix0
end while
return ⊥

As a second example we take a Merkle-Damgård mode with final-node sep-

aration and length encoding, but without leaf anchoring, depicted in Figure 5.
This means that we cannot identify radicals by the absence of IV1 anymore.
However, we can make use of the other properties. We take STrad = STfinal , the
smallest possible set. This means that we only have to identify a radical for any
subtree that contains the final node. As we have final-node separation we can
identify this. If the given tree does not contain a final node, we always return ⊥
as we do not know how long the message is, which is allowed by the definition of
radical-decodability as those trees are not in STrad . If a tree does contain a final
node we can read the length of the message from it. Using this, we know the
number of block cipher calls, from which we can deduce whether the data input
is a chaining value or a message block, satisfying radical-decodability. An imple-
mentation of radical() is illustrated in Algorithm 4. The procedure extract() is
not illustrated but is again very similar to radical(), but it extracts the message
instead of the radicals.
Finally we may revisit the example in Figure 3. We already noted that no
radicals exist for this mode, meaning that only STrad = ∅ is possible. However,
this contradicts the requirement that STfinal ⊆ STrad , hence this construction is
not radical-decodable.

12
 M2 ∥ 0 M3 ∥ 0 2∥1

M1 E E E y

Fig. 5: A Merkle-Damgård mode with final-node separation and length encoding.

Radical-decodability can be achieved by identifying the final node and using the
length to know when to stop extending the tree.

Algorithm 4 Implementation of radical() for the mode pictured in Figure 5

Interface: radical(S)
i : (k, x, α) ← lookup(S, ⊥)
ℓ∥s←k ▷ with |s| = 1
if s = 0 then
return ⊥ ▷ fail if it is not a final node
end if
α′ ← ix0
for j ← 0 to ℓ do ▷ process ℓ blocks based on the length encoding
if lookup[S](α′ ) = ⊥ then
return α′
end if
i : (k, x, α) ← lookup(S, α′ )
α′ ← ix0
end for
return ⊥

Now we define subtree-freeness, which is a generalization of the problem in

length-extension attacks and states that a full tree can never be a subtree of a
different tree.
Definition 7 (subtree-freeness [DMA18]). A mode of operation T is subtree-
free if
ST ∩ STsub = ∅.
Next, we introduce some new conditions not present in [DMA18]. These are
about full and partial final-anchoring. Full final-anchoring states that the full
input of the final node should contain a fixed value, while partial final-anchoring
additionally allows for a single chaining value to be present.
Definition 8 (full final-anchoring). A mode of operation T that is leaf-anchored
is fully final-anchored if for every template Z ∈ ZT the first b bits of the final
node encode IV2 ∈ {0, 1}b as frame bits.
Strictly speaking, a mode cannot satisfy both leaf-anchoring and full final-
anchoring as the definitions conflict on the first c bits of the final node. Leaf-
anchoring requires these bits to be chaining pointer bits, while full final-anchoring
requires them to encode IV2 . However, in our definition, we make an exception for

13
this: the requirement of full final-anchoring overwrites the one of leaf-anchoring
for the final node.
The final block cipher call of a mode with full final-anchoring will always
look like the example in Figure 6.

M1 M2

IV1 E E

IV2 E y

Fig. 6: Example mode using full final-anchoring.

Definition 9 (partial final-anchoring). A mode of operation T that is leaf-

anchored is partially final-anchored if for every template Z ∈ ZT the following
holds for the final node:

– When it is a leaf node, it encodes IV′1 as frame bits, where IV′1 ∈ {0, 1}b with
⌊IV′1 ⌋m = IV1 .
– When it is a non-leaf node, the first c bits are chaining pointer bits and its
last b − c bits encode IV2 ∈ {0, 1}b−c as frame bits.

There may be P different possibilities for IV2 , denoted by the set IV 2 .

An example of a mode using partial final-anchoring is depicted in Figure 7.

M1 M2

IV1 E E y
IV2

Fig. 7: Example mode using partial final-anchoring.

2.3 Indifferentiability

We use the indifferentiability framework introduced by Maurer et al. [MRH04]

applied to hash functions by Coron et al. [CDMP05].

14
Definition 10. Let T be a hashing mode based on a block cipher E : {0, 1}κ ×
{0, 1}b → {0, 1}b , finalization ζ : {0, 1}b × {0, 1}b → {0, 1}n , template construc-
tion Z and with Y the template execution function as described in Section 2.2.2.
Let RO be a random oracle with the same domain and range as ζ ◦ Y[E] and S
be a simulator with oracle access to RO. The indifferentiability advantage of a
distinguisher D is defined as
 h i h i
ζ◦Y[E],E,E −1 −1
Advdiff
T [E],S (D) = P D = 1 − P DRO,S[RO],S [RO] = 1  ,
 

where D can only make construction queries (M, Z) such that Z = Z(M, A) for
some A ∈ A.

2.4 Elementary Results

Our proof will rely on the H-coefficient technique introduced by Patarin [Pat08]
and modernized by Chen and Steinberger [CS14]. Let D be a information-
theoretic deterministic distinguisher trying to distinguish O1 = (ζ ◦ Y[E], E, E −1 )
and O2 = (RO, S[RO], S −1 [RO]). Let ν be the view of D after interacting with
either oracle, consisting of a list of all its queries made. Let DO1 denote the
probability distribution of views of D interacting with O1 and DO2 likewise for
O2 . A view ν is attainable if it can be observed by D in the ideal world, i.e.
P [DO2 ] > 0. We define V as the set of all attainable views. The H-coefficient
technique states the following for Advdiff
T [E],S (D).

Lemma 1 (H-coefficient Technique [Pat08,CS14]). Let O1 = (ζ◦Y[E], E, E −1 )

and O2 = (RO, S[RO], S −1 [RO]). Let D be a deterministic distinguisher and
V = Vgood ∪ Vbad be a partition of the set of views into good and bad views. Let
ε ⩾ 0 be such that for all ν ∈ Vgood :

P [DO1 = ν]
⩾ 1 − ε.
P [DO2 = ν]

Then Advdiff
T [E],S (D) ⩽ ε + P [DO2 ∈ Vbad ].

We will have to upper bound the probability of multi-collisions. We use the

following result from Choi et al. [CLL19] for this.
Lemma 2. Suppose we have a sequence of s elements where every element is
randomly chosen from {0, 1}a and let Fx denote the number of elements that hit
the value x ∈ {0, 1}a . Then we have that
h i 2s
E max Fx ⩽ a + ln(s) + a + 1.
x 2
Proof. We follow the same reasoning as in Equation 3 in [CLL19].
The variable Fx can be seen as the sum of s Bernoulli variables Bi with
parameter p = 1/2a . As

E etBi = 1 + p(et − 1) ⩽ 1 + 2pt ⩽ e2pt

 

15
for any 0 < t ⩽ 1, we can apply the Chernoff bound to get
a 1
P [Fx ⩾ j] ⩽ e−t(j−2ps) = e−t(j−2s/2 )
⩽ .
s · 2a
for any j ⩾ 2s/2a + ln(s · 2a )/t. Therefore we have
h i X h i
E max Fx = P max Fx ⩾ j
x x
j⩾1
2s X h i
⩽ + ln(s · 2a )/t + P max Fx ⩾ j
2a x
j>2s/2a +ln(s·2a )/t
2s X X
⩽ + ln(s · 2a )/t + P [Fx ⩾ j]
2a
j>2s/2a +ln(s·2a )/t x∈{0,1}a
a
2s s·2
⩽ + ln(s · 2a )/t +
2a s · 2a
2s
⩽ a + (ln(s) + a)/t + 1.
2
Setting t = 1 gives the desired result. ⊔
⊓

3 Errors
The faulty bounds in the original analysis in [DMA18] were superficially cor-
rected in [GDM20]. Nevertheless, a more thorough investigation reveals that the
root cause is more fundamental and applies to many earlier indifferentiability
proofs.
The main error is that the calls to the random oracle from the simulator are
considered to be random. The output of the random oracle is indeed random.
However, as the distinguisher also has access to this random oracle, it might know
the output beforehand. Let us take a look at a simple example of this. Let D
be a distinguisher that makes the following queries, where T is the construction
oracle of a simple Merkle-Damgård-like mode and E the primitive oracle, with
the message M consisting of one block:
– query T (M ) = h,
– query Eh (IV1 ) = y,
– query EM (IV1 ) = h.
The final output needs to be h, as this computes the hash of M .
As the simulator simulates E, the only queries that it sees are (h, IV1 ) with
output y and (M, IV1 ) with output h. Although this h comes from the random
oracle, its value is magically equal to the key input of the first query, from the
simulator’s point of view.
When presented in this way, it may be obvious that the output of (M, IV1 )
cannot be considered random as it is part of the fundamental interaction be-
tween the oracles. However, it becomes more subtle when it is more abstractly

16
presented and when some simplifications are made. It is very common to rep-
resent the queries to the oracle as two separate lists. In the above example
we would get the list M = ((M, h)) for the construction oracle and the list
L = ((h, IV1 , y), (M, IV1 , h)) for the primitive oracle. These lists contain dupli-
cate information, as from either (M, h) or (M, IV1 , h) we can derive the fact that
the hash of the message M is equal to h. In order to simplify the analysis we
might be tempted to drop one of these queries. For example, we might drop all
queries from M which can be derived from L. In this case this means that M be-
comes empty and we would only have to consider L = ((h, IV1 , y), (M, IV1 , h)).
However, this is a faulty reasoning as the output of (M, IV1 ) is always h and
cannot be considered to be randomly generated.
Besides [DMA18], where the error had a significant influence on the proven
security bound, the same error appeared in multiple other papers as well [CN08,
MPN10, MP15, Lee17, BN18, ABR21].
– In [CN08], the authors use the following reasoning in the Section ‘Some
Important Observations’:
“Thus, we assume that A do not make any O1 -query which is computable
from the previous query-responses of O2 . More particularly, we can remove
all those O1 -queries from the final view which are computable from the query-
responses of O2 .”
Here, A denotes the distinguisher, O1 the construction oracle and O2 the
primitive oracle. The first sentence is correct, but the second one is not.
The error can be fixed in a straightforward manner by not removing those
queries from the final view. The probabilities have to be computed in a
slightly different way, as some output will be known. However, as the only
way these known outputs are used is in upper bounding the probability of
a mutlicollision, whose analysis remain exactly the same, this does not have
any influence on the bound.
– The same error appeared in work on the indifferentiability of the sum of
permutations [MPN10, MP15, Lee17, BN18]. In the original paper [MPN10]
they apply a common transformation to the distinguisher D. The new distin-
guisher D′ is the same as D, but it additionally verifies all the construction
queries. This transformation is fine as it simplifies some analysis, we use
this transformation as well. However, after this transformation they simply
ignore the queries to the random oracle, which is not correct. The other pa-
pers [MP15,Lee17,BN18] are based on this and also copy the same error. As
a matter of fact [DMA18] copied the approach from them as well.
Looking at the most recent work with the best bound [BN18], the error does
have a significant impact on the proof. The primitive queries are viewed as
random variables, without taking possible construction queries into account.
These queries influence the distributions, which has a significant effect on the
proof as these distributions are used in the χ2 -technique. This does not mean
that the bound is necessarily incorrect, but the proof has to be significantly
changed.
– The same error appeared in recent work of Andreeva et al. [ABR21]. In Sec-
tion 5 the authors show that their ABR+ mode is indifferentiable. However,

17
 again, after the common transformation to D′ at the start of Section 5.3
the construction queries are incorrectly ignored. Nevertheless, in this case
the error should not have an impact on the result. As the construction is
fixed-length and uses a different random function (not permutation) in all
locations, including the final one, the knowledge of the construction results
will be independent and not influence other parts. In short, although the pa-
per makes the same common error, the result should still be correct because
of the specifics of the construction.

A possible cause for the error can be from the notations of the views. It is
convenient to denote the interaction of the construction and primitive oracles
separately. However, this notation can be misleading. It implies that the inter-
action between the two different oracles is somewhat disconnected, while this is
not the case. The common error of dropping all the queries to the construction
oracles is basically equivalent to changing the security model. Instead of always
having access to both oracles, the adversary instead operates in two phases: first
it is only allowed access to the primitive oracle and after it is done with this
oracle, it is allowed to only query the construction oracle. A way to prevent this
faulty implication is to denote the view in one list. In our example we would
denote the view as ν = ((M, h), (h, IV1 , y), (M, IV1 , h)), where the final h con-
tains no randomness. This can complicate the analysis, depending on the used
mode. It can be easier to use this reasoning when there is truncation involved,
as that means that there is still some randomness in the query that can be used.
For example, the work [CLL19] does do this correctly: they denote the view as
a single list and also have a mode using truncation.

4 Results

For all results stated below we consider a tree hashing mode based on a b-bit
block cipher and with capacity c denoting the size of the chaining values. These
results are also summarized in Table 1.

Theorem 1. Let T be a mode that is subtree-free, radical-decodable, message-

decodable, leaf-anchored with IV1 -length m and has finalization function ζ(y) =
⌊y⌋n . Then there exists a simulator S such that for any distinguisher D that
makes q queries total and r queries to the construction oracle we have

q q2 q 2 + 2qr (ln(r) + n + 1)q

Advdiff
T [E],S (D) ⩽ m
+ c + + .
2 2 2b 2b−n
The simulator S makes at most q queries to the random oracle.

The proof is given in Section A.

Theorem 2. Let T be a mode that is radical-decodable, message-decodable, leaf-

anchored with IV1 -length m and has finalization function ζ(y) = ⌊y⌋n . Then

18
there exists a simulator S such that for any distinguisher D that makes q queries
total and r queries to the construction oracle we have

q + r q 2 + 2qr q 2 + 2qr  q q 
Advdiff
T [E],S (D) ⩽ + + + (ln(r) + n + 1) + .
2m 2c 2b 2c−n 2b−n
The simulator S makes at most q queries to the random oracle.
The proof is given in Section A.6.
Theorem 3. Let T be a mode that is radical-decodable, message-decodable, leaf-
anchored with IV1 -length m and has finalization function ζ(y) = ⌈y⌉n . Then
there exists a simulator S such that for any distinguisher D that makes q queries
total and r queries to the construction oracle we either have

q q2 q2
Advdiff
T [E],S (D) ⩽ m
+ c + b−n ,
2 2 2
if b − n ⩾ c, and

q + r q2 q 2 + 2qr (2 ln(r) + 2n + 2)q

Advdiff
T [E],S (D) ⩽ m
+ c + +
2 2 2b 2b−n
otherwise. The simulator S makes at most q queries to the random oracle.
The proof is given in Section A.7.
Theorem 4. Let T be a mode that is subtree-free, radical-decodable, message-
decodable, leaf-anchored with IV1 -length m, fully final-anchored and has final-
ization function ζ(y) = y. Then there exists a simulator S such that for any
distinguisher D that makes q queries total and r queries to the construction
oracle we have
q 3q 2 + q 3q 2 + 2qr
Advdiff
T [E],S (D) ⩽ + + .
2m 2c 2b
The simulator S makes at most q queries to the random oracle.
The proof is given in Section B.
Theorem 5. Let T be a mode that is subtree-free, radical-decodable, message-
decodable, leaf-anchored with IV1 -length m, partially final-anchored with P pos-
sibilities for IV2 and has finalization function ζx (y) = x ⊕ y. Then there exists
a simulator S such that for any distinguisher D that makes q queries total and
r queries to the construction oracle we have

q 3q 2 + 4qr + 4r2 + 2r 3q 2 + 2P qr
Advdiff
T [E],S (D) ⩽ + + .
2m 2c 2b
The simulator S makes at most P q 2 queries to the random oracle.
The proof is given in Section C.

19
5 Applications
5.1 Truncated SHA-2
SHA-2 [SHA08] uses a straightforward Merkle-Damgård mode based on a block
cipher with the Davies-Meyer feed-forward on top of it. By using Theorem 2
we are able to prove this mode secure, without requiring any feed-forward. The
mode is illustrated in Figure 8.

M1 M2 M3

IV1 E E E h

Fig. 8: Illustration of the Merkle-Damgård mode used in SHA-2, but without

any feed-forward.

We show that this mode satisfies the required conditions. First of all, it is
message-decodable as the message can be retrieved from the tree and it is also
leaf-anchored by definition. For radical decodability we take STrad = STsub \ STleaf
as the largest possible set and identify radicals by the absence of the IV1 . This
means that we can apply Theorem 2 with m = c = b ∈ {256, 512} the internal
state size and n ∈ {224, 256, 384, 512} (the latter two only for b = 512) the
digest length. If n is close to b this gives an insecure bound, as then the mode is
vulnerable to a length extension attack.

5.2 BLAKE3
BLAKE3 [OANW20] is a recently introduced tree hash that makes full use of
the parallelism that it provides. We will not describe the hashing mode in de-
tail, but we show that with our results we can analyze the security of the mode
of operation of BLAKE3. The BLAKE3 paper cites the article by Daemen et
al. [DMA18] in the security analysis and show that it satisfies the required con-
ditions. This works for the truncated version, but a full-length output version
is also used. For this they informally state that the feed-forward is sufficient for
this. Using our Theorem 5 we are able to show that this informal reasoning is
not completely correct, as the extendable output mode introduces new security
considerations.
We succinctly describe what the final compression call looks like, as that
one is relevant for the applicability of the feed-forward and the partial final-
anchoring. The data input to the final call is of the for form CV∥IV2 ∥t∥b∥d with
key a message M ∈ {0, 1}512 , where CV ∈ {0, 1}256 is the chaining value (or
the initial value, if the block consists of one block), IV2 ∈ {0, 1}128 a fixed value
used for every compression call, t ∈ {0, 1}64 a counter for extendable output,

20
b ∈ {0, 1}32 the number of bytes in the message M and d ∈ {0, 1}32 some
flags. The output of the block cipher is VL ∥VH = EM (CV∥IV2 ∥t∥b∥d), with
VL , VH ∈ {0, 1}256 . The final digest is h = (VL ⊕ VH ) ∥ (VH ⊕ CV). This is also
illustrated in Figure 9.

CV VL hL
E
IV2 ∥t∥b∥d VH hH

Fig. 9: Illustration of the final compression call of BLAKE3.

5.2.1 Fixed Output In the fixed output mode of BLAKE3 the final digest
h is truncated to 256 bits, which corresponds to VL ⊕ VH , where VL ∥VH is
the output of the final block cipher call. This means that no feed-forward with
the previous chaining value is used. Although this finalization is different from
truncation, which would be just VL , this difference is not essential and the result
could be easily modified for this finalization. Therefore, we do get an appropriate
bound from Theorem 1 with b = 512, m = 256, c = 256 and n = 256.

5.2.2 Extendable Output In addition to a fixed output mode, BLAKE3

also introduces an extendable output mode, allowing for an arbitrary number
of output bits, similar to the sponge construction [BDPV07]. In contrast to the
sponge construction, which uses a sequential output, BLAKE3 uses a counter for
its extendable output. It behaves similar to the generic construction where the
counter is appended to the message, which would result in the output H(M ∥0) ∥
H(M ∥1) ∥ H(M ∥2) ∥ . . . for a generic hash function H. In contrast to this
generic construction, the counter is placed in the final compression call, making
computing successive outputs much more efficient, while still allowing efficient
random access in contrast to the sponge. However, as we will see, this feature of
allowing efficient random access comes with new security considerations which
BLAKE3 does not adhere fully.
For the extendable output mode the full output h = (VL ⊕ VH ) ∥ (VH ⊕ CV)
of the compression function is used. To get an arbitrary number of output bits
BLAKE3 uses a counter t that is part of the final compression call. Let ht denote
the output with size b stated above when a counter t is used. Then the full output
is equal to h0 ∥h1 ∥h2 ∥ . . ..
Our definition of a tree hashing mode does not directly include this extend-
able output, but it can be achieved by making use of the parameters. Recall

21
that the tree template does not only depend on the length of the message |M |,
but also on the parameters A which can be chosen freely from a custom defined
set A. In this case we choose A = {0, 1, . . . , ℓ − 1}, where ℓ is the maximum
number of allowed output blocks, to represent the value of the counter t. This
means that the output can be computed by computing the hashes of (M, t) for all
relevant counters t. Note that definition allows for more freedom than a sequen-
tial construction as this t can start at any arbitrary offset. This extra freedom
does correspond to the use of BLAKE3, as it indeed can efficiently compute the
output starting at any offset.
As with the fixed output, this finalization does not directly correspond to our
definition of the feed-forward. But, again, the proof only uses the randomness
of the chaining value, which is included, so the bound of Theorem 5 is still
applicable for this finalization.
A more significant problem arises when we look at the other new require-
ment for a secure mode that uses feed-forwarding. The mode should also satisfy
partial final-anchoring, which means that there should be a limited number of
possibilities for the input of the final compression call other than the chaining
value. As stated earlier, for BLAKE3 this consists of IV2 ∥t∥b∥d, where our main
focus will be t, which is the counter that underlies the extendable output. This
t has ℓ possible values, which is maximum number of allowed output blocks. As
BLAKE3 allows for a maximum of 264 output bytes we get ℓ = 264 /64 = 258 , al-
though the counter can in principle be any 64-bit value. The values b and d both
have 26 possibilities, hence partial final-anchoring is satisfied with P = ℓ · 212 ,
which is typically dominated by ℓ.
This means that we can apply Theorem 5 to this mode with P = ℓ · 212 ,
b = 512, m = 256 and c = 256, with ℓ ⩽ 258 the maximum number of output
blocks in the extendable output mode. Although P is quite large, this still gives
the expected security level as P · 2c ⩽ 2b . There is a downside to the large P ,
though, as the simulator becomes quite inefficient with its query complexity of
P q 2 . This is actually reflected in some non-ideal behavior of BLAKE3 that we
describe next.

5.2.3 Computing the Counter Suppose that a query of the form hL ∥hH =
h = H(M, t) is performed, where M is the message and t the block offset in
the extendable mode, which corresponds to the counter. Assume that M and
h are known to an attacker, but t is not. Ideally, the only way to retrieve t
is to try all possible t′ ⩽ ℓ and check whether H(M, t′ ) equals h. However, in
the case of BLAKE3 this t can be retrieved much more efficiently. Recall that
digest is defined as (VL ⊕ VH ) ∥ (VH ⊕ CV), with VL ∥VH the output of the
final block cipher call. As M is known to the attacker, it can compute CV.
Furthermore, hL = VL ⊕ VH and hH = VH ⊕ CV are also known, so it can
compute VH = hH ⊕ CV and VL = hL ⊕ VH . This means that it can perform
−1
the inverse of the final block cipher call as Em (VL ∥VH ) = CV∥IV2 ∥t∥b∥d, with
m the message input to the final block, and retrieve t this way. This operation

22
costs just one query to E (and some to compute CV), which is significantly less
than the expected ℓ, which can be as high as 258 .
This problem can be illustrated by the following example. Suppose that
BLAKE3 is used as the following illustrative MAC. This MAC gets as input a key
K ∈ {0, 1}128 and a message M ∈ {0, 1}∗ . It splits the key as K = K1 ∥K2 with
K1 ∈ {0, 1}70 and K2 ∈ {0, 1}58 and computes the MAC as H(M ∥K1 , t = K2 ).
For an ideal hash function this construction gives a secure MAC, as the offset
can essentially be viewed as part of the input. However, when instantiated with
BLAKE3 this is not the case. Given h = H(M ∥K1 , t = K2 ) and M , but not K,
an adversary can compute K in roughly 270 queries, instead of the expected 2128 .
This is done by first guessing an arbitrary K1 ∈ {0, 1}70 . Then the adversary
can compute the offset K2 from h and M ∥K1 as described above. If the guess
of K1 is correct, this computes the value of K2 ∈ {0, 1}58 using a single query,
performing a key-recovery attack. As there are 270 possible values for K1 this
attack succeeds using roughly 270 queries. Although BLAKE3 supports a dedi-
cated keyed mode that is preferred, the previous example should still be secure.
This shows that the counter in BLAKE3 can only contain public information.

5.2.4 Conclusion BLAKE3 makes full use of tree hashing capabilities with
an interesting way of generating extendable output by making use of a counter.
Although its tree structure is secure, its use of a counter, which makes efficient
random access possible, comes with new security considerations. In particular,
from a usage perspective it behaves similar to an extra small efficient message
input. However, its security properties do not align with this behavior as the
counter can be efficiently computed by knowing the message and the hash output.
This is not the case for a normal message input, making BLAKE3 in essence
add an extra requirement in that the counter should always be public.

5.3 Tree Sponge

Here we introduce a tree generalization of the sponge construction [BDPV07].

The absorbing phase is generalized to have a tree structure, allowing for paral-
lel compression. Additionally, the squeezing phase is modified to likewise allow
for parallel expansion by making use of a counter. The construction requires a
minimal number of frame bits: the only ones present are initial values required
to prevent inverse queries from succeeding.
First of all we note that all our results also apply to permutations by simply
setting κ = 0. The tree sponge makes use of the flexible conditions present
in Theorem 3. The main observation is that subtree-freeness can be dropped
without negative consequences when the chaining values and the hash digests
originate from different parts of the output of the permutation. This is the same
as in the original sponge construction, which has an inner part that outputs
chaining values, which are secret, and an outer part that outputs hash digests,
which are public.

23
IV1 5 4
p p
M1 M2
3
p
1
6
p
IV1 8 7
IV1 ∥0 11 h0
p p 2
M3 M4 p
9

p
IV1 10
IV1 ∥1 h1
p
M5

absorbing combining squeezing

Fig. 10: Example of the minimal permutation-based tree hashing mode with
w = 2 giving two blocks of output. The order in which the radicals are identified
is indicated by the gray numbers 1–11, starting from the final permutation call
resulting in h0 . Underlined numbers indicate a radical, while the other numbers
indicate a different value: either a leaf or a counter value. The dashed permu-
tation call resulting in h1 is not part of the tree found by the radical finding
algorithm.

5.3.1 Description The tree sponge contains three different phases and de-
pends on a fixed parameter w ∈ N>0 representing the width:

– Absorbing. In this phase the message is split such that every part can be
absorbed by a sponge of width w. The final part may be smaller. All different
parts are absorbed this way in parallel and each generate their own chaining
value.
– Combining. The chaining values generated in the previous phase are com-
bined by using a tree structure. The chaining values are split into two non-
empty parts, with the first part the largest possible power of two. The two
parts are recursively reduced to a single chaining value and combined using
a permutation call.

24
Algorithm 5 Implementation of the tree sponge mode pictured in Figure 10
Interface: TreeSponge(M, t)
CV ← combine(M )
return ⌈p(CV ∥ IV1 ∥ t)⌉3b/4

Interface: combine(M )
W ← w · b/2 + b/4 ▷ maximum sequential absorption
if |M | ⩽ W then
return absorb(M )
end if
k ← ⌊log2 (|M |/W )⌋ ▷ largest k such that W · 2k ⩽ |M |
ML ∥ MR ← M ▷ with |ML | = W · 2k
CVL ← combine(ML )
CVR ← combine(MR )
return ⌊p(CVL ∥ CVR )⌋b/2

Interface: absorb(M )
M0 ∥ M1 ∥ · · · ∥ Mℓ−1 ← M ▷ with |M0 | = 3b/4 and |Mi | = b/2
x ← IV1 ∥ M0
for i ← 1 to ℓ do
x ← ⌊p(x)⌋b/2 ∥ Mi
end for
return ⌊p(x)⌋b/2

– Squeezing. The resulting chaining value is fed into multiple final permutation
calls appended by IV1 ∥t, with t = 0, 1, . . . a counter for an arbitrary long
output.
An example of this mode is pictured in Figure 10 and an implementation is
illustrated in Algorithm 5.

5.3.2 Security We show that this mode satisfies the required conditions.
Again, message-decodability and leaf-anchoring are satisfied in a straightforward
way. Radical-decodability is more interesting for this mode.
We take STrad = STsub \ STleaf as the largest possible set and use leaf-anchoring
to identify most radicals. We identify leaf nodes by the occurrence of IV1 , which
do not have any radical. If we do not find a leaf node, we do not immediately
know whether the node has one or two chaining values. However, we only have
to find one radical at a time and we know that the first c bits will always point to
a chaining value. We continue this process for the topmost chaining value until
we hit a leaf node. Then we know that the first w calls after the leaf node are
sequential and do not have any other chaining values. All the other nodes do
have a chaining value in the bottom halve and we recursively continue the process
on all those values. The only exception is the counter in the end, but we can
recognize this again by the presence of IV1 . Furthermore, the fact that the final
message block may have a width smaller than w does not matter as it is the final

25
block the algorithm finds. An example of this process is pictured in Figure 10
by the gray numbers and an implementation is illustrated in Algorithm 6.

Algorithm 6 Implementation of radical() for the tree sponge mode pictured in

Figure 10
Interface: radical(S)
(α, depth) ← radical′ (S, ⊥)
return α

Interface: radical′ (S, α′ )

if lookup(S, α′ ) = ⊥ then
return (α′ , ⊥)
end if
i : (k, x, α) ← lookup(S, α′ )
if ⌊x⌋b/4 = IV1 then
return (⊥, 1) ▷ end of path by leaf-anchoring
end if
α′ ← ix0
(α′ , depth) ← radical′ (S, α′ ) ▷ scan the top half for radicals
if α′ ̸= ⊥ then
return (α′ , ⊥)
end if
if depth ̸= ⊥ ∧ depth < w then
return (⊥, depth + 1) ▷ absorb phase
else
x1 ∥ x2 ← x ▷ with |x1 | = |x2 | = b/2
if ⌊x2 ⌋b/4 = IV1 then
return (⊥, ⊥) ▷ squeeze phase
else
α′ ← ixb/2 ▷ combine phase
return radical′ (S, α′ ) ▷ scan the bottom half for radicals
end if
end if

Given a permutation of size b we choose c = b/2 as we have a binary tree.

This leads to a security level of at most b/4, which is inherently the maximum
for a permutation-based tree hash. Given this security level we are additionally
able to choose m = b/4 and n = 3b/4 to optimize the efficiency while keeping
the same security level.

6 Proof Sketch

The full proof is given in the Supplementary Material, but the main ideas in it
are the following:

26
 – The simulator uses radical-decodability to reconstruct the tree correspond-
ing to a (potential) message. Message-decodability is used to reconstruct
the message in order to be consistent with the random oracle. Otherwise
randomly generated values are used.
– Various bad events are defined to make sure the following properties hold
for good views:
• The simulator is consistent with the random oracle.
• The simulator is consistent as a permutation, i.e. Sk (x1 ) = Sk (x2 ) im-
plies x1 = x2 and similar for the inverse.
The main goal of the bad events is to prevent various collisions and to prevent
inversions of the final compression call. This last property was not handled
appropriate in [DMA18] and is solved by the various finalization functions:
• Truncation/Chopping: by throwing away part of the input the inverse
calls can only succeed by guessing the discarded bits, which is negligible
for sufficient truncation.
• Enveloped: as in the final compression call the message related can only
be part of the key input, no information can be gained from an inverse
call. The output contains the data input, which is constant. Notably,
the inverse simulator has to modified to account for the possibility of
making an unorthodox query by computing the hash normally, except
for the final call for which the inverse is used.
• Feed-forward: this case is similar to the enveloped case. A key difference
is that the final inverse call does not necessarily correspond to a single
message, making the inverse simulator having to loop over all possibili-
ties.
These bad events occur with negligible probability as all the values are ran-
domly generated. Most of the difficulty comes from identifying the faulty
queries. As the wrong simplification discussed in Section 3 cannot be ap-
plied, it becomes more tricky to identify the faulty queries, which become
more varied. This is especially true for the feed-forward mode as the inverse
queries can correspond to multiple messages.

Acknowledgments. Aldo Gunsing is supported by the Netherlands Organisa-

tion for Scientific Research (NWO) under TOP grant TOP1.18.002 SCALAR.

References

ABR21. Elena Andreeva, Rishiraj Bhattacharyya, and Arnab Roy. Compactness

of Hashing Modes and Efficiency Beyond Merkle Tree. In Anne Canteaut
and François-Xavier Standaert, editors, Advances in Cryptology - EURO-
CRYPT 2021 - 40th Annual International Conference on the Theory and
Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21,
2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer
Science, pages 92–123. Springer, 2021.

27
BDPV07. Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
Sponge functions. Ecrypt Hash Workshop, 2007. http://sponge.noekeon.
org/SpongeFunctions.pdf.
BDPV14. Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
Sufficient conditions for sound tree and sequential hashing modes. Int. J.
Inf. Sec., 13(4):335–353, 2014.
Bel06. Mihir Bellare. New Proofs for NMAC and HMAC: Security without
collision-resistance. In Cynthia Dwork, editor, Advances in Cryptology -
CRYPTO 2006, 26th Annual International Cryptology Conference, Santa
Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117
of Lecture Notes in Computer Science, pages 602–619. Springer, 2006.
BN18. Srimanta Bhattacharya and Mridul Nandi. Full Indifferentiable Security of
the Xor of Two or More Random Permutations Using the χ2 Method. In
Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology
- EUROCRYPT 2018 - 37th Annual International Conference on the The-
ory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April
29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in
Computer Science, pages 387–412. Springer, 2018.
BR06. Mihir Bellare and Thomas Ristenpart. Multi-Property-Preserving Hash
Domain Extension and the EMD Transform. In Xuejia Lai and Kefei Chen,
editors, Advances in Cryptology - ASIACRYPT 2006, 12th International
Conference on the Theory and Application of Cryptology and Information
Security, Shanghai, China, December 3-7, 2006, Proceedings, volume 4284
of Lecture Notes in Computer Science, pages 299–314. Springer, 2006.
Bra90. Gilles Brassard, editor. Advances in Cryptology - CRYPTO ’89, 9th Annual
International Cryptology Conference, Santa Barbara, California, USA, Au-
gust 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer
Science. Springer, 1990.
CDMP05. Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, and Prashant
Puniya. Merkle-Damgård Revisited: How to Construct a Hash Function.
In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th
Annual International Cryptology Conference, Santa Barbara, California,
USA, August 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in
Computer Science, pages 430–448. Springer, 2005.
CLL19. Wonseok Choi, Byeonghak Lee, and Jooyoung Lee. Indifferentiability of
Truncated Random Permutations. In Steven D. Galbraith and Shiho Mo-
riai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th Interna-
tional Conference on the Theory and Application of Cryptology and In-
formation Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part
I, volume 11921 of Lecture Notes in Computer Science, pages 175–195.
Springer, 2019.
CLNY06. Donghoon Chang, Sangjin Lee, Mridul Nandi, and Moti Yung. Indif-
ferentiable Security Analysis of Popular Hash Functions with Prefix-Free
Padding. In Xuejia Lai and Kefei Chen, editors, Advances in Cryptology
- ASIACRYPT 2006, 12th International Conference on the Theory and
Application of Cryptology and Information Security, Shanghai, China, De-
cember 3-7, 2006, Proceedings, volume 4284 of Lecture Notes in Computer
Science, pages 283–298. Springer, 2006.
CN08. Donghoon Chang and Mridul Nandi. Improved Indifferentiability Secu-
rity Analysis of chopMD Hash Function. In Kaisa Nyberg, editor, Fast

28
 Software Encryption, 15th International Workshop, FSE 2008, Lausanne,
Switzerland, February 10-13, 2008, Revised Selected Papers, volume 5086
of Lecture Notes in Computer Science, pages 429–443. Springer, 2008.
CS14. Shan Chen and John P. Steinberger. Tight Security Bounds for Key-
Alternating Ciphers. In Nguyen and Oswald [NO14], pages 327–350.
Dam89. Ivan Damgård. A Design Principle for Hash Functions. In Brassard [Bra90],
pages 416–427.
DMA18. Joan Daemen, Bart Mennink, and Gilles Van Assche. Sound Hashing Modes
of Arbitrary Functions, Permutations, and Block Ciphers. IACR Trans.
Symmetric Cryptol., 2018(4):197–228, 2018.
DRRS09. Yevgeniy Dodis, Leonid Reyzin, Ronald L. Rivest, and Emily Shen. Indif-
ferentiability of Permutation-Based Compression Functions and Tree-Based
Modes of Operation, with Applications to MD6. In Orr Dunkelman, ed-
itor, Fast Software Encryption, 16th International Workshop, FSE 2009,
Leuven, Belgium, February 22-25, 2009, Revised Selected Papers, volume
5665 of Lecture Notes in Computer Science, pages 104–121. Springer, 2009.
GBK16. Praveen Gauravaram, Nasour Bagheri, and Lars R. Knudsen. Building in-
differentiable compression functions from the PGV compression functions.
Des. Codes Cryptogr., 78(2):547–581, 2016.
GDM20. Aldo Gunsing, Joan Daemen, and Bart Mennink. Errata to Sound Hashing
Modes of Arbitrary Functions, Permutations, and Block Ciphers. IACR
Trans. Symmetric Cryptol., 2020(3):362–366, 2020.
GLC08. Zheng Gong, Xuejia Lai, and Kefei Chen. A synthetic indifferentiability
analysis of some block-cipher-based hash functions. Des. Codes Cryptogr.,
48(3):293–305, 2008.
KBC97. Hugo Krawczyk, Mihir Bellare, and Ran Canetti. HMAC: Keyed-Hashing
for Message Authentication. RFC, 2104:1–11, 1997.
Lee17. Jooyoung Lee. Indifferentiability of the Sum of Random Permutations To-
ward Optimal Security. IEEE Trans. Inf. Theory, 63(6):4050–4054, 2017.
LGD+ 09. Yiyuan Luo, Zheng Gong, Ming Duan, Bo Zhu, and Xuejia Lai. Revisiting
the Indifferentiability of PGV Hash Functions. IACR Cryptol. ePrint Arch.,
2009:265, 2009.
LLG11. Yiyuan Luo, Xuejia Lai, and Zheng Gong. Indifferentiability of Domain
Extension Modes for Hash Functions. In Liqun Chen, Moti Yung, and
Liehuang Zhu, editors, Trusted Systems - Third International Conference,
INTRUST 2011, Beijing, China, November 27-29, 2011, Revised Selected
Papers, volume 7222 of Lecture Notes in Computer Science, pages 138–155.
Springer, 2011.
LMN16. Atul Luykx, Bart Mennink, and Samuel Neves. Security Analysis of
BLAKE2’s Modes of Operation. IACR Trans. Symmetric Cryptol.,
2016(1):158–176, 2016.
Men13. Bart Mennink. Indifferentiability of Double Length Compression Functions.
In Martijn Stam, editor, Cryptography and Coding - 14th IMA International
Conference, IMACC 2013, Oxford, UK, December 17-19, 2013. Proceed-
ings, volume 8308 of Lecture Notes in Computer Science, pages 232–251.
Springer, 2013.
Mer89. Ralph C. Merkle. One Way Hash Functions and DES. In Brassard [Bra90],
pages 428–446.
MP15. Bart Mennink and Bart Preneel. On the XOR of Multiple Random Permu-
tations. In Tal Malkin, Vladimir Kolesnikov, Allison Bishop Lewko, and

29
 Michalis Polychronakis, editors, Applied Cryptography and Network Secu-
rity - 13th International Conference, ACNS 2015, New York, NY, USA,
June 2-5, 2015, Revised Selected Papers, volume 9092 of Lecture Notes in
Computer Science, pages 619–634. Springer, 2015.
MPN10. Avradip Mandal, Jacques Patarin, and Valérie Nachef. Indifferentiability
beyond the Birthday Bound for the Xor of Two Public Random Permu-
tations. In Guang Gong and Kishan Chand Gupta, editors, Progress in
Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryp-
tology in India, Hyderabad, India, December 12-15, 2010. Proceedings, vol-
ume 6498 of Lecture Notes in Computer Science, pages 69–81. Springer,
2010.
MRH04. Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indifferentiabil-
ity, Impossibility Results on Reductions, and Applications to the Random
Oracle Methodology. In Moni Naor, editor, Theory of Cryptography, First
Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA,
February 19-21, 2004, Proceedings, volume 2951 of Lecture Notes in Com-
puter Science, pages 21–39. Springer, 2004.
NO14. Phong Q. Nguyen and Elisabeth Oswald, editors. Advances in Cryptology
- EUROCRYPT 2014 - 33rd Annual International Conference on the The-
ory and Applications of Cryptographic Techniques, Copenhagen, Denmark,
May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer
Science. Springer, 2014.
OANW20. Jack O’Connor, Jean-Philippe Aumasson, Samuel Neves, and Zooko
Wilcox-O’Hearn. BLAKE3. https://blake3.io, 2020.
Pat08. Jacques Patarin. The “Coefficients H” Technique. In Roberto Maria
Avanzi, Liam Keliher, and Francesco Sica, editors, Selected Areas in
Cryptography, 15th International Workshop, SAC 2008, Sackville, New
Brunswick, Canada, August 14-15, Revised Selected Papers, volume 5381
of Lecture Notes in Computer Science, pages 328–345. Springer, 2008.
PGV93. Bart Preneel, René Govaerts, and Joos Vandewalle. Hash Functions Based
on Block Ciphers: A Synthetic Approach. In Douglas R. Stinson, editor,
Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryp-
tology Conference, Santa Barbara, California, USA, August 22-26, 1993,
Proceedings, volume 773 of Lecture Notes in Computer Science, pages 368–
378. Springer, 1993.
SHA08. National Institute of Standards and Technology. Secure Hash Standard
(SHS). Federal Information Processing Standards Publication 180-3, Oc-
tober 2008.

30
Supplementary Material

A Security of Truncation (Theorem 1)

A.1 Distinguisher
We will consider a distinguisher D′ based on D. The distinguisher D′ behaves
similar to D, but it will verify all its queries to the random oracle at the end
by querying the primitive on the necessary queries. This distinguisher has the
same advantage as D as it always outputs the same decision and the simulator
is not influenced as the verification queries happen at the end. Moreover, it
does increase the total query complexity as these verification queries have to be
included, but these extra queries are limited to a maximum of Lr, where L is
the maximum length of a message (in permutation calls).

A.2 Simulator
The simulator consists of two parts: the main simulator defined in Algorithm 8
and the helper functions radicalExtend[L] and radicalValue[L] defined in Algo-
rithm 7, based on [DMA18]. The helper function radicalExtend[L](S) extends
all possible radicals in the given tree S with values from the list L, while the
function radicalValue[L](S) returns the value of a radical that cannot be ex-
tended, if it exists, and ⊥ otherwise. As fixed points are allowed in general, the
algorithm radicalExtend[L](S) could get in an infinite loop. To mitigate this
problem, we can set a maximum message length L (in permutation calls) and
let the algorithm return when its recursion exceeds this L. As this is about the
computational complexity and not the query complexity this L does not show
up in our bound.
The simulator calls radicalExtend[Lrel ](S) for some set Lrel we define later
to determine whether the current query completes a tree in which case it should
query the random oracle and answer accordingly. Otherwise it answers randomly.
On inverse queries it always gives a random output.
The simulator does not consider all queries when looking to complete a tree,
but only queries from Lrel which we recursively define as

Lrel = { (ki , xi , yi ) ∈ Lfwd | radicalExtend[Lrel / ST ∪ STrad } ,

i−1 ](ki , xi ) ∈

where Lfwd are all forward queries made to the simulator and where Lrel
i−1 denotes
the list Lrel up to index i − 1. These should be the only queries that are part of
a complete tree as non-final nodes, which is the reason that the simulator only
considers these queries. The bad events will make sure that this will indeed be
the case. Note that the simulator can efficiently derive Lrel .

A.3 Views
We denote by ν = { (X1 , Y1 ), . . . , (Xq+r , Yq+r ) } the view seen by distinguisher
D′ on interaction, where Xi is the input to either the primitive or construction

31
Algorithm 7
Interface: radicalExtend[L](S)
if radical(S) = ⊥ then
return S
end if
for all (k, x, y) ∈ L do
if ⌊y⌋c = S[radical(S)] then
i ← |S| ▷ fresh node identifier
S ′ ← S ∪ {i : (k, x, radical(S))} ▷ fill in the radical
return radicalExtend[L](S ′ ) ▷ recursively fill in the rest
end if
end for
return S ▷ no extension found

Interface: radicalValue[L](k, x)
S ← radicalExtend[L]({0 : (k, x, ⊥)})
return S[radical(S)]

oracle and Yi the output. We split this view into Lfwd for the forwards primitive
oracle, for which Xi = (ki , xi ) and Yi = yi , into Linv for the inverse primitive
oracle, for which Xi = (ki , yi ) and Yi = xi and into M for the construction
oracle, for which Xi = (Mi , Zi ) and Yi = hi . We combine these lists as this
preserves the order in which the distinguisher made the queries. With Lk we
denote the sublist of the list L containing only queries with key k and with this
key omitted from the list. With domLk we denote the inputs to the block cipher
in the list Lk and with rngLk likewise the outputs from the block cipher. We
define several sublists which all require different analysis. First of all we define
Lrad as
Lrad = { (ki , xi , yi ) ∈ Lfwd | radicalExtend[Lrel rad
i−1 ](ki , xi ) ∈ ST } .

These are radical queries and introduce the radical radicalValue[Lrel

i−1 ](ki , xi ),
which should not be filled. Additionally we define Lcomplete as
Lcomplete = { (ki , xi , yi ) ∈ Lfwd | radicalExtend[Lrel
i−1 ](ki , xi ) ∈ ST } .

These are queries that complete a tree and in the ideal world the simulator
will call the random oracle to determine the result. As a shorthand, we use the
following definition to get the corresponding message for such queries.
Definition 11. Let 1 ⩽ i ⩽ q + r, k ∈ {0, 1}κ and x ∈ {0, 1}b . We define
extractFrom[Lrel
i−1 ](k, x) as
(
extract(radicalExtend[Lrel rel
i−1 ](k, x)) if radicalExtend[Li−1 ](k, x) ∈ ST ,
⊥ otherwise.

Now we define the set Lfwd,known as the queries in Lcomplete whose hash result
is already known to the distinguisher. In the case of truncation, this means that

32
Algorithm 8
Interface: S : {0, 1}κ × {0, 1}b → {0, 1}b , (k, x) 7→ y
if x ∈/ domLk then
S ← radicalExtend[Lrel ](k, x) ▷ radical-extend tree from single node
if S ∈ ST then ▷ query completes tree
(M, Z) ← extract(S) ▷ extract message and tree template
h ← RO(M, Z)
$
y←− ζ −1 (h)
else ▷ query does not complete tree
$
y←− {0, 1}b
end if
Lk (x) ← y
end if
return Lk (x)

Interface: S −1 : {0, 1}κ × {0, 1}b → {0, 1}b , (k, y) 7→ x

if y ∈
/ rngLk then
$
x←− {0, 1}b
−1
Lk (y) ← x
end if
return L−1k (y)

the distinguisher already knows the first n bits of the output, while the last b − n
bits are randomly generated.
Lfwd,known = { (ki , xi , yi ) ∈ Lcomplete | extractFrom[Lrel
i−1 ](ki , xi ) ∈ domMi−1 }

This is the essence of the error in [DMA18]: there it was assumed that all bits
are randomly generated.
The complement of this are queries which are completely unknown to the
distinguisher. Even if a query completes a tree and queries the random oracle, if
the distinguisher does not know the hash output, all bits are randomly generated
from its point of view. We define Lfwd,random as exactly this set.
Lfwd,random = Lfwd \ Lfwd,known .
Finally, we note that Lrel = Lfwd \ (Lrad ∪ Lcomplete ) ⊆ Lfwd,random , which means
that all queries that the simulator considers in building the tree are completely
randomly generated.
We also split M into two smaller sets, similar to Lfwd,known .
Mknown = { (Mi , Zi , hi ) ∈ M | ∃(kj , xj , yj ) ∈ Lcomplete
i−1 : extractFrom[Lrel
j−1 ](kj , xj ) = (Mi , Zi ) } ,

Mrandom = M \ Mknown .

The output of queries in Mknown are already completely known to the distin-
guisher and essentially contain no information, while queries in Mrandom are
completely randomly generated.

33
 An attainable view ν is called bad if:

(i) There exist (ki , xi , yi ), (kj , xj , yj ) ∈ Lrel with i < j such that ⌊yi ⌋c = ⌊yj ⌋c .
(ii) There exist (ki , xi , yi ) ∈ Lrad and (kj , xj , yj ) ∈ Lrel with i < j such that
⌊yj ⌋c = radicalValue[Lrel i−1 ](ki , xi ).
(iii) There exists (ki , xi , yi ) ∈ Linv such that ⌊xi ⌋m = IV1 .
(iv) There exist (ki , xi , yi ) ∈ Linv and (kj , xj , yj ) ∈ Lrel such that ⌊xi ⌋c = ⌊yj ⌋c
(v) There exist (ki , xi , yi ) ∈ Lrel such that ⌊yi ⌋m = IV1 .
(vi) There exist (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈ Lfwd with i < j and
ki = kj such that yi = yj .
(vii) There exist (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈ Linv with i < j and
ki = kj such that xi = xj .

Bad events (i)–(iv) ensure the consistency of the simulator with the random
oracle, bad event (v) allows for the relaxation in the definitions of radical-
decodability and subtree-freeness, while bad events (vi) and (vii) ensure that
the simulator is consistent as a permutation.
An important property of the simulator is that it should be consistent with
the random oracle on good views. To show this, we first define what the verifi-
cation queries are.
Definition 12. For every query (M, Z, h) ∈ M we define the ιfinal (M, Z) as the
index on which the distinguisher D′ made the final verification query for message
(M, Z). By our definition of D′ , we know that this query exists.
Now we show that the simulator is consistent with the random oracle.
Lemma 3. Let ν be an attainable view such that none of the bad events (i)–(v)
happen. Then for every query (M, Z, h) ∈ M we have that (ki , xi , yi ) ∈ Lcomplete
and ζ(yi ) = h, where i = ιfinal (M, Z).

Proof. We show that the simulator agrees with the random oracle. Let (M, Z, h) ∈
M. First we show that all non-final verification queries belong to Lrel . In par-
ticular, we show that they cannot be in either Lcomplete , Lrad or Linv . First of
all, they cannot be in Lcomplete , as that would contradict subtree-freeness in
combination with radical-decodability. Second, we show that any subtree can-
not contain queries in Lrad or Linv by using induction based on leaf-anchoring,
which states that any subtree will be a leaf node or a non-leaf node with a smaller
subtree as a child.
Leaf nodes cannot be in Lrad as STleaf ∩ STrad = ∅, and they cannot be in Linv
either by bad event (iii).
Non-leaf nodes cannot be in Lrad as the radical has to be filled in. As this
refers to a smaller subtree, it has to consist of queries in Lrel . This cannot be
done earlier by the definition of radical-decodability and cannot be done later
by bad event (ii). Non-leaf nodes cannot be in Linv by bad event (iv).
This means that we can only consider the queries in Lrel , which is what
the simulator does. By bad event (i) the tree is also uniquely defined, which
means that, in combination with radical-decodability and message-decodability,

34
the simulator also finds the right message if the final verification query happened
last. If the final query did not happen last it had to be in STrad as STfinal ⊆ STrad ,
but that would contradict bad event (ii) in a later query. ⊔
⊓
Corollary 1. For any good view we have |Mrandom | = |Lfwd,known |.
Proof. By Lemma 3 every query in M is correctly verified. For queries in Mknown
this happened in a previous query which cannot be in Lfwd,known . For queries
in Mrandom this happens later, hence that query has to be in Lfwd,known . This
means that |Mrandom | = |Lfwd,known | as this mapping is bijective. ⊔
⊓

A.4 Analysis of Bad Views

First we analyze bad events (i)–(v). As all relevant values are uniformly randomly
generated from {0, 1}c (for (i), (ii) and (iv)) or {0, 1}m (for (iii) and (v)), we get
the following upper bounds:
(i) |Lrel |2 /2c .
(ii) |Lrad | · |Lrel |/2c .
(iii) |Linv |/2m .
(iv) |Linv | · |Lrel |/2c .
(v) |Lrel |/2m .
Combining these upper bounds, we get a total upper bound of
|Linv | + |Lrel | (|Lrel | + |Lrad | + |Linv |) · |Lrel | q q2
+ ⩽ + .
2m 2c 2m 2c
The analysis of bad events (vi) and (vii) is more elaborate.
(vi) In order to make the analysis easier, we define the following helper event:
1. There exist (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈ Lfwd,known with
i < j such that yi = yj .
For this helper event to occur between (ki , xi , yi ) ∈ Lfwd ∪Linv and (kj , xj , yj ) ∈
Lfwd,known with i < j we need to have both ⌊yi ⌋n = ⌊yj ⌋n and ⌈yi ⌉n =
⌈yj ⌉n . As ⌊yj ⌋n = hk for some (Mk , Zk , hk ) ∈ Mrandom
j−1 and ⌈yj ⌉n is ran-
domly generated, this gives a probability for a single suitable query with
hk = ⌊yi ⌋n of 1/2b−n . Let Fh denote the number of queries (Mk , Zk , hk ) ∈
Mrandom with hk = h. As every query in Lfwd,known corresponds to a unique
query in Mrandom there are at most F⌊yi ⌋n suitable queries (kj , xj , yj ) ∈
Lfwd,known for any (ki , xi , yi ) ∈ Lfwd ∪ Linv , giving a maximum of |Lfwd ∪
Linv | · maxh Fh possible pairs, which in turns gives an upper bound of
X |Lfwd ∪ Linv |  
q
 
· x · P max Fh = x = b−n · E max Fh .
x
2b−n h 2 h

By Lemma 2 this leads to the upper bound

 
q 2r 2qr (ln(r) + n + 1)q
b−n
· n
+ ln(r) + n + 1 ⩽ b + .
2 2 2 2b−n

35
 Now we derive the real bad event under the assumption that the helper
event does not occur. Let (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈
Lfwd with i < j. By our helper event we can assume that (kj , xj , yj ) ∈
Lfwd,random , hence it is randomly generated. This gives a bound of
|Lfwd ∪ Linv | · |Lfwd,random |
.
2b
(vii) As (kj , xj , yj ) ∈ Linv is randomly generated, the probability is bounded by
|Lfwd ∪ Linv | · |Linv |
.
2b
The probability of bad event (vi) and (vii) combined is bounded by
|Lfwd ∪ Linv | · (|Lfwd,random | + |Linv |) q2
b
⩽ b,
2 2
with the helper event having an upper bound of
2qr (ln(r) + n + 1)q
+ .
2b 2b−n
Combining all these gives
 ′  q q2 q 2 + 2qr (ln(r) + n + 1)q
P DO ∈ Vbad ⩽ m + c + + .
2
2 2 2b 2b−n

A.5 Analysis of Good Views

A.5.1 Real World In the real world the randomness is generated by the
primitive oracle. For every construction query, the necessary primitive queries
are implicitly made. First of all, we want to make these implicit queries explicit.
As our modified distinguisher D′ verifies all the construction queries, this only
may move some queries forward in the list. As the queries were already made
implicitly, this does not influence the probability.
By Lemma 3 this means that every query (Mi , Zi , hi ) ∈ M can be derived
correctly from νi−1 , hence these queries have a probability 1 of occurring. As
we are working with a block cipher, every query (ki , xi , yi ) ∈ Lfwd ∪ Linv has a
probability of 1/(2b − qk,i ) of occurring, where qk,i is the number of queries made
with key k before query i. Furthermore, by bad events (vi) and (vii), and the
fact that all construction queries are verified, there is no (implicit) permutation
inconsistency and no outputs have probability 0. As all these probabilities are
independent the final probability becomes
k −1
qY
 ′  Y 1
P DO =ν =
1
2b − i
k∈{0,1}κ i=0
Y 1
⩾
2bqk
k∈{0,1}κ
1
= ,
2bq

36
where qk is the total number of queries made with key k.

A.5.2 Ideal World In the ideal world the randomness is generated by both
the simulator and the random oracle. Any query in Lfwd,known has a probability
of 1/2b−n of getting a specific value, as the first n bits are determined from
Mi−1 . Correspondingly, any query in Mrandom has a probability of 1/2n , while
queries in M \ Mrandom have a probability of 1 as they are correctly determined
from νi−1 by Lemma 3. As |Mrandom | = |Lfwd,known | we can alternatively count
over queries in Lfwd,known with a probability of 1/2b .
Furthermore, any other query has a probability of 1/2b of getting a specific
value, as all bits are randomly generated. This means that we get a final upper
bound of
 ′  1
P DO = ν ⩽ bq .
2
2

A.5.3 Ratio This gives us the following ratio:

 ′ 
P DO 1
=ν 2bq
 ′  ⩾ bq = 1.
P DO2 = ν 2

A.6 Removing Subtree-Freenees

If we drop the subtree-freeness requirement, we have to change the definition of
Lrel to also include Lcomplete in order for Lemma 3 to still hold. This influences
the analysis of bad events (i), (ii), (iv) and (v), but only when the last query is
in Lfwd,known , as only those are not completely randomly generated. This means
that we get the original bound, but with extra terms for the following bad events:
(i’) There exist (ki , xi , yi ) ∈ Lrel and (kj , xj , yj ) ∈ Lfwd,known with i < j such
that ⌊yi ⌋c = ⌊yj ⌋c .
(ii’) There exist (ki , xi , yi ) ∈ Lrad and (kj , xj , yj ) ∈ Lfwd,known with i < j such
that ⌊yj ⌋c = radicalValue[Lrel i−1 ](ki , xi ).
(iv’) There exist (ki , xi , yi ) ∈ Linv and (kj , xj , yj ) ∈ Lfwd,known with i < j such
that ⌊xi ⌋c = ⌊yj ⌋c .
(v’) There exist (ki , xi , yi ) ∈ Lfwd,known such that ⌊yi ⌋m = IV1 .
We get the following upper bounds:
(i’) Let (ki , xi , yi ) ∈ Lrel and (kj , xj , yj ) ∈ Lfwd,known with i < j and ⌊yi ⌋n =
⌊yj ⌋n . As ⌈yj ⌉n is randomly generated, we get a probability of 1/2c−n for
a single such query. Similar to before, there are at most |Lrel | · maxh Fh
such possible pairs, where Fh denotes the number of queries (Mk , Zk , hk ) ∈
Mrandom with hk = h. This leads to an upper bound of

|Lrel | · E [maxh Fh ]
.
2c−n

37
 (ii’) This event is very similar, but now ⌊yj ⌋c has to hit a radical value, giving
an upper bound of
|Lrad | · E [maxh Fh ]
.
2c−n
(iv’) Again, by the same reasoning we get an upper bound of
|Linv | · E [maxh Fh ]
.
2c−n
(v’) In this case we actually have to split based on the values of m and n. If m ⩽
n we simply have to bound the probability of ⌊hj ⌋m = IV1 occurring for
any (Mj , Zj , hj ) ∈ Mrandom , which is r/2m . If m > n we get a probability
of 1/2m−n for any query (ki , xi , yi ) ∈ Lfwd,known with ⌊yi ⌋n = ⌊IV1 ⌋n .
This leads to the upper bound
 
E F⌊IV1 ⌋n r/2n r
m−n
⩽ m−n = m ,
2 2 2
which is the same as the previous case.
All in all, using Lemma 2 these values combined give an extra term of
r E [maxh Fh ]
m
+ (|Lrel | + |Lrad | + |Linv |) ·
2  2c−n

r q 2r
⩽ m + c−n · + ln(r) + n + 1
2 2 2n
r 2qr (ln(r) + n + 1)q
= m+ c + .
2 2 2c−n
As these are extra terms, we get a total bound of
 ′  q + r q 2 + 2qr q 2 + 2qr  q q 
P DO ∈ Vbad ⩽ m + c
+ b
+ (ln(r) + n + 1) c−n + b−n .
2
2 2 2 2 2

A.7 Chopping
Similar to Section A.6 we only have to modify the analysis of the bad views. We
split the analysis based on the values of b − n and c.

b − n ⩾ c. In this case all relevant bits in the bad events (i)–(v) are generated
randomly, which gives the same upper bound as in Section A.4 of
q q2
+ .
2m 2c
Furthermore, for bad events (vi) and (vii) we can always consider the first b − n
bits to be considered random, giving the upper bound of
q2
.
2b−n
Combining these, we get the upper bound
q q2 q2
P [D′ O2 ∈ Vbad ] ⩽ + + .
2m 2c 2b−n

38
b − n < c. The analysis for bad events (i)–(v) is very similar to the one in
Section A.6, but the number of fixed and randomly generated bits changes.
In this case the first b − n bits are randomly generated, while the bits from
b − n to c are fixed. This essentially means that we do not look for the number
of queries (Mk , Zk , hk ) ∈ Mrandom with hk = h for a specific h (previously
denoted by Fh ), but at the number of queries (Mk , Zk , hk ) ∈ Mrandom with just
c−(b−n)
⌊hk ⌋c−(b−n) = ⌊h⌋c−(b−n) for a specific h, denoted by Fh . This leads to
the extra term
|Lrel | + |Lrad | + |Linv |
 
r c−(b−n)
+ · E max Fh
2m 2b−n h
 
r q 2r
⩽ m + b−n · + ln(r) + c − (b − n) + 1
2 2 2c−(b−n)
r 2qr (ln(r) + n + 1)q
⩽ m+ c + .
2 2 2b−n
Although we use chopping instead of truncation, we can reuse the analysis for
bad events (vi) and (vii) in Section A.6, as those analysis are symmetrical. This
gives a total bound of

 ′  q + r q 2 + 2qr q 2 + 2qr (2 ln(r) + 2n + 2)q

P DO ∈ Vbad ⩽ m + + + .
2
2 2c 2b 2b−n

B Security of Enveloped (Theorem 4)

First of all we may assume that q ⩽ 2c−2 as the bound holds trivially otherwise.

B.1 Simulator

The simulator is defined in Algorithm 9 and is based on the previous one given
in Algorithm 8. In particular, the forward direction has remained unchanged.
However, the inverse direction has been modified significantly. It mostly just
gives a random result, but the mode has to satisfy one additional property in
that it is difficult to invert the final compression call. This is prevented by having
the IV2 as the data path in this call, which is unlikely to be hit by chance.
However, a distinguisher is able to fool a naive simulator by modifying its queries
slightly. Instead of verifying the hash of a message M by building the complete
tree in the forward direction, a distinguisher might do its final query in the
backward direction. To perform this query the distinguisher has to get the hash
of the message by querying the construction oracle beforehand. In this case the
simulator cannot give a random result, but has to output IV2 . To circumvent
this problem, the simulator assumes that any inverse query can be of this form
and calls the construction oracle to check.
In the enveloped mode we define ζx (y) = y and getX[L] = {IV2 }. These are
changed for the feed-forward in Section C.

39
Algorithm 9
Interface: S : {0, 1}κ × {0, 1}b → {0, 1}b , (k, x) 7→ y
if x ∈/ domLk then
S ← radicalExtend[Lrel ](k, x) ▷ radical-extend tree from single node
if S ∈ ST then ▷ query completes tree
(M, Z) ← extract(S) ▷ extract message and tree template
h ← RO(M, Z)
y ← ζx−1 (h)
else ▷ query does not complete tree
$
y←− {0, 1}b
end if
Lk (x) ← y
end if
return Lk (x)

Interface: S −1 : {0, 1}κ × {0, 1}b → {0, 1}b , (k, y) 7→ x

if y ∈
/ rngLk then
for x ∈ getX[Lrel ] do ▷ loop over all potential x
S ← radicalExtend[Lrel ](k, x)
if S ∈ ST then
(M, Z) ← extract(S)
h ← RO(M, Z)
if ζx−1 (h) = y then
L−1
k (y) ← x
return x
end if
end if
end for
$
x← − {0, 1}b \ getX[Lrel ]
−1
Lk (y) ← x
end if
return L−1 k (y)

B.2 Views
The definition of the views is very similar to the one in Section A.3, but the
queries Linv are split similarly to Lcomplete into
−1
Linv,known = { (ki , xi , yi ) ∈ Linv | ∃x ∈ getX[Lrel rel
i−1 ] : ζx (Mi−1 (extractFrom[Li−1 ](x∥ki ))) = yi } ,

Linv,random = Linv \ Linv,known ,

where Linv,known are queries whose result is, mostly, as we will see later, al-
ready known to the distinguisher, whereas the result of queries in Linv,random
are completely unknown to the distinguisher.
Furthermore, the different simulator has an influence on the values of the
construction oracle: they are not necessarily fully random anymore, as some
values can be discarded by the use of the inverse simulator. As there can be at

40
most q values discarded, the set of values from which the construction oracle
chooses randomly, is at least 2b − q ⩾ 2b /2.
This has influence on the distribution of some queries.
– Lcomplete \ Lfwd,known : as the result from the construction oracle is randomly
chosen from at least 2b /2 values, every value has a probability of at most
2/2b of occurring. We can use the same bound for queries in Lfwd,random .
– Linv,random : there is a possibility that an x from getX[Lrel i−1 ] succeeds, but
every such x has a probability of at most 2/2b . Other values, which are
distinct, are randomly chosen from at least 2b − |getX[Lrel ]| ⩾ 2b /2 values.
– Linv,known : it is known that a specific x ∈ getX[Lrel i−1 ] succeeds, but there
is a possibility that an earlier one also succeeds. However, as in our case
|getX[Lrel
i−1 ]| = 1 this cannot happen.

The bad events (i)–(vii) remain mostly the same, but we have to modify bad
events (iii) and (v) to also include ⌊IV2 ⌋c to compensate for the minor violation
of leaf-anchoring. Furthermore, we define the following extra bad events to make
the analysis of bad event (vi) more structured.
(a) There exist (ki , xi , yi ) ∈ Lfwd,random and (kj , xj , yj ) ∈ Lfwd,known with i < j
and ki = kj such that yi = yj .
(b) There exist (ki , xi , yi ) ∈ Lfwd,known ∪ Linv,known and (kj , xj , yj ) ∈ Lfwd,known
with i < j and ki = kj such that yi = yj .
(c) There exist (ki , xi , yi ) ∈ Linv,random and (kj , xj , yj ) ∈ Lfwd,known with i < j
and ki = kj such that yi = yj .
We also update Lemma 3 and Corollary 1 to include inverse queries, as they can
complete a tree as well.
Lemma 4. Let ν be a good view. Then for every query (M, Z, h) ∈ M we have
that (ki , xi , yi ) ∈ Lcomplete ∪ Linv and ζxi (yi ) = h, where i = ιfinal (M, Z).
Proof. This is similar to the proof of Lemma 3, but we have to change the
analysis of the inverse queries. In this case the inverse queries for which the
simulator finds a suitable digest can be a verification query. By subtree-freeness
this can only happen for final verification queries and by design the simulator
only gives consistent results for such queries. The analysis for the other inverse
queries still holds and they cannot be verification queries. ⊔
⊓
Corollary 2. For any good view we have |Mrandom | = |Lfwd,known ∪ Linv,known |.
Proof. As before, this is similar to the proof of Corollary 1, but we have to
include the queries Linv,known as they can be final verification queries. ⊔
⊓

B.3 Analysis of Bad Views

The analysis of the original bad events (i)–(v) is the same as in Section A.4,
giving an upper bound of
q q2
+ .
2m 2c

41
The modifications of (iii) and (v) lead to an extra term |Linv |/2c + |Lrel |/2c ⩽
q/2c .
(a) In order to make the analysis easier, we define the following helper event:
1. There exist (ki , xi , yi ) ∈ Lfwd,random and (Mj , Zj , hj ) ∈ Mrandom with
i ̸= j such that yi = hj .
For this helper event we know that yi and hj are both randomly generated
from at least 2b /2 values, hence we get an upper bound of

2 · |Lfwd,random | · |Mrandom | 2r · |Lfwd,random |

⩽ .
2b 2b
Now we derive the real bad event under the assumption that the helper event
does not occur. Let (ki , xi , yi ) ∈ Lfwd,random and (kj , xj , yj ) ∈ Lfwd,known
with i < j. There has to be a corresponding (Mk , Zk , hk ) ∈ Mrandom for
query j and hk = yj = yi . As i ̸= k this contradicts the helper event.
(b) Again, in order to make the analysis easier, we define a helper event:
1. There exist (Mi , Zi , hi ) ∈ Mrandom and (Mj , Zj , hj ) ∈ Mrandom with
i < j such that hi = hj .
For this helper event we know that hj is randomly generated from at least
2b /2 values, hence we get an upper bound of

2 · |Mrandom |2 2r · |Mrandom |
⩽ .
2b 2b
Now we derive the real bad event under the assumption that the helper event
does not occur. Let (ki , xi , yi ) ∈ Lfwd,known ∪ Linv,known and (kj , xj , yj ) ∈
Lfwd,known with i < j. There has to be a corresponding (Mk , Zk , hk ) ∈
Mrandom for query j and hk = yj . Similarly there has to be a correspond-
ing (Mℓ , Zℓ , hℓ ) ∈ Mrandom for query i and hℓ = yi = hk . As k ̸= ℓ this
contradicts the helper event.
(c) We define the following helper events:
1. There exist (ki , xi , yi ) ∈ Linv,random and (Mj , Zj , hj ) ∈ Mrandom with
i < j such that yi = hj .
2. There exist (ki , xi , yi ) ∈ Linv,random and (kj , xj , yj ) ∈ Lrel with i < j such
that ⌊yj ⌋c = radicalValue[Lrel i−1 ](ki , IV2 ).
For helper event (1) we know that hj is uniformly randomly generated from
at least 2b /2 values, leading to the following upper bound

2 · |Linv,random | · |Mrandom | 2r · |Linv,random |

⩽ .
2b 2b
For helper event (2) we know that ⌊yj ⌋c is uniformly randomly generated
from at least 2c /2 values, giving an upper bound of

2 · |Linv,random | · |Lrel | 2q 2
c
⩽ c .
2 2
Now we derive the real bad event under the assumption that the helper
events do not occur. Let (ki , xi , yi ) ∈ Linv,random and (kj , xj , yj ) ∈ Lfwd,known

42
 with i < j. There has to be a corresponding (Mk , Zk , hk ) ∈ Mrandom with
k < j and hk = yj = yi . Furthermore, by final leaf-anchoring we know that
xj = IV2 .
If i < k this contradicts helper event (1) and i = k cannot happen, hence
we can assume that k < i. We separate different cases:
– radicalValue[Lrel rel
i−1 ](ki , IV2 ) = ⊥. This means that radicalExtend[Lj−1 ](kj , xj ) =
rel rel
radicalExtend[Li−1 ](ki , IV2 ), therefore RO(extractFrom[Li−1 ](ki , IV2 )) =
yj = yi , hence query i would have been in Linv,known .
– radicalValue[Lreli−1 ](ki , IV2 ) ̸= ⊥. As we know that (Mk , Zk ) is con-
structed in query j, this radical has to be filled after query i. However,
that contradicts helper event (2).
(vi) Let (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈ Lfwd with i < j and ki = kj .
If (kj , xj , yj ) ∈ Lfwd,random then yj is random from at least 2b /2 values,
hence we get an upper bound of
2 · |Lfwd ∪ Linv | · |Lfwd,random | 2q · |Lfwd,random |
⩽ .
2b 2b
Otherwise (kj , xj , yj ) ∈ Lfwd,known , which means that we contradict bad
event (a), (b) or (c) based on the specifics of query i.
(vii) Let (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈ Linv with i < j and ki = kj .
If (kj , xj , yj ) ∈ Linv,random then xj is randomly chosen from at least 2b /2
values, hence we get an upper bound of
2 · |Lfwd ∪ Linv | · |Linv,random | 2q · |Linv,random |
⩽
2b 2b
for this case. Otherwise, we can assume that (kj , xj , yj ) ∈ Linv,known .
Let Si = radicalExtend[Lrel rel
i−1 ](ki ∥xi ) and Sj = radicalExtend[Lj−1 ](kj ∥xj ).
As (kj , xj , yj ) ∈ Linv,known , we know that Sj ∈ ST . This means that
Si ∈ ST ∪ STfinal ⊆ ST ∪ STrad . If Si ∈ STrad the radical had to be ex-
tended before query j, contradicting bad event (ii). Therefore Si ∈ ST and
we know that Si = Sj .
If (ki , xi , yi ) ∈ Lfwd we get that (ki , xi , yi ) ∈ Lcomplete hence yi = yj , which
cannot happen. If (ki , xi , yi ) ∈ Linv we know that xi = xj ∈ getX[Lrel j−1 ],
which can only happen when query i returned a value derived from the
random oracle. However, as Si = Sj this also means that yi = yj , which
cannot happen.
By combining all upper bounds and using that |Lfwd,random | + |Mrandom | +
|Linv,random | ⩽ q and |Lfwd,random | + |Linv,random | ⩽ q we get an upper bound of
 ′  q 3q 2 + q 2q 2 + 2qr
P DO ∈ Vbad ⩽ m + + .
2
2 2c 2b

B.4 Analysis of Good Views

B.4.1 Real World The analysis of the real world is identical to the one in
Section A.5.1, but with Lemma 4.

43
B.4.2 Ideal World In the ideal world the randomness is generated by both
the simulator and the random oracle. For any query in Lfwd,known ∪Linv,known we
trivially get an upper bound of 1 for hitting a specific value. Correspondingly,
any query in Mrandom has a probability of at most 1/(2b − q), while queries in
M \ Mrandom have a probability of 1 as they are correctly determined from νi−1
by Lemma 4. As |Mrandom | = |Lfwd,known ∪ Linv,known | by Corollary 2 we can
alternatively count over queries in Lfwd,known ∪ Linv,known with a probability of
at most 1/(2b − q). Similarly, queries in Lcomplete \ Lfwd,known have a probability
of at most 1/(2b − q) as well.
Any query in Lfwd \ Lcomplete has a probability of 1/2b of getting a specific
value. For a query i in Linv,random we separate based on whether it hits a value
in getX[Lrel rel
i−1 ] or not. Every value in getX[Li−1 ] is hit with a probability of at
most 1/(2 − q), while any value outside getX[Lrel
b
i−1 ] is hit with a probability of
at most 1/(2b − |getX[Lrel b
i−1 ]|) = 1/(2 − 1).
As all possibilities are upper bounded by 1/(2b − q), we can use that bound
for all queries, simplifying the final bound to
 q
 ′  1
P DO2 = ν ⩽ .
2b − q

B.4.3 Ratio This gives us the following ratio:

 ′   q
P DO 1
=ν 2b − q
 ′ ⩾
P DO 2
=ν 2b
 q q
= 1− b
2
2
q
⩾ 1− b.
2

C Security of Feed-Forward (Theorem 5)

First of all we may assume that q ⩽ 2c−2 as the bound holds trivially otherwise.
Furthermore, the simulator is the same as in Algorithm 9, but we have to update
the finalization function to ζx (y) = x ⊕ y and the set of possible inputs to
getX[L] = {IV′1 } ∪ { ⌊y⌋c ∥IV2 : (k, x, y) ∈ L, IV2 ∈ IV 2 } accordingly.

C.1 Views

The views are similar to the ones in Section B.2, but we have to modify the
extra events. Before we can do that we define some extra procedures in order to
define them.
Definition 13. Given a message (M, Z) and a list L we define buildForward[L](M, Z)
as the procedure that builds a partial tree corresponding to (M, Z) up to the data
input x of the final node and as far as possible from the bottom up by using

44
queries from L. This is similar to computing the hash result of (M, Z), but ig-
nores the key input and it might not finish. We define buildX[L](M, Z) as the
data input x of the final node, or ⊥ if it does not finish.
When additionally given an x ∈ getX[L] we define buildBackward[L](M, Z, ⌊x⌋c )
as the procedure that builds the tree corresponding to (M, Z) as far as possible by
starting with ⌊x⌋c as the first c bits in the final node and filling in all chaining
values. Note that ⌊x⌋c is either ⌊IV′1 ⌋c or a chaining value. This is similar to
the procedure radicalExtend[L](k, x), but it does not need the key k as it already
knows the template from the message (M, Z) and it tries to fill in all chaining
values, not just one.
We will now define the additional bad events.

(a) There exists a (ki , xi , yi ) ∈ Linv,known such that xi ̸= x, where x is the

predicted value.
(b) Let (Mi , Zi , hi ) ∈ Mrandom , (kj , xj , yj ) ∈ Lrel and x ∈ {0, 1}b with i < j.
This bad event occurs when:
– buildX[Lrel rel
j−1 ](Mi , Zi ) = ⊥, but buildX[Lj ](Mi , Zi ) ̸= ⊥.
– buildForward[Lj−1 ](Mi , Zi ) and buildBackward[Lrel
rel
j−1 ](Mi , Zi , x) do not
contradict each other.
– buildBackward[Lrel j−1 ](Mi , Zi , x) is not trivial.
(c) There exist (ki , xi , yi ) ∈ Lfwd,random and (kj , xj , yj ) ∈ Lfwd,known with i < j
and ki = kj such that yi = yj .
(d) There exist (ki , xi , yi ) ∈ Lfwd,known ∪ Linv,known and (kj , xj , yj ) ∈ Lfwd,known
with i < j and ki = kj such that yi = yj .
(e) There exist (ki , xi , yi ) ∈ Linv,random and (kj , xj , yj ) ∈ Lfwd,known with i < j
and ki = kj such that yi = yj .

Bad event (a) ensures that the predicted value for queries in Linv,known will be
hit, bad event (b) will make sure that there will be a unique query that defines the
⌊x⌋c in the feed-forward, which will make reasoning over ⌊y⌋c = ⌊x ⊕ h⌋c easier.
The bad events (c), (d) and (e) will make the analysis of (i) more structured.
We note that Corollary 2 still holds as bad event (a) ensures that the queries
in Linv,known behave as expected and verify the correct messages.

C.2 Analysis of Bad Views

The analysis of bad events (i)–(v) are the same as in Section A.4, giving an
upper bound of
q q2
+ .
2m 2c
The main goal of the analysis is to make sure that there is no permutation
inconsistency in the simulator. Most outputs are randomly generated, making
such analysis straightforward. However, the simulator also has to be consistent
with the construction oracle, which forces some outputs. In particular, the queries
in Lfwd,known are difficult to analyze. As the mode uses a feed-forward in the

45
finalization, we know that h = x ⊕ y, where h is the hash digest, x is the input
to the final query and y is the output of the final query. This means that the
final output y = h ⊕ x is determined when both the hash digest h and the input
x are known. As both h and ⌊x⌋c are randomly generated, the same holds for
⌊y⌋c when the last one of h and ⌊x⌋c is. However, there are a few caveats:
– If the message consists of a single message block, x equals the fixed value
IV′1 . This does not impose any problems, as this means that h, which is
random, will always be generated last.
– The distinguisher might make clever queries which make ⌊x⌋c not uniformly
random. For example, take a simple Merkle-Damgård construction. The dis-
tinguisher can query almost all blocks, except the first and last, where it
guesses the first chaining value. When constructing the start of the message
it might hit the first chaining value and if it misses it might hit the sec-
ond, etc. All in all, this means that some chosen values of ⌊x⌋c might be
more probable than others, although not significantly so. This would make
the analysis very complicated, so we introduce bad event (b) to make sure
that there is only a specific query that determines ⌊x⌋c , making sure that
it is randomly generated. The problematic cases could also be prevented by
making the procedure radicalExtend[L](k, x) not depend on the unknown k.
However, this modification is not possible without compromising the gener-
ality.

Definition 14. Let (Mi , Zi , hi ) ∈ Mrandom . Query j ⩾ i completes (Mi , Zi ) if:

– j = i and buildX[Lrel i−1 ](Mi , Zi ) ̸= ⊥.
– j > i, (kj , xj , yj ) ∈ Lrel and j is the final node in buildForward[Lrel
j−1 ](Mi , Zi )
(so ⌊buildX[Lrel j ](M i , Z )⌋
i c = ⌊y ⌋
j c ).
Note that a query can complete multiple messages. As the distinguisher verifies
all the queries in Mrandom at the end, we know that for every (Mi , Zi , hi ) ∈
Mrandom there is always exactly one query y index (Mi , Zi ) ⩾ i that completes
(Mi , Zi ) with value y final (Mi , Zi ) = buildX[Lrel
j ](Mi , Zi )⊕hi , where j = y
index
(Mi , Zi ).

This definition does not depend on the output of query y index (Mi , Zi ) hence
⌊y final (Mi , Zi )⌋c can be considered random at query y index (Mi , Zi ). Due to the
fact that the construction oracle no longer perfectly random, the probability of
getting a specific value is at most 2b−c /(2b − q) ⩽ 2/2c . Furthermore, after this
query the output of the verification query of (Mi , Zi ) is determined.

Lemma 5. Let (Mi , Zi , hi ) ∈ Mrandom and let y be the output of the verification
query of (Mi , Zi ). If bad event (b) does not occur, we have y = y final (Mi , Zi ).

Proof. Let j ⩾ i be the query that determines y. If j = i we have that buildX[Lreli−1 ](Mi , Zi ) ̸=
⊥, hence j = y index (Mi , Zi ). If j > i we know that (kj , xj , yj ) ∈ Lrel and
that query j determines x. This means that buildX[Lrel j ](Mi , Zi ) = x ̸= ⊥
and buildX[Lrel
j−1 ](M i , Zi ) = ⊥. Furthermore, buildForward[L rel
j−1 ](Mi , Zi ) and
rel
buildBackward[Lj−1 ](Mi , Zi , x) cannot contradict each other, as query j gives as

46
output x. Finally, by bad event (b) this means that buildBackward[Lrel
j−1 ](Mi , Zi , x)
has to be trivial, which means that the final query has not happened in the first
j − 1 queries, hence it happened at query j and we get y = y final (Mi , Zi ) as
desired. ⊔
⊓

(a) For query (ki , xi , yi ) ∈ Linv,known there are at most |getX[Lrel

i−1 ]| ⩽ 1 + P (q −
1) ⩽ P q possibilities before the predicted x that can be hit. Every such
possibility has a probability of at most 2/2b to be hit, which leads to an
upper bound of

2 · |Linv,known | · |getX[Lrel ]| 2P qr
b
⩽ .
2 2b
(b) In order to upper bound this bad event, we first show that for every (Mi , Zi , hi ) ∈
Mrandom and x ∈ {0, 1}b there is at most one possible (kj , xj , yj ) ∈ Lrel that
has a possibility of satisfying bad event (b). For this, we first define precisely
what such query is.
Definition 15. Let (Mi , Zi , hi ) ∈ Mrandom , (kj , xj , yj ) ∈ Lrel and x ∈
{0, 1}b with i < j. We call query j a candidate when there is a y ∈
{0, 1}b such that bad event (a) is satisfied, but where in the final condition
buildForward[Lrel rel
j ](Mi , Zi ) is replaced by buildForward[Lj−1 ∪{(kj , xj , y)}](Mi , Zi ).
Note that this definition does not depend on the output yj .
Now we show that there is at most one such candidate for every (Mi , Zi , hi ) ∈
Mrandom and x ∈ {0, 1}b .
Lemma 6. For every (Mi , Zi , hi ) ∈ Mrandom and x ∈ {0, 1}b there is at
most one candidate.

Proof. Let j be the first candidate, if one exists. If j is successful, we have

buildX[Lrel
k−1 ](Mi , Zi ) ̸= ⊥ for any k > j, hence there can be no later can-
didate. If j is not successful it means that buildForward[Lrel j ](Mi , Zi ) and
rel
buildBackward[Lj ](Mi , Zi , x) contradict each other, as j was the final part
missing. As these keep contradicting each other in further queries, no later
candidate is possible. ⊔
⊓

First of all, as buildBackward[Lrelj−1 ](Mi , Zi , x) is not trivial, we need to have

that x ∈ getX[Lrelj−1 ]. As the definition only depends on ⌊x⌋c this leads to at
most q possible values for x. Furthermore, by Lemma 6 there is at most one
candidate, hence we can upper bound the bad event by

2 · |Mrandom | · q 2qr
c
⩽ c .
2 2
(c) In order to make the analysis easier, we define the following helper events:
1. There exist (ki , xi , yi ) ∈ Lfwd,random and (Mj , Zj , hj ) ∈ Mrandom with
i ̸= y index (Mj , Zj ) such that ⌊yi ⌋c = ⌊y final (Mj , Zj )⌋c .
2. There exists (Mi , Zi , hi ) ∈ Mrandom such that ⌊hi ⌋c = 0c .

47
 For these helper events we know that ⌊yi ⌋c , ⌊y final (Mj , Zj )⌋c (helper event
(1)) and ⌊hi ⌋c (helper event (2)) are all randomly generated from at least
2c /2 values. This leads to the following upper bound
2 · |Lfwd,random | · |Mrandom | 2 · |Mrandom | 2 · |Lfwd,random | · r 2r
+ ⩽ + c.
2c 2c 2c 2
Now we derive the real bad event under the assumption that the helper
events do not occur. Let (ki , xi , yi ) ∈ Lfwd,random and (kj , xj , yj ) ∈ Lfwd,known
with i < j. There has to be a corresponding (Mk , Zk , hk ) ∈ Mrandom for
query j with k ′ = y index (Mk , Zk ) < j, hence y final (Mk , Zk ) = yj = yi .
If i ̸= k ′ this contradicts helper event (1) and if i = k ′ then ⌊hk ⌋c =
⌊yj ⊕ buildX[Lrel c
k′ ](Mk , Zk )⌋c = ⌊yj ⊕ yi ⌋c = 0 , contradicting helper event
(2).
(d) Again, in order to make the analysis easier, we define some helper events:
1. There exist (Mi , Zi , hi ) ∈ Mrandom and (Mj , Zj , hj ) ∈ Mrandom with
y index (Mi , Zi ) < y index (Mj , Zj ) such that ⌊y final (Mi , Zi )⌋c = ⌊y final (Mj , Zj )⌋c .
2. There exist (Mi , Zi , hi ) ∈ Mrandom and (Mj , Zj , hj ) ∈ Mrandom with
i < j such that ⌊hi ⌋c = ⌊hj ⌋c .
As ⌊y final (M ′ , Z ′ )⌋c (helper event (1)) and ⌊hj ⌋c (helper event (2)) are ran-
domly generated from at least 2c /2 values, we get the following upper bound
for these helper events:
2 · |Mrandom |2 2 · |Mrandom |2 4r2
+ ⩽ .
2c 2c 2c
Now we derive the real bad event under the assumption that the helper
events do not occur. Let (ki , xi , yi ) ∈ Lfwd,known ∪Linv,known and (kj , xj , yj ) ∈
Lfwd,known with i < j. There has to be a corresponding (Mk , Zk , hk ) ∈
Mrandom for query j with k ′ = y index (Mk , Zk ) < j, hence y final (Mk , Zk ) =
yj = yi . Similarly there has to be such corresponding (Mℓ , Zℓ , hℓ ) ∈ Mrandom
for query i with ℓ′ = y index (Mℓ , Zℓ ) < i.
If k ′ ̸= ℓ′ this contradicts helper event (1) and k ′ = ℓ′ can only happen when
x = buildX[Lrel rel
k′ ](Mk , Zk ) = buildX[Lℓ′ ](Mℓ , Zℓ ), hence ⌊hk ⌋c = ⌊yi ⊕ x⌋c =
⌊yj ⊕ x⌋c = ⌊hℓ ⌋c , which contradicts helper event (2).
(e) We define the following helper events:
1. There exist (ki , xi , yi ) ∈ Linv,random and (Mj , Zj , hj ) ∈ Mrandom with
i < y index (Mj , Zj ) such that ⌊yi ⌋c = ⌊y final (Mj , Zj )⌋c .
2. There exist (Mi , Zi , hi ) ∈ Mrandom , (kj , xj , yj ) ∈ Linv,random and (kk , xk , yk ) ∈
Lrel with i ⩽ y index (Mi , Zi ) < j < k and y final (Mi , Zi ) = yj such that
⌊yk ⌋c = radicalValue[Lrel j−1 ](kj , x), where x = hi ⊕ yj .
For helper event (1) we know that ⌊yjfinal (M, Z)⌋c is randomly generated
from at least 2c /2 values, leading to the following upper bound
2 · |Linv,random | · |Mrandom | 2 · |Linv,random | · r
c
⩽ .
2 2c
For helper event (2) we know that ⌊yk ⌋c is randomly generated from at least
2c /2 values and in the previous bad event we saw that for every ⌊yj ⌋c there

48
 is at most one (Mi , Zi , hi ) ∈ Mrandom with ⌊y final (Mi , Zi )⌋c = ⌊yj ⌋c , hence
we get the upper bound of

2 · |Linv,random | · |Lrel | 2q 2
⩽ .
2c 2c
Now we derive the real bad event under the assumption that the helper
events do not occur. Let (ki , xi , yi ) ∈ Linv,random and (kj , xj , yj ) ∈ Lfwd,known
with i < j. There has to be a corresponding (Mk , Zk , hk ) ∈ Mrandom with
k ′ = y index (Mk , Zk ) < j, hence y final (Mk , Zk ) = yj = yi .
If i < k ′ this contradicts helper event (1) and i = k ′ cannot happen as k ′
cannot be an inverse query, hence we can assume that k ′ < i. This also means
that x = hk ⊕ y final (Mk , Zk ) is known at query i and that x ∈ getX[Lrel i−1 ].
We separate different cases:
– radicalValue[Lrel rel rel
i−1 ](ki , x) = ⊥. As radicalExtend[Li−1 ](ki , x) = radicalExtend[Lj−1 ](kj , x)
we know that ζx−1 (RO(extractFrom[Lrel i−1 ](ki , x))) = yj = yi , hence
query i would have been in Linv,known .
– radicalValue[Lrel i−1 ](ki , x) ̸= ⊥. As we know that (Mk , Zk ) is constructed
in query j, this radical has to be filled after query i. However, that
contradicts helper event (2).

Now we look at the ‘real’ bad events (vi) and (vii).

(vi) Let (ki , xi , yi ) ∈ Lfwd ∪ Linv and (kj , xj , yj ) ∈ Lfwd with i < j and ki = kj .
If (kj , xj , yj ) ∈ Lfwd,random then yj is randomly chosen from at least 2b /2
values, hence we get an upper bound of

2 · |Lfwd ∪ Linv | · |Lfwd,random | 2q · |Lfwd,random |

⩽ .
2b 2b
Otherwise (kj , xj , yj ) ∈ Lfwd,known , which means that we contradict bad
event (c), (d) or (e) based on the specifics of query i.
(vii) The analysis is the same as in Section B, giving an upper bound of

2q · |Linv,random |
.
2b
By combining all upper bounds and using that |Lfwd,random | + |Linv,random | ⩽ q
we get an upper bound of
 ′  2q 2 + 4qr + 4r2 + 2r 2q 2 + 2P qr
P DO ∈ Vbad ⩽ + .
2
2c 2b

C.3 Analysis of Good Views

The analysis of the good views is identical to the one in Section B, giving a ratio
of  ′ 
P DO =ν q2
 ′ 1
 ⩾ 1− b.
P DO2 = ν 2

49