Ewan FleischmannZertifikatlose Public-Key Kryptographie Sicherheitsbeweise für zertifikatlose Public-Key Schemata Ewan Fleischmann Kryptowochenende 2006

Ewan Fleischmann Zertifikatlose Public-Key Kryptographie

Sicherheitsbeweise für zertifikatlose Public-Key Schemata

Ewan Fleischmann

Kryptowochenende 200601/02. Juli 2006

Ewan Fleischmann Zertifikatlose Public-Key KryptographieEwan Fleischmann Zertifikatlose Public-Key Kryptographie

Ziele der Diplomarbeit

Thema: Im Standardmodell beweisbar sichere Public-Key Kryptographie

Ziele:• Suchen nach einfacher zu beschreibendem, aber äquivalentem, Angriffsmodell

• Problematik der Sicherheitsbeweise im Standardmodell

• Generische Konstruktionsmethoden für zertifikatlose Kryptosysteme

• Konstruktion eines konkreten, im Standardmodell sicheren Systems

Ewan Fleischmann Zertifikatlose Public-Key KryptographieEwan Fleischmann Zertifikatlose Public-Key Kryptographie

GrundlagenZertifikatlose VerschlüsselungSicherheit im Standardmodell

Agenda

Grundlagen

Zertifikatlose Public-Key Kryptographie

Sicherheit im Standardmodell

• Zertifikatbasierte Verschlüsselung (CBE)• Identitätsbasierte Verschlüsselung (IBE)• Eigenschaften

• Kommunikationsmodell• Aufbau• Angriffsmodell

• Grundsätzliche Problematik• Folgerungen & Lösungsmöglichkeiten

Generische Konstruktionsmechanismen



Zertifikatbasierte Verschlüsselung (CBE)Identitätsbasierte Verschlüsselung (IBE)Eigenschaften IBE

Grundlagen

Zertifikatbasierte Public-Key Kryptographie

Alice Bob

Zertifizierungsstelle

Schlüsselverzeichnis Public-K

ey pk

pk

Cert = Sign(pk,id)

CertBob

…CertBob

SK

Vertra

uen

(funk

tiona

l) Vertrauen (funktional)

Public-Key




Grundlagen

Zertifikatbasierte Public-Key Kryptographie

Nachteile:

• Public-Key Infrastruktur muss vorhanden sein (Zertifizierungsstellen, Rückruf von Zertifikaten, …)• Sender obliegt die Überprüfung des Zertifikates (bei Low-End mobilen Geräten eventuell zu aufwändig)

Idee (1985, Shamir):Sender kann sich zu beliebigem Empfänger den öffentlichen Schlüssel selbst bestimmen! Keine Public-Key Infrastruktur mehr nötig


Berechnung…



Identitätsbasierte Public-Key Kryptographie

Alice Bob

[email protected]

Private-Key-Generator (PKG)

Vertra

uen

(bed

ingun

gslos

) Vertrauen (bedingungslos)

Public-Key

PKBob

sk Private-K

ey-Extract sk




Grundlagen


Ein IBE-Verschlüsselungsschema besteht aus vier randomisierten Algorithmen:

Setup(k): Systemparameter und Schlüsselerzeugunggeheimer Masterschlüsse masterkey

Private-Key-Extract(ID): Erzeugung des privaten Schlüssels einer Identität

Encrypt(m, ID): Verschlüsselt eine Nachricht m für eine Identität

Decrypt(sk,c): Entschlüsselt eine Nachticht c mit dem durch Private-Key-Extract erhaltenen privaten Schlüssel sk.


Solver



Grundlagen - IBE

KeyGen

Sim1

Challenge-Creator

Sim2

Angreifer

A1

A2

Öffentlicher Schlüssel des PKG

Orakelanfragen

Orakelanfragen

ID, m0, m1

Encrypt(mb,ID)

Probleminstanz

