Langzeitsichere Signaturen durch den Einsatz hashbasierter Signaturverfahren Andreas Hülsing, Johannes Braun 16.05.2013 | TU Darmstadt | A. Huelsing |

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


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


RSA – DSA – EC-DSA - …


Trapdoor one-way function

Digital signature scheme

Collision resistant hash

function

RSA, DH, SVP, MQ, …

Merkles Signaturverfahren


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


Vorwärtssichere Digitale Signaturen


Vorwärtssichere Digitale Signaturen


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


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


Langzeitsicherheit


XMSS Langzeitmechanismen

„Frühwarnsystem“

Redundanz

Effizientere Archivierung (siehe Robuste PKI)


FREE

Frühwarnsystem


Eigenschaften von (Hash)Funktionsfamilien


Kollisionsresistenz

2nd-preimage-resistenz

Einweg Pseudozufällig

An

na

hm

e /

An

gri

ffe

stark / leichter

schwach /schwerer

Angriffe auf Hashfunktionen


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


Redundanz


Redundanz

Hash-Combiner- Kollisionsresistenz / 2nd-Preimage-Resistenz:

- PRF:


)(||)()( 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


Effiziente Archivierung


Kettenmodell mittels FSS

sk1 sk2 skiskT

sk1 sk2

sk1 sk2 skj

),( jMtime

End entity certificate

CA certificate

Root certificate


Robuste PKI

- Kettenmodell mit FSS

-> Weniger Zeitstempel

-> Effizientere Archivierung


Danke!

Fragen?



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


Nmmqmmp

km khH }}1,0{|}1,0{}1,0{:{ )()(

Konstruktion


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


PRG

PRG

PRG

PRG

PRG

PRG


= ( , 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


i

i Signatur = (i, , , , )

b0 b0 b0 b0

b1 b1

b2

Vorwärtssicheres XMSS


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!


XMSS in der Praxis



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


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

Documents

Langzeitsichere Signaturen durch den Einsatz hashbasierter Signaturverfahren Andreas Hülsing, Johannes Braun 16.05.2013 | TU Darmstadt | A. Huelsing |