Be-Paranoid.net

XOR verschlüsseln und die Keylänge bestimmen - Kryptanalse Teil 1

Orginal Version | Artikel editieren | Versionen anzeigen | Bottom
Letzte Änderung: 26.08.2009, 10:22

Inhaltsverzeichnis

• Vorwort
  
• XOR
  
• Der Quellcode für eine XOR Verschlüsselung
  
• Kryptoanalyse
  
• Eine Implementierung in Matlab
  
• C++ Quellcode
  
• Wie geht es weiter?
  
• Weblinks
  

Vorwort Top

In diesem Tutorial geht es darum, einen Text mit XOR zu verschlüsseln, und anschließend eine Möglichkeiten zur Kryptoanalyse auszuprobieren.

Ich muss zugeben dass ich eigentlich keine Ahnung von Kryptologie habe, das Tutorial hier ist ein Experiment in dem ich Wissen das ich aus dem Internet gesammelt habe anwenden will. Falls jemand einen Fehler findet -> Editieren

XOR Top

Die erste Frage, die gestellt werden sollte ist folgende: "Wie funktioniert unser Verschlüsselungssystem?"

Wir haben folgendes:

• Plaintext P, die Nachricht die verschlüsselt werden sollte.

• Key K, der Schlüssel den wir hinzu geben damit unsere Nachricht geschützt wird

• Ciphertext C das Ergebniss, unser Verschlüsselte Text

Unser einfaches Verschlüsselungssystem funktioniert wie folgt:

P ⊕ K = C

Der Plaintext wird bitweise mit dem Schlüssel per XOR (⊕) verbunden - der Chiptertext entsteht.

XOR ist symmetrisch: Entschlüsselt wird einfach, in dem der Chiptertext und der Schlüssel mit XOR verbunden wird:

C ⊕ K = P

Nebenbei gilt noch folgendes:

C ⊕ P = K

Die Wahrheitstabelle von XOR (exclusive OR) sieht so aus:

Code:


0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

Diese Verschlüsselung ist theoretisch die sicherste Verschlüsselung: Es ist mathematisch Bewiesen, dass diese Verschlüsselung 100% sicher ist, allerdings nur unter der Bedingung, dass der Schlüssel absolut zufällig ist, das er nur einmal verwendet wurde, dass der Schlüssel genau so lang wie die Nachricht ist. Meistens ist keine dieser Bedingungen erfüllt, deshalb hat das System auch Schwachstellen, Bruce Schneier meint dazu das man XOR Verschlüsselungen vielleicht dazu verwenden könnte um die kleine Schwester am Lesen der Dateien zu hindern, allerdings hält es keinen Kryptoanalytiker für mehr als ein paar Minuten auf. Mehr zum Thema 100% sichere Verschlüsselung unter One-Time-Pad...

Der Quellcode für eine XOR Verschlüsselung Top

Ein wenig Praxis: Ich habe eine XOR Verschlüsselung einmal in Matlab und einmal in C++ implementiert:

• Matlab
  Hier der Quellcode für die Matlab Datei EncryptXOR.m:
  
  

  Code:
  
  
  function [] = EncryptXOR(PlaintextFile, KeyFile, OutputFile)
  %EncryptXOR Encrypts something bitwise XOR
  %
  
  %Reads the Key
  fd = fopen(KeyFile, 'r');
  
  if(fd == -1)
      error('Das KeyFile exisitert nicht.'); 
  end
  
  Key = fread(fd);
  fclose(fd);
  
  
  %Reads the Plaintext
  fd = fopen(PlaintextFile, 'r');
  
  if(fd == -1)
      error('Das Plaintext File exisitert nicht.');
  end
  
  Plaintext = fread(fd);
  fclose(fd);
  
  a = 1;
  
  %Verschlüsselt
  for i=1:length(Plaintext)
  
      Output(i) = bitxor(Plaintext(i),Key(a));
  
      a = a + 1;
      
      if(a > length(Key))
          a = 1;
      end
  end
  
  
  %Reads the Key
  fd = fopen(OutputFile, 'w');
  
  if(fd == -1)
      error('Das Outputfile konnte nicht erstellt werden.');
  end
  
  fwrite(fd, Output);
  
  fclose(fd);
  
  disp('Encryption Done...');
  disp(sprintf('Keylength: %d',length(Key)));
  disp(sprintf('Plaintextlength: %d',length(Plaintext)));
  

  
  
  Die Funktion wird mit EncryptXOR(PlaintextFile, KeyFile, OutputFile) aufgerufen.
  
  Beispiel
  

  Code:
  
  >> EncryptXOR('plaintext','keyfile','out'); LengthXOR('out');
  Encryption Done...
  Keylength: 48
  Plaintextlength: 636
  Keylength Average: 1.792354
  

