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

Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (12) 2020 11 
Hoang Dinh Linh, Tran Hong Thai 
Abstract—We propose a new double-block-
length compression function which is called 
Alpha-DBL. This scheme uses two parallel secure 
single block length schemes based on a block 
cipher with 𝟐𝒏-bit key and 𝒏-bit block size to 
compress a 𝟑𝒏-bit string to a 𝟐𝒏-bit one. We show 
that the Alpha-DBL scheme attains nearly 
optimal collision security and preimage security 
bounds (up to 𝟐𝒏 and 𝟐𝟐𝒏 queries for finding a 
collision and a preimage, respectively). More 
precisely, for 𝒏 = 𝟏𝟐𝟖, no adversary making less 
than 𝟐𝒏−𝟏.𝟐𝟕 = 𝟐𝟏𝟐𝟔.𝟕𝟑 queries can find a collision 
with probability greater than 1/2. To our 
knowledge, this collision security bound is nearly 
better than other such compression functions. In 
addition, we provide a preimage security analysis 
of Alpha-DBL that shows security bound of 
𝟐𝟐𝒏−𝟓 = 𝟐𝟐𝟓𝟏 queries for 𝒏 = 𝟏𝟐𝟖. Using this 
scheme in the iterated hash function construction 
can preserve the collision resistance security and 
the preimage resistance security. 
Tóm tắt—Chúng tôi đề xuất một hàm nén độ 
dài khối kép mới được gọi là Alpha-DBL. Lược đồ 
này sử dụng hai lược đồ độ dài khối đơn an toàn 
song song dựa trên mã khối với khóa 𝟐𝒏-bit và 
kích thước khối 𝒏-bit để nén chuỗi 𝟑𝒏-bit thành 
chuỗi 𝟐𝒏-bit. Chúng tôi đã chứng minh rằng, lược 
đồ Alpha-DBL đạt được cận an toàn kháng va 
chạm và kháng tiền ảnh gần như tối ưu (tối đa 𝟐𝒏 
và 𝟐𝟐𝒏 truy vấn tương ứng để tìm va chạm và tiền 
ảnh). Cụ thể với 𝒏 = 𝟏𝟐𝟖, một kẻ tấn công bất kỳ 
thực hiện ít hơn 𝟐𝒏−𝟏.𝟐𝟕 = 𝟐𝟏𝟐𝟔.𝟕𝟑 truy vấn chỉ có 
thể tìm thấy một va chạm với xác suất nhỏ hơn 1/2. 
Theo hiểu biết của chúng tôi, cận an toàn kháng va 
chạm này tốt hơn so với các hàm nén khác. Ngoài 
ra, chúng tôi đã đưa ra phân tích độ an toàn kháng 
tiền ảnh của Alpha-DBL cho thấy cận an toàn là 
2𝟐𝟐𝒏−𝟓 = 𝟐𝟐𝟓𝟏 truy vấn cho 𝒏 = 𝟏𝟐𝟖. Sử dụng 
lược đồ này trong việc xây dựng hàm băm được 
lặp có thể bảo toàn độ an toàn kháng va chạm và 
an toàn kháng tiền ảnh. 
This manuscript is received on December 23, 2020. It is 
commented on December 24, 2020 and is accepted on 
December 24, 2020 by the first reviewer. It is commented on 
December 30, 2020 and is accepted on December 30, 2020 by 
the second reviewer. 
Keywords—double-block-length compression function, 
collision security, preimage security, ideal cipher model. 
Từ khóa—hàm nén độ dài khối kép, độ an toàn kháng va 
chạm, độ an toàn kháng tiền ảnh, mô hình mã pháp lý tưởng. 
I. INTRODUCTION 
A cryptographic hash function is a function 
which takes an input of arbitrary length and 
returns an output of fixed length. A general way 
of hashing messages of arbitrary length is to 
repeat a compression function using some general 
structures, e.g. Merkle-Damgard, HAIFA... A 
base compression function can be built from a 
mishmash of components or based on 
cryptographic primitives such as block ciphers. 
Block cipher-based compression functions 
have been extensively studied. The most 
common approach is to build a 2𝑛-bit to 𝑛-bit 
compression function using a block cipher of 
𝑛-bit block length, namely a single-block-
length (SBL) compression function. However, 
such an SBL compression function may be 
susceptible to collision attacks because of its 
short output length. For example, we can 
successfully execute a birthday attack on an 
SBL compression function based on the AES-
128 that only approximates 264 queries. This 
prompted the study of double-block-length 
(DBL) compression functions which have the 
output length double the block length of the 
base block cipher. 
DBL compression function can be classified 
into 2 classes: The first class are compression 
functions that use a block cipher with the key 
length of 𝑛-bit, i.e. 𝐸: {0,1}𝑛 × {0,1}𝑛 → {0,1}𝑛, 
denoted by 𝐷𝐵𝐿𝑛. The second class are 
compression functions that use a block cipher 
with the key length of 2𝑛-bit, i.e. 𝐸: {0,1}2𝑛 ×
{0,1}𝑛 → {0,1}𝑛, denoted by 𝐷𝐵𝐿2𝑛. This class 
consists of Tandem-DM [1] and Abreast-DM [1], 
Hirose’s scheme [2], Stam’s Type-I compression 
function [3] and general constructions of Hirose 
[4] and Ozen and Stam construction [5]. All the 
above compression functions provide optimal 
Alpha-DBL: A Reasonable High Secure 
Double-Block-Length Hash Function 
Journal of Science and Technology on Information security 
12 No 2.CS (12) 2020 
collision security (up to 2𝑛 queries), Tandem-
DM, Abreast-DM and Hirose’s scheme have also 
proven to be optimal preimage resistance (up to 
22𝑛 queries). 
Recently, there have been some proposed 
compression schemes such as Weimar-DM [6], 
and MR-MMO [7]. The Weimar-DM scheme 
uses two different keys for two block ciphers in a 
compression function call and is proven secure in 
the ideal cipher model (ICM). The MR-MMO 
scheme claimed by the author is more effective 
when using only one key for both block ciphers in 
a compression function call, but is proven in the 
weak cipher model (WCM). The MR-MMO is 
claimed that its collision resistance security bound 
is tighter than Weimar-DM’s one but it is not valid 
in our understanding of the matter. The first 
reason is that Weimar-DM is considered in the 
ICM while MR-MMO is studied in the WCM. 
Secondly, there is an incorrect statement in the 
proof for MR-MMO’s collision security bound. 
More precisely, in [7] the authors stated that: 
Pr[𝐶𝑗] ≤
2(𝑗 − 1)
(2𝑛 − (2𝑗 − 1))
2 ≤
2(𝑗 − 1)
22𝑛
, 
for 𝑗 ≤ 𝑞. It is clear that this statement is wrong 
which implies that the collision resistance 
security bound is incorrect. On the other hand, 
the two schemes are in the class of cyclic 
compression functions [8], which have been 
shown to be secure generally. 
TABLE 1. THE ANALYSIS RE ... �ℎ𝑡𝑚𝑜𝑠𝑡𝑛(�̅�𝑎) 
= 𝑌𝑏 ⊕ 𝑋𝑏 ⊕ 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑏), 
where 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾) and 𝐿𝑒𝑓𝑡𝑚𝑜𝑠𝑡𝑛(𝐾) are 
𝑛 bits farthest to the right and 𝑛 bits farthest to 
the left of 𝐾, respectively. 
Indeed, the condition (i) implies a collision 
pair (𝐺𝑎 , 𝐻𝑎 , 𝑀𝑎), (𝐺𝑏, 𝐻𝑏 , 𝑀𝑏) with 
𝐻𝑎 = 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑎), 
𝑀𝑎 = 𝐿𝑒𝑓𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑎), 𝐺𝑎 = 𝑋𝑎 ⊕ 𝑀𝑎 , 
𝐻𝑏 = 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑏), 
𝑀𝑏 = 𝐿𝑒𝑓𝑡𝑚𝑜𝑠𝑡𝑛(�̅�𝑏), 𝐺𝑏 = 𝑋𝑏 ⊕ 𝑀𝑏. 
The condition (ii) implies a collision pair 
(𝐺𝑎 , 𝐻𝑎 , 𝑀𝑎), (𝐺𝑏, 𝐻𝑏, 𝑀𝑏) with 
𝐻𝑎 = 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑎), 
𝑀𝑎 = 𝐿𝑒𝑓𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑎), 𝐺𝑎 = 𝑋𝑎 ⊕ 𝑀𝑎 , 
𝐻𝑏 = 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(�̅�𝑏), 
𝑀𝑏 = 𝐿𝑒𝑓𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑏), 𝐺𝑏 = 𝑋𝑏 ⊕ 𝑀𝑏. 
Construction of the list: The adversary 𝒜 will 
make a query number 𝑖 to 𝐸 or 𝐸−1 for 1 ≤ 𝑖 ≤
𝑞. Then the adversary gets a triple-tuple 
(𝑋𝑖, 𝐾𝑖 , 𝑌𝑖) such that 𝐸𝐾𝑖(𝑋𝑖) = 𝑌𝑖 in case of a 
forward query and 𝐸𝐾𝑖
−1(𝑌𝑖) = 𝑋𝑖 in case of a 
backward query. In either case, the value 𝑋𝑖 ⊕
𝑌𝑖 ⊕ 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑖) is randomly determined 
by the output of the query. 
Now, 𝒜′ checks if an entry 𝐿 = (𝑋𝑖, 𝐾𝑖 ,∗,∗) or 
𝐿′ = (𝑋𝑖, 𝐾𝑖 ,∗,∗) belongs to the recent list ℒ, 
where “∗” is an arbitrary value. Obviously, there 
are 2 scenarios: both 𝐿, 𝐿′ are not in ℒ, or both of 
them are already in ℒ. Indeed, if 𝐿𝑖: =
(𝑋𝑖, 𝐾𝑖 , 𝑌𝑖 , 𝑌𝑖′) ∈ ℒ then we also have 𝐿𝑖: =
(𝑋𝑖, 𝐾𝑖 , 𝑌𝑖′, 𝑌𝑖) ∈ ℒ. 
Scenario 1: If 𝐿 or 𝐿′ are not in ℒ. Then 𝒜′ will 
make an additional forward query 𝑌𝑖′ = 𝐸�̅�𝑖(𝑋𝑖). 
Since 𝐾𝑖 ≠ 𝐾𝑖 for every 𝐾𝑖 ∈ {0,1}
𝑛 then the 
value of 𝑌𝑖′ is independently and randomly 
distributed with 𝑌𝑖. Then, the adversary sets 
𝐿𝑖: = (𝑋𝑖, 𝐾𝑖 , 𝑌𝑖 , 𝑌𝑖′) 
and appends to the list ℒ. 
Let 𝑆𝑢𝑐𝑐𝑒𝑠𝑠𝑖, for 1 ≤ 𝑖 ≤ 𝑞, be the event that 
the 𝑖𝑡ℎ success, i.e. there exists 𝑗 < 𝑖 such that 𝐿𝑖 
collide with 𝐿𝑗. For 1 ≤ 𝑗 < 𝑖, we have: 
Pr [
𝑋𝑖 ⊕ 𝑌𝑖 ⊕ 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑖)
= 𝑋𝑗 ⊕ 𝑌𝑗 ⊕ 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑗)
] ≤
1
𝑁 − 𝑞
and 
Pr [
𝑋𝑖 ⊕ 𝑌𝑖
′ ⊕ 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(�̅�𝑖)
= 𝑋𝑗 ⊕ 𝑌𝑗′ ⊕ 𝑅𝑖𝑔ℎ𝑡𝑚𝑜𝑠𝑡𝑛(𝐾𝑗)
] ≤
1
𝑁 − 𝑞
. 
Since these above events are independent then 
the probability of condition (i) occurring is at 
most 
1
(𝑁−𝑞)2
. Similarly, the probability of 
condition (ii) occurring is at most 
1
(𝑁−𝑞)2
. 
Therefore, the probability of success of the 𝑖𝑡ℎ 
query is 
Pr[𝑆𝑢𝑐𝑐𝑒𝑠𝑠𝑖] ≤ ∑
𝑖−1
𝑗=1
2
(𝑁 − 𝑞)2
=
2(𝑖 − 1)
(𝑁 − 𝑞)2
. 
Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (12) 2020 15 
 Thus, the total probability of success for 𝑞 
