Alpha-Dbl: A reasonable high secure double-block-length hash function

 푞 oracle queries. where ̅ denotes the bit-by-bit complement of H. 
 The advantage of 풜 finding a IV. PROVABLE SECURITY OF ALPHA-DBL 
collision/preimage of an iterated hash function is 
defined similarly. A. Collision resistance security 
 푙 ℎ 3푛 2푛
 In this model, the experiments make a Theorem 1. Let 퐹 : {0,1} → {0,1} be a 
decision based on the history of the adversary’s compression function based on block cipher as 
queries to encryption/decryption oracles. defined in Definition 1. Then, 
However, the adversary may, without asking 푞(푞 − 1)
anything from the oracles, try to construct a 푣 표푙푙 (푞) ≤ . 
 푙 ℎ ( − 푞)2
collision or a preimage, for example, to guess. 
 Số 2.CS (12) 2020 13 
Journal of Science and Technology on Information security 
Proof. Consider an arbitrary adversary 풜 has = 푅푖 ℎ푡 표푠푡푛(퐾 ), 
 −1
made 푞 queries to or in order to attain a = 퐿푒 푡 표푠푡푛(퐾̅ ), = ⊕ , 
 푙 ℎ 
collision for the compression function 퐹 . 풜 = 푅푖 ℎ푡 표푠푡푛(퐾̅ ), 
 푞
will record a query history 𝒬 = {푄푖}푖=1, where = 퐿푒 푡 표푠푡푛(퐾 ), = ⊕ . 
푄 = ( , 퐾 , 푌 ) such that ( ) = 푌 . Note 
 푖 푖 푖 푖 퐾𝑖 푖 푖 Construction of the list: The adversary 풜 will 
that the adversary 풜 never asks a query to which make a query number 푖 to or −1 for 1 ≤ 푖 ≤
it already knows the answer. We build a more 푞. Then the adversary gets a triple-tuple 
powerful adversary 풜′ which copies 풜 but it can ( ) ( )
 푖, 퐾푖, 푌푖 such that 퐾𝑖 푖 = 푌푖 in case of a 
ask an extra query to in some cases. Therefore, forward query and −1(푌 ) = in case of a 
we just need to find an upper bound of the 퐾𝑖 푖 푖
 backward query. In either case, the value ⊕
advantage of 풜′ finding a collision for 퐹 푙 ℎ . 푖
 푌푖 ⊕ 푅푖 ℎ푡 표푠푡푛(퐾푖) is randomly determined 
 The adversary 풜′ maintains a list ℒ (be null by the output of the query. 
at the beginning) that represents any possible 
 Now, 풜′ checks if an entry 퐿 = ( , 퐾 ,∗,∗) or 
input/output of the compression function 퐹 푙 ℎ 푖 푖
 퐿′ = ( , 퐾̅ ,∗,∗) belongs to the recent list ℒ, 
computed by adversary 풜. An element 퐿 ∈ ℒ is 푖 푖
 where “∗” is an arbitrary value. Obviously, there 
a quad-tuple ( , 퐾, 푌, 푌′) ∈ {0,1}5푛 where ∈
 are 2 scenarios: both 퐿, 퐿′ are not in ℒ, or both of 
{0,1}푛, 퐾 ∈ {0,1}2푛 is the 3푛-bit input to 
 them are already in ℒ. Indeed, if 퐿푖: =
compression function such that 퐾 = ( ̅푖, 푖−1) 
 ( 푖, 퐾푖, 푌푖, 푌푖′) ∈ ℒ then we also have 퐿푖: =
and = 푖−1 ⊕ 푖. The 푛-bit values 푌, 푌′ can 
 ( 푖, 퐾̅푖, 푌푖′, 푌푖) ∈ ℒ. 
be computed by 푌 = 퐾( ) and 푌′ = 퐾̅( ). 
 Scenario 1: If 퐿 or 퐿′ are not in ℒ. Then 풜′ will 
 Let’s define a collision in the list. Fix two 
 ( )
 make an additional forward query 푌푖′ = 퐾̅𝑖 푖 . 
integers , with ≠ , such that 퐿 = 푛
 Since 퐾̅푖 ≠ 퐾푖 for every 퐾푖 ∈ {0,1} then the 
( , 퐾 , 푌 , 푌 ′) represents the -th element in ℒ 
 value of 푌푖′ is independently and randomly 
and 퐿 = ( , 퐾 , 푌 , 푌 ′) is the -th element in 
 distributed with 푌푖. Then, the adversary sets 
ℒ. We say that 퐿 and 퐿 “collide” if we can find 
a collision using the query results given in 퐿 and 퐿푖: = ( 푖, 퐾푖, 푌푖, 푌푖′) 
퐿 . This event occurs if and only if one of the 
 and appends to the list ℒ. 
following two conditions is satisfied: 
 Let 푆 푒푠푠푖, for 1 ≤ 푖 ≤ 푞, be the event that 
 (i) 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ) 푡ℎ
 the 푖 success, i.e. there exists 푗 < 푖 such that 퐿푖 
 = 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ) and 
 ′ collide with 퐿푗. For 1 ≤ 푗 < 푖, we have: 
 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾̅ ) 
 ̅
 = 푌 ′ ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ), 푖 ⊕ 푌푖 ⊕ 푅푖 ℎ푡 표푠푡푛(퐾푖) 1
 Pr [ ] ≤ 
 = ⊕ 푌 ⊕ 푅푖 ℎ푡 표푠푡 (퐾 )
(ii) 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ) 푗 푗 푛 푗 − 푞
 ′ ̅
 = 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ) and and 
 ′ ̅
 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ) ′ ̅
 푖 ⊕ 푌푖 ⊕ 푅푖 ℎ푡 표푠푡푛(퐾푖) 1
 = 푌 ⊕ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾 ), Pr [ ] ≤ . 
 = 푗 ⊕ 푌푗′ ⊕ 푅푖 ℎ푡 표푠푡푛(퐾̅푗) − 푞
where 푅푖 ℎ푡 표푠푡푛(퐾) and 퐿푒 푡 표푠푡푛(퐾) are 
푛 bits farthest to the right and 푛 bits farthest to Since these above events are independent then 
the left of 퐾, respectively. the probability of condition (i) occurring is at 
 most 1 . Similarly, the probability of 
 Indeed, the condition (i) implies a collision ( −푞)2
 1
pair ( , , ), ( , , ) with condition (ii) occurring is at most . 
 ( −푞)2
 = 푅푖 ℎ푡 표푠푡 (퐾 ), 
 푛 Therefore, the probability of success of the 푖푡ℎ 
 = 퐿푒 푡 표푠푡 (퐾̅ ), = ⊕ , 
 푛 query is 
 = 푅푖 ℎ푡 표푠푡푛(퐾 ), 
 ̅ 푖−1
 = 퐿푒 푡 표푠푡푛(퐾 ), = ⊕ . 2 2(푖 − 1)
 Pr[푆 푒푠푠푖] ≤ ∑ = . 
 The condition (ii) implies a collision pair ( − 푞)2 ( − 푞)2
 푗=1
( , , ), ( , , ) with 
14 No 2.CS (12) 2020 
 Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Thus, the total probability of success for 푞 Combining this with Theorem 1, we get the 
queries is following theorem: 
 푞
 푞(푞 − 1) Theorem 2. Let be an iterated hash function 
Pr[푆 푒푠푠(푞)] ≤ ∑ Pr[푆 푒푠푠푖] ≤ . built on the compression function 퐹 defined in 
 ( − 푞)2
 푖=1 Definition 1. Then 
Scenario 2: Both 퐿 and 퐿′ are in ℒ. Therefore, 푞(푞−1)
 푣 표푙푙(푞) ≤ , for every 1 ≤ 푞 < . 
풜′ ignores this query and we know that 풜 has ( −푞)2
no chance of winning. B. Preimage resistance security 
 Therefore, the probability of the adversary Theorem 3. Let 퐹 푙 ℎ : {0,1}3푛 → {0,1}2푛 be a 
풜′ success is compression function based on block cipher as 
 defined in Definition 1. Then 
 표푙푙 푞(푞 − 1)
 푣퐹 푙 ℎ (풜′) ≤ 2. 
 ( − 푞) 푃 푒 16푞
 푣 푙 ℎ (푞) ≤ . 
 Now, we return to evaluate the advantage of 2