• C++
  Der Quellcode für die Verschlüsselung sieht so aus:
  
  

  Code:
  
  
  #include <iostream>
  #include <fstream>
  
  int main(int args, char* argv[])
  {
      if(args != 4)
      {
          std::cout << "Usage: " << argv[0] << " <Input File> <Key File> <Output File>" << std::endl;
          return 0;
      }
  
          std::string strInputFile        = argv[1];
          std::string strKeyFile          = argv[2];
          std::string strOutputFile       = argv[3];
  
          std::string strInputFileData    = GetData(strInputFile);
          std::string strKeyFileData      = GetData(strKeyFile);
  
          std::ofstream OFStream;
          OFStream.open(strOutputFile.c_str(), std::ios::out);
  
      int KeyLength = 0;
  
      //Size der files auf 0 überprüfen
      //TODO
  
          int z = 0;
  
          for (int i = 0; i < (int) strInputFileData.size(); i++)
          {
                  if(z >= (int) strKeyFileData.size())
                          z = 0;
  
                  char Key        = strKeyFileData[z];
                  char Input      = strInputFileData[i];
                  char Output     = Input ^ Key;
  
                  OFStream << Output;
  
                  z++;
          }
  
          OFStream.close(); 
  
     return 0;
  }

Kryptoanalyse Top

Kommen wir zur Kryptoanalyse. Als Bruce Schneider schreibt in seinem Buch "Applied Cryptography" dazu folgendes:

Quote:

1. Discover the length of the key by a procedure known as counting
coincidences.
XOR the ciphertext against itself shifted various numbers of bytes, and
count those bytes that are equal. If the displacement is a multiple of the key
length, then something over 6 percent of the bytes will be equal. If it is not,
then less than 0.4 percent will be equal (assuming a random key encrypting
normal ASCII text; other plaintext will have different numbers).
This is called the index of coincidence. The smallest displacement
that indicates a multiple of the key length is the length of the key.

Soweit so gut, wir wenden dazu eine Technik namens "counting
coincidences" an: wir verschieben unseren Text jetzt n=Keylength mal mit sich selbst und zählen jeweils die übereinstimmenden Buchstaben in dem wir sie mit XOR verbinden, da 1 XOR 1 = 0 und 0 XOR 0 = 0 erhalten wir eine 0 wenn die Bytes übereinstimmen. Bei einem Messwerte (der index of coincidence) über 6% sind sie vielfaches der Keylänge, wir suchen einfach das KGV des ganzen.

Der index of coincidence gibt das Verhältnis der Übereinstimmung an. Er ist dann am höchsten wenn ein vielfaches der Keylänge verwendet wird, weil zwei gleiche "Sprachen" verwendet werden, wenn die richtige Keylänge benutzt wird. Das wird genauer in der Wikipedia. erklärt. Wenn der Key um ein vielfaches mit sich selber mit XOR verbunden wird entsteht wieder ein Produkt mit der selben "Sprache", beim index of coincidence entsteht ein peak, ein Spitzenwert.

Eine Implementierung in Matlab Top

Für Matlab habe ich das ganze gegenüber C++ noch erweitert, man gibt eine Grenze an innerhalb der gesucht wird, und es werden die kgVs angegeben, die gefunden werden.

Code:


function [] = LengthXOR(EncryptedText)
%LengthXOR returns the expected value of the keylength
%

%Reads the encrypted Text
fd = fopen(EncryptedText, 'r');

if(fd == -1)
    error('Die Datei exisitert nicht.');
end

%The encrypted text which we have to analyse
Enc = fread(fd);
fclose(fd);

%Gets the length
a = 1;
b = 1;
Average = 0;

%We create the table of convenience
while (a < length(Enc))

    Carent = a + 1;

    Passed = 0;
    b = 1;

    while (b <= length(Enc))
        if(Carent > length(Enc))
            Carent = 1;
        end

        if(bitxor(Enc(Carent),Enc(b)) == 0)
            Passed = Passed + 1;
        end

        Carent = Carent + 1;

        b = b + 1;
    end

    Convidence(a) = Passed * 100.0/length(Enc);
    Average = Average + Convidence(a);

    a = a + 1; 
end

%The average of the convenience
Average = Average / length(Enc);
disp(sprintf('Keylength Average: %f',Average));