Lösung

}1,0{b

Setup

Angriffsphase I

Challenge

Angriffsphase II

Ratephase

Private-Key-Extract( ID)Decrypt( ID, C )




Grundlagen


Zentraler Nachteil:

• Der Private-Key Generator kann sich die privaten Schlüssel zu jedem Nutzer erzeugen

Ein erstes praktikables IBE-Verschlüsselungsschema wurde erst im Jahr 2001 von Boneh & Franklin vorgestellt (basierend auf Paarungen).

Idee (2003, Al-Riyami)Entwicklung von Verschlüsselungsverfahren mit den gemeinsamen Vorteilen von CBE (keine Schlüsselhinterlegung) und IBE (keine PKI nötig).


SK

PK


KommunikationsmodellAufbauAngriffsmodell


Berechnung…

Alice Bob

[email protected]

Key-Generation-Center (KGC)

Vertra

uen

(funk

tiona

l) Vertrauen (funktional)

Public-Key

PKKGC

Schlüsselverzeichnis…

PKBob

…PKBob

SKBob

Partial-P

rivate-Key-E

xtract

SKKGC


Definition CLE

Ein CLE-Verschlüsselungsschema besteht aus sieben randomisierten Algorithmen:

(1) Setup(k): Systemparameter und Schlüsselerzeugunggeheimer Masterschlüssel masterkey

(2) Partial-Private-Key-Extract(ID): Erzeugung des privaten Schlüssels einer Identität

(3) Encrypt(m, pk): Verschlüsselt eine Nachricht m für eine Identität

(4) Decrypt(sk,c): Entschlüsselt eine Nachticht c mit dem durch Private-Key-Extract erhaltenen privaten Schlüssel sk.




Definition CLE (2)

Ein CLE-Verschlüsselungsschema besteht aus sieben randomisierten Algorithmen:



(5) Set-Secret-Value(ID):Benutzer: privates Geheimnis x auswählen

(6) Set-Public-Key(x):Benutzer: eigenen öffentlichen Schlüssel berechnen(basiert nur auf dem privaten Geheimnis)

(7) Set-Secret-Key(x,Partial-Private-Key-Extract[ID]):Benutzer: eignen (vollständigen) privaten Schlüsselberechnen


Angriffsszenarien

2 mögliche Angriffsszenarien:



(1) Eine böswillige dritte (externe) Partei darf die Sicherheit nicht kompromittieren können

(2) Ein bösartiges KGC aber auch nicht! (…im Gegensatz zur IBE) (diese kennt den masterkey)

Zwei verschiedene Angreifer AI und AII mit verschiedene Fähigkeiten müssen modelliert werden

Definition:Ein CLE-System heißt sicher, wenn es sowohl gegenüber einem Angreifer AI als auch gegenüber einem Angreifer AII sicher ist.


Angriffsmodell



Solver

KeyGen

Sim1

Challenge-Creator

Sim2

Angreifer

A1

A2

Öffentlicher Schlüssel des KGC

Orakelanfragen

Orakelanfragen

PK, ID, m0, m1

Encrypt(mb,ID)

Probleminstanz

Lösung

}1,0{b

Setup

Angriffsphase I

Challenge

Angriffsphase II

Ratephase

Private-Key-Extract ( ID, PK ) Partial-Private-Key-Extract ( ID )Request-Public-Key( ID )Decrypt( ID, PK, C )


2 mögliche Typen von Angreifern

GrundlagenZertifikatlose Verschlüsselung (CLE)

CLE: Sicherheit im Standardmodell


TYP I: AI („externer“ Angreifer, keinen Zugriff auf masterkey des KGC)

TYP II: AII („interner“ Angreifer, Zugriff auf masterkey des KGC)

Zugriff auf alle Orakelanfragen, „übliche Einschränkungen“

Zugriff auf alle Orakelanfragen, „übliche Einschränkungen“Kann mit masterkey den KGC-Anteil des Schlüssels bestimmen Einschränkung: kann öffentliche Schlüssel im Schlüsselverzeichnis nicht austauschen


Grundsätzliche Problematik



ProblematikLösungsansätze

Aktuelle Situation:

• es existieren Schemas mit Sicherheitsbeweisen im Zufallsorakelmodell (Al-Riyami u.a.)

• Prolematisch: Black-Box Beweise

Kern des Problems:

„Schema sicher gegen Typ I Schema unsicher gegen Typ II“ (Typ I Entschlüsselungs-Simulator ist Typ II Angreifer)


Konstruktion des Typ I – Angreifers AI




1. Erhalte öffentlichen Schlüssel PKKGC des KGC

2. Wähle Identität ID, wähle zufälligen geheimen Wert xID sowie einen öffentlichen Schlüssel PKID

3. Wähle zwei Nachrichten m0 und m1

4. Verschlüssele mb (b zufällig) unter ID, PKKGC und PKID erhalte C

5. Entschlüssle C mit Entschlüsselungsorakel

6. Gebe (ID, PKID, m0, m1) aus

Angreifer „weiß“ was der Simulator ihm auf die Entschlüsselungsanfrage antworten muss (mb)

Nutze diese Eigenschaft um einen Typ-II Angreifer zu konstruieren


Konstruktion des Typ II – Angreifers AII




1. Erhalte öffentlichen Schlüssel PKKGC und privaten Schlüssel SKKGC des KGC

2. Wähle Identität ID

3. Wähle zwei unterschiedliche Nachrichten m0 und m1, gebe sie und ID aus

A1II

1. Erhalte Challenge Chiffretext C*

2. Frage PKID ab

3. Initialisiere Sim1 (mit PKKGC und SKKGC) und nutze Entschlüsselungsorakel zum Entschlüsseln von C*

A2II

Angreifer II mit überwältigender Wahrscheinlichkeit erfolgreich


Problematik




Angreifer I kann mehr (Entschlüsselung nach Austausch des öffentlichen Schlüssels) als Angreifer II.

Eigentlich unrealistische Annahme

Verschiedene „Lösungsmöglichkeiten“…

Grundsätzliche Prolematik oder nur beweistechnische Problematik?

Vermutlich nur Beweistechnische Problematik – keine Grundsätzliche („Observational/Black-Box Proofs“) [Dent/Kudla, 2005]


Lösungsansätze




Vorschläge [Dent/Kudla, 2005]

• Abschwächung des Angriffsmodells (Keine Entschlüsslungsanfragen zu ausgetauschten Schlüsseln, „unrealistische Annahme“)

• Sim1 umkonstruieren (z.B. zusätzliche Initialparameter) damit AII ihn nicht nutzen kann

• Andere Beweistechniken versuchen (Game hopping, neue entwickeln, …)

• Black-Box des Angreifers öffnen, (nicht so, dass die Nachteile des Zufallsorakelmodells entstehen)




Generische Konstruktionsmethoden

Idee: Konstruktion eines zertifikatlosen Kryptosystems aus einem identitätsbasierten und einem PK Kryptosystem

Sei f die Verschlüsselungsfunktion eines IBE-Schemas, g die Verschlüsselungsfunktion eines PK Schemas. Sei m eine Nachricht.

(1) Dann ist die Verschlüsselungsfunktion h = f(g(m)) die Verschlüsselungsfunktion eines CL-Schemas.

(2) Sei x zufällig gewählt. x‘ = x+m, „+“ geeignet, dann ist die Verschlüsselungsfunktion

die Verschlüsselungsfunktion eines CL-Schemas.

))(),'((' xgxfh

Satz: Seien f ein IND-ID-CCA2 sicheres IBE-Schema und g ein ID-CCA2 sicheres PK-Schema. Dann sind h und h‘ die Verschlüsselungfunktion eines IND-CL-CCA2 sicheren CLE-Schemas.

Ewan Fleischmann Zertifikatlose Public-Key KryptographieEwan Fleischmann

E N D E


Documents

Ewan FleischmannZertifikatlose Public-Key Kryptographie Sicherheitsbeweise für zertifikatlose Public-Key Schemata Ewan Fleischmann Kryptowochenende 2006