UEFI over BeagleBone Black: Notes

The Tianocore/EDK2 project provides an opensource implementation of UEFI specification. It has its own Python-scripted build system that supports configuring the build parameters on the go using build metadata files [http://tianocore.sourceforge.net/wiki/Build_Description_Files]. These files decide which library instances are required for a package; which instance implementation is to be used, what interfaces it exports, compiler specifications for the package and the generated image’s flash layout.

I am working to bring up UEFI support for a BeagleBone Black. Currently, I am using u-boot’s SPL to call the UEFI image (by placing generated .Fd on an MMC as “u-boot.img”), which, in turn, would provide the UEFI console and kernel loading functionality.

Since SPL does memory, stack and irq initialization, the SEC/PEI phases have little work. As per the BBB SoC (an AM335x), all multicore and AArch64 code can be safely removed from the package. UART being similar to the 16550 module can be written to by implementing SerialPortLib accordingly. Console services can be made available only after the EFI_BOOT_SERVICES table has been populated, which requires DXE phase completion.


Advertisements

Some Notes on Randomness

Judging the ‘quality’ of random data is indeed a complex statistical problem. The dieharder suite has been designed around this issue, which consists of a number of tests that establish a criteria for an RNG to be good, and fail if it isn’t met. The tests differ significantly from each other; some of these may be easier to pass than the others.

A PRNG needs to be initialized using a ‘seed’, which may be taken from the machine-available sources of entropy (/dev/random, /dev/urandom on Linux). Since it works on deterministic algorithms, for the same seed, the PRNG produces the same results on each run. So, if the seed is compromised, the adversary may be able to predict the sequence produced by the PRNG. Since /dev/random and /dev/urandom are char devices, their concurrent reads from multiple applications will preserve the uniqueness of the data received by each application. This implies that if multiple PRNGs are being initialized at the same time, each of these receives a unique seed.

The OpenSSL PRNG, on Unix-like OSes it seeds itself using data obtained by reading /dev/urandom, /dev/random and /dev/srandom (on OpenBSD), spending 10 ms on each (openssl/crypto/rand/rand_unix.c). For the PRNG to be cryptographically secure, its initial seed must not become known. This, in case of OpenSSL, implies that the external devices it reads from must be reliable sources of randomness.

For machines that lack /dev/random as an option, Entropy Gathering Daemon can be used. It is a perl script which runs in the background, calling the programs available on the machine and using their results to slowly fill its entropy pool (egd.pl:175 – 321). OpenSSL can be configured to use EGD as a source of randomness. A virtual machine running on QEMU can also be fed from EGD but this is slow due to EGD’s way of working and is being investigated. Also, if EGD is not running in the `–bottomless` mode, it often blocks when being used with QEMU. So, it is not advisable to be used as of now.

Another source of randomness could be the hardware random number generators. These claim to be cryptographically secure and unpredictable, and are often very fast. But these are only as reliable as their manufacturer. Certain Intel processors provide an instruction that they claim returns reliable random numbers. But a recent revelation indicates that this instruction may have been rigged because of influence from the NSA. Therefore, depending on an HWRNG as the only source of randomness would be a bad idea. A better option is to just add this data to the main entropy pool along with data from other sources.

Dieharder Tests on a qemu VM – 3: Results II

Continued from Dieharder Tests on a qemu VM – 2: Results

Here are the results for running dieharder on a guest not feeding on the host’s entropy (i.e. invoking qemu without the virtio-rng-pci device). The test returns WEAK at a number of places, as opposed to the previous results, indicating that the entropy supplied to it isn’t completely random. This implies that using the virtio-rng-pci device is a good choice if there are no explicit sources of randomness available to the guest.

guest:entropy_avail stayed around 160 while running. The host, when not running a vm seemed to pass the dieharder suite.

#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
stdin_input_raw|  2.62e+06  | 762187023|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.83795012|  PASSED
      diehard_operm5|   0|   1000000|     100|0.91399772|  PASSED
  diehard_rank_32x32|   0|     40000|     100|0.99934932|   WEAK
    diehard_rank_6x8|   0|    100000|     100|0.75473508|  PASSED
   diehard_bitstream|   0|   2097152|     100|0.52888766|  PASSED
        diehard_opso|   0|   2097152|     100|0.99863189|   WEAK
        diehard_oqso|   0|   2097152|     100|0.99544153|   WEAK
         diehard_dna|   0|   2097152|     100|0.35600968|  PASSED
diehard_count_1s_str|   0|    256000|     100|0.55492562|  PASSED
diehard_count_1s_byt|   0|    256000|     100|0.93158424|  PASSED
 diehard_parking_lot|   0|     12000|     100|0.00682730|  PASSED
    diehard_2dsphere|   2|      8000|     100|0.60579818|  PASSED
    diehard_3dsphere|   3|      4000|     100|0.50801068|  PASSED
     diehard_squeeze|   0|    100000|     100|0.20780916|  PASSED
        diehard_sums|   0|       100|     100|0.03163035|  PASSED
        diehard_runs|   0|    100000|     100|0.91464960|  PASSED
        diehard_runs|   0|    100000|     100|0.76009031|  PASSED
       diehard_craps|   0|    200000|     100|0.83910125|  PASSED
       diehard_craps|   0|    200000|     100|0.17404472|  PASSED
 marsaglia_tsang_gcd|   0|  10000000|     100|0.42896571|  PASSED
 marsaglia_tsang_gcd|   0|  10000000|     100|0.34960417|  PASSED
         sts_monobit|   1|    100000|     100|0.26441569|  PASSED
            sts_runs|   2|    100000|     100|0.97799925|  PASSED
          sts_serial|   1|    100000|     100|0.99506951|   WEAK
          sts_serial|   2|    100000|     100|0.72894480|  PASSED
          sts_serial|   3|    100000|     100|0.88766272|  PASSED
          sts_serial|   3|    100000|     100|0.71821524|  PASSED
          sts_serial|   4|    100000|     100|0.27325832|  PASSED
          sts_serial|   4|    100000|     100|0.16764233|  PASSED
          sts_serial|   5|    100000|     100|0.39649567|  PASSED
          sts_serial|   5|    100000|     100|0.17208569|  PASSED
          sts_serial|   6|    100000|     100|0.75970039|  PASSED
          sts_serial|   6|    100000|     100|0.04285571|  PASSED
          sts_serial|   7|    100000|     100|0.05956044|  PASSED
          sts_serial|   7|    100000|     100|0.51915899|  PASSED
          sts_serial|   8|    100000|     100|0.02280669|  PASSED
          sts_serial|   8|    100000|     100|0.36128748|  PASSED
          sts_serial|   9|    100000|     100|0.42272524|  PASSED
          sts_serial|   9|    100000|     100|0.96531298|  PASSED
          sts_serial|  10|    100000|     100|0.90920764|  PASSED
          sts_serial|  10|    100000|     100|0.07381200|  PASSED
          sts_serial|  11|    100000|     100|0.56475893|  PASSED
          sts_serial|  11|    100000|     100|0.22136924|  PASSED
          sts_serial|  12|    100000|     100|0.63632280|  PASSED
          sts_serial|  12|    100000|     100|0.90584207|  PASSED
          sts_serial|  13|    100000|     100|0.98929282|  PASSED
          sts_serial|  13|    100000|     100|0.84940410|  PASSED
          sts_serial|  14|    100000|     100|0.51337504|  PASSED
          sts_serial|  14|    100000|     100|0.35658437|  PASSED
          sts_serial|  15|    100000|     100|0.69324168|  PASSED
          sts_serial|  15|    100000|     100|0.96847166|  PASSED
          sts_serial|  16|    100000|     100|0.90513868|  PASSED
          sts_serial|  16|    100000|     100|0.65808536|  PASSED
         rgb_bitdist|   1|    100000|     100|0.46915603|  PASSED
         rgb_bitdist|   2|    100000|     100|0.95162255|  PASSED
         rgb_bitdist|   3|    100000|     100|0.23686073|  PASSED
         rgb_bitdist|   4|    100000|     100|0.65453723|  PASSED
         rgb_bitdist|   5|    100000|     100|0.46193454|  PASSED
         rgb_bitdist|   6|    100000|     100|0.85670400|  PASSED
         rgb_bitdist|   7|    100000|     100|0.02560679|  PASSED
         rgb_bitdist|   8|    100000|     100|0.31628821|  PASSED
         rgb_bitdist|   9|    100000|     100|0.45408518|  PASSED
         rgb_bitdist|  10|    100000|     100|0.12875926|  PASSED
         rgb_bitdist|  11|    100000|     100|0.48889700|  PASSED
         rgb_bitdist|  12|    100000|     100|0.11948926|  PASSED
rgb_minimum_distance|   2|     10000|    1000|0.80584597|  PASSED
rgb_minimum_distance|   3|     10000|    1000|0.09039280|  PASSED
rgb_minimum_distance|   4|     10000|    1000|0.87310457|  PASSED
rgb_minimum_distance|   5|     10000|    1000|0.47373390|  PASSED
    rgb_permutations|   2|    100000|     100|0.97254452|  PASSED
    rgb_permutations|   3|    100000|     100|0.87507703|  PASSED
    rgb_permutations|   4|    100000|     100|0.43610221|  PASSED
    rgb_permutations|   5|    100000|     100|0.99864288|   WEAK
      rgb_lagged_sum|   0|   1000000|     100|0.58568154|  PASSED
      rgb_lagged_sum|   1|   1000000|     100|0.13875851|  PASSED
      rgb_lagged_sum|   2|   1000000|     100|0.94819967|  PASSED
      rgb_lagged_sum|   3|   1000000|     100|0.19215309|  PASSED
      rgb_lagged_sum|   4|   1000000|     100|0.57478843|  PASSED
      rgb_lagged_sum|   5|   1000000|     100|0.72827902|  PASSED
      rgb_lagged_sum|   6|   1000000|     100|0.58226183|  PASSED
      rgb_lagged_sum|   7|   1000000|     100|0.74428735|  PASSED
      rgb_lagged_sum|   8|   1000000|     100|0.56414577|  PASSED
      rgb_lagged_sum|   9|   1000000|     100|0.97272745|  PASSED
      rgb_lagged_sum|  10|   1000000|     100|0.88742338|  PASSED
      rgb_lagged_sum|  11|   1000000|     100|0.65596031|  PASSED
      rgb_lagged_sum|  12|   1000000|     100|0.31356087|  PASSED
     rgb_kstest_test|   0|     10000|    1000|0.52619545|  PASSED
     dab_bytedistrib|   0|  51200000|       1|0.77236000|  PASSED
             dab_dct| 256|     50000|       1|0.51011037|  PASSED
        dab_filltree|  32|  15000000|       1|0.57769621|  PASSED
        dab_filltree|  32|  15000000|       1|0.75930039|  PASSED
      rgb_lagged_sum|  13|   1000000|     100|0.32785148|  PASSED
       dab_filltree2|   0|   5000000|       1|0.31084546|  PASSED
       dab_filltree2|   1|   5000000|       1|0.13226028|  PASSED
      rgb_lagged_sum|  14|   1000000|     100|0.27358978|  PASSED
        dab_monobit2|  12|  65000000|       1|0.51741346|  PASSED

Dieharder Tests on a qemu VM – 1: Setup

Diehard suite is a collection of tests for random number generators. I recently used it on a virtual machine feeding on the /dev/urandom of it’s host.

The Setup:

Used Debian 7.2 as both the host and the guest. The virtio-rng-pci virtual device allows feeding entropy from the host to the guest since qemu 1.3.

Invoking qemu with

-device virtio-rng-pci

attaches host:/dev/random to guest:/dev/hwrng. This is usually slow (tried it; too slow on my laptop), because /dev/random blocks. So I used the following:

$ qemu-system-x86_64 debian.qcow -L pc-bios -enable-kvm \
  -object rng-random,filename=/dev/urandom,id=rng0 \
  -device virtio-rng-pci,rng=rng0

which ties the host:/dev/urandom to the guest:/dev/hwrng. To verify that this is happening, run

$ cat /sys/devices/virtual/misc/hw_random/rng_available
$ cat /sys/devices/virtual/misc/hw_random/rng_current

These should return `virtio`

Now that guest:/dev/hwrng is available, it can be used to feed other sources of entropy on the guest. This can be done using rngd – a daemon available with the rng-tools package. The file /etc/default/rng-tools lets you provide the source of input to rngd. Adding

HRNGDEVICE=/dev/hwrng

to the file and restarting the daemon

$ /etc/init.d/rng-tools start

begins mixing entropy into the kernel’s pool. If you were running low on entropy, there is a noticeable rise in guest:entropy_avail sometime after this, host:entropy_avail falls a little.

You can find an opensource implementation of the diehard tests here.

$ cat /dev/urandom | dieharder -a -g 200

begins dieharder with all (-a) tests on the data obtained from stdin (-g 200), i.e. the data piped from /dev/urandom

Keep looking at entropy_avail and notice a drop. (Reading from it too much also depletes entropy, so read less often).

 

Random Numbers, Linux’s Way

The primary contributors to randomness on Linux are the input devices (the keyboard and the mouse), the storage disk and the interrupts that occur while runtime. All of the information coming in from these sources is mixed up and added to the entropy pool, which is typically 4096 bits wide. The amount of available entropy can be found at `/proc/sys/kernel/random/entropy_avail`, which noticeably increases upon casually using the machine for some time, or even just moving the mouse around. Crudely, when an event occurs, it’s timestamp is paired with the device ID that caused this event, and this word is XOR-ed with the previous bits from the pool, and the so obtained word is added to the pool. This happens at `drivers/char/random.c`.

This isn’t so!

Linux provides two interfaces to the users to access entropy: /dev/random (blocking) and /dev/urandom (non-blocking). `/dev/random` is suited to high quality randomness needs, but when the available entropy goes down below a certain threshold,, it blocks until more entropy is gathered, i.e. it waits for more casual user activity and disk events. This can cause large setbacks if the machine is supposed to provide a crucial service to its users (like an HTTPS server that needs to serve private keys to tons of users connected to it).

`/dev/urandom` does not block. If the system is running low on entropy, it still keeps hashing the data from the entropy pool. This makes it less secure and unsuitable for generating SSH/SSL/GPG keys.

Every time a random number is generated, the kernel lowers it’s estimate of available entropy. From the random’s manpage,

[Linux’s PRNG] is designed for security, not speed, and is poorly suited to generating large amounts of random data. Users should be very economical in the amount of seed material that they read from /dev/urandom (and /dev/random); unnecessarily reading large quantities of data from this device will have a negative impact on other users of the device.

Servers are often headless machines–they don’t need a keyboard and a mouse attached to them. They’re operated remotely through ssh connections. This creates a problem: how do they gather reliable entropy? Sure, there are disk events and network events happening, but still, the entropy pool may run out because of the large amount of requests coming in. A solution is to deploy hardware random number generators. These devices usually gather the environmental noise and add it to the pool. Intel’s Ivy Bridge processors provide the RDRAND instruction that returns random numbers. Yet another way of handling this is the audio_entropyd and video_entropyd daemons, which collect randomness from an audio and video source respectively.

Related Articles: