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

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

Hey Simon,

On 15.10.2019 16:49, Simon Kuenzer wrote:
> Hey Vlad,
>
> On 15.10.19 14:56, Vlad-Andrei BĂDOIU (78692) wrote:
>> 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
>
> Hum, these are actually good points. But I still think we should keep 
> both for now - also to demonstrate how we can plug-in different 
> algorithms. I would expect that we have even more implementations in 
> the future. What do you think? I am thinking that we should set the 
> secure configuration as default.
I agree, but I think that we should only keep cryptographically secure 
algorithms in the future. For the v2 I'll add a config option that lets 
the user chose between algorithms.
>
>>
>>>
>>>
>>> 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
>>>> +
>
> I would actually introduce a second choice which configures the seed 
> generation. Only if the user select the option to take a pre-compiled 
> seed, the prompt of LIBUKSWRAND_INITIALSEED should be visible.
In this case I'll remove LIBUKSWRAND_PERFORMANCE and keep only the 
option to take a pre-compiled seed.
>
>>>>    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
>
> The detailed struct defintion should actually go to the corresponding 
> C files. So, you would have the prototype only:
>
>     struct uk_swrand;
>
> The extern struct needs to be a pointer:
>
>     extern struct uk_swrand *uk_swrand_def;
>
> or you move uk_swrandr_randr() to the generic code C file that also 
> initializes the default random number generator according to the menu 
> configuration (the library constructor).
I'll move the struct defintion to the corresponding C file. I'm trying 
to keep the changes to a minimum since this patch series is suppose to 
add a new algorithm.
>
>
>>>>    };
>>>>      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)
>>>> +{
>
> I think this function could be also generic. Could be used for both, 
> MWC and ChaCha. But I would provide it publicly on the API: 
> uk_swrandr_gen_seed(), this way you could still have multiple 
> instances of number generators (e.g., per CPU if you wish) and 
> initialize them individually.
I agree.
>
>
>>>> +    __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
>
> This else case you do not need in the code. You could use KConfig 
> syntax to unlock the RDRAND way of gnerating on x86 only.
Could you provide me with an example

> There can be also other sources, like using the current timestamp 
> which we may want to add (maybe as default for non x86?). Having the 
> seed compileable could be useful to have for debugging code that uses 
> random numbers. The sequence of random numbers is then always the 
> same. Obviously this should not be standard.
That sounds good. I'll keep rdrand for x86 and the current timestamp for 
arm as the default option if the pre-compiled seed is not selected.
>
>>>> +    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);
>
> I would not change the signature, just do:
>
>     uk_swrand_init_r(&uk_swrand_def, uk_swrandr_gen_seed());
Noted.
>
>>>>    }
>>>>      UK_CTOR_FUNC(UK_SWRAND_CTOR_PRIO, _uk_swrand_ctor);
>>>>
>
>
> What do you think?
>
> Thanks,
>
> Simon
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel