List of changes in the specification document:
1. Abstract:
Original submission (31st October):
such a Feistel block cipher
Updated submission (15th January):
such as a Feistel block cipher
2. Introduction:
Page 1, second paragraph:
Original submission (31st October):
In this paper,
Updated submission (15th January):
In this document,
Page 2, second paragraph:
Original submission (31st October):
efficient, and suitable to many platforms (both modern CPUs, as well as
smart card and 8-bit machines). Our current implementation of SHAvite-3
Updated submission (15th January):
efficient, and suitable for many platforms (both modern CPUs, as well as
smart cards and 8-bit machines). Our current implementation of SHAvite-3
Page 2, fourth paragraph:
Original submission (31st October):
The design criteria and motivation is outlined in Section 5.
Updated submission (15th January):
The design criteria and motivation are outlined in Section 5.
Original submission (31st October):
Several test vectors are given in Appendix A, and detailed internal values
during the execution of SHAvite-3 for several messages is given in Appendix B.
Updated submission (15th January):
Several test vectors are given in Appendix A.
3. Section 2: AES and Some Mathemtical Background
Page 2, second paragraph:
Original submission (31st October):
Throughout this paper we denote by $AESRound_{subkey}(x)$ one round of AES
as defined in the FIPS [51], using
Updated submission (15th January):
Throughout this document we denote by $AESRound_{subkey}(x)$ one round of
AES as defined in Federal Information Processing Standard 197 [51], using
4. Section 3: HAsh Iterative FrAmework
Page 4, second paragraph:
Original submission (31st October):
In particular, we show that the HAIFA mode of iteration is protected
against the second preimage attacks of [1,25,36,37].
Updated submission (15th January):
In particular, we show that the HAIFA mode of iteration is protected
against the second preimage attacks and the chosen-target preimage
attacks of [1,25,36,37].
Page 4, third paragraph:
Original submission (31st October):
we define in Section 7.
Updated submission (15th January):
we suggest in Section 7).
Page 4, Section 3.1, item 2:
Original submission (31st October):
Compressing the message using HAIFA-compatible compression function.
Updated submission (15th January):
Compressing the message using a HAIFA-compatible compression function.
Page 4, second list, second item:
Original submission (31st October):
A Message block (of length $n$),
Updated submission (15th January):
A message block (of length $n$),
Page 5, first paragraph:
Original submission (31st October):
Hence, to compress a message $M$, the user first chooses a $salt$ at random.
The salt can be application specific (e.g., a string identifying the
application), a serial number within the application (e.g., the serial
number of the message signed), or even a counter.
Updated submission (15th January):
Hence, to compress a message $M$, the user first chooses a salt $salt$
at random. The salt can be application specific (e.g., a string identifying
the application), a serial number within the application (e.g., the serial
number of the message being signed), or even a counter.
Page 5, Section 3.2, last paragraph:
Original submission (31st October):
processed with a different $\# bits$ parameter than in prior invocations.
Updated submission (15th January):
processed with a different $\# bits$ parameter than for prior invocations of
the compression function.
Page 6, Section 3.4.1, second paragraph:
Original submission (31st October):
As HAIFA uses salts, we shall consider the strongest definition of
a collision in the compression function where the adversary may
control all input parameters to the compression function and tries
to generate the same output. We assume under this strong assumption that the
adversary can even manipulate the $\# bits$ parameter.
Updated submission (15th January):
As HAIFA uses salts, we shall consider the strongest definition of
a collision in the compression function where the adversary may
control all the input parameters to the compression function including the
salt, and tries to generate the same output. Under this strong assumption
we assume that the adversary can even manipulate the $\# bits$ parameter.
Page 6, Section 3.4.2, third paragraph:
Original submission (31st October):
$HAIFA_{salt}(m)$ and $x$ (even if $salt$ is given).
Updated submission (15th January):
$HAIFA_{salt}(m)$ for any $x$ (even if the salt $salt$ is known).
Page 7, Section 3.4.3, first paragraph:
Original submission (31st October):
to distinguish SHAvite-3 is to use internal collisions, providing
security of $\min\{2^m,2^{m_c/2}\}$ against attacks which try to
distinguish an HAIFA hash function from a random string/random oracle.
Updated submission (15th January):
to distinguish a HAIFA hash function effectively
from a random string/random oracle
is to use internal collisions, providing
security of $\min\{2^s,2^m,2^{m_c/2}\}$ against these attacks.
Page 7, Section 3.4.4, bullet Dean's expandable message technique:
Original submission (31st October):
While it maybe easy to find a fix-point for an instance of the compression
function, the use of the $\# bits$ counter prevents
Updated submission (15th January):
While it may be easy to find a fix-point for an instance of the compression
function, the use of the $\# bits$ counter prevents
Page 7, Section 3.4.4, bullet Kelsey and Schneier's expandable message
Original submission (31st October):
with three blocks. The result is a limited "expandable message"
of between two and five
Updated submission (15th January):
with three blocks. The result is a very limited "expandable message"
of between two and five
Added at the end of this bullet:
We recall that despite the "expandable message", the connection phase
still requires the adversary to commit to a specific location, i.e., the
time complexity of the online phase of the attack is not reduced at all
(and is $2^{m}$).
Page 7, Section 3.4.4, bullet The Herding Attack:
Original submission (31st October):
As the salt length is equal to the digest size (or even longer),
Updated submission (15th January):
If the salt length is equal to half the chaining value size (or even longer),
Page 8, Section 3.4.5, first paragraph:
Original submission (31st October):
an instance of the randomized hashing concept [29], thus, it also
Updated submission (15th January):
an instance of the randomized hashing concept [29]. Thus, it
Page 8, Section 3.4.5, second bullet:
Original submission (31st October):
Transformation of all attacks on the hash function that can use
precomputation from an off-line part and an on-line part to only on-line
part (as the exact $salt$ is not known in advance).
Updated submission (15th January):
Transformation of all attacks on the hash function that can use
precomputation from an off-line part and an on-line part to only an on-line
part (as the exact $salt$ is not known in advance).
Page 10, bullet 1(a):
Original submission (31st October):
Let
\[
t[0..3]=AESRound_{0}((rk[i-15]||rk[i-14]||rk[i-13]||rk[i-16]) \xor
(salt[0]||salt[1]||salt[2]||salt[3])).
\]
Updated submission (15th January):
Let
\[
t[0..3]=AESRound_{0^{128}}((rk[i-15]||rk[i-14]||rk[i-13]||rk[i-16]) \xor
(salt[0]||salt[1]||salt[2]||salt[3])).
\]
Page 10, bullet 1(f):
Original submission (31st October):
Let
\[
t[0..3]=AESRound_{0}((rk[i-15]||rk[i-14]||rk[i-13]||rk[i-16])\xor
(salt[4]||salt[5]||salt[6]||salt[7])).
\]
Updated submission (15th January):
Let
\[
t[0..3]=AESRound_{0^{128}}((rk[i-15]||rk[i-14]||rk[i-13]||rk[i-16])\xor
(salt[4]||salt[5]||salt[6]||salt[7])).
\]
Page 13, paragraph before section 4.2.1:
Original submission (31st October):
The nonlinear function is composed of four full rounds of AES.
Updated submission (15th January):
The nonlinear function $F^4(\cdot)$ is composed of four full rounds of AES.
Page 13, Section 4.2.1, second paragraph:
Original submission (31st October):
$F^4(\cdot)$ accepts an input of 128 bits $R_i$ as well as 512-bit subkey
Updated submission (15th January):
$F^4(\cdot)$ accepts an input of 128 bits (either $R_i$ or $A_i$)
as well as 512-bit subkey
Page 13, Section 4.2.2, first paragraph:
Original submission (31st October):
accepts a 1024-bit message block, 128-bit counter, and 512-bit salt.
Updated submission (15th January):
accepts a 1024-bit message block, a 128-bit counter, and a 512-bit salt.
Page 14, bullet 1(a):
Original submission (31st October):
Let
\[
t[0..3]=AESRound_{0}((rk[i-31]||rk[i-30]||rk[i-29]||rk[i-32]) \xor
(salt[0]||salt[1]||salt[2]||salt[3])).
\]
Updated submission (15th January):
Let
\[
t[0..3]=AESRound_{0^{128}}((rk[i-31]||rk[i-30]||rk[i-29]||rk[i-32]) \xor
(salt[0]||salt[1]||salt[2]||salt[3])).
\]
Page 14, bullet 1(e):
Original submission (31st October):
Let
\[
t[0..3]=AESRound_{0}((rk[i-31]||rk[i-30]||rk[i-29]||rk[i-32]) \xor
(salt[4]||salt[5]||salt[6]||salt[7])).
\]
Updated submission (15th January):
Let
\[
t[0..3]=AESRound_{0^{128}}((rk[i-31]||rk[i-30]||rk[i-29]||rk[i-32]) \xor
(salt[4]||salt[5]||salt[6]||salt[7])).
\]
Page 15, bullet 1(i):
Original submission (31st October):
Let
\[
t[0..3]=AESRound_{0}((rk[i-31]||rk[i-30]||rk[i-29]||rk[i-32]) \xor
(salt[8]||salt[9]||salt[10]||salt[11])).
\]
Updated submission (15th January):
Let
\[
t[0..3]=AESRound_{0^{128}}((rk[i-31]||rk[i-30]||rk[i-29]||rk[i-32]) \xor
(salt[8]||salt[9]||salt[10]||salt[11])).
\]
6. Section 5:
Page 17, first paragraph:
Original submission (31st October):
that small nonlinearity in bit-wise operations, spread using a mixture of
XORs, modular additions,
Updated submission (15th January):
that small nonlinearity in bit-wise operations, diffused using a mixture of
XORs, modular additions,
Page 17, Section 5.1, second paragraph:
Original submission (31st October):
as the AESround implementation can be done and verified only once.
Updated submission (15th January):
as the AESround can be implemented and verified only once.
Page 18, Section 5.2, bullet Tree-hash:
Original submission (31st October):
the memory requirements for a tree hash functions
Updated submission (15th January):
the memory requirements for tree hash functions
Page 18, Section 5.2, bullet Sponge constructions:
Original submission (31st October):
Explicit constructions solve this issue by using a weak round function, a very
dangerous
Updated submission (15th January):
Explicit constructions solve this issue by using a weak round function, which
is a very dangerous
Page 18, Section 5.3, second paragraph:
Original submission (31st October):
protect against herding attacks (i.e., $s>m_c/2$).
Updated submission (15th January):
to protect against herding attacks (i.e., $s>m_c/2$) [15].
Page 19, Section 5.4, second paragraph:
Original submission (31st October):
These values can easily be computed on the
Updated submission (15th January):
These values can be easily computed on the
Page 19, Section 5.4, third paragraph:
Original submission (31st October):
allow parallel computation of all the AES rounds of nonlinear expansion step.
Updated submission (15th January):
allow parallel computation of all the AES rounds of the
nonlinear expansion step.
Page 19, Section 5.4, sixth paragraph:
Original submission (31st October):
Even if (somehow) the attack generates the same state in
Updated submission (15th January):
Even if (somehow) the attacker can generate the same state in
Page 19, Section 5.4, last paragraph:
Original submission (31st October):
(as the issue of weak inputs is solved by AES' constants and design criteria).
Updated submission (15th January):
(as the issue of possibly weak values is solved by AES' constants and its
design criteria).
Original submission (31st October):
we conclude that there is no need for additional round constants.
Updated submission (15th January):
we conclude that there is no need for any additional round constants.
Page 20, paragraph after lemma 2:
Original submission (31st October):
The upper bound given in Lemma 2 is not tight.
Updated submission (15th January):
Note that the upper bound given in Lemma 2 is not tight.
Page 20, just before lemma 3:
Original submission (31st October):
As $C_{256}$ uses 3-round AES as the round function, we conclude that:
Updated submission (15th January):
As $C_{256}$ uses 3-round AES as the round function, we use the following
lemma:
Page 20, first paragraph of the proof:
Original submission (31st October):
This is possible if, and only if, there is one active S-box in the
Updated submission (15th January):
This is possible if and only if there is one active S-box in the
Page 20, second paragraph of the proof:
Original submission (31st October):
Consider a possible output difference of this differential,
Updated submission (15th January):
Consider a possible output difference of this differential
Original submission (31st October):
then there are only 255 possible differences after the second
round, whose differences in the active bytes is linearly dependent
Updated submission (15th January):
then there are only 255 possible differences {\em after} the second
round, whose differences in the active four bytes is linearly dependent
Original submission (31st October):
127 possibilities for the first 2-round differentials which may lead
to the desired output difference.
Updated submission (15th January):
127 possibilities for the output difference of the 2-round differentials
in the first two rounds.
Original submission (31st October):
any 2-round differential has probability at most $53 \cdot 2^{-34}$, and
that in the one-round characteristics there are four active S-boxes.
Updated submission (15th January):
any 2-round differential has probability of at most $53 \cdot 2^{-34}$,
and that in the one-round characteristics there are four active S-boxes.
Original submission (31st October):
probability $2^{-6}$. Therefore, we conclude that the
Updated submission (15th January):
probability $2^{-6}$ that leads to the desired output difference.
Therefore, we conclude that the
Page 21, second bullet of the first proof:
Original submission (31st October):
difference, i.e., has probability of at most $(2^{-49})^3 = 2^{-147}$.
Updated submission (15th January):
difference, and has probability of at most $(2^{-49})^3 = 2^{-147}$.
Page 21, second bullet of the second proof:
Original submission (31st October):
Recall that $F^4(\cdot)$, is composed of 4 AES rounds.
Updated submission (15th January):
Recall that $F^4(\cdot)$ is composed of four AES rounds.
Original submission (31st October):
have two consecutive rounds with input difference zero. If there were two
such non-consecutive rounds (out of the three) with input difference zero,
then that would mean that the non-zero difference which entered the round
function produced a zero output difference, which is impossible due to the
bijectiveness
Updated submission (15th January):
have two consecutive rounds with input difference zero.
Due to the bijectiveness
Original submission (31st October):
maximal differential probability of 3-round differential characteristics is
Updated submission (15th January):
maximal differential probability of any 3-round differential characteristics
is
Page 21, footnote 1:
Original submission (31st October):
similar to the initial permutation and final permutation of DES.
Updated submission (15th January):
similar to the initial and final permutations of DES.
Page 22, Section 6.1.1, first paragraph:
Original submission (31st October):
though its usage in the hash function context is unclear).
Updated submission (15th January):
though the use of linear cryptanalysis in the hash function context is
unclear).
Page 22, Section 6.1.1, third paragraph:
Original submission (31st October):
showing that there security is indeed intact:
Updated submission (15th January):
showing that their security is indeed intact:
Page 22, bullet Impossible Differential Cryptanalysis:
Original submission (31st October):
For $E^{512}$, there is a 9-round impossible differential (a structural
Updated submission (15th January):
For $E^{512}$, there is a 9-round impossible differential (following the
structural
Original submission (31st October):
This (along with the strong round function) suggest that it is secure against
Updated submission (15th January):
The strong round function suggests that there are no longer impossible
differentials, and we conclude that $E^{512}$ is secure against
Page 23, bullet Slide Attacks:
Original submission (31st October):
(where the adversary has no control over the inputs),
Updated submission (15th January):
(where the adversary has almost no control over the inputs),
Page 23, bullet Square Attacks:
Original submission (31st October):
three rounds of $E^{256}$ and $E^{512}$ at most.
Updated submission (15th January):
three rounds of $E^{256}$ and $E^{512}$.
Page 23, Section 6.1.2, third paragraph:
Original submission (31st October):
active in the input and output in any layer of AES rounds in the message
schedule of SHAvite-3.
Updated submission (15th January):
active in the input and the output in any layer of AES rounds in the message
expansion of SHAvite-3.
Original submission (31st October):
especially if the original differences are linear independent as
Updated submission (15th January):
especially if the original differences are linearly independent as
Page 24, Section 6.2, second paragraph:
Original submission (31st October):
the results obtained in [2], which claim that
Updated submission (15th January):
the results obtained in [2] which claim that
Original submission (31st October):
The proof of [2]
Updated submission (15th January):
The claim of [2]
Page 24, Section 6.2, third paragraph:
Original submission (31st October):
requires the use of generic attacks (i.e., exhaustive search).
Updated submission (15th January):
requires the use of generic attacks (i.e., exhaustive search or time-memory
tradeoff attack).
Page 25, Section 6.3, first paragraph:
Original submission (31st October):
This is also true for the signatures schemes and HMAC.
Updated submission (15th January):
This is also true for signatures schemes such as RSA-PSS and message
authentication codes such as HMAC.
Page 26, Section 7, first paragraph:
Removed: "According to the security analysis,"
Page 26, first formula:
Original submission (31st October):
\mbox{HAIFA-MAC}_k(M) = \mbox{HAIFA}^C_k(M).
Updated submission (15th January):
\mbox{HAIFA-MAC}^C_k(M) = \mbox{HAIFA}^C_k(M).
Page 26, last paragraph of section 7:
Original submission (31st October):
but for short messages (up to 53 bytes), it is 50\% gain (also in the
Updated submission (15th January):
but for short messages (up to 53 bytes), it offers a 50\% gain (also in the
Page 26, footnote 2:
Original submission (31st October):
For example, some weak possibilities are identified and discussed
Updated submission (15th January):
For example, some weak possibilities (where the
salt does not enter the real compression function) are identified and
discussed
Page 27, Section 8, second paragraph:
Original submission (31st October):
the speed of an AES round would be reduced to roughly 6 cycles.
Updated submission (15th January):
the speed of an AES round would be reduced to roughly 6 cycles and
several of these rounds can run in parallel.
Page 27, Section 8.1.1, second paragraph:
Original submission (31st October):
3766 cycles per block is reported on an AVR processor.
Updated submission (15th January):
3766 cycles for a block is reported on an AVR processor.
Page 28, Section 8.1.2, first paragraph:
Original submission (31st October):
1 GB RAM, running in a full 32-bit mode).
Updated submission (15th January):
1 GB RAM, running in a full 32-bit mode, compiled with gcc 4.0.3).
Page 28, Section 8.1.3, third paragraph:
Original submission (31st October):
512 KB cache, 1 GB RAM).
Updated submission (15th January):
512 KB cache, 1 GB RAM, compiled with gcc 4.2.4).
Page 29, Table 4:
The titles were changed from "32-Bit Machine" and "64-Bit Machine"
into "32-Bit Platform" and "64-Bit Platform", respectively.
Page 29, second paragraph:
Original submission (31st October):
For SHAvite-3$_{512}$,
where we expect even better use of the command, non-interleaved code (with
168 AES rounds and 528 32-bit XORs) is expected to have a running time of
1540 cycles per invocation,
Updated submission (15th January):
For SHAvite-3$_{512}$,
where we expect even better use of the command, non-interleaved code (with
168 AES rounds and 528 32-bit XORs) is expected to have a running time of
about 1540 cycles per invocation,
Page 29, Section 8.3, second paragraph:
Original submission (31st October):
We shall be interested in two main optimization goals:
Updated submission (15th January):
At the moment, we discuss two optimization goals:
Page 30, Section 8.3.2, third bullet:
Original submission (31st October):
The message expansion can be computed four words at a time.
Updated submission (15th January):
The message expansion can be computed four 32-bit words at a time.
Page 30, Section 8.3.2, first paragraph after the list:
Original submission (31st October):
Hence, an area efficient approach would implement the AES round once, and use
it repeatedly for each application. Due to the way SHAvite-3 works, the
Updated submission (15th January):
Hence, an area efficient approach would implement the AES round once, and
use it repeatedly for each application. Due to the way SHAvite-3 works, an
Original submission (31st October):
each bit requires about~6 gates), and another 1360 gates for the AES core
Updated submission (15th January):
each bit requires about~6 gates) and another 1360 gates for the AES core,
Page 30, last sentence (continues to the next page):
Original submission (31st October):
The longest datapath of $C_{256}$
Updated submission (15th January):
The critical datapath of $C_{256}$
Page 31, first paragraph:
Original submission (31st October):
it seems that one invocation of $C_{256}$ takes about 36 cycles.
Updated submission (15th January):
it seems that one invocation of this implementation of $C_{256}$ takes
about 36 cycles.
Page 31, Section 8.3.3, third paragraph:
Original submission (31st October):
is due to the additional internal memory), and
Updated submission (15th January):
is due to the additional internal memory) and
Original submission (31st October):
(which means a throughput of 1121.5 Mbps).
Updated submission (15th January):
(which means a throughput of 1.12 Gbps).
9. Bibliography:
Original submission (31st October):
10. , Guido Bertoni, Joan Daemen,
Updated submission (15th January):
10. Guido Bertoni, Joan Daemen,
Original submission (31st October):
20. Jean Daemen, Vincent Rijmen The design of Rijndael
Updated submission (15th January):
20. Joan Daemen, Vincent Rijmen, The design of Rijndael
Original submission (31st October):
27. Martin Feldhofer, Johannes Wolfkerstorfer, Vincent Rijmen AES
Implementation
Updated submission (15th January):
27. Martin Feldhofer, Johannes Wolfkerstorfer, Vincent Rijmen, AES
Implementation
Original submission (31st October):
35. Liam Keliher, ..., IACR ePrint report 2005/321.
Updated submission (15th January):
35. Liam Keliher, ..., IACR ePrint report 2005/321, 2005.
10. Test vectors:
All the test vectors for 224-bit and 256-bit versions were replaced due to
an error in the implementation.
Test vectors for 384-bit:
test vector for the string "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
Original submission (31st October):
D9801602 8CF45738 E3693462 3C116A6C 4563630D 4409E219
FCA250C5 FA1BCDF2 A5CAB273 72076F5E EDBF0DA5 6FBC251E
Updated submission (15th January):
ED91E3CE 0C870C9A 43FAC5DB 1921CDC6 E9791999 62A520BA
89104D39 F4CB3CE5 ADA14057 B3E8709A 42A8634E 5BFCF6A8
(change due to using the wrong string).
Test vector for the string "ABCDEFGHIJKLMNOPQRSTUVWXYZ" with salt:
Original submission (31st October):
B1C3EC47 17551167 C2022012 40FD286F 58D614B1 611DDBCB
C2B56CBE 7D10F428 2E4D0070 8F9F5011 FB018AA5 31D0D4A4
Updated submission (15th January):
2BB39B67 3AA85B3A 05245404 E89B308E 8348B206 2BC1061C
4B72A4FB 12FE280F CE48D798 086F43D1 131B8700 5D006D9D
(change due to using the wrong string).
Test vectors for 512-bit:
test vector for the string "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
Original submission (31st October):
D7BB7A7D B0FD516F 7082BB81 4FAC2376 733A462B 4800E553
E1872241 A0B1CC20 61B66339 6646CEB2 C52A904B E2FD7AA8
CDD0B368 A7864C3A 17E41A92 7CC699A9
Updated submission (15th January):
1FBA8163 192CCA3A 8E8D17D2 CD8702D9 72BA8A41 7D0EF27D
303D8818 E4E3A76B CF310F64 7DB46E95 97E7CCAC 42C5CCD5
7E53DDD8 DCED91C5 B28D95E4 A1472AA9
(change due to using the wrong string).
Test vector for the string "ABCDEFGHIJKLMNOPQRSTUVWXYZ" with salt:
Original submission (31st October):
4650F205~3C132994~FA83994B~11F6A2E1~~937E41A8~26818580
E3EF471E~816F461C~~495A43E3~72154215~FD52651D~3480C000
40D382A3~F6E9C459~BBBAEF7C~F8C406E8
Updated submission (15th January):
9F5CE9B9 2308892A 0315CF5C F22752E7 BAAA25FA 7B1D4A6A
52766774 AC8C4B88 A882D2BA 8DD64110 F3E0FEE8 C4AB9CED
73DF065B 92CD912C 928204BD 1415F167
(change due to using the wrong string).
All the internal values of Appendix B were removed (and are now (after
update) in the respective text files).