Sind die ersten 32 Bits eines 160-Bit-SHA1-Hash ein akzeptabler Ersatz für einen CRC32-Hash?

Question

Ich arbeite an einem .NET 3.5-Projekt und ich brauche einen 32-Bit-Hash-Wert. Es scheint keine Methoden in den .NET Cryptography-Klassen zu geben, die einen 32-Bit-Hash zurückgeben (MD5 ist 128 Bit, SHA1 ist 160 Bit usw.). Ich habe eine CRC32-Klasse implementiert, aber ich finde, dass die SHA1- und MD5-Hashfunktionen, die bereits existieren, viel schneller sind.

Wäre es ein Problem (d. H. Erhöhte Wahrscheinlichkeit von Kollisionen) mit mir mit der SHA1-Hash-Funktion und nur die ersten 32 Bits abzubrechen, um als Hash-Wert zu speichern?

Answer 1

Wenn Sie nicht die zusätzlichen Funktionen des CRC32 (ein linearer Code) wollen, sollten Sie mit der Ausgabe auf 32 schneiden Bit.

Ob die Ausgabe einiger kryptographischer Hash-Funktionen die Sicherheit in Bezug auf Kollisionsresistenz verletzt, ist ein offenes Forschungsproblem ("unnatürlich" konstruierte Beispiele existieren, wenn ich mich richtig erinnere). Aber NIST (wahrscheinlich mit der Zustimmung der NSA) verwendete die Schneidtechnik, um den SHA-224 trotzdem von SHA-256 zu erhalten (siehe article about SHA in wikipedia).

EDIT: die CRC32 ermöglicht zu erkennen (und vielleicht korrigieren) Einzelbit Fehler, während eine kryptografische Hash-Funktion die Eigenschaft haben sollte, dass Sie nicht zwei Eingänge finden, die den gleichen Hash-Wert haben.

Kennen Sie das "Geburtstagsparadox" (siehe auch Wikipedia)? Bei einer 32-Bit-Prüfsumme erwarten Sie eine Kollision (d. H. Zwei Eingänge mit demselben Hash-Wert), wenn Sie etwa 2^16 Eingänge haben und Sie viel mehr Eingänge hashen möchten. (Erneutes Einlesen Ihres Kommentars könnte für Sie kein Problem sein.)

Answer 2

Wenn Sie nicht beabsichtigen, die 32-Bit für einen kryptografischen Zweck zu verwenden, sollten Sie in Ordnung sein. Ansonsten würde ich nicht darauf vertrauen, dass die ersten 32 Bits die gleiche Verteilung wie der gesamte Hash haben.

Warum können Sie nicht einfach den breiteren Hash verwenden, der verfügbar ist?

Answer 3

CRC32 ist wahrscheinlich angemessen für Ihre Bedürfnisse. Dies wurde in this question diskutiert.

In Bezug auf das Abschneiden eines Hash-Primitivs ist die einzige stark genutzte Anwendung davon die SSL/TLS Pseudo Random Function (PRF), die verwendet wird, um Schlüssel zu generieren. Es verwendet HMACs, Startwerte und Beschriftungen, um so viele Bytes zu generieren, wie Sie benötigen, indem Sie mehrere Male hashen und dann auf die benötigte Anzahl von Bytes abschneiden. obwohl

In Bezug auf Ihre Frage, können Sie die Ausgabe der Hash in Int32 der lesen und sie dann zusammen xor wenn du paranoid bist:

static void Main() 
{ 
    int xorCrc = GetHashedCrc(new SHA1Cng(), new byte[] {0xDE, 0xAD, 0xBE, 0xEF}); 
} 

private static int GetHashedCrc(HashAlgorithm algorithm, byte[] bytesToHash) 
{ 
    byte[] hash = algorithm.ComputeHash(bytesToHash); 
    int totalInt32s = hash.Length/sizeof(int); 
    int result = 0; 
    for(int i = 0; i < totalInt32s; i++) 
    { 
     int currentInt = BitConverter.ToInt32(hash, sizeof(int)*i); 
     result = result^currentInt; 
    } 

    return result; 
} 

Answer 4

die Annahme, dass eine Hash-Funktion gleichermaßen seine Eingänge verteilt über seinen Codecom scheint es logisch anzunehmen, dass es sich auch gleichmäßig auf jede Teilmenge davon verteilen wird. Die Verwendung einer "nativen" 32-Bit-Hash-Funktion wird jedoch wahrscheinlich immer noch die bessere Wahl sein. Vielleicht kann jemand mehr in die Sache uns einen besseren Grund als nur mein Bauchgefühl bieten :)

Answer 5

Warum verwenden Sie nicht einfach string.GetHashCode(). Es wurde entwickelt, um einen 32-Bit-Hash-Wert zu berechnen und bei realen Daten wenige Kollisionen zu erzeugen. Natürlich ist es nicht sicher, aber Ihre Frage enthält das nicht als Voraussetzung.