Noch mehr Spaß mit “Bingo Voting”

Am “preisgekrönten” Wahlverfahren “Bingo Voting” der Uni Karlsruhe kommen mir immer mehr Zweifel. Nun auch statistische. Über false positives und Manipulationen.

Ich habe vor ein paar Tagen schon Zweifel für den Fall besonders kleiner Wahlen (wenig Kandidaten, wenig Wähler) geäußert. Betrachten wir nun mal den anderen Fall, große Wahlen. Um die Problematik wieder deutlich zu machen gehen wir mal von einer ungewöhnlich großen Wahl aus. Tun wir mal so, als stünden 100 Kandidaten zur Wahl und 50 Millionen Deutsche würden an einer Wahlmaschine wählen. Das ist natürlich etwas unrealistisch, aber es geht ja darum, die Mängel gut erkennbar offenzulegen. Und letztlich machen die Autoren ja auch keine quantitativen oder qualitativen Aussagen dazu, für welche Größenordnungen das Verfahren taugen soll. Die Abstimmung mit Papierwahlzetteln degeneriert übrigens nicht, wenn die Zahl steigt. Es könnten problemlos alle Deutschen oder alle Europäer ihren Zettel in eine einzige Urne werfen, ohne daß das Verfahren prinzipbedingt schlechter würde.

“Bingo Voting” hat jedoch die Eigenschaft, daß es nicht skaliert, für große Zahlen funktioniert es auch nicht. Das Problem dabei ist, daß mit steigender Wähler- oder Kandidatenzahl auch die Zufallszahlen länger werden müßten. Das können sie aber nicht, weil es eine Grenze dessen ist, was dem Wähler noch zumutbar ist und von ihm verglichen werden würde. Werden die Zahlen, die der Wähler vergleichen soll, zu lang, sinken die Akzeptanz und der Wille zur Verifizierung. Schon daher degeneriert “Bingo Voting” für große Zahlen.

Betrachten wir es aber näher. Einer der Autoren sagt in einem Forum, daß sie mit Zufallszahlen von 40 Bit arbeiten wollen, das sehen sie als noch zumutbar und ausreichend für das an, was an einem Wahltag an einer Wahlmaschine passieren kann. Ich drehe für die nachfolgende Betrachtung zur Verdeutlichung die Zahlen wie gesagt etwas hoch (100 Kandidaten, 50 Millionen Wähler).

In der Vorbereitungsphase müßte man also 100 * 50.000.000 = ca. 2³² Zufallszahlen ziehen.

Das reicht aber vermutlich nicht. Denn wenn die Zuteilung der Zufallszahlen an die Kandidaten nicht jeweils gleich groß ist, würde das Wahlergebnis verfälscht. Die Wahlmaschine müßte also zunächst mal beweisen, daß sie für jeden Kandidaten gleich viel Nein-Stimmen erzeugt hat. Wie das genau und zuverlässig funktionieren soll, sagen die Autoren nicht so genau. Es heißt lapidar

Additionally, the equal distribution of the committed dummy votes to the candidates is proven without opening the commitments. This can be done via randomized partial checking [JJR02] if the part of the commitment containing the candidate can be opened without revealing the random number.

JJR02 ist der Verweis auf Jakobsson, Juels, Rivest: Making Mix Nets Robust For Electronic Voting By Randomized Partial Checking. Ich habe das Paper noch nicht gelesen, nur mal überflogen, aber zumindest bisher ist mir nicht klar, wie die Bingo-Autoren das hier meinen. Im zitieren Paper geht es um Permutationen, die durch einzelne Tests teilweise verifiziert werden. Mir ist zumindest nicht direkt ersichtlich, wie das hier Anwendung finden und den Kandidaten-Teil des Commitments nachweisen könnte ohne die Zufallszahl aufzudecken. Es ist immer dubios wenn in einer Protokollbeschreibung die faulen Stellen mit solchen Selbstverständlichkeitsfloskeln überspielt werden und dem Leser aufgegeben wird, sich doch selbst etwas dazu zu denken wie das gemeint sein könnte. Die deutsche Version ist da etwas anders gelagert:

Es wird bewiesen, daß für jeden Kandidaten genau gleich viele Commitments erzeugt wurden (z. B. durch Erzeugen von mehr Commitments, als eigentlich benötigt werden, und zufälliges Aufdecken. Wir empfehlen Randomized Partial Checking, wie es weiter hinten erklärt wird). […] Dieser Beweis kann entweder durch einen großen Zero-Knowledge-Beweis geführt werden, oder er kann, wenn die Commitments eine zusätzliche Homomorphitätseigenschaft haben, über sogenanntes “Randomized Partial Checking” erfolgen.

