View
112
Download
1
Category
Preview:
Citation preview
Langzeitsichere Signaturen durch den Einsatz hashbasierter Signaturverfahren
Andreas Hülsing, Johannes Braun
16.05.2013 | TU Darmstadt | A. Huelsing | 1
Langzeitsicherheit
Realwelt:
Handschriftliche Signatur theoretisch unendlich gültig
16.05.2013 | TU Darmstadt | A. Huelsing | 2
Digital:
Sicherheit Kryptographischer Schlüssel „verblasst“
Verfahren können plötzlich unsicher werden
Outline
Hash-basierte Signaturen
Langzeitsicherheit
16.05.2013 | TU Darmstadt | A.Huelsing | 3
Hash-basierte Signaturen
16.05.2013 | TU Darmstadt | A. Huelsing | 4
RSA – DSA – EC-DSA - …
16.05.2013 | TU Darmstadt | A. Huelsing | 5
Trapdoor one-way function
Digital signature scheme
Collision resistant hash
function
RSA, DH, SVP, MQ, …
Merkles Signaturverfahren
16.05.2013 | TU Darmstadt | A. Huelsing | 6
OTS
OTS OTS OTS OTS OTS OTS OTS
hh h h h h h h
h h h h
h h
h
PK
Secret Key
State of the Art
eXtended Merkle Signature Scheme (XMSS) / [PQ-Crypto, 2011]
XMSS+
[SAC 2012]
Minimale komplexitätstheoretische Annahmen
Generische Konstruktion
Effizient (vergleichbar mit RSA)
Vorwärtssicher
16.05.2013 | TU Darmstadt | A. Huelsing | 7
Vorwärtssichere Digitale Signaturen
16.05.2013 | TU Darmstadt | A. Huelsing | 8
Vorwärtssichere Digitale Signaturen
16.05.2013 | TU Darmstadt | A. Huelsing | 9
time
classical
pk
sk
Key g
en.
forward sec
pk
sk
sk1 sk2 skiskT
t1 t2 titT
ijjMGoal ),,(:
XMSS Implementierungen
C Implementierung mit OpenSSL
Sign (ms)
Verify (ms)
Signature (byte)
Public Key (byte)
Secret Key (byte)
Bit Security
XMSS-SHA-2 15,17 1,02 2.083 1.696 3.364 146 H = 20,w = 64
XMSS-SHA-2 33,47 2,34 1.923 1.696 3.364 100 H = 20,w = 108
XMSS-AES-NI 1,72 0,11 2.451 912 1.684 93 H = 20,w = 4
XMSS-AES 2,87 0,22 2.451 912 1.684 93 H = 20,w = 4
RSA 2048 3,08 0,09 ≈ 256 ≈ 512 ≈ 512 87
Intel(R) Core(TM) i5 CPU M540 @ 2.53GHz with Intel AES-NI
16.05.2013 | TU Darmstadt | A. Huelsing | 10
XMSS Implementierungen
Smartcard Implementierung
Sign (ms)
Verify (ms)
Keygen(ms)
Signature (byte)
Public Key (byte)
Secret Key (byte)
Bit Sec.
Comment
XMSS 134 23 925.400 2.388 800 2.448 97 h = 16,w = 4, k = 4
XMSS+ 106 25 5.600 3.476 544 3.760 96 H = 16,w = 4, k = 2
XMSS+ 173 28 10.500 1.588 544 3.056 92 H = 16,w = 32, k = 2
XMSS+ 124 22 28.300 1.956 576 3.744 89 H = 20,w = 16, k = 4
RSA 2048
190 7 11.000 ≈ 256 ≈ 256 ≈ 512 87
Infineon SLE78 16Bit-CPU@33MHz, 8KB RAM, TRNG, Sym. co-processor
16.05.2013 | TU Darmstadt | A. Huelsing | 11
Langzeitsicherheit
16.05.2013 | TU Darmstadt | A. Huelsing | 12
XMSS Langzeitmechanismen
„Frühwarnsystem“
Redundanz
Effizientere Archivierung (siehe Robuste PKI)
16.05.2013 | TU Darmstadt | A. Huelsing | 13
FREE
Frühwarnsystem
16.05.2013 | TU Darmstadt | A. Huelsing | 14
Eigenschaften von (Hash)Funktionsfamilien
16.05.2013 | TU Darmstadt | A. Huelsing | 15
Kollisionsresistenz
2nd-preimage-resistenz
Einweg Pseudozufällig
An
na
hm
e /
An
gri
ffe
stark / leichter
schwach /schwerer
Angriffe auf Hashfunktionen
16.05.2013 | TU Darmstadt | A.Huelsing | 16
2004 2005 2008
MD5 Kollisionen
(theo.)
SHA-1 Kollisionen
(theo.)
MD5 Kollisionen(praktisch!)
2012
MD5 & SHA-1Keine (Second-)
Preimage Attacks!
Frühwarnsystem
XMSS benötigt keine Kollisionsresistenz
Wenn Kollisionsresistenz gebrochen – wechsel Hashfunktion
Archiv: Übersignatur
Nur halbe Wahrheit: Nachrichtenhash!
Aber: Kein Problem für Archiv
16.05.2013 | TU Darmstadt | A.Huelsing | 17
Redundanz
16.05.2013 | TU Darmstadt | A.Huelsing | 18
Redundanz
Hash-Combiner- Kollisionsresistenz / 2nd-Preimage-Resistenz:
- PRF:
16.05.2013 | TU Darmstadt | A. Huelsing | 19
)(||)()( xfxgxh kkk
)()()( xfxgxh kkk
Redundanz (cont‘d)
Verhindert unerwarteten Bruch des Verfahrens
ersetzt Doppelsignatur
Signaturgröße wächst nur minimal, i.e. +H*n
Laufzeit ~ verdoppelt
16.05.2013 | TU Darmstadt | A.Huelsing | 20
Effiziente Archivierung
16.05.2013 | TU Darmstadt | A.Huelsing | 21
Kettenmodell mittels FSS
sk1 sk2 skiskT
sk1 sk2
sk1 sk2 skj
),( jMtime
End entity certificate
CA certificate
Root certificate
16.05.2013 | TU Darmstadt | A.Huelsing | 22
Robuste PKI
- Kettenmodell mit FSS
-> Weniger Zeitstempel
-> Effizientere Archivierung
16.05.2013 | TU Darmstadt | A. Huelsing | 23
Danke!
Fragen?
16.05.2013 | TU Darmstadt | A.Huelsing | 24
02.12.2011 | TU Darmstadt | A.Huelsing | 25
Ausgabelänge von Hashfunktionen
HashfunktionsfamilieAnnahme:
- generische Angriffe,- Sicherheitslevel n
Collision resistance:
→ Generischer Angriff = Geburtstagsangriff → m = 2n
2nd-preimage resistance:
→ Generischer Angriff = Vollständige Suche → m = n
16.05.2013 | TU Darmstadt | A. Huelsing | 26
Nmmqmmp
km khH }}1,0{|}1,0{}1,0{:{ )()(
Konstruktion
16.05.2013 | TU Darmstadt | A. Huelsing | 27
Winternitz parameter w, security parameter n, message length m, function family
Key Generation: Compute l , sample k, sample R
WOTS+
21.03.2013 | TU Darmstadt | Andreas Hülsing | 28
c0k(skl , R ) = skl
c1k(skl ,
R )pkl = cw-1
k(skl , R )
}}1,0{|}1,0{}1,0{:{ nnnkn kfF
c0k(sk1, R ) = sk1
c1k(sk1, R )
pk1 = cw-1k(sk1, R )
WOTS+ Signature generation
21.03.2013 | TU Darmstadt | Andreas Hülsing | 29
M
b1 b2 b3 b4 … … … … … … … bl 1bl 1+1 bl 1+2 … … bl
C
c0k(skl , R ) = skl
pkl = cw-1k(skl , R )
c0k(sk1, R ) = sk1
pk1 = cw-1k(sk1, R )
σ1=cb1k(sk1, R )
σl =cbl k(skl ,
R )
XMSS verwendet mehrere Einmalsignaturschlüssel.Generiert mittels Pseudozufallsgenerators (PRG), konstruiert
mittels PRFF Fn:
Secret key: Zufälliger SEED für pseudozufällige Erzeugung des aktuellen Signaturschlüssels.
XMSS – Secret key
16.05.2013 | TU Darmstadt | A. Huelsing | 30
PRG
PRG
PRG
PRG
PRG
PRG
16.05.2013 | TU Darmstadt | A. Huelsing | 31
= ( , b0, b1, b2, h)
h h h h h h h h
XMSS – Public key
b0 b0 b0 b0
b1 b1
bh
h h
h
h
h
h
h
Modifizierter Merkle Tree [Dahmen et al 2008] h: 2nd-preimage resistant Hashfunktion
Public key
XMSS Signatur
16.05.2013 | TU Darmstadt | A. Huelsing | 32
i
i Signatur = (i, , , , )
b0 b0 b0 b0
b1 b1
b2
Vorwärtssicheres XMSS
16.05.2013 | TU Darmstadt | A. Huelsing | 33
FSPRG FSPRG FSPRG FSPRGFSPRG
PRG
FSPRG: Vorwärtssicherer PRG basierend auf PRFF Fn
i
j
Beschleunigte SchlüsselerzeugungTree Chaining (XMSS+)
2h+1 → 2*2 h/2+1 = 2 h/2+2
Aber: Größere Signaturen!
16.05.2013 | TU Darmstadt | A. Huelsing | 34
XMSS in der Praxis
16.05.2013 | TU Darmstadt | A. Huelsing | 35
16.05.2013 | TU Darmstadt | A. Huelsing | 36
XMSS – InstantiierungenBlockchiffren
Gegeben: Blockchiffre
Ist pseudozufällige Funktionsfamilie
Hashfunktion
mittels Matyas-Meyer-Oseas & Merkle-Darmgard:
}}1,0{|}1,0{}1,0{:{ nnnkn kfF
K
M
C
k
M1
M2
}}1,0{|}1,0{}1,0{:{ )()( mqmmpkm khH
hk(M)
M = M1 || M2
16.05.2013 | TU Darmstadt | A. Huelsing | 37
XMSS – InstantiierungenHashfunktion
Gegeben: M-D Hashfunktion
Annahme: Ist zufällige Funktion aus Familie
PRFF
mittels HMAC Variante:
}}1,0{|}1,0{}1,0{:{ nnnkn kfF
mmpmh }1,0{}1,0{: )(
h
Pad(k)
h h(M)
IV
M
Recommended