ChaCha20 und Poly1305

    • C#
    • .NET 5–6

    Es gibt 1 Antwort in diesem Thema. Der letzte Beitrag () ist von exc-jdbi.

      ChaCha20 und Poly1305

      Hallo Community

      Wie sicher einige feststellen durften, funkst das ChaCha20Poly1305 in .Net6.0 noch nicht. Es werden Zusatzerweiterungen von OpenSsl (erst in einer höheren Version) gefordert, um der Plattformkompatibilität gerecht zu werden. Als Win10 Nutzer (vor allem auf dem Laptop) ist man da gleich ein wenig gefordert, vor allem wenn nicht mehr genug Speicher vorhanden ist. Das neue Packet verschling beim Update, bzw. Installation gleich ein paar 100Mb.

      Ich habe mir kurz die Zeit genommen, und mich mit ChaCha20 und Poly1305 ein wenig beschäftigt. Wie ich auch im Nachhinein feststellen durfte sind schon einige NuGet im Umlauf, die ChaCha20Poly1305 anbieten.

      Wer möchte kann sich mein Projekt von Github runterlanden, und sich ein wenig damit beschäftigen, wie diese zwei Algorithmen funktionieren. Ist OpenSource und darf im Sinne der Lizenz verwendet werden.

      Freundliche Grüsse

      exc-jdbi
      Mein eigen erstelltes Pflichtenheft

      ChaCha20 und Poly1305

      ChaCha20 ist ein symmetrischer Stromverschlüsselungsalgorithmus und wurde von Professor Dan Bernstein entwickelt. Der Authentifizierungsmodus Poly1305 stammt ebenfalls von ihm.

      In ChaCha20 steht die Zahl 20 für die Rundenanzahl. Der Name Poly1305 ist durch die Primzahl 2^130 – 5 entstanden, der für die Modulo Berechnung

      Quellcode

      1. H = ((H + M) * R) mod P

      herangezogen wird.

      ChaCha20 ist in RFC 8439 (vorher RFC 7539) definiert, als Alternative zu AES. ChaCha20 ist gegenüber AES sagt man schneller und einfacher implementierbar.

      Poly1305 ist ebenfalls in RFC 8439 definiert und generiert im Sinne von MAC ein 16 Byte Tag als Authentifikator. Die eigentliche Nutzung beider Algos im Sinne von AEAD ist ebenfalls in dieser Spezifikation beschrieben.

      Vielleicht noch ein kleiner Hinweis. Poly1305 ist kein HMAC, und darf daher auch nicht so angewendet werden. Vielmehr ist die Nutzung von Poly1305 auf das Generieren eines einmaligen Tag beschränkt. Mehr dazu weiter unten.


      Wo kommen ChaCha20 und Poly1305 zum Einsatz

      Die IETF (Internet Engineering Task Force) hat eine Spezifikation RFC 7905 für die Nutzung im TLS (Transport Layer Security) herausgegeben. Man möchte mit ChaCha20 und Poly1305 den jetzigen Sicherheitsbedenken ein bisschen entgegenwirken.

      ChaCha20 und Poly1305 können aber noch an vielen anderen Orten eingesetzt werden. Da es sehr schnell ist, könnte ich mir auch vorstellen, dass grössere Speichermedien damit ver- bzw. entschlüsselt werden können. Gerade in diesem Bereich gibt es sehr wenige gute Algos die sich wirklich Praxistauglich zeigten.

      Ansonsten kommt es auch überall dort zum Einsatz, wo ver- und entschlüsselt werden muss.

      Ich denke die Zukunft wird es zeigen, wie weit das Vertrauen auf ChaCha20 und Poly1305 sich bewähren.

      datatracker.ietf.org/doc/html/rfc7905
      datatracker.ietf.org/doc/html/…ha20poly1305-04#section-8



      Funktionsweise von ChaCha20

      Die Initialisierung von ChaCha20, der CurrentBlock

      Ohne jetzt gross auf die mathematischen Gegebenheiten einzugehen, ist der ChaCha20-Algorithmus grundlegend sehr einfach und genau so genial aufgebaut.

      Für die Initialisierung von ChaCha20 werden vorwiegend 3 Parameter benötigt.
      • Key 32 / 16
      • Iv (Nonce) 8 / 12
      • Tau-Sigma 16
      Je nach Keylänge 16 oder 32 (zufällig generiert), wird das entsprechende tau = „expand 16-byte k“ oder sigma = „expand 32-byte k“ verwendet. Sie werden vielfach auch „Constants“ benannt, weil beide Parameter von Professor D.J. Bernstein so fix definiert worden sind, und besitzen jeweils die Länge 16 Byte.

      Bei der Initialisierung von ChaCha20 werden alle 3 Parameter zu einem Block gebildet. In meinem Programm heisst dieser Block CurrentBlock. Es gibt aber auch andere Bezeichnungen wie z.B. Engine oder eben einfach nur Block.

      Der Currentblock (L = 16 UInt32) wird folgendermassen zusammengebaut.
      • Die ersten 4 Indexes (0 - 3) sind die Constants.
      • Die Indexes 4 - 12 werden aus dem 32 Byte Key gebildet. Ist der Key nur 16 Byte lang, so werden einfach nur die Indexes 4 - 8 gefüllt.
      • Und zum Schluss kommen noch 8 Byte von der Iv (Nonce). Sie werden in die Indexes 14 und 15 gefüllt. Sofern ein Iv (Nonce) von 12 Byte verwendet wird, wird sie einfach auf die Indexes 13 - 15 verteilt (Vorteil und Nachteil siehe unten).
      Nun gibt es noch den Index 12 und 13. Sie werden als Counter verwendet. D.h. bei jedem Anfordern eines neuen Block-Key (wird auch Block-Update genannt) wird der Counter um 1 inkrementiert.

      Da es zwei Counter-Indexes gibt kann der Counter also bis auf (2^32)^2 = 2^64 inkrementiert werden. Dann sind beide Indexes wieder 0, und genau dann ist der CurrentBlock als Key komplett ausgedient, und muss erneuert werden. Man behilft sich einfach damit, dass man einen neuen Iv (Nonce) in die Indexes 14 und 15 einfliessen lässt. Von jetzt an kann der CurrentBlock für weitere 2^64 Inkrementes genutzt werden, was einer Verschlüsselungsstrecke von 2^64 * 64 = 2^70 (ca. 1 Billion GB) entspricht.

      Hinweis: Die IETF-8439 definiert einen Iv (Nonce) von 94 Bit bzw. 12 Byte. Auch das ist natürlich möglich. Dadurch ist die Verschlüsselung wesentlich stärker, jedoch wird der Counter auf 2^32 beschränkt, was für Verschlüsselungen von kleineren Speichermedien ausreichen würde. Für grössere Speichermedien reicht sie jedoch nicht aus. Die Verschlüsselungsstrecke wäre nur 2^38 = 2^32 * 64 (256GB).


      Verschlüsselung bzw. die Entschlüsselung in ChaCha20

      Die Ver- wie auch die Entschlüsselung funktionieren ganz genau gleich. In dem Sinne darf man sagen dass es sich hier um eine Forward-Programmierung handelt.

      In meinem Programm habe ich sie getrennt, weil bei mir noch ein Tag gebildet wird bzw. eine Verifizierung gemacht wird. Damit das funktioniert, musste ich jedoch einen kleinen Trick anwenden, da ich nicht das Poly1305 zur Tagbildung herangezogen habe.

      Wie aus dem obigen Beitrag heraus geht, bleibt der CurrentBlock immer aus den Bestanteilen Constants, Key, Counter und Iv (Nonce). Das einzige was sich ändert ist der Counter der um 1 Inkrementiert wird. Um ein einfaches Tag bilden zu können speichere ich anfangs beide Counter-Werte in eine Variable, und bilde nach der Verschlüsselung mitsamt der hashed associated und den ursprünglichem CurrentBlock ein Tag. Die Verifizierung funktioniert genau gleich, und sobald das aktuelle Tag berechnet ist, kann es verglichen werden.

      Wie funktioniert nun die Ver- bzw. Entschlüsselung in ChaCha20 eigentlich?

      Der Plaintext (auch Message) wird blockweise mit dem angeforderten internen Key und mit einer XOR-Verkryptung verschlüsselt. Der interne Key ist 64 Byte lang und wird aus dem aktuellen Abbild des Currentblock und dem eigentlichen ChaCha20 Algorithmus (ChaCha20Core: ARX Addition-Rotation-XOR) erzeugt bzw. transformiert. Das ist auch schon alles.

      Ist also eine Message kleiner als 64 Byte wird nur einmal ein interner Key angefordert. Ist eine Message z.B. 1000 Byte lang, so wird der interne Key 16x angefordert, und ist jedes Mal anders, weil der Counter erstens immer um 1 inkrementiert wird und zweitens der ChaCha20-Algorithmus dafür sorgt, dass es nie der gleiche Key sein kann.

      Hinweis: Wer auch eine Iv (Nonce) von 8 Byte wie ich es in meinem Programm habe verwenden möchte, aber die Verkryptung ein bisschen verstärken will, der kann die Variable associated (oder eine Blockabhandlung davon) in die XOR Verkryptung miteinbeziehen.

      Es gibt auch noch andere Möglichkeiten auf Seitens des CurrentBlock die ich hier aber nicht weiter erwähnen möchte.


      Bildung eines Tag in ChaCha20

      Es kann generell nie schaden eine Verifizierung einzubeziehen. Das Tag wird erst bei der Entschlüsselung geprüft, d.h. bevor überhaupt die Entschlüsselung eingeleitet wird, wird der Ciphertext kontrolliert ob irgendwelche Manipulationen vorgenommen worden sind.

      Wie hoch die tatsächliche Wahrscheinlichkeit ist, dass eine verfälschte Nachricht zurückgewiesen wird, lässt sich durch meine Eigenkonstruktion nicht so leicht sagen. Tests die ich jedoch so gut wie möglich gemacht habe zeigen dass sie sehr hoch sein muss, und darum denke ich dass es der SUF-CMA-Terminologie (strong unforgeability against chosen-message attacks) standhält.

      Wissen muss man also, dass das Erstellen eines Tag ein separater Bestandteil ist, und in dem Sinne nichts mit der Verschlüsselung oder der Verschlüsselungsstärke des Ciphertext zu tun hat.


      Verschlüsselungsstärke von ChaCha20

      ChaCha20 darf was die Verschlüsselungsstärke anbelangt ruhig mit AES verglichen werden, da die Verschlüsselung selber als reine ARX Addition-Rotation-XOR ablauft. Es gibt keine Nachschlagtabelle wie AES es hat und ist daher gegen Cache-Timing-Angriffe sicher. Auch ist der ARX sehr CPU-Anweisungsfreundlich, was ChaCha20 wiederum robust und schnell macht.

      Aktuell sind Angriffe rar und nur die Zukunft selber wird wirklich zeigen, wie gut sich ChaCha20 nun wirklich sich bewährt.

      Wer sich weiter informieren will, dem habe ich auch noch ein paar Links.
      cr.yp.to/chacha.html
      cr.yp.to/chacha/chacha-20080128.pdf
      datatracker.ietf.org/doc/html/rfc7539
      datatracker.ietf.org/doc/html/rfc8439#section-2.4


      Funktionsweise von Poly1305

      Wie oben schon erwähnt erzeugt Poly1305 ein 16 Byte Tag als Authentifikator. Poly1305 kann genutzt werden um einen Einmalschlüssel mittels Key und Iv (Nonce) zu generieren. Man muss sich aber dessen bewusst sein, dass Poly1305 kein PRF (Pseudo Random Function) ist, d.h. der zufällige 32 Byte Key darf prinzipiell nur einmal (pro System) verwendet werden.

      Der Algorithmus selber ist sehr einfach, die mathematische Umsetzung hingegen, da mit UInt32 Variablen gearbeitet wird ein bisschen schwieriger.

      Für die Umsetzung des Algos werden mehrere Variable benötigt.
      • H ist der Accumulator und in der Regel eine 128 Bit Zahl (16 Byte). Kann kurzfristig grösser werden.
      • R ist der Multiplicator und ist eine 128 Bit Zahl (16 Byte).
      • S ist der Secretkey und auch eine 128 Bit Zahl (16 Byte)
      • P ist die Primzahl 2^130 - 5

      Initialisierung von Poly1305 (Vereinfachte Form)

      Auch hier möchte ich nicht tiefgründig in die mathematischen Gegebenheiten vordringen. Wer sich meinen Code angeschaut hat, der wird sehr schnell merken, dass es mehrere Möglichkeiten gibt, Poly1305 zu initialisieren. Schlussendlich wird jedoch das gleiche gemacht, bis auf die mathematische Darstellung. Ich erlaube mir hier die aus meiner Sicht einfachere Variante zu erklären.

      Poly1305 benötigt für die Initialisierung einen 32 Byte Key, der dazu genutzt wird die Variable R und S zu füllen. Man beachte, dass R aus 5 UInt32 (20 Byte) besteht und S aus 4 UInt32 (16 Byte).

      Die ersten 16 Byte vom Key werden für den Multiplikator R verwendet. Die einzelnen Werte vom Key, werden auf 5 UInt32 Items verteilt (Range 2^26). Die restlichen Werte im Key, werden ganz normal in den Secretkey S kopiert.


      Berechnung des Tag

      Für die Berechnung des Hash wird noch die Message benötigt. Der wird in 16er Byte-Blöcke eingeteilt. Ist also z.B. M.Length = 50, so werden 4 Blöcke gebildet, was auch 4 Runden bedeutet. Der Accumulator H ist am Anfang 0 (Unmittelbar nach der Initialisierung).


      Der BlockUpdate, die Modulo Berechnung

      Jeder einzelne Block ist wiederum eine 128 Bit Zahl (16 Byte). Zu dieser Zahl wird 2^128 dazugezählt. Nun wird mit der Primzahl P nach der Formel H = ((H + M) * R) % P eine Modulo-Berechnung gemacht.

      Da es 4 Blöcke gibt, wird diese Berechnung 4x (4 Runden) gemacht. Durch die Modulo-Berechnung ist der Accumulator H nach 4 Runden kleiner als die Primzahl P.

      Das Finale, Bildung eines Tag

      Zum Accumulator H wird nun noch der Secretkey S (128 Bit Zahl) dazu addiert. Dieser Hash-Wert wird auf den 16 Byte Tag mit folgender Ganzzahl Rechnung verteilt. (\ entspricht div-Berechnung)

      Quellcode

      1. Tag(0) = H mod 256; H \= 256;
      2. Tag(1) = H mod 256; H \= 256;
      3. etc.


      Weitere Literatur, Bemerkung

      Vielleicht wird sich der eine oder andere Fragen, warum nutzt man für das Poly1305 nicht den BigInteger? Nun diese Frage lässt sich einfach beantworten, denn der Weg über einen BigInteger bzw. über 128Bit Zahlen ist im Moment noch sehr unperformant. Für solche Berechnungen gibt es Polynom-Berechnungen, die es erlauben mit Bytes oder wie es hier der Fall ist mit UInt32 Datentypen zu arbeiten.

      Nimmt man sich für die Berechnung die Range 2^26 heran bleibt man mit 5 Variablen innerhalt von 2^130, was die Berechnung ein bisschen übersichtlicher gestaltet. (Die Modulo Berechnung mit P ist ein integrierter Bestandteil davon)

      Wer die mathematischen Hintergründe einsehen möchte, dem empfehle ich zu allererst das Whitepaper von Professor D.J. Bernstein durchzulesen. Die ganze Erklärung basiert zwar auf der Range 2^32 (UInt32), aber ich denke wer das verstanden hat, der kann die Ableitung auf die Range 2^26 nachher auch nachvollziehen.

      cr.yp.to/mac/poly1305-20050329.pdf
      datatracker.ietf.org/doc/html/rfc8439#section-2.5


      AEAD - Authenticated Encryption with Associated Data

      AEAD ist gemäss Wikipedia ein Betriebsmodi, die nebst Vertraulichkeit auch Authentizität und Integrität sicherstellen soll.

      In AES kennen wir sie z.B. als CBC oder GCM und sie ermöglichen in dem Sinne die Authentifizierung nicht nur der verschlüsselten Daten, sondern von beliebig weiteren Daten.

      Der neuste Modus von AES als Beispiel, ist GCM und ist ein authentifizierter Verschlüsselungsmodus mit assoziierten Daten. Die Authentifizierung wird hier durch parallel zur Verschlüsselung laufende Multiplikationen im Galoiskörper 2^128 realisiert.

      Und genau dieses Prinzip möchte man mit den zwei oben vorgestellten Werkzeugen auch realisieren. Es geht also darum die Möglichkeit zu besitzen nach dem schon Daten verschlüsselt worden sind, weitere Daten (per Continue) weiter zu verschlüsseln.

      ChaCha20Poly1305 und XChaCha20Poly1305 bieten diese Möglichkeit und sind im RFC 8439 bzw. in einer Zusatzspezifikation beschrieben. Wie weit die Zusatzspezifikation schon genehmigt worden ist, geht jedoch leider nicht hervor.

      de.wikipedia.org/wiki/Authenticated_Encryption
      datatracker.ietf.org/doc/html/rfc8439#section-2.8
      datatracker.ietf.org/doc/html/draft-irtf-cfrg-xchacha-03


      Funktionsweise von ChaCha20Poly1305

      ChaCha20Poly1305 kombiniert wie es der Name schon sagt die beiden oben vorgestellten Werkzeuge mit einer AEAD Konstruktion. Die AEAD Konstruktion gewährleistet, dass ein Ciphertext erzeugt wird, der die gleiche Länge wie der grundlegende Plaintext hat und nebst dem wird noch ein Tag erzeugt, dass 16 Byte lang ist. Eigentlich nichts Neues.

      Microsoft hat ab .Net6.0 die Klasse ChaCha20Poly1305 integriert. Für die Verwendung auf Windows wird jedoch Plattformkompatibilität vorausgesetzt, die nur mit einer höheren Version von OpenSsl gewährleistet werden kann. Es kann also durchaus sein, dass einige von euch (mich eingeschlossen) diese Klasse nicht verwendet können.


      Initialisierung von ChaCha20Poly1305

      Für die Initialisierung wird ein zufälliger 32 Byte Key und ein zufälliger 12 Byte Iv (Nonce) benötigt. Beide Variablen werden für die Initialisierung von ChaCha20 im Sinne von RFC 8439 für das erzeugen eines Subkey benötigt.

      Der frisch erzeugte Subkey wird für die Initialisierung der Poly1305, der ein übergeordneter integrierter Bestandteil in der ChaCha20Poly1305 Klasse ist, benötigt.

      Noch ein kleiner Hinweis zu ChaCha20. Gemäss RFC 8439 werden bei der Initialisierung dem CurrentBlock die kompletten 12 Byte in die Indexes 13, 14 und 15 kopiert. Der Counter beschränkt sich also nur auf den Index 12, was die Durchmischung (Transformation) in der ChaCha20Core schlussendlich erhöht.

      Weiter möchte ich nicht darauf eingehen. Wie die Initialisierung erfolgt sollte jetzt eigentlich klar sein, und sind genauer in den oberen Werkzeugen beschrieben.



      Verschlüsselung bzw. die Entschlüsselung in ChaCha20Poly1305

      Da nach dem AEAD Prinzip gearbeitet wird, wird für das Verschlüsseln bzw. Entschlüsseln ein AAD (Additional authenticated data) erwartet. Es ist nicht zwingend den mitzuführen (aad == null), in meinem Programm habe ich es jedoch gefixt auf Minimum Länge = 1.

      Ich bin einfach der Ansicht, wenn schon im AEAD-Modus gearbeitet wird, dann sollte auch ein AAD dabei sein. Ich persönlich gebe hier wenn ich kein AAD nutzen will eine Zahl (0 - 255) oder meinen Usernamen mit, und die Sache hat sich dann für mich erledigt.

      Wie funktioniert nun die Ver- bzw. Entschlüsselung in ChaCha20Poly1305 eigentlich?

      Der Plaintext wird in 64er Byte Blöcke eingeteilt. Mit Hilfe der ChaCha20-Instanz kann jederzeit ein 64 Byte interner Key angefordert werden (BlockUpdate), der für die XOR-Verschlüsselung des 64er Plaintext-Block verwendet wird. Sobald die Block-Verschlüsselung vollendet ist, wird der 64 Byte CipherBlock für den Update von Poly1305 verwendet. Wie der Update erfolgt habe ich oben beschrieben.

      Nur so viel, der 64 Byte CipherBlock wird wiederum in 16 Byte Blöcke (4 Runden) eingeteilt, und Durchlauft dann die H = ((H + M) * R) mod P Berechnung.

      Sobald die komplette Verschlüsselung des Plaintext durchzogen ist, wird noch das Tag von Poly1305 (siehe oben) berechnet und das war‘s dann auch schon.

      Weitere Infos gibt dazu die RFC 8439.
      datatracker.ietf.org/doc/html/rfc8439


      XChaCha20 und XChaCha20Poly1305

      Beide Algorithmen basieren auf den Grundalgorithmen, die Professor D.J. Bernstein entwickelt hat. Sie sind aber für die Verwendung modifiziert worden.

      Sie funktionieren zwar genauso wie die Grundalgorithmen, nur wird das „Auffüllen“ des CurrentBlock von ChaCha20 ein bisschen anders bewerkstelligt. Man verspricht sich so eine höhere Verschlüsselungsstärke, bei gleicher CPU- Anweisungsfreundlichkeit und Robustheit.

      Durch das geschickte Füllen des CurrentBlock können Verschlüsselungsstrecken von 2^70 (1 Billion GB) gewährleistet werden.

      Wer sich genauer informieren will, der schaut am besten den Code und die Zusatzspezifikation an

      github.com/exc-jdbi/Chacha20-and-Poly1305
      datatracker.ietf.org/doc/html/draft-irtf-cfrg-xchacha-03



      Geschichtlicher Hintergrund von ChaCha20 und Poly1305

      Professor D.J. Bernstein entwickelte als Nachfolger von Salsa im Jahre 2008 den ChaCha Algorithmus. In Zusammenarbeit mit Google entstand dann auch Poly1305, das auch von Bernstein entwickelt worden ist. (Der Name Poly1305 leitet sich ab von der Primzahl 2^130 – 5)

      Bernstein gab schon damals Empfehlungen heraus die Rundenanzahl von ChaCha auf 20 zu setzen, und gleichzeitig den Poly1305-Algorithmus als MAC (Message Authentication Code) zu verwenden.

      Google ersetzte später (2015) im TLS- und TCP-Bereich den RC4-Algorithmus mit ChaCha20 und Poly1305, und die IETF (Internet Engineering Task Force) standardisierte mit RFC 7465 (später RFC 8439) beide Algorithmen.

      Kurz darauf übernahm auch OpenSSH beide Algos und kappte somit die Abhängigkeit zu OpenSsl. Chrome und FireFox wurden entsprechend für den Einsatz aktualisiert.

      Im Zuge von Google standardisierte die IETF mit RFC 7634 IKE (Internet Key Exchange Protocol) und IPsec, und fast gleichzeitig mit RFC 7905 die TLS (Transport Layer Security).

      Es kamen weitere Einsatzorte hinzu, so implementierte Linux mit nonblocking dev/urandom device 4.8 den ChaCha20-Algorithmus im Randombereich. (OpenBSD hatte den Algo schon damals im Einsatz)

      WireGuard VPN verwendet für den Schlüsselaustausch Curve25519 und für die eigentliche Verschlüsselung ChaCha20 und Poly1305.

      Standardisierung von ChaCha20Poly1305 für den Einsatz in QUIC, eine frühere Entwicklung von Google.


      ChaCha20

      Ist eine symmetrische Stromverschlüsselung basierend auf der pseudozufälligen Funktion von ARX (Add-Rotate-XOR-Operationen).

      Der Kern des Algorithmus nutzt einen Block mit der Länge 16 UI32 (64 Byte) der wie folgt nach RFC 8439 für die Initialisierung zusammengestellt ist:
      • 4 Plätze für die fixe Konstante (tau oder sigma)
      • 8 Plätze für den Key
      • 1 Plätze als Counter
      • 3 Plätze für den Iv (Nonce)
      Der ChaCha20-Algorithmus nimmt diesen Block und erzeugt einen 64 Byte SubKey nach dem ARX-Verfahren, für die XOR-Verschlüsselung mit den in 64er Byte-Blöcke (assimiliert) eingeteilten Plaintext, und zählt den Counter jeweils um 1 hoch. Mehr macht der ChaCha20-Algorithmus nicht.

      Das ARX-Verfahren operiert hier als FSM (endlicher Automat), da durch die Iteration des Counters ein neuer Wert für die Neuinitialisierung und somit auch ein neuer Output berechnet wird.

      Es gibt aber noch die Möglichkeit den Block anders zu gestalten, in dem man einen Iv nimmt mit der Länge 8 Byte statt 12 Byte. Der entsprechende Block sieht dann so aus:
      • 4 Plätze für die fixe Konstante (tau oder sigma)
      • 8 Plätze für den Key
      • 2 Plätze als Counter
      • 2 Plätze für den Iv (Nonce)
      Der Vorteil der zweiten Variante ist, dass der Counter 2-UI32 Plätze besetzt, und somit zusammen bis auf (2^32)^2 => 2^64 inkrementiert werden kann.

      Die Verschlüsselungstrecke ist in der Variante 1 => 2^32 * 64 => 2^38 was 256 GB entspricht. In der Variante 2 ist die Verschlüsselungsstrecke 2^64 * 64 => 2^70 was ca. 1 Billion GB entspricht.




      Poly1305

      Ist ein MAC (Cryptographic Message Authentication Code) und wird verwendet um die Datenintegrität und die Authentizität eines Ciphertext zu überprüfen. Der Algorithmus erzeugt ein 16 Byte Tag (Authentifkator) für jede bedenkliche Länge einer Nachricht (Plaintext).

      Dazu nimmt Poly1305 einen 32 Byte Key als Initialisierer, der auf die Variable R (Multiplikator) und S (Secretkey) verteilt wird.

      Die nach der Initialisierung eingereichte Message (Ciphertext) wird in 16er Byte Blöcke (fix) aufgeteilt, und der Accumulator H wird mit der Primzahl 2^130-5 nach jeder Runde (FSM-Prinzip) nach der Formel

      Quellcode

      1. H = ((H + M) * R) mod P

      berechnet (M = MessageBlock + 1<<(MessageBlock.Length * 8)). Am Schluss wird H noch mit S addiert und so auf das 16-Byte Tag (Modulo 2^128) verteilt und das war’s dann auch schon.




      ChaCha20Poly1305

      Wie es der Name schon sagt, werden ChaCha20 und Poly1305 kombiniert (AEAD). Für die Initialisierung von Poly1305 wird vorgängig ChaCha20 mit dem Key und Iv initialisiert. Der daraus gewonnene Subkey wird halbiert und für die Initialisierung von Poly1305 verwendet.

      Für die Verschlüsselung des Plaintext (64 Byte Blöcke assimiliert) wird weiterhin ChaCha20 verwendet. Gleichzeitig wird in Poly1305 nach jeder Blockverschlüsselung ein BlockUpdate gemacht (siehe Formel H = ((H + M) * R) mod P).

      Nach der kompletten Verschlüsselung des Plaintext erzeugt Poly1305 mit H + S ein 16 Byte Tag, und somit ist auch dieser Algorithmus abgeschlossen. Die Entschlüsselung basiert genau auf dem gleichen Prinzip.


      XChaCha20 und XChaCha20Poly1305

      Sind zwei weitere modifizierte Verfahren basierend auf den von Professor Bernstein entwickelten Algorithmen. Vom Ablauf, funktionieren sie ganz genau so wie ChaCha20 bzw. Poly1305.

      Der einzige Unterschied besteht daraus, dass der Block in XChaCha20 statt mit dem Originalkey mit dem Subkey gefüllt wird. Der Subkey wird vorgängig mit einer ChaCha20-Instanz erzeugt.


      ChaCha20 und Poly1305 auf Github

      Alle 4 Algorithmen sind als einzelne Library konzipiert. Die einzelnen Dll’s sind nicht voneinander abhängig. Die erforderlichen Längen der Parameter die für die Instanzierung benötigt werden können problemlos abgefragt werden. Z.B.

      Quellcode

      1. ChaCha20.KEY_SIZE = 32

      Es ist noch ein UnitTest dabei, der zeigt wie die einzelnen Algorithmen verwendet werden. Sollten trotzdem Fragen entstehen stehe ich euch gerne zur Verfügung.

      Ich hoffe der Beitrag hat euch zu einer kleinen Übersicht verholfen. Um sich den Funktionen und Anwendungen mehr bewusst zu werden, kann ich nur empfehlen die einzelnen Projekte kurz auszuprobieren.


      Mein Link zum SourceCode:
      github.com/exc-jdbi/Chacha20-and-Poly1305
      Dateien

      Dieser Beitrag wurde bereits 21 mal editiert, zuletzt von „exc-jdbi“ ()

      Fragen und Antworten

      Hallo Community

      Es sind doch einige Fragen entstanden, und ich erlaube mir die hier zu veröffentlichen. Ich versuchen die Fragen so gut wie möglich zu beantworten.

      Ich hoffe dass es auch noch viele andere User gibt, die selber Fragen haben oder die interessiert sind auf solche Fragen zu antworten.

      Vielleicht ist ja jemand auch nicht meiner Meinung, und ich würde es begrüssen wenn das bekundet wird.


      Ist ChaCha20 eine Block-Chiffre (Block-Verschlüsselung)?
      ChaCha20 ist ganz klar eine Strom-Chiffre. Daher aus meiner Sicht klar nein, und zwar schon aus mindestens zwei Gründen.

      Die Einteilung(!) des Plaintext in 64er Byte-Blöcke habe ich aus didaktischen Gründen so gezeigt, weil der Subkey 64 Byte lang ist. Und sobald der Subkey für die XOR-Verschlüsselung "verbraucht" ist, wird ein neuer Subkey erzeugt. In dem Sinne werden die Blöcke nicht irgendwie herausgerissen (siehe Diagramm), sondern nur in 64er Byte-Blöcke eingeteilt.

      Der zweite Grund ist, dass der letzte „Block“ im Plaintext nicht zwingend 64 Byte lang sein muss. Hat der Plaintext z.B. eine Länge von 1000 Byte, so ist der letzte „Block“ 40 Byte lang, und es werden auch nur 40 Byte vom Subkey abverlangt.

      Die restlichen Werte werden meistens in einer Block-Chiffre mit Nullen oder Zufallszahlen gefüllt.


      Ich hab gesehen in der ChaCha20Poly1305 wird die Message in 16 Byte Blöcke eingeteilt. Basiert also da die Poly1305 auf einer Block-Chiffre?
      Definitiv nicht. Die Poly1305 ist ein MAC und hat in dem Sinne nichts mit einer Verschlüsselung zu tun.

      Aber ich verstehe den Hintergrund, warum eine solche Annahme gemacht werden kann. Das Problem in ChaCha20Poly1305 ist, das Poly1305 erst einen Update machen kann, nachdem ChaCha20 den „64er Block“ (muss am Schluss nicht 64 Byte lang sein) verschlüsselt hat. Dieser Block muss zwingend für den Update für Poly1305 in 16er Byte Blöcke eingespielt werden, ansonsten der Update nicht richtig funktioniert.

      Da es sich aber hier um Poly1305 handelt und nicht um die ChaCha20-Verschlüsselung, kann also auch keine Rede davon sein, dass es sich um eine Block-Chiffre handelt.


      Was darf man unter ARX verstehen?
      Allgemein betrachtet ist ARX (Add-Rotate-XOR) eine Kombination von Verknüpfungen, die sich im Krypto-Bereich bestens bewährt hat. Wie es der Name schon sagt besteht ARX aus 3 Operationen (A - Modulare Addition, R - Rotation, X - XOR)

      ARX hat den „Status“ als Funktion gesehen einer PRF (Pseudo Random Function). Je nach Eingabe der Parameter und der Erhöhung der Anzahl Runden wird der Rückschluss auf die ursprünglichen Werte schwieriger, bei gleichzeitiger Wahrung der Transformation.

      ARX-Operationen sind sehr beliebt, weil sie für Software wie auch für Hardware einfach zu implementieren sind. Aus dieser Sicht heraus darf man also sagen dass sie sehr CPU-Anweisungsfreundlich, und in den Laufeigenschaften robust und schnell sind.

      Das robust bezieht sich hier auf die Kompaktheit wie auch auf die Fehlerlosigkeit sowie auch auf den konstanten Zeitablauf der Berechnung der einzelnen Operationen. Timing-Attacks können so quasi ausgeschlossen werden.

      ARX wird z.B auch in Speck, XXTEA und BLAKE verwendet.


      Du schreibst ARX kann die Transformation wahren. Ist Chacha20 reversibel?
      Ich finde das ist eine berechtigte Frage, und hat schlussendlich mit der Konzeption zu tun, wie ARX genutzt wird, und was noch speziell dazukommt. Ich konkretisiere jetzt die Frage, und beziehe meine Antwort hauptsächlich auf ChaChaCore, der eigentliche Kernalgoritmus von ChaCha20.

      Je nachdem wie die Verknüpfungen der 3 Operationen zusammengestellt sind, kann ARX reversibel sein. Ist ARX spezifisch auf dem Aspekt einer Permutation ausgelegt, so müsste man eigentlich sagen können, dass eine Umkerfunktion vorhanden sein muss.

      ChaCha20 ist aber schlussendlich ein eigener Algorithmus, und das hat seine Berechtigung. Die QR-Konzeption (QuarterRound) ist bewusst von Professor D. J. Bernstein so gewählt worden, genau so auch die Bitwise-Rotation. Auch macht ChaChaCore am Schluss nochmals eine Addition mit dem Input und diese Vorgehendsweise erschwert meiner Meinung nach ungemein die Möglichkeit einer Reversibilität. Steigt die Rundenzahl, um so mehr Bit-Informationen gehen verloren, und es wird schwieriger wenn sogar unmöglich diese zu rekonstruieren.

      ARX hat den Status einer PRF. Was aber noch viel wichtiger ist, ist die Qualität des Output. Bei einem kryptographisch sicheren Zufallsgenerator wäre mein erster Grundgedanke auch etwas zu konzipieren, dass nicht reversibel ist, wie es bei einem echten Zufallsgenarator der Fall ist. Der innere Zustand eines echten Zufallsgenerator ist nicht bekannt, und es ist nicht möglich die Zahlen voraus zu sagen.

      Da ChaCha20 auf ARX basiert, ist die Konzeption so gewählt worden, dass annähernd ähnliche Bedingungen bestehen wie bei einem echten Zufallsgenerator. D.h. wiederum so, dass der innere Zustand sich nicht mehr reproduzieren lässt. Das erreicht man einerseits, in dem ein geheimer zufällig generierter 32 Byte Key und ein 8/12 Byte Nonce für die Initialisierung des Currentblock wählt, und anderseits ARX so aufbaut, dass die Generierung des Output mathematisch nur in einer Richtung funktioniert (Prinzip Einwegfunktion). Das erschwert schlussendlich auch irgendwelche Rückschlüsse über den Key oder die Nonce zu machen.

      In Bezug auf die Ver- und Entschlüsselung wird ChaChaCore wie oben beschrieben nur in einer Richtung verwendet. ChaChaCore wird also genau so eingesetzt wie ein echter Zufallsgenerator, wo der Output nicht vorhersehbar ist. Und da der Output nicht bekannt ist, reicht eine XOR-Verknüpfung für die Ver- wie auch für die Entschlüsselung.

      Die XOR-Verknüpfung am Schluss ist ein sehr wichtiger zusätzlicher Schritt um eine eventuell mögliche bijektive Korrespondenz Seitens PRF-Output (ChaChaCore), mit dem Input und dem daraus folgendem Gesamt-Output zu verzerren.

      Mir persönlich ist keine mathematische Funktion oder Herleitung bekannt, die eine Reversibilität von ChaCha20Core begründet.


      Ist die Verwendung einer 8 Byte Nonce in ChaCha20 unsicher?
      Die Frage ist nicht einfach so zu beantworten, und kann nur die Praxis beantworten. Aus meiner Sicht ist die Verwendung einer 8 Byte Nonce sicher. Wie es überall in der Kryptographie ist, ist die Länge des Schlüssels wie auch die Länge des Plaintext sehr entscheidend.

      Die Nonce wird ähnlich gehandhabt wie ein Initialisierungsvektor. Und dazu gehört auch noch ein Key.

      Der 16 UI32 CurrentBlock ist eigentlich ein Block der aus 64 Byte besteht. Davon sind 16 Byte für die bekannte Konstante reserviert. Hinzukommt ein geheimer zufälliger 32 Byte Key sowie die im Normalfall auch zufällig generierte 8 Byte Nonce. Im Extremfall, wenn davon ausgegangen wird, dass die Nonce nicht zufällig sein sollte, so hängt die tatsächliche Stärke des Blockes allein auf den garantiert immer geheimen 32 Byte Key.

      Die RPL-Berechnung (Erforderliche Passwortlängenberechnung sagt aus: 1.835 E69 Jahre) vom 32 Byte Key sollte ein wenig Auskunft darüber abgeben, wie sicher das Ganze nun gegen Brute Force wirklich ist. Bestimmt gibt es noch andere Attacks die auch nicht zu unterschätzen sind.

      Im Moment habe ich keine Erfahrungswerte und auch keine Infos darüber wie sicher es nun mit einer 8 Byte Nonce wirklich ist. Ich hoffe aber, dass zukünftig die Praxis, die Institutionen wie auch die Medien viel mehr und genaueres darüber berichten können.


      In der Zusatzspezifikation XChaCha20Poly1305 hält der Autor fest, das es sich um eine Verschlüsselungsstrecke von 2^80 handelt. Ist dir hier ein Fehler unterlaufen?
      Nein ich denke nicht, da ich mich rein auf die physikalische Eigenschaft des Blockes beziehe.

      Der Autor in der Zusatzspezifikation von XChaCha20Poly1305 bezieht sich auf die Kollisionswerte eines sicheren Zufallsgenerators bei einem Grenzwert von 2^-32. Das heisst, so wie ich das jetzt verstanden habe, eine Nonce von 24 Byte besitzt also hier die Verschlüsselungsstrecke von Wurzel(256^24 * 2^-32) = 2^80 = 1.2089E24.

      Ich selber halte mich fest an die Berechnung, die ich hier gezeigt habe, da sie “physikalisch“ durch den Block so gestaltet ist.

      Nachtrag:

      Ich wollte mich mit obigen Antwort neutral ausdrücken. Was der Autor geschrieben und berechnet hat ist nachvollziehbar. Das einzige was noch nicht stattgefunden hat, ist die Abnahme der Spezifikation. Status ist immer noch "Informational". Vielleicht gibt es tatsächlich einen Grund, warum das noch nicht übernommen worden ist.


      Poly1305 ist kein HMAC. Warum wird in deinem UnitTest der Poly1305 für die Continue-Verschlüsselung trotzdem verwendet. Der Key ist immer der gleiche.
      Was auch so korrekt angewendet ist.

      Es stimmt. Poly1305 ist kein PRF, und darf daher auch nicht so verwendet werden wie ein Hmac.

      Das eigentliche Problem ist aber, dass durch die Authentifizierung zweier unterschiedlicher Message mit dem gleichen Key, Authentifikatoren gesammelt werden können die als Vergleichswert später herangezogen werden können, um Rückschlüsse auf den Key zu finden. Auch kann unter blöden Umständen ein Angreifer die Authentifikatoren nutzen um andere Messages mit dem selben Schlüssel zu fälschen.

      Das ist aber nur der Fall, wenn Poly1305 jeweils neu mit dem gleichen Key initialisiert wird, und somit der Accumulator = 0 ist am Anfang. Wie man erkennen kann nutze ich Poly1305 anders, und zwar wird der Poly1305 nicht jeweils neu initialisiert, sondern eben als "per Continue" weiterverwendet. Der Accumulator besitzt den letzten Hashwert, der übrigens nicht eine 128 Bit Zahl sein muss.

      H kann auch viel grösser sein (bis 2^130 - 6 + S), und die Verteilung auf das 16 Byte Tag gilt nicht einfach als Konvertierung zu einer 128 Bit Zahl a 16 Bytes, sondern ist eine Ganzzahlberechnung die 16x durchgeführt wird (Modulo mit 2^128).
      Tag(0) = H mod 256; H \= 256;
      Tag(1) = H mod 256; H \= 256;
      etc.


      Es stellt sich also trotzdem die Frage, ob ein Angreifer den letzten Hashwert nutzen kann, um Poly1305 ab diesen Zustand weiter laufen lassen zu können.
      Was meiner Meinung nach ein sehr schweres Unterfangen wäre, weil dazu trotzdem der Key bekannt sein muss, oder anders gesagt der Multiplikator, der Secretkey und der eigentliche Wert des Accumulator. Anders geht’s nicht.


      Wann kommt XChaCha20Poly1305 zum Einsatz?
      Die modifizierte ChaCha20Poly1305 ist ideal so finde ich, wenn der Key eine Abhandlung aus einem Password und einem Salt ist, also wenn der Key nicht zufällig als 32 Byte Key generiert ist. (Besser wäre zwar auch hier die Verwendung eines zufälligen Key, jedoch in Kombination mit der aad kann auch da an Sicherheit gewonnen werden)

      Auch bietet der XChaCha20Poly1305-Algo eine höhere Verschlüsselungsstärke und ist gemäss der Zusatzspezifikation für Verschlüsselungsstrecken von 2^80 geeignet. Leider ist diese noch nicht übernommen worden, und kann daher wahrscheinlich auch eine gewisse Unsicherheit hervorrufen.

      In den meisten Fällen wird sowieso nie eine solche hohe Verschlüsselungsstrecke genutzt. Wer also XChaCha20Poly1305 als ganz normales Verschlüsselungswerkzeug für ganz normale Verschlüsselungsgrössen nutzen will, sollte mit diesem Werkzeug bestens bedient sein.


      Du schreibst "Die Nonce wird ähnlich gehandhabt wie ein Initialisierungsvektor". Was ist die eigentliche Aufgabe der Nonce?
      Die Nonce hat im Sinne der Anwendung mindestens 2 Aufgaben.

      Mit Hilfe der Nonce wird sichergestellt, dass mit dem gleichen Plaintext nicht der gleiche Ciphertext erzeugt wird (siehe Known-Plaintext-Attack und Birthday Problem). Daher ist es auch wichtig, dass die Nonce bei jeder Neuinstanzierung bzw. Neuinitialisierung auch neu und zufällig generiert wird (zufällige Key-Nonce-Kombination).

      Die 2. Aufgabe ist die Erhöhung der Verschlüsselungsstärke und somit auch die Erhöhung der Verschlüsselungsstrecke. Um so länger die Nonce sein darf, um so wirkungsvoller sind die oben erwähnten Erhöhungen. In dem Sinne darf eine Nonce ein Stückweit auch als Verlängerung des Key betrachtet werden.

      Eine Nonce muss prinzipiell richtig angewendet werden (unter anderem Einhaltung der vorgegebene Längen). Wie man im Programm-Code erkennen kann, darf die gleiche Nonce auch für "per Continue" verwendet werden, da der Counter im Block immer weiter gezählt wird, und das ARX-Verfahren dafür sorgt, das ein sicherer Subkey generiert wird.


      Müssen Antworten nachkontrolliert werden? Zweitmeinungen?
      Ein Thema das besonders in diesem Bereich sehr wichtig ist.

      Die Meinungsfreiheit hier in Europa gewährleistet das Recht auf freie Meinungsäusserung in Wort, Schrift und Bild in der Öffentlichkeit. Dies umfasst jedoch nicht die Äusserung von nachprüfbaren Unwahrheiten.

      Der Zweck meiner Beiträge die ich hier veröffentliche, sollen reinen informativen Charakter haben. Als Autor ist es mein Wunsch das Geschriebene mit den vorhanden Bezugsquellen abzugleichen (RFC XXXX, vb-paradise.de, github.com etc.).

      Trotzdem kann es wahrscheinlich vorkommen, das Textabschnitte unabsichtlich so geschrieben sind, dass sie anders interpretiert werden können. Es ist daher wichtig, dass der aufmerksame Leser bei Unklarheiten selber Konkretisierungen anbringt und die erwähnten Bezugsquellen gründlich nachliest, sofern das erforderlich ist.

      Zweitmeinungen sind immer gut, um die eigenen Erkenntnisse als Verständnis zu diesem doch sehr komplexen Thema abzusichern.

      Dieser Beitrag wurde bereits 23 mal editiert, zuletzt von „exc-jdbi“ ()

    Facebook
    Telefonspende