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

[Vlad-Andrei BĂDOIU (78692) <vlad_andrei.badoiu@xxxxxxxxxxxxxxx>]

Hey Simon,

Please see my response inline.

Thanks,

Vlad

On 15.10.2019 15:30, Simon Kuenzer wrote:
> Hey,
>
> can't we keep MWC together with ChaCha and compile one of them 
> according the the configuration? It is fine if you mark MWC in the 
> menu as insecure and take ChaCha as default. I could imagine that MWC 
> is faster - is this true?

I think that we could keep them together, although the difference in 
performance between MWC and ChaCha should be minimal. Furthermore, the 
boot time with ChaCha should be faster if the performance option is 
selected due to the fact that MWC has the following iteration:

for (i = 3; i < 4096; i++)
        r->Q[i] = r->Q[i - 3] ^ r->Q[i - 2] ^ PHI ^ i;

Lastly, most operating system seem to be using ChaCha[1] so I am not 
sure if it we should keep MWC as an option. Let me know what you think.

[1] https://en.wikipedia.org/wiki/Salsa20#ChaCha20_adoption

>
>
> Thanks,
>
> Simon
>
> On 15.10.19 13:57, Vlad-Andrei BĂDOIU (78692) wrote:
>> 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)
>
> If you keep mwc.c and add chacha.c, you may want to move some 
> functions (like this one) to a generic place.
>
>> @@ -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);
>>
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel