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

foofoobar · Samstag um 12:58

BeBur schrieb:
@foofoobar 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, kommt natürlich auch auf den Anwendungsfall an.

Dann ist deine hashfunktion scheiße.

Hier mal für das letzte Byte von sha256 und deinen Input:

Code:

$ cat foo.sh
for i1 in a b c d e f g h i j k l m n o p q r s t u v w x y z
do
    for i2 in a b c d e f g h i j k l m n o p q r s t u v w x y z
    do
        for i3 in a b c d e f g h i j k l m n o p q r s t u v w x y z
        do
            for i4 in a b c d e f g h i j k l m n o p q r s t u v w x y z
            do
                echo $i1$i2$i3$i4
            done
        done
    done
done |
xargs -I{} -n1 -P 64 sh -c 'echo {} | /usr/bin/sha256sum'  |
sed '1,$ s/^..............................................................//' |
awk ' { foo[$1]++ } END { for (i in foo) { print i " " foo[i] }}'
$ sh foo.sh
94 1814
be 1808
4c 1843
76 1831
d3 1888
04 1780
a7 1824
48 1720
cd 1752
34 1760
81 1713
2c 1741
5f 1857
b4 1830
e1 1760
9e 1836
42 1768
db 1767
6e 1814
10 1838
f5 1795
29 1764
bb 1768
71 1769
d4 1801
4d 1800
93 1776
27 1767
c0 1821
8e 1744
52 1806
64 1718
fd 1906
1a 1733
a4 1754
e8 1831
07 1823
31 1821
ca 1755
5c 1875
84 1723
2f 1799
78 1803
ab 1797
0a 1786
59 1819
15 1760
f0 1757
72 1781
ba 1807
d7 1772
90 1852
ed 1836
00 1739
a3 1881
38 1768
1f 1810
63 1812
fc 1783
9a 1793
a9 1710
df 1711
46 1765
7c 1719
e5 1792
b0 1829
cb 1752
32 1685
87 1809
2e 1716
69 1853
0d 1786
d8 1752
23 1877
3d 1769
c4 1870
56 1821
8a 1755
d2 1751
4b 1863
ea 1800
77 1822
bd 1788
95 1757
a0 1799
b9 1848
03 1825
80 1773
ce 1709
2b 1783
35 1834
7d 1858
da 1718
9f 1784
b7 1727
41 1694
e2 1717
6d 1799
f4 1784
28 1767
11 1929
ad 1815
8d 1763
3a 1804
26 1800
53 1740
c1 1834
67 1748
89 1744
1b 1768
06 1768
e9 1837
a5 1741
36 1800
83 1828
cf 1764
5d 1741
2a 1781
ac 1808
79 1778
16 1792
f3 1819
c8 1787
6c 1756
4f 1830
d6 1714
ee 1779
91 1768
73 1789
f9 1825
25 1721
3b 1802
c2 1850
50 1769
fb 1740
62 1752
39 1742
e6 1796
45 1849
de 1765
b3 1886
9b 1824
09 1756
2d 1840
33 1758
68 1788
86 1800
cc 1810
5a 1806
0c 1784
98 1756
3e 1764
57 1790
22 1777
c5 1849
eb 1815
4a 1849
96 1794
d1 1762
74 1765
b8 1743
a1 1730
02 1814
fa 1813
61 1863
1d 1779
e3 1810
7e 1778
40 1763
b6 1760
12 1739
f7 1851
ae 1753
0f 1796
8c 1771
54 1759
c6 1770
18 1853
3f 1734
21 1752
66 1816
1c 1773
88 1763
ff 1769
a6 1795
49 1695
05 1748
37 1743
5e 1791
82 1707
e0 1758
dc 1777
43 1827
b5 1803
7f 1773
9d 1798
c9 1779
f2 1763
17 1892
6b 1797
92 1864
d5 1749
bc 1851
70 1824
4e 1810
ef 1707
f8 1723
24 1762
3c 1739
51 1822
8f 1788
c3 1738
fe 1749
65 1757
dd 1760
e7 1803
b2 1790
7a 1733
44 1769
08 1795
9c 1748
85 1769
5b 1783
30 1804
99 1789
0b 1762
aa 1820
58 1818
f1 1828
14 1707
6a 1757
75 1779
bf 1750
d0 1733
97 1832
ec 1732
01 1718
a2 1772
60 1749
1e 1788
47 1784
e4 1771
a8 1748
7b 1805
b1 1795
6f 1776
f6 1747
13 1760
d9 1774
0e 1798
af 1859
c7 1756
8b 1769
19 1787
20 1860
55 1789
$

