Hash cse lecture2

  • Published on
    22-May-2015

  • View
    1.035

  • Download
    0

Embed Size (px)

Transcript

  • 1. 1
    -. 2:

    Microsoft Research, Silicon Valley
    , 16-17 , 2011

2.


,

-
-


-

2
3.
-
:
,=h,
g p, ,/
,=,
h=h
+=+, =h

3
4.
4
23=3651.2

5.
5
:0,1->[1..]
H(x1), H(x2),, H(xm)
,
i, j [1..m], H(xi) = H(xj)?

6.

Eij=1,=()0,()
:
Pr1

6
7. ...
, :
11112131
, 1,
01/2/3/=(1)2
, 12>ln2, > 50%.

7
8.

:
Pr>1

8
9.
H(x1), H(x2),, H(xm),...
MD5 128 , 1000 .
264:
~ 228Tb
200K CPU/

9
10.
:
:0,1->[1..]
:[1..]->[1..]

10
11.
11
DES:
P. Flajolet and A. Odlyzko, Random mapping statistics
12.
:
12log
:
0.76
:
0.78

12
13.
13

xi+1=H(xi)



14.
14
xi+1=H(xi)

=/8


=/8

15.
15
: xi+1=H(xi)
:yi+1=H(H(yi))
16.
16
: xi+1=H(xi)
:yi+1=H(H(yi))
+

17.
17
: xi+1=H(xi)
:yi+1=H(H(yi))
xk= yk= x2k
18.
18
: xi+1=H(xi)
:yi+1=H(H(yi))
xk= yk= x2k

19.
, :
19
xi+1=H(xi)
()

(4)

(3)

(2)

(1)

Nivasch, "Cycle detection using a stack", IPL, 2004
20.
20
xi+1=H(xi)
min
~log N
21.
:
=.000

21
k
1

1

,

2

2

3

3

4

4

Oorschot, Wiener, Parallel Collision Search with Application to Hash Functions and Discrete Logarithms, ACM CCS, 1994
22.
22

,

=



=




23.
:2
:/2
: 2/2
!


23
24.
24




25.
3- ?
2/3 1/3:
Joux, Lucks, Improved generic algorithms for 3-collisions, ASIACRYPT09

25
26. -
-> -
1:
1,,=()
2:
1,,=(,)

26
27. -
27



2,2

1,1

4,4

3,3

28. -
28



1,1

3,3

2,2

4,4

29. -
29



2

1,1

3,3

2,2

4,4









30. -
30
22>2()/2

00



222=22

00
00


2

1,1

3,3

2,2

4,4









31. -
31
22>2()/2

00



==/3

222=22

00
00


2

1,1

3,3

2,2

4,4









32. -
32
22>2()/2

00



==/3

222=22

2/3

00
00


2

1,1

3,3

2,2

4,4









33.
=2
2+1
: =3?
?

33
Wagner, A Generalized Birthday Problem, CRYPTO02
34.
- (time-memory trade-off)
34
()=

?
35. -
35
36.
36
1

2

3

4

5

1

2

3

4

5

1,1

2,2

3,3

4,4

5,5

37.
37
1

1

1,1

2

2,2

2

3,3

3

3

4,4

4

4

5,5

5

5



=

38.
38
t
1

2

3

4

5

1

2

3

4

5

:
/

:
1/2

m


2
->=+1->+1->+1

40. !
40
t
11

11

>

21

21

1

m

2


3

=
=

2
2


2>2

23>2


42.
42
2
2

==2/3

43. -
43
44. 11

:
44
11

21

21

1

=.000

m

1

1

k
12

12

2

22

22

m

2

2

1

1

2

2



m





()!
45. :
45
t
t

1

2



11

11

1

1

21

21

2

2

m

3

3

1

1

12

12

22

22

m




2

2

1

1

2

2

m









Oechslin, "Making a Faster Cryptanalytic Time-Memory Trade-off", CRYPTO'03
46. passcracking.com
MD5(1..7 - )
: 24
-:
-: 30
26Mb
(http://www.freerainbowtables.com/en/tables/)
46
47. -
?
:
47
3>3

==3/4

Fiat, Naor, Rigorous Time/Space Tradeoffs for Inverting Functions, STOC 1991
48.
:
, H()
48
:
49.
49
()





+1



0.1% 8 50%
Narayanan,Shmatikov, Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff, ACM CCS05
50.



50
51. ...
:
, H()
+
, r, H(r||)
51
52. -
1:

2:

52
2>()2


2>2

2>2

2>2

S
53. -
1:

2:

2>()2

53
2>2
=


2>()2

: ?
54.
:
?
HKDF (RFC 5869)
54
Krawczyk, Cryptographic Extraction and Key Derivation: The HKDF Scheme,CRYPTO 2010