queries is 
Pr[𝑆𝑢𝑐𝑐𝑒𝑠𝑠(𝑞)] ≤ ∑ Pr[𝑆𝑢𝑐𝑐𝑒𝑠𝑠𝑖] ≤
𝑞(𝑞 − 1)
(𝑁 − 𝑞)2
𝑞
𝑖=1
. 
Scenario 2: Both 𝐿 and 𝐿′ are in ℒ. Therefore, 
𝒜′ ignores this query and we know that 𝒜 has 
no chance of winning. 
 Therefore, the probability of the adversary 
𝒜′ success is 
𝐴𝑑𝑣
𝐹𝐴𝑙𝑝ℎ𝑎
𝐶𝑜𝑙𝑙 (𝒜′) ≤
𝑞(𝑞 − 1)
(𝑁 − 𝑞)2
. 
Now, we return to evaluate the advantage of 
𝒜. We have 
𝐴𝑑𝑣
𝐹𝐴𝑙𝑝ℎ𝑎
𝐶𝑜𝑙𝑙 (𝒜) ≤ 𝐴𝑑𝑣
𝐹𝐴𝑙𝑝ℎ𝑎
𝐶𝑜𝑙𝑙 (𝒜′) ≤
𝑞(𝑞 − 1)
(𝑁 − 𝑞)2
. 
Since 𝒜 is an arbitrary 𝑞-query adversary then 
𝐴𝑑𝑣𝐴𝑙𝑝ℎ𝑎
𝐶𝑜𝑙𝑙 (𝑞) ≤
𝑞(𝑞 − 1)
(𝑁 − 𝑞)2
. 
 We can easily get the following corollary: 
Corollary 1. Let 𝐹𝐴𝑙𝑝ℎ𝑎: {0,1}3𝑛 → {0,1}2𝑛 be 
a compression function based on block cipher 
as defined in Definition 1. Then for 𝑞 ≤ 2𝑛−1.27 
we have 
𝐴𝑑𝑣𝐴𝑙𝑝ℎ𝑎
𝐶𝑜𝑙𝑙 (𝑞) ≤
1
2
+ 𝑜(1) 
where 𝑜(1) tends to 0 when 𝑛 tends to infinity. 
Proof. Firstly, it can be seen that the right hand 
side of Theorem 1 is an increasing function in 𝑞 
for 𝑞 < 𝑁. Consider 
𝑞(𝑞 − 1)
(𝑁 − 𝑞)2
=
1
2
. 
We get 
𝑞 ≈ 𝑁(√2 − 1) = 2𝑛−1.27. 
Applying Theorem 1, we have the proof. 
For example, for 𝑛 = 128 Corollary 1 implies 
that any adversary making less than 2126.73 
queries cannot find a collision with probability 
greater than 1/2. 
The MD-strengthening design preserves 
collision resistance (see Theorem 2.4.1, [11]). 
Combining this with Theorem 1, we get the 
following theorem: 
Theorem 2. Let 𝐻 be an iterated hash function 
built on the compression function 𝐹 defined in 
Definition 1. Then 
 𝐴𝑑𝑣𝐻
