Home

Konzepte für eine sichere Schlüsselverwaltung

1. sign Partia Signature decrypt PartiaiDecryption publicKey PublicKey AbstraciPrivateKey Share AbstractPrivateKeyShare getPublicKey PublicKey getKeyAlgorithm String getidentifier byte getThreshold int getShareNumberint sharesSecret boolean combine bytel equals boolean getAlgorithm String getFormat String getEncoded byte getVerificationKey Publickey AbstractPartialSignature interface PartiaiDecryption algorithm String AbstractPartiaiDecryption AbstractPartialDecryption getAlgorithm String getldentifier byte getThreshold int getshareNumberint sharesSecretboolean getEncoded bytel share KeyShare combine byte combine bytel combine byte combine bytel PKCS7 makeDummyCertificateX509Certj encrypt byte makeDummyCertificate X509Cert encrypt byte sign byte decrypt byte combineSignedCertificateX509C sign byte combineSignedData SignedData PartialSignerlnfo PartiallyDecryptedEnvelopedData SimpleElGamalPrivateKeyShare RedundantElGamalPrivateKeyS ShoupRSAPrivateKeyShare FGMY RSAPrivateKeyShare SimpleRSAPrivateKeyShare SimpleElGamalPrivateKeyShare share SimpleElGamalPrivateKe RedundantElGamalPrivateKeySh share RedundantElGamalPrivate ShoupRSAPrivateKeyShare share ShoupRSAPrivateKeyShar FGMY_RSAPrivateKeyShare share FGMY_RSAPrivateKeyShar SimpleRS
2. PartialSignerlnfo PartiallyDecryptedEnvelopedData SimpleRSAPrivateKeyShare RedundantElGamalPrivateKeyS RedundantElGamalPrivateKeySha share RedundantElGamalPrivate ShoupRSAPrivateKeyShare ShoupRSAPrivateKeyShare share ShoupRSAPrivateKeyShare FGMY_RSAPrivateKeyShare share FGMY RSAPrivateKeyShard SimpleRSAPrivateKeyShare share SimpleRSAPrivateKeyShard sign PartialSignature decrypt PartialDecryption sign PartialSignature decrypt PartialDecryption PartialEIGamalDecryption PartialRSASignature PartialRSADecryption sign PartialSignature decrypt PartialDecryption getPsLL2H BigInteger PartialRSASignature PartialRSADecryption Abbildung 5 2 Key Sharing Basisklassen aus dem Paket keyshare 52 sign PartialSignature decrypt PartialDecryption PartialRSASignature PartialRSADecryption ist PrivateKeyShare diese Schnittstelle erweitert KeyShare und gleichzeitig die JCA Schnittstelle PrivateKey um Methoden mit denen der zugeh rige ffentliche Schl ssel eines Schl sselanteils erfragt werden sowie Teilsigna turen und Teilentschl sselungen f r ein zu bergebendes Byte Array er zeugt werden k nnen AbstractPrivateKeyShare diese abstrakte Klasse stellt Default Implementie rungen f r die Methoden eines PrivateKeyShare bereit und dient damit zur Vermeidung von Code Duplikaten Insbesondere implementiert sie ei ne Kodierung von Schl sselanteilen im PK
3. JET und Interpolationsstellen d f i auf die Teilnehmer verteilt Wir erkennen daB dieses Polynom ber den ganzen Zahlen und nicht in einer Restklasse ausgewertet wird und alle Interpolationsstellen d Vielfache von L sind d Schl sselverwendung Um gemeinsam s m mod N zu berechnen be stimmt jeder Teilnehmer 7 A seinen Anteil s m mod N mit AA II ie IE A i Auferund der Konstruktion der d sind hierf r keine Invertierungen notwendig Es ergibt sich SA 1 s m si mP Zi diria ml m mod N ie F r den letzten Schritt in dem die partiellen Berechnungsergebnisse kombi nert werden ist eine weitere Exponentiation m notwendig Hierzu schlagen die Autoren des Verfahrens vor da einer der Teilnehmer m berechnet und zusammen mit seiner Teilberechnung m an den Kombinierer bermittelt MSYO00 Eine Alternative hierzu besteht darin da einer der Teilnehmer zum Beispiel derjenige mit der kleinsten Teilnehmernummer anstelle von m direkt mP ermittelt und weitergibt Dann kann der Kombinierer wie im Verfahren aus Abschnitt 3 4 einfach die Anteile zusammenmultiplizieren In jedem Fall sind weder m noch P geheime Informationen und folglich k nnte der Kombi nierer den Korrekturfaktor m auch selbst berechnen 24 3 5 2 Fine Variante des Verfahrens Das im vorigen Abschnitt geschilderte Verfahren hat einige Nachteile die wir hier diskutieren wollen Abschlie end stellen wir
4. Konzepte fiir eine sichere Schliisselverwaltung Thilo Planz Juni 2002 Diplomarbeit am Lehrstuhl fiir Theoretische Informatik der Technischen Universitat Darmstadt Prof Dr J Buchmann Betreuer Alexander Wiesmaier ITU Darmstadt Fachbereich Informatik Matrikelnr 547479 mail to planz epost de Ehrenw rtliche Erkl rung Hiermit versichere ich die vorliegende Diplomarbeit ohne Hilfe Dritter und nur mit den angegebenen Quellen und Hilfsmitteln angefertigt zu haben Alle Stel len die aus den Quellen entnommen wurden sind als solche kenntlich gemacht worden Diese Arbeit hat in gleicher oder hnlicher Form noch keiner Pr fungs beh rde vorgelegen Darmstadt den 5 Juni 2002 Thilo Planz planz epost de Vorwort Die vorliegende Arbeit ist Teil des umfangreichen FlexiTrust Projekts welches die Entwicklung einer leistungsf higen Trustcenter Software zum Ziel hat Mei ne Arbeit entstand aus dem Wunsch heraus diese Software um M glichkeiten der sicheren Verwaltung des Signaturschliissels der Zertifizierungsinstanz sowie der sicheren Verwahrung von Benutzerschliisseln zu erg nzen Auch wenn ich mich nicht auf diese beiden Problemstellungen beschr nkt habe habe ich mich bem ht sie nicht aus den Augen zu verlieren Das vorliegende Dokument ist nur ein Teil meiner Diplomarbeit die zum grofen Teil auch aus der konkreten Umsetzung der hier geschilderten Verfah ren in Form einer Programmierarbeit bestand Diese Impl
5. p g A zu verschl sseln w hlt der Absender eine Zufallszahl ber 1 p 2 und berechnet B g mod p Anschlie end wird die Nachricht als Zahl zwischen 1 und p 1 interpretiert und es ergibt sich der Schliisseltext B c mit c Am mod p Der Empf nger kann die Nachricht unter Verwendung seines geheimen Expo nenten a entschliisseln Brite B gh Abm g g m m mod p Genau wie bei der RSA Verschliisselung wird man lange Nachrichten zun chst symmetrisch verschliisseln und nur den symmetrischen Schl ssel mit ElGamal bermitteln Im Gegensatz zu RSA ist die ElGamal Verschl sselung durch die Wahl von b randomisiert so daB ein Padding mit Zufallszahlen nicht notwen dig ist die Sicherheit des Verfahrens beruht brigens darauf da bei jeder Verschliisselung ein neues b gew hlt wird Um eine Signatur fiir die Nachricht m zu erzeugen benutzt der Absender mit dem privaten Schl ssel p g a eine kryptographische Hashfunktion die die Nachricht auf einen Wert h m zwischen 1 und p 2 abbildet Anschlie end w hlt er eine Zufallszahl k er 1 p 2 mit ggT k p 1 1 und berechnet das Inverse k von k modulo p 1 sowie r g mod p und s k h x ar mod p 1 Die Signatur ist das Paar r s Bei der Verifikation kann mit dem ffentlichen Schl ssel p g A berpr ft werden ob gilt Ars g mod p In diesem Fall handelt es sich um eine giltige Signatur denn Ars gar qkk h z ar ge
6. 4 3 wiederherstellbare Schl ssel Eine interessante M glichkeit private Schl ssel zur ckzugewinnen erh lt man durch das Einbetten dazu ausreichender Informationen in den ffentlichen Teil des Schl ssels Hierzu verwendet man spezielle Schl sselgeneratoren die bei der Erzeugung der Schl sselpaare daf r sorgen da Recovery Operatoren und nur diese zu einem sp teren Zeitpunkt aus dem ffentlichen Schl ssel den privaten errechnen k nnen Da ffentliche Schl ssel vielfach repliziert gespeichert wer den besteht erstens keine Notwendigkeit ein zus tzliches Archiv zu f hren und zweitens kein Risiko diese Daten zu verlieren Andererseits er ffnen die im fol genden geschilderten Verfahren neue Angriffswege auf die Sicherheit der Benut zerschl ssel denn die eingebaute Hintert r f r das Key Recovery k nnte mi braucht werden Die dazu notwendigen Daten sind in den ffentlichen Schl sseln und dem Schl sselgenerator enthalten und damit weniger gut gesch tzt als in einem Archiv eines Trustcenters es wird nat rlich weiterhin eine private Infor mation der Recovery Operatoren ben tigt Wir wollen in diesem Abschnitt einige M glichkeiten aufzeigen wie Schl ssel generatoren gestaltet werden k nnen die scheinbar ganz normale Schl sselpaare erzeugen gleichzeitig aber eine Hintert r vorsehen die es dem Hersteller des Generators erm glicht den privaten Schl ssel aus dem ffentlichen abzuleiten Dabei ist es wichtig
7. Einen Teil der vorgestellten Verfahren aus den Bereichen Secret Sharing Key Sharing und Key Escrow haben wir in der Programmiersprache Java im plementiert Die Implementierung war dabei auf die Erfordernisse im Rahmen des FlexiTrust Projekts des Fachgebiets ausgerichtet In diesem Projekt wird eine Trustcenter Software entwickelt die durch diese Diplomarbeit um verteilt gespeicherte CA Schl ssel und einen Key Recovery Mechanismus f r Benutzer schl ssel erweitert werden sollte Die Dokumentation der Implementierung besteht aus drei Teilen e Einen berblick ber die Implementierung stellt dieses Kapitel der Di plomarbeit dar Hier werden die einzelnen Teile ihr Zusammenspiel so wie die bei der Programmierung getroffenen Entscheidungen erl utert UML Klassendiagramme sollen den Zugang erleichtern e In Java integriert ist eine Dokumentationsschnittstelle f r Klassenbiblio theken namens JavaDoc Hiermit lassen sich Java Klassen f r die Verwen dung in anderen Programmen dokumentieren Die von JavaDoc erzeugten sehr ansehnlichen HTML Dateien dienen damit im wesentlichen dem Anwendungsprogrammierer e JavaDoc beschreibt die Schnittstelle einer Klasse wie eine Black Box In terne Details der Programmierung werden nicht sichtbar gemacht Hier zu kann man auf den Quellcode und die dort enthaltenen Kommentare zur ckgreifen der sich im CVS Repositorium des FlexiTrust Projektes befindet 5 1 Kryptographie in Java Ein fester Bestan
8. erdem k nnen Schl ssel nicht wieder geladen werden Die Schl ssel werden automatisch mit einem geeigneten Key Sharing Verfahren auf die abh ngigen Keystores verteilt Wenn es kein solches Verfahren f r den vorliegenden Schl sseltyp gibt wird eine Ausnahme ausgel st ks setKeyEntry alias key password certificateChain 69 Keystore speichern Der KeySharer speichert die abh ngigen Keystores in tern zwischen und schreibt sie erst in ihre Dateien zuriick wenn die Methode store aufgerufen wird Der Ausgabestrom der der store Methode ber geben wird wird dabei ignoriert Das Pa wort allerdings wird zum Integrit ts schutz der abh ngigen Keystores verwendet ks store null password 5 3 5 Das Key Escrow System Das Key Escrow System besteht aus zwei unabh ngigen Komponenten Zum einen k nnen Schl sselpaare erzeugt werden aus denen zum Recovery der pri vate aus dem ffentlichen Schl ssel berechnet werden kann Hier kommen die Verfahren aus Abschnitt 4 3 zum Einsatz Auf der anderen Seite k nnen private Schl ssel in verschl sselten Dateien hinterlegt und so sp ter wiederhergestellt werden Der zweite Ansatz ist universell einsetzbar w hrend der erste nur f r bestimmte Schl ssel geeignet ist Wiederherstellbares Schl sselpaar erzeugen Um ein wiederherstellba res Schl sselpaar f r RSA oder ElGamal zu erzeugen werden entsprechende KeyPairGenerator per JCA angefordert und konfiguriert Bei der Initialisie
9. sseln anschlie end gemeinsam Private Key Operationen Signaturen Entschl sselungen durchf hren k nnen e ein Klient der eine Entschl sselung oder Signatur w nscht sich an die Teilnehmer wendet die wiederum seine Identit t und Berechtigung pr fen e die Teilnehmer bei einer solchen Anfrage eine Teilsignatur beziehungswei se entschl sselung berechnen ohne dabei untereinander oder mit jemand anderem zu kommunizieren e die Teilnehmer ihr Ergebnis an den Klienten bermitteln wobei bei Ent schl sselungen ein abh rsicherer Kanal zu w hlen ist e der Klient die Ergebnisse der Teilnehmer aufgrund lediglich ffentlicher Informationen und seiner Eingabe zu einer g ltigen Signatur oder Ent schl sselung kombinieren kann e eine gemeinsam erzeugte Signatur sich nicht von einer auf normale nicht verteilte Art entstandener Signatur unterscheiden l t Diese Modellierung zeichnet sich im wesentlichen durch zwei Merkmale aus n mlich die Existenz eines vertrauensw rdigen Gebers und die fehlende Interak tion zwischen den Teilnehmern Dies hat zur Folge da nur wenige Nachrichten w hrend des Key Sharing ausgetauscht werden m ssen und die Kommunika tion asynchron zum Beispiel per Email erfolgen kann Eine kurze Diskussion von Modellen ohne Geber findet sich in Abschnitt 3 9 Eine weitere Folge der nicht vorhandenen Interaktion ist die Unm glichkeit der Erzeugung von verteil ten Signaturen f r Verfahren die auf diskr
10. abzulegen anhand derer Signaturen auf Benutzerzertifikaten berpr ft werden sollen Durch das Integrit tspa wort wird sichergestellt da nicht unbemerkt Zertifikate entfernt oder installiert werden k nnen 5 1 3 Algorithmen F r die verschiedenen kryptographischen Operationen sind jeweils eigene Klas sen vorgesehen die vom Programmierer mit einer getInstance Methode ak tiviert werden k nnen Die Implementierung wird dabei erst zur Laufzeit aus gew hlt und dynamisch geladen Auf diese Weise wird eine Java Anwendung von den unterschiedlichen Algorithmen und den Bibliotheken in denen die se bereit gestellt werden entkoppelt Beispielsweise wird eine MD5withRSA Signatur gem JCA wie folgt erzeugt Signature signer Signature getInstance MD5withRSA signer initSign PrivateKey privateKey signer update byte message byte signature signer sign 46 Um den Signaturalgorithmus auszutauschen mu lediglich ein anderer Algo rithmenname angegeben werden Kann kein Algorithmus mit diesem Namen ge funden werden hat dies eine NoSuchAlgorithmException zur Folge Nat rlich m ssen die verwendeten Schl ssel zu den Algorithmen passen Ist dies nicht der Fall wird ebenfalls eine entsprechene Exception ausgel st Mit JCA ist es m glich mehrere Kryptographie Bibliotheken sogenann te Service Provider nebeneinander zu verwenden An welchen der installierten Provider der Anruf von getInstance weitergereich
11. anderen Verfahren lediglich berechnungssicher computationally secure was bedeutet da ihre Sicherheit auf einem hoffentlich schwierig zu l senden mathematischen Problem beruht Praktische Einsetzbarkeit Die Sicherheit des One Time Pad Verfahrens beruht auf der Zuf lligkeit des Schliissels Wenn er nicht wirklich zuf llig erzeugt wurde sondern durch einen Algorithmus einen Pseudo Zufallszahlengenerator dann l t sich die Shannon Sicherheit nicht mehr beweisen Dar ber hinaus er fordert die bermittlung des Schl ssels an den Empf nger ein vorheriges Treffen oder vertrauensw rdige Boten Nicht zuletzt darf der Schl ssel nur ein einziges Mal benutzt werden Damit ist der Einsatz des eigentlich simplen Verfahrens mit gro em organisatorischen Aufwand verbunden in der Tat wurde es vor allem f r wichtige diplomatische und milit rische Mitteilungen in der ersten H lte des 20 Jahrhunderts verwendet f r die der hohe Aufwand zu rechtfertigen war 2 1 2 Die XOR Methode Wenn der Absender einer mit dem One Time Pad verschl sselten Nachricht den Schl sseltext einem Boten bergibt k nnen wir uns dies als das Aufteilen der Nachricht auf zwei Personen vorstellen den Boten und den Empf nger Der Bote besitzt die verschl sselte Nachricht und der Empf nger das zugeh rige One Time Pad Solange die beiden nicht zusammenarbeiten was blicherweise darin besteht da der Bote den Schl sseltext an den Empf nger bergibt kann ke
12. athe gm mod p 30 3 8 ElGamal Key Sharing Wie wir gesehen haben sind ElGamal Verschliisselungen und Signaturen ran domisierte Berechnungen in die jeweils eine Zufallszahl eingeht Die Verschliisse lung ist eine Public Key Operation so da ein Key Sharing auf sie keinen Ein fluB hat Zur Signatur allerdings wird der private Schl ssel beziehungswei se die privaten Schl sselteile ben tigt so da die Erzeuger der Teilsignatu ren untereinander kommunizieren m ssen um sich auf die Zufallszahl zu ei nigen Da wir uns in dieser Arbeit nur mit Protokollen besch ftigen wollen die keine Interaktion der Teilnehmer erforderlich machen werden wir verteilte ElGamal Signaturen und andere davon abgeleitete Signaturen beispielsweise DSA nicht besprechen und verweisen auf die Literatur GJKR96 Genau wie beim nicht redundanten RSA Key Sharing ist es sehr einfach m glich den geheimen Exponenten a in beliebig viele Summanden a mit gt gt a a mod p 1 zu zerlegen die dann unabh ngig voneinander zur Berechnung von Teilentschl sselungen verwendet werden k nnen B B mod p und cl B Be m mod p Beim Versuch das Shamir Verfahren direkt auf ElGamal Exponenten zu bertragen st t man wie beim RSA Verfahren erneut auf das Problem da sich die Exponenten in einer nicht primen Restgruppe bewegen in diesem Fall Z p 1 Z die Ordnung dieser Gruppe mu zwar im Gegensatz zum RSA Verfahren nicht gehei
13. d aix a 12 mod p 1 g 1 und dessen Interpolationsstellen di f i mod p 1 q 1 auf mehrere RSA Teilschl ssel d N zu verteilen Dann k nnte man genau wie im vorigen Abschnitt RSA Teilberechnungen mit den Teilschl sseln ausf hren und anschlieBend durch Multiplikation zum Gesamtergebnis kombinieren um 22 d mod N zu berechnen bestimmt jeder Teilnehmer A gemeinsam s m seinen Anteil s m iA mod N mit Ma I 7 mod p 1 4 1 Ie A i und es ergibt sich s I m mod N 1EA Diese Vorgehensweise scheitert allerdings an der Berechnung der Interpola tionskoeffizienten A a da hierzu Invertierungen von i modulo p 1 q 1 notwendig sind die Primzahlen p und q jedoch niemandem bekannt sein diirfen da darauf die Sicherheit des RSA Schliissels beruht des weiteren sind auch nicht alle i invertierbar beispielsweise sind es s mtliche geraden Differenzen nicht Schl sselerzeugung Das Problem l t sich jedoch durch geeignete Modi fikationen des Polynoms beheben FGPY97 MSY00 Durch die Hinzunahme von hinreichend gro en Faktoren k nnen die Berechnungen der Koeffizienten durch normale Ganzzahldivisionen geleistet werden so da Invertierungen in der Exponentengruppe unbekannter Ordnung nicht notwendig sind Der Faktor durch den anschlie end alle Teilexponenten ohne Rest dividier bar sein m ssen h ngt von der Anzahl n der Teilnehmer ab Sei L n 1
14. geheimen Exponenten a aus 1 q 1 und berechnet den ffentlichen Schl ssel p q g A mit A g mod p 31 Die geheimen Teilexponenten a fiir die Teilnehmer werden gem f dem Shamir Verfahren durch ein Polynom f x ber Z qZ erzeugt f z a fist feirt mod q mit fi ER 0 q 1 und Qi f i Schliisselverwendung Um eine Nachricht m f r den Empf nger mit dem ffentlichen Schl ssel p q g A zu verschl sseln w hlt der Absender eine Zu fallszahl ber 1 q 1 und berechnet B g mod p Anschlie end wird die Nachricht als Zahl zwischen 1 und p 1 interpretiert und es ergibt sich der Schl sseltext B c mit c A m mod p Um gemeinsam m B9 c mod p zu berechnen bestimmt jeder Teil nehmer i A seinen Anteil B c mod p und die Anteile k nnen dann kombiniert werden um die Nachricht zu ent schl sseln m Bc II Be mod p iE A mit MA I mod 9 IE A i Die notwendigen Invertierungen zur Berechnung von A a sind nicht schwierig da der Modul q sowohl prim als auch ffentlich bekannt ist Wie wir bereits angek ndigt haben gehen wir auf die Erzeugung verteilter Signaturen aufgrund der Notwendigkeit hierbei zu interagieren nicht weiter ein 3 9 verteilte Schliisselerzeugung In dem von uns verwendeten Modell fiir Key Sharing siehe Abschnitt 3 2 be steht die gr te Schwachstelle in der Existenz eines vertrauensw rdigen Gebers D
15. h chstens so schwierig wie das Faktorisierungsproblem Da sich Mathematiker in den letzten 3000 Jahren vergeblich bemiiht haben einen effizienten Algorithmus zum Fak torisieren zu finden kann man vermuten daf dies wirklich schwierig ist Das Hauptproblem der RSA Annahme hingegen ist es da es eventuell eine ande re M glichkeit gibt das RSA Problem zu l sen als N zu faktorisieren Selbst wenn das Faktorisierungsproblem schwer bleibt k nnte RSA somit gebrochen werden Zwar ist kein solcher Algorithmus bisher bekannt aber es konnte im Gegensatz zum verwandten Rabin Problem auch nicht bewiesen werden da es keinen geben kann Schl sselerzeugung Um ein RSA Schl sselpaar zu erzeugen bestimmt der Schl sselgenerator zun chst zwei zuf llige Primzahlen p und q Daraus ergibt sich der ffentliche Modul N pq Die Gr e L nge der Bitdarstellung von N bestimmt die Sicherheit des Verfahrens und den Berechnungsaufwand Zur Zeit gilt 1024 bit RSA als hinreichend sicher f r die meisten Anwendungen 2048 bit RSA wird f r extrem kritische Schl ssel gefordert Demnach haben p und q jeweils mindestens 512 Bit sie sollten gleich gro sein Als n chstes w hlt der Generator einen ffentlichen Exponenten e mit ggT e p 1 q 1 1 Au er dieser Bedingung mu e keine weiteren Eigenschaften besitzen Aus Si cherheitsgr nden Low Exponent Attacke sollte e nicht zu klein sein aber an sonsten kann es zur Beschleunigung von P
16. hen da alle Parameter vom Schl sselgenerator frei bestimmt werden k nnen Dadurch wird es m glich den geheimen Exponenten a mit einem ElGamal Backup Schl ssel zu B c zu verschl sseln und diese beiden Werte in den Pa rametern p und g zu verstecken Young und Yung YY96 geben dar ber hinaus auch zwei Algorithmen an die mit einem vorgegebenen p oder einem vorgege benen g arbeiten k nnen Der Schl sselgenerator enth lt den Backup Schl ssel pr gr Ar Als erstes erzeugt er den zuf lligen Exponenten a Dieser Wert wird mit dem Backup Schl ssel und einem zuf lligen k zu B c 9 Aba mod pr verschl sselt Falls m glich setzt er die Parameter p und g des zu erzeugenden Schl ssels als p c und g B Hierzu mu c eine Primzahl sein c 1 sollte au erdem einen gro en Primfaktor haben uns es mu gelten a lt c und B lt c Ist dies nicht der Fall wird die Verschl sselung mit einem neuen k wiederholt Young und Yung fordern nicht da g tats chlich die gesamte Gruppe Z pZ erzeugt obwohl dies im ElGamal Verfahren eigentlich vorgesehen ist Der letzte Parameter A g mod p ergibt sich abschlie end aus p g und a Zum Key Recovery werden die Parameter g und p des ffentlichen Schl ssels einfach als ElGamal Chiffretext aufgefa t und mit dem Recovery Schl ssel zu a entschl sselt 43 Kapitel 5 Implementierung Der Worte sind genug wechselt la t mich auch endlich Taten sehen aus Goethes Faust
17. mod N zu erzeugen die dann durch Multiplikationen zum Gesamtergebnis kombiniert werden k nnen s m mod N und s 5 m m2 m mod N Wir bemerken hierzu da die Teilberechnungen sich au er durch den Wert des Exponenten nicht von einer normalen RSA Berechnung unterscheiden und da zur Kombination der Teilergebnisse durch Multiplikation modulo N keine geheimen Informationen notwendig sind 3 5 Redundantes RSA Key Sharing Wie wir im vorigen Abschnitt gesehen haben erlauben die mathematischen Eigenschaften eines RSA Schliissels ihn auf recht einfache Weise in eine be liebige Anzahl von Schliisselanteilen zu zerlegen die unabh ngig voneinander zum Erzeugen von Teilergebnissen verwendet werden k nnen aus denen dann das Ergebnis der privaten RSA Operation abgeleitet werden kann ohne da der eigentliche Schl ssel jemals rekonstruiert werden mu Da das geschilderte Verfahren jedoch stets alle Teilschl ssel ben tigt bricht es bereits beim Verlust eines einzigen dieser Teile zusammen In diesem Abschnitt wollen wir zeigen wie sich das Shamir Verfahren aus Abschnitt 2 2 1 auf RSA Teilschl ssel bert ragen l t und so ein Threshold RSA Key Sharing erm glicht 3 5 1 Verfahren von Frankel Gemmell MacKenzie und Yung Die direkteste Adaption des Shamir Verfahrens f r den Einsatz mit RSA Exponenten besteht darin da man f r ein Key Sharing versucht den geheimen Expo nenten d durch ein Polynom f z
18. rung mu der ffentliche Schl ssel des Recovery Operators angegeben werden Mit diesem werden die Informationen ber den privaten Schl ssel dann chif friert und in den ffentlichen Schl ssel eingebracht Es ist nicht notwendig da dieser Schl ssel und das erzeugte Schl sselpaar dem gleichen Algorithmus an geh ren Au erdem wird die Bitl nge des zu erzeugenden Schl ssels angegeben Hierbei ist darauf zu achten da sie gro genug ist um die chiffrierten Daten unterzubringen also mindestens so gro wie der Escrow Schl ssel KeyPairGenerator keygen KeyPairGenerator getInstance RSA KeySharingProvider keygen initialize new EscrowedKeyParameterSpec 1024 PublicKey escrow KeyPair pair keygen generateKeyPair privaten Schl ssel wiederherstellen F r die Schliisselwiederherstellung sieht JCA keine Schnittstelle vor Statt dessen miissen statische Methoden der entsprechenden KeyPairGenerator Klassen aufgerufen werden Dieses wird der zugeh rige ffentliche Schl ssel des gew nschten privaten Schliissels bergeben sowie das Escrow und Recovery Schl sselpaar PrivateKey recovered RSAKeyPairGenerator recover RSAPublicKey key PrivateKey recovery PublicKey escrow privaten Schliissel im Dateisystem verwahren Die Klasse FileKeyEscrow speichert die ihr bergebenen Schl ssel als chiffrierte PKCS7 Dateien in einem Verzeichnis im Dateisystem ab Die Schl ssel werden dabei durch die Ausstel ler und
19. sein wenn ein versehentliches berschreiben der Anteile durch eine Art Nur Lesen Modus verhindert werden soll oder wenn die Anteile neu erzeugt werden sollen ohne zuvor die eventuell nicht existen ten Dateien einzulesen Die Einstellung INTERACTIVE aktiviert die graphische Benutzeroberfl che bei jedem Lade und Speichervorgang Auf diese Weise kann der Benutzer die Dateien ausw hlen Instanz erzeugen KeyStore ks KeyStore getInstance ShamirStore 67 Keystore laden Der ShamirStore setzt sich aus den in der Konfigurations datei bezeichneten Anteilen zusammen wenn seine load Methode aufgerufen wird Die Konfigurationsdatei muf ihm ber den InputStream dieser Metho de zugef hrt werden Ein ebenfalls angegebenes Pa wort wird dazu verwendet die Integrit t der KeyStore Datei die sich aus den Anteilen ergibt zu pr fen Dies ist zu unterscheiden von dem Integrit tspa worts f r die einzelnen Anteile welches in der XML Datei angegeben werden kann FileInputStream in new FileInputStream configuration xml ks load in password in close Wenn das Laden aufgrund fehlender oder fehlerhafter Anteile fehlschl gt wird eine IOException geworfen Keystore verwenden Der ShamirStore verwendet intern einen normalen JavaKeyStore an den er alle Anfragen weiterreicht Daher reagiert er genau so wie man es von einem solchen erwarten w rde Unter anderem kann man einen Schl ssel mit einem Alias versehen pa wortgesch tzt
20. signer Signature getInstance DistributedMD5withRSA signer initSign keyshare signer update message byte partialSignature signer sign Da die erzeugten Instanzen von KeyShare fiir alle unterstiitzten Arten von java security PrivateKey selbst die Schnittstelle PrivateKey implementie ren k nnen die Teilberechnungen JCA konform ber java security Signature und javax crypto Cipher erstellt werden Hierzu m ssen die entsprechenden Implementierungen des keyshare jca Provider verwendet werden der folg lich im Laufzeitsystem registriert werden sollte Implementiert sind die Signa turen DistributedMD5withRSA DistributedSHAlwithRSA sowie die Chiffren DistributedRSA und DistributedElGamal Teilberechnungen zusammenf hren public static byte combine byte shares byte message throws NoSuchAlgorithmException SecretSharingException 66 Die Teiberechnungen k nnen direkt als zwei dimensionales Bytefeld bergeben werden Der zweite Parameter message kann bei Signaturen verwendet werden um die entstandene Signatur automatisch zu verifizieren Bei Entschliisselungen wird er nicht ausgewertet Wenn die Kombination aufgrund fehlerhafter Ein gaben nicht rekonstruiert werden konnte wird eine SecretSharingException ausgel st wenn die Verifikations Funktion fiir Signaturen fehlt gibt es eine NoSuchAlgorithmException 5 3 3 Der Shamir KeyStore Der ShamirStore ist ein spezieller KeyStore der seinen Inhalt automatis
21. AKeyPairGenerator StrongRSAPrivateCrtKey ElGamalPrivateKey KeyFactorySpi ExtendedElGamalPrivateKey KeyFactory ExtendedElGamalPrivateKey engineGeneratePublic Publickey engineGeneratePrivate PrivateKe q Biginteger FengineGetKeySpec KeySpec encoded bytel engineTranslateKey Key Provider initialize void StrongRSAPrivateCrikey generateKeyPair KeyPair publicExponent BigInteger primeP Biglnteger prime BigInteger primeP1 BigInteger prime 1 BigInteger primeExponentP Biglnteger primeExponent Biginteger crtCoefficient Biglnteger privateExponent Biglnteger modulus Biglnteger algorithm String format String encoded hyte 83 KeyStoreSpi Key StoreBase FmakekeyStore void FloadKeyStore void FloadKeyStore void FgetEncodedKeyStore bytel encodeKeyStore void engineAliases Enumeration engineContainsAlias boolean engineDeleteEntry void engineGetCertificate Certificate engineGetCertificateAlias String engineGetCertificateChain Certifid engineGetCreationDate Date engineGetkey Key enginelsCertificateEntry boolean enginelsKeyEntry boolean engineSetCertificateEntry void engineSetkeyEntry void engineSetkKeyEntry void engineSize int engineload void engineLoad void engineSetKeyEntryvoid engineStore void engineStore void share PrivateKeyll 84 Share KeySharer ShamirStore ShareSelector Load ShareSelector Store IntegrityPassword CancelFinishedBut
22. APrivateKeyShare share SimpleRSAPrivateKeyShari sign PartialSignature decryptPartialDecryption sign PartialSignature decrypt PartialDecryption sign PartialSignature decrypt PartialDecryption FsplitElGamalCipherText Biglnte PartialElGamalDecryption PartialElGamalDecryption 82 PartialRSASignature PartialRSADecryption sign PartialSignature decrypt PartialDecryption getPsl L2H Biglnteger PartialRSASignature PartialRSADecryption sign PartialSignature decrypt PartialDecryption PartialRSASignature PartialRSADecryption SignatureSpi E CipherSpi SignatureBase CipherBase enginelnitverityvoid engineSetMode void FenginelnitSign void engineSetPadding void engineUpdate void engineGetBlockSize int FengineUpdate woid engineGetOutputSize int engineSign byte tengineGetlV hyte engineVerify boolean engineGetParameters Algorith engineSetParameter void enginelnitvoid engineGetParameter Object enginelnitvoid enginelnitvoid signatureAlgorithmName Strin engineUpdate byte engineUpdate int engineDoFinal byte engineDoFinal int cipherAlgorithmName String MD5withRSA SHA1withRSA signatureAlgorithmName Strin signatureAlgorithmName Strin RSAPKCS1 v1 5 ElGamal cipherAlgorithmName String cipherAlgorithmName String java security Provider KeyPairGeneratorSpi RSAPrivateCrtkey Provider StrongRS
23. CA vorgegebene hinaus ist damit nicht m glich Unterpaket keyshare keystore gui Der ShamirStore verf gt ber eine gra phische Benutzeroberfl che mit dessen Hilfe er den Benutzer fragen kann in welche Dateien die Anteile geschrieben beziehungsweise aus welchen Dateien sie gelesen werden sollen Diese Oberfl che wurde mit dem Java eigenen Swing Framework implementiert und befindet sich im Paket keyshare keystore gui ShareSelector Load diese von JFrame abgeleitete Klasse implementiert ein Fenster in dem der Benutzer die vorgegebene Zahl an Dateien zur Rekon struktion des ShamirStore ausw hlen und anhand des Integrit tspa worts berpr fen kann ShareSelector_Store diese von JFrame abgeleitete Klasse bringt ein Fenster auf den Bildschirm in dem der Benutzer die Anzahl der Anteile und das Integrit tspa wort einstellen kann und anschlie end die Zieldateien ausw hlt IntegrityPassword diese von JPanel abgeleitete Klasse stellt eine Eingabe fl che f r das Integrit tspa wort dar Sie wird von den beiden Selector Klassen verwendet CancelFinishedButton dieses JPanel beinhaltet eine Eingabefl che mit den beiden Schaltfl chen zum Abbrechen und Best tigen Sie wird von den beiden Selector Klassen verwendet 59 Select the secret shares N The keystore has been distributed using 2 out of 3 secret sharing C x Secret Share 1 threshold is 2 verified 1a share browse Share 2 missing File 2
24. CS8 Austauschformat PartialSignature diese Schnittstelle erweitert SecretShare und repr sen tiert das Teilergebnis einer verteilten Signatur Es sind Methoden vor gesehen um den Verifikationsschl ssel zu erhalten sowie den Namen des Signaturalgorithmus AbstractPartialSignature diese abstrakte Klasse stellt Default Implemen tierungen f r die Methoden einer PartialSignature bereit und dient da mit zur Vermeidung von Code Duplikaten Sie erbt dabei von AbstractSecretShare PartialDecryption diese Schnittstelle erweitert SecretShare und repr sen tiert das Teilergebnis einer verteilten Entschl sselung Es ist eine Methode vorgesehen um den Namen des Verschl sselungsalgorithmus zu erfragen AbstractPartialDecryption diese abstrakte Klasse stellt Default Implemen tierungen f r die Methoden einer PartialDecryption bereit und dient damit zur Vermeidung von Code Duplikaten SimpleRSAPrivateKeyShare diese Klasse stellt einen durch das einfache Ver fahren zum Teilen von RSA Schl sseln Abschnitt 3 4 entstandenen Teil schl ssel dar Sie enth lt auch Methoden zum Verteilen eines RSAPrivateCrtKey nach diesem Verfahren sowie innere Klassen f r die zugeh rigen PartialSignature und PartialDecryption SimpleElGamalPrivateKeyShare diese Klasse stellt einen durch das einfache Verfahren zum Teilen von ElGamal Schl sseln Abschnitt 3 8 entstan denen Teilschl ssel dar Sie enth lt auch Methoden zum Verteilen eines ElGamalPrivateKey nach
25. Disziplin der Kryptogra phie die sich mit dem Chiffrieren von Informationen besch ftigt viel Aufmerk samkeit erhalten Ihr ist es zu verdanken da mittlerweile zahlreiche Verfahren zur Verf gung stehen mit denen Daten so stark verschl sselt werden k nnen da sie ein Unbefugter auch mit enormem Rechenaufwand nicht entschl sselt kann mit denen Dokumente vor unbemerkten Ver nderungen gesch tzt werden k nnen und mit denen man Nachrichten mit einer digitalen Signatur versehen kann die eindeutig einer bestimmten Person zugeordnet werden kann Das wichtigste Problem beim Einsatz kryptographischer Verfahren besteht in der Verwaltung der daf r ben tigten Schl ssel In der traditionellen Kryp tographie mu ten sich der Sender und der Empf nger einer Nachricht vorab auf einen gemeinsamen Schl ssel verst ndigen und diesen fortan geheim hal ten Um vertrauliche Nachrichten senden zu k nnen mu te au erdem jeder Absender f r jeden Empf nger einen anderen Schl ssel vorhalten Wenn der geheime Schl ssel in die falschen H nde geriet war die Sicherheit der Kommu nikation verloren Durch das Aufkommen der Public Key Kryptographie hat sich diese Lage deutlich verbessert jetzt gab es separate Schl ssel f r Sender und Empf nger und alle Sender konnten pro Empf nger denselben Schl ssel verwenden Dieser Schl ssel mu te nicht mehr geheim gehalten werden im Ge genteil sollte er m glichst allgemein bekannt gemacht werden Das Problem d
26. FlexiCore Provider zur Verwendung von ElGamal Schl sseln mu der FlexiCore Provider installiert sein Dieser wird vom Fachgebiet Theoretische Infor matik entwickelt und ist auch doch frei erh ltlich Auch sonst empfiehlt sich dessen Verwendung da sich w hrend der Entwicklung in einigen Be reichen Probleme mit dem Provider von Sun ergaben ASN 1 Codec zum Umgang mit den ASN 1 Datenstrukturen wird das Codec Paket des Fraunhofer Instituts verwendet das mittlerweile ebenfalls vom Fachgebiet gepflegt wird XML die Verarbeitung von XML Dateien wird Castor tiberlassen einem Open Source Paket zum Transformieren von Java Klassen in unter anderem XML Kommandozeilen Parser die Kommandozeilen Applikationen verwenden die Bibliothek jargs zum Auswerten der bergebenen Parameter JUnit zum Ausfiihren der Testklassen wird das Testframework JUnit ben tigt 64 5 3 Programmierschnittstelle 5 3 1 Secret Sharing Basisfunktionalit t Die grundlegenden Secret Sharing Funktionen werden durch die statischen Me thoden der Klasse keyshare SecretSharer zug nglich gemacht Geheimnis verteilen public static SecretShare share byte secret int threshold int sharenumber throws InvalidParameterException NoSuchAlgorithmException Diese Methode erzeugt fiir das Bytefeld secret insgesamt sharenumber An teile von denen threshold zur Rekonstruktion ben tigt werden Ob dabei die XOR Methode oder das Shamir Verfahren zum Einsatz kommt wir
27. JCA SignatureSpi bereit und dient damit zur Ver meidung von Code Duplikaten Es ist vorgesehen zur Verifikation eine Signature Instanz eines anderen Providers zu kapseln und die Erzeugung einer Teilsignatur an den jeweiligen PrivateKeyShare zu delegieren MD5withRSA diese konkrete Implementierung von SignatureBase bietet ver teilte RSA Signaturen mit MD5 Hashing Die Hashfunktion und die Ve rifikation werden dabei an andere Provider delegiert m ssen also bereits vorhanden sein SHA1withRSA diese konkrete Implementierung von SignatureBase bietet ver teilte RSA Signaturen mit SHA1 Hashing Die Hashfunktion und die Ve rifikation werden dabei an andere Provider delegiert m ssen also bereits vorhanden sein CipherBase diese abstrakte Klasse stellt Default Implementierungen f r die Methoden eines JCE CipherSpi bereit und dient damit zur Vermeidung von Code Duplikaten Es ist vorgesehen zur Verschl sselung eine Cipher Instanz eines anderen Providers zu kapseln und die Erzeugung einer Teil entschl sselung an den jeweiligen PrivateKeyShare zu delegieren RSAPKCS1_v1_5 diese konkrete Implementierung von CipherBase erzeugt ver teilte RSA Entschl sselungen Es wird dabei das PKCS1 Padding in der Version 1 5 verwendet Die Verschl sselung wird dabei an andere Provider delegiert mu also bereits vorhanden sein ElGamal diese konkrete Implementierung von CipherBase erzeugt verteilte El Gamal Entschl sselungen Die Verschl sselung wird
28. Key a escrow recover X509Certificate userCert password 91 Index AbstractEscrowedKeyPairGenerator 60 AbstractPartialDecryption 53 AbstractPartialSignature 53 AbstractPrivateKeyShare 53 AbstractSecretShare 50 AbstractSecretShareWithPassword 50 access structures 14 ApplicationMode 62 AppTests 64 ASN 1 77 auto escrowing keys 40 CA 77 CancelFinishedButton 59 CipherBase 56 CommandLineApp 62 Diffie Hellman Problem 29 distinguished name 77 DN 77 Double Dispatch 51 DSA 31 ElGamal 29 Sicherheit des Verfahrens 29 ElGamal 56 ElGamalKeyPairGenerator 60 EscrowedKeyParameterSpec 60 ExtendedElGamalPrivateKey 56 FGMY_RSAPrivateKeyShare 53 FileKeyEscrow 60 FileSharer 71 FileSharer 62 Function Sharing 14 Integrit tsschutz 51 IntegrityPassword 59 92 Java Cryptography Architecture 44 JavaDoc 44 JCA 44 77 Key Escrow 35 Key Recovery 35 Key Sharing 16 ElGamal 31 Modell 17 RSA 21 22 27 KeyEscrow 74 KeyEscrow 62 KeyEscrowBase 60 KeyEscrowTests 64 KeyFactory 56 KeyShare 51 KeySharer 72 KeySharer 54 57 62 68 KeySharerTests 64 KeyStoreBase 57 Kleptographie 39 Kryptographie asymmetrisch 16 symmetrisch 8 Lagrange 10 MD5withRSA 56 One Time Pad Verschl sselung 8 Padding 21 PartialDecryption 53 PartialSignature 53 PasswordIntegrityProtected 50 PKCS 77 PKCS12 62 PKCST 54 PKCS7Tests 64 PKCS8 54 PKI 77 Polynomint
29. Recovery Systems werden betr chtliche Kosten f r Hersteller Regierung und Benutzer entstehen Zusammenfassend u ern sich die Autoren entschieden gegen jede Art von staatlich verordnetem Key Escrow Die Argumentation zielt im wesentlichen auf die Unbeherrschbarkeit einer umfassenden Key Escrow L sung ab Unabh ngi ge und selbstbestimmte Systeme auf lokaler oder unternehmensweiter Ebene scheinen ihnen hingegen sinnvoll zu sein zumal es dabei weniger um die ber wachung von Kommunikation als um den Schutz vor dem Verlust gespeicherter Informationen geht 4 2 Schliisselverwahrung Die scheinbar einfachste M glichkeit Key Recovery zu erm glichen besteht darin Kopien von allen erzeugten privaten Schl sseln aufzubewahren Die Ar chivierung und Verwaltung der dabei entstehenden Daten ist eine extrem si cherheitskritische Angelegenheit und erfordert eine vertrauensw rdige Instanz Das Vertrauen das in eine solche Instanz gesetzt wird hat dabei eine ande re Qualit t als das einer Zertifizierungsstelle entgegengebrachte da es hierbei nicht darum geht ob man die Instanz f r f hig h lt Identit ten zu berpr fen sondern ihr zutraut einen privaten Schl ssel sicher aufzubewahren und nicht zu mi brauchen Eine normale CA ist nicht in der Lage die vertrauliche Kommu nikation ihrer Benutzer mitzulesen eine Key Recovery Stelle hingegen schon Insofern macht es Sinn diese beiden Instanzen zu trennen Andererseits bringt es organis
30. Schliisselinhabers kann mit der Option dname gesetzt werden wo bei die X 501 Namenskonventionen eingehalten werden missen zum Beispiel CN Thilo Planz O TU Darmstadt C DE wiederherstellbaren Schliissel rekonstruieren KeyEscrow recover lt filename gt cert lt certfilename gt key lt alias gt keystore lt keystore gt password lt password gt Ein wiederherstellbarer Schl ssel kann aus dem ffentlichen Schl ssel der einem X 509 Zertifikat entnommen wird rekonstruiert werden Der rekonstru ierte Schl ssel wird dann in die PKCS12 Datei filename geschrieben Zur Rekon struktion ist allerdings ein Recovery Key notwendig der dem Keystore keystore entnommen wird unter dem Namen alias und Pa wort password Schl ssel in einer Datei verwahren KeyEscrow escrow lt filename gt password lt password gt escrowDir lt escrowdir gt cert lt certfilename gt KeyEscrow legt im bezeichneten Verzeichnis escrowDir verschl sselte Benut zerschl ssel ab im PKCS7 Format Der Recovery Operator der die Dateien wieder entschl sseln kann wird durch sein Zertifikat in der Datei certfilena me bezeichnet Der Benutzerschl ssel selber wird der PKCS12 Datei filename entnommen die sich mit dem Pa wort password ffnen lassen mu 74 Schliissel aus der Datei wiederherstellen KeyEscrow recover lt filename gt cert lt certfilename gt escrowDir lt escrowdir gt keystore lt keystore gt password lt pass
31. Seriennummern der zugeh rigen Zertifikate identifiziert Sowohl das 70 Verzeichnis als auch der Escrow Schliissel mit dem die PKCS7 Dateien ver schliisselt werden sind frei w hlbar FileKeyEscrow escrow new FileKeyEscrow File escrowDir escrow setEscrowCert X509Certificate cert escrow escrow Key key X509Certificate userCert Normalerweise speichert der FileKeyEscrow keine Schliissel die zur Ausstel lung digitaler Signaturen geeignet sind dies ist anhand des Zertifikats ersicht lich Statt dessen erzeugt er eine Ausnahme Sollen dennoch Signaturschliissel verwahrt werden kann dieses Verhalten explizit unterdriickt werden privaten Schliissel aus dem Dateisystem wiederherstellen Die Wieder herstellung der privaten Schl ssel aus den PKCS7 Dateien geschieht ebenfalls durch die Klasse FileKeyEscrow Ben tigt werden hierzu das Zertifikat des ge suchten Schliissels um die Datei zu finden und der Recovery Schliissel um die Datei zu entschl sseln Der Recovery Schliissel mu sich dabei in einem KeyStore befinden der dem FileKeyEscrow bergeben wird Das zugeh rige Pa wort wird der Methode recover mitgegeben escrow setRecoveryKeys KeyStore ks Key a escrow recover X509Certificate userCert password Kann die PKCS7 Datei zwar gefunden aber nicht entschl sselt werden weil beispielsweise der Recovery Schl ssel nicht im KeyStore vorhanden ist so wirft die Methode eine UndecryptableKeyException I
32. Transactions on Information Theory IT 31 469 472 1985 PAUL FELDMAN A practical scheme for non interactive verifiable secret sharing In 28th Annual Symposium on Foundations of Com puter Science S 427 437 1987 94 FGPY97 Y FRANKEL P GEMMELL P D MACKENZIE und M YUNG GHJV96 GJKR96 MSY00 Oak98 Ped91 Ped92 RSA78 Sha79 Sho00 WMB99 YY96 YY97 ZSvR00 Optimal resilience proactive public key cryptosystems In Proc 38th Annual Symposium on Foundations of Computer Science S 384 393 1997 ERICH GAMMA RICHARD HELM RALPH JOHNSON und JOHN VLISSIDES Entwurfsmuster Addison Wesley 1996 ROSARIO GENNARO STANISLAW JARECKI HUGO KRAWCZYK und TAL RABIN Robust Threshold DSS Signatures Lecture Notes in Computer Science 1070 354 371 1996 SHINGO MIYAZAKI KOUICHI SAKURAI und MOTI YUNG On Threshold RSA Signing with no Dealer In SONG JOOSEOK Her ausgeber ISISC 99 S 197 207 Springer Verlag 2000 SCOTT OAKS Java Security O Reilly 1998 TORBEN PEDERSEN A threshold cryptosystem without a trusted party Advances in Cryptology EUROCRYPT 91 547 522 526 1991 TORBEN PEDERSEN Non interactive and information theoretically secure verifiable secret sharing Advances in Cryptology CRYPTO 91 576 129 140 1992 R L RIVEST A SHAMIR und L M ADLEMAN a method for obtaining digital signatures and public key cryptosystems Commu nications of t
33. Wenn die d Vielfache von L sind dann k nnen die Berechnungen l didi A d II si lEA i ber den ganzen Zahlen erfolgen in der urspr nglichen Arbeit FGPY97 wur de der Faktor L n gew hlt es gen gt aber auch das kleinere L n 1 MSY00 Um dies zu erreichen m ssen alle Koeffizienten des Polynoms Viel fache von L sein inklusive des geheim zu haltenden Achsenabschnittes ao der folglich nicht direkt dem Exponenten d entsprechen kann da dieser nicht un bedingt ein Vielfaches von L sein mu Daher bestimmen wir ein modifiziertes Geheimis ay aus dem sich der Exponent d zur ckgewinnen l t Sei zun chst H ggT e L Weil e invertierbar ist modulo p 1 q 1 ist auch H invertierbar Au erdem ist H ein Teiler von L und es existieren keine gemeinsamen Teiler von e und Mithilfe des erweiterten Euklidschen Algorithmus k nnen wir Faktoren P und s berechnen f r die gilt 2 L eP s 1 23 Auf diese Weise ergibt sich eine Zahl k mit d P L k mod p 1 q 1 und k dsH mod p 1 g 1 mit deren Hilfe wir nun einen modifizierten Exponenten d L k definieren welcher durch L teilbar ist weil wir nicht modulo p 1 q 1 reduzieren und aus dem sich der urspr ngliche Exponent d zur ckrechnen l t zumindest innerhalb der Exponentenrestklasse d P d mod p 1 g 1 Dieser modifizierte RSA Exponent d wird nun durch das Polynom f z d aix airt mit a ER O L
34. a dieser das Schl sselpaar erzeugt liegt es bis zur Verteilung auf die brigen Teilnehmer an einem einzelnen Ort Dem Geber mu zugetraut werden seine Berechnungen sicher durchf hren zu k nnen und anschlie end seine Kopie des privaten Schl ssels verl lich zu vernichten Neben der Gef hrdung der Vertrau lichkeit des Schl ssels h ngt auch die Einsatzf higkeit des Key Sharing Systems an der Korrektheit der Berechnungen durch den Geber Beide Probleme treten in Verfahren die ohne einen Geber auskommen nicht auf Ohne im Detail auf 32 diese Verfahren eingehen zu wollen geben wir hier Verweise auf andere Arbei ten die sich mit der Thematik auseinandersetzen Mit der verteilten Erzeugung und Verwendung von RSA Schl sseln besch fti gen sich Miyazaki Sakurai und Yung MSYO00 Sie greifen dabei eine Arbeit von Boneh und Frankel BF97 auf in der gezeigt wird wie mehrere Parteien einen RSA Schliissel gemeinsam ohne Geber erzeugen k nnen Das dort beschriebe ne Verfahren ist allerdings kein redundantes Key Sharing Verfahren weshalb sie es mit dem in Abschnitt 3 5 1 geschilderten Verfahren von Frankel Gemmell MacKenzie und Yung FGPY97 kombineren Dieses Verfahren kam auch im Rahmen des gemeinsamen Projekts des Fachgebiets Theoretische Informatik mit der japanischen Telefongesellschaft NTT ABF 99 zur Implementierung eines verteilten Zeitstempeldienstes zum Einsatz Ein verteiltes System zur Erzeugung von Signaturen nach dem S
35. abspeichern und auch wieder laden ks setKeyEntry alias key password certificateChain Key key ks getKey alias password Certificate cert ks getCertificate alias Keystore speichern Der ShamirStore speichert den intern verwendeten Ja vaKeyStore zun chst in ein Bytefeld ab und verteilt dieses dann ber den SecretSharer auf die angegeben Dateien Der Ausgabestrom der der store Methode bergeben wird wird dabei ignoriert Das Pa wort allerdings wird zum Integrit tsschutz des JavaKeyStores verwendet wenn dieser in das Byte feld geschrieben wird ks store null password 5 3 4 Der KeySharer KeyStore Der KeySharer ist ein spezieller Keystore der die ihm anvertrauten Schl ssel mit einem Key Sharing Verfahren verteilt und in mehrere abh ngige Keystores speichert Die entstehenden Keystores k nnen unabh ngig voneinander verwen det werden um mit den Teilschl sseln zu arbeiten Im Gegensatz zu den dabei entstehenden Teilergebnissen ist es nicht vorgesehen die Schl ssel selbst wieder zusammenzusetzen Dementsprechend sollten die Methoden die einen Schl ssel aus dem Keystore laden f r den KeySharer nicht aufgerufen werden Statt des sen m ssen die abh ngigen Keystores direkt und einzeln verwendet werden 68 Konfiguration Der KeySharer bezieht seine Parametrisierung aus einer XML Datei die ihm w hrend dem Ladevorgang ber einen Eingabestrom zugef hrt werden mu Die XML Datei hat folgenden Aufbau lt k
36. an l ngere Nachrichten dann auch mit einem symmetrischen Verfahren und verschl sselt nur den symmetrischen Schl ssel der je nach Verfahren zwischen 50 und 200 Bits lang ist mit RSA Au erdem bietet es sich aus Sicherheitsgr nden an alle Nachrichten mit einigen Zufallsbits auf eine feste L nge zu bringen Padding so da unter anderem jede Nachricht zu immer neuen Schl sseltexten f hrt Neben Verschl sselungen sind auch Signaturen m glich Um eine Signatur f r eine Nachricht m zu erzeugen die wieder als nat rliche Zahl zwischen 1 und N 1 angesehen wird potenziert der Absender die Nachricht m mit sei nem privaten Exponenten d Es ergibt sich eine Signatur s von der mit dem ffentlichen Schl ssel e N berpr ft werden kann ob sie zu der Nachricht geh rte s m mod N und m s m m m m mod N Auch hier ist wieder anzumerken da Nachrichten blicherweise gr er sind als die RSA Moduln so da anstelle der Nachricht m nur eine Pr fsumme h m signiert wird die mithilfe einer kryptographischen Hashfunktion gewon nen werden kann Dadurch wird es allerdings unm glich aus der Signatur die Nachricht zur ckzugewinnen Vielmehr mu die Nachricht zusammen mit der Signatur bertragen werden Ein Padding mit Zufallszahlen ist bei RSA Signaturen nicht angezeigt so da die Signatur ein deterministisches Verfahren bleibt dies erm glicht die in den folgenden Abschnitten beschriebenen verteil ten RSA Signat
37. as Geheimnis ist dann gegen ber Au enstehenden und gegen ber einer Minderheit an Teilneh mern gesch tzt kann aber bei Bedarf durch Kooperation rekonstruiert werden Man sagt die Teilnehmer seien neugierig aber ehrlich curious but honest Teilnehmer die sich nicht an das Protokoll halten k nnen die Rekonstruktion aufhalten Au erdem kann ein Teilnehmer sich nicht sicher sein da sein Anteil berhaupt korrekt gebildet wurde bertragungsfehler Sabotage betr geri scher Geber Beide M ngel k nnen mit einem Verfahren von Torben Peder sen Ped92 behoben werden das auf einem Commitment des Gebers beruht und die Verifikation der Teilgeheimnisse erm glicht Dieses Verfahren zeichnet sich gegen ber anderen vorgeschlagenen Verfahren dadurch aus da es ohne Interaktionen zwischen den Teilnehmern oder mit dem Geber auskommt und da durch die zus tzlichen Verifikationsinformationen keinerlei Hinweise auf das Geheimnis gegeben werden 2 3 1 Das Pedersen Verfahren Das Verfahren ben tigt eine weitere Primzahl q mit q mp 1 f r ein belie biges m glicherweise kleines m Dadurch ergibt sich der K rper Z qZ der ber eine Untergruppe G der Ordnung p verf gt Sei g Gp ein erzeugendes Element von G und h Gp ein weiteres Element aus Gp f r das der diskrete 11 Logarithmus log h beziiglich des Erzeugers g nicht bekannt ist Der Geber kann nun ein Commitment f r zwei Werte s und s aus Z pZ eingehen ohne dam
38. asse invertierbar Die Primzahl p mu nicht f r jedes Geheimnis das ver teilt werden soll neu gew hlt werden sondern kann auch als fester Bestandteil des Verfahrens angesehen und somit global bekannt sein Um die geheime Zahl s Z pZ zu verteilen w hlt der Geber zuf llige Koeffizienten a Er Z pZ 1 lt j lt t 1 wodurch sich das Polynom 1 f z s ain Loft mod p ergibt Dieses Polynom hat den Grad t 1 wird also durch t seiner St tzstellen eindeutig festgelegt Jeder Teilnehmer 1 n erh lt den Funktionswert s f i als seinen Anteil des Geheimnisses Rekonstruktion des Geheimnisses Wenn sich mindestens t der n Teil nehmer zusammenfinden k nnen sie das Geheimnis durch Offenlegung ihrer Teilgeheimnisse gemeinsam rekonstruieren Wir wollen die Menge der Num mern dieser Teilnehmer als A C 1 n bezeichnen Unter Verwendung der Interpolationsformel von Lagrange t 1 t t X gt x f z Y aja fai i i 0 i 1 I 1 l i f r beliebige St tzstellen x ergibt sich das Geheimnis s als s f 0 gt s eh Jeudi mod p 4 10 Sicherheit des Verfahrens Fin Angreifer dem es gelingt bis zu t 1 Teil geheimnisse s in Erkenntnis zu bringen kann dadurch keine Riickschliisse auf das Geheimnis s ziehen Wenn t 1 St tzstellen des geheimen Polynoms be kannt sind exisitiert fiir jeden denkbaren Wert s genau ein Polynom welches alle Stii
39. assword throws NoSuchAlgorithmException Anteile serialisieren byte bytes share getEncoded Anteile zusammensetzen public static byte combine SecretShare shares throws NoSuchAlgorithmException SecretSharingException public static byte checkAndCombine SecretShare shares String integrityPassword throws NoSuchAlgorithmException SecretSharingException E 2 Key Sharing Basisfunktionalit t Schliissel verteilen 89 public static KeyShare share Key secret int threshold int sharenumber throws InvalidParameterException NoSuchAlgorithmException InvalidKeySpecException Teilsignaturen und Teilentschliisselungen erstellen Signature signer Signature getInstance DistributedMD5withRSA signer initSign keyshare signer update message byte partialSignature signer sign Teilberechnungen zusammenf hren public static byte combine byte shares byte message throws NoSuchAlgorithmException SecretSharingException E 3 Der Shamir KeyStore Konfiguration lt shamir store threshold 2 load AUTO store AUTO integrity password Passwort gt lt share file 1a share gt lt share file 2b share gt lt share file 3c share gt lt shamir store gt Instanz erzeugen KeyStore ks KeyStore getInstance ShamirStore Keystore laden FileInputStream in new FileInputStream configuration xml ks load in password in close Keystore verwenden ks se
40. atorische Vorteile und vermindert die Zahl an notwendigen vertrau ensw rdigen Stellen wenn man Zertifizierungsinstanzen zu Trustcentern mit solch erweiterter Funktion ausbaut Offensichtlich funktioniert Key Recovery anhand von Backups nur wenn diese Backups auch angelegt wurden Dies macht die Kooperation des Schl ssel inhabers notwendig der seinen Schl ssel entweder vom Trustcenter erzeugen lassen mu einen speziellen Schl sselgenerator verwenden mu der das Recovery Konzept unterst tzt etwa den vor einiger Zeit von den USA propagierten 38 Clipper Chip oder aktiv seinen Schl ssel zur Verwahrung vorlegen mu W hrend dies kein Problem darstellt wenn der Benutzer mit dem Backup einverstanden ist wird eine obligatorische Schl sselverwahrung schwierig durchzusetzen Das Archiv der Schl sselkopien stellt ein immenses Sicherheitsrisiko dar und mu entsprechend gesch tzt werden Um eine Verschl sselung dieser Da ten f hrt somit kein Weg herum Dadurch entstehen Key Recovery Schl ssel die von den Recovery Operatoren verwendet werden um Benutzerschl ssel aus dem Archiv zu holen Diese sind ebenfalls extrem kritisch Eine M glichkeit diese Master Schl ssel zu sichern ist durch das in Kapitel 3 geschilderte Key Sharing gegeben Durch Key Sharing kann man gleichzeitig die Kontrolle ber das Key Recovery auf mehrere Instanzen oder Personen verteilen was die Ver trauensw rdigkeit des Systems bei den Benutzern erh ht
41. baren Anspruch ein Key Escrow fiir Signaturschliissel zu betreiben da der einzige Zweck eines solchen Unterfangens Urkundenf lschung sein k nn te Durch eine solche Ma nahme w rde man die konomisch sehr bedeutsame Rechtswirksamkeit digitaler Signaturen gef hrden Im deutschen Signaturgesetz ist vorgeschrieben da digitale Signaturschl ssel nicht verwahrt oder wieder hergestellt werden d rfen Au erdem d rfen diese Schl ssel nicht f r andere Zwecke zum Beispiel Verschl sselungen eingesetzt werden 36 4 1 1 Key Recovery fiir Strafverfolgungsbeh rden Gegen ein umfassendes und verbindliches Key Recovery System wie es noch vor wenigen Jahren intensiv diskutiert wurde sind zahlreiche grunds tzliche und technische Bedenken ge u ert worden Vor allem durch die explosive Ent wicklung des E Commerce der sich in seiner wachsenden wirtschaftlichen Be deutung stark auf kryptographische Methoden st tzt haben sich seither die Bef rworter einer unreglementierten Kryptographie durchsetzen k nnen Dies mu jedoch nicht f r alle Zeiten so bleiben und deshalb wollen wir ihre bekann testen Argumente skizzieren grunds tzliche Einw nde Ein sehr fundamentaler Einwand bezieht sich auf eventuelle Verletzungen b rgerlicher Grundrechte durch ein Key Recovery System Insbesondere wird mit dem Recht auf Privatsph re inklusive dem Recht auf vertrauliche Kommunikation und dem Recht auf freie Meinungs u e rung argumentiert Deswe
42. ber weiterhin ein v er Qy also ein invertierbares Quadrat aus Z NZ und bestimmt f r jeden Teilnehmer i dessen Verifikationsschl ssel v vt On Der ffentliche Schl ssel ist e N der geheime Anteil von Teilnehmer i ist d Dazu kommen die ffentlichen Verifikationsschliissel v und v 27 Schliisselverwendung Es stellt sich wieder das Problem der Berechnung der Lagrange Koeffizienten l Ma IT 7 IE A i Ahnlich wie beim Verfahren aus Abschnitt 3 5 1 kann man diese Berech nungen iiber den ganzen Zahlen durchfiihren wenn man den Ausdruck mit L n 1 zu l Xa La eZ IEA i erweitert in der Originalarbeit Sho00 ist L n aber auch hier gen gt wieder L n 1 Mit diesen modifizierten Koeffizienten kann man zwar nicht direkt den Exponenten d rekonstruieren aber zumindest Ld y A adi mod Ha 1EA Die von jedem Teilnehmer durchgefiihrte Berechnung ist si ml On und liefert ein Element aus Q yzur ck wobei allerdings vorausgesetzt wird da die Nachricht m aus Z NZ stammt Diese zus tzliche Forderung gegen ber dem normalen RSA Verfahren ist allerdings keine wirkliche Einschr nkung da fast alle Elemente aus Z NZ ebenfalls in Z NZ liegen Wenn man ein m aus Z NZ Z NZ findet so gilt ggT m N 1 und man hat N faktorisiert Bei digitalen Signaturen kann das Problem ebenfalls nicht auftreten da die Hashwerte von Nachrichten k rzer sind als die Bitl ngen von p und q N
43. browse Secret Share 3 threshold is 2 verified 3c share browse v check share integrity with the password Cancel Finish Abbildung 5 6 Dialog zum Einlesen von Anteilen des Shamir Store 5 2 4 Paket keyshare escrow Das Paket keyshare escrow besch ftigt sich mit Schl sselverwahrung und wiederherstellung Es enth lt eine Implementierung f r eine Verwahrung in Dateien sowie spezielle KeyPairGenerator f r wiederherstellbare RSA und ElGamal Schl ssel Abschnitt 4 3 AbstractEscrowedKeyPairGenerator diese abstrakte Basisklasse stellt die all gemeing ltigen Methoden f r einen Schl sselgenerator f r wiederherstell bare Schl ssel zur Verf gung Dies umfa t vor allem die Kapselung eines normalen KeyPairGenerators f r den entsprechenden Algorithmus und die Verwaltung der zum Einsatz kommenden Cipher Instanz Die kon krete Schliisselerzeugung wird mittels einer Schablonenmethode an die konkreten Unterklassen delegiert EscrowedKeyParameterSpec mit dieser Klasse kann der ffentliche Schl ssel der zum Key Escrow verwendet werden soll bermittelt werden Wird der KeyPairGenerator nicht mit einer solchen Instanz initialisiert erzeugt er normale nicht wiederherstellbare Schl sselpaare ElGamalKeyPairGenerator diese Klasse generiert wiederherstellbare ElGamal Schl ssel RSAKeyPairGenerator diese Klasse generiert wiederherstellbare RSA Schl ssel KeyEscrowBase diese abstrakte Basisklasse leistet die Ver u
44. bt davon jedoch unbeeinflu t Ein Teilneh mer oder Au enstehender kann durch Kenntnis von log h keine R ckschl sse auf das Geheimnis ziehen da wie beim reinen Shamir Verfahren informations theoretisch sicher bleibt 2 4 Weitergehende Eigenschaften von Secret Sharing Verfahren Abschlie end wollen wir noch einmal die bisher vorgestellten und weitere Eigen schaften von Secret Sharing Verfahren zusammenfassen und damit einen ber blick ber die in der Literatur verwendete Terminologie sowie die verschiedenen Anforderungen an die Verfahren bieten e Ein Secret Sharing Verfahren hei t perfekt wenn sich aus der Kenntnis einer f r die Rekonstruktion unzureichender Menge an Teilgeheimnis sen keinerlei Informationen ber das Geheimnis ableiten lassen die man nicht auch ohne Kenntnis eines einzigen Teilgeheimnisses h tte Beim 1 Shamir Verfahren bedeutet dies da trotz t 1 bekannter Stiitzstellen wei terhin alle denkbaren Achsenabschnitte des geheimen Polynoms m glich und gleichwahrscheinlich sind 13 e Ein Secret Sharing Verfahren hei t redundant wenn nicht alle Teilgeheim nisse zur Rekonstruktion ben tigt werden Dadurch ist das Verfahren nicht anfallig gegen den Verlust einzelner Anteile e Wir sprechen von Secret Sharing wenn eine beliebige t elementige Teilmenge der n ausgegebenen Anteile ausreicht um das Geheimnis zu rekonstruieren Damit sind automatisch alle Anteile gleichberechtigt Im Gegensatz da
45. ch auf mehrere Dateien verteilt aus denen er auch wieder geladen werden kann Dieser Vorgang ist aufgrund der Einbettung in das KeyStore Interface der JCA fiir den Anwender transparent Konfiguriert wird der ShamirStore mit einer XML Datei Konfiguration Der ShamirStore bezieht seine Parametrisierung aus einer XML Datei die ihm w hrend dem Ladevorgang iiber einen Eingabestrom zu gef hrt werden mu Dieser etwas umst ndliche Weg ist durch die seitens JCA vorgegebene Schnittstelle bedingt Die XML Datei hat folgenden Aufbau lt shamir store threshold 2 load AUTO store AUTO integrity password Passwort gt lt share file 1a share gt lt share file 2b share gt lt share file 3c share gt lt shamir store gt Fiir jeden Anteil der erzeugt werden soll gibt es ein geschachteltes lt share gt Tag welches den Namen der Datei angibt die diesem Anteil zugeordnet wird Die Anzahl der Anteile die ben tigt werden um den ShamirStore zu rekon struieren wird durch das Attribut threshold festgelegt Das optionale At tribut integrity password gibt das Integrit tspa wort zum Schutz der An teile an Die beiden Attribute load und store bestimmen das Verhalten des ShamirStore beim Laden und Zuriickschreiben Mit der Einstellung AUTO wer den die entsprechenden Dateien automatisch ausgelesen beziehungsweise ange legt Die Einstellung OFF f hrt dazu da der ShamirStore nicht geladen oder gespeichert wird Sie kann sinnvoll
46. chenden Anzahl von Anteilen kann die Datei filename mit FileSharer combine lt filename gt p lt password gt delete rekonstruiert werden Die Anteile werden in den Dateien filename 1 bis filena me n erwartet Das optionale Passwort password wird zur Uberpriifung der Integrit t der Anteile herangezogen Wenn die Option delete gesetzt ist werden anschliefend die Dateien mit den Anteilen gel scht 5 4 2 Das Key Sharing Kommandozeilen Tool Der KeySharer dient zur Erzeugung und Verwendung von verteilten RSA und ElGamal Schlisseln Er kann diese Schl ssel importieren oder erzeugen und anschliefend auf mehrere Keystore Dateien verteilen Mit jeder dieser Keystore Dateien k nnen dann Teilsignaturen und Teilentschliisselungen durchgefiihrt werden welche dann ebenfalls mit KeySharer zusammengesetzt werden k nnen Teilschl ssel erzeugen KeySharer kann RSA und ElGamal Schl ssel so wohl erzeugen als auch von einem Keystore importieren Die daraus abgeleiteten Teilschl ssel speichert das Programm dann in eine Reihe abh ngiger Keystores welche an die Teilnehmer des Key Sharing bermittelt werden k nnen Der Befehl um den Schl ssel alias aus dem Keystore keystore zu importieren und zu verteilen lautet KeySharer share t lt threshold gt n lt shares gt import lt keystore gt key lt alias gt password lt password gt storetype lt type gt storepass lt storepass gt Dabei wird das Password pass
47. d CommonParams Share Combine 86 interface AppiicationiAode parseParameters void run void usage void KeySharer setupCmdLineOptions void identifyMode ApplicationMode main void CommonParams Encrypt Decrypt Sign SignPKCS Signx509 Combine CreateNew ShareExisting Anhang D Benutzerhandbuch Kommandozeilenapplikationen D 1 FileSharer Datei aufteilen FileSharer share lt filename gt p lt password gt t lt threshold gt n lt shares gt delete Datei wiederherstellen FileSharer combine lt filename gt p lt password gt delete D 1 1 KeySharer Teilschliissel erzeugen KeySharer share t lt threshold gt n lt shares gt import lt keystore gt key lt alias gt password lt password gt storetype lt type gt storepass lt storepass gt KeySharer create lt alias gt t lt threshold gt n lt shares gt keystore lt keystore gt keytype lt type gt keysize lt keysize gt password lt password gt Berechnungen mit den Teilschl sseln durchf hren KeySharer decrpyt lt filename gt keystore lt keystore gt password lt password gt KeySharer sign lt filename gt key lt alias gt keystore lt keystore gt password lt password gt sigAlg lt algorithm gt KeySharer signX509 lt filename gt key lt alias gt keystore lt keystore gt password lt password gt signature lt algorith
48. d automa tisch anhand des threshold entschieden Ungiiltige Werte fiir sharenumber und threshold f hren zu einer InvalidParameterException falls auf dem System keine MD5 Hashfunktion zur Berechnung der ID fiir die Anteile verfiigbar ist wird eine NoSuchAlgorithmException ausgel st Integrit tspa wort setzen public static void protectIntegrity PasswordIntegrityProtected shares String password throws NoSuchAlgorithmException Bevor der Geber die Anteile an die Teilnehmer weiterreicht kann er sie mit ei nem Integrit tspa wort versehen Um das von der Methode share byte int int erhaltene SecretShare bergeben zu k nnen ist ein Typecast notwendig Bei den von der genannten Methode erzeugten SecretShare ist dies stets m glich Falls die MD5 Funktion auf der der Integrit tsschutz beruht nicht verf gbar ist wird eine NoSuchAlgorithmException ausgel st Anteile serialisieren byte bytes share getEncoded Jeder SecretShare verf gt ber eine Methode byte getEncoded die ihn in eine serialisierte Form berf hrt in der er leicht transportiert werden kann Da hierbei Java Objektserialisierung zum Einsatz kommt kann es mit ei nem java io ObjectInputStream aus dieser Form wieder instantiiert werden Anteile zusammensetzen public static byte combine SecretShare shares throws NoSuchAlgorithmException SecretSharingException public static byte checkAndCombine 65 SecretShare shares S
49. d f r den Sicherheitsbeweis ben tigt 3 7 Das ElGamal Verfahren Neben dem RSA Verfahren ist das auf der Schwierigkeit der Berechnung diskre ter Logarithmen beruhende ElGamal Verfahren ElG85 die bekannteste Basis f r Public Key Kryptosysteme Es wurde 1985 von Taher ElGamal vorgeschla gen und hnelt dem Diffie Hellman Schliisselaustausch Protokoll Das Diffie Hellman Problem Die Sicherheit des ElGamal Verfahrens be ruht auf der Annahme daf es keinen effizienten Algorithmus gibt um das sogenannte Diffie Hellman Problem zu l sen Das Diffie Hellman Problem besteht darin fiir eine gegebene prime Rest klassengruppe Z pZ mit einem bekannten erzeugenden Element Generator g Z pZ f r zwei Elemente A o und B g das Element C g zu berechnen obwohl a und b unbekannt sind Eine M glichkeit das Element C zu bestimmen besteht darin die Expo nenten a oder b zu berechnen Dann ergibt sich C A B Man bezeich net a und b als diskrete Logarithmen von A beziehungsweise B zur Basis g in der Gruppe Z pZ Fiir dieses Diskrete Logarithmus Problem sind aller dings keine effizienten Algorithmen bekannt Das Diffie Hellman Problem und das Diskrete Logarithmus Problem stehen dabei in einer hnlichen Beziehung zueinander wie das RSA Problem und das Faktorisierungs Problem es ist nicht bekannt ob sie quivalent sind Da das Diffie Hellman Problem in keiner bekannten Beziehung zum RSA Problem steht bietet das ElGamal V
50. da durch eine genaue Analyse des Generators zwar festge stellt werden kann da er dieses automatische Key Recovery unterst tzt aber es darf nicht m glich werden dadurch an Informationen zu kommen die es erm glicht das Recovery auch tats chlich durchzuf hren Im allgemeinen wird der Generator einen ffentlichen Backup Schl ssel enthalten aber nicht den dazugeh rigen privaten Recovery Schl ssel 4 3 1 Kleptographie Adam Young und Moti Yung bezeichnen die folgenden Techniken als Kleptogra phie und modellieren die in den Schliisselgeneratoren eingebauten Hintert ren als SETUP secretly embedded trapdoor with universal protection von denen sie drei Kategorien unterscheiden YY96 YY97 Derjenige der eine SETUP einrichtet wird von ihnen als Angreifer bezeichnet 39 SETUP Eine regu re SETUP ist eine Modifikation eines Kryptosystems so da die Eingaben mit den Spezifikationen des ursprtinglichen Kryptosystems tiber einstimmen das modifizierte Kryptosystem die ffentliche Verschl sselungsfunktion des Angreifers enth lt nicht aber dessen private Entschl sselungsfunktion die Ausgabe den urspr nglichen Spezifikationen entspricht gleichzeitig aber verschl sselte Informationen ber den Benutzerschl ssel enth lt die f r den Angreifer leicht zug nglich sind die Ausgaben der beiden Kryptosysteme ununterscheidbar sind au er f r den Angreifer es auch nach vollst ndiger Analyse des modifizierte
51. da eine Anwendung aus mehreren Modi besteht von denen jeweils einer ausgew hlt und durch gef hrt wird Diese Schnittstelle beschreibt die Methoden die dabei au tomatisch von CommandLineApp aufgerufen werden FileSharer diese Klasse implementiert die Applikation FileSharer Abschnitt 5 4 1 KeySharer diese Klasse implementiert die Applikation KeySharer Abschnitt 5 4 2 KeyEscrow diese Klasse implementiert die Applikation KeyEscrow Abschnitt 5 4 3 5 2 6 Paket keyshare tests Das Paket keyshare tests enth lt Testf lle anhand derer die korrekte Funk tionsweise der Klassen in den anderen Paketen berpr ft werden kann Die Testf lle sind gem dem Framework JUnit erstellt worden welches sich mit Komponententests f r Java Klassen besch ftigt Dementsprechend k nnen sie mit entsprechenden Tools automatisch durchgef hrt und ausgewertet werden Die Pflege der Testf lle hat sich w hrend der Entwicklung als extrem wertvoll 62 usage void KeyEscrow setupCmdLineOptions void identifyMode ApplicationMode main void CommonParams CreateNew Escrow Recover RecoverFromFile CommandLineApp Usage void setupCmd ineOptions void identitWode ApplicationMode run void Usage void FileSharer setupCmdLineOptions void identifyMode ApplicationMode main void CommonParams Share Combine interface AppiicationiAode parseParameters void run void usage void KeySharer setupCmdLi
52. dabei an andere Pro vider delegiert mu also bereits vorhanden sein 56 5 2 3 Paket keyshare keystore Das Paket keyshare keystore enth lt zwei KeyStore Implementierungen die von Secret und Key Sharing Gebrauch machen Der ShamirStore kapselt einen anderen Software Keystore beispielsweise den JKS von Sun und verteilt ihn zur Speicherung in mehrere Dateien nach dem Shamir Verfahren Der Key Sharer verteilt die einzelnen Schliissel die in ihn gesteckt werden mit jeweils daf r geeigneten Key Sharing Verfahren auf mehrere abh ngige Keystores Die se Keystores k nnen dann zum Erstellen von Teilsignaturen und entschl sse lungen genutzt werden Der Shamir Store verf gt ber eine kleine graphische Benutzerschnittstelle die sich im Unterpaket keyshare keystore gui befin det Beide Keystores werden ber XML Dateien konfiguriert deren Zugriffs pfade im Unterpaket keyshare keystore xml definiert sind KeyStoreBase diese abstrakte Klasse stellt Default Implementierungen f r die Methoden eines JCA KeyStoreSpi bereit und dient damit zur Vermei dung von Code Duplikaten Sie bedient sich dabei einer gekapselten KeyStore Instanz aus einem anderen Provider ShamirStore diese von KeyStoreBase abgeleitete Klasse implementiert den ShamirStore Keystore KeySharer diese von KeyStoreBase abgeleitete Klasse implementiert den KeySharer Keystore Unterpaket keyshare keystore xml Die Keystores werden tiber XML Dateien konfiguriert in den
53. die Klasse Provider Im Prinzip handelt es sich dabei um eine Tabelle die einem Algorithmennamen den Namen der implementierenden Klasse zuord net die dann dynamisch geladen werden kann Die Providerklassen selbst wer den dem Laufzeitsystem entweder ber Systemeigenschaften oder zur Laufzeit durch Security addProvider Provider bekannt gemacht 5 1 5 ASN1 Codec Ein Aspekt der durch JCA nicht abgedeckt wird ist die Erzeugung von ASNI Datenstrukturen Gem diesem Kodierungsstandard werden beispielsweise X 509 Zertifikate geschrieben Infolgedessen kann man mit JCA zwar Zertifikate lesen und auswerten aber nicht ausstellen Wir haben daher ein urspr nglich von der Fraunhofer Gesellschaft entwickeltes ASN1 Codec verwendet welches mittler weile auf den Fachbereich Theoretische Informatik bergegangen ist 5 2 berblick ber die Java Klassen Die Java Klassen sind in eine Reihe von Paketen gruppiert keyshare das Paket enth lt die grundlegenden Algorithmen und Datenstruktu ren zur Implementierung der Secret Sharing und Key Sharing Verfahren keyshare jca das Paket enth lt H llen und Adapterklassen mit denen eine m glichst gro e Kompatibilit t zur Java Cryptographic Architecture her gestellt werden soll Das Paket enth lt Implementierungen von Cipher Signature und KeyFactory zum Umgang mit Schl sselanteilen keyshare keystore das Paket enth lt verschiedene KeyStore Implementie rungen die von Secret und Key Sharing G
54. diesem Verfahren sowie eine innere Klasse f r die zugeh rige PartialDecryption FGMY_RSAPrivateKeyShare diese Klasse stellt einen durch das Verfahren zum Teilen von RSA Schl sseln nach Frankel Gemmell MacKenzie und Yung Abschnitt 3 5 2 entstandenen Teilschl ssel dar Sie enth lt auch Metho den zum Verteilen eines RSAPrivateCrtKey nach diesem Verfahren sowie innere Klassen f r die zugeh rigen PartialSignature und PartialDecryption 53 ShoupRSAPrivateKeyShare diese Klasse stellt einen durch das Verfahren zum Teilen von RSA Schliisseln nach Shoup Abschnitt 3 6 entstandenen Teil schliissel dar Sie enth lt auch Methoden zum Verteilen eines StrongRSAPrivateCrtKey nach diesem Verfahren sowie innere Klassen fiir die zugeh rigen PartialSignature und PartialDecryption RedundantElGamalPrivateKeyShare diese Klasse stellt einen durch das redun dante Verfahren zum Teilen von speziellen ElGamal Schl sseln Abschnitt 3 8 entstandenen Teilschliissel dar Sie enth lt auch Methoden zum Ver teilen eines ExtendedElGamalPrivateKey nach diesem Verfahren sowie eine innere Klasse fiir die zugeh rige PartialDecryption KeySharer diese Klasse enthalt statische Methoden zum einfachen Zugriff auf die Key Sharing Funktionalit t Erzeugen von Teilschliisseln Kombinie ren von Teilsignaturen und entschliisselungen Sie bietet damit eine Fas sade fiir den Key Sharing Teil des Pakets X509 diese Klasse enthalt statische Hilfsmethoden im Zusam
55. diglich eine einfach anzubindende M glich keit geschaffen werden um den CA Schl ssel verteilt zu speichern er w rde zur Laufzeit dann zusammengesetzt Es sollte auch m glich sein ohne gro en Aufwand alternativ den bisherigen oder einen dritten Weg zur Schl sselspeiche rung zu verwenden Hierzu haben wir die n tige Secret Sharing Funktionalit t in eine f r FlexiTrust und andere Java Anwendungen leicht zug ngliche Form gebracht Jenseits des FlexiTrust Projekts seien hier drei Projekte genannt die Key Sharing zur Erstellung verteilter Signaturen einsetzen n mlich der verteilte Zeitstempeldienst den der Fachbereich gemeinsam mit NTT entwickelt hat ABF 99 die von Boneh Malkin und Wu beschriebene Integration in einen 33 SSL Webserver WMB99 und das COCA Projekt der Cornell Universit t ZSvR00 das eine verteilte Online CA implementiert Um eine m glichst sichere Verwahrung von Benutzerschliisseln zu erm gli chen werden diese von der CA verschl sselt gespeichert siehe hierzu auch Abschnitt 4 1 Die Public Key Kryptographie macht es m glich da die CA diese Daten selbst nicht mehr unbedingt entschl sseln kann sondern jemand anders daf r zust ndig sein kann Durch Key Sharing kann die Aufgabe des Key Recovery auch auf mehrere Personen verteilt werden Dabei wird gleich zeitig die Sicherheit des daf r notwendigen Schl ssels erh ht 34 Kapitel 4 Schliisselverwahrung Sollte es zu einer Serie terroristi
56. dteil der Java Laufzeitumgebung ist die Java Cryptography Architecture JCA die dem Programmierer eine umfangreiche Schnittstelle zum Zugriff auf kryprographische Funktionen bietet Dabei ist es vorgesehen 44 da die einzelnen Algorithmen von verschiedenen Anbietern Provider imple mentiert werden k nnen die Verwaltung der verschiedenen auch gleichzeitig installierten Provider f r den Anwender jedoch transparent auf dessen Wunsch aber auch zur Laufzeit beeinflu bar ist Da wir Teile unserer Implementierung ber JCA anbieten ist ein Grundverst ndnis der Konzepte von JCA notwendig so da wir an dieser Stelle einen kurzen berblick geben wollen Zur Vertiefung sei auf die Literatur Oak98 und die Internetseiten von Sun Microsystems ver wiesen Ein Teil der JCA Klassen wird auch als Java Cryptography Extension JCE bezeichnet Im Gegensatz zu den brigen JCA Klassen die sich in den java security Paketen befinden liegen die JCE Klassen in javax crypto Paketen Diese Auf teilung war aufgrund von mittlerweile gelockerten Exportvorschriften der US Regierung notwendig ist dann aber hinf llig geworden so da auch JCE in zwischen zum Standardumfang der Laufzeitumgebung geh rt Wir werden im folgenden nicht zwischen JCA und JCE unterscheiden 5 1 1 Schl ssel JCA modelliert private ffentliche und symmetrische Schl ssel und bietet Klas sen zu deren Erzeugung Konvertierung und Speicherung an Key diese Schnittstell
57. dundant nach dem Ver fahren von Frankel Gemmell MacKenzie und Yung Abschnitt 3 5 2 verteilt ElGamal Schl ssel werden nach den Verfahren aus Abschnitt 3 8 verteilt Da eine redundante Verteilung von ElGamal Schl sseln Schl ssel spezieller Gestalt erfordert steht diese M glichkeit nur bei neu erzeugten Schl sselpaaren zur Verf gung und nicht beim Import aus einem KeyStore Berechnungen mit den Teilschl sseln durchf hren Die Teilschl ssel k nnen f r Teilentschl sselungen und nur bei RSA f r Teilsignaturen verwen det werden In beiden F llen erzeugt KeySharer dabei eine Ausgabe die sp ter zusammen mit den Ausgaben der anderen Teilnehmer zur Gesamt Entschl sse lung bzw Signatur kombiniert werden kann Bei der Entschl sselung wird das PKCS7 Format unterst tzt Um eine ver schl sselte PKCS7 Datei wie sie beispielsweise von der Klasse KeyEscrow er zeugt wird teilweise zu entschl sseln wird der Befehl KeySharer decrypt lt filename gt keystore lt keystore gt password lt password gt verwendet Der bezeichnete Keystore wird dabei automatisch nach einem pas senden Schl ssel durchsucht der dann mit dem angegebenen Pa wort geladen werden kann Die Teilentschl sselung wird in die Datei filename n geschrieben wobei n die Nummer des Teilschl ssels ist Mit RSA Teilschl sseln k nnen auch Teilsignaturen erzeugt werden Hierbei werden rohe Signaturen sowie teilsignierte X509 Zertifikate und PKCS7 Dateien unte
58. e Schltisselerzeugung erfolgt zun chst genauso wie beim Frankel Gemmell MacKenzie Yung Verfahren aus Abschnitt 3 5 1 Dieses wird vollst ndig ausgef hrt so da im Ergebnis die Interpolationsstellen d f r die einzelnen Teilnehmer berechnet wurden Wie oben dargelegt sind al le d durch L teilbar um Invertierungen zu vermeiden Gleichzeitig sind die d dadurch auch gr fer als normale RSA Exponenten und k nnen durch die Inter polationskoeffizienten A a jc A Gi 15 mit denen sie multipliziert werden auch negativ werden In unserem Verfahren fiihren wir alle Divisionen die sich durch die Koeffi zienten ergeben k nnen bereits als Vorberechnung aus Ieta i d Infolge dessen m ssen durch den einzelnen Teilnehmer i zur Berechnung seines Teilergebnisses s m i mod N keine Divisionen sondern nur noch Multiplikationen des neuen Exponenten d vorgenommen werden daa d 1 1 1 leA i le l n A Diese Multiplikationen im Exponenten k nnen aber auch als Exponentia tionen ausgefiihrt werden mhAda my lleno ret njati mod N Schliisselverwendung Da fir die Exponentiationen keine geheimen Infor mationen notwendig sind sondern lediglich Kenntnis iiber die Beteiligten i A k nnen diese Berechnungen auch beim Kombinieren durchgefiihrt werden Es wird also m glich da die Teilergebnisse von den Teilnehmern ohne Kenntnis der Identit t der anderen Beteiligten erstellt werden Sie m ssen nur noch eine gew h
59. e Sicherheit h ngt nur davon ab den Schl ssel geheimzuhalten August Kerckhoffs von Nieuwenhof in La Cryptographie militaire 3 1 Public Key Kryptographie In herk mmlichen kryptographischen Verfahren wird eine Nachricht von einem Chiffrieralgorithmus in einen Schliisseltext umgewandelt der nur von einem pas senden Dechiffrierverfahren wieder entschliisselt werden kann Der Sender pa rametrisiert dabei die Chiffre mit einem Schliissel den der Empf nger ebenfalls in die Entschl sselungsfunktion einsetzen mu Einem Angreifer ohne Kenntnis des Schl ssels bleibt nur die M glichkeit alle denkbaren Schl ssel durchzupro bieren was angesichts deren Anzahl unpraktikabel ist Ein Problem bei diesen Verfahren besteht in der Geheimhaltung der Schliissel Dies ist noch zu bew ltigen wenn die Daten nur vom Sender selbst entschliisselt werden sollen kryptographische Datenspeicher Ansonsten mu der Sender al len Empf ngern vorab und auf sicherem Wege den Schl ssel zukommen lassen Wenn der Schl ssel mehrmals verwendet werden soll m ssen alle Beteiligten den Schl ssel fortan geheim halten und den brigen Teilnehmern zutrauen da diese den Schl ssel ebenfalls geheim halten Ein zweites Problem ist die Anzahl der ben tigten Schl ssel Wenn jeder Teilnehmer in der Lage sein soll jedem anderen Teilnehmer eine Nachricht zu senden deren Inhalt kein dritter Teilnehmer und nat rlich auch kein Au en stehender erkennen kann dann b
60. e gruppiert alle kryptographischen Schl ssel Sie schreibt lediglich vor da ein Schl ssel einem Algorithmus zugeordnet wird und eine Bin rkodierung unterst tzen sollte PrivateKey diese Schnittstelle ohne Methoden dient nur zur typsicheren Un terscheidung von ffentlichen und privaten Schl sseln PublicKey diese Schnittstelle ohne Methoden dient nur zur typsicheren Unter scheidung von ffentlichen und privaten Schl sseln KeyPair diese Klasse fa t einen PrivateKey und einen PublicKey zu einem Schl sselpaar zusammen SecretKey diese Schnittstelle ohne Methoden dient nur zur typsicheren Iden tifikation eines symmetrischen Schl ssels KeySpec zus tzlich zu den Key Klassen gibt es noch die KeySpec Klassen die beschreibende Informationen ber einen Schl ssel enthalten anhand derer eine Key Instanz erzeugt werden kann Dabei kann es sich um bin re Be schreibungen wie PKCS8 handeln oder auch um algorithmenabh ngige offene Beschreibungen etwa zwei BigInteger Werte e und N zur Spezi fikation eines ffentlichen RSA Schl ssels KeyPairGenerator ein KeyPairGenerator erzeugt ein neues Schl sselpaar KeyPair KeyFactory eine KeyFactory transformiert Schl sselbeschreibungen etwa Bin rfor mate in Key Instanzen 45 KeyStore der KeyStore eignet sich zur sicheren Aufbewahrung kryptographi scher Schl ssel Die Integrit t des Speichers sowie jeder einzelne Schl ssel werden durch Pa worte gesichert Die Art der Spe
61. eben den Teilberechnungen s erzeugen die Teilnehmer der Rekonstruk tion mithilfe der Verifikationsschl ssel noch einen Korrektheitsbeweis Bevor wir diesen Schritt erl utern wollen wir jedoch zeigen wie die s zu einem s kombiniert werden k nnen so da gilt s m damit h tten wir eine g ltige RSA Signatur oder analog eine Entschl sselung Zur Kombination berechnen wir w II sn md mod N TEN Das Endergebnis ist dann s wm mod N mit a 4L7 be 1 wie die Rechnung 2 2 se q tebe mil dae be mitt a de be ma 4L be _ m mod N zeigt die Exponenten a und b existieren da ggT e L 1 weil e gt n eine Primzahl ist Mit dem Korrektheitsbeweis k nnen die Teilnehmer nachweisen daf der diskrete Logarithmus von s zur Basis m der gleiche ist wie der diskrete 28 Logarithmus von v zur Basis v also d Nat rlich darf dabei keine zus tzliche Information ber d entstehen die Beziehung v v ist ja bereits bekannt Sei H eine Hashfunktion mit einer Ausgabe von L Bits Der Teilnehmer w hlt eine zuf llige Zahl r er 0 2F N 3L _ 1 da er die Gruppenordnung p q nicht kennt mu er mit hinreichend gro en Zahlen arbeiten und berechnet den Korrektheitsbeweis z c als AL SEH c H v m vi s2 u m und z d c r Damit kann die korrekte Berechnung von s berpr ft werden denn es mu ia 4L 2 Z C 4Lz _2c c H v e Se gelten daB mit s anstatt s gerechnet wird wir
62. ebrauch machen Zwei Unter pakete keyshare keystore gui und keyshare keystore xml stellen ei ne graphische Benutzerschnittstelle und Zugriff auf XML Konfigurations dateien bereit keyshare escrow das Paket enth lt Klassen zum Erzeugen und Wiederher stellen von wiederherstellbaren RSA und ElGamal Schl sseln siehe Ab schnitt 4 3 keyshare apps das Paket enth lt ausf hrbare Java Kommandozeilen Applika tionen mit denen Secret und Key Sharing verwendet werden kann 48 Serializable AbstractSecretShare interface AbstractSecretShareWithPass SecretShare AbstractSecretShare getldentifier byte FAbstractSecretShareWithPasswo sharesSecret boolean getThreshold int setintegriyPassword void combine bytef getShareNumberint checkintegrity boolean sharesSecret boolean identifier byte toString String threshold int equals boolean shareNumberint getEncoded bytel encoded bytel XORSecretShare XORSecretShare share XORSecretShare combine byte combine byte ShamirSecretShare ShamirSecretShare share ShamirSecretShare combine byte combine byte interface PasswordintegrityProtected checkintegrity boolean integrityPassword String evaluatePolynomial int SecretSharer Exception higintToByteArray byte higintToByteArray_1_0_ Padding SecretSharingException 4 yl N a bigIntToByteArray_PKCS1_v1_5 fixArray Sec
63. eine eigene Variante vor die zumindest zwei dieser Nachteile behebt e es existiert kein Sicherheitsbeweis f r das vorgestellte Verfahren In der Tat wird es von Frankel Gemmell MacKenzie und Yung lediglich als Heuristik bezeichnet FGPY97 Darauf aufbauend entwickeln sie noch ein weiteres Verfahren dessen Sicherheit auf das RSA Verfahren zur ck gef hrt werden kann welches allerdings Interaktionen zwischen den Teil nehmern ben tigt weshalb wir uns in dieser Arbeit nicht weiter damit besch ftigen wollen Trotz der fehlenden beweisbaren Sicherheit ist das Verfahren von anderen Autoren aufgegriffen worden MSY00 und wur de zum Beispiel auch im Rahmen eines von der TU Darmstadt und der japanischen Telefongesellschaft NTT gemeinsam entwickelten verteilten RSA Zeitstempeldienstes eingesetzt ABFT 99 die Schl sselanteile die den Teilnehmern zugestellt werden sind keine normalen RSA Schl ssel Die Exponenten die bei den partiellen RSA Berechnungen zum Einsatz kommen sind aufgrund der Multiplikationen zum Herstellen der Teilbarkeit um einige Bit l nger als normale RSA Exponenten und aufgrund der Interpolationskoeffizienten teilweise auch negativ Beides erschwert den Einsatz von kryptographischen Bibliothe ken oder Hardwareimplementierungen f r RSA Berechnungen Insbeson dere entf llt die M glichkeit der sicheren Speicherung der Teilschl ssel auf RSA f higen Chipkarten zum Berechnen der Teilergebnisse m ssen die Teilnehme
64. emeinsamen Schl ssel vereinbart haben bei dem es sich um eine zuf llige Bitfolge handelt die mindestens genauso lang ist wie die Nachricht Jedes Bit der Nachricht wird dann mit dem entsprechenden Bit des Schl ssels des One Time Pads per XOR kombiniert Beispielsweise w rde aus dem Klar text 101011 unter Verwendung des Schl ssels 100100 der Schl sseltext 001111 Danach vernichtet der Sender seine Kopie des Schl ssels Aufgrund der Ei genschaft da sich die zweifache Anwendung von XOR gegenseitig aufhebt a b b a kann der Klartext durch erneute Kombination mit dem Schl ssel durch den Empf nger wieder sichtbar gemacht werden 001111 100100 101011 F r jeden anderen ist der Schl sseltext nur eine rein zuf llige Zeichen folge Informationstheoretische Sicherheit Obwohl das One Time Pad Verfahren sehr simpel aufgebaut ist erf llt es doch das st rkste bekannte Sicherheitskri terium die informationstheoretische Sicherheit Dies bedeutet da durch die Kenntnis des Schl sseltextes und s mtlicher ffentlicher Eigenschaften des Ver fahrens keinerlei R ckschl sse auf den Klartext m glich sind weil alle denkba ren Klartexte auch bei dem vorliegenden Schl sseltext die gleiche Wahrschein lichkeit aufweisen Da dieses Forderung zuerst von Claude Shannon erhoben wurde spricht man auch von Sicherheit nach Shannon Shannon hat gezeigt da das One Time Pad Verfahren diese Eigenschaft hat Im Gegensatz dazu sind fast alle
65. ementierung wird im folgenden in ihren wesentlichen Z gen geschildert f r einen genauen Einblick sei auf die Dokumentation und den Quelltext im CVS Repositorium verwiesen Besonderer Dank gilt meinem Betreuer Alexander Wiesmaier und Professor Johannes Buchmann der f r seine Studenten auch bei ungew hnlichen Anlie gen so wie ich sie selbst in den letzten Monaten vorgebracht habe stets ein offenes Ohr hat Inhaltsverzeichnis 1 Einleitung 2 Secret Sharing 2 1 2 2 2 3 2 4 Einfaches Secret Sharing ne Redundantes Secret Sharing Verifizierbares Secret Sharing Weitergehende Eigenschaften von Secret Sharing Verfahren 3 Key Sharing 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 Public Key Kryptographie 002004 Modellierung von Key Sharing se Das RSA Verfahren Einfaches RSA Key Sharing e Redundantes RSA Key Sharing 0 Verifizierbares RSA Key Sharing 2 Das ElGamal Verfahren ke ElGamal Key Sharing se verteilte Schl sselerzeugung o 3 10 Anwendungen e 4 Schl sselverwahrung 4 1 4 2 4 3 Key Eserow u a are nenn Schl sselverwahrung wiederherstellbare Schl ssel se 5 Implementierung 5 1 5 2 5 3 5 4 Kryptographie in Java lt se berblick ber die Java Klassen Programmierschnittstelle se Applikationen a ee PO na 6 Ausblick A Abkiirzungsverzeichnis B Symbol
66. en Empf ngerschl ssel geheim zu halten blieb bestehen wenn man ihn auch nicht mehr mit anderen den Sendern teilen mu te Dazu kam das Problem die ffentlichen Schl ssel eindeutig und resistent gegen Betrugsversuche den teil nehmenden Personen zuzuordnen Mit dieser Aufgabe wurden Zertifizierungs instanzen betraut In dieser Arbeit die Teil eines gr eren Projektes zur Entwicklung einer Software zum Betrieb einer Zertifizierungsinstanz ist werden algorithmische Verfahren zum Schutz der privaten Schl ssel vor Verlust und Spionage vorge stellt Diese eignen sich insbesondere zum Schutz der wertvollen Schl ssel die von einer solchen Instanz selbst verwaltet werden und an denen folglich die Sicherheit vieler anderer Schl ssel h ngt Die meisten der im folgenden geschil derten Algorithmen haben wir auch implementiert so da sie direkt verwendet werden k nnen Kapitel 2 Secret Sharing Wenn ich mein Geheimnis verschweige ist es mein Gefangener Lasse ich es entschl pfen bin ich sein Gefangener arabisches Sprichwort Ein grunds tzliches Problem das sich beim Einsatz eines kryptographischen Systems stellt ist die sichere Verwahrung der geheimzuhaltenden Schl ssel W hrend dem Betrieb h lt ein solches System seine Schl ssel blicherweise in einem gesch tzten Speicherbereich dessen Inhalt bei einem Aussp hversuch oder sonstigem Angriff sofort unwiderbringlich gel scht wird Damit ist der Schl ssel dagegen gesch
67. en gt um das Geheimnis zur ckzugewinnen Secret Sharing Die meisten Vertreter redundanter Secret Sharing Verfahren sind sogenannte Threshold Verfahren Schwellwertverfahren Hierbei werden alle n ausgegebenen Anteile als gleichwertig betrachtet so da eine beliebige Kombination von mindestens t dieser Anteile ausreicht um das Geheimnis zu rekonstruieren Ein solches Verfahren wird dann als Secret Sharing bezeich net 2 2 1 Das Shamir Verfahren Die bekannteste Umsetzung von redundantem Secret Sharing ist das von Adi Shamir vorgeschlagene Polynominterpolationsverfahren Sha79 Um ein 1 Secret Sharing einer geheimen Zahl s zu betreiben w hlt der Geber ein zuf lli ges Polynom f x von Grad t 1 mit Achsenabschnitt f 0 s und teilt jedem Teilnehmer i den Funktionswert s f i mit Mit dem Satz von Lagrange kann dann aus t Funktionswerten das Polynom inklusive des Achsenabschnittes s rekonstruiert werden Da das Polynom iiber einer primen Restklasse ausgewer tet wird sind bei Kenntnis von weniger als t Interpolationsstellen weiterhin alle denkbaren Achsenabschnitte m glich und gleichwahrscheinlich Erzeugung der Teilgeheimnisse Der Geber w hlt zun chst eine Primzahl p die gr er ist als jede m gliche geheime Zahl s und gibt sie ffentlich bekannt Alle folgenden Berechnungen werden in der Restklasse Z pZ ausgef hrt Da p eine Primzahl ist sind insbesondere alle von Null verschiedenen Elemente der Restkl
68. en Polynome f x und f x sind t 1 Si f i 8 Y a j 1 und t 1 s f i s Yari j 1 12 Diese beiden Gleichungen k nnen durch das Commitment des Gebers an die Koeffizienten berpr ft werden es mu n mlich f r jeden Anteil s s gelten da t 1 t 1 II Ei g h Tier IR yA E gras ot pe eer aji gio pro j 0 j 1 g h mod q Rekonstruktion des Geheimnisses Die Rekonstruktion von s aus den s verl uft genau wie beim Shamir Verfahren Auf diese Weise k nnten die Teil nehmer auch s aus den s berechnen aber dies ist keine wertvolle Information Anmerkung zur Bedeutung von s Das zweite Geheimnis s dient da zu die informationstheoretische Sicherheit nach Shannon von s zu erhalten Es wirkt dabei wie ein Blendfaktor Wenn man diese Forderung nicht erhebt kann man das hnlichere aber einfachere Verfahren von Feldman Fel87 ver wenden in dem g bekannt wird Damit ist s nur noch dadurch sicher da es schwierig ist diskrete Logarithmen zu berechnen Beispielsweise kann so auch das niederwertigste Bit von s nicht mehr geheim gehalten werden Die Verifizierbarkeit der Teilgeheimnisse h ngt davon ab da der Geber bei seinem Commitment nicht betr gen kann Dazu w re er in der Lage wenn er den diskreten Logarithmus log h berechnen k nnte In diesem Fall erlangt der Geber die M glichkeit Teilnehmern fehlerhafte Anteile unterzuschieben Die Vertraulichkeit des Geheimnisses blei
69. en beispielsweise angegeben wird auf wieviele und welche Dateien der Keystore seinen Inhalt verteilen soll eine Beschreibung der m gli chen Einstellungen findet sich in Abschnitt 5 4 Diese Dateien werden mit Hilfe des Castor XML Frameworks ausgewertet Dieses stellt ein Mapping zwischen XML Tags und Java Klassen bereit Die entsprechenden Klassen liegen im Pa ket keyshare keystore xml ShamirStore diese Klasse entspricht dem lt shamir store gt XML Tag welches das Wurzel Element fiir die Konfigurationsdatei des ShamirStore dar stellt Es besitzt einige Attribute und kann geschachtelte lt share gt Tags aufnehmen KeySharer diese Klasse entspricht dem lt key sharer gt XML Tag welches das Wurzel Element fiir die Konfigurationsdatei des KeySharers darstellt Es besitzt einige Attribute und kann geschachtelte lt share gt Tags aufnehmen Share diese Klasse entspricht dem lt share gt Tag welches in beiden Konfigura tionsdateien verwendet wird um den Anteilen ihre Dateien zuzuordnen Konfiguration nur ber Dateien Die beiden KeyStores k nnen nur ber die XML Dateien konfiguriert werden Dies geschieht durch Einlesen der Da teien w hrend der Methode KeyStore load InputStream char Fiir eine 57 KeyStoreSpi Key StoreBase FmakekeyStore void FloadKeyStore void FloadKeyStore void FgetEncodedKeyStore bytel encodeKeyStore void engineAliases Enumeration engineContainsAlias boolean engineDeleteEntry void eng
70. erfahren eine echte Alternative zum RSA Verfahren selbst wenn eines der Verfahren aufgrund neuer Erkenntnisse unsi cher werden sollte muf das andere davon nicht betroffen sein Dariiberhinaus l t sich das ElGamal Verfahren leicht auf andere Gruppen als Z pZ ber tragen in denen das Diffie Hellman und das Diskrete Logarithmus Problem andere L sungsans tze erfordern Am bekanntesten sind hierbei die Elliptischen Kurven deren Struktur k rzere Schl ssell ngen im Vergleich zu ElGamal ber Z pZ zulassen 29 Schliisselerzeugung Um ein ElGamal Schl sselpaar zu erzeugen w hlt der Schliisselgenerator eine Primzahl p und bestimmt eine Primitivwurzel g aus Z pZ dies ist ein Element aus Z pZ dessen Potenzen die ganze Gruppe Z pZ erzeugen Dann w hlt er zuf llig und gleichverteilt den geheimen Ex ponenten a aus 1 p 2 und berechnet den ffentlichen Schl ssel p g A mit A g mod p Die Gr e von p bestimmt die Sicherheit des Verfahrens Es mu unm glich gemacht werden diskrete Logarithmen in Z pZ zu berechnen Zur Zeit gelten 1024 Bit Schl ssel als hinreichend sicher Schl sselverwendung Wie beim RSA Verfahren k nnen auch ElGamal Schliis sel fiir zwei unterschiedliche Operationen n mlich Verschltisselung und Signatur herangezogen werden Im Unterschied zu RSA sind hierbei jedoch zwei verschie dene Algorithmen anzuwenden Um eine Nachricht m fiir den Empf nger mit dem ffentlichen Schliissel
71. erpolation 10 Pretty Awful Privacy 40 PrivateKeyShare 53 Provider 54 Public Key Kryptographie 16 RedundantElGamalPrivateKeyShare 54 RSA 19 Assumption 19 Sicherheit des Verfahrens 19 RSAKeyPairGenerator 60 RSAPKCS1_v1_5 56 Schliisselerzeugung ElGamal 30 Teilschl ssel 31 wiederherstellbar 43 RSA 20 Teilschliissel 21 23 26 27 wiederherstellbar 40 verteilt 32 Schliisselverwendung ElGamal 30 verteilt 32 RSA 20 verteilt 22 24 26 28 Secret Sharing 7 ideal 14 ohne Geber 14 Pedersen Verfahren 11 perfekt 13 proaktiv 14 redundant 9 14 robust 14 Shamir Verfahren 10 blockweise 50 verifizierbar 11 XOR Methode 9 SecretShare 49 SecretSharer 50 SecretSharerTests 64 SecretSharingException 50 SETUP 39 SHA1withRSA 56 ShamirSecretShare 50 93 ShamirStore 57 67 ShamirStoreTests 64 Shannon 8 Share 57 ShareSelector_Load 59 ShareSelector_Store 59 Shoup 27 ShoupRSAPrivateKeyShare 53 Sicherheit berechnungssicher 8 informationstheoretisch 8 SignatureBase 56 SimpleElGamalPrivateKeyShare 53 SimpleRSAPrivateKeyShare 53 SSL 77 StrongRSAKeyPairGenerator 56 StrongRSAPrivateCrtKey 56 Threshold Cryptography 18 UndecryptableKeyException 60 Util 50 wiederherstellbare Schliissel 39 X 509 77 X509 54 X509Tests 64 XML 78 XORSecretShare 50 Literaturverzeichnis AAB 97 ABF 99 BF97 Bla79 CKLW00 DF 90 DH76 ElG85 Fe
72. et Sharing Teil des Pakets Util diese Klasse enth lt einige statische Hilfsmethoden die von anderen Klas sen verwendet werden k nnen blockweises Shamir Secret Sharing In der Schilderung des Shamir Ver fahrens in Abschnitt 2 2 1 sind wir davon ausgegangen da sich das Geheimnis einfach als Zahl auffassen und durch ein Polynom verteilen l t Dies ist bei Geheimnissen die mehr als nur ein paar Byte lang sind zwar m glich aber unpraktikabel Sinnvoller ist es das Geheimnis in mehrere Bl cke aufzuteilen und diese einzeln zu verteilen Dabei ergibt sich f r jeden Block ein neues Po lynom Die Blockgr e kann beliebig gew hlt werden so da man sich bei den Berechnungen auf Zahlenbereiche beschr nken kann die vom Computer effi zient bearbeitet werden k nnen In unserer Implementierung haben wir das Geheimnis byteweise verteilt Durch vorgeschaltete Base64 Kodierung bestan den die Bytes des Geheimnisses nur aus druckbaren ASCII Zeichen so da wir Polynome modulo 127 verwenden konnten Durch den festen Moduln konnten wir auch die notwendigen Invertierungen als Vorberechnungen ausf hren und in einer Tabelle in das Programm integrieren 50 MD5 zum Berechnen der ID Jedes SecretShare verf gt ber eine ID die es erm glicht zusammengeh rige S tze von Anteilen zu erkennen Diese ID ergibt sich durch einen Hashwert ber das jeweilige Geheimnis und wird beim Erzeugen der Anteile dem Aufteilen des Geheimnisses berechnet Wi
73. eten Logarithmen basieren wie etwa ElGamal Abschnitt 3 7 Dies liegt daran da diese Signaturen randomisiert werden m ssen so da eine Verteilung die Synchronisation der verwendeten Zufallszahlen notwendig macht Verteilte Entschl sselungen bleiben weiterhin m glich 3 3 Das RSA Verfahren Das erste und weitaus erfolgreichste Public Key Verfahren ist das von Ronald Rivest Fiat Shamir und Leonard Adleman 1977 vorschlagene RSA Verfahren RSA78 Es beruht auf dem RSA Problem einem mathematischen Problem das mit dem Problem der Zerlegung gro er Zahlen in ihre Primfaktoren ver wandt ist RSA hat eine enorme Verbreitung erfahren und wird heute in fast allen Public Key Produkten eingesetzt Die RSA Annahme Die Sicherheit des RSA Verfahrens beruht auf der An nahme da es keinen effizienten Algorithmus gibt um das sogenannte RSA Problem zu l sen Das RSA Problem besteht darin f r eine gegebene ganze Zahl c und einen Moduln N eine ganze Zahl m zu bestimmen so da c m mod N f r einen ebenfalls bekannten Exponenten e Dabei ist N pq das Produkt zweier gro er 19 Primzahlen die aber nicht bekannt sind und e ist ein sogenannter invertierbarer Exponent modulo N das Inverse von e ist allerdings auch nicht bekannt Eine M glichkeit die Zahl m zu bestimmen besteht darin N zu faktorisie ren Dann l t sich ein Element d berechnen mit de 1 mod p 1 q 1 und es gilt c m4 m mod N Somit ist das RSA Problem
74. ey sharer threshold 2 gt lt share file 1a keystore gt lt share file 2b keystore gt lt share file 3c keystore gt lt key sharer gt Fiir jeden Anteil der erzeugt werden soll gibt es ein geschachteltes lt share gt Tag welches den Namen der Datei angibt die diesem Anteil zugeordnet wird Die Anzahl der aus Anteilen erzeugten Teilsignaturen oder entschliisselungen die ben tigt werden um das Gesamtergebnis erhalten zu k nnen wird durch das Attribut threshold festgelegt Instanz erzeugen KeyStore ks KeyStore getInstance KeySharer Keystore laden Der KeySharer l dt die abh ngigen Keystores aus den in der Konfigurationsdatei bezeichneten Dateien wenn seine 1oad Methode auf gerufen wird Die Konfigurationsdatei muf ihm iiber den InputStream dieser Methode zugef hrt werden Ein ebenfalls angegebenes Pa wort wird dazu ver wendet die Integrit t dieser Keystores zu priifen Obwohl die abh ngigen Key stores geladen werden werden die darin enthaltenen Teilschliissel nicht wieder zusammengesetzt Das Laden dient nur dazu die Keystores um neue Schliissel zu erganzen FileInputStream in new FileInputStream configuration xml ks load in password in close Wenn das Laden aufgrund fehlender oder fehlerhafter Anteile fehlschl gt wird eine IOException geworfen Keystore verwenden Der KeySharer eignet sich nur zum Speichern von Schl sseln Zertifikatseintr ge k nnen nicht angelegt werden au
75. f die H lfte der L nge von N beschr nkt ist Wenn man hierf r ebenfalls RSA einsetzen will mu man Benutzerschl ssel erzeugen die doppelt so lang sind wie der Recovery Schl ssel Dies ist sicher eine etwas ung nstige Situation Im folgenden gehen wir davon aus da der Recovery Schl ssel ein RSA Schl ssel mit Modul Nr und Exponenten dp und ep ist Der Generator erzeugt zun chst die zuf llige Primzahl p Diese Primzahl p wird anschlie end durch eine symmetrische Chiffre F mit festem Schl ssel K in eine Zahl p berf hrt Der Schl ssel K ist dabei fest in den Generator integriert Er mu nicht ge 41 heimgehalten werden da die Chiffre F nur der Randomisierung von p gilt Falls p kein g ltiger RSA Klartext f r die Recovery Chiffre ist es mu gelten p lt Np so wird der Schl ssel K um eins weitergez hlt K K 1 und H wird erneut berechnet Diese zweite Funktion der Chiffre F vermeidet das h ufige Suchen nach geeigneten Primzahlen p und senkt so die Rechenzeit Erst nach einer bestimmten Anzahl an Iterationen B wird abgebrochen und das Verfahren neu gestartet mit der Suche nach einem neuen p Sobald ein g ltiges p gefunden wurde wird dieses mit dem Backup Schliissel verschl sselt Von dem entstehenden Schl sseltext c p mod Np wird nun erneut durch die symmetrische Chiffre F mit anf nglichem Schl ssel K eine Reihe von Kandidaten c f r die obere H lfte von N erzeugt jeweils durch Weiter
76. f hin da wir in dieser Darstellung unterschlagen haben da die Berechnungen des Shamir Verfahrens in einer primen Restklasse zu erfolgen haben was zu einigen technischen Problem f hrt auf die wir sp ter eingehen werden Die bekanntesten Public Key Verfahren setzen auf dem RSA siehe Ab schnitt 3 3 oder dem ElGamal Verfahren siehe Abschnitt 3 7 auf Beide Ver fahren erf llen die geschilderte Homomorphie Eigenschaft und eignen sich somit f r Key Sharing Ein Key Sharing Verfahren auf Basis eines Secret Sharing Verfahrens wird auch als Threshold Cryptography bezeichnet Ablauf eines Key Sharing In der Literatur lassen sich verschiedene Mo dellierungen der Vorg nge und Teilnehmer eines Key Sharing finden In dieser Arbeit gehen wir von einer Situation aus in der e es einen Geber gibt dem alle Teilnehmer vertrauen und dessen Aufgabe es ist einen zuvor von ihm selbst oder au erhalb des Modells erzeugten privaten Schl ssel zu verteilen e zur Erzeugung der Teilschl ssel ein 5 Verfahren eingesetzt wird e der Geber mit niemandem w hrend der Berechnung der Teilschl ssel kom muniziert e der Geber die Teilschl ssel auf einem abh rsicheren Kanal an die Teilneh mer bermittelt e der Geber sich nach der erfolgten bermittlung der Teilschl ssel zur ck zieht e die Teilnehmer ihre Teilschl ssel so verwalten als handelte es sich dabei um ihre privaten Schl ssel 18 e die Teilnehmer mit ihren Teilschl
77. g Eine spezielle Anforderung n mlich die Verwendbarkeit geteilter Schl ssel ohne deren jemalige Rekonstruk tion wird uns dann im n chsten Kapitel besch ftigen 2 1 Einfaches Secret Sharing Eine sehr einfache Methode eine geheime Information unter mehreren Teil nehmern zu verteilen basiert auf der Idee der One Time Pad Verschl sselung Hierbei wird das Geheimnis in eine Reihe von Summanden aufgeteilt und kann dann als Summe dieser Summanden wiederhergestellt werden Die einzelnen Summanden sind rein zuf llig und enthalten keinerlei Information ber das Ge heimnis Das Verfahren l t sich sehr effizient implementieren und ist beweisbar sicher Allerdings werden s mtliche Teilnehmer ben tigt um das Geheimnis zu rekonstruieren 2 1 1 One Time Pad Verschliisselung Bei diesem Verfahren handelt es sich um ein Verschl sselungsverfahren das hei t es beschreibt wie ein Sender eine Nachricht derart verschl sseln kann da nur ein authorisierter Empf nger die Nachricht wieder entschl sseln kann Der Empf nger wird dadurch authorisiert da er sich mit dem Sender vorab auf einen gemeinsamen Schliissel zur Ver und Entschliisselung der Nachricht geeinigt hat man bezeichnet ein solches Verschliisselungsverfahren als symme trisch Bei der Beschreibung des Verfahrens wollen wir davon ausgehen da es sich bei der Nachricht um eine Bitfolge handelt Um eine Nachricht zu verschl sseln m ssen Sender und Empf nger vor ab einen g
78. he ACM 21 2 120 126 1978 ADI SHAMIR How to Share a Secret Communications of the ACM 22 11 612 613 November 1979 VICTOR SHOUP Practical Threshold Signatures In Theory and Application of Cryptographic Techniques S 207 220 2000 THOMAS Wu MICHAEL MALKIN und DAN BONEH Building In trusion Tolerant Applications In Proceedings of the 8th USENIX symposium S 79 91 1999 ADAM YOUNG und MOTI YUNG The Dark Side of Black Box Cryp tography Advances in Cryptology CRYPTO 96 S 89 103 1996 ADAM YOUNG und MOTI YUNG Kleptography Using Cryptography Against Cryptography Advances in Cryptology EUROCRYPT 97 1233 62 74 1997 LIDONG ZHOU FRED B SCHNEIDER und ROBBERT VAN RENESSE COCA A secure distributed on line certification authority Techni scher Report Department of Computer Science Cornell University 2000 95
79. i der Schliisselwiederherstellung der Schl ssel nicht ent schliisselt werden konnte zum Beispiel weil der Recovery Schliissel nicht vorlag Die Klasse kapselt dabei die verschliisselte Datei die dann an an dere Applikationen weitergereicht werden kann PKCS12 diese Klasse enth lt statische Methoden zum Zugriff auf PKCS12 Daten PKCS12 ist ein Standard f r Softtoken also dateibasierte Tr ger vertrau licher Informationen Die Key Escrow Applikation und die FlexiTrust Trustcentersoftware benutzen PKCS12 als Transportformat fiir Schliissel 5 2 5 Paket keyshare apps Das Paket keyshare apps enth lt drei ausf hrbare Java Kommandozeilen Appli kationen mit denen Secret und Key Sharing verwendet sowie Key Escrow durch gef hrt werden k nnen Dies sind der FileSharer mit dem beliebige Dateien nach dem Shamir Verfahren in mehrere Anteile aufgeteilt werden k nnen der KeySharer der sich zum Erzeugen verteilter Schl ssel von Teilsignaturen und entschl sselungen sowie deren Kombination eignet und KeyEscrow mit dessen Hilfe Schl ssel hinterlegt und rekonstruiert werden k nnen Die Funktionsweise der Programme ist in den Abschnitten 5 4 1 5 4 2 und 5 4 3 beschrieben CommandLineApp diese abstrakte Basisklasse stellt einige Grundfunktionalit t zum Auswerten der Kommandozeilenparameter fest und bestimmt mit Schablonenmethoden den groben Ablauf der drei davon abgeleiteten Appli kationen ApplicationMode CommandLineApp geht davon aus
80. icherung ist je nach Implementierung unterschiedlich Sun liefert eine propriet te dateibasier te Implementierung den Java KeyStore JKS Andere M glichkeiten sind PKCS12 oder Chipkarten 5 1 2 Zertifikate Um Public Key Kryptographie sinnvoll betreiben zu k nnen ist der Umgang mit Zertifikaten unerl lich Diese beinhaltet die M glichkeit die bin r kodier ten Zertifikate einlesen und auswerten zu k nnen also ffentliche Schl ssel zu entnehmen Signaturen zu pr fen Aussteller zu identifizieren und Zertifikats inhalte Erweiterungen und Einschr nkungen zu behandeln Certificate diese Basisklasse stellt ein Public Key Zertifikat dar X509Certificate als Erweiterung von Certificate handelt es sich hierbei um ein Zertifikat nach dem X 509 Standard Es gibt unter anderem Methoden um den Inhaber und seinen ffentlichen Schl ssel den Aussteller oder den G ltigkeitszeitraum zu erfahren sowie um die Signatur zu pr fen hierzu mu der ffentliche Schl ssel des Ausstellers vorliegen CRL diese Klasse repr sentiert eine Revokationsliste certificate revocation list Hier sind Zertifikate aufgef hrt die f r ung ltig erkl rt wurden Es gibt auch eine Unterklasse f r X 509 Revokationslisten CertificateFactory eine CertificateFactory erzeugt Certificate Instanzen aus Eingabestr men zum Beispiel aus Dateien KeyStore neben der Speicherung von Schl sseln dient ein KeyStore auch da zu vertrauensw rdige Zertifikate
81. ignatur standard DSS inklusive Schliisselerzeugung beschreiben Gennaro Jarecki Kra wczyk und Rabin GJKR96 Dieses System unterst tzt auch die M glichkeit der proaktiven Erneuerung der Anteile 3 10 Anwendungen Fiir die geschilderten Techniken lassen sich eine Reihe von Anwendungen nen nen In der Literatur h ufig angefiihrt werden private Schliissel die keinen ein zelnen Personen geh ren sondern Unternehmen zuzuordnen sind In diesem Fall k nnten zum Beispiel eine Gruppe fiihrender Angestellter gemeinsam tiber einen Signaturschl ssel verf gen k nnen sollen Da diese Diplomarbeit im Rahmen des FlexiTrust Projektes entstanden ist welches sich mit der Entwicklung einer Trustcenter Software zum Betrieb einer Zertifizierungs und Registrierungsstel le besch ftigt haben wir uns vor allem f r Einsatzm glichkeiten in einer CA interessiert Die beiden wesentlichen Aufgabenbereiche sehen wir im Schutz des CA Schl ssels mit dem Zertifikate ausgestellt werden und der Recovery Schl ssel mit denen Benutzerschl ssel wiederhergestellt werden k nnen falls die CA Benutzerschl ssel verwahrt Die konsequenteste M glichkeit w re sicherlich die Verteilung der von der CA durchgef hrten Signaturen auf mehrere Rechner die jeweils mit einem Teil schl ssel ausgestattet sein w rden Dies war allerdings in den Planungen f r die FlexiTrust Software nicht vorgesehen und h tte gr ere nderungen zur Folge gehabt Statt dessen sollte le
82. ilhaber in die Lage zu versetzen die kryptographischen Operationen mit ihren Teilschl sseln auszuf hren so da die Ergebnisse anschlie end kombiniert werden k nnen Dabei behalten sie die Kontrolle ber ihre Teilschl ssel die sie nicht offenbaren m ssen Das Shamir Verfahren und homomorphe Funktionen Eine kryptogra phische Operation etwa eine Entschl sselung oder Signatur ist eine Funktion g x k deren Ergebnis von einer Eingabe x beispielsweise der Nachricht und einem Schl ssel k abh ngt Viele Kryptosysteme haben die Eigenschaft da diese Funktion homomorph ist also g x ky k2 g x k g a k2 17 dies mu nicht unbedingt f r die gesamte Operation gelten es reicht wenn eine wesentliche Komponente davon homomorph ist Hashfunktionen und Padding kann man hierbei oft au er acht lassen Diese Homomorphie l t sich gut mit dem Shamir Secret Sharing verkn pfen denn dort wird der Schl ssel k verteilt als k gt Ab EA so da g x k verteilt ausgewertet werden kann g x k g x K Mia ki II g x A aki IT g x ky ied ic A ied Dadurch wird es m glich da die Teilnehmer jeder f r sich g x k berech nen und das Ergebnis an einen Kombinierer bermitteln der das Endergebnis g x k bestimmen kann wenn er gen gend Teilergebnisse erh lt Dazu ben tigt der Kombinierer keinerlei geheime Informationen lediglich die Identit t der Teilnehmer ihre Nummern i Wir weisen darau
83. ineGetCertificate Certificate engineGetCertificateAlias String engineGetCertificateChain Certifid engineGetCreationDate Date engineGetkey Key enginelsCertificateEntry boolean enginelsKeyEntry boolean engineSetCertificateEntry void engineSetkeyEntry void engineSetkeyEntry void engineSize int Share KeySharer ShamirStore ShareSelector Load ShareSelector Store IntegrityPassword CancelFinishedButtons engineLoad void engineLoad void engineSetKeyEntryvoid engineStore void engineStore void share PrivateKeyll Abbildung 5 4 Klassen aus dem Paket keyshare keystore 58 ES Distribute the keystore E Joj x distribute with E Out of E secret sharing Y protect the shares with the integrity password Cancel Finish Abbildung 5 5 Dialog zum Anlegen von Anteilen des Shamir Store direkte Kontrolle des KeyStores durch das Programm in dem es verwendet wird ist dies etwas umst ndlich In einem solchen Fall mu zun chst eine ent sprechende XML Datei zumindest im Speicher erzeugt werden Angenehmer w ren Methodenaufrufe auf der KeyStore Instanz zur Parameterwahl etwa ei ne Methode setThreshold int Dies ist allerdings aufgrund der Vorgaben durch die JCA nicht m glich Unsere Implementierung wird als KeyStoreSpi von JCA internen Klassen instantiiert und nicht f r die Anwendung zug nglich gemacht Eine Erweiterung der Schnittstelle ber die seitens J
84. iner von beiden und auch kein Dritter die Nachricht rekonstruieren und verf gt nur ber eine zuf llige Bitfolge Mit der in Abschnitt 2 2 eingef hrten Sprechweise haben wir es hier mit einem 5 Secret Sharing Verfahren zu tun Das Verfahren l t sich leicht auf beliebig viele Teilnehmer verallgemeinern Um eine geheime Information s gl Helm 2 dal mit m Bits auf t Teil nehmer zu verteilen erhalten alle Teilnehmer bis auf den letzten jeweils einen m bit langen Zufallsstring gt j Si ll ll sll Er 0 1 1 lt i lt t und der letzte Teilnehmer erh lt die XOR Summe st Tar S so s sil y s SU aller anderen Anteile mit dem Geheimnis Damit l t sich bei Vorliegen aller i Teilgeheimnisse s jedes Bit sl von s als sl D s zuriickgewinnen 2 2 Redundantes Secret Sharing Wie wir gesehen haben erm glicht es die XOR Methode ein Geheimnis auf mehrere Orte zu verteilen wodurch es wesentlich besser dagegen gesch tzt ist aufgedeckt zu werden Auf diese Weise wird das Sicherheitsproblem einer repli zierten Speicherung umgangen Ungl cklicherweise geht aber auch der Vorteil einer Replikation verloren n mlich die Robustheit gegen den Verlust einzelner Anteile Sobald auch nur einer der Anteile der XOR Methode nicht mehr zur Verf gung steht kann das Geheimnis nicht mehr rekonstruiert werden Diesem Mangel treten redundante Secret Sharing Verfahren entgegen bei denen bereits eine Teilmenge der Anteile g
85. ines RSA Schliisselpaares werden zwei zufallige Primzah len p und q gew hlt deren Produkt N pq den RSA Modulus ergibt sowie zwei Exponenten d und e mit de 1 mod p 1 q 1 f r Details des RSA Verfahrens siehe Abschnitt 3 3 Die Primzahlen p und q werden im Laufe 40 des Verfahrens nicht mehr ben tigt au er um Berechnungen mit dem priva ten Schl ssel zu beschleunigen und m ssen nicht gespeichert werden Da die Kenntnis der Faktorisierung von N ausreichend ist um d aus e zu berechnen sind p und q auf jeden Fall geheim zu halten Die hier geschilderten Verfahren bringen eine verschl sselte Version von p in den ffentlichen Schl ssel ein so da der Recovery Operator daraus den Primfaktor p und damit auch g Y p entschl sseln und den privaten Exponenten d berechnen kann Verschl sselung im Exponenten e Das einfachere der beiden hier geschil derten Verfahren erzeugt p und q genauso wie ein normaler RSA Schl sselgene rator Der Algorithmus enth lt den ffentlichen Backup Schl ssel des Recovery Operators Mithilfe dieses Schl ssels verschl sselt er den Faktor p und erh lt einen Chiffretext c Um die Sicherheit des Verfahrens nicht von anderen Algo rithmen abh ngig zu machen sollte es sich bei dem Backup Schl ssel ebenfalls um einen RSA Schl ssel handeln Falls die Verschl sselung c teilerfremd zu p 1 q 1 ist setzt der Generator den ffentlichen Exponenten e c Falls nicht verschl ssel
86. it Informationen ber s oder al preiszugeben E s s g h mod q Das Commitment an den ffentlich gemachten Wert E s s kann durch Of fenlegung von s und s berpr ft werden Es kann gezeigt werden da es unm glich ist das Commitment zu f lschen ohne log h zu kennen Ped92 Dieses Commitment Verfahren wird nun mit dem Shamir Verfahren kombiniert Dabei verteilt der Geber neben dem eigentlichen Geheimnis s eine zweite Zahl s und gibt ein Commitment f r die beiden dabei benutzten Polynome ab Das Commitment kann dann von jedem Teilnehmer anhand seines Anteils s si berpr ft werden Erzeugung der Teilgeheimnisse Um die geheime Zahl s Z pZ zu ver teilen w hlt der Geber zuf llige Koeffizienten a Er Z pZ 1 lt j lt t 1 wodurch sich das Polynom Has aie sk aja mod p ergibt Zus tzlich verteilt der Geber die zuf llige Zahl s Z pZ auf analoge Weise durch ein vollst ndig zuf lliges Polynom t 1 f x a x ab x mod p Jeder Teilnehmer i 1 n erh lt die Funktionswerte s f i und s f i als seinen Anteil des Geheimnisses AuBerdem gibt der Geber ein Commitment an die beiden Polynome ab indem er Fo E s s g h mod q und e Ej Elaj aj g h i mod q Dei lt j lt t 1 ver ffentlicht Verifikation eines Teilgeheimnisses Ein Teilgeheimnisses s s ist genau dann g ltig wenn die beiden Werte tats chlich St tzstellen der vom Geber gew hlt
87. iteren wird darauf hingewiesen da die M glichkeit zum Key Recovery mi braucht und beispielsweise nicht nur im Kampf gegen das organisierte Ver brechen sondern auch gegen politische Gegner eingesetzt werden k nnte Nicht jeder vertraut seiner Regierung so weit da er ihr weitere Mittel zur Kontrolle der B rger zur Verf gung stellen m chte Eine nicht staatliche oder gar private Organisation wird man mit der Aufgabe ebensowenig betrauen wollen In der letzten Zeit haben es die Regierungen aufgegeben die Kontrolle ber kryptographische Algorithmen behalten zu wollen Gerade das Aufkommen frei verf gbarer Kryptosoftware macht jede Art von Reglementierung schwierig Ei ne Umkehr hierbei m te gegen den erbitterten Widerstand der Wirtschaft und der radikalen Verfechter freier Software die jede Art von Zensur Exportbe schr nkung oder auch nur Patentierung ablehnen durchgef hrt werden zudem auch noch auf internationaler Ebene Und selbst wenn es gel nge alle am Markt erh ltlichen Kryptoprodukte zu reglementieren darf man vermuten da gerade Kriminelle sich nicht an die Vorschriften bez glich legaler Kryptographie hal ten und statt dessen illegale Produkte einsetzen mit denen kein Key Recovery m glich ist technische Einw nde Es gibt auch eine Reihe Einw nde technischer Na tur die gegen Key Escrow Systeme vorgebracht wurden In einer gemeinsamen Erkl rung AAB 97 zu Key Escrow zur Unterst tzung der Arbeit von Straf verf
88. kasten vorstellen CKLWO00 S 8 Jedermann der im Besitz des ffent lichen Schl ssels ist kann einen Brief hineinwerfen Aber nur der Empf nger als Besitzer des privaten Schl ssels kann den Briefkasten ffnen und den Brief wieder herausnehmen Neben dem vereinfachten Schl sselmanagement bieten asymmetrische kryp tographische Verfahren auch die M glichkeit digitaler Signaturen Hierbei er zeugt der Absender f r das zu signierende Dokument mithilfe seines privaten Schl ssels eine Signatur die fortan von jedem unter Verwendung des ffentli chen Absenderschl ssels berpr ft werden kann Die bekannteste konkrete Umsetzung von Diffies und Hellmans Idee ist das nach seinen Erfindern Ronald Rivest Fiat Shamir und Leonard Adleman be nannte RSA Verfahren RSA78 das wir in Abschnitt 3 3 erl utern wollen Fast berall wo heute asymmetrische Kryptographie zum Einsatz kommt handelt es sich um RSA 3 2 Modellierung von Key Sharing Das wichtigste Einsatzgebiet von Secret Sharing ist die sichere Verwahrung und Verwendung von privaten Schl sseln eines Public Key Kryptosystems Durch simple Secret Sharing Verfahren kann ein solcher Schl ssel sicher auf mehrere Teilhaber aufgeteilt und von diesen verwahrt werden Soll der Schl ssel aller dings eingesetzt werden zum Beispiel um eine digitale Signatur zu leisten so mu er an einem Ort rekonstruiert werden wodurch er wieder sehr angreifbar wird Die Idee des Key Sharings ist es die Te
89. key FengineGeneratePrivate PrivateKe tengineGetKeySpec KeySpec engineTranslateKey Key Provider initialize void generateKeyPair KeyPair StrongRSAPrivateCriKey publicExponent BigInteger primeP Biginteger prime BigInteger primeP1 Biglnteger prime01 Biglnteger primeExponentP Biglnteger primeExponent Biginteger crtCoefficient Biglnteger privateExponentBiginteger modulus BigInteger algorithm String format String encoded kyte Abbildung 5 3 JCA Kompatibilit tsklassen aus dem Paket keyshare jca 55 Provider dieser JCA Provider meldet die implementierten Algorithmen ent sprechend der JCA Namenskonventionen an StrongRSAPrivateCrtKey diese Klasse erweitert einen JCA RSAPrivateCrtKey und repr sentiert einen privaten RSA Schliissel mit zwei Primfaktoren der Gestalt p 2p 1 und q 2q 1 Solche Schl ssel werden vom Shoup Verfahren ben tigt ExtendedElGamalPrivateKey diese Klasse erweitert ElGamalPrivateKey aus dem FlexiProvider und repr sentiert einen privaten ElGamal Schl ssel mit einem Modul der Form p mq 1 wie er vom redundanten ElGamal Key Sharing Verfahren ben tigt wird KeyFactory diese Klasse dient zum Erzeugen von PrivateKeyShare Instanzen aus ihren PKCS8 Repr sentationen StrongRSAKeyPairGenerator dieser Schl sselgenerator erzeugt RSA Schl ssel paare mit einem StrongRSAPrivateCrtKey SignatureBase diese abstrakte Klasse stellt Default Implementierungen fiir die Methoden eines
90. l87 HAL ABELSON Ross ANDERSON STEVEN M BELLOVIN JOSH BENALOH MATT BLAZE WHITFIELD DIFFIE JOHN GILMORE PETER G NEUMANN RONALD L RIVEST JEFFREY I SCHILLER und BRUCE SCHNEIER The risks of key recovery key escrow trusted third party encryption http www cdt org crypto risks98 1997 A report by an ad hoc group of cryptographers and computer scientists HELO APPEL INGRID BIEHL ARNULPH FUHRMANN MARKUS RUPPERT TSUYOSHI TAKAGI AKIRA TAKURA und CHRISTIAN VALENTIN Ein sicherer robuster Zeitstempeldienst auf der Basis verteilter RSA Signaturen Technischer Report TI 22 99 Fachge biet Theoretische Informatik TU Darmstadt 1999 DAN BONEH und M FRANKLIN Efficient generation of shared RSA keys Advances in Cryptology CRYPTO 97 S 425 439 1997 G R BLAKLEY Safeguarding cryptographic keys In Proc AFIPS 1979 National Computer Conference S 313 317 AFIPS 1979 INGMAR CAMPHAUSEN STEFAN KELM BRITTA LIEDTKE und LARS WEBER Aufbau und Betrieb einer Zertifizierungsinstanz Deutsches Forschungsnetz DFN PCA Vogt K lln Stra e 30 22527 Hamburg Marz 2000 Yvo DESMEDT und YAIR FRANKEL Threshold cryptosystems Ad vances in Cryptology CRYPTO 89 435 307 315 1990 WHITFIELD DIFFIE und MARTIN E HELLMAN New Directions in Cryptography IEEE Transactions on Information Theory IT 22 6 644 654 1976 TAHER ELGAMAL A public key cryptosystem and a signature sche me based on discrete logarithms IEEE
91. lanteilen sowie einen JCA Provider der die neuen Algorithmen anmeldet und dadurch verf gbar macht Dar berhin aus werden die speziellen Schl ssel die vom Shoup und vom redundanten ElGamal Key Sharing Verfahren ben tigt werden bereitgestellt Die Struktur der im folgenden kurz beschriebenen Klassen und Schnittstellen ist in Abbil dung 5 3 dargestellt 54 SignatureSpi E SignatureBase CipherSpi CipherBase enginelnitverityvoid enginelnitSign void FengineUpdate void FengineUpdate void engineSign byte engineVerify boolean engineSetParameter void engineGetParameter Object signatureAlgorithmName Strin MD5withRSA SHA1withRSA engineSetMode void engineSetPadding void engineGetBlockSize int engineGetOutputSize int engineGetl byte engineGetParameters Algorith enginelnitwoid enginelnit void enginelnitvoid engineUpdate byte engineUpdate int engineDoFinal byte engineDoFinal int cipherAlgorithmName String RSAPKCS1v15 ElGamal signatureAlgorithmName Strin signatureAlgorithmName Strin cipherAlgorithmName String java security Provider KeyPairGeneratorSpi Provider StrongRSAKeyPairGenerator cipherAlgorithmName String RSAFrivateCrtkey StrongRSAPrivateCrtKey ElGamalPrivateKey ExtendedElGamalPrivateKey KeyFactorySpi KeyFactory ExtendedElGamalPrivateKey q Biginteger encoded bytel engineGeneratePublic Public
92. lige Primzahlen p und q die der zus tzlichen Eigenschaft gen gen da p 2 1 und q 2q 1 f r zwei weitere Primzahlen p und o Man nennt solche Primzahlen p und q starke Primzahlen Dadurch ergibt sich der RSA Modul N pq Den ffent lichen Exponenten e w hlt der Geber als beliebige Primzahl e gt n F r den Sicherheitsbeweis ist es wichtig daB alle Teilberechnungen nicht ber der gan zen Gruppe Z NZ ausgef hrt werden sondern nur ber den Quadraten aus Z NZ Die Quadrate aus Z NZ bilden eine zyklische Untergruppe Oder Ordnung p q so da die Exponenten f r Elemente aus Qymodulo ga gerech net werden k nnen Folglich wird der private Exponent d auch derart bestimmt da de 1 mod ga gilt und nicht modulo p 1 q 1 F r diesen Ex ponenten d wird nun wie beim Shamir Verfahren ein Polynom f x d aix a 1x mod p q mit a Er 1 p d 1 konstruiert Wir stellen fest da hier nicht ber einem Primk rper gerechnet wird so da nicht alle Elemente invertierbar sind Es wird sich aber zeigen da das Verfahren keine Invertierungen ben tigt Sei nun L N die Bitl nge von N und L die Bitl nge der Ausgabe einer kryptographischen Hashfunktion also beispielsweise 160 F r jeden Teilneh mer w hlt der Geber die Teilschl ssel d zuf llig aus der Menge di ER x 0 lt lt 2th zs f i mod gail Um die Berechnungen der Teilnehmer sp ter verifizieren zu k nnen w hlt der Ge
93. m gehalten werden aber das ndert nichts daran da sich gewisse Elemente nicht invertieren lassen Es gibt verschiedene Vorschl ge wie dieses Problem umgangen werden kann Man kann das ElGamal Verfahren in anderen Zahlk rpern durchf hren etwa Z pZ mit p 2 und p 1 prim ein anderes Secret Sharing Verfahren anwenden DF90 oder hnlich wie im Pedersen Verfahren aus Abschnitt 2 3 1 in einer primen Untergruppe G von Z pZ rechnen Ped91 Wir verwenden hier letztere Vorgehensweise Wenn die Primzahl p sich als p mq 1 darstellen l t wobei g eben falls eine Primzahl ist dann l t sich das ElGamal Verfahren wie folgt abwan deln Das Element g wird nicht mehr so gew hlt da es die gesamte Gruppe Z pZ erzeugt sondern lediglich eine Untergruppe G mit q Elementen Infol ge dessen bewegen sich die auftretenden Exponenten nur noch in der kleineren aber ebenfalls primen Gruppe Z qZ so da man im Exponenten nicht mehr modulo p 1 rechnen mu sondern modulo q rechen kann in der Basis mu weiterhin modulo p gerechnet werden Auf diese Weise kommt man mit kleine ren Exponenten aus das wird beim DSA Verfahren ausgenutzt und kann auch das Shamir Verfahren direkt verwenden Schl sselerzeugung Der Schl sselgenerator w hlt zwei Primzahlen p und q mit p mg 1 und bestimmt eine Element g aus Z pZ mit Ordnung q dieses Element erzeugt eine Untergruppe Gg von Z pZ Dann w hlt er zuf llig und gleichverteilt den
94. m gt KeySharer signPKCS7 lt filename gt key lt alias gt keystore lt keystore gt password lt password gt signature lt algorithm gt 87 Teilberechnungen kombinieren KeySharer combine lt filename gt Dateien verschliisseln KeySharer encrypt lt filename gt cert lt certfilename gt D 2 KeyEscrow wiederherstellbaren Schliissel erzeugen KeyEscrow create lt filename gt keytype lt keytype gt password lt password gt dname lt dn gt cert lt certfilename gt wiederherstellbaren Schliissel rekonstruieren KeyEscrow recover lt filename gt cert lt certfilename gt key lt alias gt keystore lt keystore gt password lt password gt Schliissel in einer Datei verwahren KeyEscrow escrow lt filename gt password lt password gt escrowDir lt escrowdir gt cert lt certfilename gt Schliissel aus der Datei wiederherstellen KeyEscrow recover lt filename gt cert lt certfilename gt escrowDir lt escrowdir gt key lt alias gt keystore lt keystore gt password lt password gt 88 Anhang E Benutzerhandbuch Programmierschnittstelle E 1 Secret Sharing Basisfunktionalit t Geheimnis verteilen public static SecretShare share byte secret int threshold int sharenumber throws InvalidParameterException NoSuchAlgorithmException Integrit tspa wort setzen public static void protectIntegrity PasswordIntegrityProtected shares String p
95. menhang mit X 509 Zertifikaten Sie kapselt damit Aufrufe an das ASN1 Codec PKCS7 diese Klasse enth lt statische Hilfsmethoden im Zusammenhang mit PKCS7 Dateien Dies ist ein standardisiertes Format f r verschl sselte und oder signierte Daten Die Klasse kapselt Aufrufe an das ASN1 Codec JCA kompatible Schl sselkodierung Zur Integration in die JCA war es von entscheidender Bedeutung da die privaten Schl sselanteile von Kompo nenten wie KeyStore und Signature verwendet werden k nnen Hierzu waren zwei Ma nahmen notwendig die Unterst tzung der JCA Schnittstelle PrivateKey und eine Kodierung gem PKCS8 Dies erlaubt es n mlich beispielsweise einem KeyStore den Schl ssel zu serialisieren und wieder zu rekonstruieren PKCS8 identifiziert Schl sselalgorithmen anhand eines Object Identifiers OID Der KeyStore sucht beim Laden von Schl sseln dann ber JCA eine KeyFactory f r diesen OID die wir folglich ebenfalls implementierten Der verwendete OID ist 1 3 6 1 4 1 8301 3 2 99 und entstammt einem der TU Darmstadt zugeordne ten Nummernkreis Die PKCS8 Kodierung selbst enth lt diesen OID und den Teilschl ssel als serialisiertes Java Objekt 5 2 2 Paket keyshare jca Das Paket keyshare jca enth lt H llen und Adapterklassen mit denen eine m glichst gro e Kompatibilit t zur Java Cryptographic Architecture hergestellt werden soll Das Paket enth lt Implementierungen von Cipher Signature und KeyFactory zum Umgang mit Schl sse
96. n im Gegensatz zu Signaturen die auf asymmetrischer Kryptographie aufbauen und zu reinen Hashwerten die berhaupt nicht gesch tzt sind SecureRandom diese Klasse erzeugt kryptographisch sichere also nicht vorher sehbare Pseudozufallszahlen AlgorithmParameterSpec viele Algorithmen m ssen parametrisiert werden Hierzu existieren die AlgorithmParameterSpec Klassen die je nach Al gorithmus ganz unterschiedlich Gestalt annehmen k nnen Durch diese gemeinsame Schnittstelle k nnen sie von der JCA zumindest durchge reicht werden 5 1 4 Schnittstellen f r Dienstanbieter Die in den vorherigen Abschnitten geschilderten Klassen stellen die Schnitt stelle f r den Anwendungsprogrammierer dar Spiegelbildlich dazu gibt es eine 47 entsprechende Schnittstelle fiir Dienstanbieter die eigene Implementierungen liefern wollen Diese Schnittstelle besteht im wesentlichen aus Service Provider Interface Klassen fiir die jeweiligen Konzepte zum Beispiel SignatureSpi oder KeyStoreSpi Um einen JCA konformen Algorithmus zu implementieren mu man diese abstrakten Basisklassen geeignet erweitern und die Klasse im Provi der registieren Wie wir gesehen haben l dt JCA eine implementierende Klasse automa tisch anhand des Algorithmen und des optionalen Providernamens die einer getInstance String String Methode bergeben wurden Damit dies funk tioniert m ssen die Dienstanbieter ihre Implementierungen registrieren Hierf r existiert
97. n Algorithmus nicht m glich wird die erzeugten Schl ssel zu rekonstruieren au er durch den Angrei fer schwache SETUP Eine schwache SETUP unterscheidet sich von einer re gul ren dadurch da der Besitzer eines privaten Schl ssel in der Lage ist die Ausgabe sein Schl sselpaar von einer gew hnlichen Ausgabe zu unterscheiden Bei einer regul ren SETUP vermag dies nur der Angreifer starke SETUP Eine Kerneigenschaft der regul ren SETUP ist die Unun terscheidbarkeit ihrer Ausgaben von den Ausgaben des unmodifizierten Kryp tosystems Nach vollst ndiger Analyse k nnen die Benutzer des Algorithmus zwar aus seinen Ausgaben die darin enthaltenen sublimen Informationen nicht nutzen wissen jedoch um deren Existenz Eine starke SETUP nutzt die ein gebaute Hintert r nicht immer sondern greift gelegentlich auf das normale Verfahren zur ck Dabei bleiben die kontaminierten Schl ssel und die nicht kontaminierten Schl ssel ununterscheidbar Einsatzgebiet Als Anwendung einer SETUP nennen Young und Yung die hier vorgeschlagenen wiederherstellbaren Schl ssel auto escrowing keys Zu gleich stehen sie dem Einsatz eines solches Systems kritisch gegen ber was sich nicht zuletzt in der Namensgebung f r ihr System PAP Pretty Aw ful Privacy ausdr ckt Auch wir m chten durch unsere Implementierung der kleptographischen Algorithmen nicht deren tats chlichen Einsatz in einer PKI empfehlen 4 3 2 RSA Schliissel Bei der Erzeugung e
98. n Homomorphie Eigenschaften Der wichtigste Spezialfall von Function Sharing ist das in Kapitel 3 beschrie bene Key Sharing e Die Sicherheit eines verteilten Geheimnisses kann erh ht werden wenn man die Teilgeheimnisse regelm ig erneuert Die alten Anteile werden dabei gel scht so da ein potentieller Angreifer die ben tigten Teilge heimnisse innerhalb eines gewissen Zeitfensters erbeuten mu da diese sonst ung ltig und wertlos werden Wichtig dabei ist da das eigentliche Geheimnis gleich bleibt Ein Secret Sharing Verfahren das es den Teil nehmern erlaubt die Teilgeheimnisse zu erneuern ohne da Geheimnis daf r rekonstruieren zu m ssen hei t proaktiv e Der Geber stellt eine gro e Schwachstelle von Secret Sharing Verfahren dar In Situationen wo das Geheimnis nicht a priori feststeht sondern auch erst w hrend des Verfahrens erzeugt werden kann dies ist zum Bei spiel bei kryptographischen Schl sseln der Fall ist es m glich auf den Geber zu verzichten Die Teilnehmer einigen sich dann auf ein Geheimnis 14 ohne es selbst zu kennen und erhalten dabei ihre Anteile Durch den Verlust des Gebers als vertrauenswiirdige Instanz ergibt sich die Notwen digkeit eines robusten Verfahrens um das Verhalten der anderen nicht unbedingt vertrauenswiirdigen Teilnehmer kontrollieren zu k nnen 15 Kapitel 3 Key Sharing Die Sicherheit eines Kryptosystems darf nicht davon abh ngen das Verfahren geheimzuhalten Di
99. n Versuch gelangen wir zu 746357 also p 647 q 1153 und N 745991 wobei der angesprochene Ubertragsfehler aufgetreten ist Von den zehn Kan didaten f hrten drei zum Erfolg davon zwei mit Ubertragsfehler Wenn auf diese Weise passende N p und q gefunden wurden kann man den ffentlichen Exponenten e frei w hlen solange ggT e p 1 q 1 1 gilt und den dazugeh rigen privaten Exponenten d mit dem erweiterten Euklidschen Algorithmus berechnen Um den Schliissel wiederherzustellen betrachtet der Recovery Operator die obere H lfte des Moduln N als Schliisseltext d der Chiffre F Da er nicht genau wissen kann welcher der Kandidaten d zum Erfolg gefiihrt hat der symme trische Schl ssel K wurde dabei jeweils weitergez hlt entschl sselt er d f r jedes m gliche K deren Zahl durch die Iterationsschranke B begrenzt ist und erh lt damit eine Reihe denkbarer RSA Schl sseltexte c die er mit sei nem Recovery Schl ssel zu einer Menge von m glichen p entschl sseln kann Auch hier mu er wieder die symmetrische Chiffre F mit den Bj m glichen Schl sseln K anwenden solange bis er einen Primfaktor p von N entschl sseln konnte Konnte kein p gefunden werden mu er aufgrund des m glichen bert 42 ragsfehlers die Berechnungen auch noch fiir die um eine Einheit erh hte obere H lfte von N durchf hren 4 3 3 ElGamal Schliissel Bei der Erzeugung eines ElGamal Schl ssels p g a A wollen wir davon ausge
100. n dieser ist die unentschl ssel te PKCS7 Datei enthalten die folglich weitergereicht werden kann Auf diese Weise kann man zum Beispiel eine verteilte Entschl sselung realisieren 5 4 Applikationen Die Programme werden mittels einer Batch Datei f r Windows oder einem Shell Skript f r andere Plattformen gestartet wobei einige Parameter ange geben werden k nnen 5 4 1 Das Secret Sharing Kommandozeilen Tool Der FileSharer dient zum Zerteilen von beliebigen Dateien in n Anteile die ebenfalls wieder in Dateien gespeichert werden von denen t ben tigt wer den um die Datei zur ckzugewinnen Dazu wird das XOR oder das Shamir Verfahren eingesetzt Abschnitt 2 1 beziehungsweise Abschnitt 2 2 1 Die er zeugten Dateien k nnen optional mit einem Pa wort versehen werden um ihre Integrit t zu sch tzen Datei aufteilen Durch Eingabe von FileSharer share lt filename gt p lt password gt t lt threshold gt n lt shares gt delete 71 wird die Datei filename in shares Dateien filename 1 bis filename n aufgeteilt von denen threshold beliebige vorhanden sein miissen um die Datei zu rekon struieren Wenn mit der Option p ein Passwort angegeben wird werden die Anteile mit diesem Integrit tspa wort versehen Wenn die Option delete ge setzt ist wird anschlie end die Ursprungsdatei filename gel scht Die Defaultein stellungen sehen ein 3 aus 5 Secret Sharing vor Datei wiederherstellen Aus einer ausrei
101. nd Entschl sse lungsoperationen f r die Schl sselhinterlegung Die Art der Speicherung zum Beispiel in Dateien oder einer Datenbank wird den Unterklassen berlassen FileKeyEscrow diese Klasse implementiert die Speicherung der hinterlegten Schl ssel in das Dateisystem 60 KeyPairGenerator KeyEscrowBase AbstractEscrowedKeyPairGen I mui AbstractEscrowedKeyPairGenera tescrowvold generateKeyPair KeyPair escrow void ttaenerateEscrowedkeyPairKevP escrow void initialize void HrecoverP7 bytel initialize void recover PrivateKey initialize void recoverP12 bytel initialize void makeP7 hytel isGoodForSigning boolean IndexedKeyStore escrowCertx509Certificate recoveryKeys KeyStore bulkEncryptionAlgorithm String ElGamalKeyPairGenerator ElGamalKeyPairGenerator RSAKeyPairGenerator generateEscrowedKeyPair KeyPa generateEscrowedKeyPair KeyPa recover ElGamalPrivateKey recover RSAPrivateKey FileKeyEscrow getP7File File recoverP7 bytel escrow void UnrecoverableKeyException AlgorithmParameterSpec PKCS12 UndecryptableKeyException EscrowedKeyParameterSpec A retrieveKeyAndCenrtificate Object UndecryptableKeyException EscrowedKeyParameterSpec UndecryptableKeyException keysize int envelopedKey EnvelopedData escrowkey PublicKey Abbildung 5 7 Klassen aus dem Paket keyshare escrow 61 UndecryptableKeyException diese Ausnahme wird von den Key Escrow Klassen geworfen wenn be
102. neOptions void identifyMode ApplicationMode main void CommonParams Encrypt Decrypt Sign SignPKCS Signx509 Combine CreateNew ShareExisting Abbildung 5 8 Klassen aus dem Paket keyshare apps 63 bei der Fehlervermeidung suche und behebung erwiesen Insgesamt enth lt das Paket 22 Testf lle SecretSharerTests diese Klasse umfa t drei Tests fiir die Klasse SecretSharer und testet somit die Secret Sharing Grundfunktionalitat KeySharerTests diese Klasse testet die Key Sharing Grundfunktionalit t an hand von sechs Tests f r die verschiedenen damit befa ten Klassen vor allem KeySharer und die Signature und Cipher Implementierungen ShamirStoreTests diese Klasse testet den ShamirStore KeyEscrowTests diese Klasse testet mit zwei Tests die Key Escrow Funktionen PKCS7Tests diese Klasse testet Ver und Entschl sselung mit PKCS7 X509Tests diese Klasse testet die verteilte Erzeugung und Zusammenf hrung von X 509 Zertifikaten AppTests diese Klasse testet mit acht Tests die Applikationen FileSharer Key Sharer und KeyEscrow 5 2 7 Ben tigte Klassenbibliotheken Unsere Implementierung greift auf eine Reihe von Java Klassenbibliotheken zur ck die Basisfunktionalit t aus verschiedenen Bereichen bereitstellen Al le diese Bibliotheken miissen in Form von JAR Dateien vorliegen Kryptographie Erweiterungen falls eine Java Umgebung vor Version 1 4 verwendet wird mu die JCE nachinstalliert werden
103. ner verteilten Signatur gem DSS die n here Erforschung und Beurteilung der kleptographischen Methoden zur Schl sselwiederherstellung sowie die proaktive Erneuerung der Anteile durch die Teilnehmer selbst 76 Anhang A Abk rzungsverzeichnis ASN 1 abstract syntax notation eine Beschreibungssprache f r Datenstrukturen Wird unter anderem bei X 509 eingesetzt ASN 1 Daten werden im Gegensatz zu XML Daten in einem kompakten Bin rformat gespeichert CA certification authority Zertifizierungsinstanz Trustcenter Vertrauenswiirdige Stelle die die ein deutige Zuordnung von ffentlichen Schl sseln zu den Mitgliedern der Kommunikationsgemeinschaft garantiert DN distinguished name Nach dem X 500 Standard f r Verzeichnisdienste verf gt jeder Teilnehmer ber einen eindeutigen Namen der aus mehreren Namensbestandteilen z B Organisationsname L ndername Name der Person aufgebaut ist zwischen denen eine Hierarchie besteht Auch die Teilnehmer einer X 509 PKI werden durch ihren DN identifiziert JCA Java Cryptography Architecture Teil der Java Plattform der den Zugriff auf kryptographische Algorith men und Daten regelt PKCS public key cryptography standards PKI SSL von den RSA Laboratories entwickelte Familie von Standards PKCS 7 definiert ein Format fiir signierte und oder verschliisselte Dateien PK CS 8 ein Bin rformat f r private Schl ssel und PKCS 12 das sogenann te Softtoken ein gesch tzte
104. nliche RSA Operation si m mod N durchf hren Dadurch k nnen wir bei der Schl sselerzeugung die Exponen ten d die im allgemeinen zwar kleiner als die urspr nglichen d aber immer noch gr er als normale RSA Exponenten sowie teilweise negativ sein werden modulo p 1 q 1 reduzieren die Gruppenordnung ist zum Zeitpunkt der Schl sselerzeugung noch bekannt Auf diese Weise k nnen den Teilnehmern gew hnliche RSA Schl ssel bergeben werden Die Kombination der Teilergeb nisse erfolgt dann als yhen si Trea ga Mie ga nyya i mod N Vie A und 26 s m si mod N EA 3 6 Verifizierbares RSA Key Sharing Das in Abschnitt 3 5 vorgestellte Verfahren verfiigt ber zwei Nachteile n mlich den fehlenden Sicherheitsbeweis und die fehlende M glichkeit die von den Teil nehmern abgegebenen Berechnungsergebnisse zu verifizieren Beide M ngel sind in einem von Victor Shoup vorgeschlagenen Verfahren nicht anzutreffen fiir den Sicherheitsbeweis verweisen wir auf die Originalarbeit Sho00 Es erzeugt ebenfalls normale RSA Signaturen und Entschliisselungen ohne Interaktionen zwischen den Teilnehmern zu ben tigen Allerdings setzt das Verfahren spezi elle RSA Moduln voraus und die Teilschl ssel und die damit durchzuf hrenden Berechnungen lassen sich im Gegensatz zu unserem Vorschlag aus Abschnitt 3 5 2 nicht in normale RSA Implementierungen einbetten Schliisselerzeugung Der Geber bestimmt zwei zufal
105. odellierung eingeschr nkt so da viele andere interessante Verfahren der Threshold Cryp tography und hnlicher Gebiete unbeachtet geblieben sind Dies lag sicher auch am begrenzten Umfang dieser Arbeit Wir wollen daher abschlie end noch ein paar Stichworte f r eine weitergehende Besch ftigung geben Zun chst einmal k nnte man unsere Implementierung noch abrunden Ei nige der geschilderten Verfahren sind nicht Pedersen Verfahren oder nur teil weise Shoup Verfahren ohne Verifikation implementiert Auch ist die Imple mentierung nicht auf Performanz ausgerichtet und bietet durch die Komman dozeilenapplikationen und die Programmierschnittstelle eine zwar brauchbare aber nur sehr rudiment re Infrastruktur Interessant w re ihr Einsatz in einem gr eren Projekt f r eine verteilte kryptographische Applikation etwa eine ver teilte CA Ein sehr bedeutsames Gebiet das wir nur am Rande gestreift haben ist die verteilte Schl sselerzeugung In konsequenter Weiterf hrung des Modells in dem es gilt den Schl ssel vor unvertrauensw rdigen Parteien zu sch tzen wird hier auch die Existenz eines vertrauensw rdigen Gebers abgestritten der einen Schl ssel unbeaufsichtigt erzeugen k nnte An seine Stelle tritt eine Koopera tion von Teilnehmern die sich alle nicht vollst ndig vertrauen aber trotzdem gemeinsam einen Schl ssel erzeugen und verwenden k nnen Ebenfalls sinnvoll w re die Implementierung weiterer Algorithmen etwa ei
106. olgungsbeh rden haben Harold Abelson Ross Anderson Steven Bellovin Josh Benaloh Matt Blaze Whitfield Diffie John Gilmore Peter Neumann Ronald Rivest Jeffrey Schiller und Bruce Schneier 1997 den technisch orien tierten Teil der Diskussion zusammengefa t Wir wollen hier ihre wesentlichen Argumente wiedergeben e durch M glichkeiten des Key Recovery werden zus tzliche Schwachstel len und Risiken in das Kryptosystem eingebracht Die beiden gr ten Problem sind der Verlust der Garantie da es keinen anderen Zugang zu Klartexten gibt als den Benutzerschl ssel und die Tatsache da die 37 mit Key Recovery beauftragten Institutionen neue extrem attraktive An griffsziele darstellen e ein solches System kann nur sinnvoll sein wenn es umfassend wom glich weltweit eingesetzt wird Aufgrund der dann notwendigen Zusammenar beit zahlloser Beh rden L nder Softwarehersteller und Benutzer zur Ver waltung der Millionen von Benutzer und Sitzungsschliisseln die von Tau senden unterschiedlicher Kryptoprodukte teilweise ad hoc erzeugt wer den entstehen unbeherrschbare Komplexit ten Insbesondere entsteht ein Widerspruch zwischen den von den Strafverfolgungsbeh rden geforderten kurzen Bearbeitungszeiten und den organisatorischen Ma nahmen zur Si cherstellung der Pr fung der Legitimation eines Recovery Antrags sowie dessen ordnungsgem er Durchf hrung e durch die Entwicklung den Betrieb und die berwachung eines Key
107. otwen dig da Java beim Aufruf einer Methode lediglich den Typ des Empf ngerobjekts dynamisch ermittelt nicht jedoch die Typen der Argumente Man bezeichnet diese Vorgehensweise als Single Dispatch W rde Java direkt einen Double Dis patch unterst tzen h tten wir die Adaptermethoden combine in denen le diglich ein Typecast vorgenommen wird nicht in jeder Klasse implementieren m ssen Key Sharing Es wurden die einfachen nicht redundanten Key Sharing Verfahren f r RSA Abschnitt 3 4 und ElGamal Abschnitt 3 8 die bei den redundaten RSA Key Sharing Verfahren von Frankel Gemmell MacKen zie und Yung in der abgewandelten Version aus Abschnitt 3 5 2 sowie von Shoup Abschnitt 3 6 und das redundante Key Sharing Verfahren f r spezielle ElGamal Schl ssel Abschnitt 3 8 implementiert Die RSA Teilschliissel un terst tzen sowohl Entschl sselungen als auch das Erstellen von Signaturen die ElGamal Teilschl ssel eignen sich nur zum Entschl sseln aufgrund des ange sprochenen Kommunikationsbedarfs bei Signaturen siehe Abschnitt 3 8 Die Struktur der im folgenden kurz beschriebenen Klassen und Schnittstellen ist in Abbildung 5 2 dargestellt KeyShare diese Schnittstelle erweitert SecretShare um eine Methode zum Er fragen des Namen des Algorithmus f r den der verteilte Schl ssel geeignet 51 SimpleElGamalPrivateKeyShare SimpleElGamalPrivateKeyShare share SimpleElGamalPrivateKe sign PartialSignature decry
108. ptPartialDecryption splitElGamalCipherText Bi PartialElGamalDecryption identifier byte threshold int interface KeyShare keyAlgorithm String PrivateKey interface PrivateKeyShare sign PartialSignature deciypt PartiaiDecryption publicKey PublicKey AbstractPrivateKey Share AbstractPrivateKeyShare getPublicKey PublicKey getKeyAlgorithm String getldentifier byte getThreshold int getShareNumber int sharesSecretboolean combine byte equals boolean getAlgorithm String getFormat String getEncoded byte Y A Y Serializable interface SecretShare sharesSecret boolean combine bytel shareNumberint encoded byte interface PartialSignature algorithm String verificationKey PublicKey AbstraciPartiaiSignature getAlgorithm String getVerificationKey PublicKey AbstractPartialSignature interface PartiaiDecryption algorithm String AbstractPartiaiDecryption AbstractPartialDecryption getAlgorithm String getldentifier bytel getThreshold int getShareNumberint sharesSecret boolean getEncoded bytel share KeyShare combine byte combine byte combine bytel combine byte x509 PKCS7 makeDummyCertificate x509Cert encryptbyte makeDummyCertificate X509Cenl encrypt byte sign byte decrypt byte combineSignedCentificate X509C FGMY RSAPrivateKeyShare sign byte combineSignedData SignedData
109. r der Berechnung bekannt sein die Menge A Wenn sich erst sp ter herausstellt da einige Teilnehmer nicht zur Verf gung stehen m ssen alle Teilnehmer die Be rechnung wiederholen Das Problem vergr ert sich noch in Anbetracht des n chsten Kritikpunktes ein vorliegendes Teilergebnis l t sich nicht auf Korrektheit berpr fen Ein fehlerhaftes Ergebnis wird erst nach der Kombination aller Teilergeb nisse erkannt ohne da allerdings bekannt w re welche der Teilergebnisse zum Fehler gef hrt haben Dies macht es sehr schwierig einen fehlerhaft arbeitenden Teilnehmer zu erkennen und auszuschlie en In unserer Implementierung haben wir eine Variation des Verfahrens ent wickelt bei der den Teilnehmern gew hnliche RSA Schl ssel zugeteilt werden mit denen sie die partiellen Berechnungen durchf hren k nnen Die Teilergeb nisse k nnen dann in beliebigen Kombinationen zusammengef hrt werden oh ne da Neuberechnungen durch die Teilnehmer notwendig werden Damit sind zwei der angesprochenen vier M ngel behoben Das Problem einen fehlerhaf ten Beitrag erkennen zu k nnen wird ebenfalls gemildert da alle zul ssigen Kombinationen getestet werden k nnen ohne weitere Beteiligung der eventu ell betr gerischen Teilnehmer Bestehen bleibt die unbewiesene Sicherheit des 25 Verfahrens ein beweisbar sicheres Verfahren das auch betriigerische Teilneh mer aufdeckt wird in Abschnitt 3 6 vorgestellt Schliisselerzeugung Di
110. r haben uns f r die MD5 Hashfunktion entschieden die in jeder Laufzeitumgebung per JCA verf gbar sein sollte Die ID eines Anteils ist somit 16 Byte lang Pa wort Integrit tsschutz Wir haben das Pedersen Verfahren f r verifi zierbares Secret Sharing nicht implementiert weil es nicht ganz in unser Modell pa t und der Schutz von fehlerhaft berechneten Anteilen auch nicht ben tigt wird wir vertrauen dem Geber Um trotzdem dem Kombinierer die M glich keit zu geben von den Teilnehmern verf lschte Anteile zu erkennen haben wir die M glichkeit vorgesehen da der Geber die Anteile mit einem den Teilneh mern unbekannten Pa wort versieht Dieses Pa wort geht dann gemeinsam mit der ID und dem Inhalt des Anteils in eine Pr fsumme ein wieder MD5 die ohne Kenntnis des Pa worts nicht manipuliert werden kann Auf diese Weise k nnen bei der Kombination die Beitr ge der Teilnehmer anhand des Pa wortes berpr ft werden Double Dispatch Das Interface SecretShare schreibt eine Methode combine vor mit der eine Menge gleichartiger SecretShare Instanzen zusammengesetzt werden k nnen Diese Methode ist in allen konkreten Implementierungen von SecretShare derart realisiert da das hereingereichte Feld von SecretShare auf den konkreten Typ beispielsweise ShamirSecretShare eingeengt wird und dann einer weiteren combine Methode weitergereicht wird welche die tats chlichen Berechnungen durchf hrt Dieser explizite Typecast ist n
111. raucht jedes Paar von Teilnehmern einen eige nen Schl ssel Die Zahl der Schl ssel w chst hierbei quadratisch mit der Anzahl der Teilnehmer In gro en Gemeinschaften oder gar dem Internet als Ganzem ist dies v llig unpraktikabel Das Problem der gemeinsam geheimzuhaltenden Schl ssel wird bei der so genannten Public Key oder asymmetrischen Kryptographie umgangen In diesem von Whitfield Diffie und Martin Hellman 1976 vorgestellten Verfahren DH76 besitzt jeder Teilnehmer einen privaten und einen ffentlichen Schl ssel 16 Diese beiden Schliissel bilden dadurch dall sie in einer gewissen mathematischen Beziehung zueinander stehen ein Schliisselpaar Mit dem 6ffentlichen Schliissel eines Empf ngers k nnen Nachrichten verschl sselt werden die anschlie end nur mit dessen privatem Schl ssel wieder entziffert werden k nnen Ein Public Key Kryptoverfahren basiert auf einem schwierigen das hei t f r praktische Zwecke nicht l sbaren mathematischen Problem das es unm glich macht den privaten Schl ssel aus dem ffentlichen Schl ssel zu berechnen ob wohl die Beziehung der beiden zueinander allgemein bekannt ist sonst w re es nicht als Schl sselpaar zu verwenden So wird es m glich den ffentlichen Schl ssel v llig frei zu verteilen ohne da dadurch eine Gefahr f r den geheimen Schl ssel der weiterhin verborgen bleiben mu entsteht Man kann sich die Verwendung asymmetrischer Kryptographie wie einen Hausbrief
112. retShare evaluatePolynomial Biglnteger evaluatePolynomial Biglnteger extendedEuclid Biglnteger share SecretShare protectintegribyvoid combine byte checkAndCombine byte SecretSharingException SecretSharingException Abbildung 5 1 Secret Sharing Basisklassen aus dem Paket keyshare keyshare tests das Paket enth lt Testf lle gem f dem JUnit Framework mit denen die korrekte Funktionsweise der Implementierung berpr ft werden kann 5 2 1 Paket keyshare Das Paket keyshare enth lt die grundlegenden Algorithmen und Datenstruktu ren zur Implementierung sowohl der Secret Sharing als auch der Key Sharing Verfahren Secret Sharing Es wurden das XOR Secret Sharing Verfahren Abschnitt 2 1 und das Shamir Verfahren Abschnitt 2 2 1 implementiert F r beide Ver fahren ist vorgesehen da die Anteile bei ihrer Erzeugung mit einem Inte grit tspa wort gesch tzt werden k nnen Dies soll verhindern da Ver nde rungen der Anteile unerkannt bleiben Nicht implementiert wurde das verifi zierbare Pedersen Verfahren Abschnitt 2 3 1 Die Struktur der im folgenden kurz beschriebenen Klassen und Schnittstellen ist in Abbildung 5 1 dargestellt SecretShare diese Schnittstelle definiert die Methodensignatur eines Geheim nisanteils Fin SecretShare mu Auskunft ber seine Nummer die An zahl der ben tigten Anteile eine ID und dar ber ob er zu einem bestimm ten Geheimnis pa t geben Au erdem mu e
113. rfahren die Primzahl die den Raum der Ge heimnisse Z pZ bestimmt das Geheimnis Beim Shamir Verfahren s Z pZ die Teilgeheimnisse Jeder Teilnehmer 7 erh lt ein s Threshold Anzahl der ben tigten Anteile um das Geheim nis zu rekonstruieren Schl sseltext verschl sselte Nachricht c m mod N privater Exponent wird zum Entschliisseln und Signieren verwendet ffentlicher Exponent wird zum Verschliisseln und Verifizie ren verwendet Klartext Nachricht Zahl aus Z NZ bei Signaturen ein Hashwert ffentlicher Modulus N pg geheimer Primfaktor des Modulus N pg geheimer Primfaktor des Modulus N pg Signatur s m mod N 79 ElGamal a A SQ Di privater Exponent wird zum Entschliisseln und Signieren verwendet ffentlicher Schl ssel wird zum Verschl sseln und Verifizie ren verwendet A g mod p Teil das Schliisseltexts Basiselement Teil des ffentlichen Schl ssels ffentlich bekannte Primzahl bestimmt die Gruppe Z pZ in der gerechnet wird optionale ffentliche Primzahl die bewirkt da ElGamal Exponenten nicht modulo p 1 sondern modulo q gerech net werden Wird im DSA Verfahren verwendet und bei ElGamal Key Sharing p mq 1 80 Anhang C UML Klassendiagramme Serializable interface SecretShare sharesSecret boolean combine bytel identifier byte threshold int shareNumberint encoded bytel SecretSharer share SecretSharel p
114. rotectintegrity void combine byte checkAndCombine byte AbstractSecretShare AbstractSecretShareWithPass AbstractSecretShare getldentifier byte getThreshold int getShareNumber int sharesSecret boolean toString String equals boolean getEncoded bytel AbstractSecretShareWithPasswo setlntegrityPassword void checklntegrity boolean interface PasswordintegrityProtected checkintegrity boolean XORSecretShare KORSecretShare shareXORSecretShare combine bytell combine byte ShamirSecretShare integrityPassword String evaluatePolynomial int biglntToByteArray byte kiglntToByteArray 1 0 Padding Exception SecretSharingException biglntToByteArray PKCS1 vi 5 fixArray SecretShare evaluatePolynomial Biglnteger evaluatePolynomial Biglnteger extendedEuclid Biginteger SecretSharingException SecretSharingException 81 ShamirSecretShare share ShamirSecretShare combine byte combine bytell Serializable interface SecretShare sharesSecret boolean combine bytel identifier byte threshold int shareNumberint encoded bytel interface KeyShare keyAlgorithm String PrivateKey interface PrivateKeyShare interface PartialSignature algorithm String verificationKey PublicKey AbstractPartiaiSignature getAlgorithm String
115. rst tzt KeySharer sign lt filename gt key lt alias gt keystore lt keystore gt password lt password gt sigAlg lt algorithm gt KeySharer signX509 lt filename gt key lt alias gt keystore lt keystore gt password lt password gt signature lt algorithm gt KeySharer signPKCS7 lt filename gt key lt alias gt keystore lt keystore gt password lt password gt signature lt algorithm gt Teilberechnungen kombinieren KeySharer combine lt filename gt 73 Dateien verschliisseln Der KeySharer kann auch dazu verwendet werden um Dateien mit einem ffentlichen Schl ssel im PKCS7 Format zu verschl sseln KeySharer encrypt lt filename gt cert lt certfilename gt 5 4 3 Das Key Escrow Kommandozeilen Tool Die Applikation KeyEscrow dient zum Verwahren von Schliisseln in chiffrierten Dateien zum Erzeugen von wiederherstellbaren Schliisseln Abschnitt 4 3 und zur Wiederherstellung der Schliissel Die Schliissel werden dabei in Form von PKCS12 Dateien eingelesen und ausgegeben wiederherstellbaren Schliissel erzeugen KeyEscrow create lt filename gt keytype lt keytype gt password lt password gt dname lt dn gt cert lt certfilename gt Der Schliissel wird in eine PKCS12 Datei mit dem angegebenen Namen filename geschrieben und mit dem Password password gesch tzt In dieser ent halten ist auch ein Dummy X 509 Zertifikat mit dem ffentlichen Schl ssel Der Name des
116. s Transportformat fiir Schl sselpaare Public Key Infrastruktur System aus Richtlinien Abl ufen Institutionen und Datenformaten zur Verwaltung der in der asymmetrischen Kryptographie ben tigten ffent lichen Schl ssel secure socket layer Protokoll zur sicheren Kommunikation ber das Internet Server und op tional Client authentifizieren sich mit Zertifikaten die bertragenen Daten werden mit einem Einmalschl ssel verschl sselt 77 X 509 ITU Empfehlung X 509 auch ISO IEC 9594 8 dominierender PKI Standard Enth lt unter anderem ein flexibles Zerti fikatsformat das mittlerweile in fast allen Anwendungen verwendet wird XML extensible markup language universelles Austauschformat fiir strukturierte Daten XML zeichnet sich gegen ber dem lteren SGML durch eine stark vereinfachte Syntax aus die die Entwicklung vom XML f higen Anwendungen vereinfacht hat XML hat in letzter Zeit eine gro e Verbreitung erreicht XML ist im Gegensatz zu ASN 1 kein Bin rformat sondern textbasiert 78 Anhang B Symbolverzeichnis Secret Sharing f x AA D vgs gt Co 3 n R 8 gt Beim Shamir Verfahren das Polynom ber Z pZ mit des sen Hilfe das Geheimnis s f 0 verteilt wird Interpolationskoeffizient f r Teilnehmer 7 aus A Aja Tieay pa Menge der Teilnehmer nummern fiir die Rekonstruktion Anzahl der Anteile in die das Geheimnis aufgeteilt wird t aus n Secret Sharing Beim Shamir Ve
117. s sich in ein Byte Array se 49 rialisieren lassen und die Methode zur Rekonstruktion des Geheimnisses implementieren der man dann gen gend viele Anteile bergeben mu SecretSharingException diese Ausnahme wird geworfen wenn ein Fehler bei der Rekonstruktion eines Geheimnisses auftritt PasswordIntegrityProtected diese Schnittstelle wird von Geheimnisanteilen implementiert die mit einem Integrit tspa wort gesch tzt werden sollen Sie definiert Methoden zum Setzen und berpr fen des Pa worts AbstractSecretShare diese abstrakte Klasse stellt Default Implementierungen f r die Methoden eines SecretShare bereit und dient damit zur Vermei dung von Code Duplikaten AbstractSecretShareWithPassword diese abstrakte Klasse erweitert AbstractSecretShare um Unterst tzung f r die Schnittstelle PasswordIntegrityProtected und damit um ein Integrit tspa wort ShamirSecretShare diese Klasse stellt einen durch das Shamir Verfahren ent standenen Anteil dar Sie enth lt auch Methoden zum Verteilen eines geheimen Byte Arrays nach diesem Verfahren XORSecretShare diese Klasse stellt einen durch das XOR Verfahren entstande nen Anteil dar Sie enth lt auch Methoden zum Verteilen eines geheimen Byte Arrays nach diesem Verfahren SecretSharer diese Klasse enth lt statische Methoden zum einfachen Zugriff auf die Secret Sharing Funktionalit t Erzeugen Pr fen und Kombinieren von Anteilen Sie bietet damit eine Fassade f r den Secr
118. scher Greueltaten kommen von denen die Sicherheitsbeh rden zeigen k nnen da sie durch Abh rma nahmen verhindert h tten werden k nnen dann werden Regierungen sehr schnell mehr Unterst tzung f r Key Escrow bekommen Simon Singh in The Code Book Ein Thema von vor allem politischer Brisanz sind Schl sselverwahrung Key Escrow und Schl sselwiederherstellung Key Recovery durch jemand ande ren als den Schl sselinhaber Insbesondere ist umstritten ob Strafverfolgungs beh rden die M glichkeit erhalten sollen Kopien von privaten Dechiffrier Schl s seln zu erhalten so da sie in die Lage versetzt werden verschl sselte und da mit eigentlich vertrauliche Kommunikation abzuh ren Neben grunds tzlichen Einw nden von Verfechtern der Grundrechte auf informationelle Selbstbestim mung gibt es hier zahlreiche technische Bedenken ob man durch die Einf hrung einer solchen Abh rm glichkeit nicht das Kryptosystem insgesamt zu unsicher machen w rde Wir wollen die Argumente f r und gegen Key Escrow in Ab schnitt 4 1 wiedergeben und in den darauf folgenden Abschnitten darstellen wie man es realisieren k nnte 4 1 Key Escrow Es gibt unterschiedliche Motivationen daf r einen Schl ssel wiederherstellen zu wollen e wenn der Besitzer des Schl ssels diesen verliert kann er an ihn adres sierte verschl sselte Nachrichten nicht mehr lesen Es ist davon auszuge hen da ein Trustcenter in dem der Schl ssel hinterleg
119. t er den anderen Faktor q wenn dies ebenfalls nicht zum Erfolg f hrt w hlt er solange neue Primfaktoren p bis sich ein geeignetes c er gibt Der private Exponent d errechnet sich aus e p und q mit dem erweiterten Euklidschen Algorithmus Um den Schl ssel wiederherzustellen betrachtet der Recovery Operator den ffentlichen Exponenten e als Schl sseltext und entschl sselt ihn zum Primfak tor p Wegen N pq erh lt er damit zugleich auch den anderen Faktor q und kann mit dem erweiterten Euklidschen Algorithmus den privaten Exponenten d als multiplikatives Inverses zu e modulo p 1 q 1 bestimmen Das Problem bei dieser Vorgehensweise liegt daran da es nicht immer m glich ist den ffentlichen Exponenten e frei zu w hlen Viele RSA Implemen tierungen verlangen nach einem kleinen e weil sich dies positiv auf die Rechen zeit der ffentlichen RSA Operationen auswirkt ohne einen negativen Effekt auf die Sicherheit zu haben Das obige Verfahren erzeugt jedoch Exponenten e mit einer Bitl nge die der verwendeten Backup Chiffre und damit falls RSA verwendet wurde aus Sicherheits berlegungen der Bitl nge des Moduln N mindestens jedoch der Bitl nge von p entspricht Verschl sselung im Moduln N Wenn ffentliche Exponenten e beliebiger Gr e nicht m glich sind kann der Chiffretext f r den Primfaktor p auch in der oberen H lfte des Moduln N untergebracht werden Hierbei ist jedoch zu beachten da der Chiffretext dann au
120. t wird entscheidet JCA zur Laufzeit anhand einer konfigurierbaren Priorisierung und des Algorithmenange bots der Provider Es ist ferner m glich explizit einen Providernamen anzuge ben der verwendet werden soll Falls dieser nicht existiert oder den gew nsch ten Algorithmus nicht anbietet werden eine NoSuchProviderException oder NoSuchAlgorithmException geworfen Signature diese Klasse wird zum Erzeugen und Pr fen digitaler Signaturen verwendet Sie wird mit einem geeigneten Schl ssel zum Signieren oder Verifizieren initialisiert Die Nachricht wird mit einer update bytel Methode bergeben die Signatur mit sign erzeugt oder mit verify byte signature berp ft Cipher diese Klasse eignet sich zur Ver und Entschl sselung von Daten Je nach Algorithmus wird sie mit ffentlichen oder symmetrischen Schl sseln zur Verschl sselung mit privaten oder symmetrischen Schl sseln zur Ent schl sselung initialisiert Auch hier gibt es wieder update byte Methoden das Ergebnis entsteht durch den Aufruf von doFinal MessageDigest diese Klasse erzeugt kryptographische Hashwerte Digests Fin gerprints von Nachrichten Hashwerte werden verwendet um die Inte grit t einer Nachricht zu berpr fen wobei zumindest der Hashwert aus sicherer Quelle stammen mu Mac diese Klasse implementiert Message Authentication Codes Hierbei han delt es sich um integrit tssicherende Pr fsummen die auf symmetrischen Schl sseln basiere
121. t wurde diesen ausfallsicher speichern k nnte In diesem Fall wird der Schl ssel nur auf ausdr cklichen Wunsch des Besitzers wiederhergestellt Es ist denkbar da f r diesen Vorgang seine aktive Beteiligung notwendig ist indem er etwa eine geheime Information beisteuert Hierdurch kann sichergestellt werden da das Trustcenter den Schl ssel nicht ohne seine Genehmigung 35 verwenden kann Andererseits ergibt sich das Problem da der Schl ssel besitzer diese geheime Information aufbewahren mu ein Problem das sich nicht grunds tzlich davon unterscheidet den Schliissel aufzubewah ren e wenn der Schliissel innerhalb eines Unternehmens oder einer sonstigen Organisation zur Verschl sselung von gesch ftlichen Nachrichten einge setzt wird kann ein berechtigtes Interesse der Organisation bestehen den Schliissel wiederherstellen zu k nnen beispielsweise nachdem der damit betraute Mitarbeiter das Unternehmen verlassen hat In diesem Fall kann etwa ein Vorgesetzter in die Lage versetzt werden die gesch ftliche Kor respondenz seiner Untergebenen einzusehen Dies kann zwar auch ohne Beiteiligung und Wissen der eigentlichen Empf nger der Nachricht gesche hen aber iiblicherweise gibt es keinen Grund die betroffenen Mitarbeiter davon nicht in Kenntnis zu setzen e durch den Einsatz von starker Kryptographie stehen Strafverfolgungs beh rden vor dem Problem da Abh rma nahmen als Ermittlungswerk zeug nicht mehr eingeset
122. tKeyEntry alias key password certificateChain Key key ks getKey alias password Certificate cert ks getCertificate alias Keystore speichern ks store null password 90 E 4 Der KeySharer KeyStore Konfiguration lt key sharer threshold 2 gt lt share file 1a keystore gt lt share file 2b keystore gt lt share file 3c keystore gt lt key sharer gt Instanz erzeugen KeyStore ks KeyStore getInstance KeySharer Keystore laden FileInputStream in new FileInputStream configuration xml ks load in password in close Keystore verwenden ks setKeyEntry alias key password certificateChain Keystore speichern ks store null password E 5 Das Key Escrow System Wiederherstellbares Schliisselpaar erzeugen KeyPairGenerator keygen KeyPairGenerator getInstance RSA KeySharingProvider keygen initialize new EscrowedKeyParameterSpec 1024 PublicKey escrow KeyPair pair keygen generateKeyPair privaten Schliissel wiederherstellen PrivateKey recovered RSAKeyPairGenerator recover RSAPublicKey key PrivateKey recovery PublicKey escrow privaten Schliissel im Dateisystem verwahren FileKeyEscrow escrow new FileKeyEscrow File escrowDir escrow setEscrowCert X509Certificate cert escrow escrow Key key X509Certificate userCert privaten Schliissel aus dem Dateisystem wiederherstellen escrow setRecoveryKeys KeyStore ks
123. tons KeyEscrowBase KeyPairGenerator AbstractEscrowedKeyPairGen AbstractEscrowedKeyPairGenera generateKeyPair KeyPair ttaenerateEscrowedkeyPairKeyP initialize void initialize void initialize void initialize void keepSigningKeys void tescrowvold escrow void escrow void HrecoverP7 bytel recover PrivateKey recoverP12 hyte makeP byte isGoodForSigning boolean IndexedKeyStore escrowCertx509Cenificate recoveryKeys KeyStore bulkEncryptionAlgorithm String RSAKeyPairGenerator RSAKeyP airGenerator generateEscrowedKeyPair KeyPa recover RSAPrivateKey ElGamalKeyPairGenerator ElGamalKeyPairGenerator generateEscrowedKeyPair KeyPa recover ElGamalPrivateKey FileKeyEscrow getP7File File recoverP7 byte Fescrow void UnrecoverableKeyException AigorithmParameterSpec PKCS12 UndecryptableKeyException EscrowedKeyParameterSpec retrieveKeyAndCertificate Object UndecryptableKeyException EscrowedKeyParameterSpec UndecryptableKeyException keysize int envelopedKey EnvelopedData escrowkey PublicKey 85 usage void KeyEscrow setupCmdLineOptions void identifyMode ApplicationMode main void CommonParams CreateNew Escrow Recover RecoverFromFile CommandLineApp Usage void setupCmd iIneOptions void identitWode ApplicationMode run void Usage void FileSharer setupCmdLineOptions void identifyMode ApplicationMode main voi
124. tring integrityPassword throws NoSuchAlgorithmException SecretSharingException Diese beiden Methoden kombinieren die ihnen bergebenen Anteile zu dem By tefeld aus dem diese hervorgegangen sind checkAndCombine berpr ft dabei zuvor die Integrit t der Anteile anhand eines Pa wortes Wenn das Geheim nis aufgrund fehlerhafter Eingaben nicht rekonstruiert werden konnte wird ei ne SecretSharingException ausgel st wenn die MD5 Funktion die ben tigt wird um die Korrektheit des Geheimnisses zu pr fen fehlt gibt es eine NoSuchAlgorithmException 5 3 2 Key Sharing Basisfunktionalit t Die grundlegenden Key Sharing Funktionen werden durch die statischen Me thoden der Klasse keyshare KeySharer zug nglich gemacht Schl ssel verteilen public static KeyShare share Key secret int threshold int sharenumber throws InvalidParameterException NoSuchAlgorithmException InvalidKeySpeckxception Diese Methode erzeugt f r den bergebenen Schl ssel secret insgesamt sharenumber Anteile von denen threshold zur Rekonstruktion ben tigt werden Das dabei eingesetzte Verfahren h ngt von der Art des Schl ssels sowie von den Werten f r sharenumber und threshold ab Ung ltige Werte f r sharenumber und threshold f hren zu einer InvalidParameterException nicht unterst tzte Schl sseltypen verursachen eine NoSuchAlgorithmException oder eine InvalidKeySpecException Teilsignaturen und Teilentschl sselungen erstellen Signature
125. tzstellen und diesen Wert s beinhaltet Aufgrund der Konstruktion des Polynoms ist jedes dieser m glichen Polynome gleichwahrscheinlich Das Shamir Verfahren ist somit informationstheoretisch sicher im Shannon schen Sinne 2 3 Verifizierbares Secret Sharing Eine Hauptmotivation fiir den Einsatz von Secret Sharing ist die M glichkeit Angriffe auf die Vertraulichkeit und Verfiigbarkeit des Geheimnisses abzuweh ren Durch das Shamir Verfahren wird sichergestellt daf das Geheimnis einem Angreifer nur in die H nde fallen kann wenn er Kenntnis von einer Mindestmen ge an Teilgeheimnissen erh lt Trotzdem kann ein Angreifer der die Kontrolle ber einige wenige Teilnehmer erh lt zumindest die Verf gbarkeit des Geheim nisses empfindlich st ren wenn er die Rekonstruktion sabotiert Es ist n mlich bei der Kombination der Teilgeheimnisse nicht m glich zu erkennen ob der Beitrag einzelner Teilnehmer korrekt war oder nicht Das macht es schwierig betr gerische Teilnehmer auszuschlie en Von einem robusten Secret Sharing Verfahren wird verlangt da es auch eine gewisse Menge an Teilnehmern ver kraftet die sich nicht an alle Einzelheiten des Protokolls halten Eine wichtige Komponente robuster Secret Sharing Verfahren sind verifizierbare Teilgeheim nisse die wir in diesem Abschnitt besprechen wollen Das Shamir Verfahren funktioniert wenn sich alle Teilnehmer inklusive des Gebers an die vorgeschriebenen Protokollabl ufe halten D
126. tzt in unbefugte H nde zu fallen aber durch seinen Verlust wird auch der weitere Betrieb des Systems unm glich gemacht Daher ist man gezwungen eine oder mehrere nicht fl chtige Kopien des Schl ssels an einem sicheren Ort zu hinterlegen Mit jeder dieser Kopien steigt das Risiko da eine der Kopien von einem Angreifer erbeutet wird Legt man allerdings zu wenige Kopien an k nnten alle gleichzeitig zerst rt werden Eine L sung des Problems haben unabh ngig voneinander Adi Shamir Sha79 und G R Blakley Bla79 vorgeschlagen Man erzeuge aus dem Geheimnis ei ne Anzahl neuer Geheimnisse die f r sich genommen keinen R ckschlu auf das urspr ngliche Geheimnis erm glichen Schutz gegen Spionage aus denen dieses aber rekonstruiert werden kann wenn nur gen gend viele von ihnen vor liegen Schutz gegen Verlust Beispielsweise kann man mit den von Shamir und Blakley geschilderten Verfahren das Geheimnis auf f nf Teile aufteilen von denen man sp ter mindestens drei ben tigt um das Geheimnis wiederher zustellen Bevor wir das relativ bekannte Verfahren von Shamir in Abschnitt 2 2 1 erl utern wollen wir in Abschnitt 2 1 eine einfachere Methode vorstellen die jedoch nicht gegen den Verlust einzelner Anteile gesichert ist Danach schildern wir in Abschnitt 2 3 1 eine Erweiterung des Shamir Verfahrens Zum Abschlu dieses Kapitels geben wir einen berblick ber weitergehende Anforderungen und Entwicklungen zum Thema Secret Sharin
127. ublic Key Operationen stets einer kleinen Konstante gleichgesetzt werden etwa 65537 Aufgrund der Tatsache da e und p 1 q 1 keine gemeinsamen Tei ler besitzen kann mit dem erweiterten Euklidschen Algorithmus der geheime Exponent d bestimmt werden mit ed 1 mod p 1 q 1 Der ffentliche Schl ssel besteht aus e N der private Schl ssel ist d N oder auch sinnvoll zur Beschleunigung von Berechnungen von Private Key Operationen mit dem Chinesischen Restsatz d p q Schl sselverwendung RSA Schl ssel lassen sich f r zwei Operationen ein setzen n mlich zur Nachrichtenverschl sselung und f r digitale Signaturen In beiden F llen kommt dabei eine identische Berechnungsvorschrift zum Einsatz lediglich die Rollen von ffentlichem und privatem Schl ssel werden vertauscht Diese Symmetrie wird sich sp ter beim RSA Key Sharing als n tzlich erweisen Um eine Nachricht m f r den Empf nger mit dem ffentlichen Schl ssel e N zu verschl sseln wird sie als Zahl zwischen 1 und N 1 aufgefa t und 20 mit dem ffentlichen Exponenten e potenziert Es ergibt sich der Schl sseltext c den der Empf nger mit seinem geheimen Exponenten d entschl sseln kann c m mod N und m c m m m m mod N Durch die Interpretation der Nachricht m als nat rliche Zahl kleiner als N ergibt sich da die Bitl nge der Nachricht nicht l nger als die des RSA Moduln sein kann In der Tat verschl sselt m
128. uren 3 4 Einfaches RSA Key Sharing Das RSA Verfahren hat die erstaunliche Eigenschaft da es auf einem Problem beruht da sehr einfach zu erkl ren aber offenbar sehr schwer zu l sen ist Der gr te Vorteil der sich daraus ergibt sind die sehr soliden Argumente f r die Sicherheit von RSA die wesentlich besser fundiert sind als diejenigen f r weniger transparente Verfahren wie etwa die symmetrische DES Chiffre Ein anderer Vorteil ist die M glichkeit andere Kryptosysteme auf RSA aufzubauen zum Beispiel das in diesem Abschnitt vorgestellte RSA Key Sharing Schl sselerzeugung Um einen geheimen RSA Schl ssel d p q auf n Teil nehmer aufzuteilen die ihn dann nur gemeinsam verwenden k nnen w hlt der Geber f r jeden Teilnehmer i zuf llige Exponenten d aus der Menge 1 p 1 q 1 deren Summe modulo p 1 q 1 wieder den eigentlichen Ex ponenten d ergibt gt di d mod p 1 g 1 21 Den Teilnehmern bermittelt er die Teilschliissel d N es ist absolut not wendig den Teilnehmern die Faktorisierung N pq zu verheimlichen da sie ansonsten den geheimen Exponenten d berechnen k nnten Schl sselverwendung Da RSA Berechnungen einfache Exponentiationen sind gelten die allgemein bekannten Rechenregeln hierzu insbesondere auch die Ho momorphie mh d q Uma Damit ist auch klar da die Teilschl ssel d N dazu verwendet werden k nnen um Teilergebnisse s der Berechnung s m
129. verzeichnis 11 13 16 16 17 19 21 22 27 29 31 32 33 35 35 38 39 44 44 48 65 71 76 77 79 C UML Klassendiagramme D Benutzerhandbuch Kommandozeilenapplikationen Deb EileSh rer eu mau aOR doy a ENG ee as D 2 KeyEscrow oi 28 dk tet Be a ae en E Benutzerhandbuch Programmierschnittstelle E 1 Secret Sharing Basisfunktionalit t E 2 Key Sharing Basisfunktionalit t E 3 Der Shamir KeyStore aoaaa E 4 DerKeySharer KeyStOrT 2 0 0 02080 E 5 Das Key Escrow System aoaaa Index 81 87 87 88 89 89 89 90 91 91 91 Kapitel 1 Einleitung Durch die in den letzten Jahren rasant vorangeschrittene Digitalisierung von Informationen und deren Speicherung auf Rechnersystemen sowie durch die immer umfassendere Vernetzung dieser Rechnersysteme und die damit einher gehenden neuen M glichkeiten zum Datenaustausch haben sich betr chtliche Probleme bez glich der Datensicherheit ergeben Insbesondere besteht ein gro er Widerspruch zwischen dem auf offenen Net zen basierenden Internet das sich mittlerweile als absolut dominantes Kommu nikationsmedium durchgesetzt hat und mit dessen Hilfe sich gewaltige Kosten senkungs und Effizienzsteigerungen in fast allen rechnergest tzten Abl ufen erzielen lassen und den Anforderungen zum Schutz von personenbezogenen oder unternehmenskritischen Daten In diesem Zusammenhang hat die mathematische
130. word gt Der rekonstruierte Schliissel wird in eine mit dem angegeben Password geschiitzte PKCS12 Datei filename geschrieben Der gewtinschte Schltissel wird anhand des zugeh rigen Zertifikats in der Datei certfilename identifziert Zur Rekonstruktion ist ein Recovery Key notwendig der dem Keystore keystore entnommen wird er wird automatisch gesucht und mit dem Pafwort password geladen Wenn es sich dabei nur um Teilschliissel handelt wird statt der PKCS12 Datei der partiell dechiffrierte Schliissel ausgegeben Die so entste henden Teile k nnen mit dem KeySharer zusammengesetzt werden Wenn der Recovery Schl ssel berhaupt nicht vorliegt wird statt dessen die verschl sselte PKCS7 Datei ausgegeben Diese kann dann weitergereicht werden beispielswei se im Rahmen eines verteilten Recovery mit der Anwendung KeySharer 75 Kapitel 6 Ausblick Wir haben mit dieser Arbeit einen Einstieg vor allem in Techniken des Secret Sharing und der Threshold Cryptography geben wollen Au erdem haben wir uns mit der Key Escrow Problematik und einigen Ans tzen hierzu besch ftigt Durch die Implementierung eines gro en Teils der genannten Algorithmen konn ten wir zum einen deren Einsatzf higkeit demonstrieren und zum anderen einen hoffentlich n tzlichen Beitrag zum FlexiTrust Projekt des Fachgebietes leisten Entsprechend unserer urspr nglichen Motivation n mlich der sicheren Spei cherung privater Schl ssel haben wir uns auf eine bestimmte M
131. word verwendet um den Schl ssel zu lesen und das optionale Integrit tspa wort storepass um die Unversehrtheit des Einga bekeystores zu pr fen Falls es sich dabei nicht um einen JavaKeyStore JKS handelt kann dessen Typ mit der Option storetype angegeben werden Die Teilschl ssel erhalten in den jeweiligen Keystores ebenfalls den Namen alias Die erzeugten Keystores werden als JavaKeyStores in den Dateien keystore 1 bis keystore n abgelegt Falls diese Dateien bereits zuvor existierten werden sie eingelesen und durch den neuen Schl ssel erg nzt Die neuen Keystores wer den ohne Integrit tspa wort gespeichert der Schl ssel selbst wird durch das Pa wort password gesch tzt Ein neues Schl sselpaar kann mit dem Befehl 72 KeySharer create lt alias gt t lt threshold gt n lt shares gt keystore lt keystore gt keytype lt type gt keysize lt keysize gt password lt password gt erzeugt und verteilt werden Wie oben werden dabei die Teilschl ssel auf Key stores in Dateien keystore 1 bis keystore n verteilt Sie werden dort unter dem Namen alias abgelegt und mit dem Pa wort password gesch tzt Der Typ des Schl ssel kann entweder RSA oder ElGamal sein die optionale keysize gibt die Schl ssell nge an Das verwendete Key Sharing Verfahren h ngt von der Art des Schl ssels und von dem Bedarf nach Redundanz ab RSA Schl ssel werden nicht redundant nach dem einfachen Verfahren aus Abschnitt 3 4 oder re
132. z hlen von K Testweise wird jeder Kandidat d durch Konkatenation mit zuf lligen Bits auf die doppelte L nge gebracht Die entstehende Zahl wird durch p geteilt Ganzzahldivision ohne Rest falls dabei eine Primzahl q ent steht setzt man N pq und hat damit einen RSA Modulus erhalten dessen obere H lfte aus dem Chiffretext d besteht aufgrund von bertragsbits und dem fehlenden Rest bei der Ganzzahldivision kann die obere H lfte Nz c 1 auch um eine Einheit zu niedrig sein Hierzu werden mehrere Versuche not wendig sein allerdings aufgrund des Primzahltheorems nicht allzu viele Die Chiffre F erzeugt ohne gro en Rechnenaufwand eine gewisse Anzahl randomi sierter Kandidaten Auch hier mu das Verfahren erst bei einer vorgegebenen Iterationsschranke Bo neu gestartet werden mit einem neuen p Zur Verdeutlichung der Funktionsweise der Suche nach N wollen wir ein klei nes und stark vereinfachtes Beispiel geben Wir wollen einen RSA Schl ssel mit 6 Dezimalstellen erzeugen wobei der Primfaktor p den umgekehrt gelesenen er sten drei Ziffern des Moduln N entspricht Zuf llig entnehmen wir aus der Prim zahltabelle die Kandidaten p 271 953 647 443 751 337 607 823 523 107 und verschl sseln sie zu d 172 359 746 344 157 733 706 328 325 701 Unser erster Versuch f hrt zu 172512 die letzten drei Ziffern zuf llig erg nzt ganzzahlige Division durch 271 ergibt 636 keine Primzahl Aber schon im drit te
133. zt werden k nnen In diesem umstrittensten Einsatzgebiet von Key Recovery sollen Schl ssel ausdr cklich ohne Wis sen und Zustimmung der Betroffenen wiederhergestellt werden und den Beh rden zug nglich gemacht werden Neben dieser Verdecktheitseigen schaft besteht noch ein weiterer Unterschied zu anderen Formen von Key Recovery n mlich daf der Zugriff nicht auf gespeicherte Daten beschr nkt bleibt sondern vor allem auch Kommunikationsvorg nge entschlisselt werden sollen Signaturschliissel In all den oben genannten Situationen geht es um Dechiffrier Schliissel Im Gegensatz dazu gibt es keinen Grund Signaturschltissel wieder herstellen zu wollen Vielmehr muf dies verhindert werden Wenn ein Signatur schliissel verloren geht k nnen keine weiteren Signaturen ausgestellt werden Trotzdem bleiben die bis dahin geleisten Signaturen g ltig und k nnen auch anhand des 6ffentlichen Schltissels verifiziert werden Um neue Signaturen aus stellen zu k nnen kann einfach ein neues Schl sselpaar erzeugt werden so da sich kein grofer Nutzen darin ergibt den verlorenen Schliissel wiederherstel len zu k nnen Die Unbequemlichkeit ein neues Schliisselpaar verwenden zu m ssen steht dem Risiko gegen ber daf jemand anders den Schl ssel wieder herstellen und damit unberechtigt digitale Signaturen ausstellen k nnte Dies ist auf jeden Fall zu vermeiden Es gibt also auch von seiten staatlicher Uberwachungsorgane keinen nach vollzieh
134. zu gibt es Verfahren die ber unterschiedlich wertvolle An teile verf gen oder explizite Gruppen access structures von Anteilen zur Rekonstruktion vorgeben e Offensichtlich f hrt ein fehlerhafter Beitrag eines Teilnehmers bei der Re konstruktion zu einem fehlerhaften Ergebnis Das richtige Ergebnis und die Identit t des Teilnehmers l t sich im allgemeinen dann nur durch versuchsweises Durchprobieren aller m glicher Gruppen von Teilnehmern errechnen Ein Secret Sharing Verfahren hei t robust wenn es den Teil nehmern m glich ist zu kontrollieren ob andere Teilnehmer sich an das Protokoll halten Hierzu mu man zus tzliche Informationen in die Teilge heimnisse einbringen Man spricht auch von verifizierbarem Secret Sharing insbesondere wenn auch das Verhalten des Gebers gepr ft werden kann e Ein Secret Sharing Verfahren hei t ideal wenn die Bitl nge des gr ten Anteils der geheim gehalten werden mu die Bitl nge des Geheimnisses nicht bersteigt Es l t sich zeigen da ideale Verfahren nicht gleichzeitig robust sein k nnen e Wenn das Geheimnis in Berechnungen verwendet werden soll dann ist es unter Umst nden m glich die Berechnung in Teilberechnungen f r die Inhaber der Teilgeheimnisse aufzubrechen so da diese die Berech nung durchgef hren k nnen ohne das Geheimnis dabei rekonstruieren zu m ssen Dies wird als Function Sharing bezeichnet und eignet sich ins besondere f r Funktionen mit gewisse

Konzepte für eine sichere Schlüsselverwaltung

Contents

Download Pdf Manuals

Related Search

Related Contents

Konzepte f&uuml;r eine sichere Schl&uuml;sselverwaltung

Contents

Download Pdf Manuals

Related Search

Related Contents

Konzepte für eine sichere Schlüsselverwaltung