# Breaking DES with Python
Solutions to the third homework assignment for the NWI-IBC023 Cryptography course, spring 2015, Radboud University Nijmegen.

See the LICENSE file for the license & copyright information.

## Dependencies
Python 2.7.6 (other versions may work) with libraries: Crypto, sys, getopt, os.path, binascii, random, time

## Files

### des-demo.py (exercise i)
Encrypt or decrypt a specified message using a specified key with DES. See `des-demo.py -h` for usage.

### des-test.sh
Test des-demo.py using the test vectors from the assignment.

### nthkey.py (exercise ii)
Demonstration of the working of the `nthKey(n)` method. No command line parameters, edit the number on the last line for another `n`.

### 2des-demo.py (exercise iii)
2DES using two random keys: chooses two random keys with the right parity using `nthKey(n)`, then performs 2DES on ten random plaintexts using those keys. See `2des-demo.py -h` for usage.

### break.py (exercise iv)
Breaking 2DES using a known-plaintext attack. Supply at least a plaintext (`-p`) and a ciphertext (`-c`), possibly also a keylength (`-l`). There is an option to save the dictionary to a file (`-s`) if you're planning to reuse it. 

There is detailed timing information for the second stage of the attack: the time used by `nthKey()`, `DES.decrypt()` and finding values in the dictionary.

Example:

    $ ./break.py -p 6be6065663da8d2c -c 4d0ed7812caeee83 -l 16
    Making dictionary (p:6be6065663da8d2c;l:16)... 1.429026s
    Finding matches... 1.618808s
    Key generation:      0.403714s
    Decryption:          1.048049s
    Matching dictionary: 0.046321s
    k1: 0101010101011afb; k2: 0101010101012073

## Concrete break
I was given the following plaintext-ciphertext pairs:

    0123456789ABCDEF e0ac28c346fb8de5
    1122334455667788 49e4857e94f9655d
    99aabbccddeeff00 b5a2eefb51b04401

Breaking these (on the Lenovo described under Benchmarks):

    $ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24
    Making dictionary (p:0123456789abcdef;l:24)... 417.513822s
    Finding matches... 419.125502s
    Key generation:      102.954099s
    Decryption:          269.473773s
    Matching dictionary: 15.134741s
    k1: 0101010101164613; k2: 0101010102a719c2
    $ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24
    Making dictionary (p:1122334455667788;l:24)... 386.554364s
    Finding matches... 424.907323s
    Key generation:      106.151418s
    Decryption:          271.449573s
    Matching dictionary: 15.2167599999s
    k1: 0101010101164613; k2: 0101010102a719c2
    $ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24
    Making dictionary (p:99aabbccddeeff00;l:24)... 394.505993s
    Finding matches... 431.637707s
    Key generation:      109.764972s
    Decryption:          274.681545s
    Matching dictionary: 14.4759990001s
    k1: 0101010101164613; k2: 0101010102a719c2

We find k1 = `0101010101164613`; k2 = `0101010102a719c2`.

## Benchmarks

### Lenovo U410, i7-3517U @ 1.9GHz, 8GB RAM, 16GB /swap, Ubuntu 14.04
Creating dictionary: 417.5s, 386.5s, 394.5s (**avg: 399.5s**)  
Finding matches: 419.1s, 424.9s, 431.6s (**avg: 425.2s**)

The exact log is in the Concrete Break section above.

### Lilo
Creating dictionary: 286.8s, 283.6s, 273.0s (**avg: 281.1s**)  
Finding matches: 301.6s, 285.6s, 292.2s (**avg: 293.1s**)

    $ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24
    Making dictionary (p:0123456789abcdef;l:24)... 286.83s
    Finding matches... 301.56s
    Key generation:      64.47s
    Decryption:          200.23s
    Matching dictionary: 9.27s
    k1: 0101010101164613; k2: 0101010102a719c2
    $ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24
    Making dictionary (p:1122334455667788;l:24)... 283.55s
    Finding matches... 285.63s
    Key generation:      60.66s
    Decryption:          189.44s
    Matching dictionary: 9.27s
    k1: 0101010101164613; k2: 0101010102a719c2
    $ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24
    Making dictionary (p:99aabbccddeeff00;l:24)... 272.96s
    Finding matches... 292.21s
    Key generation:      63.89s
    Decryption:          191.04s
    Matching dictionary: 9.41s
    k1: 0101010101164613; k2: 0101010102a719c2