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

Groups > linux.kernel > #1394619

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

From "H. Peter Anvin" <hpa@zytor.com>
Newsgroups linux.kernel
Subject Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG
Date 2016-05-04 20:40 +0200
Message-ID <rv9Sj-Pg-59@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> <rv9IB-Ky-1@gated-at.bofh.it>
Organization linux.* mail to news gateway

Show all headers | View raw

On May 4, 2016 11:22:25 AM PDT, Jeffrey Walton <noloader@gmail.com> wrote:
>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

We don't care about UB, we care about gcc, and to a lesser extent LLVM and ICC.  If bitops.h doesn't do the right thing, we need to fix bitops.h.
-- 
Sent from my Android device with K-9 Mail. Please excuse brevity and formatting.

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