Kryptographische Schlüssel aufteilen

Wissenschaft Informatik
#1

Hallo,

es ist relativ leicht, einen kryptographischen Schlüssel auf zwei Personen aufzuteilen, sodass beide sich zusammentun müssen, um eine Nachricht zu entschlüsseln: Man generiert eine Zufallszahl, die genauso lang ist wie der Schlüssel, und gibt einer Person diese Zufallszahl, der anderen Zufallszahl XOR Schlüssel.

Das kann man ja auch noch leicht auf N Schlüsselfragmente verallgemeinern, sodass alle Fragemente verfügbar sein müssen.

Meine Frage ist jetzt: kann man das auch so verallgemeinern, dass z.B. 2 von 3 Fragmenten reichen, um einen Schlüssel zu rekonstruieren, einer aber definitiv nicht reicht? Oder noch allgemeiner, sodass k von N Fragmente reichen, mit 1

#2

Meine Frage ist jetzt: kann man das auch so verallgemeinern,
dass z.B. 2 von 3 Fragmenten reichen, um einen Schlüssel zu
rekonstruieren, einer aber definitiv nicht reicht? Oder noch
allgemeiner, sodass k von N Fragmente reichen, mit 1

#3

Morgen!

Meine Frage ist jetzt: kann man das auch so verallgemeinern,
dass z.B. 2 von 3 Fragmenten reichen, um einen Schlüssel zu
rekonstruieren, einer aber definitiv nicht reicht?

Das nennt sich RAID Array!

Ist zwar für eine andere Nutzung würde aber genau deine Forderung
erfüllen.

Gruß
Stefan

#4

Hallo,

Meine Frage ist jetzt: kann man das auch so verallgemeinern,
dass z.B. 2 von 3 Fragmenten reichen, um einen Schlüssel zu
rekonstruieren, einer aber definitiv nicht reicht?

Das nennt sich RAID Array!

Ist zwar für eine andere Nutzung würde aber genau deine
Forderung
erfüllen.

Das ist das erste mal, dass ich davon hoere, dass RAID Arrays in irgend einer Hinsicht kryptographisch sicher sind.
Koenntest du bitte erklaeren, wieso du annimmst dass sie es sind?

Gruesse,
Moritz

#5

Das ist das erste mal, dass ich davon hoere, dass RAID Arrays
in irgend einer Hinsicht kryptographisch sicher sind.
Koenntest du bitte erklaeren, wieso du annimmst dass sie es
sind?

Rein theoretisch ginge das, in dem du z.B. ein System analog zu RAID-4 benutzt und den Schlüssel über alle Festplatten verteilst. Nimm z.B. folgende Abbildung:
http://de.wikipedia.org/wiki/Datei:RAID_4.svg

Angenommen der Schlüssel wäre (A1||A2||A3)
Dann würde keine Festplatte den gesamten Schlüssel haben, sondern alle nur einen Teil davon. Die vierte Platte verfügt nur über eine geXORte Version von A1, A2 und A3 und kann damit alleine auch nichts anfangen. Da auf der vierten Festplatte eben noch ein Paritäts-Bit in XOR-Form liegt, sind damit mindestens 3 Festplatten der vier Festplatten nötig, um den Schlüssel zu rekonstruieren. Auch würde keine der Festplatten den Schlüssel als ganzes kennen.

Aber:
Mit einem normalen RAID geht das nicht, weil da hast du üblicherweise keinen Einfluss darauf, wo auf der Festplatte eine Datei abgespeichert wird. Und hier ist es essentiell, dass der Schlüssel zu gleichmäßigen Teilen auf die Festplatten verteilt ist. Einfach nur ein RAID zu benutzen und den Schlüssel zu speichern bringt dagegen gar nichts, weil der dann in fast allen Fällen komplett auf einer Festplatte liegen wird. Außerdem musst du das ganze ja auch noch auf mehrere Rechner verteilen, denn innerhalb eines Systems machts das ganze ja ohnehin keinen Sinn.

Also:
Mit einem handelsüblichen RAID geht das nicht. Man könnte sich aber selber ein System welches an das RAID-4 Prinzip angelehnt ist (wie oben beschrieben) basteln, aber mit RAID hat das dann eigentlich überhaupt nichts mehr zu tun und die Sicherheit beruht dann ja v.a. darauf, dass jeder nur einen Teil des Schlüssels hat und die Information auf der Paritätsplatte durch das XOR keinen Rückschluss auf den Schlüssel zulässt.

Das ganze ließe sich auch so umgestalten, dass z.B. auch zwei Festplatten fehlen können, also analog zu RAID-6 mit zwei Paritätsfestplatten:
http://de.wikipedia.org/wiki/Datei:RAID_6.svg

#6

Hallo,

vielen Dank, das sieht sehr gut aus. Ich werde am Wochenende mal eines der Paper lesen…

Grüße,
Moritz

#7

Abend!

Das ist das erste mal, dass ich davon hoere, dass RAID Arrays
in irgend einer Hinsicht kryptographisch sicher sind.

Muß sie bei deiner Aufgabenstellung doch gar nicht sein!

Koenntest du bitte erklaeren, wieso du annimmst dass sie es
sind?

Nehmen wir an die Nachricht wird mit einer AES256 verschlüsselt.
Ich teile den Schlüssel nun in der Mitte und gebe den Personen

  1. Person, die ersten 128 Bit des Schlüssels und eine Kennung 1
  2. Person, die zweiten 128 Bit des Schlüssels une eine Kennung 2
  3. Person, das XOR Ergebnis von dem 1. und 2. Teil des Schlüssels

