# hashline32 ## Wie hoch ist denn die Kollisionswahrscheinlichkeit dieses Hash-Verfahrens? Die Kollisionswahrscheinlichkeit für dieses Hashverfahren hängt primär von der Bitbreite des Rückgabewerts und der Anzahl der gehashten Zeilen ab. Obwohl djb2 initial als 32bit non-cryptographic hash konzipiert ist, implementiert die hiesige Funktion djb2_64 tatsächlich eine 64-Bit-Variante des djb2-Algorithmus, da sie einen unsigned long long (64-Bit) zurückgibt und die Bitverschiebung im 64-Bit-Raum stattfindet. Die Ausgabe ist daher auch ein 64bit Wert in hexadezimaler Schreibweise. Und ja, die Berechung und Ausgabe als 64bit Wert funktioniert auch auf einem 32bit System und wenn der code dort kompiliert wird. Daher heißt dieses Tool hashline32, da es problemlos auch abwärtskompatibel auf legacy systemen genutzt werden kann. ## Kollisionswahrscheinlichkeiten | Anzahl der Zeilen | Kollisionswahrscheinlichkeit | Risiko | ----------------- | ---------------------------- | -------------------------- | 1 Million | 1:37.000.000 | Extrem Gering | 10 Millionen | 1:370.000 | Sehr gering | 100 Millionen | 0.027% | Spürbar und für kritische Systeme zu hoch | 5 Milliarden | 50% | Kollisionsgrenze (50% Chance) | 50 Milliarden | 99,99% | Fast garantierte Kollision ## Wichtige Besonderheiten des Codes 1. Effektive Bitbreite (64-Bit statt 32-Bit): Der Code nutzt uint64 für hash. Der klassische djb2-Multiplikator (33) wird durch (hash << 5) + hash realisiert. Da kein Abschneiden auf 32-Bit stattfindet, nutzt du den vollen 64-Bit-Suchraum. Das erhöht die Sicherheit gegen zufällige Kollisionen massiv im Vergleich zu echtem 32-Bit (wo bereits ab ca. 77.000 Zeilen eine 50%-Chance auf Kollision besteht). 2. Nicht-kryptografischer Hash: djb2 ist extrem schnell, aber nicht resistent gegen böswillige Angriffe (Pre-image / Collision Attacks). Wenn Angreifer die Eingabedaten kontrollieren, können sie gezielt und in Millisekunden unterschiedliche Zeilen erzeugen, die exakt denselben Hashwert liefern (Hash-Flooding). 3. Eingabeabhängigkeit: Da djb2 stark von den Byte-Werten abhängt, neigt er bei sehr ähnlichen, sequentiellen Strings (z. B. feine Nuancen in URLs oder Log-Zeitstempeln) manchmal zu Mustern, was die reale Kollisionsrate gegenüber der mathematischen Idealtheorie leicht verschlechtern kann. Das heißt im Klartext: ## djb2 ist und bleibt ein nicht-kryptografischer Hash!! Das ist sehr wichtig zu verstehen: echo -n USER_000002 | hashline c029b2d299939045 USER_000002 echo -n USER_000001 | hashline c029b2d299939044 USER_000001 echo -n USER_000000 | hashline c029b2d299939043 USER_000000 ähnliche Zeilen führen auch zu ähnlichen Hashes. Wir haben in dieser Form der Implementierung ohne XOR keinen Lawineneffekt! ## Verhalten des Tools Wenn eine einzelne Zeile größer als BUFSIZE (64 KB) ist, stürzt das Programm nicht ab und es kommt auch zu keinem Pufferüberlauf. Es gibt hingegen exakt die maximalen 64k (65535 bytes) aus und beendet sich dann sauber mit exitcode 0. Warum? Alles Andere wäre undefiniertes Verhalten. Im djb stil muss sinngemäß ein Programm terminieren, wenn ansonsten undefiniertes Verhalten eintreten würde. Das ist genau das, was hashline tut. Es splittet bei Überschreitung von 64k pro Zeile also nicht einfach ungefragt die Daten in zwei Teile auf, setzt keine Marker und manipuliert die Zeilen nicht stillschweigend. Es wartet auch nicht endlos auf newline um einen hash bilden zu können. Es alloziert auch nicht beliebigen weiteren Speicher, um irgendwann ggf. durch einen externen OOM Killer abgeschossen zu werden, wenn es nie ein newline findet. Es nutzt das bekannte, hart definierte, eincompilierte und detektierbare Limit von BUFSIZE und beendet sich, falls das Limit überschritten wurde. Aus datenlogischer Sicht ist das sofortige Beenden des Programms der einzig richtige und sichere Weg (Fail-Fast). Das Verhalten ist eine konsequente und logische Design-Entscheidung. Da wir festlegen, dass Zeilen über 64 KB (65535 bytes) und ebenso gleichermaßen ein EOF das Ende des Datenstroms markieren, ist das Verhalten per Definition kein Softwarefehler, sondern eine reguläre Terminierung des Streams. Alle Mögliche Alternativen hätten ansonsten dieses Praxisproblem: Zeilen verwerfen und weitersuchen: Wenn ein Angreifer oder ein fehlerhaftes System Terabytes an Daten ohne ein einziges \n schickt, würde das Programm endlos im Kreis lesen, Hashes für Müll berechnen und CPU-Zyklen verschwenden, ohne jemals sinnvolle Daten zu liefern. ## Warum beendet es auch in diesem Fall mit fehlercode 0 (erfolg) statt mit fehlercode 1 oder höher? Da das Limit von 64 KB pro Einzelzeile eine bekannte, feste Eigenschaft des Programms ist, ist das Verhalten für den Anwender deterministisch und somit vollkommen korrekt dokumentiert. Ein weiterer separater Exitcode ist zudem nicht gesetzt, weil es auch kein Fehlerzustand ist. Der Zustand des Abbruchs ist also nachträglich und auch ohne Evaluierung des exitcodes am Content selbst erkennbar, nämlich dass die Zeilenlänge nach dem hash der letzten hashline dem definierten Limit entspricht. Das ist wichtig, wenn diese Daten in logfiles laufen, da dort ja selbst keine exitcodes protokollieren. Das Verhalten wird hier also nicht über exitcodes protokolliert und signalisiert, sondern ist an der Länge des Content ersichtlich. Das Programm verhält sich durch das wohldefinierte BUFSIZE Limit daher wie ein sicherer Filter, der bei einer Überschreitung der Spezifikation die Verarbeitung sauber einfriert, den bisherigen Puffer leert und sich kontrolliert beendet. Zusammen mit -fstack-protector-strong und -static-pie ist das ein robustes Tool für den Zweck, für den es gebaut wurde. ## Wie verhindere ich, dass ein Angreifer das 64k limit nutzt, um meine pipeline zu crashen? Schalte ein | cut -c-65532 | in einer pipe voran und schneide damit vorher überlange zeilen ab. dann wird hashline auch nicht terminieren, weil du das limit nie erreichst. zudem limitieret du dsmit die Ressourcen für deinen Angreifer. Das ist nicht eingebaut in hashline, weil es keine Aufgabe von hashline ist und der unix mentalität widerspricht. Du sollst selbst entscheiden können, wie du in deiner pipe verfährst. ## Ich habe Zeilen, die exakt 64k groß sind? Ja. Und newline ist +1 Byte. Wie ist die Frage? ## Ich habe aber Zeilen die größer 64k sind und will weiterprozessieren - Was nun? Dann musst du z.B. ein fold -w 65532 in der pipeline voranschalten, um Zeilenumbrüche zuvor aktiv zu erzwingen, sodass das hashline bewusst nicht terminiert und für die hash kalkulation unter dem Limit bleibt. Diese Datenmodifikation gibst du als Nutzer damit dann auch bewusst in Auftrag und du musst das im weiteren Verlauf berücksichtigen. Auch kannst du das Ende der Zeile mit einem Flag deiner Wahl markieren, um die Lines zu reversen. Das ist nicht Aufgabe von hashline. Und der hash wird stets nur über bytefolgen unterhalb des limits berechnet sein. So sieht modulare und Unix-konforme Softwareentwicklung aus. Nach der Unix-Philosophie ("Do one thing and do it well") muss hashline nicht die Probleme unvollständiger oder überlanger Zeilen lösen. Das Tool geht wie erwähnt fest davon aus, dass eine valide Zeile in den 64-KB-Puffer passt. Wenn die Datenbasis außerhalb dieser Norm liegt, ist es die Aufgabe der Pipeline, die Daten vorzubereiten. Ein vorgeschaltetes ... | awk '{while(length($0)>65535){printf "%s\036\n",substr($0,1,65532);$0=substr($0,65533)}print}' | ... bricht die Zeilen inkl. einem Marker sauber um, bevor sie hashline erreichen. Wenn du das also brauchst, kannst du das in der Kette nutzen, bekommst einen hash über den Tielstring inkl. marker und musst alles später wieder reversen. ## Warum machst du das so? Dadurch folgt der Code der Unix Philosophie und bleibt für alle anderen Nutzer weiterhin performant, weil er keine komplexe, dynamische Speicherverwaltung (wie realloc) benötigt. Sicher, da der Puffer statisch bleibt und das Risiko von Heap-Exploits komplett entfällt. Kompakt, was perfekt zu einer statischen Verlinkung mit musl-gcc passt. Die Härtung mit Stack-Protector und PIE fängt dann genau die verbleibenden Risiken ab, falls in der Pipeline doch mal etwas Unvorhergesehenes passiert. Das Gesamtsystem ist damit sowohl architektonisch als auch plattformseitig größtmöglich abgesichert. ## Mir würden schon 128k Limit reichen... kannst du nicht...? Nein. Die 64k sind ein bewusst gewähltes Limit mit Berücksichtigung der Performance und Memory Footprint. Aber du hast den Quellcode und er ist public domain. Dann modifiziere die BUFSIZE Definition und baue deine special binary.