%Plot the indices of convenience
a = (1 : 1 : length(Enc)-1);
plot(a, Convidence, 'g+-');
xlabel('Move / Steps')
ylabel('Convidence / %')
%axis([1,length(Enc)-1, 0, 100])
title('Keylength Analyse');

%We have to set an border
NewAverage = input(sprintf('Average Border (0 = %d), try 4.5:', Average + 1.5));

if(NewAverage == 0)
    NewAverage = Average +1;
end

a = 1;
b = 0;

KeyLength = 0;

KeyLengthVector(1, 1) = 0;

%We create a table of convenience in the border
while(a < length(Enc))

    if(Convidence(a) > NewAverage)

        KeyLengthVector(b+1,1) = a;

        if(b == 0)
            KeyLength = a;
        end
    
        b = b + 1;
    end    

    a = a + 1;
end

disp(sprintf('Keylength calculated by the first peek: %d',KeyLength));    

%Keylengthtable
b = 1;
c = 1;
NewKeyLengthVector(1,1) = 0;
NewKeyLengthVector(1,2) = 0;

while(b <= length(KeyLengthVector))

    KeyLengthVector(b,2) = 0;

    a = 1;

    while(a <= length(KeyLengthVector))

        if(rem(KeyLengthVector(a), KeyLengthVector(b)) == 0)
            KeyLengthVector(b,2) = KeyLengthVector(b,2) +1;
        end

        a = a + 1;
    end

    if(KeyLengthVector(b,2) > 1)
    
        NewKeyLengthVector(c,1) = KeyLengthVector(b,1);
        NewKeyLengthVector(c,2) = KeyLengthVector(b,2);

        c = c + 1;
    end
            
        b = b + 1;
end

disp('Other possible Keylengths [Keylenght, Num of peaks: the highter, the better]:');

disp(sortrows(NewKeyLengthVector,2));

Ein Beispiel:

Code:


Key:
AsWrTes

Plaintext:
Coincidence counting can help determine when two texts are written in the same language... [aus der Wikipedia]

>> EncryptXOR('plaintext','keyfile','out'); LengthXOR('out');
Encryption Done...
Keylength: 8
Plaintextlength: 297
Keylength Average: 1.639289
Average Border (0 = 3.139289e+00), try 4.5:3.139
Keylength calculated by the first peek: 8
Other possible Keylengths [Keylenght, Num of peaks: the highter, the better]:
    48     2
    40     3
    56     3
    32     4
    24     6
    16     8
     8    17

Wir haben eine übereinstimmung von 17 mal bei 8, alles andere sind vielfache von 8.

Das Bild am Graph sieht so aus:

C++ Quellcode Top

Hier ist der gesammte Quellcode zur Bestimmung der Keylänge in C++, den ich zuerst erstellt habe, später bin ich auf Matlab umgestiegen:

Code:


#include <sstream> 
#include <iostream>
#include <fstream>
#include <iterator>

std::string IntToString(int iValue)
{
    std::stringstream ssStream;
    ssStream << iValue;
    return ssStream.str();
} 

std::string GetData(std::string strFileName)
{
        std::ifstream FStream;
        FStream.open(strFileName.c_str());

        FStream.unsetf(std::ios_base::skipws);
        std::istream_iterator<char> begin(FStream), end;
        std::string strFileData(begin, end);

        FStream.close();

        return strFileData;
}

int main(int args, char* argv[])
{
    if(args != 4)
    {
        std::cout << "Usage: " << argv[0] << " <Input File> <Key File> <Output File>" << std::endl;
        return 0;
    }

        std::string strInputFile        = argv[1];
        std::string strKeyFile          = argv[2];
        std::string strOutputFile       = argv[3];

        std::string strInputFileData    = GetData(strInputFile);
        std::string strKeyFileData      = GetData(strKeyFile);

        std::ofstream OFStream;
        OFStream.open(strOutputFile.c_str(), std::ios::out);

    int KeyLength = 0;

    //Size der files auf 0 überprüfen
    //TODO

        int z = 0;

        for (int i = 0; i < (int) strInputFileData.size(); i++)
        {
                if(z >= (int) strKeyFileData.size())
                        z = 0;

                char Key        = strKeyFileData[z];
                char Input      = strInputFileData[i];
                char Output     = Input ^ Key;

                OFStream << Output;

                z++;
        }

        OFStream.close();

        /****************** DECRYPT **************/

    //
    //1. Part: Try to get the keylength
    //

        std::string strOutputFileData   = GetData(strOutputFile);
        int OutPutSize                  = strOutputFileData.size();
        int Carent                      = 0;

    std::cout << "Output: " << OutPutSize << " chars\n";
    std::cout << "Key:    " << strKeyFileData.size() << " chars\n";
    std::cout << "Input:  " << strInputFileData.size() << " chars\n";

    float *Coincidence    = new float[OutPutSize];
    float Average        = 0;

        for(int i = 0; i < (OutPutSize - 1); i++)
        {
        Carent = i+1;

            int iPass = 0;

                for(int y = 0; y < OutPutSize; y++)
                {
                        if(Carent >= OutPutSize)
                                Carent = 0;

                        char OutputShifted      = strOutputFileData[Carent];
                        char Output             = strOutputFileData[y];

                        char New                = Output ^ OutputShifted;

                        if(New == 0)
                                iPass++;

                        Carent++;
                }

                   //std::cout << "Equal " << i << ": " << iPass << " in percent: " << ((float)iPass * 100.0 /(float)OutPutSize) << "%" << std::endl;

        Coincidence[i]    = ((float)iPass * 100.0 /(float)OutPutSize);
        Average     += Coincidence[i];
           }

    // Calculates the average
    Average = Average / OutPutSize;

    for(int a = 0; a < OutPutSize; a++)
        if(Coincidence[a] > Average)
        {
            //The first peak index
            KeyLength = (a+1);    
            break;
        }

    std::cout << "Key Length: " << KeyLength << std::endl;

    //
    //2. Part: Try to get the plaintext shifted with the keylength
    //

    //XOR the chipertext with itself shifted by the keylength
    Carent = KeyLength;
    
    std::string KeyShiftedByItself = "";

    for(int c = 0; c < OutPutSize; c++)
    {
        if(Carent >= OutPutSize)
            Carent = 0;

        KeyShiftedByItself +=  strOutputFileData[Carent] ^ strOutputFileData[c];
        
        Carent++;
    }

    //
    //3. Part: Analyse
    //

    //
    //in suchen, im suchen
    
    int Index    = 0;
    int MaxCombo    = 0;

    for(int d = 0; d < OutPutSize; d++)
    {
        Index = 0;

        while((int)KeyShiftedByItself[d + Index] == 0)
        {
            Index++;

            if(Index > MaxCombo && Index < 4)
                MaxCombo = Index;
        }
    }    
    
    std::string Output = "";
    std::string Key = "";

    for(int h = 0; h < KeyLength; h++)
        Key += " ";

    std::string Pattern = "";

    std::cout << "We found some pattern with " << MaxCombo << " chars which seems to appear frequently. Set the pattern:";
    std::cin >> Pattern;
    std::cout << "Replace the first 0x00 with " << Pattern << std::endl;

    for(int e = 0; e < OutPutSize; e++)
    {
        bool Pass = true;
    
        for(int f = 0; f < MaxCombo; f++)
        {
            if(KeyShiftedByItself[e + f] != 0)
                Pass = false;
        }

        if(Pass == true)
            for(int g = 0; g < MaxCombo; g++)
                Key[(g % KeyLength)] = strOutputFileData[g] ^ Pattern[g];
    }

//    for(int j = 0; j < OutPutSize; j++)
//        Output += strOutputFileData[j] ^ Key [j];

//    std::cout << Output << std::endl;    

    std::cout << Key;

    delete[] Coincidence;

        return 0;
}

Hier ein Ergebnis mit Excel ausgewertet:

Wie geht es weiter? Top

Im Teil 1 ging es nur darum eine XOR verschlüsselung zu realisieren, und für einen Chipertext-only Angriff aus einem verschlüsselten Text die Länge des Schlüssels zu bekommen.

Jetzt müssen wir noch den Chipertext mit sich selbst, um die Schlüssellänge n verschoben mit XOR verknüpfen, dann erhalten wir den Plaintext der mit sich selbst um n verschoben verknüpft wurde.

Wenn wir was gemacht haben, haben wir folgendes zur Verfügung:

• Chipertext

• n, die Schlüssellänge

• Plaintext um n verschoben = Chipertext um n verschoben

Daraus müssen wir dann mit Häufigkeitsanalysen auf den Plaintext kommen.

Weblinks Top

• de.wikipedia.org/wiki/Kasiski-Test

• en.wikipedia.org/wiki/Kasiski_examination

• en.wikipedia.org/wiki/Coincidence_counting

• Applied Cryptography von Bruce Schneier

• de.wikipedia.org/wiki/XOR

Orginal Version | Artikel editieren | Versionen anzeigen | Top
Letzte Änderung: 26.08.2009, 10:22