Ammour K, et al. Sci China Inf Sci March 2019 Vol. 62 032112:3
claim the non-necessity of pre fix-free c omputing (PFC) for PRO MDHF by providing a counterexam-
ple. We construct an indifferentiable MDHF assuming the compression function to be ideal. Mainly, we
tweak the padding algorithm. Our padding algorithm is defined as Pad(M) := Pad
1
(M)kPad
2
(M), wher e
k is concatenation, and Pad
1
(·) and Pad
2
(·) are two suffix-free padding algorithms (refer to Section 4 for
details). The hash process is the same as strengthened MD (SMD). Note that each message block is
hashed twice. Further, Liskov et al. [23] proposed an itera ted MDHF that processes each block twice.
Our c ounterexample is not prefix-free computing, i.e., for two messages M and M
′
= Pad(M), Pad(M) is
a prefix of Pad(M
′
). We provide a definition of the simulator that permits the maintenance of consistency
with RO in order to prove the indifferentiability of our construction.
Finally, we observed that there is no relationship between LEA and the PFC property. Indeed, from
our non-PFC counterexample given above, which is PRO, we deduce that an LEA-resistant MDHF need
not be a prefix-free computing algorithm. Furthermore, we provide a simple PFC MDHF construction
that uses a permutation at its end. We show that this construction is not secure against LEA. We
conclude that the PFC property for MDHF is not necessarily secur e agains t LEA.
Paper outline. Section 2 introduces the notations and definitions used in this pa per. The related
work a bout the variants of PRO-MDHF and the common structural property der ived are provided in
Section 3. Section 4 explores the PFC non-necessity for a PRO-MDHF. Finally, in Section 5, we show
there is no relationship between the resistance against LEA and the PFC property for an MDHF.
2 Preliminaries
In this sectio n, we introduce notations and properties which will be used throughout this paper.
Notations. Let A be the distinguisher (adversary) and hM i represents the length of a message M
in bits. MDHF denotes the Merk le -Damg˚ard ha sh function, RO represents the random oracle and S
the simulator. Let CF be the compression function, Pad the padding alg orithm, PFC-MD the prefix
free computing Merkle-Damg˚ard and PFE-MD the prefix free encoding Merkle-Damg˚ard. Assigning a
random value fro m {0, 1}
n
to z is denoted by z
$
←− {0, 1}
n
.
Random oracle (RO). The fixed-input-length random oracle (FIL-RO) is defined by a func-
tion f such that f: {0, 1}
m
7→ {0, 1}
n
chooses the value f(x) randomly from {0, 1}
n
for each x ∈
{0, 1}
m
. More precisely, assume that a subset of the input-output relations of f is known: f (x
1
) =
y
1
, f(x
2
) = y
2
, . . . , f(x
t
) = y
t
. For simplicity, we denote f (X) = Y where X = {x
1
, x
2
, . . . , x
t
} and
Y = {y
1
, y
2
, . . . , y
t
}. For a ny x ∈ {0, 1}
m
\X, Pr[f(x) = y|f (X) = Y ] =
1
2
n
for any y ∈ {0, 1}
n
. In
this paper, a random oracle RO is referred to as the one with arbitrary-length inputs, whose domain
is usually denoted as {0, 1}
∗
. Let F be the set of all functions f with the same domain and range.
The compression function CF can be e qually regarde d as a function f uniformly and randomly selected
from F.
Merkle-Damg˚ard hash functions (MDHF). MD hash function uses four basic parts which are
defined as follows:
(1) An initial value IV ∈ {0, 1}
n
.
(2) An underlying compress ion function CF: {0, 1}
n+b
7→ {0, 1}
n
such that CF(h
i−1
, m
i
) = h
i
.
(3) A classica l iterated function CF
+
IV
: ({0, 1}
n+b
)
+
7→ {0, 1}
n
defined as CF
+
IV
(m
1
, . . . , m
ℓ
) =
CF(· · · CF(CF(IV, m
1
), m
2
), · · · , m
ℓ
)
(4) An injective function called padding function Pad : {0, 1}
∗
7→ ({0, 1}
b
)
+
such that for a message
M ∈ {0, 1}
∗
, Pad(M) = (m
1
, . . . , m
ℓ
) where ℓ is the number of blocks in the message M. O ne of the roles
of ℓ is to make the length of the message compatible with the domain of CF
+
IV
.
So, the classical iterated MDHF is defined for all M ∈ {0, 1}
∗
as MD
CF
IV,Pad
(M) = CF
+
IV
(Pad(M)).
Indifferentiability. According to [10, 11], the indifferentiability is defined as follows.
Definition 1. An algorithm H with access to an ideal primitive CF is said to be (t
A
, t
S
, q, ǫ) indiffer-
entiable from an ideal primitive RO if there is a simulator S such that for any distinguisher A it holds
that
剩余14页未读，继续阅读
weixin_38621427
- 粉丝: 10
- 资源: 941
我的内容管理
展开
最新资源
- zlib-1.2.12压缩包解析与技术要点
- 微信小程序滑动选项卡源码模版发布
- Unity虚拟人物唇同步插件Oculus Lipsync介绍
- Nginx 1.18.0版本WinSW自动安装与管理指南
- Java Swing和JDBC实现的ATM系统源码解析
- 掌握Spark Streaming与Maven集成的分布式大数据处理
- 深入学习推荐系统：教程、案例与项目实践
- Web开发者必备的取色工具软件介绍
- C语言实现李春葆数据结构实验程序
- 超市管理系统开发：asp+SQL Server 2005实战
- Redis伪集群搭建教程与实践
- 掌握网络活动细节：Wireshark v3.6.3网络嗅探工具详解
- 全面掌握美赛：建模、分析与编程实现教程
- Java图书馆系统完整项目源码及SQL文件解析
- PCtoLCD2002软件：高效图片和字符取模转换
- Java开发的体育赛事在线购票系统源码分析
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
