Keccak Hashing for Kernel RNG

December 5th, 2019

With the measurements done, now it is time to cement the Keccak hashes into the RNG module. I have also implemented a feature request for user-settable key, and fixed a small bug.

As for the reason for delay with preparation of this vpatch, it is rather embarassing and outlined in the top of the previous article.

The vpatch and seal are available here:

curl 'http://bvt-trace.net/vpatches/linux-keccak-rng.vpatch' > linux-keccak-rng.vpatch
curl 'http://bvt-trace.net/vpatches/linux-keccak-rng.vpatch.bvt.sig' > linux-keccak-rng.vpatch.bvt.sig

I implemented a feature request - a knob for setting the key for hashing. As Keccak does not have an explicit key argument, I use a user-provided buffer to set up the initial Keccak state, which is later used in all operations. The buffer can be of arbitrary length. The initial Keccak state is initialized early during boot:

static struct keccak_state init_keccak_state;

static int
rand_initialize(void)
{
        keccak_init(&init_keccak_state);
        return 0;
}
early_initcall(rand_initialize);

Populating the state with user input happens in set_hash_key:

static int
set_hash_key(const unsigned char __user *user_key, size_t key_len)
{
        size_t hashed = 0;
        size_t nbytes;
        int r = 0;
        unsigned long flags;
        u8 block[KECCAK_BLOCK_SIZE];

        spin_lock_irqsave(&outer_lock, flags);

        keccak_init(&init_keccak_state);
        while (hashed < key_len) {
                nbytes = min_t(size_t, key_len - hashed, sizeof(block));
                if (copy_from_user(&block[0], &user_key[hashed], nbytes)) {
                        r = -EINVAL;
                        keccak_init(&init_keccak_state);
                        goto out;
                }
                keccak_update(&init_keccak_state, &block[0], nbytes);
                hashed += nbytes;
        }
        keccak_pad(&init_keccak_state);

out:
        spin_unlock_irqrestore(&outer_lock, flags);
        return r;
}

It receives a buffer with the user key as an argument and feeds the user-provided data into the state. Repeated calls to this function don't update the key, but rather replace it. This can be changed if someone wants to use multiple files as a key (i.e. ksum or gpg binary, and a file with randomness from FG), or wants to have a key resettable only through a reboot.

set_hash_key is exposed as a new ioctl, available only to the root user:

@@ -668,6 +427,20 @@
                kfifo_reset(&inner_ring);
                kfifo_reset(&outer_ring);
                return 0;
+       case RNDSETKEY:
+               if (!capable(CAP_SYS_ADMIN))
+                       return -EPERM;
+               s_p = (size_t __user *)p;
+               if (get_user(key_len, s_p++))
+                       return -EFAULT;
+               u_p = (uintptr_t __user *)s_p;
+               if (get_user(key_ptr, u_p))
+                       return -EFAULT;
+               retval = set_hash_key( (const char __user *)key_ptr, key_len);
+               if (retval < 0)
+                       return retval;
+               return 0;
+
        default:
                return -EINVAL;
        }
@@ -731,10 +504,11 @@

The definition of RNDSETKEY is added to relevant headers, but it has to be propagated to kernel-headers package to become available to userspace applications.

I considered making a /proc/sys/kernel entry for invoking set_hash_key initially, but then decided against it:

  • the invocation would still have to happen in one write(2) call from userspace, which would disqualify using standard tools like cat for writing larger files;
  • in case key is resettable on reboot and additional writes update the key, I would have to add a yet another file to apply keccak padding, which would only increase the complexity of the RNG component.

Currently I am satisfied with the tradeoffs taken. If you are not, please drop a comment below.

What I did expose in the /proc/sys/kernel/, is the hash of the key used on the machine:

static int
proc_do_key_hash(struct ctl_table *table, int write,
                void __user *buffer, size_t *lenp, loff_t *ppos)
{
        struct ctl_table fake_table;
        unsigned char buf[2*KECCAK_DIGEST_SIZE+1];
        u8 hash[KECCAK_DIGEST_SIZE];
        struct keccak_state kst;
        unsigned long flags;
        size_t i = 0;

        spin_lock_irqsave(&outer_lock, flags);
        random_init_keccak(&kst);
        spin_unlock_irqrestore(&outer_lock, flags);

        while (i < sizeof(hash)) {
                u8 tmpbuf[KECCAK_BLOCK_SIZE];
                size_t nbytes = min_t(size_t, sizeof(tmpbuf), sizeof(hash) - i);
                keccak_squeeze(&kst, tmpbuf);
                memcpy(&hash[i], tmpbuf, nbytes);
                i += nbytes;
        }

        bin2hex(buf, hash, sizeof(hash));
        buf[2*KECCAK_DIGEST_SIZE] = 0;

        fake_table.data = buf;
        fake_table.maxlen = sizeof(buf);

        return proc_dostring(&fake_table, write, buffer, lenp, ppos);

}

