Didier Stevens

Friday 1 January 2016

XOR Known-Plaintext Attack

Filed under: Encryption,My Software — Didier Stevens @ 16:00

To celebrate my Microsoft MVP award 2016, I’m releasing a new XOR-tool. Because you can never have enough XOR-tools in your toolbox :-).

When data is XOR-encrypted with a repeating key and you known some of the plaintext, you can perform a simple known-plaintext attack. Because when you XOR the ciphertext with the plaintext, you recover the key-stream.

With “repeating key” I mean the following: let’s assume that the encryption key is “Secret”. Then the first byte of the plaintext is XORed with “S”, the second byte with “e”, the third byte with “c”, …, the sixth byte with “t”. And for the seventh byte, we start again with “S”, then for the eighth byte again with “e”, …

When we know some of the plaintext, for example the beginning of the file, and we XOR this with the ciphertext, we obtain the key-stream: SecretSecretSecretSec It’s simple to extract the repeating key (Secret).

I’ve written a small Python program that automates this process: xor-kpa.py.

As an example, I’ve XORed the notepad.exe program with a key. We know that PE files contain the string “This program cannot be run in DOS mode”, this string is store in text file plaintext.txt. This is how you use xor-kpa:

C:\Demo>xor-kpa.py -e 3 plaintext.txt notepad-ciphertext.exe
Key:       Password
Extra:     30
Keystream: rdPasswordPasswordPasswordPasswordPass

This result shows that the recovered keystream is “rdPasswordPasswordPasswordPasswordPass”, and that the repeating key is “Password”. Extra (30) is the difference between the keystream length (38) and the key length (8). The higher the value of extra is, the higher the confidence is we recovered the correct key. When Extra is only 1, the confidence is low. To properly recover the key, the known-plaintext must be longer than the key.

With option -e you can filter for the minimum value of Extra.

Since the known-plaintext can often be a a short ASCII string, you can provide it directly as an argument in stead of writing it in a text file. To achieve this, just precede the argument with character #, like in this example (the double quotes are necessary because of the space characters):

C:\Demo>xor-kpa.py -e 3 "#This program cannot be run in DOS mode" notepad-ciphertext.exe
Key:       Password
Extra:     30
Keystream: rdPasswordPasswordPasswordPasswordPass

xor-kpa_V0_0_1.zip (https)
MD5: 4265BB1AFCD470A98070FFBDFCB1B52A
SHA256: CF41CEDE7281459FA47061B366AA9B4A5F579CC9BA46E73098B52EA8CAB6E816

Blog at WordPress.com.