ChaCha20 is a cryptographically secure pseudorandom number generator. We replace
the existing implementation, which is not secure, with ChaCha20. The
implementation is based on the reference implementation of the author[1].
We add a new config option, LIBUKSWRAND_PERFORMANCE to disable the use of
rdrand for seed generation. Currently, the seed is generated randomly only on
X64.
[1]
http://cr.yp.to/streamciphers/timings/estreambench/submissions/salsa20/chacha8/ref/chacha.c
Signed-off-by: Vlad-Andrei Badoiu <vlad_andrei.badoiu@xxxxxxxxxxxxxxx>
---
lib/ukswrand/Config.uk | 15 ++++--
lib/ukswrand/Makefile.uk | 2 +-
lib/ukswrand/include/uk/swrand.h | 91 ++++++++++++++++++++++++++++++--
lib/ukswrand/mwc.c | 54 +++++++++----------
4 files changed, 124 insertions(+), 38 deletions(-)
diff --git a/lib/ukswrand/Config.uk b/lib/ukswrand/Config.uk
index c58371bb..e4ed6521 100644
--- a/lib/ukswrand/Config.uk
+++ b/lib/ukswrand/Config.uk
@@ -6,18 +6,25 @@ menuconfig LIBUKSWRAND
if LIBUKSWRAND
choice
prompt "Algorithm"
- default LIBUKSWRAND_MWC
+ default LIBUKSWRAND_CHACHA
-config LIBUKSWRAND_MWC
- bool "Multiply-with-carry"
+config LIBUKSWRAND_CHACHA
+ bool "ChaCha20"
help
- Use multiply-with-carry algorithm
+ Use ChaCha20 algorithm
endchoice
config LIBUKSWRAND_INITIALSEED
int "Initial random seed"
default 23
+config LIBUKSWRAND_PERFORMANCE
+ bool "Performance settings over security"
+ default y
+ help
+ Use LIBUKSWRAND_INITIALSEED for the initial seed, the PRG is no
+ longer cryptographically secure
+
config LIBUKSWRAND_DEVFS
bool "Register random and urandom device to devfs"
select LIBDEVFS
diff --git a/lib/ukswrand/Makefile.uk b/lib/ukswrand/Makefile.uk
index 6cf1223e..b890c818 100644
--- a/lib/ukswrand/Makefile.uk
+++ b/lib/ukswrand/Makefile.uk
@@ -3,6 +3,6 @@ $(eval $(call addlib_s,libukswrand,$(CONFIG_LIBUKSWRAND)))
CINCLUDES-$(CONFIG_LIBUKSWRAND) += -I$(LIBUKSWRAND_BASE)/include
CXXINCLUDES-$(CONFIG_LIBUKSWRAND) += -I$(LIBUKSWRAND_BASE)/include
-LIBUKSWRAND_SRCS-$(CONFIG_LIBUKSWRAND_MWC) += $(LIBUKSWRAND_BASE)/mwc.c
+LIBUKSWRAND_SRCS-$(CONFIG_LIBUKSWRAND_CHACHA) += $(LIBUKSWRAND_BASE)/mwc.c
LIBUKSWRAND_SRCS-$(CONFIG_LIBUKSWRAND_DEVFS) += $(LIBUKSWRAND_BASE)/dev.c
LIBUKSWRAND_SRCS-y += $(LIBUKSWRAND_BASE)/getrandom.c
diff --git a/lib/ukswrand/include/uk/swrand.h b/lib/ukswrand/include/uk/swrand.h
index 8523e207..3b6545dc 100644
--- a/lib/ukswrand/include/uk/swrand.h
+++ b/lib/ukswrand/include/uk/swrand.h
@@ -45,18 +45,99 @@ extern "C" {
#endif
struct uk_swrand {
-#ifdef CONFIG_LIBUKSWRAND_MWC
- __u32 Q[4096];
- __u32 c;
- __u32 i;
+#ifdef CONFIG_LIBUKSWRAND_CHACHA
+ int k;
+ __u32 input[16], output[16];
#endif
};
extern struct uk_swrand uk_swrand_def;
-void uk_swrand_init_r(struct uk_swrand *r, __u32 seed);
+/* This value isn't important, as long as it's sufficiently asymmetric */
+static const char sigma[16] = "expand 32-byte k";
+
+void uk_swrand_init_r(struct uk_swrand *r);
__u32 uk_swrand_randr_r(struct uk_swrand *r);
+static inline __u32 _uk_rotl32(__u32 v, int c)
+{
+ return (v << c) | (v >> (32 - c));
+}
+
+static inline void _uk_quarterround(__u32 x[16], int a, int b, int c, int d)
+{
+ x[a] = x[a] + x[b];
+ x[d] = _uk_rotl32(x[d] ^ x[a], 16);
+
+ x[c] = x[c] + x[d];
+ x[b] = _uk_rotl32(x[b] ^ x[c], 12);
+
+ x[a] = x[a] + x[b];
+ x[d] = _uk_rotl32(x[d] ^ x[a], 8);
+
+ x[c] = x[c] + x[d];
+ x[b] = _uk_rotl32(x[b] ^ x[c], 7);
+}
+
+static inline void
+_uk_salsa20_wordtobyte(__u32 output[16], const __u32 input[16])
+{
+ __u32 i;
+
+ for (i = 0; i < 16; i++)
+ output[i] = input[i];
+
+ for (i = 8; i > 0; i -= 2) {
+ _uk_quarterround(output, 0, 4, 8, 12);
+ _uk_quarterround(output, 1, 5, 9, 13);
+ _uk_quarterround(output, 2, 6, 10, 14);
+ _uk_quarterround(output, 3, 7, 11, 15);
+ _uk_quarterround(output, 0, 5, 10, 15);
+ _uk_quarterround(output, 1, 6, 11, 12);
+ _uk_quarterround(output, 2, 7, 8, 13);
+ _uk_quarterround(output, 3, 4, 9, 14);
+ }
+
+ for (i = 0; i < 16; i++)
+ output[i] += input[i];
+}
+
+static inline void _uk_key_setup(struct uk_swrand *r, __u32 k[8])
+{
+ int i;
+
+ for (i = 0; i < 8; i++)
+ r->input[i + 4] = k[i];
+
+ for (i = 0; i < 4; i++)
+ r->input[i] = ((__u32 *)sigma)[i];
+}
+
+static inline void _uk_iv_setup(struct uk_swrand *r, __u32 iv[2])
+{
+ r->input[12] = 0;
+ r->input[13] = 0;
+ r->input[14] = iv[0];
+ r->input[15] = iv[1];
+}
+
+static inline __u32 _get_random_seed(void)
+{
+ __u32 val;
+
+#ifdef CONFIG_LIBUKSWRAND_PERFORMANCE
+ return CONFIG_LIBUKSWRAND_INITIALSEED;
+#endif
+
+#ifdef CONFIG_ARCH_X86_64
+ asm volatile ("rdrand %%eax;"
+ : "=a" (val));
+#else
+ /* TODO: Generate the seed randomly on ARM */
+ val = CONFIG_LIBUKSWRAND_INITIALSEED;
+#endif
+ return val;
+}
/* Uses the pre-initialized default generator */
/* TODO: Add assertion when we can test if we are in interrupt context */
/* TODO: Revisit with multi-CPU support */
diff --git a/lib/ukswrand/mwc.c b/lib/ukswrand/mwc.c
index 85abf0c6..21c91f3a 100644
--- a/lib/ukswrand/mwc.c
+++ b/lib/ukswrand/mwc.c
@@ -39,8 +39,6 @@
#include <uk/assert.h>
#include <uk/ctors.h>
-/* https://stackoverflow.com/questions/9492581/c-random-number-generation-pure-c-code-no-libraries-or-functions */
-#define PHI 0x9e3779b9
#define UK_SWRAND_CTOR_PRIO 1
struct uk_swrand uk_swrand_def;
@@ -50,45 +48,45 @@ struct uk_swrand uk_swrand_def;
*/
static void _uk_swrand_ctor(void);
-void uk_swrand_init_r(struct uk_swrand *r, __u32 seed)
+void uk_swrand_init_r(struct uk_swrand *r)
{
__u32 i;
UK_ASSERT(r);
+ /* Initialize chacha */
+ // TODO: add config option to enable/disable this
+ __u32 k[8], iv[2];
- r->Q[0] = seed;
- r->Q[1] = seed + PHI;
- r->Q[2] = seed + PHI + PHI;
- for (i = 3; i < 4096; i++)
- r->Q[i] = r->Q[i - 3] ^ r->Q[i - 2] ^ PHI ^ i;
+ for (i = 0; i < 8; i++)
+ k[i] = _get_random_seed();
- r->c = 362436;
- r->i = 4095;
+ iv[0] = _get_random_seed();
+ iv[1] = _get_random_seed();
+
+ _uk_key_setup(r, k);
+ _uk_iv_setup(r, iv);
+
+ r->k = 16;
}
__u32 uk_swrand_randr_r(struct uk_swrand *r)
{
- __u64 t, a = 18782LL;
- __u32 x, y = 0xfffffffe;
- __u32 i, c;
+ __u32 res;
- UK_ASSERT(r);
+ for (;;) {
+ _uk_salsa20_wordtobyte(r->output, r->input);
+ r->input[12] = r->input[12] + 1;
+ if (r->input[12] == 0)
+ r->input[13]++;
- i = r->i;
- c = r->c;
+ if (r->k < 16) {
+ res = r->output[r->k];
+ r->k += 1;
+ return res;
+ }
- i = (i + 1) & 4095;
- t = a * r->Q[i] + c;
- c = (t >> 32);
- x = t + c;
- if (x < c) {
- x++;
- c++;
+ r->k = 0;
}
-
- r->i = i;
- r->c = c;
- return (r->Q[i] = y - x);
}
ssize_t uk_swrand_fill_buffer(void *buf, size_t buflen)