𝐶𝑜𝑙𝑙(𝑞) ≤
𝑞(𝑞−1)
(𝑁−𝑞)2
, for every 1 ≤ 𝑞 < 𝑁. 
B. Preimage resistance security 
Theorem 3. Let 𝐹𝐴𝑙𝑝ℎ𝑎: {0,1}3𝑛 → {0,1}2𝑛 be a 
compression function based on block cipher as 
defined in Definition 1. Then 
𝐴𝑑𝑣𝐴𝑙𝑝ℎ𝑎
𝑃𝑟𝑒 (𝑞) ≤
16𝑞
𝑁2
. 
Proof. The idea of the proof follows the proofs of 
Theorems 1 and 2 in [9]. Let 𝑈||𝑉 ∈ {0,1}2𝑛 be 
the preimage target (chosen by the adversary 
before he mounts any query to 𝐸). We need to 
upper bound the probability that the adversary 
finds a point 𝐴||𝐿||𝑀 ∈ {0,1}3𝑛 such that 
𝐹𝐴𝑙𝑝ℎ𝑎(𝐴, 𝐿, 𝑀) = (𝑈, 𝑉) using 𝑞 queries. 
We also reuse the notion of free queries and 
super queries [9]: 
 After the adversary asks a forward query 
𝐸�̅�||𝑀(𝐴 ⊕ 𝐿), it is given the answer of the query 
𝐸𝐿||�̅�(𝐴 ⊕ 𝐿) for free. Similarly, if the adversary 
makes a backward query 𝐸�̅�||𝑀
−1 (𝑅), and receives 
an answer 𝐴 ⊕ 𝐿 = 𝐸�̅�||𝑀
−1 (𝑅) then the answer of 
the forward query 𝐸𝐿||�̅�(𝐴 ⊕ 𝐿) is given for free. 
Therefore, the entries of the adversary’s query 
history 𝒬 can be grouped into adjacent pairs of 
the form (𝐴 ⊕ 𝐿, �̅�||𝑀, 𝑅), (𝐴 ⊕ 𝐿, 𝐿||�̅�, 𝑆), 
namely “adjacent query pair”. 
 After completing each adjacent query 