풜. We have Proof. The idea of the proof follows the proofs of 
 2푛
 푞(푞 − 1) Theorems 1 and 2 in [9]. Let 푈|| ∈ {0,1} be 
 표푙푙 표푙푙 the preimage target (chosen by the adversary 
 푣퐹 푙 ℎ (풜) ≤ 푣퐹 푙 ℎ (풜′) ≤ 2. 
 ( − 푞) before he mounts any query to ). We need to 
 Since 풜 is an arbitrary 푞-query adversary then upper bound the probability that the adversary 
 finds a point ||퐿|| ∈ {0,1}3푛 such that 
 푞(푞 − 1)
 푣 표푙푙 (푞) ≤ . 퐹 푙 ℎ ( , 퐿, ) = (푈, ) using 푞 queries. 
 푙 ℎ ( − 푞)2
 We also reuse the notion of free queries and 
 We can easily get the following corollary: super queries [9]: 
 푙 ℎ 3푛 2푛
Corollary 1. Let 퐹 : {0,1} → {0,1} be After the adversary asks a forward query 
a compression function based on block cipher 
 ̅ ( ⊕ 퐿), it is given the answer of the query 
as defined in Definition 1. Then for 푞 ≤ 2푛−1.27 퐿|| 
 퐿|| ̅ ( ⊕ 퐿) for free. Similarly, if the adversary 
we have −1
 makes a backward query 퐿̅|| (푅), and receives 
 1 −1
 표푙푙 an answer ⊕ 퐿 = 퐿̅|| (푅) then the answer of 
 푣 푙 ℎ (푞) ≤ + 표(1) 
 2 the forward query 퐿|| ̅ ( ⊕ 퐿) is given for free. 
where 표(1) tends to 0 when 푛 tends to infinity. Therefore, the entries of the adversary’s query 
 history 𝒬 can be grouped into adjacent pairs of 
Proof. Firstly, it can be seen that the right hand 
 the form ( ⊕ 퐿, 퐿̅|| , 푅), ( ⊕ 퐿, 퐿|| ̅, 푆), 
side of Theorem 1 is an increasing function in 푞 
 namely “adjacent query pair”. 
for 푞 < . Consider 
 After completing each adjacent query 
 푞(푞 − 1) 1 2푛
 = . pair, we check whether the key 퐾 ∈ {0,1} 
 ( − 푞)2 2 used for the latest query satisfies the query 
 history contains exactly /2 queries with this 
 We get 
 key. If this occurs, all remaining queries under 
 the key and the remaining queries under key 
 푞 ≈ (√2 − 1) = 2푛−1.27. 퐾
 퐾̅ will be given to the adversary for free. We add 
 Applying Theorem 1, we have the proof. these /2 free query pairs to the query history. 
 For example, for 푛 = 128 Corollary 1 implies Since the adversary is assumed never to make a 
that any adversary making less than 2126.73 query to which it knows the answer, then the 
queries cannot find a collision with probability adversary cannot make any more queries under 
greater than 1/2. this key after these free queries have been added 
 into the query history. We say that a super query 
 The MD-strengthening design preserves occurs if and only if /2 free query pairs are 
collision resistance (see Theorem 2.4.1, [11]). given to the adversary. Note that a super query 
 Số 2.CS (12) 2020 15 
Journal of Science and Technology on Information security 
is the set of /2 free query pairs that returned Let 풟 and ℛ be the domain and the range of that 
to the adversary. super query, respectively. If ⊕ 퐿 ∈ 풟 then the 
 probability that ( ⊕ 퐿) ⊕ ⊕ 퐿 ⊕ =
 An adjacent query pair ( ⊕ 퐿, 퐿̅|| , 푅), 퐿̅|| 
( ⊕ 퐿, 퐿|| ̅, 푆) is called “winning” if 푈 is either 0 if ⊕ 퐿 ⊕ ⊕ 푈 ∉ ℛ, or is 
 exactly 2/ if ⊕ 퐿 ⊕ ⊕ 푈 ∈ ℛ. Thus, the 
 ⊕ 퐿 ⊕ 푅 ⊕ = 푈 and ⊕ 퐿 ⊕ 푆 ⊕ ̅ = , 
 probability that 퐿̅|| ( ⊕ 퐿) ∈ {푈 ⊕ ⊕ 퐿 ⊕
or if , ⊕ ⊕ 퐿 ⊕ } is at most 4/ . 
 ⊕ 퐿 ⊕ 푅 ⊕ = and ⊕ 퐿 ⊕ 푆 ⊕ ̅ = 푈. If 퐿̅|| ( ⊕ 퐿) ∈ {푈 ⊕ ⊕ 퐿 ⊕ , ⊕
 Therefore, if the adversary obtains a winning ⊕ 퐿 ⊕ }, then the probability that 
 ̅
adjacent query pair then it obtains a preimage of 퐿|| ̅ ( ⊕ 퐿) ∈ {푈 ⊕ ⊕ 퐿 ⊕ , ⊕ ⊕
푈|| . In addition, the winning query pair is part 퐿 ⊕ ̅} is at most 1/( /2). Therefore, the 
of a super query or not. Let probability that the super query produces a 
푆 푒 푄 푒 푊푖푛(𝒬) and winning pair of adjacent queries is at most ×
 2
 ( ) 8 4
 표 푙푄 푒 푊푖푛 𝒬 be the event that the = . Since there are at most 푞/( /2) super 
adversary obtains a winning query pair that is 2 
part of a super query and normal queries, queries, we have 
respectively. Therefore, we need to upper bound Pr[푆 푒 푄 푒 푊푖푛(𝒬)] ≤ 8푞. (2) 
 2
 Pr[푆 푒 푄 푒 푊푖푛(𝒬)]
 Combining (1) with (2) completes the proof. 
 + Pr[ 표 푙푄 푒 푊푖푛(𝒬)]. 
 Corollary 2. Let 퐹 푙 ℎ : {0,1}3푛 → {0,1}2푛 be a 
 When the event 표 푙푄 푒 푊푖푛(𝒬) 
 compression function based on block cipher as 
occurs. Assume that the adversary asks a forward 
 defined in Definition 1. Then 
query 퐿̅|| ( ⊕ 퐿), then at most ( /2 − 2) 
queries (including free queries) have been 1
 푣푃 푒 (22푛−5) ≤ . 
previously answered with the key 퐿̅|| . It’s 푙 ℎ 2
implies that, 1
 Proof. Considering 푞 ≤ 2. Applying 
 2 32
 Pr[ ⊕ 퐿 ⊕ 푅 ⊕ = 푈] ≤ . Theorem 3, we have 
 1
 If then the probability 푣푃 푒 (22푛−5) ≤ . 
 ⊕ 퐿 ⊕ 푅 ⊕ = 푈 푙 ℎ 2
of the free query ̅ ( ⊕ 퐿) returns ⊕ 퐿 ⊕
 퐿|| For example, for 푛 = 128 Corollary 2 
 ⊕ that is at most 1/( /2) = 2/ , since the 
 implies that any adversary making less than 
answer to the free query comes uniformly at 
 251 queries cannot find a preimage with a 
random from a set of size at least /2 + 2 > 2
 considerable probability. 
 /2. Therefore, we have 
 The Merkle-Damgard design also preserves 
 ( ⊕ 퐿 ⊕ 푅 ⊕ = 푈) ∧ 4
 Pr [ ] ≤ . preimage resistance (see Theorem 2.4.2, [11]). 
 ̅ 2
 ( ⊕ 퐿 ⊕ 푆 ⊕ = ) Combining Theorem 3 with Theorem 2.4.2 [11], 
 Similarly, we get the preimage resistance of a hash function 
 composed of in Definition 1. 
 ( ⊕ 퐿 ⊕ 푅 ⊕ = ) ∧ 4 퐹
 Pr [ ] ≤ . 
 ( ⊕ 퐿 ⊕ 푆 ⊕ ̅ = 푈) 2 Theorem 4. Let be an iterated hash function 
 built on the compression function 퐹 specified in 
 Moreover, since the adversary makes 푞 
 Definition 1. Then 
queries total then we have 
 8푞 푃 푒 16푞
 Pr[ 표 푙푄 푒 푊푖푛(𝒬)] ≤ . (1) 푣 (푞) ≤ . 
 2 2
 In case the event 푆 푒 푄 푒 푊푖푛(𝒬) 
occurs. Assume that a super query occur on keys 
퐿̅|| and 퐿|| ̅, then the value of 퐿̅|| (. ) and 
 퐿|| ̅ (. ) is already known on exactly /2 points. 
16 No 2.CS (12) 2020 
 Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 V. CONCLUSION on Advanced Information Networking and 
 Applications (AINA), IEEE, 2015. 
 In this paper, we have proposed a double 
block length compression function called [8] Fleischmann, E., Gorski, M., and Lucks, S. 
Alpha-DBL. We have shown very tight “Security of cyclic double block length hash 
collision security bound for the proposed functions”. IMA International Conference on 
 Cryptography and Coding. Springer, Berlin, 
scheme. To our knowledge, the collision Heidelberg, 2009. 
security bound of the proposed scheme is nearly 
better than other double block length schemes. [9] Armknecht, F., et al. “The preimage security of 
On the other hand, the proposed scheme also double-block-length compression functions”. 
achieves the same preimage security bound as International Conference on the Theory and 
 Application of Cryptology and Information 
the Weimar-DM scheme, which is nearly the 
 Security. Springer, Berlin, Heidelberg, 2011. 
best second preimage security bound. Using our 
compression function in the iterated hash [10] Lee, J., Stam, M., and Steinberger, J. “The 
function construction can preserve the collision security of Tandem-DM in the ideal cipher 
resistance and preimage resistance security. model”. Journal of Cryptology, 2017. 30(2): p. 
 495-518 
Moreover, it is shown in [12] that under certain 
conditions, collision resistance implies second [11] Mennink, B., “Provable security of 
preimage resistance. Thus, we conclude that our cryptographic hash functions”. University of 
proposed hash function is second preimage Bristol, UK, 2013. 
resistance as well. [12] Rogaway, P., Shrimpton, T. “Cryptographic 
 hash-function basics: Definitions, implications, 
 and separations for preimage resistance, second-
 REFERENCES preimage resistance, and collision resistance”. In 
 International workshop on fast software 
[1] Lai, X. and Massey, J.L. “Hash functions based encryption. Springer, Berlin, Heidelberg, 2004. 
 on block ciphers”. Workshop on the Theory and 
 Application of Cryptographic Techniques. 
 Springer, Berlin, Heidelberg, 1992. 
 ABOUT THE AUTHOR 
[2] Hirose, S. “Some plausible constructions of 
 Hoang Dinh Linh 
 double-block-length hash functions”. 
 International Workshop on Fast Software Workplace: Institute of Cryptographic 
 Encryption. Springer, Berlin, Heidelberg, 2006. Science and Technology 
 Email: hoangdinhlinh@bcy.gov.vn 
[3] Stam, M. “Blockcipher-based hashing 
 Education: Received a Bachelor’s 
 revisited”. Fast Software Encryption. Springer, 
 degree in Mathematics in Hanoi 
 Berlin, Heidelberg, 2009. University of Science in 2014. 
[4] Hirose, S. “Provably secure double-block-length Current research direction: symmetric cryptography 
 hash functions in a black-box model. algorithm, random number generation, randomness tests. 
 International Conference on Information 
 Security and Cryptology. Springer, Berlin, 
 Tran Hong Thai 
 Heidelberg, 2004. 
 Workplace: Institute of 
[5] Özen, O. and Stam, M. “Another glance at Cryptographic Science and 
 double-length hashing”. IMA International Technology 
 Conference on Cryptography and Coding. Email: ththai@bcy.gov.vn 
 Springer, Berlin, Heidelberg, 2009. 
 Education: Received an Engineer’s 
[6] Fleischmann, Ewan, et al. “Weimar-DM: a degree in 2000 and Master's degree in 
 highly secure double-length compression Cryptographic Engineering in 2007, Academy of 
 function”. Australasian Conference on Cryptography Techniques. 
 Information Security and Privacy. Springer, Current research direction: research and evaluate the 
 Berlin, Heidelberg, 2012. security of cryptographic hashes and block ciphers. 
[7] Miyaji, A. and Rashed, M. “A new (n, 2n) double 
 block length hash function based on single key 
 scheduling”. The 29th International Conference 
 Số 2.CS (12) 2020 17