CyborgBeta · Samstag um 13:21

0x8100 schrieb:
es gibt keine kryptografisch sichere hashfunktion,

Ich habe doch nie die Eigenschaft "kryptografisch sicher" erwähnt.

Ich will Diffusion erreichen, alle anderen Eigenschaften sind schon erfüllt.

Aber ok, dann bin ich halt blöd.

0x8100 · Samstag um 13:30

CyborgBeta schrieb:
Ich habe doch nie die Eigenschaft "kryptografisch sicher" erwähnt.

CyborgBeta schrieb:
Gewünschte Eigenschaften der Hashwerte:

eindeutig

feste Länge

kollisionsresistent

einwegig

deterministisch

pseudozufällig

gleichverteilt

https://de.wikipedia.org/wiki/Kryptographische_Hashfunktion#Eigenschaften

du willst eine kryptografisch sichere hashfunktion selber bauen, anstatt einfach ein etabliertes verfahren zu benutzen. vielleicht magst du noch sagen, wo das zum einsatz kommen soll, damit ich das nicht aus versehen noch verwende...

CyborgBeta · Samstag um 13:45

Mit hash += multiplier * (((s.charAt(i) - 'a') * 31) % 26); sähe die Ausgabe schon zufälliger aus, sie ist aber noch nicht schön verteilt:

Java:

public class Names {
    public static void main(String[] args) {
        int maxOccurrences = (int) Math.ceil(Math.pow(26, 4) / 10_000);
        test(maxOccurrences - 1, maxOccurrences, false);
        System.out.println();
        test(maxOccurrences - 1, maxOccurrences, true);
        System.out.println();
        System.out.println("Hash code 1 from aaaa: " + hashCode1("aaaa"));
        System.out.println("Hash code 1 from baaa: " + hashCode1("baaa"));
        System.out.println("Hash code 1 from abaa: " + hashCode1("abaa"));
        System.out.println("Hash code 1 from bbaa: " + hashCode1("bbaa"));
        System.out.println("Hash code 1 from zzzz: " + hashCode1("zzzz"));
        System.out.println();
        System.out.println("Hash code 2 from aaaa: " + hashCode2("aaaa"));
        System.out.println("Hash code 2 from baaa: " + hashCode2("baaa"));
        System.out.println("Hash code 2 from abaa: " + hashCode2("abaa"));
        System.out.println("Hash code 2 from bbaa: " + hashCode2("bbaa"));
        System.out.println("Hash code 2 from zzzz: " + hashCode2("zzzz"));
    }

    public static void test(int minOccurrences, int maxOccurrences, boolean modifiedAlgorithm) {
        int[] occurrences = new int[10_000];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    for (int l = 0; l < 26; l++) {
                        String s = "" + (char) ('a' + i) + (char) ('a' + j) + (char) ('a' + k) + (char) ('a' + l);
                        int hash = Integer.parseInt(modifiedAlgorithm ? hashCode2(s) : hashCode1(s));
                        occurrences[hash]++;
                    }
                }
            }
        }
        for (int i = 0; i < 16; i++) {
            System.out.println("Hash " + i + " occurs " + occurrences[i] + " times.");
        }
        for (int i = 0; i < occurrences.length; i++) {
            if (occurrences[i] < minOccurrences || occurrences[i] > maxOccurrences) {
                System.out.println("Hash " + i + " occurs " + occurrences[i] + " times!");
            }
        }
    }

    public static String hashCode1(String s) {
        if (s.length() < 4) {
            s += "a".repeat(4 - s.length());
        }
        int hash = 0;
        int multiplier = 1;
        for (int i = 0; i < 4; i++) {
            hash += multiplier * (s.charAt(i) - 'a');
            multiplier *= 26;
        }
        return String.format("%04d", (int) (10000.0 / Math.pow(26, 4) * hash));
    }

    public static String hashCode2(String s) {
        if (s.length() < 4) {
            s += "a".repeat(4 - s.length());
        }
        int hash = 0;
        int multiplier = 1;
        for (int i = 0; i < 4; i++) {
            hash += multiplier * (((s.charAt(i) - 'a') * 31) % 26);
            multiplier *= 26;
        }
        return String.format("%04d", (int) (10000.0 / Math.pow(26, 4) * hash));
    }
}

