Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <cover.1670778651.git.david.keisarschm@mail.huji.ac.il>
 <7c16cafe96c47ff5234fbb980df9d3e3d48a0296.1670778652.git.david.keisarschm@mail.huji.ac.il>
 <01ade45b-8ca6-d584-199b-a06778038356@meta.com>
In-Reply-To: <01ade45b-8ca6-d584-199b-a06778038356@meta.com>
From:   Amit Klein <aksecurity@gmail.com>
Date:   Tue, 13 Dec 2022 00:35:24 +0200
Message-ID: <CANEQ_+KDR+kC=hYhTtNeQuSTp+-Dg0tRx-9MzJKQ2zH++fBGyQ@mail.gmail.com>
Subject: Re: [PATCH 2/5] Replace invocation of weak PRNG in kernel/bpf/core.c
To:     Yonghong Song <yhs@meta.com>
Cc:     david.keisarschm@mail.huji.ac.il,
        Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        John Fastabend <john.fastabend@gmail.com>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>, Yonghong Song <yhs@fb.com>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>,
        "David S. Miller" <davem@davemloft.net>,
        Eric Dumazet <edumazet@google.com>,
        Jakub Kicinski <kuba@kernel.org>,
        Paolo Abeni <pabeni@redhat.com>, ilay.bahat1@gmail.com,
        bpf@vger.kernel.org, linux-kernel@vger.kernel.org,
        netdev@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Mon, Dec 12, 2022 at 8:03 PM Yonghong Song <yhs@meta.com> wrote:
>
>
>
> On 12/11/22 2:16 PM, david.keisarschm@mail.huji.ac.il wrote:
> > From: David <david.keisarschm@mail.huji.ac.il>
> >
> > We changed the invocation of
> >   prandom_u32_state to get_random_u32.
> >   We deleted the maintained state,
> >   which was a CPU-variable,
> >   since get_random_u32 maintains its own CPU-variable.
> >   We also deleted the state initializer,
> >   since it is not needed anymore.
> >
> > Signed-off-by: David <david.keisarschm@mail.huji.ac.il>
> > ---
> >   include/linux/bpf.h   |  1 -
> >   kernel/bpf/core.c     | 13 +------------
> >   kernel/bpf/verifier.c |  2 --
> >   net/core/filter.c     |  1 -
> >   4 files changed, 1 insertion(+), 16 deletions(-)
> >
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
[...]
> Please see the discussion here.
> https://lore.kernel.org/bpf/87edtctz8t.fsf@toke.dk/
> There is a performance concern with the above change.
>

I see. How about using (in this instance only!) the SipHash-based
solution which was the basis for prandom_u32() starting with commit
c51f8f88d705 (v5.10-rc1) up until commit d4150779e60f (v5.19-rc1)?
Copying the relevant snippets (minus comments, for brevity) from
/lib/random32.c and /include/linux/prandom.h from that era (the 32
random bits are generated by prandom_u32() at the bottom; I didn't
bother with initialization, and I don't know if the per_cpu logic is
needed here, or perhaps some other kind of locking, if any):


#define PRND_SIPROUND(v0, v1, v2, v3) ( \
v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \
v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \
v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \
v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \

)

struct siprand_state {
    unsigned long v0;
    unsigned long v1;
    unsigned long v2;
    unsigned long v3;
};

static DEFINE_PER_CPU(struct siprand_state, net_rand_state)
__latent_entropy;   // do we actually need this? -AK

static inline u32 siprand_u32(struct siprand_state *s)
{
    unsigned long v0 = s->v0, v1 = s->v1, v2 = s->v2, v3 = s->v3;

    PRND_SIPROUND(v0, v1, v2, v3);
    PRND_SIPROUND(v0, v1, v2, v3);
    s->v0 = v0;  s->v1 = v1;  s->v2 = v2;  s->v3 = v3;
    return v1 + v3;
}


u32 prandom_u32(void)
{
    struct siprand_state *state = get_cpu_ptr(&net_rand_state);
    u32 res = siprand_u32(state);

    trace_prandom_u32(res);
    put_cpu_ptr(&net_rand_state);
    return res;
}
EXPORT_SYMBOL(prandom_u32);