Crypto-Challenge #1: Kryptoanalyse Magenta

[Elderan]

Ich habe vor hier eine kleine Crypto-Challenge zu veranstalten und hoffe das einige freudig dran teilnehmen.

Es geht in der Crypto-Challenge um die Kryptoanalyse von Magenta, welcher von der Deutschen Telekom als Algorithmus zum Advanced Encryption Standard eingereicht wurde.
Magenta ist eine Feistelchiffre mit einer Blockgröße von 128 Bit und einer Keylänge von 128 bis 256 Bit, wobei wir uns nur die 128 Bit Variante betrachten.


Dann wollen wir mal unsere Chancen zur Kryptoanalyse abschätzen, dazu zuerst ein Paper welches Magenta weiter beschreibt: The MAGENTA Block Cipher Algorithm (Paper muss nicht gelesen werden)

To date, no significant security weaknesses are known for the MAGENTA block cipher algorithm. It seems to have sufficient avalanche properties, no statistical weaknesses have been found, and attacks based on differential and linear cryptanalysis do not offer any signifficant improvement over a brute force attack.

Hört sich erstmal schlecht, allerdings hier kommt die gute Nachricht:
Innerhalb von 20 Minuten, noch während der Präsentation von Magenta, wurde von Eli Biham, Alex Biryukov, Niels Ferguson, Lars Knudsen, Bruce Schneier und Adi Shamir eine eklatante Schwäche in Magenta gefunden, womit der Algorithmus als gebrochen gilt.
(Am Rande: Magenta war außerdem noch einer der langsamsten Algorithmen die eingereicht wurden).


Regeln ? Wichtig!
Es hat keinen Sinn sich bereits fertige Kryptoanalysen von Magenta anzugucken. Hat man diese einmal durchgelesen, gibt es nicht viel mehr zu entdecken womit die Challengen für einen dann beendet wäre.
Auch wenn das 1. Zitat wenig Mut macht, die Kryptoanalyse ist leichter als erwartet und sollte auch von fortgeschrittenen Anfängern zu meistern sein. Irgendwelche abgefahrenen Kentnisse in differentielle/lineare Kryptoanalyse sind nicht notwendig. Grundkenntnisse in Kryptographie sollten ausrecihen.
Ich werde ausreichend Tipps ins spoiler-Tags geben, wobei man sich diese erst angucken sollte, wenn man wirklich nicht mehr weiter weiß.
Sollte Ihr eine Lösung gefunden haben, dann verwendet bitte ebenso Spoiler-Tags.

Reverse Engineering oder ähnliche Verfahren sind nicht erlaubt, allerdings sind alle Angriffstechniken aus der Kryptographie erlaubt.


Woraus besteht die Challenge?
Diese Challenge besteht aus mehreren Teilen, einmal soll man einen Angriff gegen Magenta beschreiben, der natürlich deutlich schneller als Brute Force (2^128) ist.

Dann gibt es auch noch einen Praxis-Teil, ich habe eine reduzierten Magenta-Version geschrieben, die für den selben Angriff anfällig ist wie die orginal Magenta Version.
Diese Version arbeitet mit einer Blockgröße von 64 Bit sowie einer Key Länge von 64 Bit. Ein Brute Force Angriff wäre möglich (2^64 Schritte), aber dennoch zu aufwendig.

Für diesen Algorithmus soll man den Angriff, der auch gegen orginal Magenta klappt, implementieren. Dazu ist im Anhang eine DLL (Magenta64.dll), die einen geheimen Schlüssel enthält und nur ver- und entschlüsseln mit diesem geheimen Key anbietet.
Das Auslesen durch Reverse Engineering ist natürlich nicht erlaubt. Ziel ist es also, mit diesem Angriff den Key in Erfahrung zu bringen.



Zuerst nocheinmal klären, wann ein Algorithmus als gebrochen gilt:

WHAT DOES IT MEAN TO "BREAK" A CIPHER?
Breaking a cipher doesn't necessarily mean finding a practical way for an eavesdropper to recover the plaintext from just the ciphertext.
In academic cryptography, the rules are relaxed considerably. Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute-force. Never mind that brute-force might require 2^128 encryptions; an
attack requiring 2^110 encryptions would be considered a break. Breaks might also
require unrealistic amounts of known or chosen plaintext - 2^56 blocks - or unrealistic
amounts of storage: 2^80. Simply put, a break can just be a "certifcational
weakness": evidence that the cipher does not perform as advertised.
Successful cryptanalysis might mean showing a break against a reduced-round
variant of the cipher - 8-round DES versus the full 16-round DES, for example -
or a simplified variant of the cipher. Most breaks start out as cryptanalysis
against reduced-round variants, and are eventually (maybe years later) extended
to the full cipher. In fact, a break on a reduced-round version of a cipher is often
a publishable result.

Self-Study Course in Block Cipher Cryptanalysis