pair, we check whether the key 𝐾 ∈ {0,1}2𝑛 
used for the latest query satisfies the query 
history contains exactly 𝑁/2 queries with this 
key. If this occurs, all remaining queries under 
the key 𝐾 and the remaining queries under key 
𝐾 will be given to the adversary for free. We add 
these 𝑁/2 free query pairs to the query history. 
Since the adversary is assumed never to make a 
query to which it knows the answer, then the 
adversary cannot make any more queries under 
this key after these free queries have been added 
into the query history. We say that a super query 
occurs if and only if 𝑁/2 free query pairs are 
given to the adversary. Note that a super query 
Journal of Science and Technology on Information security 
16 No 2.CS (12) 2020 
is the set of 𝑁/2 free query pairs that returned 
to the adversary. 
An adjacent query pair (𝐴 ⊕ 𝐿, �̅�||𝑀, 𝑅), 
(𝐴 ⊕ 𝐿, 𝐿||�̅�, 𝑆) is called “winning” if 
𝐴 ⊕ 𝐿 ⊕ 𝑅 ⊕ 𝑀 = 𝑈 and 𝐴 ⊕ 𝐿 ⊕ 𝑆 ⊕ �̅� = 𝑉, 
or if 
𝐴 ⊕ 𝐿 ⊕ 𝑅 ⊕ 𝑀 = 𝑉 and 𝐴 ⊕ 𝐿 ⊕ 𝑆 ⊕ �̅� = 𝑈. 
Therefore, if the adversary obtains a winning 
adjacent query pair then it obtains a preimage of 
𝑈||𝑉. In addition, the winning query pair is part 
of a super query or not. Let 
𝑆𝑢𝑝𝑒𝑟𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬) and 
𝑁𝑜𝑟𝑚𝑎𝑙𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬) be the event that the 
adversary obtains a winning query pair that is 
part of a super query and normal queries, 
respectively. Therefore, we need to upper bound 
Pr[𝑆𝑢𝑝𝑒𝑟𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬)]
+ Pr[𝑁𝑜𝑟𝑚𝑎𝑙𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬)]. 
When the event 𝑁𝑜𝑟𝑚𝑎𝑙𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬) 
occurs. Assume that the adversary asks a forward 
query 𝐸�̅�||𝑀(𝐴 ⊕ 𝐿), then at most (𝑁/2 − 2) 
queries (including free queries) have been 
previously answered with the key �̅�||𝑀. It’s 
implies that, 
Pr[𝐴 ⊕ 𝐿 ⊕ 𝑅 ⊕ 𝑀 = 𝑈] ≤
2
𝑁
. 
If 𝐴 ⊕ 𝐿 ⊕ 𝑅 ⊕ 𝑀 = 𝑈 then the probability 
of the free query 𝐸𝐿||�̅�(𝐴 ⊕ 𝐿) returns 𝐴 ⊕ 𝐿 ⊕
𝑉 ⊕ 𝑀 that is at most 1/(𝑁/2) = 2/𝑁, since the 
answer to the free query comes uniformly at 
random from a set of size at least 𝑁/2 + 2 >
𝑁/2. Therefore, we have 
Pr [
(𝐴 ⊕ 𝐿 ⊕ 𝑅 ⊕ 𝑀 = 𝑈) ∧
(𝐴 ⊕ 𝐿 ⊕ 𝑆 ⊕ �̅� = 𝑉)
] ≤
4
𝑁2
. 
Similarly, 
Pr [
(𝐴 ⊕ 𝐿 ⊕ 𝑅 ⊕ 𝑀 = 𝑉) ∧
(𝐴 ⊕ 𝐿 ⊕ 𝑆 ⊕ �̅� = 𝑈)
] ≤
4
𝑁2
. 
Moreover, since the adversary makes 𝑞 
queries total then we have 
Pr[𝑁𝑜𝑟𝑚𝑎𝑙𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬)] ≤
8𝑞
𝑁2
. (1) 
 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. 