Somit können immer zwei Personen den gesamten Schlüssel herstellen,
die Sicherheit gegenüber Dritten entspricht einer AES256, die
Sicherheit der 3 Schlüsselträger ist eine AES128.

Gruß
Stefan

#8

Abend!

aber mit RAID hat das dann eigentlich überhaupt nichts mehr zu tun

Ich meinte auch nicht das man einfach ein RAID Array dazu nutzen
könnte aber das Verfahren entspricht der Aufgabenstellung.

Gruß
Stefan

#9

Ich teile den Schlüssel nun in der Mitte und gebe den Personen

  1. Person, die ersten 128 Bit des Schlüssels und eine Kennung
    1
  2. Person, die zweiten 128 Bit des Schlüssels une eine Kennung
    2
  3. Person, das XOR Ergebnis von dem 1. und 2. Teil des
    Schlüssels

Das Problem ist halt nur, dass bei einer Verteilung des Schlüssels auf n Teilnehmer immer n-1 erforderlich sind, um den Schlüssel zu rekonstruieren. Auch kennen die Personen 1 und 2 in deinem Beispiel die Hälfte des Schlüssels im Klartext. Damit reduziert sich erstens generell die Stärke des Schlüssels auf die eines 128bit Schlüssels. Der Rechenaufwand zum Knacken des gesamten Schlüssels wird damit dramatisch gesenkt, so dass das Verfahren in dieser Hinsicht nicht mehr als sicher betrachtet werden kann.

Außerdem gibt es vielleicht auch noch eine Reihe weiterer Angriffe in der Kryptoanalyse die dieses Wissen über die Hälfte des Schlüssels noch besser ausnutzen können, so dass die Stärke dann vielleicht noch deutlich unter 128bit liegen würde.

Ein weiterer Nachteil ist, dass das Verfahren in Bezug auf das Sicherheitskriterium Verfügbarkeit sehr schlecht abschneidet, denn wenn eine der Personen ein falsches Teil des Schlüssels liefert, dann hast du keine vernünftige Möglichkeit rauszufinden, wer der „Falschspieler“ ist oder was der eigentliche Schlüssel ist. Denn RAID setzt ja darauf, dass sich alle Teilnehmer gutartig verhalten, kryptografische Verfahren gehen jedoch immer davon aus, dass sich einer oder auch mehrere Teilnehmer als Angreifer verhalten. Und auf sowas ist RAID nicht ausgelegt.

Als kryptografisch sicher würde ich das Verfahren daher in keiner Weise betrachten.

Bei Schlüsselverteilung mithilfe von Polynom-Interpolation kennt eben niemand der Leute, auf die ich den Schlüssel verteile, auch nur einen Hauch des Klartextes des Schlüssels, so dass er kein Zusatzwissen bekommt, dass ihm beim Knacken des Schlüssels behilflich wäre. Auch kann man durch die entsprechende Wahl des Polynom-Grades sehr gut den Trade-off zwischen Verfügbarkeit (es sind nur wenige Personen nötig um den Schlüssel zu rekonstruieren) und Resistenz gegen viele Angreifer (es sind viele bösartige Teilnehmer nötig, um an den Schlüssel zu kommen) bewerkstelligen, da sich beide Eigenschaften konträr gegenüberstehen und man nicht beides im vollem Maße haben kann.

#10

Das Problem ist halt nur, dass bei einer Verteilung des
Schlüssels auf n Teilnehmer immer n-1 erforderlich sind, um
den Schlüssel zu rekonstruieren.

So war ja auch die ursprüngliche Aufgabe.

Der Rechenaufwand
zum Knacken des gesamten Schlüssels wird damit dramatisch
gesenkt, so dass das Verfahren in dieser Hinsicht nicht mehr
als sicher betrachtet werden kann.

Naja, zumindest heute ist eine AES128 immer noch als sicher
anzusehen.

Außerdem gibt es vielleicht auch noch eine Reihe weiterer
Angriffe in der Kryptoanalyse die dieses Wissen über die
Hälfte des Schlüssels noch besser ausnutzen können, so dass
die Stärke dann vielleicht noch deutlich unter 128bit liegen
würde.

Nein, das würde bedeuten das eine AES kein Zufallsorakel ist und der
Beweis steht aus.
Oder anders ausgedrückt es würde bedeuten das zwischen Schlüssel,
Klartext und Geheimtext ein statistischer Zusammenhang besteht.

Ein weiterer Nachteil ist, dass das Verfahren in Bezug auf das
Sicherheitskriterium Verfügbarkeit sehr schlecht abschneidet,
denn wenn eine der Personen ein falsches Teil des Schlüssels
liefert, dann hast du keine vernünftige Möglichkeit
rauszufinden, wer der „Falschspieler“ ist oder was der
eigentliche Schlüssel ist.

Wenn man die Aufgabenstellung weiter modifiziert dann kann es durchaus
sein, das diese einfache Methode nicht mehr sinnvoll ist, kein Zweifel.

Als kryptografisch sicher würde ich das Verfahren daher in
keiner Weise betrachten.

Was heißt denn bitte „kryptografisch sicher“?

Gruß
Stefan

#11

Das Problem ist halt nur, dass bei einer Verteilung des
Schlüssels auf n Teilnehmer immer n-1 erforderlich sind, um
den Schlüssel zu rekonstruieren.

So war ja auch die ursprüngliche Aufgabe.

Nein, die ursprüngliche Aufgabe lautete:
Gibt es ein Verfahren zur Schlüsselverteilung, so dass k von N Fragmenten (mit 1