Ihr werdet es vermutlich nicht schaffen, nur aus dem Geheimtext den Key zurückzugewinnen, dennoch ist der Angriff so verheerend, dass man Magenta nicht guten gewissens verwenden kann.
Versucht also nicht irgendwie den Geheimtext statistisch zu untersuchen, sondern verwendet andere Angriffstechniken



1. Teil
(Erst den 1. Teil lesen, dann aber besser mit dem 2. Teil anfangen)
Finde einen Angriff gegen Magenta, welcher deutlich schneller als Brute Force (2^128 ) ist. Welche Voraussetzungen werden benötigt, um diesen Angriff durchzuführen? Welche Komplexilität wird für diesen Angriff benötigt? Von welchen Parametern hängt die Komplexilität ab und mit was für einem Aufwand kann man im aller schlimmsten Fall rechnen? Ist dieser Worst-case realistisch (mit Begründung)?
Kann man aus diesem Angriff evt. noch andere Angriffsarten ableiten? Wenn ja, wie ist deren Aufwand?

Wenn ihr noch Lust habt: Nenne ein nachvollziehbares (also aus der Realität) Beispiel, bei dem dieser Angriff schlimme Folgen haben können.


Magenta ist wie folgt aufgebaut: Wie gewohnt bei Feistelchiffren wird der 128 Bit Klartextblock in einen Linken und einen Rechten teil aufgespalten.

Der 128 Bit-Schlüssel wird ebenso in zwei Teile aufgeteilt, in k1 und k2. Der Schlüssel k1 wird für die ersten beiden Rundenfunktionen und die letzten beiden Rundenfunktionen verwendet, k2 kommt in den beiden mittleren Rundenfunktionen zum Einsatz, als Grafik sieht dies wie folgt aus:

Dabei ist F die Rundenfunktion, dieses Kreuz im dem Kreis bedeutet XOR.

Soviel schon gesagt, dieser entsprechende Angriff funktioniert ohne nähere Details der Rundenfunktion F. Deswegen solltet ihr auch, wenn ihr die modifizierten Magenta Versionen (Magenta64 und Magenta16) betrachten, nicht versuchen irgendwelche Eigenschaften der Rundenfunktion F auszunutzen, sondern das Problem liegt in der Struktur des Magenta-Algorithmus. Als Rundenfunktion könnte auch z.B. ein sicherer Algorithmus wie Rijndael zum Einsatz kommen.

2. Teil
Schreibe ein Programm, welches diesen Angriff auf die Magenta64 Version anwendet. Ermittel damit den geheimen Schlüssel aus der Magenta64.dll (Reverse Engineering nicht erlaubt).
Ermittle den benötigten Aufwand.


------------------------------------------------------------------

Magenta64
Magenta64 hat eine Feistelstruktur mit einer Block- und Keygröße von 64 Bit.
Dabei wird wie beim echten Magenta der Key in zwei Teile mit je 32 Bit aufgeteilt, ebenso der Klartext besteht aus einer linken und einer rechten Hälfte, mit je 32 Bit. Der Ablauf für die Verschlüsselung ist identisch mit der Grafik oben. Für die Entschlüsselung wird die Struktur einfach rückwärts durchlaufen, also man beginnt unten, wobei die Entschlüsselung für den gesuchten Angriff unerheblich ist.


Ich veröffentliche Implementierungen in C und C#. Es ist sehr empfehlenswert eine IDE mit sehr guten Debugger zu verwenden, mit dem man sich die einzelnen Zwischenergebnisse angucken kann.
Die Portierung des Algorithmus in andere Sprachen (z.B. Java) sollte nicht das Problem darstellen, sofern jmd. es schon gemacht hat, kann er es hier gerne veröffentlichen, so dass ich es einbinden kann. Ein Testvektor kann im Anhang gefunden werden.

Die Rundenfunktion F sieht wie folgt aus:

Spoiler: C Implementierung

// k = Key
unsigned int F(unsigned int input, unsigned int k) {
              
            //Rotate left 3:
            input = input << 3 | input >> 29;

            //Input + shifted Const           
            input += 0x7A8E7B86U << (int)( (input ^ k) & 7) | (0x7A8E7B86U << (int)(32 - ( (input ^ k) & 7)));

            //Rotate left 4:
            input = input << 4 | input >> 28;            
            
            //Input XOR Key
            input ^= k;
            
            //Input + shifted Const
            int leftShift = (int)( (unsigned int)((input ^ k) & 0xF0000000) >> 28);
            input += 0xCF9C5DFC << leftShift | 0xCF9C5DFC >> (32-leftShift);           
            
            return input;
        }

Spoiler: C# Implementierung

