Known-plaintext attack tool for XOR-encrypted data

Εργαλείο επιθέσεων γνωστού αρχικού κειμένου έναντι XOR-κρυπτογραφημένων δεδομένων

· Cryptography Κρυπτογραφία Cybersecurity Κυβερνοασφάλεια · cryptanalysis κρυπτανάλυση tool εργαλείο attack επίθεση known-plaintext γνωστό αρχικό κείμενο xor xor

Let's say we XOR-encrypt a text file using this "secure" password/key: @v3RyS3cREtK3y!

We should not forget that:

  • plaintext ⊕ key = encrypted_text
  • encrypted_text ⊕ plaintext = key
  • encrypted_text ⊕ key = plaintext

If the key is smaller than the plaintext, the key is repeated. This fact makes this encryption scheme extremely weak.

In practice, the above equations mean that if we know a part of the initial plaintext, then we can retrieve part of the key relatively easily. By using this partial key we can retrieve a larger part of the plaintext and then a larger part of the key and so forth and so on, till we have accomplished to retrieve the whole key and -as a consequence- the whole plaintext.

Ας πούμε ότι κρυπτογραφούμε ένα αρχείo κειμένου εφαρμόζοντας αποκλειστική διάζευξη (XOR) με αυτόν τον "ασφαλή" κωδικό/κλειδί: @v3RyS3cREtK3y!

Δεν πρέπει να ξεχνάμε ότι:

  • αρχικό_κείμενο ⊕ κλειδί = κρυπτογραφημένο_κείμενο
  • κρυπτογραφημένο_κείμενο ⊕ αρχικό_κείμενο = κλειδί
  • κρυπτογραφημένο_κείμενο ⊕ κλειδί = αρχικό_κείμενο

Αν το κλειδί είναι μικρότερο σε μέγεθος από το αρχικό κείμενο τότε το κλειδί επαναλαμβάνεται όσες φορές χρειάζεται. Αυτό το γεγονός καθιστά αυτή τη μέθοδο κρυπτογράφησης εξαιρετικά αδύναμη.

Οι παραπάνω εξισώσεις πρακτικά σημαίνουν ότι αν γνωρίζουμε ή υποψιαζόμαστε κάποιο μέρος του αρχικού κειμένου, τότε μπορούμε σχετικά εύκολα να ανακτήσουμε μέρος του κλειδιού. Χρησιμοποιώντας αυτό το μερικό κλειδί μπορούμε να ανακτήσουμε ένα μεγαλύτερο κομμάτι του αρχικού κειμένου και ύστερα ένα μεγαλύτερο μέρος του κλειδιού κ.ο.κ. ώσπου τελικά έχουμε κατορθώσει να ανακτήσουμε ολόκληρο το κλειδί και κατά συνέπεια ολόκληρο το αρχικό κείμενο.

The problem with this approach is that we may not know the size of the key and the exact position of a word or phrase in the initial text. Therefore, I wrote a tool which searches for a word or phrase in the whole encrypted text and it tries automatically all the possible keys that emerge from this process. We regard as criteria for a successful decryption the existence of the known plaintext and the non-existence of non-printable characters in the recovered plaintext. This means our method is applicable only to text files. Moreover -in order to recude the number of possible keys we try- we can also reject all those keys that contain non-printable characters by setting inside the script the variable printable_key = True (this is the default value). Last but not least, we can also set the max key length we want to try.

Το πρόβλημα σε αυτήν την προσέγγιση είναι ότι μπορεί να μην ξέρουμε την ακριβή θέση μια λέξης ή φράσης στο αρχικό κείμενο καθώς και το μέγεθος του κλειδιού. Έτσι, έγραψα ένα εργαλείο που ψάχνει να βρεί κάποια λέξη ή φράση σε ολόκληρο το κρυπτογραφημένο κείμενο και δοκιμάζει αυτόματα όλα τα πιθανά κλειδιά που προκύπτουν από αυτήν τη διαδικασία. Θεωρούμε ως κριτήρια επιτυχούς αποκρυπτογράφησης την εμφάνιση του γνωστού μέρους στο ανακτηθέν κείμενο και την πλήρη απουσία μη-εκτυπώσιμων χαρακτήρων από αυτό. Δηλαδή, η μέθοδός μας εφαρμόζεται μόνο για αρχεία κειμένου. Επίσης -για να μειώσουμε τον αριθμό των πιθανών κλειδιών που δοκιμάζουμε- μπορούμε να εξετάζουμε μόνο όσα κλειδιά δεν περιέχουν και τα ίδια μη-εκτυπώσιμους χαρακτήρες, θέτοντας μέσα στον κώδικα τη μεταβλητή printable_key = True (αυτή είναι η προκαθορισμένη ρύθμιση). Τέλος, μπορούμε να καθορίσουμε και το μέγιστο μέγεθος για τα κλειδιά που θέλουμε να δοκιμαστούν.

