SipHash

SipHash [sip] ist eine kryptografische Pseudozufallsfunktion mit einem 128-Bit-Seed und einer 64-Bit-Ausgabe. Er wurde von Jean-Philippe Aumasson und Daniel J. Bernstein als schneller und sicherer schlüsselbasierter Hash-Algorithmus entwickelt. Er wird von Ruby, Perl, OpenDNS, Rust, Redis, FreeBSD und anderen verwendet. Die C-Referenzimplementierung wurde unter CC0-Lizenz (Public Domain) veröffentlicht.

Zitat von der SipHash-Website

SipHash ist eine Familie von pseudozufälligen Funktionen (auch bekannt als schlüsselbasierte Hash-Funktionen), die für Geschwindigkeit bei kurzen Nachrichten optimiert sind. Zielanwendungen sind die Authentifizierung von Netzwerkverkehr und die Abwehr von DoS-Angriffen durch Hash-Flooding.

siphash24 ist die empfohlene Variante mit bester Leistung. Sie verwendet 2 Durchgänge pro Nachrichtenblock und 4 Finalisierungsdurchgänge. Neben der Referenzimplementierung sind mehrere andere Implementierungen verfügbar. Einige sind Single-Shot-Funktionen, andere verwenden einen Ansatz ähnlich der Merkle–Damgård-Konstruktion mit init-, update- und finalize-Funktionen. Marek Majkowskis C-Implementierung csiphash [csiphash] definiert den Prototyp der Funktion. (Hinweis: k ist in zwei uint64_t aufgeteilt)

uint64_t siphash24(const void *src, unsigned long src_sz, const char k[16])

SipHash erfordert einen 64-Bit-Datentyp und ist nicht kompatibel mit reinen C89-Plattformen.

MurmurHash

MurmurHash [murmur] ist eine Familie von nicht-kryptografischen schlüsselbasierten Hash-Funktionen, die von Austin Appleby entwickelt wurden. Murmur3 ist die neueste und schnellste Variante von MurmurHash. Die C++-Referenzimplementierung wurde in die Public Domain gestellt. Sie bietet eine Ausgabe von 32 oder 128 Bit mit einem 32-Bit-Seed. (Hinweis: Der Out-Parameter ist ein Puffer mit entweder 1 oder 4 Bytes.)

Die Funktionsprototypen von Murmur3 sind

