Yet another insecure group key distribution scheme using secret sharing

Die Arbeit widerlegt die Sicherheit und Funktionalität des auf Secret-Sharing basierenden Gruppen-Schlüsselverteilungsschemas UMKESS und bezeichnet dessen Design als unzulänglich, womit es sich als weiterer fehlerhafter Ansatz in einer langen Reihe ähnlicher Schemata erweist.

Das Wesentliche

Das Geheimnis der kaputten Schlüsselverteilung

Eine Zusammenfassung von Chris J. Mitchells Kritik am UMKESS-Verfahren

Stellen Sie sich vor, eine Gruppe von Freunden möchte ein gemeinsames Geheimnis (einen Schlüssel) teilen, damit sie sich alle sicher unterhalten können. Um das zu tun, vertrauen sie einem neutralen Vermittler, dem „Schlüssel-Manager" (im Papier KGC genannt).

Ein neuer Vorschlag namens UMKESS sollte genau das tun: Der Manager verteilt Schlüssel an verschiedene Freundesgruppen, indem er ein mathematisches Zaubertrick namens „Geheimnis-Sharing" (Secret Sharing) benutzt. Die Idee ist, dass jeder ein kleines Puzzleteil bekommt und nur wer alle Teile hat, das Bild sieht.

Der Autor dieses Papers, Chris Mitchell, sagt jedoch ganz klar: „Das ist nicht nur unsicher, es funktioniert oft gar nicht richtig, und die Idee dahinter ist von Grund auf falsch."

Hier ist die Geschichte, warum das System versagt, erklärt mit einfachen Bildern:

1. Der mathematische Stolperstein (Das Puzzle, das nicht passt)

Stellen Sie sich vor, der Manager zeichnet eine Kurve (eine Linie), auf der die Geheimnisse versteckt sind. Jeder Freund bekommt ein paar Punkte auf dieser Linie. Um das Geheimnis zu finden, müssen die Freunde die Linie wiederherstellen.

Das Problem: Der Manager berechnet die Positionen der Punkte basierend auf der Summe der Nummern der Freunde in einer Gruppe.

• Beispiel: Gruppe A besteht aus Person 1 und Person 5 (Summe = 6). Gruppe B besteht aus Person 1, 2 und 3 (Summe = 1+2+3 = 6).
• Die Katastrophe: Da beide Gruppen die gleiche Summe (6) haben, versucht der Manager, zwei verschiedene Geheimnisse an denselben Punkt auf der Linie zu hängen. Das ist mathematisch unmöglich! Es ist, als würde man versuchen, zwei verschiedene Briefe in denselben Briefkasten zu stecken, ohne dass sie sich berühren. Das System bricht zusammen, noch bevor es beginnt.

2. Der Dieb im Haus (Der Insider-Angriff)

Das ist das gefährlichste Problem. Stellen Sie sich vor, Sie und Ihr Freund sind in zwei verschiedenen Gruppen. Ihr Freund (der Angreifer) ist nicht böswillig, aber er ist schlau.

• Der Trick: Der Angreifer fängt die Nachricht ab, die Sie an den Manager senden, und ändert ein einziges kleines Detail darin (eine Zahl). Er schickt dann die gefälschte Nachricht an den Manager weiter.
• Die Folge: Der Manager reagiert darauf und schickt dem Angreifer die richtigen Puzzleteile für die Gruppen, in denen er mit Ihnen zusammen ist. Durch die kleine Änderung, die er vorgenommen hat, kann er nun aus den Puzzleteilen, die er bekommt, und den Informationen, die er über Ihre Gruppen hat, Ihren persönlichen, langfristigen Geheimcode berechnen.
• Das Ergebnis: Der Angreifer hat nicht nur Ihren Code geknackt, sondern kann nun alle Geheimnisse entschlüsseln, die Sie jemals erhalten. Es ist, als würde ein Mitbewohner, der nur Ihre Post abfängt, Ihren Hausschlüssel nachbauen und damit in Ihr Schlafzimmer eindringen.

3. Die unsichere Post (Vertrauen ohne Beweis)

Das Papier kritisiert auch, dass die Autoren des UMKESS-Verfahrens nicht klar sagen, wie sicher die Nachrichtenübertragung ist.

• Sie sagen: „Der Manager sendet eine Liste der Gruppen." Aber was passiert, wenn ein Hacker diese Liste manipuliert?
• Das Szenario: Der Hacker ändert die Liste so, dass Sie denken, Sie sind in einer Gruppe mit Person X, dabei sind Sie aber eigentlich mit Person Y und Z. Sie erhalten den Schlüssel, glauben aber, er sei für eine andere Gruppe bestimmt. Das führt zu totaler Verwirrung und Sicherheitslücken.
• Der Autor sagt: Man kann nicht einfach annehmen, dass die Post sicher ist. Wenn man das nicht absichert, ist das ganze System wie ein Schloss, das man mit Knete gemacht hat.

4. Warum die Idee selbst falsch ist (Der falsche Vergleich)

Die Erfinder des UMKESS-Verfahrens sagten: „Unser System ist schneller und besser als andere!"

• Der Vergleich: Sie verglichen ihr System mit einem sehr alten, bekannten System, das schon lange als kaputt bekannt war. Das ist, als würde ein Autohersteller sagen: „Unser neues Auto ist sicherer als das Modell von 1980, das schon immer Bremsprobleme hatte." Das ist kein fairer Vergleich.
• Die Realität: Es gibt bereits moderne, bewährte und sichere Methoden, um Gruppen-Schlüssel zu verteilen. Die Erfinder ignorieren diese bewährten Standards komplett und erfinden das Rad neu – nur um es kaputt zu machen.

5. Warum „Reparaturen" nutzlos sind

In der Geschichte der Kryptografie gibt es einen traurigen Zyklus: Jemand erfindet ein System -> Jemand findet einen Fehler -> Jemand versucht, es zu reparieren -> Jemand findet einen neuen Fehler.

• Der Autor warnt davor, einfach „Flickwerk" zu veröffentlichen. Wenn man ein System repariert, indem man es so komplex macht, dass man digitale Unterschriften für alles braucht, dann hat man den ursprünglichen Vorteil (einfach und schnell) zerstört. Man könnte dann genauso gut ein bereits sicheres System benutzen.

Das Fazit in einem Satz

Das Paper ist eine Warnung: Hören Sie auf, neue, unsichere Verschlüsselungsmethoden zu veröffentlichen, nur weil sie „neu" klingen. Die Wissenschaft sollte sich darauf konzentrieren, Dinge zu beweisen, die wirklich sicher sind, anstatt immer wieder die gleichen alten Fehler zu wiederholen und sie dann mit Pflastern zu überkleben.

Es ist wie beim Bauen eines Hauses: Wenn das Fundament (die mathematische Logik) wackelig ist, hilft es nichts, die Farbe zu ändern oder die Vorhänge zu tauschen. Das Haus wird trotzdem einstürzen.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert ein langjähriges und wiederkehrendes Problem in der Kryptographie: Die Entwicklung von Gruppen-Schlüsselverteilungsprotokollen (Group Key Distribution), die auf Secret-Sharing-Techniken (geheime Aufteilung) basieren.

• Kontext: Seit über 30 Jahren werden Protokolle vorgeschlagen, die versuchen, Geheimnisse (Schlüssel) über Secret Sharing zu verteilen. Die Literatur ist voll von solchen Vorschlägen, die sich als unsicher herausstellen.
• Spezifisches Ziel: Das Paper untersucht ein kürzlich vorgeschlagenes Protokoll namens UMKESS (von Hsu, Harn und Zeng, 2020). Die Autoren von UMKESS behaupten, ein sicheres Protokoll für die gleichzeitige Verteilung mehrerer Gruppenschlüssel an verschiedene Gruppen von Benutzern durch eine vertrauenswürdige Autorität (Key Generation Centre, KGC) zu bieten.
• Das Kernproblem: Der Autor argumentiert, dass UMKESS nicht nur unsicher ist, sondern aufgrund fundamentaler Designfehler auch nicht immer funktioniert. Zudem ignoriert das Design die umfangreiche historische Evidenz über die Unzulänglichkeit solcher Ansätze.

2. Methodik und Analyse des UMKESS-Protokolls

Der Autor analysiert das UMKESS-Protokoll Schritt für Schritt, basierend auf der Beschreibung in [7].

Protokoll-Überblick:

• Setup: Ein KGC und $n$ Benutzer teilen sich langfristige Geheimnisse $x_i$. Es wird ein großes Primfeld $GF(p)$ und eine Hash-Funktion $h$ verwendet.
• Ablauf:
  1. Das KGC listet Gruppen $G_1, \dots, G_m$ mit ihren Mitgliedern.
  2. Benutzer senden zufällige Werte $r_{ij}$ an das KGC (unverschlüsselt/ungeschützt).
  3. Das KGC generiert für jeden Benutzer ein Polynom $f_i$, das durch bestimmte Punkte geht, die von den Gruppenmitgliedschaften und den gesendeten Zufallswerten abhängen.
  4. Das KGC sendet Punkte auf diesen Polynomen an die Benutzer zurück.
  5. Benutzer rekonstruieren das Polynom und berechnen die Gruppenschlüssel.

Die Analyse des Autors:
Mitchell untersucht das Protokoll auf logische Konsistenz, funktionale Korrektheit und kryptographische Sicherheit. Er identifiziert drei Hauptkategorien von Fehlern:

1. Funktionsfähigkeit: Ob das Protokoll unter realen Bedingungen überhaupt funktioniert.
2. Sicherheit: Ob ein Angreifer (Insider oder Outsider) Schlüssel oder langfristige Geheimnisse kompromittieren kann.
3. Design-Rationale: Ob der Vergleich mit anderen Protokollen und die gewählten Sicherheitsannahmen sinnvoll sind.

3. Wichtige Beiträge und Ergebnisse

Der Autor liefert folgende kritische Erkenntnisse:

A. Funktionsfehler (Definitional Issue)

Das Protokoll kann in nicht unwahrscheinlichen Fällen versagen.

• Das Problem: Das Polynom für einen Benutzer wird durch Punkte definiert, deren x-Koordinaten die Summe der Indizes der Gruppenmitglieder ($S(G_i)$) sind.
• Der Fehler: Es ist möglich, dass zwei verschiedene Gruppen die gleiche Summe der Mitgliederindizes haben (z. B. Gruppe $\{U_1, U_5\}$ und $\{U_1, U_2, U_3\}$ ergeben beide Summe 6).
• Konsequenz: Wenn ein Benutzer Mitglied zweier solcher Gruppen ist, muss das Polynom durch zwei Punkte mit derselben x-Koordinate, aber unterschiedlichen y-Koordinaten gehen. Ein Polynom kann dies nicht erfüllen. Das Protokoll ist in diesen Fällen mathematisch undefiniert und funktioniert nicht.

B. Kritische Sicherheitslücke (Insider-Angriff)

Dies ist der schwerwiegendste Befund. Ein böswilliger Insider (ein legitimer Benutzer $U_a$) kann das langfristige Geheimnis ($x_v$) eines anderen Benutzers ($U_v$) kompromittieren.

• Angriffsszenario:
  1. $U_a$ ist Mitglied derselben zwei Gruppen wie $U_v$.
  2. $U_a$ fängt die Nachricht von $U_v$ ab, die die Zufallswerte $r_{ij}$ enthält, und manipuliert einen Wert (z. B. setzt er $r'_2 = r_1$).
  3. Das KGC berechnet daraufhin ein Polynom $f_v$ basierend auf den manipulierten Werten.
  4. $U_a$ erhält die Punkte vom KGC und kennt die korrekten Gruppenschlüssel $K_{v1}, K_{v2}$.
  5. Da $U_a$ die Manipulation kennt, kann er eine lineare Gleichung aufstellen, die die Differenz der y-Werte des Polynoms $f_v$ an zwei bekannten Punkten beschreibt.
  6. Zusammen mit den vom KGC gesendeten Punkten hat $U_a$ ein lineares Gleichungssystem, das ausreicht, um das gesamte Polynom $f_v$ zu rekonstruieren.
  7. Durch Auswertung von $f_v$ an der Stelle $v$ erhält $U_a$ den Wert $x_v + r_0$. Da $r_0$ öffentlich ist, kennt $U_a$ nun das langfristige Geheimnis $x_v$ von $U_v$.
• Ergebnis: Ein Insider kann die Identität und alle zukünftigen Schlüssel eines anderen Benutzers erlangen. Dies widerlegt die Sicherheitsbehauptungen (Theorem 5) der Originalautoren.

C. Probleme bei der Zuverlässigkeit (Reliable Broadcasts)

Das Protokoll macht implizite Annahmen über die Integrität der Broadcast-Nachrichten (Gruppenlisten und Hashes der Schlüssel), ohne diese explizit zu schützen.

• Wenn die Gruppenliste manipuliert wird, kann ein Benutzer denken, er teilt einen Schlüssel mit einer falschen Gruppe.
• Wenn die Liste der Hashes der Schlüssel manipuliert wird, kann ein Insider einen Angreifer dazu bringen, einen falschen Schlüssel zu akzeptieren, ohne dass dies erkannt wird.

D. Mangelnde Begründung und Vergleich

• Ineffiziente Vergleiche: Die Originalautoren vergleichen UMKESS mit einem Public-Key-System (was erwartungsgemäß teurer ist) und mit einem anderen bekannten, unsicheren Secret-Sharing-Protokoll (Harn & Lin). Dies ist kein fairer oder sinnvoller Vergleich.
• Ignorieren etablierter Lösungen: Es gibt bereits bewährte, formal verifizierte Protokolle (z. B. ISO/IEC 11770-5), die das gleiche Ziel sicher und effizient erreichen, ohne die hier beschriebenen Schwächen zu haben.

4. Signifikanz und Fazit

Signifikanz:
Das Paper ist ein weiteres warnendes Beispiel in einer langen Geschichte von fehlerhaften Secret-Sharing-basierten Gruppen-Schlüsselprotokollen. Es zeigt, dass:

1. Neue Vorschläge oft die historischen Fehler (wie Insider-Angriffe und fehlende Forward Secrecy) ignorieren.
2. Selbst wenn ein Protokoll „fixiert" wird, geschieht dies oft ohne formale Sicherheitsbeweise, was zu einem Zyklus von „Design -> Brechen -> Falsches Fixieren" führt.
3. Die Einführung von Signaturen als „Fix" (wie in anderen Arbeiten vorgeschlagen) die Komplexität so stark erhöht, dass der ursprüngliche Vorteil von Secret Sharing (Effizienz) verloren geht.

Fazit und Empfehlungen:
Chris J. Mitchell zieht zwei klare Schlussfolgerungen:

1. Die wissenschaftliche Gemeinschaft sollte keine Sicherheitsprotokolle mehr veröffentlichen, für die keine robusten, formalen Sicherheitsbeweise vorliegen.
2. Es sollte vermieden werden, „fixierte" Versionen unsicherer Protokolle zu veröffentlichen, wenn diese Fixierungen entweder keinen Sicherheitsbeweis bieten oder den ursprünglichen Designzweck (z. B. Effizienz) durch unnötige Komplexität (wie Signaturen) zunichtemachen.

Das Paper unterstreicht die Notwendigkeit, sich an etablierte, formal verifizierte Standards und Modelle für Gruppen-Schlüsselvereinbarung zu halten, anstatt ständig neue, fehleranfällige Varianten auf Basis von Secret Sharing zu erfinden.