$ ./xorknown.py --help
Known-plaintext attack:
./xorknown.py <encrypted file> <known plaintext> [max_key_length]

Decrypt using known key:
./xorknown.py <encrypted file> --key=the_known_key

Let's see this tool in action. We have an encrypted text file and we know (or we have an inkling) that the initial text contains the word 'message':

Ας δούμε πώς λειτουργεί το εργαλείο στην πράξη. Έστω ότι έχουμε ενα κρυπτογραφημένο αρχείο κειμένου και γνωρίζουμε ή υποψιαζόμαστε ότι το αρχικό κείμενο περιέχει τη λέξη 'message':

$ ./xorknown.py xor_encrypted_text.bin message
Searching XOR-encrypted xor_encrypted_text.bin for string 'message'
Key length: 15 
Partial Key: ��3RyS3cR������ 
Plaintext: ��e XOR o��������is extr��������mmon as��������nent in��������mplex c��������By itse��������g a con��������peating��������simple ��������er can ��������y be br��������ng freq��������alysis.��������content��������message��������guessed��������rwise k��������n the k��������e revea�������� primar��������is that��������imple t��������ent, an��������he XOR ��������n is co��������nally i��������ve. A s��������peating��������e. usin��������me key ��������operati��������e whole��������ipher i��������ore som��������sed for��������informa��������cases w��������particu��������rity is��������d.

If ��������is rand��������s at le��������ong as ��������age, th��������pher is��������re secu��������when th��������ey repe��������ithin a��������. When ��������tream i��������ted by ��������-random��������generat��������result ��������eam cip��������h a key�������� truly ��������the res�������� one-ti��������which i��������kable e��������heory.
��������of thes��������s, the ��������ator is��������ble to ��������plainte��������k, sinc��������ext XOR��������ext = k��������s also ��������to flip��������ry bits��������decrypt��������text by��������ating t��������rtext. ��������called ��������lity.

As you can see, because the word 'message' was indeed in the initital text, part of the key and part of the initial text have been recovered correctly. In addition, we have discovered the key size. Now, by taking advantage of this partially revealed text we can guess some other words of the initial text. For example, this ????????rwise is probably the word 'otherwise':

Όπως βλέπετε, επειδή η λέξη 'message' όντως υπήρχε στο αρχικό κείμενο, μέρος του κλειδιού και του αρχικού κειμένου ανακτήθηκαν σωστά. Μάλιστα ανακαλύψαμε και το μέγεθος του κλειδιού. Τώρα, αξιοποιώντας το μέρος του κειμένου που αποκαλύφθηκε μπορούμε να μαντέψουμε και άλλες λέξεις του αρχικού κειμένου. Για παράδειγμα, αυτό το ????????rwise είναι κατά πάσα πιθανότητα η λεξη 'otherwise':

$ ./xorknown.py xor_encrypted_text.bin otherwise
Searching XOR-encrypted xor_encrypted_text.bin for string 'otherwise'
Key length: 15 
Partial Key: @v3RyS3������y! 
Plaintext: The XOR������tor is ex������y common ������omponent ������e complex������rs. By it������using a c������t repeati������, a simpl������cipher ca������ially be ������ using fr������y analysi������the conte������any messa������ be guess������otherwise������ then the������an be rev������ Its prim������rit is th������is simple������plement, ������at the XO������ation is ������ationally������ensive. A������e repeati������ (i.e. us������e same ke������xor opera������n the who������a) cipher������erefore s������es used f������ing infor������ in cases������ no parti������security ������uired.

I������key is ra������nd is at ������as long a������message, ������R cipher ������h more se������han when ������is key re������on within������sage. Whe������keystream������nerated b������eudo-rand������ber gener������the resul������ stream c������ With a k������t is trul������om, the r������is a one-������ad, which������breakable������in theory������any of th������phers, th������operator ������nerable t������own-plain������ttack, si������aintext X������hertext =������It is als������ial to fl������itrary bi������the decry������laintext ������ipulating������iphertext������ is calle������eability.

Thus, we have retrieved a different part of the key and a different part of the plaintext. This freq?????? reminds us the word 'frequency'. Let's test it:

Έτσι ανακτήσαμε ενα διαφορετικό μέρος του κλειδιού και του αρχικού κειμένου. Αυτό το freq?????? μας φέρνει στο μυαλό τη λέξη 'frequency'. Για να δούμε:

$ ./xorknown.py xor_encrypted_text.bin frequency
Searching XOR-encrypted xor_encrypted_text.bin for string 'frequency'
Key length: 15 
Partial Key: �����S3cREtK3y� 
Plaintext: �����OR operat������extremely������n as a co������t in more������ex cipher������itself, u������ constant������ting key,������ple XOR c������can trivi������e broken ������frequency������sis. If t������tent of a������sage can ������ssed or o������se known ������he key ca������evealed. ������imary mer������that it i������le to imp������, and tha������XOR opera������s computa������ly inexpe������ A simple������ting XOR ������using the������key for x������ration on������hole data������er is the������ sometime������ for hidi������ormation ������es where ������ticular s������y is requ������
If the k������random an������t least a������ as the m������, the XOR������r is much������secure th������n there i������repetitio������in a mess������hen the k������am is gen������ by a pse������ndom numb������erator, t������ult is a ������ cipher. ������ key that������uly rando������ result i������e-time pa������ch is unb������le even i������ry.

In a������these cip������the XOR o������r is vuln������ to a kno������intext at������since pla������ XOR ciph������ = key. I������lso trivi������flip arbi������bits in t������rypted pl������t by mani������ng the ci������xt. This ������led malle������y.

At this point, we have essentially discovered the whole key and we can use it to decrypt the whole text:

Τώρα, έχουμε ουσιαστικά ανακαλύψει ολόκληρο το κλειδί και μπορούμε να το χρησιμοποιήσουμε για να αποκρυπτογραφήσουμε ολόκληρο το κείμενο:

./xorknown.py xor_encrypted_text.bin --key='@v3RyS3cREtK3y!'
Key length: 15 
Partial Key: @v3RyS3cREtK3y! 
Plaintext: The XOR operator is extremely common as a component in more complex ciphers. By itself, using a constant repeating key, a simple XOR cipher can trivially be broken using frequency analysis. If the content of any message can be guessed or otherwise known then the key can be revealed. Its primary merit is that it is simple to implement, and that the XOR operation is computationally inexpensive. A simple repeating XOR (i.e. using the same key for xor operation on the whole data) cipher is therefore sometimes used for hiding information in cases where no particular security is required.

If the key is random and is at least as long as the message, the XOR cipher is much more secure than when there is key repetition within a message. When the keystream is generated by a pseudo-random number generator, the result is a stream cipher. With a key that is truly random, the result is a one-time pad, which is unbreakable even in theory.

In any of these ciphers, the XOR operator is vulnerable to a known-plaintext attack, since plaintext XOR ciphertext = key. It is also trivial to flip arbitrary bits in the decrypted plaintext by manipulating the ciphertext. This is called malleability.

A last observation: if we are looking for a phrase longer than the size of the repeating key, in order for the tool to find it, we have to make sure that max_key_length is multiple times the size of the key. This happens because a longer phrase will contain the key multiple times. Have a look in the following example:

Μια τελευταία παρατήρηση: αν ψάχνουμε μια φράση μεγαλύτερη από το μέγεθος του επαναλαμβανόμενου κλειδιού, για να τη βρει το εργαλείο θα πρέπει να βεβαιωθούμε ότι το max_key_length είναι πολλαπλάσιο του μεγέθους του κλειδιού. Αυτό συμβαίνει επειδή μια μεγάλη φράση θα εμπεριέχει πολλαπλές φορές το κλειδί. Δείτε το παρακάτω παράδειγμα:

./xorknown.py xor_encrypted_text.bin "extremely common" 30
4
Searching XOR-encrypted xor_encrypted_text.bin for string 'extremely common'
Key length: 30 
Partial Key: @v3RyS��������������S3cREtK3y! 
Plaintext: The XO��������������extremely common��������������t in more comple��������������itself, using a ��������������ting key, a simp��������������can trivially be��������������frequency analys��������������tent of any mess��������������ssed or otherwis��������������he key can be re��������������imary merit is t��������������le to implement,��������������XOR operation is��������������ly inexpensive. ��������������ting XOR (i.e. u��������������key for xor oper��������������hole data) ciphe�������������� sometimes used ��������������ormation in case��������������ticular security��������������
If the key is r��������������t least as long ��������������, the XOR cipher��������������secure than when��������������repetition withi��������������hen the keystrea�������������� by a pseudo-ran��������������erator, the resu�������������� cipher. With a ��������������uly random, the ��������������e-time pad, whic��������������le even in theor��������������these ciphers, t��������������r is vulnerable ��������������intext attack, s�������������� XOR ciphertext ��������������lso trivial to f��������������bits in the decr��������������t by manipulatin��������������xt. This is call��������������y.

