Cryptography Reference
In-Depth Information
If
j
is in the interval [1
,
d
], the probability of success is
Pr[
h
K
(
x
)
⊕
K
j
=
c
|
h
K
(
x
j
)
⊕
K
j
=
c
j
,
I
]
where
I
={
h
K
(
x
i
)
⊕
K
i
=
c
i
;
i
∈
[1
,
d
]
,
i
=
j
}
.
Because
of
the
distribution
of
K
1
,...,
K
j
−
1
,
K
j
+
1
,...,
K
d
, we can easily see that
I
is useless in the above prob-
ability. Finally we have
⊕
K
j
=
|
⊕
K
j
=
=
⊕
Pr[
h
K
(
x
)
c
h
K
(
x
j
)
c
j
]
Pr[
h
K
(
x
)
h
K
(
x
j
)
=
⊕
c
j
|
⊕
K
j
=
≤
ε
c
h
K
(
x
j
)
c
j
]
since
K
j
is independent from
K
.
Note that this construction generalizes by defining the MAC of
x
as being
h
K
(
x
)
encrypted using a stream cipher (instead of the Vernam cipher).
As an example of XOR-universal hash function family, we provide here a con-
struction based on linear feedback shift registers (LFSR) called LFSR Toeplitz hash
function, which is due to Hugo Krawczyk (see Ref. [108]). Given two parameters
m
and
n
, we define a hash function
h
K
from
{
0
,
1
}
n
to
{
0
,
1
}
m
based on a key
K
=
(
p
,
s
0
)
where
s
0
=
(
s
0
,...,
s
m
−
1
) is a bitstring of length
m
and
p
defines a polynomial
p
m
x
m
of degree
m
, with coefficients in GF(2), and which
is irreducible. (Note that this implies
p
0
=
p
(
x
)
=
p
0
+
p
1
x
+···+
p
m
=
1.) We define an LFSR as a finite
automaton whose state at time
t
is a bitstring
s
t
s
t
+
m
−
1
) of length
m
and
which is updated following the connection polynomial
p
(
x
), i.e. we have the following
recursion formula:
=
(
s
t
,...,
m
−
1
s
t
+
m
=
p
j
s
t
+
j
.
j
=
0
The LFSR is first initialized to
s
0
x
n
−
1
of
n
bits simply consists of XORing the states
s
t
, which correspond to a time
t
for which
x
t
=
defined by
K
. Hashing a message
x
0
,...,
1:
s
t
h
K
(
x
0
,...,
x
n
−
1
)
=
.
0
≤
t
<
n
x
t
=
1
We can prove that given a fixed
m
and
n
, the family of all
h
K
hash functions is
ε
-XOR-
2
1
−
m
.
universal with
ε
=
n
×
3.4.6 MAC from Hash Functions: HMAC
Making a hash function from a MAC algorithm is quite trivial: we just need to take
a constant key. However, we need to keep in mind that MAC does not usually protect
against collision attacks.
Search WWH ::
Custom Search