Code:

Hash code 1 from aaaa: 0000
Hash code 1 from baaa: 0000
Hash code 1 from abaa: 0000
Hash code 1 from bbaa: 0000
Hash code 1 from zzzz: 9999

Hash code 2 from aaaa: 0000
Hash code 2 from baaa: 0000
Hash code 2 from abaa: 0002
Hash code 2 from bbaa: 0002
Hash code 2 from zzzz: 8399

0x8100 schrieb:
damit ich das nicht aus versehen noch verwende

Es zwingt dich doch keiner, das einzusetzen ...

0x8100 · Samstag um 13:47

CyborgBeta schrieb:
Es zwingt dich doch keiner, das einzusetzen ...

CyborgBeta schrieb:
Schöne Prüfsummen für URL-Bestandteile berechnen (oder Namen).

ich will auch nicht aus versehen irgendeinen service nutzen, der so ein gefrickel implementiert...

CyborgBeta · Samstag um 13:49

@0x8100 Na dann, mach's gut.

Die Komplimente können wir uns sparen.

xpad.c · Samstag um 13:54

foofoobar schrieb:
Code:

$ sh foo.sh [...]

Naja...
Ist jetzt zwar nicht extrem unterschiedlich, aber die Häufigkeiten bewegen sich immerhin zwischen 1685 und 1929.

Code:

$ sort -k 2g foo.txt
32 1685
...
11 1929

xpad.c

CyborgBeta · Samstag um 13:57

xpad.c schrieb:
aber die Häufigkeiten bewegen sich immerhin zwischen 1685 und 1929

damit würde sha256sum schon einmal ausscheiden. Danke.

xpad.c · Samstag um 13:59

CyborgBeta schrieb:
@0x8100 Na dann, mach's gut. Die Komplimente können wir uns sparen.

Er hat Dich darauf hingewiesen, dass Du alle Kriterien genannt hast, die eine kryptografische Hashfunktion ausmachen.
Du ziehst Dich jetzt daran hoch, dass Du nicht "kryptografisch sicher" erwähnt hättest, aber de facto läuft es darauf hinaus.

Er hat auch damit Recht, dass man sowas aus guten Gründen nicht selbst entwickelt, und ob das nötig wäre oder nicht, können wir ja dank fehlendem Kontext nicht einschätzen. Daher die Erwähnung des guten Grundsatzes: NICHT selbst bauen.

xpad.c

Tornhoof · Samstag um 14:01

Sha256sum gekürzt ist hinreichend für sowas.
Les dir https://security.stackexchange.com/questions/97377/secure-way-to-shorten-a-hash durch und akzeptiere das es okay ist.

Wenn du was schnelleres haben willst nimm xxhash32, der ist hinreichend kollisionsresistent aber nicht kryptografisch sicher. Das sind dann 4 Byte.

BeBur · Samstag um 14:02

foofoobar schrieb:
Dann ist deine hashfunktion scheiße.

Du hast meinen Punkt nicht verstanden. Wenn du eine gleichverteilte Zufallsvariable Modulo einer Zahl rechnest, dann ist das Ergebnis (in der Regel) nicht mehr gleichverteilt. Daher, wenn du ein Verfahren verwendest, dass dir Gleichverteilung gewährleistet und das Ergebnis daraus mit Moduulo verrechnest, dann machst du damit die Gleichverteilung (in der Regel) kaputt.

CyborgBeta · Samstag um 14:02

xpad.c schrieb:
können wir ja dank fehlendem Kontext nicht einschätzen.

Ich hatte doch schon erwähnt, dass ich für lange URL-Namen schöne Abkürzungen finden möchte, die gleichzeitig Prüfsummen sein können. Dabei genügt es schon, nur die ersten 4 Zeichen der langen Namen zu verwenden.

BeBur · Samstag um 14:05

CyborgBeta schrieb:
für lange URL-Namen schöne Abkürzungen