//k = Key
public UInt32 F(UInt32 input, UInt32 k)
        {
            //Rotate Left 3:
            input = input << 3 | input >> 29;

            //Input + shifted Const           
            input += 0x7A8E7B86U << (int)( (input ^ k) & 7) | (0x7A8E7B86U << (int)(32 - ( (input ^ k) & 7)));

            //Rotate Left 4:
            input = input << 4 | input >> 28;            
            
            //Input XOR Key
            input ^= k;
            
            //Input + shifted Const
            int leftShift = (int)( (uint)((input ^ k) & 0xF0000000) >> 28);
            input += 0xCF9C5DFC << leftShift | 0xCF9C5DFC >> (32-leftShift);           
            
            return input;
        }

Komplett implementiert sieht es wie folgt aus, wobei die Entschlüsselung einfach nur die Runden von unten nach oben durchläuft:

Spoiler: Magenta64 C-Implementierung

// k = Key
unsigned int F(unsigned int input, unsigned int k) {
              
            //Rotate left 3:
            input = input << 3 | input >> 29;

            //Input + shifted Const           
            input += 0x7A8E7B86U << (int)( (input ^ k) & 7) | (0x7A8E7B86U << (int)(32 - ( (input ^ k) & 7)));

            //Rotate left 4:
            input = input << 4 | input >> 28;            
            
            //Input XOR Key
            input ^= k;
            
            //Input + shifted Const
            int leftShift = (int)( (unsigned int)((input ^ k) & 0xF0000000) >> 28);
            input += 0xCF9C5DFC << leftShift | 0xCF9C5DFC >> (32-leftShift);           
            
            return input;
        }
//Verschluesselt left und right mit den Keys k1 und k2, Ausgabe wird in leftOut/rightOut abgelegt
void Encrypt(unsigned int left, unsigned int right, unsigned int k1, unsigned int k2, unsigned int* leftOut, unsigned int* rightOut)
        {
            //1. Round
            left ^= F(right, k1);

            //2. Round
            right ^= F(left, k1);

            //3. Round
            left ^= F(right, k2);

            //4. Round
            right ^= F(left, k2);

            //5. Round
            left ^= F(right, k1);

            //6. Round
            right ^= F(left, k1);            
            
            *leftOut = left;
            *rightOut = right;         

        }
        
        
void Decrypt(unsigned int  left, unsigned int  right, unsigned int  k1, unsigned int  k2 , unsigned int* leftOut, unsigned int* rightOut)
        {
            //6. Round
            right ^= F(left, k1);

            //5. Round
            left ^= F(right, k1);

            //4. Round
            right ^= F(left, k2);

            //3. Round
            left ^= F(right, k2);

            //2. Round
            right ^= F(left, k1);

            //1. Round
            left ^= F(right, k1);

            *leftOut = left;
            *rightOut = right;         

        }


//Beispiel wie man diese Implementierung verwendet
int main() {
     unsigned int left=0x11223344, right=0xAABBCCDD;
     unsigned int k1= 0x01234567, k2=0x89ABCDEF;
     Encrypt(left, right, k1, k2 , &left, &right);
     
     printf("Encrypted: %X %X \n",left, right);
     
     Decrypt(left, right,  k1, k2, &left, &right);
     printf("Decrypted: %x %x",left, right);
     getchar();     
     }

Spoiler: Magenta64 C# Implementierung

class Magenta64
    {
        private UInt32 k1, k2;

        public Magenta64()
            : this(0, 0)
        {

        }

        public Magenta64(UInt32 k1, UInt32 k2)
        {
            this.k1 = k1;
            this.k2 = k2;
        }

        //Die Funktion F
        public virtual UInt32 F(UInt32 input, UInt32 k)
        {
            //Rotate Left 3:
            input = input << 3 | input >> 29;

            //Input + shifted Const           
            input += 0x7A8E7B86U << (int)( (input ^ k) & 7) | (0x7A8E7B86U << (int)(32 - ( (input ^ k) & 7)));

            //Rotate Left 4:
            input = input << 4 | input >> 28;            
            
            //Input XOR Key
            input ^= k;
            
            //Input + shifted Const
            int leftShift = (int)( (uint)((input ^ k) & 0xF0000000) >> 28);
            input += 0xCF9C5DFC << leftShift | 0xCF9C5DFC >> (32-leftShift);           
            
            return input;
        }


        //Encrypt mit this.k1 und this.k2
        public virtual UInt32[] Encrypt(UInt32 left, UInt32 right)
        {
            return Encrypt(left, right, k1, k2);
        }


        public UInt32[] Encrypt(UInt32 left, UInt32 right, UInt32 k1, UInt32 k2)
        {
            //1. Round
            left ^= F(right, k1);

            //2. Round
            right ^= F(left, k1);

            //3. Round
            left ^= F(right, k2);

            //4. Round
            right ^= F(left, k2);

            //5. Round
            left ^= F(right, k1);

            //6. Round
            right ^= F(left, k1);


            return new UInt32[] { left, right };

        }

        public virtual UInt32[] Decrypt(UInt32 left, UInt32 right)
        {
            return Decrypt(left, right, k1, k2);
        }


        public UInt32[] Decrypt(UInt32 left, UInt32 right, UInt32 k1, UInt32 k2)
        {
            //6. Round
            right ^= F(left, k1);

            //5. Round
            left ^= F(right, k1);

            //4. Round
            right ^= F(left, k2);

            //3. Round
            left ^= F(right, k2);

            //2. Round
            right ^= F(left, k1);

            //1. Round
            left ^= F(right, k1);

            return new UInt32[] { left, right };
        } 
   }

In Wie programmiere ich einen Algorithmus tauchte als erster Test für einen Algorithmus die statistischen Eigenschaften von diesem auf.
Wie man dem Paper über Magenta entnehmen kann, soll Magenta wohl relativ gute statistische Eigenschaften besitzen. Auch für Magenta64 habe ich ein paar statistische Eigenschaften überprüft, welche alle absolviert wurden.
Dabei wurde z.B. unter einem festen Key (z.B. 000...000) eine aufsteigende Nummer verschlüsselt und mittels der FIPS-PUB-140-1-Testbatterie auf zufälligkeit getestet. Magenta64 hat diese Test soweit soweit bestanden, dennoch kann hier von keinem sicheren Algorithmus gesprochen werden.

Ihr könnt Magenta64 mit dem gleichen Angriff wie orginal Magenta knacken, andere Analysen oder knackversuche sind natürlich herzlich willkommen und vermutlich auch durchaus möglich, da Magenta64 nur ein paar wenige statistische Tests absolviert hat und nicht speziell gegen z.B. lineare/differentielle Kryptoanalyse abgehärtet wurde.



Tipps
Da es vermutlich für die meisten unmöglich ist, von selbst ein Angriffsszenario gegen Magenta zu finden, kommen hier die Tipps.
Dabei sind einige Tipps in spoiler-Tags versteckt, und diese solltet ihr erst lesen, wenn ihr wirklich nicht mehr weiter wisst.
Das finden eines Angriffes ist nicht in 5 Minuten erledigt und man sollte schon sich einige Gedanken machen, bevor man evt. den nächsten Tipp liest.


Wenn man einen Algorithmus kryptoanalysiert, fängt man überlicherweise mit einer reduzierten Variante an, hierfür habe ich zwei Sachen vorbreitet. Direkt zu versuchen Magenta64 zu knacken ist nicht vielversprechend.


Zuerst eine reduzierte Version, dabei fehlen die Runden 5 und 6

Gegen diesen Variante gibt es zwei mögliche Angriffe, wobei die eine Angriffsform relativ offensichtlich ist, diese bringt uns aber nicht richtig weiter.

Spoiler: Sofern ihr einen Angriff gefunden habt oder überhaupt nicht weiterkommt, Spoiler öffnen

Gegen die reduzierte Variante ist ein Meet-in-the-middle attack möglich, welcher bei einer Keygröße von 128 Bit nur 2^65 Rechenschritte benötigen würde.

Dieser Angriff hilft aber nicht unbedingt weiter. Viel mehr sollte man die Besonderheit der Strucktur verwenden.

Spoiler: Sofern ihr nicht weiter kommt, Spoiler lesen

Schaut mal bei der Magenta16 Version wie die Zwischenergebnisse während der Verschlüsselung aussehen. Wichtig ist festzustellen, von was die einzelnen Zwischenschritte abhängen
Es ist empfehlenswert die Magenta16-Variante mal schrittweise durchzugehen und die einzelnen Ergebnisse (natürlich im Hex-Format) entsprechend in das Diagramm einzutragen. Natürlich kann man hier auch wieder mit der reduzierten Variante anfangen. Kann man evt. bestimmte Teile des Schlüssels leicht überprüfen?

Weil es außerdem recht unhandlich ist, mit so großen Blockgrößen zu arbeiten, gibt es noch die Magenta16 Variante, gleiche Struktur wie oben, allerdings mit einer Block- und Keygröße von 16 Bit, also 2 mal 8 Bit. Auch die Rundenfunktion wurde etwas reduziert, ändert aber nichts am Angriff.

Spoiler: Magenta16 C-Implementierung

//Magenta-Variante mit Block/Keygröße von 2 mal 8 Bit.

#include<stdio.h>
 unsigned char F(unsigned char input, unsigned char k) {
              
            //Input + Const
            input += 0x5C;

            //Rotate Left 2:
            input = (unsigned char)(((unsigned char)input << 2) | ((unsigned char)input >> 6));

            //Input XOR Key
            input ^= k;

            //Input + Const
            input += 0xA4;

            return input;
        }


  void Encrypt(unsigned char left, unsigned char right, unsigned char k1, unsigned char k2, unsigned char* leftOut, unsigned char* rightOut)
        {
            //1. Round
            left ^= F(right, k1);

            //2. Round
            right ^= F(left, k1);

            //3. Round
            left ^= F(right, k2);

            //4. Round
            right ^= F(left, k2);

            //Fuer die reduzierte Version die naechsten beiden Zeilen einfach auskommentieren
            //5. Round
            left ^= F(right, k1);

            //6. Round
            right ^= F(left, k1);            
            
            *leftOut = left;
            *rightOut = right;         

        }
        
        
void Decrypt(unsigned char  left, unsigned char  right, unsigned char  k1, unsigned char  k2 , unsigned char* leftOut, unsigned char* rightOut)
        {

            // Wenn die reduzierte Version benutzt wird, 6. und 5. Runde auskommentieren
            //6. Round
            right ^= F(left, k1);

            //5. Round
            left ^= F(right, k1);

            //4. Round
            right ^= F(left, k2);

            //3. Round
            left ^= F(right, k2);

            //2. Round
            right ^= F(left, k1);

            //1. Round
            left ^= F(right, k1);

            *leftOut = left;
            *rightOut = right;         

        }
        
        
//Moegliche Verwendung
int main() {
     unsigned char left = 0x11, right = 0xAA;
     unsigned char k1 = 0x01, k2 = 0x89;
     Encrypt(left, right, k1, k2, &left, &right);
     
     printf("Encrypted: %X %X \n",left, right);
     
     Decrypt(left, right, k1, k2, &left, &right);
     printf("Decrypted: %x %x",left, right);
     getchar();
     
     }

Spoiler: Magenta16 C#-Implentierung

//Magenta-Variante mit Block/Keygröße von 2 mal 8 Bit.
//In C# ist byte ohne Vorzeichen unsigned
class Magenta16
    {
        private byte k1, k2;

        public Magenta16() : this(0,0)
        {

        }

        public Magenta16(byte k1, byte k2)
        {
            this.k1 = k1;
            this.k2 = k2;
        }

        //Reduzierte Rundenfunktion, aendert nichts am Angriff
        public byte F(byte input, byte k)
        {
            //Input + Const
            input += 0x5C;

            //Rotate Left 2:
            input = (byte)(((byte)input << 2) | ((byte)input >> 6));

            //Input XOR Key
            input ^= k;

            //Input + Const
            input += 0xA4;

            return input;
        }


        public byte[] Encrypt(byte left, byte right)
        {
            return Encrypt(left, right, k1, k2);
        }


        public byte[] Encrypt(byte left, byte right, byte k1, byte k2)
        {
            //1. Round
            left ^= F(right, k1);

            //2. Round
            right ^= F(left, k1);

            //3. Round
            left ^= F(right, k2);

            //4. Round
            right ^= F(left, k2);

            //Fuer die reduzierte Version die naechsten beiden Zeilen einfach auskommentieren
            //5. Round
            left ^= F(right, k1);

            //6. Round
            right ^= F(left, k1);


            return new byte[] { left, right };

        }

        public byte[] Decrypt(byte left, byte right)
        {
            return Decrypt(left, right, k1, k2);
        }


        public byte[] Decrypt(byte left, byte right, byte k1, byte k2)
        {
            //Fuer die reduzierte Variante die Runde 6. und 5. auskommentieren
            //6. Round
            right ^= F(left, k1);

            //5. Round
            left ^= F(right, k1);

            //4. Round
            right ^= F(left, k2);

            //3. Round
            left ^= F(right, k2);

            //2. Round
            right ^= F(left, k1);

            //1. Round
            left ^= F(right, k1);

            return new byte[] { left, right };
        }
    }

Magenta64.dll
Die Magenta64.dll ist eine in C geschriebene Implementierung der Magenta64 Version, allerdings mit festen Key.
Diese DLL enthält die Funktionen F, Encrypt und Decrypt und zwar mit folgenden Interface:

unsigned int F(unsigned int input, unsigned int k);

void Encrypt(unsigned int left, unsigned int right, unsigned int* leftOut, unsigned int* rightOut);

void Decrypt(unsigned int  left, unsigned int  right, unsigned int* leftOut, unsigned int* rightOut);

Auf diese DLL kann man in C# z.B. wie folgt zugreifen:

Spoiler: Zugriff auf Magenta64.dll in C#

class Magenta64Dll : Magenta64
    {

        [DllImport("Magenta64.dll", EntryPoint="Encrypt")]
        public static extern void Encrypt_dll(UInt32 left, UInt32 right, out UInt32 leftOut, out UInt32 rightOut);

        [DllImport("Magenta64.dll", EntryPoint = "Decrypt")]
        public static extern void Decrypt_dll(UInt32 left, UInt32 right, out UInt32 leftOut, out UInt32 rightOut);

        //Der Zugriff auf die enthaltene Funktion F ist moeglich,
        //aber unnoetig und dauert zu lange
      

        public override uint[] Encrypt(uint left, uint right)
        {
            UInt32[] c = new UInt32[2];
            Encrypt_dll(left, right,out c[0],out c[1]);

            return c;
        }

        public override uint[] Decrypt(uint left, uint right)
        {
            UInt32[] c = new UInt32[2];
            Decrypt_dll(left, right, out c[0], out c[1]);

            return c;
        }
    }

Ziel ist es, ohne Reverse Engineering, Speicherdump u.ä., den Key zu extrahieren. Dazu kann man z.B. ein Crack-Programm schreiben, welches aus einem Magenta64-Objekt versucht den Key herrauszufinden.
Die Klasenstruktur kann in C# z.B. so aussehen:

Spoiler: C# Grundgerüst der Crackklasse

class Magenta64Crack
    {

        public UInt64 steps = 0;
       
        public Magenta64Crack()
        {
        }

        public UInt32[] Crack(Magenta64 mag)
        {  
               //Finde den Key für mag heraus
              return new Uint32[] {k1, k2}; //Return Key
              }
         }

Um eventuelle Probleme mit der .dll unter Linux zu vermeiden ihabe ich noch die Object-Datei Magenta64_dll.o angehängt.
Ich hoffe diese kann soweit Problemlos verwendet werden (es wurde gcc von Dev-C++ zur Überstzung verwendet).


Ansonsten wünsche ich euch viel Spaß und gutes gelingen. Für Fragen und Anmerkungen bin ich immer offen und hoffe dass dieses Challenge soweit lösbar ist.

 

[Harry Boeck]

So, auf die Gefahr hin, was falsches zu behaupten...(das ist nun mal Element von Arbeitshypothesen...)

P.S. (12 Stunden später...): Na ja, die hier angedeutete Idee mag vielleicht mal ans Ziel führen, ist aber so wie sie hier steht noch Stuß... (sorry, war wohl doch schon etwas spät gestern Nacht...)

-> Also: Darf ruhig reingeguckt werden. Es ist NICHT die Lösung. Ich hatte das wichtigste Ziel beim Auflösen eines Gleichungssystems übersehen (Variablen zu eleminieren), und daher ist das hier wirklich bisher nur als vage Idee zu betrachten...

Spoiler: Überlegungen

Weil das Verfahren so wenige Runden anwendet, könnte es Ziel sein, die Zwischenzustände, die mit den bekannten äußeren Zuständen nur xor-verknüpft sind, durch Gleichungsumstellung zu eleminieren. Irgendwie hatte ich mir das schon mal hergeleitet...

Mit der 4-stufigen Variante sollte es gehen. Die 6-stufige Variante könnte sich dadurch "öffnen" lassen, daß vorn und hinten derselbe Schlüssel verwendet wird.

Damit könnte dann etwas hinzukriegen sein wie y1 = f(k1, x1) und y2 = f(k2, x2), wobei sich die x und y aus irgendwelchen Verknüpfungen der von außen bekannten Werte L, R, X und Y ergeben müßten. Die Komplexität der Schlüsselermittlung für den 128-bit-Algorithmus wäre dann mit 64 bit anzusetzen, was heutzutage nicht mehr unmöglich knackbar ist.

Ich versuche es mal in dieser Richtung... (wird demnächst aktualisiert...)

----

Hmmm, ja also, für den 4-stufigen Algo sieht das in einer der möglichen Umstellungen so aus:

F(k1, L2 * F(k2, F(k2, L2) * R2)) = R * F(k2, L2) * R2

Da wir L, R, L2 (alias X), R2 (alias Y) konstant vorgeben alias kennen dürfen und auch einer der beiden Schlüssel (namentlich hier k2) beliebig, aber konstant ansetzen dürfen, läßt sich der verbleibende Schlüssel k1 (der nur noch an einer Stelle der Gleichung existiert) durch Brute Force mit der Hälfte der Bits ermitteln.
Das ganze geht natürlich noch äquivalent zur anderen Seite umzustellen.

Nun zur Variante mit den 6 Stufen... (das dürfte das eigentlich interessante werden...)

----

Ähhh...ja: trivial: (sorry, daß das Überlegen so lange gedauert hat...)
Der k1 wird einfach beliebig, aber konstant angesetzt, die äußeren, beliebigen, aber konstanten Daten L und R führen damit auf immer noch konstante und bekannte L1 und R1, und von da an ist das ganze Gerät exakt nichts anderes als der vierstufige Apparat, womit sich nach obiger Gleichungsumstellung der k2 brute forcen läßt.

Die Erstellung eines Demo-Programms erscheint jetzt aber gar nicht mehr so reizvoll...

----

Ach ja, hatte nochwas zu ermitteln vergessen: Nachdem der k2 brute forced wurde, macht man dasselbe für den k1. Allerdings könnte die Gleichungsumstellung für den k1 in der 6-stufigen Variante (die dann eine bekannte Umsetzung von L1/R1 auf L2/R2 in der Mitte hat) noch etwas abenteuerlich werden...

----

Nein, Blödsinn: Daran ist überhaupt nichts abenteuerliches: Wir KENNEN zu diesem Zeitpunkt NEBEN allen 4 äußeren Datenpaketen den Schlüssel k2 und haben nur noch den Schlüssel k1 als Variable im System übrig. Wir LASSEN die Anordnung einfach wie sie ist und brute forcen den k1 einfach von einem GANZ ÄUSSEREN Standpunkt.

----

Wer hat Lust auf ein Demo-Progrämmchen?

 

[Elderan]

Hallo,
da es noch keine Lösung gibt, dann hier mal ein paar weiterer Tipps, von 'bischen hilfreich' bis 'sehr hilfreich':

Spoiler: Art der Attacke

Wer hätte es erwartet, die leichteste Attacke ist ein choosen Plaintext attack. D.h., ihr wählt einen Klartext und lasst diesen verschlüsseln und schaut was dabei rauskommt.

Spoiler: Wie man üblicherweise versucht Algorithmen zu knacken

In den meisten Fällen ist es nicht möglich, direkt den gesamten Key zu knacken, sondern statt dessen hat man eine Möglichkeit gefunden, einzelne Teile des Keys auf seine Richtigkeit zu überprüfen.
Bei einer polyalphabetischen Substitution ist es genauso, da knackt man nicht sofort z.B. einen 8 stelligen Key, sondern knackt jedes Zeichen einzeln vom Key.

Sagen wir hätten solch ein System:

Hier könnte man die einzelnen Schlüssel K1 bis K8 ja unabhängig voneinander überprüfen und z.B. per Brute Force knacken (sofern die Verschlüsselungsschicht sicher ist).
Wäre jeder Key 1 Byte, dann wäre der aufwand nicht 2^64 sondern nur 8*2^8.


Bei der Differentiellen/Linearen Kryptoanalyse macht man dies genauso, über diese beiden Angriffsverfahren lässt sich i.d.R. der letzte Rundenschlüssel knacken.

Auch hier empfiehlt es sich zu versuchen, ob man nicht einzelne Teile des Keys getrennt überprüfen kann.
Da dies ja für allgemeine Rundenfunktionen F funktionieren soll, bleibt nich mehr soviel über, was man seperat überprüfen kann

Spoiler: Wie man damit bei der reduzierten Variante vorgehen könnte

Nehme einen Klartext, z.B. 0x00 0x00, und lasse diesen mit der reduzierten Variante (4 Runden) von Magenta16 verschlüsseln und notiere die einzelnen Zwischenwerte im Diagramm.

Gibt es nun eine Möglichkeit, irgendwie zu testen, ob wir für k1 oder k2 den richtigen Wert geraten haben? Bedenke, wir können jeden beliebigen Klartext verschlüsseln.

Spoiler: Zu Harrys Überlegungen

In der Tat liegt es an den wenigen Runden, die Formelumstellung erachte ich als nur bedingt hilfreich und führt nicht unbedingt ans Ziel.

Sinnvoller ist es, wirklich mal mit einen Klartext das Szenario durchzuspielen (also im Diagramm eintragen) und versuchen herrauszufinden, ob und wie man k1 oder k2 erraten kann.
Wenn wir k1 oder k2 sperat per brute force knacken könnten, wäre der Aufwand nicht mehr 2^128 sondern nur noch 2*2^64.

So ich hoffe das hilft euch weiter.

 

[YBF]

meine Überlegungen...

Ich poste mal meine Überlegungen:
Nicht angucken wenn, man es selber lösen will;
ist zwar keine Lösung, aber ich glaube, dass ich nah dran bin.

Spoiler: Überlegungen

Als erstes habe ich mir in dem Diagramm für Magenta die Punkte eingezeichnet, die ich ohne Wissen von K2
berechnen kann: ( bei einer Chosen-PLaintext-Attacke )

Es gilt also:
A = L xor F(R,k1)
B = R xor F(A,k1)
C = A xor D
D = X xor F(E,k1)
E = Y xor F(X,k1)

Jetzt muss ich nur noch eine Möglichkeit finden, zu Überprüfen, ob ein geratenes k1 richtig ist;
und da hapert es noch bei mir.

Meine Idee:

Wenn k1 richtig ist, dann müsste man, wenn man von beliebigen A und B
L2 und R2 berechnet, dieses dann Verschlüsselt und dann daraus C2 berechnet,
C2 gleich dem ursprünglichem C sein.

