Hi,
ich frage mich wie sicher ist Shamir’s secret sharing protocol? Und welche möglichen Angriffe sind denkbar?
Vielen Dank für eure Hilfe,
Klausi
Hy,
ich frage mich wie sicher ist Shamir’s secret sharing
protocol? Und welche möglichen Angriffe sind denkbar?
ich frage mich wie sicher ist Shamir’s secret sharing
protocol? Und welche möglichen Angriffe sind denkbar?
Shamir’s secret sharing basiert auf Polynom-Interpolation. Weiß man von einem Polynom vom Grad n mehr als n, also n+1, Stellen, dann kann man das dazugehörige Polynom errechnen. Weiß man weniger als n+1 Stellen, dann verbleiben unendlich viele Möglichkeiten, wie man Polynome durch diese Stellen legen kann. Man verteilt also n+1 Stellen (inkl Funktionswert, werden auch Shares genannt) des Polynoms auf mindestens genausoviele Server/Beteiligte. Damit kennt keiner der Beteiligten das Geheimnis komplett. Durch Abruf der einzelnen n+1 Stellen von den Servern/Beteiligten lässt sich das Geheimnis jedoch wieder herstellen.
Das ganze dürfte relativ sicher sein, zumindest sind mir keine Angriffe bekannt, die das Protokoll grundlegend brechen können. Allerdings ist die Polynom-Interpolation auch noch nicht so gut kryptografisch erforscht, wie z.B. die Primfaktor-Zerlegung, die z.B. RSA und ähnlichen Algorithmen zugrunde liegt. Da das mathematische Problem jedoch ähnlich einfach ist, wie das von RSA, ist die Wahrscheinlichkeit eher gering, dass es da noch durchschlagende Entdeckungen geben wird.
Mögliche Angriffe:
Liefern einzelne Server falsche Funktionswerte, dann könnte das Ergebnis bei der Rekonstruktion des Geheimnisses falsch, d.h. das z.B. der Key fehlerhaft wäre. Dies führt dann dazu, dass z.B. der Dienst, der mit dem Protokoll genutzt werden sollte, nicht genutzt werden kann, somit liegt eine DoS Attacke vor. Verteilt man die n+1 Ergebnisse auf genau n+1 Server, dann reicht es einem Angreifer bereits, wenn er einen Server unter seine Kontrolle bringt. Begegnen kann man dem Problem auf verschiedene Weisen: Redundanz der Aufteilung, Aufteilen von mehr als n+1 Stellen, Verwenden von Checksummen zur Erkennung von gefälschten Funktionswerten, etc…
Gleiches gilt natürlich, wenn genügend viele Server keine Funktionswerte liefern. Ursache dafür könnten herkömmliche Angriffe auch ohne Kenntnis des Protokolls sein. Man muss auf jeden Fall dafür Sorge tragen, dass eine ausreichende Robustheit des Systems gegen Ausfall oder Verfälschung vor Einzelergebnissen vorliegt.
Ein anderes Szenario wäre, wenn ein Angreifer soviele Server unter seine Kontrolle bringt, dass er n+1 der Shares kennt. Dann kann er das Geheimnis selbst berechnen. Die Server müssen also vernünftig abgesichert sein, damit ein Angreifer nicht die Kontrolle gar über die Mehrzahl der Server bekommen kann. Da Secret-Sharing-Protokolle aber meist dann eingesetzt werden, wenn Geheimnisse auf verschiedene Institutionen aufgeteilt werden sollen, sollte dies ohnehin nicht sehr einfach sein, da eine hohe Heterogenität der Systeme vorliegen sollte. Betreibt man die Server innerhalb einer Institution, dann sollte man selbst für eine Heterogenität der Server sorgen.
Bringt ein Angreifer weniger als n+1 Server unter seine Gewalt, dann fehlen ihm Shares zur Berechnung des Geheimnisses. Nun könnte er natürlich versuchen, mit Brute-Force das verbleibende Share zu errechnen. Eine in vernünftiger Zeit mathematische Hervorgehenensweise fehlt jedoch hierfür, so dass bei ausreichend komplexer Wahl des Polynoms dieses eher ausgeschlossen werden kann.
Ähnlich wie bei RSA kann natürlich dies Wahl eines schwachen Polynoms bzw Primzahlenpaars dazu führen, dass das ganze berechenbar wird. Die Wahl des Polynoms und der zugrunde liegende Zufallsgenerator müssen also sicher sein, allerdings trifft dies praktisch auf alle kryptographischen Verfahren zu und ist demnach nichts spezielles für Shamirs secret sharing.
mfg
deconstruct
Ha, ha, ha!
Hab ich nach nem Google Link gefragt? Wenn du keine Antwort weißt spar dir deinen Kommentar!
1 „Gefällt mir“
Hallo erstmal,
Hab ich nach nem Google Link gefragt? Wenn du keine Antwort
weißt spar dir deinen Kommentar!
Also zum einen war ich zu faul auf so eine magere StudienfragenFrage eine Antwort zu schreiben (deconstruct hat das ja etwas ausführlicher ausgeführt) und zum anderen steht das alles auch in meiner Antwort drin. Lernresistent?
Dr. Weiss (Berlin) hat dazu mal vor ein paar Jahren ebenso wie Schneier einige Ausführungen gemacht. Kurz (so wie deine Frage auch gestellt war): Ja, es ist möglich.
Gruß
h.
1 „Gefällt mir“