On this put up, we’re going to study a little bit of what’s the XOR encryption algorithm and easy methods to decipher it by Friedman Check utilizing Hamming Distance and Frequency Evaluation.
To begin with, what precisely is a XOR cipher?
Should you ever studied bitwise operators, you could have already heard of unique or, or just XOR.
It takes two inputs and returns 1 if these inputs are totally different.
However the attention-grabbing half is that this straightforward operation, that occurs within the bits stage, may be very helpful for composing cryptographic keys. That is what we’ll see on this put up, utilizing a little bit of Python and the issue introduced within the sixth problem of Cryptopals (set 1)
How can we use XOR as a way of encryption? In truth, what’s a cryptographic cipher?
To reply this query, let’s assume when it comes to features. Encrypting a message is taking its plaintext (or, extra exactly, its bytes), and producing an showing random output with the assistance of an encryption algorithm. This algorithm defines the sample we’ll observe when changing the unique content material with the encrypted one.
For instance, the Caesar cipher replaces a letter with its corresponding following letter, such that “ABC” turns into “BCD”. This sample goes by the entire message.
However the Caesar cipher can skip multiple letter – what issues right here is the logic of substitution. On this manner, the XOR cipher may be very comparable.
Bytes, ASCII and single-byte XOR
Earlier than introducing the encryption with a repeating cipher, let’s first perceive how a single-byte encryption can be performed.
The encryption with a single-byte XOR cipher is made once we use the XOR operation to vary the worth of every byte; we make this operation in the entire textual content utilizing a key – that’s the fixed worth which we’re going to use to do that operation.
binary_string = b"hi there"
for byte in binary_string:
print(byte ^ 100)
The outputs will probably be 12, 1, 8, 8 and 11.
It occurs as a result of every letter in a binary string could be represented by a binary quantity that, XORed towards 100 (the important thing right here), returns a unique byte. This quantity could possibly be any worth throughout the vary [0, 255].
Due to this fact, right here 100 acts as our key – we would wish to know this worth to carry out the decryption of the message. Utilizing a XOR cipher is a symmetric encryption methodology, what implies that we’d like the identical key each to encrypt and decrypt a message. It occurs as a result of XOR is an involutory operate – it is its personal inverse, so to decrypt a message we would wish to easily XOR its bytes towards the important thing once more.
So, we have already got a substitution cipher comparable when it comes to Caesar cipher, however a bit extra refined.
Aspect be aware 1: it seems that not all XORed bytes will probably be printable, since they are often outdoors the ASCII vary. On this case, we will make a conversion to base64, for instance, to print them. See (in Portuguese).
Aspect be aware 2: the article above may also be useful that will help you perceive how issues work with ASCII characters in byte-level.
Repeating XOR cipher
It seems that encrypting one thing with a single-byte key can be a really weak encryption methodology. To interrupt it, we might solely have to know which key was used – which could possibly be achieved by bruteforcing all of the 256 attainable values. Then, we might have a look at the outputs of those operations and select the one that’s extra “English-like”, by assign scores to every output, based mostly on essentially the most frequent letters throughout the English language.
PS: bear in mind this operate, we’re going to see it later once more!
# Breaking a single-byte XOR cipher: we carry out a XOR operation
# within the string utilizing all attainable values for the important thing.
# The important thing used to generate the output nearer to English is what we're looking for.
def assign_score(output_string):
string_score = 0
freq = [' ', 'e', 't', 'a', 'o', 'i', 'n', 's', 'h', 'r', 'd', 'l', 'u']
for letter in output_string:
if letter in freq:
string_score += 1
return string_score
def XOR_decode_bytes(encoded_array):
last_score = 0
greatest_score = 0
for n in vary(256): # checks for each attainable worth for XOR key
xord_str = [byte ^ n for byte in encoded_array]
xord_ascii = ('').be part of([chr(b) for b in xord_str])
last_score = assign_score(xord_ascii)
if (last_score > greatest_score):
greatest_score = last_score
key = n
return key
So, we will make it tougher to interrupt by merely creating an extended key – with extra bytes and that repeats itself throughout the textual content.
It might require us two steps to interrupt: first, we would wish to know the size of the important thing, after which we would wish to know the important thing itself – which suggests testing every attainable worth for every one of many key’s characters. A bit extra difficult, proper?
So, let’s perceive easy methods to encrypt a textual content utilizing a XOR repeating key first.
Repeating key: encryption
input_text1 = b"Burning 'em, in the event you ain't fast and nimblenI'm going loopy once I hear a cymbal"
XOR_key = b"ICE"
def XOR_repeating_encode(input_string: bytes, key: bytes) -> bytes:
xord_output = []
print(input_string)
for i in vary(len(input_string)):
xord_output.append(input_string[i] ^ key[i % len(key)])
return bytes(xord_output)
The logic right here is fairly the identical we used for the single-byte key. Briefly, we carry out a XOR operation towards every of the characters of the important thing, which is ICE right here. So, “B” is XORed towards “I”, “u” towards “C” and “r” towards “E”, and so forth till we attain the top of the textual content. Getting the plaintext again is achieved by the identical course of.
However what if we needed to get well the plaintext with out figuring out the important thing?
Right here issues begin to get attention-grabbing. Let’s examine easy methods to break a repeated-key XOR ciphertext!
1 – The important thing’s size: Hamming distance
How far is “a” from “d”?
You could say that they’re just a few letters aside within the alphabet. However there’s one other attention-grabbing strategy to measure their “distance”: what number of totally different bits they’ve – which is their Hamming distance.
So, lowercase a is 95 within the ASCII desk, and lowercase d is 100. Their binary representations are 1011111 and 1100100. They’ve 5 totally different bits, so their hamming distance is 5.
You possibly can measure this distance throughout phrases, too – the method is identical, you solely sum the consequence from every pair of characters.
What this measure has to do with the repeating XOR cipher?
The common Hamming distance between two bytes picked at random is round 4.0, whereas that of any two lowercased ASCII alphabet – whose values vary from 97 to 122 – is 2.5.
So it implies that the hamming distance between the characters of a plaintext will probably be a lot decrease than that from a bunch of random bytes – and this info may be very helpful once we get to check the attainable outputs for a wide range of attainable key lengths.
Let’s perceive it higher.
def hamming_distance(string1: bytes, string2: bytes) -> int:
distance = 0
for (byte1, byte2) in zip(string1, string2):
distance += bin(byte1 ^ byte2).rely('1')
return distance
Checking the totally different bits of two strings is mainly the identical as performing an XOR operation on them and counting the 1’s, so the operate above does precisely this.
Alright. We now have a strategy to rating a string to know the space between its bytes. How can we use it now?
On this problem, the vary of the scale of attainable keys is throughout the interval [2, 40]. Due to this fact, we must do the next steps:
1) Divide our textual content into totally different chunk sizes, starting from 2 to 40.
2) On every iteration – for every chunk dimension chosen – we’ll verify the hamming rating between the chunks.
3) The size of chunks with the decrease common hamming distance corresponds to the important thing’s size.
This method works as a result of, as soon as we get the suitable dimension for the important thing, the chunks will probably be simply XORed plaintext. Due to this fact, their hamming distance will probably be manner decrease than in the event that they have been random bytes.
def find_key_length():
# we're looking for the size that produces an output with the bottom hamming rating
min_score = len(textual content)
for keysize in vary(2, 40):
chunks = [text[start:start + keysize] for begin in vary(0, len(textual content), keysize)]
subgroup = chunks[:4]
# getting the typical hamming distance per byte
average_score = (sum(hamming_distance(a, b) for a,b in mixtures(subgroup, 2)) / 6) / keysize
if average_score < min_score:
min_score = average_score
key_length = keysize
return key_length
Within the code above, the logic is because it follows:
For instance that we’re guessing that the bottom line is 4 characters lengthy. If we had the next textual content:
textual content = "YWJjZGVmZ2hpamtsbW4="
We might divide it in a number of chunks with 4 letters every:
chunks = ['YWJj', 'ZGVm', 'Z2hp', 'amts', 'bW4=']
Now, if we take the primary 4 chunks, we’re capable of measure the typical hamming distance between them:
# keysize right here is the same as 4 and subgroup is the primary 4 chunks
# dividing the rating by 6 offers us the typical diff between chunks, dividing it by keysize offers us the typical diff between every a, b bytes for chunk1, chunk2
average_score = (sum(hamming_distance(a, b) for a,b in mixtures(subgroup, 2)) / 6) / keysize
2 – The important thing itself
As soon as we get the important thing’s size, issues get simpler.
On this explicit problem, it seems that the bottom line is 29 characters lengthy. Although we all know the size, we nonetheless have 29 characters to guess, every one having 256 prospects.
How to do this? Nicely, the reply lies on matrices.
def find_key(key_length = find_key_length()):
key_blocks = [text[start:start + key_length] for begin in vary(0, len(textual content), key_length)]
# transpose the 2D matrix
key = []
single_XOR_blocks = [list(filter(None,i)) for i in zip_longest(*key_blocks)]
for block in single_XOR_blocks:
key_n = XOR_decode_bytes(block)
key.append(key_n)
ascii_key = ''.be part of([chr(c) for c in key])
return ascii_key.encode()
If our key had precisely three characters – say the important thing was “RED” – then every first character of every chunk can be XORed towards “R”, the second towards “E” and so forth.
So, if we joined every nth character of every chunk, the consequence can be a listing of characters encrypted with a single byte XOR cipher, whose key’s the nth character of our repeating key!
Oof, that is an excessive amount of. Let’s examine it intimately:
The operation of making an array becoming a member of each nth aspect of every chunk is mainly transposing a matrix.
To lastly uncover the important thing, then, we simply want to use the operate that finds the important thing for a single-byte XOR ciphertext in every of the traces of our new generated matrix.
And now, we have now our deciphered plaintext! 
You possibly can see the total code for this put up right here.
