Pseudo random number generation lab solution

SEED Labs – Pseudo Random Number Generation Lab 1 Pseudo Random Number Generation Lab Copyright © 2018 Wenliang Du, Syracuse University. The development of this document was partially funded by the National Science Foundation under Award No. 1303306 and 1718086. This work is licensed under a Creative Commons Attribution-NonCommercialShareAlike 4.0 International License. A human-readable summary of (and not a substitute for) the license is the following: You are free to copy and redistribute the material in any medium or format. You must give appropriate credit. If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. You may not use the material for commercial purposes. 1 Overview Generating random numbers is a quite common task in security software. In many cases, encryption keys are not provided by users, but are instead generated inside the software. Their randomness is extremely important; otherwise, attackers can predict the encryption key, and thus defeat the purpose of encryption. Many developers know how to generate random numbers (e.g. for Monte Carlo simulation) from their prior experiences, so they use the similar methods to generate the random numbers for security purpose. Unfortunately, a sequence of random numbers may be good for Monte Carlo simulation, but they may be bad for encryption keys. Developers need to know how to generate secure random numbers, or they will make mistakes. Similar mistakes have been made in some well-known products, including Netscape and Kerberos. In this lab, students will learn why the typical random number generation method is not appropriate for generating secrets, such as encryption keys. They will further learn a standard way to generate pseudo random numbers that are good for security purposes. This lab covers the following topics: • • • • Pseudo random number generation Mistakes in random number generation Generating encryption key The /dev/random and /dev/urandom device files Lab Environment. This lab has been tested on our pre-built Ubuntu 16.04 VM, which can be downloaded from the SEED website. 2 2.1 Lab Tasks Task 1: Generate Encryption Key in a Wrong Way To generate good pseudo random numbers, we need to start with something that is random; otherwise, the outcome will be quite predictable. The following program uses the current time as a seed for the pseudo random number generator. Listing 1: ”Generating a 128-bit encryption key” #include #include #include #define KEYSIZE 16 SEED Labs – Pseudo Random Number Generation Lab 2 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"); } The library function time() returns the time as the number of seconds since the Epoch, 1970-01-01 00:00:00 +0000 (UTC). Run the code above, and describe your observations. Then, comment out Line À, run the program again, and describe your observations. Use the observations in both cases to explain the purpose of the srand() and time() functions in the code. 2.2 Task 2: Guessing the Key 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 in Task 1. 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 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. You can use the date command to print out the number of seconds between a specified time and the Epoch, 1970-01-01 00:00:00 +0000 (UTC).