Bocholder: Hash

Hallo,

ich muss für die Schule ein Referat halten über das Thema "Hashfunktion". Das ganze ist für den Informatikunterricht, und hierbei zum Thema Kryptologie.

Ich habe mir das jetzt mal bei Wikipedia (Hashfunktion) durchgelesen, aber verstehe es ehrlich gesagt nicht so richtig. Kann mir jemand sagen, wie ich zum Beispiel selber eine GANZ einfache Hashfunktion selber basteln könnte? Also eine Art md0.1? Und wie ich diese dann auch wieder zurückrechnen könnte in ihren ursprünglichen Wert?
Nur so verstehe ich das glaube ich auch.

Vielen Dank für eventuelle Hilfe
Bocholder

  1. Hallo,

    Und wie ich diese dann auch wieder zurückrechnen könnte in ihren ursprünglichen Wert?

    Das ist beim Häschen eigentlich unüblich. Wichtiger ist, dass unterschiedliche Ausgangswerte unterschiedliche Karnikelwerte ergeben.

    Gruß
    Kalk

  2. Hi,

    Du könntest die Quersumme über alle Bytes bilden.
    Zurückrechnen geht da nicht.

    Grüße

    • Steffen
  3. http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung

  4. Hi,

    Du kannst ja auch einen Hash auf einen ganzen Roman errechnen. Zurückrechnen würde nur gehen, wenn keine Information verloren geht. Somit wär der Hash dann ungefähr so lang wie der Roman und in dem Sinn kein Hash mehr.

    Grüße

    • Steffen
  5. Meine Herren!

    Ich roll dein Posting mal von hinten auf.

    Und wie ich diese [Hashfunktion] dann auch wieder zurückrechnen könnte in ihren ursprünglichen Wert?

    Das geht per Definition nicht. Hash-Funktionen sollen nicht umkehrbar sein.

    Die simpelste Hash-Funktion, die ich mir Vorstellen kann ist die modulo-Operation mit 2. Modulo, falls du es nicht kennst, berechnet den Rest, der bei einer Division entstünde: "2 mod 2" ist also 0. "3 mod 2" ist 1. und "4 mod 2" ist wiederum 0. Das Ergebnis ist also immer 1 oder 0. Wenn wir nun also einen Hash serviert bekommen, beispielsweise 1, dann können wir mit Sicherheit sagen, die ursprüngliche Zahl eine ungerade Zahl gewesen sein muss, wir können aber nicht sagen ob es 3,5 oder 1337 war.

    In der Kryptographie spielen solch einfache Hash-Funktionen keine große Rolle, das war erstmal pure Theorie.

    In der Kryptologie, möchte man erreichen, dass es möglichst schwierig ist EINE der potenziellen Möglichkeiten zu erraten. Die Hash-Funktion aus meinem Beispiel oben, ist also nicht besonders geeignet, weil es nur die Möglichkeiten gibt, das die Zahl gerade oder ungerade gewesen sein muss. Gibt uns jemand den Hashwert "1" und will eine Lösung von uns, können wir ohne großen Aufwand "3" antworten, oder "5" oder "7". Gibt uns jemand den Hashwert "0", antworten wir "2", "4", "42". Ganz einfach.

    Wir können das Erraten einer Lösung erschweren, indem wir die Zielmenge vergrößern, wir könnten sagen statt "mod 2", nehmen wir "mod 1000". Dann gäbe es schon 1000 verschiedene Hashes, statt nur 2. Das Raten würde dadurch auf jedenfalls schwieriger werden. Aber wir kennen ja den Algorithmus und müssen gar nicht raten, sondern wir können logisch auf eine Lösung schließen. Gibt uns jemand den Hash "42", geben wir als eine Lösung "1042" an, denn 1042 mod 1000 = 42. Wenn wir wissen, dass 1042 eine gültige Lösung für die Umkehrung dieser Hash-Funktion ist, können wir direkt weitere Lösungen aufzählen: 2042, 3042 usw.

    An eine Hash-Funktion, die in der Kryptographie nützlich ist, stellt man deshalb zusätzlich den Anspruch, dass sich die Lösungen zu einem gegebenen Hash nicht so intuitiv berechnen lassen. Wobei Intuition hier ein weit gefächerter Begriff ist.

    Die "Sicherheit" einer Hash-Funktion ergibt sich also zum einen aus Größe der Menge der Hashes die gebildet werden können und zum anderen daraus, wie unterschiedlich die Hash-Werte für "ähnliche" Eingaben ausfallen.

    --
    “All right, then, I'll go to hell.” – Huck Finn
    1. Hallo,

      Die simpelste Hash-Funktion, die ich mir Vorstellen kann ist die modulo-Operation mit 2. Modulo, falls du es nicht kennst, berechnet den Rest, der bei einer Division entstünde: "2 mod 2" ist also 0. "3 mod 2" ist 1. und "4 mod 2" ist wiederum 0. Das Ergebnis ist also immer 1 oder 0. Wenn wir nun also einen Hash serviert bekommen, beispielsweise 1, dann können wir mit Sicherheit sagen, die ursprüngliche Zahl eine ungerade Zahl gewesen sein muss, wir können aber nicht sagen ob es 3,5 oder 1337 war.

      vielen Dank, das ist ein gut nachvollziehbares Beispiel. Ich kenne das unter dem Namen "Rechnen mit Rest" aber modulo hatten wir auch schon mal im Einführungskurs.

      Ich hatte da glaube ich einen Verständnisfehler: ich dachte, es gibt nur EINE Art von Funktion, die man Hashfunktion nennt. Nur gestaffelt in unterschiedliche "Härtegrade". Also sha ist der gleiche Rechenweg wie md5, nur komplexer. Verstehe ich es richtig: jede Funktion, die einen Hash (also eine Prüfsumme) berechnet, nennt man Hash? Egal, auf welche Weise?

      Und das Wesen eines Hashes ist es, diesen nicht zurückrechnen zu können? Damit ist es schon klarer.

      An eine Hash-Funktion, die in der Kryptographie nützlich ist, stellt man deshalb zusätzlich den Anspruch, dass sich die Lösungen zu einem gegebenen Hash nicht so intuitiv berechnen lassen. Wobei Intuition hier ein weit gefächerter Begriff ist.

      Sehr interessant, vielleicht muss ich mich da mal ein wenig einarbeiten.

      vielen Dank für deine ausführliche Erklärung!

      Bocholder

      1. Hello,

        Ich hatte da glaube ich einen Verständnisfehler: ich dachte, es gibt nur EINE Art von Funktion, die man Hashfunktion nennt. Nur gestaffelt in unterschiedliche "Härtegrade". Also sha ist der gleiche Rechenweg wie md5, nur komplexer. Verstehe ich es richtig: jede Funktion, die einen Hash (also eine Prüfsumme) berechnet, nennt man Hash? Egal, auf welche Weise?

        "Hash" kommt von "kleinhacken und vermengen".
        Und "make a hash of something" steht für "etwas vermasseln".

        Das trifft bei manchen Hashfunktionen auch zu. Da gibt es nachher soviele Zielkollisionen, dass sie eigentlich nix taugen.

        Wenn Du die Daten wiederherstellen können willst, spricht man von verschlüsseln.

        Liebe Grüße aus dem schönen Oberharz

        Tom vom Berg

        --
         ☻_
        /▌
        / \ Nur selber lernen macht schlau
        http://bikers-lodge.com
      2. Hallo,

        Und das Wesen eines Hashes ist es, diesen nicht zurückrechnen zu können? Damit ist es schon klarer.

        Hashen ist nicht Komprimieren. Es ist nicht einmal verlustfreies Komprimieren. Es ist das Abbilden einer unendlichen Menge an Zahlen/String/… auf eine sehr kleine, klar begrenzte Menge.

        Nehmen wir einmal:
           "Alle meine Entchen schwimmen auf dem See."
        wird mit einer fiktiven Hashfunktion abgebildet auf eine Zahl 0-999:
           363

        Jetzt versuche einmal, von 363 auf den Ausgangssstring zu kommen. Das ist natürlich möglich, aber nicht EINDEUTIG. Es wird unendlich viele Strings geben, die auf 363 abgebildet werden.

        Der Hash hat eine feste Länge, während das Original beliebig lang sein kann. Wenn der String länger als das Hash ist, dann ist entweder bloß die Redundanz reduziert worden (d.h. die Daten wurden kompromiert) oder es sind Informationen verloren gegangen. Letzteres ist der Fall.

        Wie gesagt, Zurückrechnen ist durchaus möglich, in dem man alle möglichen Strings durchläuft und nach einem Treffer sucht. In Rainbow Tables (vorberechneten Listen mit Eingabewerten und Hashes) kann ich höchstwahrscheinlich nachschlagen, dass der obige Satz eine mögliche Eingabe ist – EINE von potenziell unendlich.

        (Ich hoffe, ich stelle das richtig dar – ich bin weder mathematisch, noch informationstechnisch oder kryptographisch geschult.)

        Mathias

        1. Hallo,

          Und das Wesen eines Hashes ist es, diesen nicht zurückrechnen zu können?

          es wurde hier schon ein paarmal erwähnt: Prüfsumme. Eine Prüfsumme ist ein Gemenge zum Prüfen, nicht mehr, nicht weniger, das sollte sich schon aus dem Namen ergeben. Insbesondere kann eine Prüfsumme nicht die ursprünglichen Daten transportieren.

          Wie gesagt, Zurückrechnen ist durchaus möglich, in dem man alle möglichen Strings durchläuft und nach einem Treffer sucht.

          (Ich hoffe, ich stelle das richtig dar – ich bin weder mathematisch, noch informationstechnisch oder kryptographisch geschult.)

          Ich hoffe, du hast im Mathe-Unterricht der Grundschule auch was auf die Finger bekommen, wenn du alle möglichen Antworten "durchlaufen", auf Deutsch: geraten hast. Raten hat mit Rechnen nichts zu tun.

          Schönen Abend, Sara

          1. Hallo!

            Wie gesagt, Zurückrechnen ist durchaus möglich, in dem man alle möglichen Strings durchläuft und nach einem Treffer sucht.

            Ich hoffe, du hast im Mathe-Unterricht der Grundschule auch was auf die Finger bekommen, wenn du alle möglichen Antworten "durchlaufen", auf Deutsch: geraten hast. Raten hat mit Rechnen nichts zu tun.

            Ich weiß leider nicht, worauf du hinauswillst. Vermutlich willst du mich auf einen Fehler in meinem Posting aufmerksam machen, vermutlich auf eine ungenaue Ausdrucksweise.

            Ich meinte tatsächlich durchlaufen im Sinne einer Schleife, die aus allen möglichen Eingaben Hashes berechnet und mit dem gegebenen Vergleich. So etwas machen im Voraus die besagten Rainbow Tables.

            Ja, das ist kein Zurückrechnen im mathematischen Sinne, das wollte ich auch nicht behaupten. Wie auch immer, es sollte klar geworden sein, was ich meine, oder?

            Grüße
            Mathias

          2. Meine Herren!

            Und das Wesen eines Hashes ist es, diesen nicht zurückrechnen zu können?

            es wurde hier schon ein paarmal erwähnt: Prüfsumme. Eine Prüfsumme ist ein Gemenge zum Prüfen, nicht mehr, nicht weniger, das sollte sich schon aus dem Namen ergeben. Insbesondere kann eine Prüfsumme nicht die ursprünglichen Daten transportieren.

            Wo wir gerade bei Terminologie sind, sollten wir es dann auch ganz genau nehmen. Hash-Funktionen sind kryptografisch stärkere Algorithmen als Prüfsummen. In meinem ersten Posting habe ich es da auch nicht so genau genommen. Meine subjektive Auffassung dieses Unterschieds ist, dass es bei Hash-Funktionen möglichst schwierig sein soll eine Kollision zu erzeugen, auch dann noch, wenn bereits Kollisionen bekannt sind.

            Ein lesenswerter Artikel zum Thema: http://blog.codinghorror.com/checksums-and-hashes/

            --
            “All right, then, I'll go to hell.” – Huck Finn
            1. Hi,

              Wo wir gerade bei Terminologie sind, sollten wir es dann auch ganz genau nehmen. Hash-Funktionen sind kryptografisch stärkere Algorithmen als Prüfsummen. In meinem ersten Posting habe ich es da auch nicht so genau genommen. Meine subjektive Auffassung dieses Unterschieds ist, dass es bei Hash-Funktionen möglichst schwierig sein soll eine Kollision zu erzeugen, auch dann noch, wenn bereits Kollisionen bekannt sind.

              Du meinst kryptographische Hashfunktionen sind stärkere Algorithmen. Auch Prüfsummen sind Hashfunktionen. Hashfunktionen haben (AFAIK) noch nichts mit Kryptografie zu tun.

              Grüße

              • Steffen
              1. Om nah hoo pez nyeetz, Steffen!

                Wo wir gerade bei Terminologie sind, sollten wir es dann auch ganz genau nehmen.
                Hash-Funktionen sind kryptografisch stärkere Algorithmen als Prüfsummen.

                Du meinst kryptographische Hashfunktionen sind stärkere Algorithmen. Auch Prüfsummen sind Hashfunktionen. Hashfunktionen haben (AFAIK) noch nichts mit Kryptografie zu tun.

                Ein Algorithmus ist zunächst einmal nichts weiter als eine poplige Rechenvorschrift. Der kann also nicht stark oder schwach sein. Wohl aber kann das Resultat bestimmte Eigenschaften haben.

                Matthias

                --
                Der Unterschied zwischen Java und JavaScript ist größer als der zwischen Star und Start.

        2. Hallo Molili,

          Und das Wesen eines Hashes ist es, diesen nicht zurückrechnen zu können? Damit ist es schon klarer.

          Hashen ist nicht Komprimieren. Es ist nicht einmal verlustfreies Komprimieren. Es ist das Abbilden einer unendlichen Menge an Zahlen/String/… auf eine sehr kleine, klar begrenzte Menge.

          ok, das habe ich allerdings auch gar nicht gemeint. Komprimieren hatten wir schon, da habe ich mir selbst ein paar (natürlich sehr simple) Algorithmen gebastelt.

          Der Hash hat eine feste Länge, während das Original beliebig lang sein kann. Wenn der String länger als das Hash ist, dann ist entweder bloß die Redundanz reduziert worden (d.h. die Daten wurden kompromiert) oder es sind Informationen verloren gegangen. Letzteres ist der Fall.

          Kompromiert? Was ist das genau? Informationsverlust ist klar.

          Wie gesagt, Zurückrechnen ist durchaus möglich, in dem man alle möglichen Strings durchläuft und nach einem Treffer sucht. In Rainbow Tables (vorberechneten Listen mit Eingabewerten und Hashes) kann ich höchstwahrscheinlich nachschlagen, dass der obige Satz eine mögliche Eingabe ist – EINE von potenziell unendlich.

          Oh, danke. Durch deine Erläuterung kapier ich das erst so langsam. Ursrpünglich dachte ich, diese REgenbogentabellen sind einfach nur Listen von (üblichen) Passwörtern, z.b. "Hund123". Dann sind gesalzene Passwörter also gegen Rainbow-Table-Angriffe absolut sicher...?

          Danke!
          Bocholder

          1. (d.h. die Daten wurden kompromiert) oder es sind Informationen verloren gegangen. Letzteres ist der Fall.

            Kompromiert? Was ist das genau?

            Ein Tippfehler. ;-) Es sollte »komprimiert« heißen.

            Dann sind gesalzene Passwörter also gegen Rainbow-Table-Angriffe absolut sicher...?

            Absolut sicher ist nichts. Gesalzene Hashes fügen dem Passwort nur einen zufälligen String hinzu, was das Nachschlagen in Rainbow-Tables erschwert. Es müsste für jeden zufälligen Salt eine entsprechende Table berechnet werden. Bei einem 16-Byte-Salt wie bei PHPs password_hash() sind das sehr viele Kombinationen. Ich bin mir sicher, dass das jemand Hashes für einen Haufen an Salts vorberechnet hat, aber in der Praxis würde man eher Brute Force verwenden, um einen gesalzenen Hash zu knacken. Der Salt ist ja meist mitgeliefert, wenn der Hash dem Angreifer in die Hände fällt.

            Mathias

            1. Kompromiert? Was ist das genau?

              Ein Tippfehler. ;-) Es sollte »komprimiert« heißen.

              ah, ok :)

              Dann sind gesalzene Passwörter also gegen Rainbow-Table-Angriffe absolut sicher...?

              Absolut sicher ist nichts. Gesalzene Hashes fügen dem Passwort nur einen zufälligen String hinzu, was das Nachschlagen in Rainbow-Tables erschwert. Es müsste für jeden zufälligen Salt eine entsprechende Table berechnet werden. Bei einem 16-Byte-Salt wie bei PHPs password_hash() sind das sehr viele Kombinationen. Ich bin mir sicher, dass das jemand Hashes für einen Haufen an Salts vorberechnet hat, aber in der Praxis würde man eher Brute Force verwenden, um einen gesalzenen Hash zu knacken. Der Salt ist ja meist mitgeliefert, wenn der Hash dem Angreifer in die Hände fällt.

              Dumme Frage: dann nennt man also das Verwenden von Regebogentabellen nicht "Brute Force"?

              "Ich bin mir sicher, dass das jemand Hashes für einen Haufen an Salts vorberechnet hat"
              Noch eine dumme Frage: das müssen ja sehr viele Daten sein, oder? Wo speichert man denn diese Datenmengen?

              Und kann man sich irgendwo Rainbow-Tables runterladen und mal nachsehen, ob dort ein md5-Hash eines x-beliebigen Wortes zu finden ist? Ich habe bisher nur so eigenartige Tutorials gefunden, wie man selbst Rainbow-Tables erstellt. So richtig kapier ichs noch nicht, vielleicht muss ich mich da mal grundsätzlich einlesen.

              vielen Dank auf alle Fälle
              Bocholder

              1. Hello,

                Noch eine dumme Frage: das müssen ja sehr viele Daten sein, oder? Wo speichert man denn diese Datenmengen?

                Auf Toilettenpapier? *scnr*

                Und kann man sich irgendwo Rainbow-Tables runterladen und mal nachsehen, ob dort ein md5-Hash eines x-beliebigen Wortes zu finden ist?

                Kann man. Aber Google oder Metager oder Ask oder ... kennst Du schon?

                Wenn man zum Beispiel den md5-Hash für "Jessica" sucht, findet man den garantiert in einer der Tabellen. Die haben zuerst nämlich alle Wörterbücher durchgerechnet.

                Liebe Grüße aus dem schönen Oberharz

                Tom vom Berg

                --
                 ☻_
                /▌
                / \ Nur selber lernen macht schlau
                http://bikers-lodge.com
              2. Hallo,

                Dumme Frage: dann nennt man also das Verwenden von Regebogentabellen nicht "Brute Force"?

                Natürlich ist es auch Brute Force, siehe Saras Posting (»Raten« statt »Rechnen«). Ich meinte damit, dass man nicht groß Rainbow-Tables vorberechnet, sondern einfach alle möglichen Eingaben mit einen gegebenen Salt ausprobiert, bis man einen Treffer findet.

                Wo speichert man denn diese Datenmengen?

                Das Speichern ist heutzutage weniger das Problem. Einen Terabyte und selbst einen Petabyte kann man in der Cloud speichern, also auf vielen Servern im Internet. Das Berechnen, effiziente Durchsuchen und Verteilen ist eher das Problem.

                Und kann man sich irgendwo Rainbow-Tables runterladen und mal nachsehen, ob dort ein md5-Hash eines x-beliebigen Wortes zu finden ist?

                Für ungesalzene MD5-Hashes gibt es durchsuchbare Datenbanken im Web, z.B. http://de.md5decoder.org/. Herunterladen lassen sie sich z.B. hier: https://www.freerainbowtables.com/de/tables2/

                Mathias

  6. Hash

    Karl-Franz zu Ferdinand von und bei Dümpelshofen

    Guten Tag.

    Ich habe mir das jetzt mal bei Wikipedia (Hashfunktion) durchgelesen, aber verstehe es ehrlich gesagt nicht so richtig. Kann mir jemand sagen, wie ich zum Beispiel selber eine GANZ einfache Hashfunktion selber basteln könnte?

    GANZ einfach? Du addierst alle gegebenen Bytes. Fertig.

    Und wie ich diese dann auch wieder zurückrechnen könnte in ihren ursprünglichen Wert?

    Früher™, als alles noch besser war, hießen die Dinger Prüfsummen, und Hasch haben wir geraucht. Ich erwähne das, weil die Funktion durch einen deutschen Begriff für dich vielleicht etwas verständlicher wird. Aus der Summe 23 kannst du auch nicht herausfinden, ob sie aus 20 + 3 oder 12 + 11 entstanden ist. Du weisst nur, dass jemand schummelt, wenn er dir zur Summe 23 die Rechnung 2 + 3 als Ausgang präsentiert.

    Mit CRC, MD, SHA & Co. ist es das Gleiche, jedoch ergibt hier auch die kleinste Änderung an den Ausgangsdaten eine garantierte Änderung der Prüfsumme.
    Im Bereich der Kryptographie betrifft dies nicht nur einfach von vornherein unterschiedliche Datensätze (20 und 3 sollte eine andere Prüfsumme ergeben als 12 und 11) oder das Erkennen, teilweise auch das Beheben von Übertragungsfehlern, es muss vor allem sichergestellt sein, dass aus einer gegebenen Prüfsumme kein passendes "Original" (lies: eine Fälschung, die aber die gegebene Prüfsumme ergibt) erstellt werden kann.

    Mein Eingangsbeispiel einer wortwörtlichen Prüfsumme taugt in dieser Hinsicht überhaupt nicht. Ist das Original "20 und 3", die Prüfsumme 23, könne ein pöser Pube mein Original in "19 und 3 und 1" ändern, ohne dass ich etwas merken täte – die Prüfsumme stimmt ja. Und schon habe ich zu den 20 Ostereiern und 3 Schokoladenhasen noch eine Waschmaschine gekauft.

  7. Hello,

    eine Übersicht über Verfahren der Verschlüsselung findest Du z.B. hier:

    https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102_pdf.pdf?__blob=publicationFile

    Liebe Grüße aus dem schönen Oberharz

    Tom vom Berg

    --
     ☻_
    /▌
    / \ Nur selber lernen macht schlau
    http://bikers-lodge.com