Week 7: Keylogging

Now that work on gathering random bytes from online sources has finished, I have begun working on tracking keystrokes and attempting to build a record of timestamps and cycles after boot-up for each key pressed. This has been more challenging than expected because each major operating system platform handles the raw input of the keyboard differently. The first platform I worked on was Mac OS X. I thought the UNIX-based OS would use device event files to record keystrokes but Apple changed the architecture so that the same information was in a much more obscure location within Application Services. Amir gave me a Macbook Air to work on but we did not have the passwords for any of the accounts. Instead of having to load a new OS on the machine, Adam let me borrow the Macbook Pro he had been working with. Eventually, the only solution I could come up with was to use logKextClient, a software that is able to capture all keyboard input. While it records the timespan range for the collected data, it does not assign a timestamp to each individual key pressed, let alone include the number of CPU cycles that have passed.

Trying to find a keylogger solution for Windows and Linux have proven similarly difficult. While I would like to test a simple script which reads the Linux device event file, that script failed when Ubuntu was loaded as a virtual machine on the MBP. In fact, the device event file for the keyboard was empty. This is probably because keyboard input is routed through the VM interface and the data never gets written to the event file. I will need to read more about device event files before I can work on the Linux platform. I found PyKeylogger, a Python extension that is supposed to work for both Windows and Linux. I downloaded it on my Windows 8 machine but the installation process always fails. I will have to take a deeper look into my options for Windows as well.

Meanwhile, I have started my Stanford online courses in cryptography and startup engineering. Both courses will give me more knowledge and experience to help me with my project on cryptographic randomness. 

Week 6: More Studying

At the beginning of this week, I made some finishing touches to our online entropy collection project. I made my script for the NIST Beacon source more dynamic. Since the source provides new random bytes every minute, I set up the script to identify the last timestamp it left off at and start collecting data from a minute after it. Later on, Amir told me that after running the cron job to collect data from online sources, there was an issue with the file naming. I had to rethink the algorithm I had made for run_all.py. By switching the steps where I moved the files from the tmp directory to daily_results and renamed the files, I was able to fix this problem.

I have been continuing my study of Python through the Lutz manual. I have found it to be an extremely powerful language because of its cross-platform system programming capabilities. The os and glob modules make automation of any command line algorithms trivial. Having Python as part of my skill set will make it much easier for me to write scripts moving forward.

After finding out about it through a friend, I enrolled for the Stanford online cryptography course, which begins on June 17^th. I feel that this course will expand my knowledge of cryptography beyond the basic concepts I learned in EECS 482. The course syllabus includes DES and AES block ciphers, collision resistant hashing, key derivation functions, Diffie-Hellman, RSA, and Merkle puzzles as well as several other topics.

On Friday, our team met with Professor Fu to discuss future work. We talked with Ari Juels about using subtle frequency variations in RFIDs to obtain randomness as well as thermal chamber testing. The first step is to order the RFIDs and with readers in order to begin testing. Those should take around a week to arrive to the lab. Until then, we will continue to focus on entropy available in desktop computers.

Week 5: Finishing up Online Sources

This week, I finished up our work with gathering entropy from online sources. I was able to circumvent the usage of twill for downloading random bytes from randomserver.dyndns.org by simply appending the form entry data to the URL. This way, I could utilize the Python URL library and the script to download 4096 random bytes became trivial. After that, I brought all of the online sources together. I standardized the output files of each script that was written and created a tmp folder for the output files to be stored in. Then, I wrote run_all.py, which uses the Python os extension to run each script from the command line. Once all the temporary files have been stored in tmp, the run_all script determines the timestamp, appends it to the file names, and moves the files to ./daily_results in the randomness github repository. Amir has set up a Cron job to execute run_all.py a couple times each day on his BICUSPID account, so the daily_results directory will continue to grow larger as we collect random bytes every day.

Throughout the week, I have been reading two different books to gain a general understanding of the Linux kernel and Python programming, which will help once I start writing scripts to isolate entropy sources and their collection for the Linux RNG.

Understanding the Linux Kernel (Bovet & Cesati): One important thing I learned from this book is that the open-source nature of the kernel has its advantages and disadvantages. On one hand, there is a strong base of Linux developers who are very talented programmers that understand how to make the operating system compact yet powerful. On the other hand, as I witnessed in trying to understand the RNG by looking at /drivers/char/random.c, the source code can get extremely messy. Another part of the overview of the kernel gave me an idea for a new source of entropy for the RNG. Linux dynamically links modules that contain code for file system management, device drivers, and other features so that main memory is not burdened with kernel code that may even go unused most of the time. If the time between module linking and unlinking events could be measured, this would provide a strong source of entropy, especially since the delta would be relatively large compared to other sources such as keystrokes or mouse clicks.   

Programming Python (Lutz): I decided to take a thorough, in-depth approach to learning Python since I found it to be a very powerful scripting language when writing my scripts for online sources. I have been getting accustomed to the syntax and writing simple Python programs, experimenting with the interpreter behavior. In the book, I have covered keeping records, using dictionaries of dictionaries as a database, Pickle files, and shelves. I left off on the advantages of object-oriented programming within Python (structure, encapsulation, customization, etc.) and the syntax for defining classes.

Week 4: Scripting Difficulties

I went down to Tennessee to attend my cousin’s high school graduation commencement and spend my Memorial Day vacation with the family. When I came back to the lab on Wednesday, I started out by trying to dig deeper into the paper on boot-time entropy in embedded devices. I tried to decipher the confusing diagrams used in the Results and Analysis section, ranging from histograms to per-test distributions to graphs of entropy over correlation threshold. While I still do not fully understand some of the statistical analysis that was done, I believe I have a better understanding of the underlying conclusion. Even with the techniques proposed to gather boot-time entropy, embedded devices are still at a disadvantage because they lack randomness from radios that wireless devices can utilize and previously saved entropy that desktops can use. These headless devices need to gather strong entropy immediately following the boot, before a network connection even occurs.

Next, I watched Dr. Avi Wigderson’s talk on Randomness and Pseudorandomness, which had been sent to me by Amir. The talk introduced several interesting real-life applications of the importance of randomness such as the P vs. NP problem, which aims to find a deterministic problem that is exponentially hard to solve – something which is trivial for non-deterministic problems. Perhaps the most intriguing part of Dr. Wigderson’s lecture, however, was his observation that randomness is relative to the computing power of the observer. He uses the example of a coin toss. An observer equipped with only his or her own eyesight will probably not be able to correctly determine the outcome of the toss with greater than 50% success rate. On the other hand, if the observer is equipped with several high-speed cameras, state-of-the-art sensors, and sophisticated momentum-measuring software, he or she will be able to predict the outcome with 100% success.

Finally, I have been facing many obstacles in writing a script to automatically download random bytes from randomserver.dyndns.org. I am used to programming on Linux, so it has taken me some time to get used to my programming environment on Windows 8. I installed Python 3.3 and twill, a Python extension that automates HTML form filling and submission. I was not able to successfully install twill, and I spent a considerable time trying to figure out what was going wrong. Eventually, I found out that the open-source code for twill was written for Python 2.5 in which ‘print’ is not a function and therefore does not wrap the argument in parentheses. I briefly attempted to write a script that would fix the print statements in all the Python scripts that were part of the twill code. I quickly realized, however, that not all the print statements outputted to the terminal, which would make fixing the scripts much more difficult. Also, there might be other differences between versions 2.5 and 3.3 that might make the installation fail anyway. My next step will be to install Python 2.5 so I can successfully install twill and get the random byte download script to work.

Week 3: Back to Research Papers

I started this week attempting to write a script to download random bytes from randomserver.dyndns.org. The issue I was having was that a web page presented a GUI for downloading a given number of bytes but the website, which streams true random numbers from a hardware RNG connected to the server, did not have additional resources for automating the streaming. Adam was able to help me out by pointing me to a script he wrote for a website with a similar problem. He used the twill extension for Python which automates HTML form filling and submission, which is exactly what I needed. I modified his script for the web site I was working on but when I tried to test the script, I found that the server was down. Since completing the script, the web site has only been active intermittently, so it has been difficult for me to properly debug it. I will keep checking the site daily to see if it is back up and stable so that the script can be finished up.

Meanwhile, Amir sent me two more papers on sources of entropy that have been recently published. The paper on boot-time entropy in particular is extremely relevant to our project and provided a lot of insight into providing sufficient randomness at all times through the Linux kernel.

Welcome to the Entropics: Boot-time Entropy in Embedded Devices

This paper starts by making the claim that a device cannot be successfully booted until it is able to provide high-entropy randomness to applications. It then introduces three methods for providing this high entropy before the traditional blocking pool for /dev/random is filled. In the first method, the number of cycles required to run each function in start_kernel is recorded. The advantage of this method is that it provides high entropy with little overhead (about 0.00016 seconds added to boot time) and can run with a single kernel thread and interrupts disabled. While every source that accounted for the non-determinism in execution time could not be identified, the paper noted that clock domain crossing and variation in DRAM access latencies among devices were major factors. The second method creates entropy by measuring the decay of DRAM storage in a live system when refresh is disabled. The decay rate of a given bit is affected by manufacturing variations, temperature, the value of the bit, and other factors. This method is tricky to deploy since it relies on memory controller operations which differ based on the DUT. The last technique measures the amount of time required for a PLL to lock onto the new output frequency. This time varies due to power supply stability, accuracy and jitter of the source oscillator, and manufacturing process differences. Even though it provides the highest bitrate of the three methods, it relies on a strong understanding of the given SoC.

Recommendation for the Entropy Sources Used for Random Bit Generation

This document specifies the design and requirements for a NIST-approved entropy source. The entropy originates from a noise source, which then may need to be digitized to produce random binary output. Optional conditioning functions are necessary to reduce bias that may arise due to a number of different factors. The conditioning functions will provide the overall output of the entropy source. Health testing functionality is required to detect malfunctions in the noise source or bias beyond the bounds for which the conditioning functions can remedy. Health tests include startup tests on all components, continuous tests on the noise source that run as long as the system is live, and on-demand tests that require more time and resources than continuous tests. On the simpler end, the Repitition Count Test and Adaptive Proportion Test do basic checks for abnormal proportions of a given sample in a fixed bitstring length. Extensive statistical analysis is performed to verify that the estimated min-entropy provided by the source is sufficient.

Week 2: Gathering Entropy from Online Sources

This week, my assignment was to collect and record output from true random number generators that are available online. These online resources typically utilize quantum interactions to generate entropy and provide random bits for personal use free of charge. Unfortunately, one of the websites I tried to extract bits from, LavaRnd, has been decommissioned indefinitely. I am currently working on obtaining random bits from randomserver.dyndns.org, which utilizes a hardware RNG. While the site has a page with a GUI for downloading a given number of random bytes, it does not contain any additional resources to directly stream from the server, so I will need to think of a way to write a script that automates the downloading process so a sufficient number of random bytes can be obtained. During this week, I was able to successfully write scripts for two of the web sites, and I uploaded the code to the randomness/onlineResources github repository.

Australian National University Quantum Random Numbers Server

A lab at ANU measures real-time quantum fluctuations of phase and amplitude within a vacuum to yield an ultra-high bandwidth random number stream. The hardware generates this stream at 5.7 Gbit/sec with no daily limit on downloading, so my script could theoretically be looped without interruption given that the bottleneck on stream rate is the internet bandwidth. The site provided a link to the anurandom github project which offers tools and sample code for downloading the random bits from the server in several different languages. I utilized Python because of the presence of a web page on the site that displays 1024 live random bits, making the extraction and storage code trivial. Therefore, my script pulls 124 random bytes and stores them as binary data in a newly created anu_random.bin file within the same directory.

Humboldt University of Berlin QRNG Service

At the Department of Physics of the Humboldt University, the Nano-Optics lab uses state-of-the-art photon timing instrumentation and data processing to generate random numbers based on photon arrival times. The device constantly delivers 150 Mbit/sec of data, so once again the script could run without interruption only limited by internet bandwidth. The site offers the libQRNG C library to interface with the server as well as demo code. I removed SSL security from the demo program because the library utilized outdated Linux SSL libraries rather than OpenSSL, rendering that portion of the code obsolete. I also modified the code so that it does not block waiting for user input, allowing the program to be looped indefinitely. I had to register as a user of the service and my user name and password is required to start a connection with the server. As it is now, this C program downloads 25 MB of random binary data from the server and stores it in qrng_output.bin within the same directory. 

Week 1: Getting up to Speed

This summer, I will be working with Adam Norton and Amir Rahmati on the cryptographic randomness project in the SPQR lab. Our primary goal is to identify sources of entropy that provide sufficient randomness for a truly secure cryptographic system, particularly on devices with limited computing power. For the first week, I read five different research papers on cryptographic randomness to get up to speed on the scope of the project. Included below is a brief summary of each paper as well as the major lessons and conclusions that will be helpful to our team.

Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

This paper details a large-scale experiment aiming to examine the security of random number generation in important cryptographic protocols. The study specifically targets TLS and SSH, performing a scan of the entire IPv4 address space to obtain TLS certificates and SSH host keys. The data shows that headless or embedded devices do not generate sufficient entropy for the PRNG in the protocols to create distinct keys. 5.57% of TLS hosts and 9.60% of SSH hosts shared keys with other hosts because of this problem. Furthermore, by exploiting weaknesses in RSA and DSA, the private keys of 0.5% of TLS hosts and 1.06% of SSH hosts could be computed using the public key. One reason embedded devices do not generate sufficient entropy is because they do not have the resources of traditional PCs, which utilize keyboard input, mouse movement, disk accesses, and other data to provide entropy. However, the final component of the experiment exposes a major reason that embedded devices do not generate sufficient entropy. The most popular software package for implementing a PRNG is /dev/urandom. The study finds that this Linux package exhibits a boot-time entropy hole that causes its random number generator to produce deterministic output. In one case, the non-blocking entropy pool which supplies urandom did not get data from the input pool until 66 seconds after boot, even though OpenSSH seeded its PRNG using urandom well before that. The paper provides helpful advice for anyone trying to create a secure embedded device: avoid using factory default keys or certificates, ensure sources of entropy are effective, test cryptographic randomness on the device, and use hardware random number generators whenever possible.

