Good Mood

Dies ist der erste Beitrag in einer 3-teiligen Serie über die Grundlagen der Kryptographie. Die Serie ist wie folgt umrissen:

1. Symmetrische Verschlüsselung
2. Datenintegrität & Authentifizierte Verschlüsselung
3. Asymmetrische Verschlüsselung mit öffentlichen/privaten Schlüsselpaaren

Das Eintauchen in die Welt der Informatik kann eine entmutigende Aufgabe sein. Besonders allein!, In dieser Blog-Serie möchte ich einen umfassenden Überblick über die Grundlagen der Kryptographie für diejenigen bieten, die sich weiter mit dem Thema befassen möchten und nicht unbedingt wissen, wo sie anfangen sollen. Diese Übersicht basiert speziell auf meinen wichtigsten Takeaways aus Stanfords Cryptography I-Kurs, wie er von Dan Boneh unterrichtet wird, verfügbar auf Coursera.

Ich habe mich für diesen Kurs entschieden, da ich ein Blockchain-Entwickler bin, der nicht aus einem traditionellen Comp-Sci-Hintergrund stammt. Ich studierte Wirtschaftswissenschaften in der Schule, aber veered mehr in Richtung Computerprogrammierung, wie ich meine Karriere begann., Seit ich mit dem Codieren begonnen habe, war ich auf der Mission, „näher am Computer“ zu sein — um die Abstraktionsebenen zurückzuziehen, die ich als Webentwickler genossen habe, und zu verstehen, was unter der Haube vor sich geht. Der Übergang von der Webentwicklung in Kryptowährung und verteilte Systeme war in vielerlei Hinsicht ein wilder und wunderbarer Schritt in diese Richtung, nicht zuletzt, um sich mit den Konzepten der Kryptographie vertraut zu machen. Ich wollte jedoch ein solideres Fundament., Da es ein ziemlich weites Feld ist, dachte ich, es lohnt sich, $70 fallen zu lassen, um diese Informationen in einem Forum zu konsumieren, das speziell von der Stanford University kuratiert wurde. Sie können diesen Kurs auch überprüfen, ohne Aufgaben kostenlos abzugeben. Die Wunder des Internets!

Fangen wir an.

Kryptographie ist im Wesentlichen die Praxis der sicheren Kommunikation in Gegenwart potenzieller Gegner Dritter. Das Konzept der sicheren Kommunikation besteht aus zwei Hauptpunkten:

1. Sicherheit gegen Abhören: Dies gewährleistet die Vertraulichkeit der Daten.,
2. Sicherheit gegen Datenmanipulation: Dies gewährleistet die Datenintegrität, dh niemand kann die von Ihnen gesendeten Daten manipulieren und den Empfänger täuschen, die manipulierten Daten als gültig zu akzeptieren.

Die Vertraulichkeit der Daten wird durch Verschlüsselung erreicht, die zwei Formen annehmen kann: symmetrisch und asymmetrisch.

• Die symmetrische Verschlüsselung verwendet einen einzigen Schlüssel, der für alle Teilnehmer freigegeben werden muss, die kommunizieren.
• Asymmetrische Verschlüsselung verwendet persönliche Schlüssel., Jeder Teilnehmer verfügt über einen eigenen öffentlichen Schlüssel und ein privates Schlüsselpaar zum Verschlüsseln und Entschlüsseln von Nachrichten bei der Kommunikation.

(Hinweis: In diesem Blogpost wird über Kryptographie im Kontext der symmetrischen Verschlüsselung gesprochen. In einem Follow-up-Beitrag werden wir in die asymmetrische Verschlüsselung eintauchen.)

Datenverschlüsselung: Zwei Arten von Chiffren

Die Verschlüsselung gewährleistet die Vertraulichkeit der Daten und umfasst zwei wichtige Komponenten:

1. Einen geheimen Schlüssel: Im Rahmen der symmetrischen Verschlüsselung können wir davon ausgehen, dass unsere Teilnehmer, Alice und Bob, einen gemeinsamen geheimen Schlüssel haben.,
2. Eine Chiffre: eine Reihe von Algorithmen, eine für die Verschlüsselung und eine für die Entschlüsselung.

Es ist wichtig zu beachten, dass die Verschlüsselungs-und Entschlüsselungsalgorithmen öffentlich bekannt sind. Das einzige, was geheim gehalten wird, ist der Schlüssel.

Zwei Arten von Chiffren sind Stream-Chiffren und Block-Chiffren. Eine mögliche Voraussetzung für ein adäquates Verständnis dieser beiden Chiffren ist die Kenntnis bitweiser Operationen (Operationen, die an Bits ausgeführt werden). Genauer gesagt, das Konzept der exklusiven-oder (XOR). Ich habe diesen Blogpost gefunden, um eine sehr klare Erklärung für bitweise Operationen zu geben., Oder Sie können versuchen, das Konzept von XOR anhand des folgenden Bildes zu verstehen. Grundsätzlich werden zwei Bits kombiniert und wenn sie unterschiedlich sind (eine 0 und eine 1), ergeben sie 1, und wenn sie gleich sind (beide 0 oder beide 1), führen sie zu 0. Von nun an gehe ich davon aus, dass der Leser das Konzept von XOR versteht und dass die universelle Notation für XOR lautet: ⊕

Stream-Chiffre

Eine Stream-Chiffre ist eine symmetrische Schlüsselchiffre, bei der der Klartext (in Byte-Form) ist XOR ‚ d Stück für Stück mit dem Schlüssel (auch in Byte-Form), um den verschlüsselten Chiffretext zu erzeugen., Der gleiche Prozess wird verwendet, um den Chiffretext zu entschlüsseln. In Anbetracht der Art der XOR Operation, wenn wir den Chiffretext mit dem Schlüssel XOR, ergibt sich dies mit dem ursprünglichen Klartext zurück.

Ein kluger Leser könnte aus dieser Beschreibung erkennen, dass der Schlüssel (in der obigen (wie „Cipher Stream“) und Klartext müssen etwas sehr Wichtiges gemeinsam haben. Das ist richtig! Der Schlüssel und der Klartext müssen gleich lang sein., Das ist natürlich nicht sehr praktisch.

Um eine Stream-Chiffre praktischer zu machen, wird die Idee eines Pseudorandom-Generators eingeführt. Ein Pseudorandomgenerator ist eine deterministische Prozedur, die eine Eingabe benötigt und ein noch längeres Pseudorandomergebnis ausgibt. Da es sich um eine deterministische Prozedur handelt, wird immer die gleiche exakte Ausgabe zurückgegeben, wenn dieselbe Eingabe angegeben wird (dh „abc123“ führt jedes Mal zu „8474f24e0d72e1b949ffd2…“)., Das Wort Pseudorandom bedeutet, dass die Ausgabe zwar nicht wirklich zufällig ist (da sie basierend auf einer bestimmten Eingabe bestimmt wird), aber tatsächlich nicht von einer wirklich zufälligen Zeichenfolge zu unterscheiden ist. Mit anderen Worten, bei einer Stichprobe von Ein-und Ausgängen gibt es keine Hinweise darauf, welcher Ausgang einem bestimmten Eingang entspricht und umgekehrt, daher ist es Pseudorandom. Es ist möglich, den gemeinsam genutzten geheimen Schlüssel als Eingabe zu verwenden, um einen noch längeren Pseudorandom-Schlüssel zu erzeugen, der als langer Schlüssel XOR ‚ d mit dem ebenso langen Klartext fungiert.,

Diese spezifische Implementierung einer Stream-Chiffre, die wir bisher veranschaulicht haben, wird als „One-time-pad“bezeichnet. Ein äußerst wichtiges Merkmal des One-time-Pad ist, dass die One-Time-Pad-Taste nur EINMAL verwendet werden kann. Sobald es ein zweites Mal verwendet wird, wird die Sicherheit dieser Nachrichten beeinträchtigt.

Unten abgebildet ist eine Folie aus dem Kurs. PRG (K) bezeichnet die Pseudorandomenfolge, die aus unserem gemeinsamen Schlüssel K erzeugt wird.Das Symbol ⊕ bezeichnet XOR. c bezeichnet Chiffretext. m bezeichnet Nachricht (oder Klartext).,

Grundsätzlich sagt diese Folie, dass wir, sobald der Schlüssel zweimal verwendet wird, XOR die Chiffretexte zusammen, und das ist genau gleich XOR ‚ ing die beiden Klartexte zusammen. Da es genügend Redundanz in Englisch gibt, kann ein versierter Angreifer diese Informationen verwenden, um die Nachrichten vollständig wiederherzustellen.

Um einen gemeinsamen geheimen Schlüssel zu erhalten, kann das Konzept eines Nonce verwendet werden, um sicherzustellen, dass wir den einmaligen geheimen Schlüssel niemals wiederholen., Eine Nonce ist eine beliebige Zahl, die nur einmal in einer kryptografischen Kommunikation verwendet werden kann. Beim Senden des Chiffretextes kann der Absender auch eine Nonce senden, die mit dem geheimen Schlüssel kombiniert werden soll, um dann als Eingabe einen eindeutigen Pseudorandomschlüssel für jede Verschlüsselung zu erzeugen.

(Sie haben vielleicht bemerkt, dass die obige Folie Attack 1 sagt., Abgesehen davon ist Angriff 2 für diejenigen, die sich fragen, was Angriff 2 ist, die Tatsache, dass Stream Cipher zwar Datenvertraulichkeit bietet, aber KEINE Datenintegrität wie im ersten Abschnitt definiert bietet)

Blockchiffre

Der zweite Verschlüsselungstyp ist eine Blockchiffre. Eine Blockchiffre nimmt eine Eingabe fester Länge auf und verschlüsselt den Klartext immer wieder iterativ mit einem anderen Schlüssel (einem „runden Schlüssel“) für jede Runde und gibt letztendlich einen Chiffretext gleicher Länge aus. 3DES und AES sind zwei Beispiele für Blockchiffren,die eine Eingabe von 48 Bit bzw.,

Die obige Folie zeigt die Grundarchitektur einer Blockchiffre. Sie können sehen, dass ein Schlüsselerweiterungsmechanismus verwendet wird, um für jede Runde einen neuen Schlüssel zu haben. Der Klartext mit der Bezeichnung (m) für Nachricht wird immer wieder verschlüsselt, bis schließlich der entsprechende Chiffretext (c) gleicher Länge zurückgegeben wird.

Der Kürze halber werde ich in diesem Blogpost auf AES eingehen., Obwohl DES / 3DES historisch bedeutsam ist, wird AES heute häufiger verwendet und akzeptiert.

AES ist als Substitutions-Permutationsnetzwerk aufgebaut. AES arbeitet auf einem 128-Bit-Block, gleich 16 Bytes. Wie oben oben links abgebildet, schreiben wir die 16 Bytes als 4 x 4 Matrix. Diese Matrix dient als Datenstruktur, die zum Mischen von Daten geeignet ist., In jeder Runde ist der Prozess wie folgt:

1. Wir XODER der runde Schlüssel, zuerst (k0), mit der aktuellen Nachricht
2. Dann durchlaufen wir einen Substitutionsprozess, bei dem Datenblöcke durch andere Blöcke ersetzt werden basierend auf einer gegebenen Substitutionstabelle (Bild oben (1) ByteSub).
3. Wir durchlaufen eine Permutationsebene, in der Bits permutiert und gemischt werden(Bild oben (2) ShiftRow & (3) MixColumn).
4. Dann wiederholen wir diesen Vorgang für 10 Runden.,

Oben abgebildet, werden Sie feststellen, dass die letzte Runde den Schritt Mix Column überspringt, XOR ist das Ergebnis mit unserer letzten runden Taste und gibt unseren resultierenden Chiffretext aus. Um zu entschlüsseln, kehren wir einfach den Prozess um. Der Kurs bietet einen umfassenden Überblick über diesen Verschlüsselungsprozess und ermutigt die Schüler, tiefer in ihn einzutauchen, wenn er für Sie von Interesse ist. Deshalb werde ich das AES-Innenleben dabei belassen. Ich würde den Leuten empfehlen, sich das Fiestel-Netzwerkverfahren von 3DES anzusehen, um einen lustigen Vergleich und Kontrast verschiedener Blockchiffren zu erhalten.,

In Bezug auf Hardware hat Intel seit der Einführung von Intel Westmere seine Prozessoren mit speziellen Anweisungen für die AES-Optimierung entwickelt, die direkt in ihre Hardware integriert sind, und AMD folgte kurz darauf.

Blockverschlüsselungsmodi

Im Gegensatz zu einer Streamverschlüsselung nimmt eine Blockverschlüsselung nur eine Eingabe fester Länge an. Offensichtlich möchten wir Daten verarbeiten, die größer als 16 Byte gleichzeitig sind. Als nächstes ist es wichtig, die Betriebsmodi zu verstehen, unter denen wir Blockchiffren verwenden können, um große Datenmengen zu verschlüsseln., Um diese Blockchiffre auf einen großen Datensatz anzuwenden, wird die erste Betriebsart, die in den Sinn kommen kann, als „Elektronisches Codebuch“ (ECB) bezeichnet. EZB teilt die Daten einfach in 16 Byte Blöcke auf und führt die AES-Verschlüsselung einheitlich durch. Es könnte sogar parallel durchgeführt werden. Sehr schnell! Aber es ist eigentlich nicht sehr sicher.

Es ist unsicher, denn wenn sich eine 16-Byte-Nachricht wiederholt, chiffretext wird auch wiederholte Daten haben., Dadurch werden Informationen über unsere Daten an einen potenziellen Angreifer weitergegeben. Wir können diese Sicherheitsanfälligkeit auf den Fall anwenden, in dem wir ein Bild mit ECB verschlüsseln. Wie Sie unten sehen können, ist es klar, dass unser Bild ein Kopfschuss ist. Im stark schwarzen Bereich sehen wir eine Silhouette über die dunklen Haare und das Hemd.

Es ist wichtig, dass unsere Verschlüsselungsschemata semantisch sicher sind., Semantische Sicherheit ist das Konzept, dass, wenn wir einen Chiffretext haben, der einem von zwei verschiedenen Klartexten entspricht, ein Gegner nicht mit größerer Wahrscheinlichkeit als 1/2 erraten kann, welchem Klartext der Chiffretext entspricht. Offensichtlich ist es nicht semantisch sicher. Unser verschlüsseltes Bild gibt uns viele Informationen, um das entsprechende einfache Bild zu erraten.

ECB ist ein Beispiel für eine Ein-Tasten – Betriebsart (das heißt, wie das Ein-Zeit-Pad kann eine Taste nur einmal verwendet werden). Ein weiterer sicherer One-Time-Key – Betriebsmodus ist der deterministische Zählermodus. Sie können es selbst untersuchen., Ich werde auf die sicheren Betriebsmodi übergehen, die viele Zeitschlüssel ermöglichen!

Cipher Block Chaining (CBC) ist eine Betriebsart, die jeden 16-Byte-Klartextblock durch XOR ‚ ing des Chiffretextes des vorherigen Klartexts in unseren aktuellen Klartext verkettet, bevor die Blockchiffreverschlüsselung (dh AES) durchgeführt wird. Die untenstehende Abbildung verdeutlicht dieses Konzept:

Wir beginnen zunächst mit einer zufälligen IV., IV steht für Initialisierungsvektor, der definiert werden kann als: der Anfangswert, der zum Starten eines iterierten Prozesses verwendet wird. Im Fall von CBC muss die IV zufällig (daher unvorhersehbar) sein, daher muss sie für jede Transaktion eindeutig sein. Der erste Block des Chiffretextes ist einfach der unverschlüsselte random IV. Um den Rest des Chiffretexts zu erzeugen, wird zuerst der random IV mit dem ersten Klartextblock (m) XOR ‚ d. Das Ergebnis wird dann mit dem runden Schlüssel k verschlüsselt, um den ersten Block verschlüsselten Chiffretexts (c) zurückzugeben., Dieser Chiffretext erhält dann XOR ‚ d mit dem nächsten Klartext-Block (m), das Ergebnis wird mit dem runden Schlüssel k verschlüsselt und gibt den zweiten verschlüsselten Chiffretext-Block (c) zurück. Der Vorgang wird fortgesetzt, bis alle Blöcke verschlüsselt wurden.

Zum Entschlüsseln kehren wir den Vorgang einfach um.

Eine wichtige Komponente der CBC-Verschlüsselung ist, dass die Zufallsrate unvorhersehbar ist., Wenn die IV vorhersehbar wird, wird unser Verschlüsselungsschema anfällig für ausgewählte Klartext-Angriffe. Ein Klartext-Angriff (CPA) ist ein Angriffsmodell, das davon ausgeht, dass der Angreifer Chiffretexte für beliebige Klartexte erhalten und diese verwenden kann, um Informationen über verschlüsselte Nachrichten preiszugeben. Daher ist eine unvorhersehbare IV erforderlich, um die CPA-Sicherheit zu gewährleisten.

Ertragen Sie mich hier, während ich versuche zu erklären, wie dieser Angriff funktionieren würde: Aufgrund der Natur von XOR ist es möglich, einen ausgewählten Klartext-Angriff in Gegenwart vorhersehbarer IVS durchzuführen., Wenn Sie XOR den gleichen Wert zusammen (0101 ⊕ 0101) es wird immer gleich 0, daher wird es abgebrochen. Wenn Sie also vermuten, dass ein beobachteter Chiffretext c einem bestimmten Klartext entspricht, können Sie Ihre Hypothese mit einem vorhersehbaren IV testen. Wenn der betreffende Klartext mit IV1 so verschlüsselt wurde, dass c = E(k, m ⊕ IV1), können Sie einen neuen Klartext zur Verschlüsselung einreichen und sehen, ob Sie ein übereinstimmendes Ergebnis erhalten: c. Da Sie vorhersagen können, dass der IV IV2 sein wird, senden Sie m ⊕ IV1 ⊕ IV2. , Der CBC-Prozess wird diese Eingabe mit dem nächsten IV, IV2 XOR, so dass: c = E(k, m ⊕ IV1 ⊕ IV2 ⊕ IV2) daher bricht IV2 ab, und wieder verschlüsseln wir E(k, IV1 ⊕ m) was wiederum zu c führen würde und wenn dies geschieht, konnten wir erraten, was zuvor mit IV1 verschlüsselt wurde.

Wirklich tollen job, wenn Sie durch das — ^

Mit, dass, würde ich mag, um zu überprüfen, noch einen block cipher mode of operation, die zum Abschluss der ersten blogpost in diesem 3 Teil der Serie. Wenn es eine große Anstrengung war, es so weit zu schaffen, könnte jetzt ein guter Zeitpunkt für eine kurze Pause sein, bevor es weitergeht!,

Ok, also haben wir EZB, CBC und ihre Schwachstellen überprüft, aber schließlich und wahrscheinlich am wichtigsten werde ich den randomisierten Zählermodus (CTR) einführen. Dies ist die neueste, sicherste Betriebsart und auch effizienter als CBC.

Randomisierte Zähler Modus nimmt auch eine zufällige IV. Die IV dient einem anderen zweck hier aber. Unser Schlüssel wird kombiniert (z., über AES) mit einer iterierten Version unserer IV: Oben fügen wir 1 zu unserer IV für jede Iteration hinzu, sonst würden wir ein wiederholtes Ergebnis erhalten. Wir tun dies, bis wir ein Pad haben, solange unsere Klartext-Nachricht. Genau wie die einmalige Pad-Stream-Chiffre xorieren wir jetzt unsere Klartextnachricht mit unserem Pseudorandom-Pad, um einen Chiffretext zu erhalten. Wenn Ihre Hardware über mehrere AES-Engines verfügt, ist dies äußerst effizient, da sie parallelisierbar ist. In CBC hing jeder Chiffretext vom vorherigen Chiffretextblock ab, sodass eine Parallelisierung unmöglich war.,

Wir brauchen nicht einmal unbedingt eine Blockchiffre, um unsere IV und key zu einem Pseudorandom Pad zu kombinieren. Blockziffern müssen reversibel sein. Wenn Sie sich die Mechanik des randomisierten Zählermodus genau ansehen, werden Sie feststellen, dass wir für die Entschlüsselung nicht F(k, IV) umkehren müssen . Angesichts der Natur von XOR müssen wir nur dasselbe Pseudorandom-Pad und XOR mit unserem Chiffretext regenerieren. Um zu entschlüsseln, müssen wir den Vorgang daher wiederholen und nicht umkehren.,

Abstrakt gesehen (ich habe bisher vermieden abstrakte Begriffe), das bedeutet, dass die Prozedur, die wir verwenden, um kombinieren unsere geheimen Schlüssel und IV F(k, IV) muss eine Pseudo-Funktion (PRF) im Gegensatz zu einer Pseudo-zufälligen Permutation (PRP). Wir haben diese Konzepte tatsächlich in diesem Blogpost angewendet. Sowohl PRPs als auch PRFs sind deterministische Verfahren, die bei einer bestimmten Eingabe zu einer Pseudorandomausgabe führen. (z.B. AES, XOR). Eine PRP ist jedoch strenger in dem Sinne, dass sie reversibel sein muss., In der Tat werden die Begriffe PRP und Blockchiffre (wie AES) oft synonym verwendet. Ein PRF muss jedoch NICHT reversibel sein. Wenn Sie zu den vorherigen Folien zurückkehren, die in diesem Beitrag angezeigt werden, verstehen Sie jetzt die Notation PRF und PRP.

Das schließt meinen Überblick über symmetrische Verschlüsselung! Wir haben Stream-Chiffren und Block-Chiffren abgedeckt. Da Blockchiffren dann jeweils nur auf etwa 16 Bytes ausgeführt werden können, haben wir die Betriebsmodi behandelt, mit denen Blockchiffren auf großen Klartexten ausgeführt werden. Wir haben auch die Konzepte von PRPs vs PRFs geklärt.