Doch mein C-Code ( http://pastebin.com/m41238971 ) gibt mir folgendes aus:

a1: C160406B
b1: 7AD28D1E
e1: 2E5EADE4
d1: 6C0800C9
c1: AD6840A2
a2: C160406B
b2: ABCDEFA
m2[RIGHT]: DAD59F39
m2[LEFT]: 61CC6F2C
x2[LEFT]: 9AE00724
x2[RIGHT]: 314b7761
e2: C160406B
d2: C160406B
C1: ad6840a2, C2: cf6c207e, K1: 1234567

( mit check_k1(0x01234567)  und k1=0x01234567, k2=0x89ABCDEF )

Fehler bei den Berechnungen habe ich keine gefunden.
( Es wundert mich aber, dass e2 und d2 gleich sind. )

Also werde ich wohl noch weiter überlegen müssen.
Falls jemand weiß was ich falsch gemacht oder vergessen habe, wäre ich sehr froh, falls mir dieser Jemand dabie auf die Sprünge helfen kann.

------------------------------------------------------
Edit:
Mir fällt grade auf, dass wenn ich bei Magenta16 B berechne, es immer der gleiche Wert bei rauskommt,
unabhängig von dem gewähltem k1. interessant... und falsch, aufgrund eines Fehlers bei der Berechnung von b1 -.-

mfg YBF

 

[Elderan]

Hallo,

Spoiler: @YBF Überlegungen, ohne zuviel zu verraten

Dein Ansatz sieht schon viel versprechend aus, und in der Tat musst du 'nur noch' überprüfen, ob k1 richtig geraten wurde.

Als kleiner Tipp: Dies lässt sich leicht umkehren, was passiert, wenn k1 nicht richtig geraten wurde?

Ansonsten für die Übersichtlichkeit empfiehlt es sich, auf Magenta16 umzusteigen, so muss man mit nur 1 Byte pro Block kämpfen.

Und wie man k1 überprüfen kann, lässt sich denke ich mal leichter an der reduzierten Variante mit 4 Runden ermitteln.

 

[YBF]

Gelöst^^

Hier meine Lösung für Magenta16 bei einer Chosen-Plaintext-Attacke:

Spoiler: Lösung

Ich habe mal ein bisschen auf Papier gerechnet, und zwar mit der reduzierten Version, als 2 Bit Magenta, und da wie
gesagt wurde die Funktionsweise der Funktion F egal ist, habe ich diese durch eine Exklusiv-Oder Verknüpgung ersetzt:
F(x,k1) = x + k1 (mod 2)

Daraus folgt dann: C = A + K1 + R + K2 (mod 2)

C kann man auch durch A + X darstellen:
A + X = A + K1 + R + K2 (mod 2) | -A
<=> X = K1 + R + K2 (mod 2)

Und aus der Tatsache, dass A wegfällt, habe ich folgende Behauptung aufgestellt:
Wenn man aus A2 und B2, für die gilt A2 != A1 und B2 = B1, L2 und R2
berechnet, aus diesen dann C2 berechnet, dann gilt, falls K1 richtig geraten wurde C1 = C2.

Kurze Überprüfung der Richtigkeit mit einem C-Programm:

Spoiler: chcek_k1

// richtiger K1 = 0x01

// richtiger K2 = 0x89;

#define LEFT 0
#define RIGHT 1
void check_k1(unsigned char k1)
{
	unsigned char c1, c2, a1, a2, b1, b2;
	unsigned char x1[2];
	unsigned char x2[2];
	unsigned char m1[2] = { 0x00, 0xFF } ;
	unsigned char m2[2];

	// vorbereiten
	Encrypt( m1[LEFT] , m1[RIGHT] , &x1[LEFT] , &x1[RIGHT] );
	


	// a1 und b2 berechnen:
	a1 = m1[LEFT] ^ F(m1[RIGHT],k1);
	b1 = m1[RIGHT] ^ F(a1,k1);
	



	// c1 berechnen
	c1 = a1 ^ x1[LEFT];




	// neuen klartext berechnen,  es gilt: a2 = a1; b2 = ein Wert ungleich b1
	a2 = a1 ^ c1;
	b2 = b1;



	m2[RIGHT] = b2 ^ F(a2,k1);
	m2[LEFT]  = a2 ^ F(m2[RIGHT],k1);


	Encrypt( m2[LEFT] , m2[RIGHT] , &x2[LEFT] , &x2[RIGHT] );






	// c2 berechnen:
	c2 = x2[LEFT] ^ a2;

	if (c1 == c2)
		printf("%x\n", k1);
	
}


int main() {
	unsigned char k1;
     for (k1 = 0x00; k1 < 0xFF; k1 += 0x01)
     {
		check_k1(k1);
     }
}

// Ausgabe:
0
1
68
80
81
e8

Leider trifft diese Behauptung, abhängig von dem gewähltem Klartext und der Wahl von A2, auf unterschiedlich viele geratene K1 zu.
Der richtige K1 lässt sich aber mit kurzen Ausprobieren leicht ermitteln...

Das heißt also:
Um K1 zu berechnen brauchen wir bei Magenta16 also 2^8 Arbeitsschritte, K2 berechnen wir jetzt einfach via Brute-Force, so dass wir insgesamt
maixmal 2^9 Schritte zum Knacken benötigen, was 128 mal schneller ist als Bruteforce

Der beschriebene Angriff lässt sich auch problemlos auf die nicht-reduzierte Version Maggenta erweitern,
und das sogar mit gleich vielen benötigten Schritten, es gilt also für die nicht reduzierten Versionen:
Max. Aufwand für Magenta16 = 2^9
Max. Aufwand für Magenta64 = 2^33
und der max. Aufwand für Magenta128 ist dann 2^65.

mfg YBF