Analysis of the Linux Random Number Generator

 The goal of this paper is to decipher the complex open-source code describing the Linux RNG that supplies /dev/random and /dev/urandom. The operating system collects entropy through mouse movement, keyboard input, specific interrupts, and disk accesses. This entropy is funneled into a 512 byte primary pool in the form of 2 32-bit words. The first word describes the timing of the event in milliseconds and the second word describes the event type. The primary pool provides entropy bits to the secondary and urandom pools, both of which store up to 128 bytes. The secondary pool outputs to /dev/random, which blocks until the entropy counter of the secondary pool is at a sufficient value. The urandom pool outputs to /dev/urandom, which does not block. Complex mathematics is involved in determining the amount of entropy entering each pool and, in turn, incrementing the entropy counter. The study also finds a vulnerability in the forward security of the system due to the fact that output from the pools is calculated after the state of the pool is updated. An algorithm is presented that can compute the five previous states of a pool with a high entropy counter based on the current state with an overhead of 2⁶⁴ using O(1) memory. This issue can be avoided by computing the output before updating the state of the pool. Additionally, the study notes that OpenWRT, a Linux distribution for wireless routers, is much less secure because it lacks strong sources of entropy such as mouse and keyboard input or disk accesses. The only source it uses are network interrupts, which are easily visible to an external adversary. Finally, the paper provides solutions for a denial-of-service attack based on continuous calls to the blocking /dev/random. This can be avoided by creating a quota per user or group on the consumption of random bits.

How to Generate Cryptographically Strong Sequences of Pseudo Random Bits

With the motivation of devising a robust, secure random number generator in mind, this paper starts out with an excellent coin-flipping analogy to define the key concept that randomness is relative to a specific model of computing with a specific amount of computational resources. Basically, an observer with no resources is unable to determine the outcome of a coin flip with greater than 50% success. However, an observer equipped with a computer capable of taking pictures and tracking the motion of the coin and efficiently calculating its speed and momentum may be able to predict the outcome with greater than 50% success. Keeping this in mind, a random number generator proposed which takes as an input a random seed value s and outputs a sequence of pseudo random bits. The bits are polynomially many in the length of s, each bit can be calculated in time polynomial in the length of s, and, given the first k pseudo-random bits not not s, it is computationally infeasible to calculate the k+1^st bit in the sequence with better than 50% success.

When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography

There are two different components to this paper. The first is a case study on the nature of snapshots used in virtual machines to reset the state of the system and the security vulnerabilities that arise due to this technique. This study has significant implications because VM managers such as VMWare and VirtualBox are used at the consumer and business level to efficiently manage computing infrastructure and the increasingly popular cloud computing relies on these management services as well. The study found that if a client runs multiple times from the same full reset snapshot, it may end up sending the same premaster secret value required for the RSA protocol to different servers. In terms of TLS servers, a vulnerability arises if multiple servers are run from the same snapshot. If a snapshot of the server was taken after startup, it would save the state of the RNG based on the boot-time seed value. Reuse of that state would lead to multiple servers using the same randomness in DSA. Fixing this vulnerability requires ensuring that the RNG gets sufficient entropy after the snapshot and that OS sources such as /dev/random and /dev/urandom generate randomness immediately preceding the cryptographic operation. The second part of the paper explores the idea of hedging currently deployed cryptography to safeguard against bad randomness and therefore mitigate the risk of RNG failures. The proposed hedging framework preprocesses RNG-derived randomness with other inputs such as mouse and keyboard events to create pseudo randomness for cryptographic operations with very little overhead. The framework can be applied to the OpenSSL code base, which is the cryptographic library for the TLS protocol.

A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications

In the introduction, this paper explains the important difference between random number generators and pseudo random number generators. RNGs use an entropy source to create randomness. On the other hand, PRNGs use random, unpredictable seed values as inputs to generate multiple “pseudorandom” numbers. Therefore, by default, a PRNG requires an RNG to operate off a seed value. The paper then presents a statistical suite of 15 tests to determine whether RNGs and PRNGs produce sufficient randomness. The first test examines a sequence of random bits and assesses the closeness of the fraction of ones to ½ to determine whether the number of ones and zeros is approximately the same as what would be expected in a truly random sequence. The next 14 tests depend on whether this first one passes. The next test checks the proportion of ones within M-bit blocks. For block size M=1, this test is the same as the first test. Another test focuses on the number of runs in the sequence, where a run is defined as an uninterrupted sequence of identical bits. This test determines whether the oscillation between zeros and ones is too fast or too slow. Other tests utilize mathematical techniques such as discrete Fourier transforms, template matching, and Maurer’s test.