Hashen und nur die ersten X Zeichen behalten und fertig. Aufwand 2 Minuten und 0 Beiträge in Foren.

Tornhoof · Samstag um 14:08

Wenn du jetzt noch kundenspezifität haben willst, also einen Salt, dann nimmst einfach sha256hmac

xpad.c · Samstag um 14:12

CyborgBeta schrieb:
Ich hatte doch schon erwähnt, dass ich für lange URL-Namen schöne Abkürzungen finden möchte, die gleichzeitig Prüfsummen sein können. Dabei genügt es schon, nur die ersten 4 Zeichen der langen Namen zu verwenden.

Das erklärt in keinster Weise die zusätzlichen Einschränkungen, die Du hier aufgestellt hast.

Zunächst ist es einem etablierten Hash-Verfahren völlig Wurst, ob Du es auf die komplette URL oder nur Teile davon anwendest. Diese Einschränkung scheint also nur Deiner... naiven... Herangehensweise geschuldet zu sein.

Dann machst Du eine weitere, extrem ungünstige Einschränkung mit dem Wertebereich Deines Ergebnisses. Es hat einen Grund, dass solche Verfahren mit der Länge ihres Ergebnisses in Bit angegeben werden und das Ergebnis als solches dann in Hex-Schreibweise ausgegeben wird: die konstante Länge. Diese Eigenschaft opferst Du hier ohne erkennbaren Grund und das ist es auch, was Dir das Hauptproblem bereitet.

xpad.c

KitKat::new() · Samstag um 14:14

BeBur schrieb:
Wenn du eine gleichverteilte Zufallsvariable Modulo einer Zahl rechnest, dann ist das Ergebnis (in der Regel) nicht mehr gleichverteilt. Daher, wenn du ein Verfahren verwendest, dass dir Gleichverteilung gewährleistet und das Ergebnis daraus mit Moduulo verrechnest, dann machst du damit die Gleichverteilung (in der Regel) kaputt.

woher hast du das?

xpad.c · Samstag um 14:22

@KitKat::new() Na, das ist doch logisch.
Wir können auch direkt ein einfaches Beispiel an Hand eines Teils der Aufgabenstellung bauen:

nimm gleichverteilte Zahlen von 0 bis 15 [0..F] (ein Nibble)
wende Modulo 10 an, weil der OP ja auf [0..9] besteht
10..15 werden auf 0..5 abgebildet
das Ergebnis ist nicht mehr gleichverteilt

xpad.c

CyborgBeta · Samstag um 14:56

xpad.c schrieb:
das Ergebnis ist nicht mehr gleichverteilt

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

bei 16: 16/10 = 1.6 also jeweils 1- oder 2-mal vorkommen. Es darf nur nicht bestimmte Zahlen 0-mal geben (in dem 16-Beispiel).

Aber dann frage ich mal anders: Wenn man eine Folge von 0 bis 9999 hat, wie bringt man die in zufällige Reihenfolge? (Selbstverständlich nicht echt-zufällig, sonst könnte man auch würfeln)

Ergänzung (Samstag um 14:59)

... Oder zwischen round_down(Optimale Anzahl Vorkommen) und round_up(Optimale Anzahl Vorkommen)

Ergänzung (Samstag um 15:18)

Habs gelöst.

Java:

import java.util.Random;

public class Names {
    public static void main(String[] args) {
        int minOccurrences = (int) Math.floor(Math.pow(26, 4) / 10_000);
        int maxOccurrences = (int) Math.ceil(Math.pow(26, 4) / 10_000);
        test(minOccurrences, maxOccurrences, false);
        System.out.println();
        test(minOccurrences, maxOccurrences, true);
        System.out.println();
        System.out.println("Hash code 1 from aaaa: " + hashCode1("aaaa"));
        System.out.println("Hash code 1 from baaa: " + hashCode1("baaa"));
        System.out.println("Hash code 1 from abaa: " + hashCode1("abaa"));
        System.out.println("Hash code 1 from bbaa: " + hashCode1("bbaa"));
        System.out.println("Hash code 1 from zzzz: " + hashCode1("zzzz"));
        System.out.println();
        System.out.println("Hash code 2 from aaaa: " + hashCode2("aaaa"));
        System.out.println("Hash code 2 from baaa: " + hashCode2("baaa"));
        System.out.println("Hash code 2 from abaa: " + hashCode2("abaa"));
        System.out.println("Hash code 2 from bbaa: " + hashCode2("bbaa"));
        System.out.println("Hash code 2 from zzzz: " + hashCode2("zzzz"));
    }

