Multiple Hash-Verschlüsselung

    In letzter Zeit muss man immer mehr über die Wahrung der Anonymität und Sicherheit in Bezug auf die Rechte an Informationseigentum nachdenken. In diesem Artikel werde ich eine ziemlich interessante Lösung für die Verschlüsselung anbieten, mit der Sie mehrere verschiedene Objekte in einem Container mit verschiedenen Hauptschlüsseln speichern können und sicherstellen, dass beim Empfang eines Objekts keine "Spuren" anderer Entitäten vorhanden sind. Darüber hinaus kann aufgrund der Konstruktionsmerkmale des Algorithmus selbst das Vorhandensein einer entschlüsselten Entität immer der Zufälligkeit zugeordnet werden (dh es gibt keine Möglichkeit zu überprüfen, ob diese Daten ursprünglich verschlüsselt wurden oder nicht). Darüber hinaus ist der Algorithmus extrem widerstandsfähig gegen "Key Matching" -Angriffe. Die Methode hat zwar einen erheblichen Nachteil - eine katastrophal niedrige Geschwindigkeit, aber in einigen Sonderfällen kann sie dennoch nützlich sein.

    Der Kern der Methode ist ein mathematisches Objekt, das als Hash-Funktion bezeichnet wird . Als kleines Bildungsprogramm empfehle ich, auch meinen vorherigen Artikel zu lesen .

    Es gibt eine Reihe ziemlich interessanter Missverständnisse über Hash-Funktionen:
    • Die Hash-Funktion ist leicht umzukehren. Angeblich gibt es ein bestimmtes Programm md5decrypt, das das Ergebnis von md5crypt wiederherstellt.
    • Hash-Funktionen wie MD5 sind längst kaputt. eine Kollision auf einer bestimmten Linie bekommen - eine Kleinigkeit;
    • Hash-Funktionen sind ein Verschlüsselungsalgorithmus.

    All dies ist offensichtlich Unsinn. Kryptografische Hash-Funktionen sind per Definition schwierig zu handhaben, und für die derzeit verwendeten Methoden (MD5, SHA) hat niemand das Gegenteil bewiesen. Wir haben gelernt, Kollisionen nur in der allgemeinsten Form zu erstellen und dabei verschiedene Linien s1, s2 zu erzeugen, so dass f (s1) = f (s2). Und Hashing ist keine Verschlüsselung, schon allein deshalb, weil es kein Konzept für Verschlüsselungsschlüssel gibt.

    Aber manchmal kann „Unsinn“ helfen, eine interessante Lösung zu konstruieren. Versuchen wir einmal, uns vorzustellen, dass die obigen Thesen wahr sind. Lassen Sie uns ein Objekt erstellen, für das sie ausgeführt werden.

    Sei R (Schlüssel, Nachricht) = die ersten N Bits von md5 (Schlüssel + Nachricht), wobei N nicht sehr groß ist, sagen wir gleich 40. Und hier beginnt der Spaß!

    Erstens können wir für einen gegebenen Schlüssel leicht eine große Anzahl verschiedener Nachrichten erstellen, die den gewünschten Wert der Funktion ergeben. Etwa 2 ^ 40 verschiedene Zeilen zu sortieren, ist eine praktikable Aufgabe für einen normalen "Heim" -Computer. Wenn wir einen gegebenen Wert von X haben, der das Ergebnis der Anwendung der Funktion R ist, können wir das inverse Bild leicht finden.

    Das heißt, lassen Sie X = R ('test_key', 'msg') = 5B7AF38712
    die Nachricht 'msg' vergessen, wir haben nur den Hash-Wert 5B7AF38712 und der Quellschlüssel ist 'test_key', wir starten die Aufzählung und nach einer Weile erhalten wir den String 'msg' als prototyp!

    Was aber, wenn wir den Schlüssel ('test_key') nicht kennen, sondern nur den Hash-Wert? Dann können wir eine unendliche Anzahl von Schlüssel-Nachrichten-Paaren aufbauen , die unseren X-Wert angeben.

    Einige dieser Paare werden sogar sinnvoll aussehen, was auch immer das bedeutet. Darüber hinaus wird eines dieser Paare die Hauptfrage des Lebens des Universums und all dessen (in einigen Formulierungen) und die Antwort darauf sein .

    Warum so? Nur weil der Satz von Eingabewerten (d. H. Tasten und Nachrichten) unendlich ist und die Funktion R eine endliche Anzahl von möglichen Werten hat, von denen jeder (grob gesagt) die gleichen Auftrittswahrscheinlichkeiten hat.

    Nun, ich denke die Idee des Prozesses ist verständlich - wenn man eine Person '5B7AF38712' sendet, die den Schlüssel kennt ('test_key'), wird sie höchstwahrscheinlich die Nachricht erhalten ('msg') (aber es gibt keine Garantien dafür, es sollte angemerkt werden). Und, nicht wissend, - irgendein Müll.

    Magie


    Jetzt wollen wir lernen, wie Nachrichten verschlüsselt werden, damit der Adressat sie mit bestimmten Garantien korrekt entschlüsseln kann. Und doch sind wir ziemlich knifflig und möchten, dass dasselbe Paket mit einem anderen Schlüssel als eine andere angegebene Nachricht entschlüsselt wird.

    Das heißt, am Eingang: key1, message1 und key2, message2.
    Darüber hinaus ist crypt (key1, message1, key2, message2) = X
    und decrypt (X, key1) = message1 und decrypt (X, key2) = message2.

    Hier müssen wir die Funktion R "modernisieren", wir werden eine ganze Reihe von Funktionen aufbauen:
    R m (Taste, msg) = erste N Bits von md5 (Taste + Zeile (m) + msg),
    wobei Zeile (m) eine eindeutige Darstellung der Zahl m as ist Zeichenfolgen (z. B. Dezimalschreibweise).

    Der Index m ist ein spezieller „Kontrollwert“, den wir beim Verschlüsseln von Nachrichten variieren (dh er wird von unserem Algorithmus ausgewählt).

    Bevor ich erkläre, wie es ausgewählt wird, werde ich eine Entschlüsselungsprozedur anbieten, da es ziemlich einfach ist:
    Entschlüsseln (X, Schlüssel) = Wert msg, so dass R (Schlüssel, msg) == X, mit dem kleinsten m.

    In iterativer Form können Sie dies schreiben (Pseudocode):
    string decrypt(X, key)
    {
        for (int m = 0; m < MAX_INT; m++)
          for (string msg in generate_all_strings(MAX_STRING_LENGTH) )
            if (first_N_bytes( md5( key + m.ToString() + msg) ) == X) // R()
              return msg;
    }
    

    Hier erscheint ein neuer Parameter MAX_STRING_LENGTH , der für die maximale Länge einer Zeichenkette verantwortlich ist, die wir mit Gewalt erhalten können. Es ist sinnvoll, sie auf eine angemessene Aufzählungsleistung zu beschränken. Wenn die ursprüngliche Nachricht beispielsweise "Hallo, Habrahabr" lautete, müssen die Verschlüsselungszeichenfolgen selbst in kürzere Sequenzen unterteilt werden, z. B. "Hölle", "o", "abra", "habr". und versuchen Sie die Verschlüsselungsfunktion für jeden von ihnen, ohne den Schlüsselwechsel zu vergessen .

    Es ist nicht schwierig, eine Kollision für die ersten 40 Bits zu erhalten, und diese Funktion gibt garantiert einen Wert zurück. Die Funktion "Verschlüsselung" hat die Aufgabe, die Rückgabe des gewünschten Wertes sicherzustellen.

    Dies kann aber auch mit brachialer Gewalt geschehen:
    string encrypt(key, msg)
    {
        for (int m = 0; m < MAX_INT; m++)
        {
             string X = first_N_bytes( md5( key + m.ToString() + msg) ); // R()
             if (decrypt(X, key) == msg)
                return X;
         }
    }
    

    So geben wir Vertrauen in die richtige Dekodierung, indem wir sie mit verschiedenen Parametern modellieren. Wenn sich der Entschlüsselungsalgorithmus nicht ändert, ist dies eine Garantie für die Richtigkeit, und beachten Sie - keine Prüfsummen, Validatoren, andere Dinge, mit denen Sie die Tatsache der korrekten Entschlüsselung "verraten" können!

    Anfangs habe ich über die Möglichkeit gesprochen, zwei Nachrichten gleichzeitig zu verschlüsseln, was nun tatsächlich zu einer selbstverständlichen Tatsache wird:
    string encrypt(key, msg, key2, msg2)
    {
        for (int m = 0; m < MAX_INT; m++)
        {
             string X = first_N_bytes( md5( key + m.ToString() + msg) ); // R()
             if (decrypt(X, key) == msg && decrypt(X, key2) == msg2)
                return X;
         }
    }
    

    Hier gibt es jedoch einige Fallstricke - mit einem festen Bereich von "Steuerwerten" (m) - eine solche Funktion R m kann nicht existieren, und es wird notwendig sein, den Bereich zu erweitern. Eine Erweiterung des Bereichs verringert die Geschwindigkeit des Algorithmus. Im Allgemeinen sollte der Bereich für den Wert von m größer sein als die Breite der Hash-Funktion R, damit wir ihn einfach reduzieren können (was ich im Testprototyp getan habe). Aber mit einem stark reduzierten Bereich von Ausgabewerten kann ein solches m auch einfach nicht existieren.

    Im Allgemeinen habe ich mich bei der Implementierung des Prototyps für die Doppelbyte-Kürzung entschieden. Um das Leistungsproblem teilweise zu lösen (ich habe den Prototyp schnell in C # skizziert und die "lokalen" Kryptografieanbieter sind einfach schrecklich langsam! Fast 50.000 Mal langsamer als die Implementierung auf der GPU, die ich etwas später ausführen werde), habe ich die Option verlassen, nur Buchstaben zu verwenden Bereich az. In solch einer "traurigen" Form funktioniert es schon. Wir geben zwei Schlüssel-Wert-Paare ein, klicken auf "Encrypt2" und erhalten nach einer Weile einen Hash-Code. Mit dem ersten Schlüssel wird es schnell in die erste Nachricht entschlüsselt:


    Mit dem zweiten bzw. in die zweite:


    Beachten Sie, dass alle verschlüsselten Texte gleich sind. Nun, mit dem falschen Schlüssel - in einer seltsamen Nachricht (aber wo ist die Garantie, dass es nicht das Original war?):


    Sie können den Prototyp hier herunterladen:dl.dropbox.com/u/243445/md5h/HashCode.7z

    Es gibt eine Menge lächerlicher Einschränkungen, aber für die Empörten erinnere ich Sie daran, dass dies nur ein Beispiel für die Idee ist. Und eine gute Anwendung, die von der Relevanz der Idee abhängt, ist denkbar.

    Jetzt auch beliebt: