haxelion's den

nothing to see here







This year I’m not elligible to participate in the Cyber Security Challenge Belgium as I’m not a student anymore so instead I’ve decided to contribute to the competition by writting a few challenges. CBC XOR was one of my contribution to the crypto category. I’m glad that 26 team managed to solve it in the end, that’s way better than my other challenge, Enter The Matrix ;)

We all known about XOR encryption and other byte (or character) substitution cipher weakness: you can attack them using frequency analysis. But this is not a problem specific to simple cipher, this problem is also found when using strong cipher (like AES) in Electronic Code Block mode (see Elecronic Coloring Book for a fun example).

So how do we solve this? Cipher Block Chaining mode! But is it really secure with a simple XOR cipher?

So for this challenge we get the encrypted file: text.enc

And the encryption program source code: cbc_xor.py

import sys

IV = 'lionhaxe'

def xor(a,b):
    c = ''
    for i in range(0,min(len(a),len(b))):
        c = c + chr(ord(a[i]) ^ ord(b[i]))
    return c

def zero_pad(data, align):
    if len(data) % align != 0:
        data = data + ''.join([chr(0) for _ in range(0, align - (len(data) % align))])
    return data

def encrypt(plaintext, key, iv):
    assert(len(key) == BLOCKLEN)
    assert(len(iv) == BLOCKLEN)
    plaintext = zero_pad(plaintext, BLOCKLEN)
    ciphertext = ''
    for i in range(0, len(plaintext), BLOCKLEN):
        ciphertext = ciphertext + xor(xor(plaintext[i:i+BLOCKLEN], iv), key)
        iv = ciphertext[i:i+BLOCKLEN]
    return ciphertext

def decrypt(ciphertext, key, iv):
    assert(len(key) == BLOCKLEN)
    assert(len(iv) == BLOCKLEN)
    assert(len(ciphertext) % BLOCKLEN == 0)
    plaintext = ''
    for i in range(0, len(ciphertext), BLOCKLEN):
        plaintext = plaintext + xor(xor(ciphertext[i:i+BLOCKLEN], key), iv)
        iv = ciphertext[i:i+BLOCKLEN]
    return plaintext

if __name__ == '__main__':
    if len(sys.argv) != 5:
        print('Usage: {} [d|e] key inputfile outputfile'.format(sys.argv[0]))
    key = sys.argv[2][0:8]
    inputtext = open(sys.argv[3], 'r').read()

    if sys.argv[1] == 'd':
        outputtext = decrypt(inputtext, key, IV)
    elif sys.argv[1] == 'e':
        outputtext = encrypt(inputtext, key, IV)
        print('Incorrect mode {}, should be d(ecryption) or e(ncryption)'.format(sys.argv[1]))
    open(sys.argv[4], 'w').write(outputtext)

What’s the problem? Well, in CBC, combining the previous ciphertext block with the plaintext block is also done with a XOR and this is a commutative operation. Because the previous ciphertext block and the IV are all known we can in fact cancel out the CBC mode and transform it into a ECB.

You could write your own tool or simply use my the encryption tool in decryption with a null key. Then you can recover the key with a traditionnal frequency analysis tool like xortool.

% python2 cbc_xor.py d 0000000000000000 text.enc text_no_cbc
% xortool text_no_cbc -c ' '
The most probable key lengths:
   1:   10.2%
   4:   12.4%
   8:   19.1%
  10:   7.8%
  12:   9.0%
  14:   6.6%
  16:   12.8%
  20:   6.5%
  24:   9.0%
  32:   6.6%
Key-length can be 4*n
2 possible key(s) of length 8:
Found 2 plaintexts with 95.0%+ printable characters
See files filename-key.csv, filename-char_used-perc_printable.csv

And xortool very nicely gives us the output file:

% cat xortool_out/1.out
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key. Block ciphers operate as important elementary components in the design of many cryptographic protocols, and are widely used to implement encryption of bulk data.

The modern design of block ciphers is based on the concept of an iterated product cipher. In his seminal 1949 publication, Communication Theory of Secrecy Systems, Claude Shannon analyzed product ciphers and suggested them as a means of effectively improving security by combining simple operations such as substitutions and permutations.[1] Iterated product ciphers carry out encryption in multiple rounds, each of which uses a different subkey derived from the original key. One widespread implementation of such ciphers, named a Feistel network after Horst Feistel, is notably implemented in the DES cipher.[2] Many other realizations of block ciphers, such as the AES, are classified as substitution-permutation networks.[3]

The publication of the DES cipher by the United States National Bureau of Standards (subsequently the U.S. National Institute of Standards and Technology, NIST) in 1977 was fundamental in the public understanding of modern block cipher design. It also influenced the academic development of cryptanalytic attacks. Both differential and linear cryptanalysis arose out of studies on the DES design. As of 2016 there is a palette of attack techniques against which a block cipher must be secure, in addition to being robust against brute force attacks.

Even a secure block cipher is suitable only for the encryption of a single block under a fixed key. A multitude of modes of operation have been designed to allow their repeated use in a secure way, commonly to achieve the security goals of confidentiality and authenticity. However, block ciphers may also feature as building-blocks in other cryptographic protocols, such as universal hash functions and pseudo-random number generators.


The wikipedia text is my fault: I had no idea for a text long enough to work with xortool so I submitted the challenge with a lorem ipsum :) The organizer put more effort into it than I did by copying wikipedia ^^

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License .