void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x86_128(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x64_128(const void *key, int len, uint32_t seed, void *out)

Die 128-Bit-Varianten erfordern einen 64-Bit-Datentyp und sind nicht mit reinen C89-Plattformen kompatibel. Die 32-Bit-Variante ist vollständig C89-kompatibel.

Aumasson, Bernstein und Boßlet haben gezeigt [sip] [ocert-2012-001], dass Murmur3 nicht resistent gegen Hash-Kollisions-Angriffe ist. Daher kann Murmur3 nicht mehr als sicherer Algorithmus betrachtet werden. Er kann immer noch eine Alternative sein, wenn Hash-Kollisions-Angriffe keine Rolle spielen.

CityHash

CityHash [city] ist eine Familie von nicht-kryptografischen Hash-Funktionen, die von Geoff Pike und Jyrki Alakuijala für Google entwickelt wurden. Die C++-Referenzimplementierung wurde unter der MIT-Lizenz veröffentlicht. Der Algorithmus basiert teilweise auf MurmurHash und gibt an, schneller zu sein. Er unterstützt 64- und 128-Bit-Ausgabe mit einem 128-Bit-Seed sowie 32-Bit-Ausgabe ohne Seed.

Der relevante Funktionsprototyp für 64-Bit CityHash mit 128-Bit-Seed ist

uint64 CityHash64WithSeeds(const char *buf, size_t len, uint64 seed0,
                           uint64 seed1)

CityHash bietet auch SSE 4.2-Optimierungen mit CRC32-Intrinsics für lange Eingaben. Alle Varianten außer CityHash32 erfordern 64-Bit-Datentypen. CityHash32 verwendet nur 32-Bit-Datentypen, unterstützt aber kein Seeding.

Wie MurmurHash haben Aumasson, Bernstein und Boßlet [sip] eine ähnliche Schwäche in CityHash gezeigt.

DJBX33A

DJBX33A ist ein sehr einfacher Multiplikations- und Additionsalgorithmus von Daniel J. Bernstein. Er ist schnell und hat geringe Einrichtungsaufwände, ist aber nicht sicher gegen Hash-Kollisions-Angriffe. Seine Eigenschaften machen ihn zu einer praktikablen Wahl für die Optimierung von kleinen String-Hashes.

Andere

Kryptografische Algorithmen wie HMAC, MD5, SHA-1 oder SHA-2 sind zu langsam und haben hohe Einrichtungs- und Finalisierungskosten. Aus diesen Gründen werden sie für diesen Zweck nicht als geeignet erachtet. Moderne AMD- und Intel-CPUs verfügen über AES-NI (AES-Befehlssatz) [aes-ni] zur Beschleunigung der AES-Verschlüsselung. CMAC mit AES-NI könnte eine praktikable Option sein, ist aber wahrscheinlich zu langsam für den täglichen Betrieb. (Test erforderlich)

Schlussfolgerung

SipHash bietet die beste Kombination aus Geschwindigkeit und Sicherheit. Entwickler anderer namhafter Projekte sind zu derselben Schlussfolgerung gekommen.

Hash-Geheimnis

Der Typ _Py_HashSecret_t von Python 2.6 bis 3.3 hat zwei Member mit jeweils 32 oder 64 Bit Länge. SipHash benötigt zwei vorzeichenlose 64-Bit-Integer als Schlüssel. Die Typedef wird in eine Union mit einer garantierten Größe von 24 Bytes auf allen Architekturen geändert. Die Union bietet einen 128-Bit-Zufallsschlüssel für SipHash24 und FNV sowie einen zusätzlichen Wert von 64 Bit für die optionale Optimierung kleiner Strings und den pyexpat-Seed. Der zusätzliche 64-Bit-Seed stellt sicher, dass pyexpat oder die Optimierung kleiner Strings keine Bits des SipHash24-Seeds preisgeben können.

Speicherlayout auf 64-Bit-Systemen

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
pppppppp ssssssss ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T
........ ........ ssssssss  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeeeeeee  pyexpat XML hash salt

Speicherlayout auf 32-Bit-Systemen

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
ppppssss ........ ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T (if available)
........ ........ ssss....  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeee....  pyexpat XML hash salt

Neue Typdefinition

typedef union {
    /* ensure 24 bytes */
    unsigned char uc[24];
    /* two Py_hash_t for FNV */
    struct {
        Py_hash_t prefix;
        Py_hash_t suffix;
    } fnv;
#ifdef PY_UINT64_T
    /* two uint64 for SipHash24 */
    struct {
        PY_UINT64_T k0;
        PY_UINT64_T k1;
    } siphash;
#endif
    /* a different (!) Py_hash_t for small string optimization */
    struct {
        unsigned char padding[16];
        Py_hash_t suffix;
    } djbx33a;
    struct {
        unsigned char padding[16];
        Py_hash_t hashsalt;
    } expat;
} _Py_HashSecret_t;
PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret;

_Py_HashSecret_t wird in Python/random.c:_PyRandom_Init() genau einmal beim Start initialisiert.

Hash-Funktionsdefinition

Implementierung

typedef struct {
    /* function pointer to hash function, e.g. fnv or siphash24 */
    Py_hash_t (*const hash)(const void *, Py_ssize_t);
    const char *name;       /* name of the hash algorithm and variant */
    const int hash_bits;    /* internal size of hash value */
    const int seed_bits;    /* size of seed input */
} PyHash_FuncDef;

PyAPI_FUNC(PyHash_FuncDef*) PyHash_GetFuncDef(void);

autoconf

Ein neuer Test wird zum Konfigurationsskript hinzugefügt. Der Test setzt HAVE_ALIGNED_REQUIRED, wenn er eine Plattform erkennt, die ausgerichteten Speicherzugriff für Integer erfordert. Die meisten aktuellen Plattformen wie X86, X86_64 und moderne ARM benötigen keine ausgerichteten Daten.

Eine neue Option --with-hash-algorithm ermöglicht dem Benutzer die Auswahl eines Hash-Algorithmus im Konfigurationsschritt.

Auswahl der Hash-Funktion

Der Wert des Makros Py_HASH_ALGORITHM bestimmt, welcher Hash-Algorithmus intern verwendet wird. Er kann auf einen der drei Werte Py_HASH_SIPHASH24, Py_HASH_FNV oder Py_HASH_EXTERNAL gesetzt werden. Wenn Py_HASH_ALGORITHM überhaupt nicht definiert ist, wird der bestverfügbare Algorithmus ausgewählt. Auf Plattformen, die keinen ausgerichteten Speicherzugriff erfordern (HAVE_ALIGNED_REQUIRED nicht definiert) und einen vorzeichenlosen 64-Bit-Integer-Typ PY_UINT64_T, wird SipHash24 verwendet. Auf strengen C89-Plattformen ohne 64-Bit-Datentyp oder auf Architekturen wie SPARC wird FNV als Fallback ausgewählt. Ein Hash-Algorithmus kann mit einer Autoconf-Option ausgewählt werden, z.B. ./configure --with-hash-algorithm=fnv.

Der Wert Py_HASH_EXTERNAL ermöglicht es Drittanbietern, ihre eigene Implementierung zur Kompilierzeit bereitzustellen.

Implementierung

#if Py_HASH_ALGORITHM == Py_HASH_EXTERNAL
extern PyHash_FuncDef PyHash_Func;
#elif Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {siphash24, "siphash24", 64, 128};
#elif Py_HASH_ALGORITHM == Py_HASH_FNV
static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * sizeof(Py_hash_t),
                                     16 * sizeof(Py_hash_t)};
#endif

sys-Modul

Das sys-Modul enthält bereits eine Struktur-Sequenz namens hash_info. Es werden weitere Felder zum Objekt hinzugefügt, um den aktiven Hash-Algorithmus und seine Eigenschaften widerzuspiegeln.

sys.hash_info(width=64,
              modulus=2305843009213693951,
              inf=314159,
              nan=0,
              imag=1000003,
              # new fields:
              algorithm='siphash24',
              hash_bits=64,
              seed_bits=128,
              cutoff=0)

_Py_HashBytes() (Objects/object.c)

_Py_HashBytes ist eine interne Hilfsfunktion, die den Hashing-Code für Bytes, Memoryviews und Datetime-Klassen bereitstellt. Sie implementiert derzeit FNV für unsigned char *.

Die Funktion wird nach Python/pyhash.c verschoben und so modifiziert, dass sie die Hash-Funktion über PyHash_Func.hash() verwendet. Die Funktionssignatur wird geändert, um als erstes Argument einen const void * zu akzeptieren. _Py_HashBytes kümmert sich auch um Sonderfälle: Sie ordnet Eingaben der Länge Null 0 zu und den Rückgabewert -1 auf -2.

bytes_hash() (Objects/bytesobject.c)

bytes_hash verwendet _Py_HashBytes, um die tp_hash-Slot-Funktion für Bytes-Objekte bereitzustellen. Die Funktion wird weiterhin _Py_HashBytes verwenden, jedoch ohne Typumwandlung.

memory_hash() (Objects/memoryobject.c)

memory_hash stellt die tp_hash-Slot-Funktion für schreibgeschützte Speicheransichten bereit, wenn auch das ursprüngliche Objekt hasbar ist. Sie ist die einzige Funktion, die in Zukunft das Hashing von nicht ausgerichteten Speichersegmenten unterstützen muss. Die Funktion wird weiterhin _Py_HashBytes verwenden, jedoch ohne Typumwandlung.

unicode_hash() (Objects/unicodeobject.c)

unicode_hash stellt die tp_hash-Slot-Funktion für Unicode bereit. Derzeit implementiert sie den FNV-Algorithmus dreimal für unsigned char*, Py_UCS2 und Py_UCS4. Eine Neuimplementierung der Funktion muss darauf achten, die korrekte Länge zu verwenden. Da das Makro PyUnicode_GET_LENGTH die Länge des Unicode-Strings und nicht seine Größe in Oktetten zurückgibt, muss die Länge mit der Größe der internen Unicode-Art multipliziert werden.

if (PyUnicode_READY(u) == -1)
    return -1;
x = _Py_HashBytes(PyUnicode_DATA(u),
                  PyUnicode_GET_LENGTH(u) * PyUnicode_KIND(u));

generic_hash() (Modules/_datetimemodule.c)

generic_hash fungiert als Wrapper um _Py_HashBytes für die tp_hash-Slots von Datums-, Zeit- und Datetime-Typen. Timedelta-Objekte werden anhand ihres Zustands (Tage, Sekunden, Mikrosekunden) gehasht und tzinfo-Objekte sind nicht hasbar. Die Datenmember der Structs der Date-, Time- und Datetime-Typen sind nicht void*-aligned. Dies kann leicht durch Kopieren von vier bis zehn Bytes in einen ausgerichteten Puffer mit memcpy() behoben werden.

