A new proof for the security of the keyed sponge construction in the ideal compression function model

y length by ℤ2 , the set of infinite-length 
 ∞
bit strings is denoted by ℤ2 , the concatenation of 
two strings x and y is denoted as x‖y. We let 
left ( ) denote the z leftmost bits of x. We 
 Fig.1. The Sponge construction 
 No 2.CS (10) 2019 19 
Journal of Science and Technology on Information Security 
Algorithm 1. 퐒퐩퐨퐧퐠퐞[풇, 풑 풅, 풓] {0,1} , a message ∈ {0,1}∗, and a natural 
Require: < 
 ∗ 
Interface: 푍 = 푠 표푛 푒( , ) with ∈ ℤ2, z > 0 and number . Then, it returns a string 푍 ∈ {0,1} : 
푍 ∈ ℤ2. 
 푃 = || [ ](| |) KeyedSponge퐾( , ) ≔ Sponge (퐾‖ , )
 푠 = 0 = 푍. 
 for i = 0 to |푃| − 1 do 
 − The security model. An adversary 𝒜 is an 
 푠 = 푠 ⊕ (푃푖||0 ) 
 푠 = (푠) algorithm that is given query access to one or 
 end for more oracle 풪, denoted 𝒜풪. Let 𝒜풪 = 1 be 
 = ⌊푠⌋ the event that returns 1 after ′ 
 while | | < do 𝒜 𝒜 푠
 푠 = (푠) interaction. In the security model of this 
 = ||leftz(푠) paper, we consider the KeyedSponge 
 end while construction is built on a random permutation 
 return 푍 = left ( ) 
 z . The PRF-security of Keyed Sponge is the 
 indistinguishability between the real world 
The absorb function. The absorb function. The 
 and the ideal world. Let 풪푅 =
function absorb(⋅) takes as input a message 푃 $
with |푃| multiple of and it outputs the state KeyedSponge퐾(⋅) with 퐾 ← {0,1} be the 
푠 ∈ ℤ oracle in the real world, and 풪 = ℛ풪 be the 
 2 oracle in the ideal world. The 
 푠 = 0 
 indistinguishability considers the case where 
 For 푖 = 0 to |푃| − 1 do 
 − 
 푠 = 푠 ⊕ (푃푖‖0 ) an adversary 𝒜 has query access to 
 푠 = (푠) −1 −1
 (풪푅, , ) in the real world and (풪 , , ) 
 End for 
 Return 푠 in the ideal world, and after 𝒜’s interaction, it 
 outputs a result ∈ {0,1}. We call queries to 
 풪 /풪 “construction queries” and queries to 
Path. 푃 is a path to the state 푠 if 푠 = 푅 
 ( , −1) “primitive queries”. We define the 
absorb(푃). 
 advantage function as 
The Sponge graph. The Sponge function can prf
 AdvKeyedSponge(𝒜)
be represented by the Sponge graph with −1
 풪푅, , 
 + ≔ |Pr[𝒜 = 1]
2 = 2 nodes and 2 edges. The nodes are −1
 − Pr[𝒜풪 , , = 1]|. 
the state values and for every couple (푠, 푡) 
 We denote 푞 and 푄 respectively as the 
 ( )
with 푡 = 푠 there is a directed edge from 푠 number of construction and primitive queries. 
to 푡. From each node, there is only one 
outgoing edge. If is a permutation, in each III. MODEL THE SECURITY OF THE 
 SPONGE CONSTRUCION 
node, there is only one incoming edge. 
 In [12], the authors evaluated the 
These nodes can be divided by the value of indistinguishability of the Sponge 
the inner state. We call the set of all nodes construction when an adversary was able to 
that same inner state by a supernode. Edges query the Sponge construction and the 
 underlying function . Then, in the ideal 
between nodes are therefore also edges world besides the oracle ℛ풪, [12] built 
between supernodes. There are 2 supernodes, another component with the same interface as 
one supernode corresponds to one inner state . For the components to be hard 
value. Each supernode has 2 nodes which to distinguish, it should simulate the behavior 
 of a random permutation of the same width as 
defined by the outer part 푠̅ of their state. 
 . For this reason it is called a simulator, 
The keyed Sponge. denoted 풫. 
The keyed Sponge is denoted as 
KeyedSponge which gets as input a key 퐾 ∈
20 No 2.CS (10) 2019 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 In addition, we have an additional End if 
constraint when an adversary queries to the Return the node 푡 at the end of the outgoing edge from 푠 
real world (the Sponge construction and its Interface 풫−1, taking node 푠 as input 
underlying function ), he the adversary can If node 푠 has no incoming edge then 
 Choose 푡 ̅ randomly and uniformly 
verify whether the responses to the queries are 
 Choose 푡̂ randomly and uniformly from ℤ2\ℛ and such 
Sponge-consistent or not. The Sponge- that 푡‖̅ 푡̂ has no outgoing edge yet 
consistent means that: the result for a Let 푡 = 푡‖̅ 푡̂ 
construction query will be the same as the Add an edge from 푡 to 푠 
 End if 
answer when we simulate the Sponge Return the node 푡 at the beginning of the incoming edge 
construction by querying directly to . In into 푠 
particular, let be a message, if we make a 
construction query ( , ) then we receive 푍. Then, [12] considered the advantage of an 
In the other hand, the message after adversary when distinguishing the two 
padding will have the form: 푃 = following world. 
 ‖pad[ ](| |). Then, we can compute the Real world. It contains the Sponge 
푗th block of 푍 by querying to the function : construction and the underlying random 
푍 = absorb̅̅̅̅̅̅̅̅̅(푃‖0 푗). For the ideal world to permutation . The adversary can make queries 
 푗 to the Sponge construction, the permutation 
be hard to distinguish from the real world it 
 and −1. 
shall also behave sponge-consistent. For that 
reason, the simulator may have query access Ideal world. It contains the random oracle 
to the random oracle ℛ풪 for satisfying ℛ풪 and the simulator 풫. The adversary can 
 make queries to 풫 and 풫−1. 
sponge-consistency. 
 Before going into the specific definition of We define the ℛ풪 differentiating advantage 
the simulator 풫 we recall some symbols. In the as 
Sponge graph, we define the set of rooted ind Sponge , , −1
 AdvSponge(𝒜) ≔ |Pr [𝒜 ]
supernodes ℛ as the subset of ℤ2 containing 0 
 −1
and all the supernodes accessible from it − Pr[𝒜ℛ풪,풫,풫 = 1]| 
through the supernode graph. We say that a 
node 푠 = (푠̅, 푠̂) is rooted if 푠̂ ∈ ℛ. Let be the Theorem 1 (Theorem 9, [12]). The ℛ풪 
set of supernodes with an outgoing edge. differentiating advantage of the Sponge 
 construction calling the random permutation 
Algorithm 2 (see algorithm 9, [12]): The simulator 풫 푖+1
 1− 
 1 −1 2
Interface 풫 , taking node 푠 as input. is upper bound by 1 − ∏푖=0 ( 푖 ) with 
 1−
If node 푠 has no outgoing edge then 2 + 
 If node 푠 is rooted AND ℛ ∪ ≠ ℤ2 (no saturation) is the number of fresh calls to . 
then 
 Construct path to 푡: find path to 푠, append 푠̅ and call the In the paper [12], was denoted by the cost 
result 푃 of the queries. However, in our security model, 
 Write 푃 as 푃 = 푃′0 푗 where 푃′ does not end with 0 it is the number of fresh calls to . 
 if 푃′ can be unpadded into then 
 Assign to 푡 ̅ the value 푍푗 with 푍 = ℛ풪( , 푗 ) IV. OUR EVALUATION FOR THE 
 Else SECURITY OF THE KEYSPONGE 
 Choose 푡 ̅ randomly and uniformly 
 end if In this section, we will evaluate the PRF-
 Choose 푡̂ randomly and uniformly form ℤ2\(ℛ ∪ ) security of the KeyedSponge construction by 
and such that 푡‖̅ 푡̂ has no incoming edge yet using Theorem 1 which states about the ℛ풪 
 Let 푡 = 푡‖̅ 푡̂ differentiating advantage of the Sponge 
 Else 
 Choose 푡 randomly and uniformly from all nodes that construction. 
have no incoming edge yet Proposition 1. Let 𝒜 be an adversary 
 End if 
 Add an edge from 푠 to 푡 making at most 푞 construction queries and at 
 No 2.CS (10) 2019 21 
Journal of Science and Technology on Information Security 
most 푄 primitive queries. Then, the PRF- construction query ( , ) is ℛ풪(퐾‖ , ). It is 
security of the KeyedSponge construction a -bit randomly and uniformly string. This is 
 identical when 𝒜 runs against the KeyedSponge 
calling the random permutation is upper 
 construction. For primitive queries , the result 
bound by: that 𝒜 receives from ℬ is 풫( ) or 풫−1( ). So, 
 푄 푄2 2 we need evaluate the difference between a 
 Advprf(𝒜) ≤ + + , 
 ℱ퐾 2 2 +1 2 +1 random permutation and the simulator 풫. 
where is the number of fresh calls to in Lemma 1 (Lemma 5, [12]). The advantage of 
both query types. an adversary in distinguishing and 풫 with 
 Proof. This result will be proved by the number of queries 푄 < 2 is upper 
reduction. It means that we will prove the bounded by: 
security of the KeyedSponge construction 
through the security of the Sponge construction 푄−1 푖 + 1
 1 − 
by constructing an adversary ℬ which against 1 − ∏ ( 2 ). 
 푖
the Sponge construction from the adversary 𝒜. 1 −
First, ℬ chooses a key 퐾 randomly and 푖=0 2 + 
uniformly from {0,1} , and it remains the same 
throughout the process (𝒜 does no 퐾). If 𝒜 (The proof of this lemma is presented in [12]). 
makes a construction query ( , ) then ℬ When 푄 is significantly smaller than 2 , the 
makes the construction query (퐾‖ , ) to its above bound can be simplified to 푄2/2 +1. 
oracle. If 𝒜 makes the primitive query then Indeed, using the 1 − ≈ 푒− approximation, 
ℬ also makes the primitive query . The we have 
adversary ℬ returns to 𝒜 the value that he 
receives. Final, after making the queries, if 𝒜 푄−1 푖 + 1
 1 − 
returns a bit ∈ {0,1} then ℬ also returns the log ∏ ( 2 )
 푖
bit . This means that, if 𝒜 thinks that the 1 −
oracles, which he interacted, is the real world, 푖=0 2 + 
 푄−1
then B also thinks that the oracles, which he 푖 + 1
interacted, is the real world, and vice versa. = ∑ [log (1 − )
 2 
 Let Pr[𝒜real ⇒ 1] or Pr[𝒜ideal ⇒ 1] be 푖=0
the probability that returns 1 when he is used 푖
 𝒜 − log (1 − )] 
as a subroutine of ℬ, where the oracle that ℬ is 2 + 
interacted is real or ideal world. We have: 
 −1
 Pr[𝒜real ⇒ 1] = Pr [ ℬSponge , , ⇒ 1] 
 푄−1
 푖 + 1 푖
and 
 ≈ ∑ [− − (− + )] 
 −1 2 2
 Pr[𝒜ideal ⇒ 1] = Pr[ℬℛ풪,풫,풫 ⇒ 1]. 푖=0
 푖+1 푖
 In the other hand, in the real world, the = ∑푄−1 [− + ] 
result that 𝒜 receives for the construction query 푖=0 2 2 + 
( , ) is Sponge (퐾‖ , ) =
 푄(푄 + 1) (푄 − 1)푄
KeyedSponge퐾( , ). This means that the view = − + . 
that 𝒜 runs as a subroutine of ℬ same the view 2 +1 2 + +1
that 𝒜 runs against the KeyedSponge 
construction. We have, Then 
 −1
 Pr[𝒜real ⇒ 1] = Pr[𝒜풪푅, , = 1]. 
 Now, we consider when ℬ accesses into the 
ideal model. The result that 𝒜 receives for the 
22 No 2.CS (10) 2019 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 2
 ind 푄 푄
 푄−1 푖 + 1 ≤ AdvSponge(ℬ) + + +1
 1 − 푄(푄+1) (푄−1)푄 2 2
 2 − + 2 2
 ∏ ( ) ≈ 푒 2 +1 2 + +1 . 푄 푄 
 푖
 1 − ≤ + +1 + +1, 
 푖=0 2 + 2 2 2
 where is the number of fresh call to 
So, we have when ℬ making the construction and primitive 
 queries. However, is also the number of fresh 
 푄−1 푖 + 1 call to when 𝒜 making the construction and 
 1 − 푄(푄+1) (푄−1)푄
 2 − +
1 − ∏ ( ) ≈ 1 − 푒 2 +1 2 + +1 primitive queries. Indeed, for the construction 
 푖 query of 𝒜 or 퐾‖ of ℬ, the oracle of 𝒜 
 푖=0 1 − + 
 2 and ℬ both compute Sponge (퐾‖ , ); for the 
 primitive query , both of them compute 
 푄(푄 + 1) (푄 − 1)푄 푄2
 ≈ − = ( ). ( ).■ 
 2 +1 2 + +1 2 +1
 V. CONCLUSION 
 Continue with the case that ℬ accesses into 
 In this paper, the security of the 
the ideal model. We can see that, if 𝒜 runs 
 KeyedSponge construction has been evaluated 