Key length: 30 
Partial Key: �����S3cREtK3y!@v3RyS��������� 
Plaintext: �����OR operator is e��������������n as a component��������������ex ciphers. By i�������������� constant repeat��������������ple XOR cipher c��������������e broken using f��������������sis. If the cont��������������sage can be gues��������������se known then th��������������evealed. Its pri��������������that it is simpl��������������, and that the X��������������s computationall�������������� A simple repeat��������������using the same k��������������ration on the wh��������������er is therefore �������������� for hiding info��������������es where no part��������������y is required.

��������������random and is at�������������� as the message,��������������r is much more s��������������n there is key r��������������in a message. Wh��������������am is generated ��������������ndom number gene��������������ult is a stream �������������� key that is tru�������������� result is a one��������������ch is unbreakabl��������������ry.

In any of t��������������the XOR operator�������������� to a known-plai��������������since plaintext �������������� = key. It is al��������������flip arbitrary b��������������rypted plaintext��������������ng the ciphertex��������������led malleability�

Here is the python code for this tool:

Ακολουθεί ο κώδικας του εργαλείου σε python:

#!/usr/bin/env python2
# Author: Alamot
# This is a XOR plaintext attack tool: If we know a part of the plaintext maybe
# we can recover the key and the whole text.
from __future__ import print_function
from __future__ import division
import string, sys


ignore_code = 0xff
printable_key = True
max_key_length = 21


def is_printable(text, ignore_code):
    ''' Function to check if every character in text is printable '''
    for ch in text:
        if ord(ch) == ignore_code:
            continue
        if ch not in string.printable:
            return False
    return True


def lrotate(s, d):
    ''' Function to rotate string left by d length '''
    return s[d:] + s[0:d]

    
if len(sys.argv) < 2 or sys.argv[1].strip().lower() == "--help":
    print("Known-plaintext attack:\n"+sys.argv[0]+" <encrypted file> <known plaintext> [max_key_length]")
    print("\nDecrypt using known key:\n"+sys.argv[0]+" <encrypted file> --key=the_known_key")
    exit()

filename = sys.argv[1]

if sys.argv[2].strip().lower()[:5] == "--key":
    known_key = sys.argv[2].strip()[6:]
    with open(filename, "rb") as f:
        data = f.read()
    decrypted_text = ""
    repeated_key = (known_key)*((len(data) // len(known_key)) + 1)
    for x in range(len(data)):
        decrypted_text += chr(ord(data[x]) ^ ord(repeated_key[x]))
    print("Key length: "+str(len(known_key)), "\nPartial Key: "+known_key, "\nPlaintext: "+decrypted_text)
    exit()
else:
    known_plaintext = sys.argv[2]

if len(known_plaintext) > max_key_length:
    print("The length of the known plaintext is greater than max_key_length (="+str(max_key_length)+"). Please give a smaller plaintext or incrase max_key_length.")
    exit()
    
if len(sys.argv) > 3:
    max_key_length = int(sys.argv[3])+1
    
with open(filename, "rb") as f:
    data = f.read()

print("Searching XOR-encrypted "+filename+" for string '"+known_plaintext+"' (max_key_length = "+str(max_key_length-1)+")")

try:    
    for i in range(len(data)-len(known_plaintext)): # Try known plaintext in every position
        partial_key = ""
        for j in range(len(known_plaintext)):
            if known_plaintext[j] == ignore_code:
                partial_key += chr(ignore_code)
            else:
                partial_key += chr(ord(data[i+j]) ^ ord(known_plaintext[j]))
        #print("Single key: "+partial_key)
        if is_printable(partial_key, ignore_code) or not printable_key:
            for n in range(len(partial_key), max_key_length): # Try different key lengths
                for m in range(n):                            # Try different partial key positions
                    expanded_key = lrotate(partial_key+chr(ignore_code)*(n-len(partial_key)), m)
                    #print(expanded_key, m)
                    repeated_key = (expanded_key)*((len(data) // len(expanded_key)) + 1)
                    decrypted_text = ""
                    for x in range(len(data)): # Try to decrypt the encoded text
                        if ord(repeated_key[x]) == ignore_code:
                            decrypted_text += chr(ignore_code)
                        else:
                            decrypted_text += chr(ord(data[x]) ^ ord(repeated_key[x]))
                    if is_printable(decrypted_text, ignore_code): # Is the whole result printable?
                        if known_plaintext in decrypted_text:
                            print("Key length: "+str(len(expanded_key)), "\nPartial Key: "+expanded_key, "\nPlaintext: "+decrypted_text)
                            print("")
except KeyboardInterrupt:
    print("\nCtrl+C received. Exiting...")
    exit()

You can download this tool from here: xorknown.py

Μπορείτε να κατεβάσετε το εργαλείο απο εδώ: xorknown.py

See also...

Δείτε επίσης...