Hash-Wert-Verteilung

Eine gute Verteilung der Hash-Werte ist für die Leistung von Dicts und Sets wichtig. Sowohl SipHash24 als auch FNV berücksichtigen die Länge der Eingabe, so dass Strings, die nur aus NULL-Bytes bestehen, nicht denselben Hash-Wert haben. Die letzten Bytes der Eingabe beeinflussen tendenziell auch die niederwertigsten Bits des Hash-Wertes. Dieses Attribut reduziert die Anzahl der Hash-Kollisionen für Strings mit einem gemeinsamen Präfix.

Typische Länge

Serhiy Storchaka hat in [issue16427] gezeigt, dass eine modifizierte FNV-Implementierung mit 64 Bits pro Zyklus lange Strings mehrmals schneller verarbeiten kann als die aktuelle FNV-Implementierung.

Laut Statistiken [issue19183] hat ein typisches Python-Programm sowie die Python-Testsuite ein Hash-Verhältnis von etwa 50% kleinen Strings zwischen 1 und 6 Bytes. Nur 5% der Strings sind größer als 16 Bytes.

Grand Unified Python Benchmark Suite

Erste Tests mit einer experimentellen Implementierung und der Grand Unified Python Benchmark Suite haben minimale Abweichungen gezeigt. Die zusammengefasste Gesamtlaufzeit des Benchmarks liegt innerhalb von 1% der Laufzeit eines unveränderten Python 3.4-Binärpakets. Die Tests wurden auf einem Intel i7-2860QM-System mit einer 64-Bit-Linux-Installation durchgeführt. Der Interpreter wurde mit GCC 4.7 für 64- und 32-Bit kompiliert.

Es werden weitere Benchmarks durchgeführt.

Pluggable (austauschbar)

Der erste Entwurf dieses PEP machte den Hash-Algorithmus zur Laufzeit austauschbar. Er unterstützte mehrere Hash-Algorithmen in einem Binärpaket, um dem Benutzer die Möglichkeit zu geben, zur Laufzeit einen Hash-Algorithmus auszuwählen. Dieser Ansatz wurde von mehreren Kern-Commiter als unnötige Komplikation angesehen [pluggable]. Nachfolgende Versionen des PEP zielen auf eine Konfiguration zur Kompilierzeit ab.

Nicht ausgerichteter Speicherzugriff

Die Implementierung von SipHash24 wurde kritisiert, da sie das Problem nicht ausgerichteten Speichers ignoriert und daher auf Architekturen, die eine Ausrichtung von Integer-Typen erfordern, nicht funktioniert. Der PEP vernachlässigt dieses Spezialfall bewusst und unterstützt SipHash24 nicht auf solchen Plattformen. Es wird einfach nicht als lohnenswert angesehen, bis das Gegenteil bewiesen ist. Alle wichtigen Plattformen wie X86, X86_64 und ARMv6+ können nicht ausgerichteten Speicher mit geringen oder sogar keinen Geschwindigkeitsbeeinträchtigungen handhaben. [alignmentmyth]

Fast jeder Block ist ohnehin ordnungsgemäß ausgerichtet. Derzeit sind Bytes- und Str-Daten immer ausgerichtet. Nur Memoryviews können unter seltenen Umständen auf nicht ausgerichtete Blöcke zeigen. Die PEP-Implementierung ist für den häufigsten Fall optimiert und vereinfacht.

ASCII str / bytes Hash-Kollision

Seit der Implementierung von PEP 393 haben Bytes und ASCII-Text das gleiche Speicherlayout. Aus diesem Grund behält die neue Hashing-API die Invariante bei

hash("ascii string") == hash(b"ascii string")

für ASCII-Strings und ASCII-Bytes. Gleiche Hash-Werte führen zu einer Hash-Kollision und verursachen daher eine geringe Geschwindigkeitsstrafe für Dics und Sets mit gemischten Schlüsseln. Die Ursache der Kollision könnte durch z.B. Subtraktion von 2 vom Hash-Wert von Bytes entfernt werden. -2, da hash(b"") == 0 und -1 reserviert ist. Der PEP ändert den Hash-Wert nicht.