Gemeint ist also die Beweisphase nach der Wahl. Ich halte es für schlampig, wenn man sich da immer erst überlegen muß, was sie da gemeint haben könnten und was sie mal empfehlen, anstatt daß die klipp und klar hinschreiben, was sie eigentlich wollen. Da können nämlich immer versteckte Fehler drin sein, die bei solchen Schlabber-Beschreibungen unentdeckt bleiben.

Würde man die Variante wählen, daß man mehr Commitments erzeugt und sie dann teilweise aufdeckt, könnte man ziemlich baden gehen. Denn man weiß ja nicht, und soll nicht wissen, welches Commitment zu welchem Kandidaten gehört, bevor man es testweise aufgedeckt und entwertet hat. Deshalb ist nicht gesagt, daß bei den Testaufdeckungen alle Kandidaten gleich oft erwischt werden, es könnte also sehr leicht passieren, daß die restlichen Stimmen nach dem Test-Aufdecken nicht mehr gleichverteilt sind, also das Verfahren die Eigenschaft gerade zerstört, die es nachweisen sollte.

Außerdem braucht man für solche Methoden sehr viel mehr Zahlen, als am Ende übrig bleiben, gute Werte sind etwa, 1000mal so viel zu produzieren und 999 davon aufzudecken. Also noch mal 2¹⁰ mal so viele Zufallszahlen. Ups. Geht nicht. Wir haben ja aus einem Zahlenraum von 2⁴⁰ schon 2³² Zahlen gezogen und sollen das jetzt vertausendfachen, brauchen also 2⁴² Zufallszahlen. Geht natürlich nicht. Und selbst wenn wir unterhalb von 2⁴⁰ blieben: Wenn man so viele Zufallszahlen aus einem so kleinen Raum ziehen muß, kommt es so gut wie sicher zu vielen Kollisionen, also vielen wiederholt gezogenen Zufallszahlen. Und im Paper steht nicht einmal, daß die Zufallszahlen verschieden sein müßten. Da steht nur Zufallszahlen, also könnten sie auch gleich sein, denn sonst wären sie nicht mehr ganz zufällig, und Zufallszahlengeneratoren dürfen auch kein Gedächtnis haben. Was ist aber, wenn da im Vorbereitungsfeld Doppel vorkommen? Dann würde das Verfahren selbst dann, wenn alles glatt läuft, im Ergebnis Manipulationen anzeigen, die nicht stattgefunden haben. Beispielsweise könnten Nein-Stimmen doppelt vorkommen und dann bei der abschließenden Aufdeckung wie eine Manipulation aussehen. Oder dieselbe Stimme könnte als Ja- und Nein-Stimme auftauchen. Oder als zwei Ja-Stimmen. Oder als gleiche Zahl für verschiedene Kandidaten. All dies wären Fälle, bei denen die Wahl vor Gericht landen würde und sicherlich aufgehoben würde – obwohl niemand angegriffen hat.

Tun wir jetzt aber mal so, als hätte der Ausrichter dafür gesorgt, daß in der Vorbereitung keine Zahl doppelt vorkommt.

Jetzt kommen 50 Millionen Wähler. Und wählen. Jedesmal wird eine Zufallszahl gezogen. Und da kann einiges passieren, denn der Zufallszahlengenerator darf ja kein Gedächtnis haben und pro Wähler nur eine einzige Zahl ausspucken – es ist nicht vorgesehen was zu passieren hat, falls es zu Kollisionen kommt:

