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