Let 𝒟 and ℛ be the domain and the range of that 
super query, respectively. If 𝐴 ⊕ 𝐿 ∈ 𝒟 then the 
probability that 𝐸�̅�||𝑀(𝐴 ⊕ 𝐿) ⊕ 𝐴 ⊕ 𝐿 ⊕ 𝑀 =
𝑈 is either 0 if 𝐴 ⊕ 𝐿 ⊕ 𝑀 ⊕ 𝑈 ∉ ℛ, or is 
exactly 2/𝑁 if 𝐴 ⊕ 𝐿 ⊕ 𝑀 ⊕ 𝑈 ∈ ℛ. Thus, the 
probability that 𝐸�̅�||𝑀(𝐴 ⊕ 𝐿) ∈ {𝑈 ⊕ 𝐴 ⊕ 𝐿 ⊕
𝑀, 𝑉 ⊕ 𝐴 ⊕ 𝐿 ⊕ 𝑀} is at most 4/𝑁. 
If 𝐸�̅�||𝑀(𝐴 ⊕ 𝐿) ∈ {𝑈 ⊕ 𝐴 ⊕ 𝐿 ⊕ 𝑀, 𝑉 ⊕
𝐴 ⊕ 𝐿 ⊕ 𝑀}, then the probability that 
𝐸𝐿||�̅�(𝐴 ⊕ 𝐿) ∈ {𝑈 ⊕ 𝐴 ⊕ 𝐿 ⊕ �̅�, 𝑉 ⊕ 𝐴 ⊕
𝐿 ⊕ �̅�} is at most 1/(𝑁/2). Therefore, the 
probability that the super query produces a 
winning pair of adjacent queries is at most 
𝑁
2
×
8
𝑁2
=
4
𝑁
. Since there are at most 𝑞/(𝑁/2) super 
queries, we have 
Pr[𝑆𝑢𝑝𝑒𝑟𝑄𝑢𝑒𝑟𝑦𝑊𝑖𝑛(𝒬)] ≤
8𝑞
𝑁2
. (2) 
 Combining (1) with (2) completes the proof. 
Corollary 2. Let 𝐹𝐴𝑙𝑝ℎ𝑎: {0,1}3𝑛 → {0,1}2𝑛 be a 
compression function based on block cipher as 
defined in Definition 1. Then 
𝐴𝑑𝑣𝐴𝑙𝑝ℎ𝑎
𝑃𝑟𝑒 (22𝑛−5) ≤
1
2
. 
Proof. Considering 𝑞 ≤
1
32
𝑁2. Applying 
Theorem 3, we have 
𝐴𝑑𝑣𝐴𝑙𝑝ℎ𝑎
𝑃𝑟𝑒 (22𝑛−5) ≤
1
2
. 
For example, for 𝑛 = 128 Corollary 2 
implies that any adversary making less than 
2251 queries cannot find a preimage with a 
considerable probability. 
The Merkle-Damgard design also preserves 
preimage resistance (see Theorem 2.4.2, [11]). 
Combining Theorem 3 with Theorem 2.4.2 [11], 
we get the preimage resistance of a hash function 
composed of 𝐹 in Definition 1. 
Theorem 4. Let 𝐻 be an iterated hash function 
built on the compression function 𝐹 specified in 
Definition 1. Then 
𝐴𝑑𝑣𝐻
𝑃𝑟𝑒(𝑞) ≤
16𝑞
𝑁2
. 
Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (12) 2020 17 
V. CONCLUSION 
 In this paper, we have proposed a double 
block length compression function called 
Alpha-DBL. We have shown very tight 
collision security bound for the proposed 
scheme. To our knowledge, the collision 
security bound of the proposed scheme is nearly 
better than other double block length schemes. 
On the other hand, the proposed scheme also 
achieves the same preimage security bound as 
the Weimar-DM scheme, which is nearly the 
best second preimage security bound. Using our 
compression function in the iterated hash 
function construction can preserve the collision 
resistance and preimage resistance security. 
Moreover, it is shown in [12] that under certain 
conditions, collision resistance implies second 
preimage resistance. Thus, we conclude that our 
proposed hash function is second preimage 
resistance as well. 
REFERENCES 
[1] Lai, X. and Massey, J.L. “Hash functions based 
on block ciphers”. Workshop on the Theory and 
Application of Cryptographic Techniques. 
Springer, Berlin, Heidelberg, 1992. 
[2] Hirose, S. “Some plausible constructions of 
double-block-length hash functions”. 
International Workshop on Fast Software 
Encryption. Springer, Berlin, Heidelberg, 2006. 
[3] Stam, M. “Blockcipher-based hashing 
revisited”. Fast Software Encryption. Springer, 
Berlin, Heidelberg, 2009. 
[4] Hirose, S. “Provably secure double-block-length 
hash functions in a black-box model. 
International Conference on Information 
Security and Cryptology. Springer, Berlin, 
Heidelberg, 2004. 
[5] Özen, O. and Stam, M. “Another glance at 
double-length hashing”. IMA International 
Conference on Cryptography and Coding. 
Springer, Berlin, Heidelberg, 2009. 
[6] Fleischmann, Ewan, et al. “Weimar-DM: a 
highly secure double-length compression 
function”. Australasian Conference on 
Information Security and Privacy. Springer, 
Berlin, Heidelberg, 2012. 
[7] Miyaji, A. and Rashed, M. “A new (n, 2n) double 
block length hash function based on single key 
scheduling”. The 29th International Conference 
on Advanced Information Networking and 
Applications (AINA), IEEE, 2015. 
[8] Fleischmann, E., Gorski, M., and Lucks, S. 
“Security of cyclic double block length hash 
functions”. IMA International Conference on 
Cryptography and Coding. Springer, Berlin, 
Heidelberg, 2009. 
[9] Armknecht, F., et al. “The preimage security of 
double-block-length compression functions”. 
International Conference on the Theory and 
Application of Cryptology and Information 
Security. Springer, Berlin, Heidelberg, 2011. 
[10] Lee, J., Stam, M., and Steinberger, J. “The 
security of Tandem-DM in the ideal cipher 
model”. Journal of Cryptology, 2017. 30(2): p. 
495-518 
[11] Mennink, B., “Provable security of 
cryptographic hash functions”. University of 
Bristol, UK, 2013. 
[12] Rogaway, P., Shrimpton, T. “Cryptographic 
hash-function basics: Definitions, implications, 
and separations for preimage resistance, second-
preimage resistance, and collision resistance”. In 
International workshop on fast software 
encryption. Springer, Berlin, Heidelberg, 2004. 
ABOUT THE AUTHOR 
Hoang Dinh Linh 
Workplace: Institute of Cryptographic 
Science and Technology 
Email: hoangdinhlinh@bcy.gov.vn 
Education: Received a Bachelor’s 
degree in Mathematics in Hanoi 
University of Science in 2014. 
Current research direction: symmetric cryptography 
algorithm, random number generation, randomness tests. 
Tran Hong Thai 
Workplace: Institute of 
Cryptographic Science and 
Technology 
Email: ththai@bcy.gov.vn 
Education: Received an Engineer’s 
degree in 2000 and Master's degree in 
Cryptographic Engineering in 2007, Academy of 
Cryptography Techniques. 
Current research direction: research and evaluate the 
security of cryptographic hashes and block ciphers.