• Die Zufallszahl könnte einer der anderen Zufallszahlen für Ja-Stimmen anderer Kandidaten entsprechen. Und das wird sie tun, denn die Wahrscheinlichkeit, daß es nicht zu einer Kollision kommt, liegt bei 5.43 * 10^-320. Rechenweg (in Ruby):

  a=1< <40 ; p=1.0 ; 50000000.times {|i| p*=(a-i).to_f/a } ; puts p

  Ginge man von nur 10000 Wählern pro Maschine aus, läge die Wahrscheinlichkeit bei 0.9999545, also scheinbar wäre es sicher, daß es in einer Maschine keine solche Kollision gäbe. Man bräuchte nun aber 5000 Wahlmaschinen, um dieselbe Zahl von Wählern abzufertigen. Und die Wahrscheinlichkeit, daß es an keiner der Maschinen zu einer Kollision käme, läge bei p⁵⁰⁰⁰ also etwa 0.797 . Berücksichtigen wir jetzt, daß der Wähler bisher nur eine Stimme abgegeben hat, bei einer typischen Wahl aber zwischen sagen wir mal 3 und bis zu 80 Stimmen abgegeben werden müssen, können wir davon ausgehen, daß es zu mindestens einer Stimmkollision pro Wahl kommen wird.

  Was passiert dann?

  Haben die beiden Wähler mit der gleichen Zufallszahl unterschiedliche Parteien gewählt, dann tauchen zwangsläufig in der Liste der Quittungen zwei Zeilen mit derselben Zahl aber unterschiedlichen Kandidaten auf. Weil sich gewisse Manipulationen aber auf dieselbe Weise äußern würden, müßte man eine Manipulation vermuten und diesen Wahlbezirk annulieren.

  Haben die beiden Wähler die gleiche Partei gewählt, käme dieses Paar später in der Liste doppelt vor, und es würde wie eine Manipulation aussehen, obwohl keine Manipulation stattgefunden hat. Auch hier wäre die Wahl aufzuheben.

  Wäre die Wahlmaschine aber manipuliert, könnte sie in diesem Fall einer Kollision dem zweiten Wähler einfach die gleiche Quittung noch einmal ausdrucken wie sie der erste Wähler erhalten hat. Beide Wähler würde dies nicht bemerken. Dafür hat die Maschine nun eine überschüssige beliebige Wahl frei, was hinterher auch nicht bemerkt werden würde.

  Es tritt also der paradoxe Fall ein, daß eine Wahl ohne Manipulation als manipuliert angezeigt würde, während umgekehrt eine Manipulation nicht erkannt würde.

• Die Zufallszahl könnte mit einer der vorbereiteten Zahlen übereinstimmen. Bezieht sie sich auf unterschiedliche Kandidaten, dann ist unklar, was passiert, es würde wohl als Manipulation ausgelegt werden. Oder sie bezieht sich auf denselben Kandidaten, dann muß man sie sicher für eine Manipulation halten, weil man annehmen muß, die Maschine hätte eine Wahl aus bestehenden Daten gefälscht und eine willkürliche Wahl vorgenommen.

Das heißt, daß mit diesem Verfahren bei einer Zahlenlänge von 40 Bit eine beispielsweise deutschlandweit ablaufende Wahl nicht fehlerfrei durchzuführen wäre, weil sogar nicht manipulierte Wahlbezirke vom Protokoll aufgrund von Kollisionen als manipuliert angezeigt würden bzw. erst dann also korrekt angezeigt würden, nachdem die Kollision durch Manipulation ausgeglichen worden wäre. Jedenfalls degeneriert das Protokoll nach unten und nach oben, und die Degeneration tritt schon bei den für Deutschland anfallenden Größenordnungen auf.

Man müßte also ganz dringend statistische Überlegungen anstellen, für welche Wählerzahlen in welcher Wahlkreisgröße welche Zahlenlänge notwendig wäre. Das wäre aber Tünnef, weil man das niemandem vermitteln kann und das Protokoll ja für sich in Anspruch nimmt beweisbar korrekt zu sein. Was es nicht ist. Fragt sich, was es überhaupt ist. Die Bemerkung eines der Autoren (Link siehe oben)

Bei der Länge dachten wir an zwei Fünfergruppen mit Hexzahlen (40 Bit), dies sollte für einen Menschen noch halbwegs gut überprüfbar sein, aber bezogen auf die an einem Wahltag an einer Wahlmaschine anfallenden Stimmen ein ausreichendes Sicherheitsniveau bieten.

ist rührend naiv.

Wie kann man allen Ernstes behaupten, dieses Protokoll wäre verifizierbar, wenn es schon eine signifikante statistische Fehlerquote gibt, die man offenbar nicht bemerkt hat? Warum fehlen jegliche statistische Überlegungen und Angaben hierzu? Würde man ordentlich hinschreiben, unter welchen Randbedingungen das Verfahren halbwegs fehlerfrei, die Sicherheit noch gar nicht betrachtet, arbeitet, würde es schon keiner mehr einsetzen.

Eine der einfachsten Anforderungen an ein Kryptoprotokoll muß doch sein, daß es wenigstens in Abwesenheit eines Angreifers, ohne Angriff und ohne Störung von außen fehlerfrei arbeitet. Aber nicht einmal das ist hier gegeben.

Man sollte es nicht für möglich halten, aber fünf Leute wollen zwei Jahre lang an diesem Protokoll entwickelt haben, 10 Mannjahre wollen die da reininvestiert haben. Die Fehler springen mich an einem Sonntagnachmittag und zwei Wochentagsabenden geradezu an.