Coder Social home page Coder Social logo

randkit's Introduction

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!

randkit's People

Contributors

vrasneur avatar

Watchers

Mojtaba Kamyabi avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.