Write a Python or C program to guess the key

Question

Key generation program in C:

    #include <stdio.h>  
    #include <stdlib.h>  
    #include <time.h>
    #define KEYSIZE 16
    void main()
    {
      int i;
      char key[KEYSIZE];
      printf("%lld\n", (long long) 
      time(NULL));
      srand (time(NULL));
      for (i = 0; i< KEYSIZE; i++){
      key[i] = rand()%256;
      printf("%.2x", (unsigned char)key[i]);
    }
    printf("\n");
    }

Scenario:

On April 17, 2018, Alice finished her tax return, and she saved the return (a PDF file) on her disk. To protect the file, she encrypted the PDF file using a key generated from the program described above.She wrote down the key in a notebook, which is securely stored in a safe. A few month later, Bob broke into her computer and gets a copy of the encrypted tax return. Since Alice is CEO of a big company, this file is very valuable.

Bob cannot get the encryption key, but by looking around Alice’s computer, he saw the key-generation program, and suspected that Alice’s encryption key may be generated by the program. He also noticed the timestamp of the encrypted file, which is “2018-04-17 23:08:49”. He guessed that the key may be generated within a two-hour window 1 before the file was created.

Since the file is a PDF file, which has a header. The beginning part of the header is always the version number. Around the time when the file was created, PDF-1.5 was the most common version, i.e., the header starts with %PDF-1.5, which is 8 bytes of data. The next 8 bytes of the data are quite easy to predict as well. Therefore, Bob easily got the first 16 bytes of the plaintext. Based on the meta data of the encrypted file,he knows that the file is encrypted using aes-128-cbc. Since AES is a 128-bit cipher, the 16-byte plaintext consists of one block of plaintext, so Bob knows a block of plaintext and its matching ciphertext. Moreover, Bob also knows the Initial Vector (IV) from the encrypted file (IV is never encrypted). Here is what Bob knows:

• Plaintext 255044462d312e350a25d0d4c5d80a34
• Ciphertext d06bf9d0dab8e8ef880660d2af65aa82
• IV 09080706050403020100A2B2C2D2E2F2

Your job is to help Bob find out Alice’s encryption key, so you can decrypt the entire document. You should write a program to try all the possible keys. If the key was generated correctly, this task will not be possible. However, since Alice used time() to seed her random number generator, you should be able to find out her key easily.

Answer 1

I agree with multithr3at3d that this question smells like a homework problem. But, it's a fun exercise - and more importantly, it highlights the reason that strong random number generators are so critical in cryptography. It also illustrates how easy it is for a hacker to brute-force an encryption key, given a small amount of known plaintext and some insight into how the key may have been generated.

Alice's encryption key is: 95fa2030e73ed3f8da761b4eb805dfd7.

To confirm:

echo -n '255044462d312e350a25d0d4c5d80a34' | xxd -r -p | openssl aes-128-cbc -nopad -e -K  95fa2030e73ed3f8da761b4eb805dfd7 -iv 09080706050403020100A2B2C2D2E2F2 -nosalt | xxd -p

produces:

d06bf9d0dab8e8ef880660d2af65aa82

To find this, first modify the C program that you included in your question, as shown below. A for loop is added using a variable (t) that iterates starting at an epoch time that is well before the time thought to have been used to seed the random number generator, and ending at an epoch time well after. Then, use t (instead of time) in the srand function, like so, to produce a key for each value of t:

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>
#define KEYSIZE 16

void main() {
    long int t;
    int i;

    for(t=1523920129; t<=1523920129+3*60*60*24; t++) {  
        char key[KEYSIZE];
        srand (t);
        for (i = 0; i< KEYSIZE; i++){
            key[i] = rand()%256;
            printf("%.2x", (unsigned char)key[i]);
        }
        printf("\n");
    }

}

This will produce a list of keys, for each value of t, like so:

ad064166051c52a4a2c474b8ddfaea15
00ebeeac8d31e686baae2cfa0c14f240
.
.
.
20669457b11ec10f5f201d3b847b0e20

Use redirection to write these keys to a file, keys.txt. Then, write a short python program, that reads the keys from this file, and tries each of them in an AES-CBC function, along with the given plaintext and iv, and tests for the case where the known ciphertext is produced, like so:

import binascii
from Crypto.Cipher import AES   

with open('./keys.txt') as fp:
    keys=fp.readlines()

for keyhex in keys:
    keyhex=keyhex.rstrip()

    iv=binascii.unhexlify('09080706050403020100A2B2C2D2E2F2'.lower()) 
    key=binascii.unhexlify(keyhex.lower()) 
    plaintext=binascii.unhexlify('255044462d312e350a25d0d4c5d80a34'.lower())  

    encryptor=AES.new(key, AES.MODE_CBC, iv)
    ciphertext=encryptor.encrypt(plaintext)

    if(ciphertext==binascii.unhexlify('d06bf9d0dab8e8ef880660d2af65aa82'.lower())): 
        print ('iv: ', binascii.hexlify(iv))
        print ('plaintext: ', binascii.hexlify(plaintext))
        print ('key: ', binascii.hexlify(key))
        print ('ciphertext: ', binascii.hexlify(ciphertext))

This produces the output below, revealing the key that Alice used to produce the known ciphertext given the known plaintext and iv:

iv:  b'09080706050403020100a2b2c2d2e2f2'
plaintext:  b'255044462d312e350a25d0d4c5d80a34'
key:  b'95fa2030e73ed3f8da761b4eb805dfd7'
ciphertext:  b'd06bf9d0dab8e8ef880660d2af65aa82'

We can verify this using openssl, by way of the command near the top of this answer.