against the KeyedSponge construction then 
 by a new way. We have proved the security of 
ℛ풪( , ) and ( ) (or −1( )) do not have 
 the KeyedSponge construction based on the 
any relationship. When 𝒜 runs as a subroutine security of the Sponge construction by 
of ℬ, the values that he receives for the reduction method. However, our indirect proof 
construction queries and the primitive queries 
 −1 lead to the security bound is not as good as the 
are ℛ풪(퐾‖ , ) and 풫( ) (or 풫 ( )). Note result in the direct way of Guido Bertoni. 
that the simulator 풫 satisfies Sponge-consistent: Therefore, closing this gap will still be an open 
the result for a construction query to ℛ풪 will be problem in the future. 
the same as the answer when we simulate by 
querying directly to 풫. However, this only REFERENCES 
happens when the adversary 𝒜 guesses the key [1]. Bertoni, G., et al. Sponge functions. in ECRYPT 
퐾 among primitive queries. The probability of it hash workshop. 2007. Citeseer. 
is 푄/2 . [2]. Bertoni, G., et al., Keccak specifications. 
Thus, in the case that ℬ accesses into the ideal Submission to NIST (round 2), 2009: p. 320-337. 
 [3]. Maurer, U., R. Renner, and C. Holenstein. 
model, we have Indifferentiability, impossibility results on 
 −1 −1 reductions, and applications to the random oracle 
 ℛ풪,풫,풫 풪 , , 
 Pr[ℬ ⇒ 1] − Pr[𝒜 = 1] methodology. in Theory of cryptography 
 푄 푄2 conference. 2004. Springer. 
 ≤ + . 
 2 2 +1 [4]. Bertoni, G., et al. On the indifferentiability of the 
 sponge construction. in Annual International 
From above arguments we have Conference on the Theory and Applications of 
 prf Cryptographic Techniques. 2008. Springer. 
 AdvKeySponge(𝒜) [5]. Bertoni, G., et al. Sponge-based pseudo-random 
 −1
 = Pr[𝒜풪푅, , = 1] number generators. in International Workshop on 
 Cryptographic Hardware and Embedded Systems. 
 풪 , , −1
 − Pr[𝒜 = 1] 2010. Springer. 
 −1 [6]. Bertoni, G., et al. On the security of the keyed 
 ≤ Pr [ ℬSponge , , ⇒ 1] sponge construction. in Symmetric Key Encryption 
 Workshop. 2011. 
 −1 푄
 ℛ풪,풫,풫 [7]. Bertoni, G., et al., Permutation-based encryption, 
 − Pr[ℬ ⇒ 1] + 
 2 authentication and authenticated encryption. 
 푄2
 + Directions in Authenticated Ciphers, 2012. 
 2 +1 [8]. Dworkin, M.J., SHA-3 standard: Permutation-
 based hash and extendable-output functions. 2015. 
 No 2.CS (10) 2019 23 
Journal of Science and Technology on Information Security 
[9]. Bertoni, G., et al. Duplexing the sponge: single- ABOUT THE AUTHORS 
 pass authenticated encryption and other 
 B.S. Tuan Anh Nguyen 
 applications. in International Workshop on Selected 
 Areas in Cryptography. 2011. Springer. Email: tuananhnghixuan@gmail. com 
[10]. Andreeva, E., et al. Security of keyed sponge The Workplace: Institute of 
 constructions using a modular proof approach. in Cryptography Science and 
 International Workshop on Fast Software Technology, Government 
 Encryption. 2015. Springer. Information Security Committee. 
[11]. Gaži, P., K. Pietrzak, and S. Tessaro. The exact The education process: Graduated 
 PRF security of truncation: tight bounds for keyed in Mathematic, VNU University of 
 sponges and truncated CBC. in Annual Cryptology Science, 2016. 
 Conference. 2015. Springer. Subjects: block cipher, hash function, message 
[12]. Guido, B., et al., Cryptographic sponge functions. 2011. authentication code, tweakable block cipher 
 PhD. Bui Cuong Nguyen 
 Email:nguyenbuicuong@gmail.
 com 
 The Workplace: Institute of 
 Cryptography Science and 
 Technology, Government 
 Information Security 
 Committee. 
 The education process: 
 Graduated in Mathematic, Hanoi National University 
 of Education, 2004. Graduated Master in Mathematics, 
 VNU University of Science, 2007. Graduated PhD in 
 Cryptography, Academy of military science and 
 technology, 2018. 
 Subjects: block cipher, hash function, message 
 authentication code, tweakable block cipher 
24 No 2.CS (10) 2019