Bash Einweg-Hashfunktion programmieren, die feste Ausgabelänge hat und pseudozufällig ist

[xpad.c]

# Prime: 33

PS: Wie sicher bist Du Dir diesbezüglich?
PPS: Oops, sollte eigentlich ein Nachtrag für den anderen Beitrag sein.

 

[CyborgBeta]

Als Stichprobe:
aaaa -> 8156 aaab->63

Den Rest überlasse ich Dir

Jap, das geht auch (relativ einfach) in Bash.

#!/bin/bash
hash_string () {
  hash_val=0x11C       # Offset basis: 284
  prime=0x21           # Prime: 33
  mask=0x1FFF          # 13-bit mask (8191)
  s=$1
  while (( ${#s} < 4 ));
  do
    s="${s}a"
  done
  for (( i=0; i<${#s}; i++ ));
  do
    j=$(printf '%d' "'${s:$i:1}")  # ordinal
    hash_val=$((hash_val ^ j))
    hash_val=$(((hash_val * prime) & mask))
  done
  printf "%04d\n" "$hash_val"
}

 

[TomH22]

@CyborgBeta : Mit 3655 Beiträgen solltest Du wissen wie das Forum funktioniert.
Die Reaktionen kommen nicht daher, dass Dich jemand beleidigen will, sondern weil Du mit einem "naiven" Ansatz in ein sehr komplexes Teilgebiet der Informatik (Kryptographie) eindringst.

Ich habe mehrere Jahre eine Entwicklungsabteilung geleitet, und wenn irgendein Entwickler auf die Idee kam, im Bereich Verschlüsselung, Hashes, Passwörter, usw. irgendeinen "naiven" Eigenbau zu starten, war das auch ein Punkt wo bei mir der Spaß aufhört.

Es gibt Dinge, die "tut man nicht", die muss man sozusagen als "Kunstfehler" betrachten. Dazu gehört z.B. auch Race Conditions bei parallelen Zugriffen zu ignorieren, weil "die Wahrscheinlichkeit gering ist".

Ich bin trotzdem immer dafür eine konstruktive Auseinandersetzung zu suchen.

PS: Wie sicher bist Du Dir diesbezüglich?

Überhaupt nicht. Deswegen habe ich ja auch einen Disclaimer benutzt:

Und gerade weil es so ist, wäre mein Ansatz, etwas etabliertes zu verwenden. Ich habe jetzt erst mal nicht geprüft ob FNV-1a wirklich was taugt, aber das wäre dann der nächste Schritt.

ChatGPT hat ein wenig erklärt warum es diesen Wert benutzt habe, und die Ausgabelänge von 13 Bit ist eben auch kurz. Es gibt getestete Implementierungen mit z.B. 32 oder 64 Bit.

Ich persönlich würde so einen Ansatz höchstens wählen, wenn es nicht sicherheitsrelevant wäre. Als Hashfunktion für Hashtable Implementierungen würde ich kein Problem sehen, dann da hätte man halt höchstens schlechte Performance wenn die Diffusion wirklich zu schlecht ist.

Sha256 gekürzt, wie hier schon mehrmals vorgeschlagen, wäre für die meisten Fälle der sichere und bessere Weg. Allerdings ist das relativ rechenintensiv, bei einem Bash Script irrelevant, für Hashwerte auf einem Mikrocontroller der mit 50Mhz läuft (da bin ich teilweise unterwegs) wäre sowas wie FNV-1a dann wieder eine Überlegung wert.

Ergänzung (13. April 2025)

Hier mal ein Beispiel wie "problematische" Hash Funktionen selbst in etablierter Software (in diesem Fall Lua, dass massgeblich von einem Informatik Professor entwickelt wurde):
https://kate.io/blog/simple-hash-collisions-in-lua/

Im Artikel wird "Hash DoSing" erwähnt, dass sind Denial-of-Sevice Angriffe auf bekannte Schwächen in Hash Funktionen die z.B. für String Interning und Hash-Tables in Laufzeitumgebungen verwendet werden.
Ein Angreifer flutet den Server mit Anfragen die zu einer großen Anzahl an Hash Kollisionen führen.

 

[Marco01_809]

Jage das durch eine fertige Hash-Funktion deiner Wahl und das Ergebnis davon modulo 10000 nehmen.

Das wäre schon sehr kurios, wenn Teilsequenzen des Ergebnisses einen Bias hätten.

Modulo 10000 führt einen Bias ein. Man darf nur auf ganze Bits kürzen, d.h. Modulo einer Zweierpotenz.

Einfaches Beispiel. Angenommen wir haben einen gleichverteilten Hash der 4 Bit rauswirft, also h \in [0,15].
Wenn wir h jetzt auf eine Dezimalstelle kürzen wollen mit f(h) := h mod 10, dann hätten wir folgende Verteilung:

f(h)	Urbild (d.h. mögl. Werte für h)	Häufigkeit
0	0, 10	12,5%
1	1, 11	12,5%
2	2, 12	12,5%
3	3, 13	12,5%
4	4, 14	12,5%
5	5, 15	12,5%
6	6	6,25%
7	7	6,25%
8	8	6,25%
9	9	6,25%

Dass das bei Zweierpotenzen nicht passiert ist leicht ersichtlich, da man mit jedem Bit das man wegnimmt die zweite Hälfte der Outputs auf die erste Hälfte umverteilt und beide Mengen gleich groß sind. Wie ein Blatt Papier das man genau in der Mitte faltet.

Darum sind Hexadezimalzahlen der übliche Weg Hashes darzustellen statt Dezimalzahlen, denn da repräsentiert jedes Zeichen eine ganzzahlige Anzahl Bits.

 

[simpsonsfan]

@Marco01_809 Da hast den Thread scheinbar nicht komplett gelesen.
Dass ein Modulo 10000 einen Bias einführt, steht hier schon im Thread. Hatte gerade BeBur als erstes erwähnt.
Und du zitierst BeBur, der von Teilsequenzen vom sha Hash spricht, also eben einfach einen Teilstring aus dem Hexadezimalen Hashstring rauszuziehen. Mit der Modulo-Idee hat das nichts zu tun.

 

[CyborgBeta]

Dass ein Modulo 10000 einen Bias einführt, steht hier schon im Thread.

Und genau diese Aussage ist falsch. Meine Implementierung hat keinen Bias / ist gleichverteilt.

Aber behauptet gerne weiter falsche Dinge über mich. 🤷‍♂️

 

[Marco01_809]

@simpsonsfan
Stimmt, ging unter beim Überfliegen weil der Thread sich irgendwie im Kreis drehte.

SHA256 ist erstmal eine 256 Bit lange Zahl. Die kann man hexadezimal darstellen (sollte man meistens auch) aber zwischen den Anforderungen vom OP schien mir die Ausgabe mit 4 Dezimalstellen noch die festeste zu sein. Und dann ist SHA256 kürzen nicht mehr trivial. (Wobei das vermutlich noch besser ist als andere Lösungen )

 

[xpad.c]

Stimmt, ging unter beim Überfliegen weil der Thread sich irgendwie im Kreis drehte.

Das tut er in der Tat schon eine ganze Weile. Wobei ich ja, aus offensichtlichen Gründen, nur noch einen Teil davon mitbekomme.

SHA256 ist erstmal eine 256 Bit lange Zahl. Die kann man hexadezimal darstellen (sollte man meistens auch) aber zwischen den Anforderungen vom OP schien mir die Ausgabe mit 4 Dezimalstellen noch die festeste zu sein.

Wie schon vorher angemerkt, ist das auch die, die am wenigsten Sinn ergibt, dabei aber gleichzeitig das Hauptproblem darstellt.

xpad.c

 

[Piktogramm]

Ah danke für die Unterhaltung, der Thread ist spitze.

Ein TE der das kleine 1x1 der Formulierungen von Anforderungen nicht hinbekommt[1] und zuletzt die mathematisch richtige Aussage zu Bias bei Modulo auf sich bezieht und daher ablehnt.
Und vor allem vermute ich, dass es eine Hausaufgabe/ein Beleg ist die der TE gern gelöst haben will. Jeder der etwas Produktives bauen wollte würde AES, SHA draufwerfen, schon allein weil moderne Bibliotheken + Prozessoren das zum quasi Nulltarif können.

Und an Stelle des TE wäre es deutlich sinnvoller statt zuerst Code zu schreiben mal zu formulieren, welche Probleme sich ergeben, wenn man einen Raum aus 26^4 Elementen auf eine Menge von 10.000 gleichmäßig abbilden will. Gefolgt von der Überlegung, wie diese Abbildung halbwegs zufällig erfolgt auf diese deutlich kleinere Menge erfolgen kann. Lustigerweise kommt da die korrekte Aussage zum Verhalten von Modulo wieder ins Spiel.

[1] Das ist der Punkt wo sich über "glauben" etc. lustig gemacht wurde. Dem TE wäre anzuraten rfc2119 zu lesen und aufs Deutsche zu übertragen.

 

[CyborgBeta]

kann weg

 

[CyborgBeta]

Jeder der etwas Produktives bauen wollte würde AES, SHA draufwerfen,

Wie oft denn noch, dass das nicht ausreicht?

 

[foofoobar]

Und an Stelle des TE wäre es deutlich sinnvoller statt zuerst Code zu schreiben mal zu formulieren, welche Probleme sich ergeben, wenn man einen Raum aus 26^4 Elementen auf eine Menge von 10.000 gleichmäßig abbilden will. Gefolgt von der Überlegung, wie diese Abbildung halbwegs zufällig erfolgt auf diese deutlich kleinere Menge erfolgen kann. Lustigerweise kommt da die korrekte Aussage zum Verhalten von Modulo wieder ins Spiel.

Wobei bei 2**256 (115792089237316195423570985008687907853269984665640564039457584007913129639936)
der "Bias" recht gering ist.
Und selbst bei 2**64 (18446744073709551616) um das ohne größeren Aufriss verarbeiten zu können hält sich der "Bias" immer noch in Grenzen.

Vulgo: Die höhere Wahrscheinlichkeit des Auftretens bestimmter Ergebnisse bei modulo 10000 ist recht gering.

[1] Das ist der Punkt wo sich über "glauben" etc. lustig gemacht wurde. Dem TE wäre anzuraten rfc2119 zu lesen und aufs Deutsche zu übertragen.

Tja, wenn man nur wüsste was der TO wirklich vorhat (ein Perpetuum mobile?) könnte man sicherlich helfen, aber das ist wahrscheinlich top secret.

 

[JoergB]

Die Mathematik hinter diesen ganzen Geschichten ist extrem komplex, im Detail bin ich da raus, ich vermute die meisten hier auch.
Wenn erforderlich habe ich auf fertige auf Konformität geprüfte Algorithmen gesetzt.
Was mir gut geholfen hat sind CRCs (sind ja auch hashes), die sind noch überschaubar und es gibt genügend Literatur dazu.
Da hat sich einer viel Gedanken gemacht und eine gute Übersicht der CRCs gemacht, da konnte ich viel an Informationen heraus ziehen:
https://users.ece.cmu.edu/~koopman/crc/index.html
Es gibt Polynome optimiert für kurze Daten und für lange Daten.
Ich habe so etwas mal benötigt für SIL Zulassungen im Bereich Datenübertragung, das war ein Kampf, aber die Zulassung durch eine Prüfstelle hat funktioniert.

 

[BeBur]

die Ausgabe mit 4 Dezimalstellen noch die festeste zu sein. Und dann ist SHA256 kürzen nicht mehr trivial.

Stimmt, guter Punkt. Wobei der Bias ziemlich klein ist bei einer 256 Bit Zahl Modulo 10.000. Ich vage zu behaupten, dass man den in vielen Anwendungsfällen akzeptieren kann.

Ah, ich sehe gerade, @foofoobar hat das auch schon geschrieben .

CRCs

Die sind nicht kollisionsresistent und es wurde explizit kollisionsresistenz als anforderung genannt.. nicht dass das jetzt viel aussagt, ich würde raten dass die eigentlich nicht benötigt wird und etwas anderes gemeint gewesen.

4 Buchstaben auf eine 4 stellige Zahl mappen hat denke ich nur theoretisch was mit hashen zu tun. Die Problemstellung an sich ist schon eher bizarr und folgt vermutlich keinem sinnvollen Anwendungsfall, von daher sind die Anforderungen auch halbwegs beliebig.

 

[CyborgBeta]

Wenn es in meiner Implementierung von vor ein paar Seiten ... einen Bias (also eine Häufung) gäbe, dann müsste es einen Bildwert geben, der 44- oder 47-mal vorkommt, und das ist nicht der Fall.

Btw. Sind CRCs nicht auch Hashverfahren?

 

[KitKat::new()]

Was spricht eigentlich dagegen [0, 2^256-1] auf [0,9999] herunterzuskalieren (noch nicht vorgeschlagen oder ich habs übersehen)?
Jede Zahl von 0-9999 bekommt x = (2^256)/10 000 Zahlen von [0, 2^256-1] zugewiesen:

use primitive_types::{U256, U512};
use sha2::{Sha256, Digest};

fn hash(input: &str, scale_limit: u16) -> u16 {
    let mut hasher = Sha256::new();
    hasher.update(input);
    let sha256_hash = hasher.finalize();
    let sha256_hash = U256::from_little_endian(sha256_hash.as_slice());
    let scaled_hash = sha256_hash.full_mul(U256::from(scale_limit)) / U256::max_value();
    scaled_hash.try_into().expect("result is smaller than 2^16")
}

fn hash_improved(input: &str, scale_limit_exclusive: u16) -> u16 {
    let mut hasher = Sha256::new();
    hasher.update(input);
    let sha256_hash = hasher.finalize();
    let sha256_hash = U256::from_little_endian(sha256_hash.as_slice());
    let scaled_hash = sha256_hash.full_mul(U256::from(scale_limit_exclusive)) 
        / (U512::from(U256::max_value()) + 1);
    scaled_hash.try_into().expect("result is smaller than 2^16")
}
fn main() {
    let chars = b'A' ..= b'Z';
    let (mut hashes, mut i_hashes) = (Vec::new(), Vec::new());
    for a in chars.clone(){
        for b in chars.clone(){
            for c in chars.clone(){
                for d in chars.clone(){
                    let string = [a, b, c, d];
                    let str = str::from_utf8(&string).expect("valid utf8");
                    let hash = hash(str, 10_000);
                    let hash_improved = hash_improved(str, 10_000);
                    println!("{str} -> {hash:04}");
                    println!("{str} -> {hash_improved:04}");
                    hashes.push(hash);
                    i_hashes.push(hash_improved);
                }
            }
        }
    }
    let (min, max) = (hashes.iter().min().unwrap(), hashes.iter().max().unwrap());
    let (min_i, max_i) = (i_hashes.iter().min().unwrap(), i_hashes.iter().max().unwrap());
    let equal = hashes == i_hashes;
    println!("equal: {equal}");
    println!("min: {min}, max: {max}");
    println!("min_i: {min_i}, max_i: {max_i}");
}

Theoretisch kann bei der einfachen Variante (2^256-1)*10000/(2^256-1)=10 000 herauskommen, daher habe ich eine zweite Variante hinzugefügt, die stattdessen (2^256-1)*10000/2^256<10 000 rechnet und dadurch ein Abrunden erzwingt.

In diesem Beispiel ändert sich nichts, da (2^256+1) als Hash durch SHA256 sehr unwahrscheinlich ist, sh. Output:

...
ZZZY -> 6302
ZZZY -> 6302
ZZZZ -> 5374
ZZZZ -> 5374
equal: true
min: 0, max: 9999
min_i: 0, max_i: 9999

 

[foofoobar]

Was spricht eigentlich dagegen [0, 2^256-1] auf [0,9999] herunterzuskalieren (noch nicht vorgeschlagen oder ich habs übersehen)?
Jede Zahl von 0-9999 bekommt x = (2^256)/10 000 Zahlen von [0, 2^256-1] zugewiesen:

Braucht halt eine Sprache die mit solchen Werten (u256) rechnen kann oder entsprechende Libs.

use primitive_types::{U256, U512};

Anscheinend kann das Rust :-)
Ich nerv dich morgen mit ein paar Fragen zu dem Code.

 

[BeBur]

Was spricht eigentlich dagegen [0, 2^256-1] auf [0,9999] herunterzuskalieren (noch nicht vorgeschlagen oder ich habs übersehen)?

Ich glaube ein Punkt war, dass TE denkt, dass man von 4 Buchstaben keinen sha256 hash bilden kann. Edit: ich glaube, das habe ich halluziniert.
Außerdem sind es dann angeblich zwei Verfahren?!?

Jage das durch eine fertige Hash-Funktion deiner Wahl und das Ergebnis davon modulo 10000 nehmen.

Nein, dann sind es zwei Verfahren, anstatt eins.

 

[CyborgBeta]

Ich glaube, ich spinne langsam ... Das hat nur indirekt mit der Frage zu tun, aber warum funktioniert der folgende Aufruf nicht?

$ echo "Hello, World!" | crcany -16
CRC-16/ARC: 0x32ba
CRC-16/CDMA2000: 0x5086
CRC-16/CMS: 0x85ce
CRC-16/DDS-110: 0x2d41
CRC-16/DECT-R: 0x19a6
CRC-16/DECT-X: 0x19a7
CRC-16/DNP: 0x391e
CRC-16/EN-13757: 0x060a
CRC-16/GENIBUS: 0x98f4
CRC-16/GSM: 0x319e
CRC-16/IBM-3740: 0x670b
CRC-16/IBM-SDLC: 0xde99
CRC-16/ISO-IEC-14443-3-A: 0xca1b
CRC-16/KERMIT: 0x77f3
CRC-16/LJ1200: 0xbab0
CRC-16/MAXIM-DOW: 0xcd45
CRC-16/MCRF4XX: 0x2166
CRC-16/MODBUS: 0x3311
CRC-16/NRSC-5: 0x2fac
CRC-16/OPENSAFETY-A: 0xa095
CRC-16/OPENSAFETY-B: 0x9fd5
CRC-16/PROFIBUS: 0xdf52
CRC-16/RIELLO: 0x7c34
CRC-16/SPI-FUJITSU: 0xa46b
CRC-16/T10-DIF: 0x7fbb
CRC-16/TELEDISK: 0x51ba
CRC-16/TMS37157: 0xae23
CRC-16/UMTS: 0x504e
CRC-16/USB: 0xccee
CRC-16/XMODEM: 0xce61

Da sollte eigentlich der crc16 0xFA4D wie hier https://crccalc.com/?crc=test&method=CRC-16&datatype=ascii&outtype=hex oder hier https://manpages.debian.org/stretch/tcllib/crc16.3tcl.en.html herauskommen, aber stattdessen immer 0x32ba ...

Das Tool ist hier beschrieben: https://github.com/madler/crcany/blob/master/crcany.c

---

Was spricht eigentlich dagegen [0, 2^256-1] auf [0,9999] herunterzuskalieren

Gibt es einen Bias?

 

[simpsonsfan]

@KitKat::new() Das führt den selben Bias ein wie die Modulovariante (weil 2^256 nämlich nicht durch 10 000 teilbar ist [2^256 mod 10 000 = 9 936])
Und damit:

Das Ergebnis ist dann nicht mehr gleichverteilt, d.h. manche Inputs haben höhrere Chancen für Kollisionen als andere. Ob das ein Problem ist? Keine Ahnung

Freilich hat ein Mapping einer begrenzten Eingabemenge von 456 976 Elementen auf eine Ausgabemenge von 10 000 Elementen immer eine Ungleichverteilung.
Zwischenzeitlich hatte der TE die anfängliche Anforderung derweil aufgeweicht:

Doch. Es genügt, wenn die Anzahl der Vorkommen zwischen ceil(Optimalwert)-1 und ceil(Optimalwert) liegen.

Hashfunktionen sollen im Allgmeinen auf beliebigen Input anwendbar sein, an der Stelle kommt dort eine Anforderung an Gleichverteilung von Pseudozufallswerten rein, die eben nicht pauschal mit "Der Bias ist aber kleiner 1" abgetan werden kann.

Nun darf man sich fragen, weshalb überhaupt eine "Gleichverteilung" als Anforderung für dieses Mapping gestellt wird. Wenn man sich der Konsequenzen einzelner Vereinfachungen oder Vernachlässigungen bewusst ist, kann man die natürlich in der Praxis auch anwenden. Wenn nicht, ist das prinzipiell schnell mal ein gefährlicher Fehler wie aus der von TomH22 beschriebenen Kategorie.

"Kunstfehler" [...] Dazu gehört z.B. auch Race Conditions bei parallelen Zugriffen zu ignorieren, weil "die Wahrscheinlichkeit gering ist".