Eine bestandene Hash-Testsuite sagt nichts über gewählte Eingaben
Serguey Asael Shinder2 Min. LesezeitThomas Dybdahl Ahle hat eine systematische Untersuchung veröffentlicht, wie sich die verbreiteten schnellen Hashfunktionen gegenüber gewählten statt zufälligen Eingaben verhalten — aktualisiert am 19. September und mit Prüfcode, Daten und Archiv versehen: https://thomasahle.com/blog/adversarial-examples-for-hashes/.
Der Satz ganz oben ist das ganze Argument: Eine bestandene statistische Testsuite sagt nichts darüber, wie oft die gewählten Eingaben eines Angreifers kollidieren — auch dann nicht, wenn er den Seed nie erfährt.
Der Zusammenhang ist Geschwindigkeit. Massen-Hashing läuft an der Grenze der Speicherbandbreite — der Beitrag nennt xxHash mit 60 GB/s — und eine lange Liste gebräuchlicher Funktionen tauscht dafür Qualität gegen Angreifer ein: komihash, a5hash, HighwayHash, SpookyHash, aHash und t1ha2 unter anderen. Jahrelang war dieser Tausch vernünftig, weil niemand Kryptoanalyse betreibt, um eine Hashtabelle zu bremsen.
Der Gegenmaßstab ist ein Beweis. Eine Funktion heißt b-bit-universell, wenn zwei Eingaben der Länge L mit höchstens L·2^−b Wahrscheinlichkeit kollidieren. Auf dieser Grundlage arbeitet die Studie das Feld durch — CityHash64, FarmHash64, MurmurHash3, gxhash, MuseAir, MUM, pengyhash, nmhash, mx3, fasthash, SipHash-1-3 und 2-4, Poly1305 und GHASH, Go maphash, Abseil Hash, .NET Marvin, foldhash — trennt bewiesene Garantien von ungeklärten Behauptungen und ergänzt bewiesene Schranken für UMASH-64/128 sowie einen korrigierten Beweis für HalftimeHash.
Was das bedeutet
Eine Testsuite misst den Durchschnittsfall; der Angreifer wählt die Eingabe. Batterien vom Typ SMHasher beantworten die Frage „sieht das über diese Testvektoren zufällig aus" — eine Aussage über eine Verteilung, die niemand zu brechen versucht. Die Frage, die über das Verhalten einer Hashtabelle unter Last entscheidet, ist eine andere: Was kann ein Gegner anrichten, der den Algorithmus kennt, den Schlüssel aber nicht? Beide Fragen haben verschiedene Antworten, und in den meisten Projekten ist nur eine davon gemessen worden.
Das Fehlerbild ist Verfügbarkeit, nicht Vertraulichkeit. Niemand liest Ihre Daten, weil eine nichtkryptografische Hashfunktion kollidiert. Ihre Map wird quadratisch, eine Anfrage von 3 Millisekunden dauert 3 Sekunden, und der Dienst kippt — genau deshalb sind Laufzeitumgebungen für ihre Standard-Maps auf Funktionen der SipHash-Klasse umgestiegen. Und deshalb verdient „wir hashen nur interne Bezeichner" einen zweiten Blick, sobald einer dieser Bezeichner über das Netz hereinkommt.
Und „wir haben eine schnelle Hashfunktion genommen" ist eine Entscheidung mit Bedrohungsmodell — ob es aufgeschrieben wurde oder nicht. Für eine Prüfsumme über eigene Dateien sind 60 GB/s die richtige Antwort. Für eine Tabelle über Nutzereingaben ist es eine Funktion mit Beweis und einem Seed, den der Aufrufer nicht sehen kann. Der praktische Wert solcher Arbeit ist, dass sich die Grenze zwischen beiden Fällen jetzt zitieren statt diskutieren lässt.