Available at /proc/sys/kernel/random/key_hash:

+       {
+               .procname       = "key_hash",
+               .maxlen         = (2*KECCAK_DIGEST_SIZE),
+               .mode           = 0444,
+               .proc_handler   = proc_do_key_hash,
+       },

All hashing operations (good, fast, self) start with this state, which is achieved in random_init_keccak:

static void
random_init_keccak(struct keccak_state *kst)
{
        keccak_init(kst);
        memcpy(&kst->st, &init_keccak_state.st, sizeof(kst->st));
}

And their code is almost the same as in previous article:

static int
hash_good(const unsigned char __user *data, size_t data_len)
{
        struct keccak_state kst;
        u8 s_block[KECCAK_BLOCK_SIZE];
        size_t nbytes;
        size_t hashed = 0;
        size_t squeezed = 0;

        random_init_keccak(&kst);
        while (hashed < data_len) {
                nbytes = data_len - hashed;
                nbytes = min_t(size_t, sizeof(s_block), nbytes);
                if (copy_from_user(s_block, data + hashed, nbytes)) {
                        return -EFAULT;
                }
                keccak_update(&kst, &s_block[0], nbytes);
                hashed += nbytes;
        }

        keccak_pad(&kst);
        while (squeezed < data_len) {
                nbytes = data_len - squeezed;
                nbytes = min_t(size_t, sizeof(s_block), nbytes);
                keccak_squeeze(&kst, s_block);
                kfifo_in(&outer_ring, s_block, nbytes);
                squeezed += nbytes;
        }
        return 0;
}

static int
hash_fast(const unsigned char __user *data, size_t data_len, size_t output_len)
{
        struct keccak_state kst;
        u8 s_block[KECCAK_BLOCK_SIZE] = {0};
        size_t nbytes;
        size_t hashed = 0;

        data_len = min_t(size_t, data_len, sizeof(s_block));
        if (copy_from_user(&s_block[0], data, data_len)) {
                return -EFAULT;
        }

        random_init_keccak(&kst);
        keccak_update(&kst, s_block, data_len);
        keccak_pad(&kst);
        while (hashed < output_len) {
                nbytes = output_len - hashed;
                nbytes = min_t(size_t, sizeof(s_block), nbytes);
                keccak_squeeze(&kst, s_block);
                nbytes = kfifo_in(&outer_ring, s_block, nbytes);
                hashed += nbytes;
        }
        return 0;
}

static void
_outer_self_hash(size_t to_hash)
{
        struct keccak_state kst;
        u8 s_block[KECCAK_BLOCK_SIZE];
        size_t nbytes, peeked;
        size_t hashed = 0;

        random_init_keccak(&kst);
        while (hashed < to_hash) {
                nbytes = min_t(size_t, sizeof(s_block), (to_hash - hashed));
                peeked = kfifo_out_peek_forward(&outer_ring, s_block, nbytes);
                keccak_update(&kst, &s_block[0], nbytes);
                keccak_pad(&kst);
                keccak_squeeze(&kst, s_block);
                nbytes = kfifo_in(&outer_ring, s_block, nbytes);
                hashed += nbytes;
        }
}

The bug fix prevents the situation where unprivileged user could write to the inner ring through /dev/urandom. Now this is prevented by a security check in random_write:

static ssize_t
random_write(struct file *file, const char __user *buffer,
             size_t count, loff_t *ppos)
{
        if (!capable(CAP_SYS_ADMIN)) {
                return -EPERM;
        }
        return _random_write(buffer, count);
}

There is a new application for setting the user hash key:

#include <stdlib.h>
#include <stdio.h>
#include <sys/ioctl.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <linux/random.h>
#include <errno.h>
#include <string.h>

#define MY_RNDSETKEY       _IOW( 'R', 0x7, int [2] )

struct {
        size_t size;
        void *buf;
} user_key;

static void
read_user_key(const char *path)
{
        struct stat st;
        int fd = open(path, O_RDONLY);
        if (fd == -1) {
                fprintf(stderr, "Cannot open key file %s: %s", path, strerror(errno));
                exit(EXIT_FAILURE);
        }
        fstat(fd, &st);
        user_key.size = st.st_size;
        user_key.buf = mmap(0, user_key.size, PROT_READ, MAP_PRIVATE, fd, 0);
        if (user_key.buf == MAP_FAILED) {
                fprintf(stderr, "Cannot map key file %s: %s", path, strerror(errno));
                exit(EXIT_FAILURE);
        }
        close(fd);
}

int main(int argc, char *argv[])
{
        int fd;
        int r;

        if (argc != 2) {
                fprintf(stderr, "usage: %s key_file\n", argv[0]);
                exit(EXIT_FAILURE);
        }
        fd = open("/dev/random", O_RDWR);
        if (fd == -1) {
                fprintf(stderr, "Error opening file: %s\n", strerror(errno));
                exit(EXIT_FAILURE);
        }
        read_user_key(argv[1]);
        r = ioctl(fd, MY_RNDSETKEY, &user_key);
        if (r == -1) {
                fprintf(stderr, "Error setting hash key: %s\n", strerror(errno));
                exit(EXIT_FAILURE);
        }
        return 0;
}

And the inner ring feeder has seen minor simplifications:

@@ -24,7 +24,6 @@
         exit(EXIT_FAILURE);
     }
     cfmakeraw(&term);
-    term.c_cc[VMIN] = 255;
     r = cfsetspeed(&term, B115200);
     if (r == -1) {
         fprintf(stderr, "Error setting serial speed: %s\n", strerror(errno));
@@ -49,17 +48,13 @@
     out = open("/dev/random", O_WRONLY);
     while (1) {
         char buf[4096];
-        ssize_t nread = 0;
-        while (nread != sizeof(buf)) {
-            usleep(500000);
-            ssize_t l = read(in, &buf[nread], sizeof(buf) - nread);
-            if (l == -1) {
-                fprintf(stderr, "Read failed: %s\n", strerror(errno));
-                exit(EXIT_FAILURE);
-            }
-            nread += l;
+        ssize_t nread = read(in, &buf[0], sizeof(buf));
+        if (nread == -1) {
+            fprintf(stderr, "Read failed: %s\n", strerror(errno));
+            exit(EXIT_FAILURE);
         }
         write(out, &buf[0], nread);
+        usleep(500000);
     }
     return 0;
 }

As for future directions, I indeed have no further plans of larger scope so far: this work was done because I had a FG and because it was interesting for me to do this work, the ugliness of the original design was discovered only later; so it followed logically for me that this is a task to do. Of course, there is always more work to do:

  • checking which new 'packets of death' were discovered;
  • general security hardening;
  • integration into TMSR-OS.

I am sure more substantial changes will be made as TMSR-OS is created and used in practice.

4 Responses to “Keccak Hashing for Kernel RNG”

  1. Congrats on getting this done!

    As MP previously noted:

    > Ripping out kernel RNG

    This however is a major priority ; especially because it can turn the currently worked-upon cuntoo from a flavour project some group stylistically flavours to a must-have item with no possible competition in the professional (as opposed to toy&smartphone) IT space.

    Cheers to that.

    As for future directions, I indeed have no further plans of larger scope so far:

    I think sorting out the integration into TMSR OS is the highest priority. The security hardening and so forth can be planned and done once we have a stable base. My starting point towards that end is determining what should be used from Cuntoo and/or what can be used from Gales.

    Given you installed the former earlier this year, how about you take the later for a spin and write an installation report, or even better a comparison ?

  2. bvt says:
    2

    Thank you!

    Yes, I agree with the plan. I can install Gales for a try and make a write-up, though the expected delivery date for this is after 20.12.2019, and I can't promise any specific date yet.

  3. Cool; when you do have an expected delivery for the Gales write-up, please share your update in #trilema.

    Enjoy your holidays!

  4. [...] December 5th, bvt published his vpatch and article to Cement Keccak Hashing into Kernel RNG, continuing his prior work of ripping out Linux kernel RNG and replacing it with a driver that [...]

Leave a Reply