[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Minios-devel] [UNIKRAFT PATCH 1/2] lib/ukswrand: Replace LCR with ChaCha20


  • To: "minios-devel@xxxxxxxxxxxxx" <minios-devel@xxxxxxxxxxxxx>
  • From: Vlad-Andrei BĂDOIU (78692) <vlad_andrei.badoiu@xxxxxxxxxxxxxxx>
  • Date: Tue, 15 Oct 2019 11:57:29 +0000
  • Accept-language: en-US
  • Arc-authentication-results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=stud.acs.upb.ro; dmarc=pass action=none header.from=stud.acs.upb.ro; dkim=pass header.d=stud.acs.upb.ro; arc=none
  • Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=kV7EsQakc+IV93jA2Fs6AJogkqepdOUUSFRIPtMovr0=; b=UsPSs2uHFwVE1MeeEgzcgdbI+sNvB4m0yxvR0ACHzywXyN20l6HZvbxGTv7y+ifXIHiHbIpMBgYLc46j0NJxeNNX8J9OlF2cLTtqaSi9dIc8FQxcpdoSCJHGIWw2GbcUA5h2o1mKofuCMrfmKN73sEf4T+RW69cC0zx73GS82BWdb0D6iTC2vN8FtWxHqsfjyPRx++pMaCO94nVk0C5rsriIF9XCmyZEfQetTO74s+NIpY8YpKH8ipOshpa359fZASke1u/p9yBg2AJNsAjFxK92cj4plQhjDPa3wDkDDVugHYxHY8TpfXqFSHalVZG0IuFE5aR6/YC5fFIDQZ2mvw==
  • Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=MRn6xZMBJuOpmF8O9FcTTv9gkFhweCzsz8WSR47yHm8x8yd7nQLIN6bKnHu+BkHeB3XUHyuYm3BW1vCUuFTacQjHjyqHc7EtE1U+3pyPAYpanbTMvMJnOZsJuWaVoktykRVyMqhBt0Bs1fTN/XWJFEN1hnzS0HVLGUj2SQ42hQqj7kAS3AG7k+g9MdAv7DH1DOrVRWV4GYi7rb7ncRkuWJXASyVy8I7zyX6z4M1Y1TjR+THm67+0Fo1g/op5QgA5Trlg5sbuWurqltFhq6sqHS5LONGoR4j6pMd6MPcdiDSKbE+HkCSir7CKkVz2OUl3xs9TNEOLRZjxMT5rkAEFEg==
  • Authentication-results: spf=none (sender IP is ) smtp.mailfrom=vlad_andrei.badoiu@xxxxxxxxxxxxxxx;
  • Cc: "felipe.huici@xxxxxxxxx" <felipe.huici@xxxxxxxxx>, "costin.lup@xxxxxxxxx" <costin.lup@xxxxxxxxx>, Vlad-Andrei BĂDOIU (78692) <vlad_andrei.badoiu@xxxxxxxxxxxxxxx>
  • Delivery-date: Tue, 15 Oct 2019 11:57:37 +0000
  • List-id: Mini-os development list <minios-devel.lists.xenproject.org>
  • Thread-index: AQHVg0+4XVd7VzXMUUmXFDcHM+Sk5w==
  • Thread-topic: [UNIKRAFT PATCH 1/2] lib/ukswrand: Replace LCR with ChaCha20

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)
@@ -114,7 +112,7 @@ ssize_t uk_swrand_fill_buffer(void *buf, size_t buflen)
 static void _uk_swrand_ctor(void)
 {
        uk_pr_info("Initialize random number generator...\n");
-       uk_swrand_init_r(&uk_swrand_def, CONFIG_LIBUKSWRAND_INITIALSEED);
+       uk_swrand_init_r(&uk_swrand_def);
 }
 
 UK_CTOR_FUNC(UK_SWRAND_CTOR_PRIO, _uk_swrand_ctor);
-- 
2.20.1


_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel

 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.