Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1394601

Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG

From Jeffrey Walton <noloader@gmail.com>
Newsgroups linux.kernel
Subject Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG
Date 2016-05-04 20:30 +0200
Message-ID <rv9IB-Ky-1@gated-at.bofh.it> (permalink)
References <rufwK-6Ok-3@gated-at.bofh.it> <rufwK-6Ok-9@gated-at.bofh.it> <rv6hJ-5S0-51@gated-at.bofh.it> <rv95U-8tM-13@gated-at.bofh.it>
Organization linux.* mail to news gateway

Show all headers | View raw

On Wed, May 4, 2016 at 1:49 PM,  <tytso@mit.edu> wrote:
> On Wed, May 04, 2016 at 10:40:20AM -0400, Jeffrey Walton wrote:
>> > +static inline u32 rotl32(u32 v, u8 n)
>> > +{
>> > +       return (v << n) | (v >> (sizeof(v) * 8 - n));
>> > +}
>>
>> That's undefined behavior when n=0.
>
> Sure, but it's never called with n = 0; I've double checked and the
> compiler seems to do the right thing with the above pattern as well.

> Hmm, it looks like there is a "standard" version rotate left and right
> defined in include/linux/bitops.h.  So I suspect it would make sense
> to use rol32 as defined in bitops.h --- and this is probably something

bitops.h could work in this case, but its not an ideal solution. GCC
does not optimize the code below as expected under all use cases
because GCC does not recognize it as a rotate (see
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157):

    return (v << n) | (v >> (sizeof(v) * 8 - n));

And outside of special cases like Salsa, ChaCha and BLAKE2, the code
provided in bitops.h suffers UB on arbitrary data. So I think care
needs to be taken when selecting functions from bitops.h.

> that we should do for the rest of crypto/*.c, where people seem to be
> defininig their own version of something like rotl32 (I copied the
> contents of crypto/chacha20_generic.c to lib/chacha20, so this pattern
> of defining one's own version of rol32 isn't new).

Yeah, I kind of thought there was some duplication going on.

But I think bitops.h should be fixed. Many folks don't realize the
lurking UB, and many folks don't realize its not always optimized
well.

>> I think the portable way to do a rotate that avoids UB is the
>> following. GCC, Clang and ICC recognize the pattern, and emit a rotate
>> instruction.
>>
>>     static const unsigned int MASK=31;
>>     return (v<<n)|(v>>(-n&MASK));
>>
>> You should also avoid the following because its not constant time due
>> to the branch:
>>
>>     return n == 0 ? v : (v << n) | (v >> (sizeof(v) * 8 - n));
>>
>
> Where is this coming from?  I don't see this construct in the patch.

My bad... It was a general observation. I've seen folks try to correct
the UB by turning to something like that.

Jeff

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[RFC PATCH 0/3] random: replace urandom pool with a CRNG Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
  [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
    Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Stephan Mueller <smueller@chronox.de> - 2016-05-03 11:00 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG Jeffrey Walton <noloader@gmail.com> - 2016-05-04 19:00 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG tytso@mit.edu - 2016-05-04 19:40 +0200
        Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-04 20:00 +0200
    Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Stephan Mueller <smueller@chronox.de> - 2016-05-03 11:40 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Stephan Mueller <smueller@chronox.de> - 2016-05-04 08:30 +0200
    Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG Jeffrey Walton <noloader@gmail.com> - 2016-05-04 16:50 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG tytso@mit.edu - 2016-05-04 19:50 +0200
        Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG Jeffrey Walton <noloader@gmail.com> - 2016-05-04 20:30 +0200
          Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-04 20:40 +0200
            Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG tytso@thunk.org - 2016-05-04 21:10 +0200
              Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-04 23:00 +0200
              Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG John Denker <jsd@av8n.com> - 2016-05-04 23:50 +0200
                Re: better patch for linux/bitops.h John Denker <jsd@av8n.com> - 2016-05-05 00:00 +0200
                Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 03:40 +0200
                Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 04:50 +0200
                Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 05:00 +0200
                Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 05:10 +0200
                Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 05:40 +0200
                Re: better patch for linux/bitops.h Theodore Ts'o <tytso@mit.edu> - 2016-05-05 06:00 +0200
                Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 06:10 +0200
                Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 08:40 +0200
                Re: UB in general ... and linux/bitops.h in particular John Denker <jsd@av8n.com> - 2016-05-05 18:20 +0200
                Re: UB in general ... and linux/bitops.h in particular Andi Kleen <andi@firstfloor.org> - 2016-05-05 19:40 +0200
                Re: UB in general ... and linux/bitops.h in particular Jeffrey Walton <noloader@gmail.com> - 2016-05-06 04:30 +0200
                Re: better patch for linux/bitops.h Sandy Harris <sandyinchina@gmail.com> - 2016-05-05 23:40 +0200
                Re: better patch for linux/bitops.h tytso@mit.edu - 2016-05-06 00:20 +0200
                Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 00:30 +0200
                Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 00:40 +0200
                Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 02:20 +0200
                Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 00:00 +0200
                Re: linux/bitops.h John Denker <jsd@av8n.com> - 2016-05-05 00:10 +0200
                Re: linux/bitops.h Andi Kleen <andi@firstfloor.org> - 2016-05-05 01:10 +0200
                Re: linux/bitops.h John Denker <jsd@av8n.com> - 2016-05-05 02:20 +0200
                Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 03:30 +0200
                Re: linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 03:30 +0200
                Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 02:40 +0200
                Re: linux/bitops.h Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-05 02:50 +0200
                Re: linux/bitops.h Sasha Levin <sasha.levin@oracle.com> - 2016-05-06 22:10 +0200
                Re: linux/bitops.h Sasha Levin <sasha.levin@oracle.com> - 2016-05-06 22:10 +0200
                Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 22:30 +0200
                Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 22:40 +0200
  [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
    Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs Stephan Mueller <smueller@chronox.de> - 2016-05-02 09:10 +0200
      Re: [PATCH 2/3] random: make /dev/urandom scalable for silly  userspace programs Theodore Ts'o <tytso@mit.edu> - 2016-05-02 15:00 +0200
        Re: [PATCH 2/3] random: make /dev/urandom scalable for silly  userspace programs Theodore Ts'o <tytso@mit.edu> - 2016-05-02 15:50 +0200
          Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs Stephan Mueller <smueller@chronox.de> - 2016-05-02 16:00 +0200
  [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
    Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Jeffrey Walton <noloader@gmail.com> - 2016-05-02 11:10 +0200
      Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Stephan Mueller <smueller@chronox.de> - 2016-05-02 11:20 +0200
        Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Theodore Ts'o <tytso@mit.edu> - 2016-05-02 15:00 +0200

csiph-web