    public static void test(int minOccurrences, int maxOccurrences, boolean modifiedAlgorithm) {
        int[] occurrences = new int[10_000];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    for (int l = 0; l < 26; l++) {
                        String s = "" + (char) ('a' + i) + (char) ('a' + j) + (char) ('a' + k) + (char) ('a' + l);
                        int hash = Integer.parseInt(modifiedAlgorithm ? hashCode2(s) : hashCode1(s));
                        occurrences[hash]++;
                    }
                }
            }
        }
        for (int i = 0; i < 16; i++) {
            System.out.println("Hash " + i + " occurs " + occurrences[i] + " times.");
        }
        for (int i = 0; i < occurrences.length; i++) {
            if (occurrences[i] < minOccurrences || occurrences[i] > maxOccurrences) {
                System.out.println("Hash " + i + " occurs " + occurrences[i] + " times!");
            }
        }
    }

    public static String hashCode1(String s) {
        if (s.length() < 4) {
            s += "a".repeat(4 - s.length());
        }
        int hash = 0;
        int multiplier = 1;
        for (int i = 0; i < 4; i++) {
            hash += multiplier * (s.charAt(i) - 'a');
            multiplier *= 26;
        }
        return String.format("%04d", (int) (10_000 / Math.pow(26, 4) * hash));
    }

    public static String hashCode2(String s) {
        if (s.length() < 4) {
            s += "a".repeat(4 - s.length());
        }

        // fisher yates shuffle
        Random random = new Random(8);
        char[] chars = new char[s.length()];
        for (int i = 0; i < chars.length; i++) {
            int j = random.nextInt(i + 1);
            chars[i] = s.charAt(i);
            chars[i] = chars[j];
            chars[j] = s.charAt(i);
        }
        s = new String(chars);

        int hash = 0;
        int multiplier = 1;
        for (int i = 0; i < 4; i++) {
            hash += multiplier * (s.charAt(i) - 'a');
            multiplier *= 26;
        }
        return String.format("%04d", (int) (10_000 / Math.pow(26, 4) * hash));
    }
}

Das bräuchte ich jetzt nur noch als Bash-Script bzw. -Funktion.

Krik · Samstag um 15:20

Was ist denn mit dem CRC16-Hash, der weiter vorne erwähnt wurde? Tut der es nicht? Ich finde, der ist ein guter Vorschlag.

xpad.c · Samstag um 15:22

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

bei 16: 16/10 = 1.6 also jeweils 1- oder 2-mal vorkommen. Es darf nur nicht bestimmte Zahlen 0-mal geben (in dem 16-Beispiel).

WAT.
Nach der beschriebenen Modulo-Operation im Beispiel ist die Anzahl der Zahlen im Interval [0..5] doppelt so hoch wie die im Interval [6..9].
Wir reden ja hier nicht davon, dass es insgesamt nur 16 sind, sondern davon, dass die Häufigkeit des vorkommens der 16 Möglichkeiten in der Gesamtmenge gleichverteilt ist. Was willst Du da jetzt mit 1 oder 2 mal? Außerdem kann es definitionsgemäß ja gar keine Zahl geben, die gar nicht vorkommt.

verwirrt
xpad.c

Ergänzung (Samstag um 15:31)

CyborgBeta schrieb:
Das bräuchte ich jetzt nur noch als Bash-Script bzw. -Funktion.

Dir wurde lang und breit erklärt, was man machen bzw. lassen sollte und warum.

Dein Bash-Skript:

Code:

HASH=$(echo $1 | sha256sum -)
echo ${HASH:0:4}

xpad.c

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

Captain

Captain

Fleet Admiral

Captain

Fleet Admiral

Captain

Ensign

Captain

Ensign

Commander

Commodore

Captain

Commodore

Commander

Ensign

Rear Admiral Pro

Ensign

Captain

Fleet Admiral

Ensign

Ähnliche Themen