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

Sprachenübersicht/Kryptologie/Cryptology/XOR

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

Diese Seite wurde 19744 mal aufgerufen.

Dieser Artikel wurde in einem Wikiweb System geschrieben, das heißt, Sie können die Artikel jederzeit editieren, wenn Sie einen Fehler gefunden haben, oder etwas hinzufügen wollen.

Editieren Versionen Linkpartnerschaft Bottom Printversion

Keywords: XOR keylänge bestimmen, XOR verschlüsseln, XOR entschlüsseln

Inhaltsverzeichnis



Vorwort Top



In diesem Tutorial geht es darum, einen Text mit XOR zu verschlüs]Key K[/b], der Schlüssel den wir hinzu geben damit unsere Nachricht geschützt wird[/enum]
xt C[/b] das Ergebniss, unser Verschlüsselte Text[/enumUnser 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:

Abbildung




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:

Abbildung



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






  • Applied Cryptography von Bruce Schneier


Gibt es noch irgendwelche Fragen, oder wollen Sie über den Artikel diskutieren?

Editieren Versionen Linkpartnerschaft Top Printversion

Haben Sie einen Fehler gefunden? Dann klicken Sie doch auf Editieren, und beheben den Fehler, keine Angst, Sie können nichts zerstören, das Tutorial kann wiederhergestellt werden

Sprachenübersicht/Kryptologie/Cryptology/XOR/XOR verschlüsseln und die Keylänge bestimmen - Kryptanalse Teil 1