subject:"\[RFC PATCH 3\/4\] random\: Only do mixback once per read"

Re: [RFC PATCH 3/4] random: Only do mixback once per read

2015-10-16 Thread George Spelvin

If anyone has the same compile pronlem, move the "random_nonce"
definition up 10 lines to before the definition of extract_buf().

It compiles (and boots; I'm running it right now) for me as posted;
I'm not sure what the difference is.  Compiler version?  I'm running
gcc 5.2.1.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC PATCH 3/4] random: Only do mixback once per read

2015-10-16 Thread kbuild test robot

Hi George,

[auto build test ERROR on v4.3-rc5 -- if it's inappropriate base, please 
suggest rules for selecting the more suitable base]

url:
https://github.com/0day-ci/linux/commits/George-Spelvin/Alternate-sclable-urandom-patchset/20151016-133627
config: x86_64-randconfig-x010-10130227 (attached as .config)
reproduce:
# save the attached .config to linux build tree
make ARCH=x86_64 

All errors (new ones prefixed by >>):

   In file included from include/asm-generic/percpu.h:6:0,
from arch/x86/include/asm/percpu.h:551,
from arch/x86/include/asm/preempt.h:5,
from include/linux/preempt.h:64,
from include/linux/spinlock.h:50,
from include/linux/seqlock.h:35,
from include/linux/time.h:5,
from include/uapi/linux/timex.h:56,
from include/linux/timex.h:56,
from include/linux/sched.h:19,
from include/linux/utsname.h:5,
from drivers/char/random.c:238:
   drivers/char/random.c: In function 'extract_buf':
>> include/linux/percpu-defs.h:91:33: error: section attribute cannot be 
>> specified for local variables
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:92:26: error: section attribute cannot be 
specified for local variables
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> include/linux/percpu-defs.h:92:26: error: declaration of 
>> '__pcpu_unique_random_nonce' with no linkage follows extern declaration
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:91:33: note: previous declaration of 
'__pcpu_unique_random_nonce' was here
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: section attribute cannot be specified 
for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:93:44: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 extern __PCPU_ATTRS(sec) __typeof__(type) name;   \
   ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: section attribute cannot be specified 
for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: weak declaration of 'random_nonce' 
must be public
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: declaration of 'random_nonce' with no 
linkage follows extern declaration
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'

Re: [RFC PATCH 3/4] random: Only do mixback once per read

2015-10-16 Thread kbuild test robot

Hi George,

[auto build test ERROR on v4.3-rc5 -- if it's inappropriate base, please 
suggest rules for selecting the more suitable base]

url:
https://github.com/0day-ci/linux/commits/George-Spelvin/Alternate-sclable-urandom-patchset/20151016-133627
config: i386-randconfig-i1-201541 (attached as .config)
reproduce:
# save the attached .config to linux build tree
make ARCH=i386 

All errors (new ones prefixed by >>):

   In file included from include/asm-generic/percpu.h:6:0,
from arch/x86/include/asm/percpu.h:551,
from arch/x86/include/asm/preempt.h:5,
from include/linux/preempt.h:64,
from include/linux/spinlock.h:50,
from include/linux/seqlock.h:35,
from include/linux/time.h:5,
from include/uapi/linux/timex.h:56,
from include/linux/timex.h:56,
from include/linux/sched.h:19,
from include/linux/utsname.h:5,
from drivers/char/random.c:238:
   drivers/char/random.c: In function 'extract_buf':
   include/linux/percpu-defs.h:91:33: error: section attribute cannot be 
specified for local variables
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:92:26: error: section attribute cannot be 
specified for local variables
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:92:26: error: declaration of 
'__pcpu_unique_random_nonce' with no linkage follows extern declaration
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:91:33: note: previous declaration of 
'__pcpu_unique_random_nonce' was here
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: section attribute cannot be specified 
>> for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:93:44: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 extern __PCPU_ATTRS(sec) __typeof__(type) name;   \
   ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: section attribute cannot be specified 
>> for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: weak declaration of 'random_nonce' 
>> must be public
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: declaration of 'random_nonce' with no 
>> linkage follows extern declaration
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'

Re: [RFC PATCH 3/4] random: Only do mixback once per read

2015-10-16 Thread kbuild test robot

Hi George,

[auto build test ERROR on v4.3-rc5 -- if it's inappropriate base, please 
suggest rules for selecting the more suitable base]

url:
https://github.com/0day-ci/linux/commits/George-Spelvin/Alternate-sclable-urandom-patchset/20151016-133627
config: i386-randconfig-i1-201541 (attached as .config)
reproduce:
# save the attached .config to linux build tree
make ARCH=i386 

All errors (new ones prefixed by >>):

   In file included from include/asm-generic/percpu.h:6:0,
from arch/x86/include/asm/percpu.h:551,
from arch/x86/include/asm/preempt.h:5,
from include/linux/preempt.h:64,
from include/linux/spinlock.h:50,
from include/linux/seqlock.h:35,
from include/linux/time.h:5,
from include/uapi/linux/timex.h:56,
from include/linux/timex.h:56,
from include/linux/sched.h:19,
from include/linux/utsname.h:5,
from drivers/char/random.c:238:
   drivers/char/random.c: In function 'extract_buf':
   include/linux/percpu-defs.h:91:33: error: section attribute cannot be 
specified for local variables
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:92:26: error: section attribute cannot be 
specified for local variables
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:92:26: error: declaration of 
'__pcpu_unique_random_nonce' with no linkage follows extern declaration
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:91:33: note: previous declaration of 
'__pcpu_unique_random_nonce' was here
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: section attribute cannot be specified 
>> for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:93:44: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 extern __PCPU_ATTRS(sec) __typeof__(type) name;   \
   ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: section attribute cannot be specified 
>> for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: weak declaration of 'random_nonce' 
>> must be public
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> drivers/char/random.c:1134:31: error: declaration of 'random_nonce' with no 
>> linkage follows extern declaration
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'

Re: [RFC PATCH 3/4] random: Only do mixback once per read

2015-10-16 Thread kbuild test robot

Hi George,

[auto build test ERROR on v4.3-rc5 -- if it's inappropriate base, please 
suggest rules for selecting the more suitable base]

url:
https://github.com/0day-ci/linux/commits/George-Spelvin/Alternate-sclable-urandom-patchset/20151016-133627
config: x86_64-randconfig-x010-10130227 (attached as .config)
reproduce:
# save the attached .config to linux build tree
make ARCH=x86_64 

All errors (new ones prefixed by >>):

   In file included from include/asm-generic/percpu.h:6:0,
from arch/x86/include/asm/percpu.h:551,
from arch/x86/include/asm/preempt.h:5,
from include/linux/preempt.h:64,
from include/linux/spinlock.h:50,
from include/linux/seqlock.h:35,
from include/linux/time.h:5,
from include/uapi/linux/timex.h:56,
from include/linux/timex.h:56,
from include/linux/sched.h:19,
from include/linux/utsname.h:5,
from drivers/char/random.c:238:
   drivers/char/random.c: In function 'extract_buf':
>> include/linux/percpu-defs.h:91:33: error: section attribute cannot be 
>> specified for local variables
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:92:26: error: section attribute cannot be 
specified for local variables
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
>> include/linux/percpu-defs.h:92:26: error: declaration of 
>> '__pcpu_unique_random_nonce' with no linkage follows extern declaration
 __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;   \
 ^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   include/linux/percpu-defs.h:91:33: note: previous declaration of 
'__pcpu_unique_random_nonce' was here
 extern __PCPU_DUMMY_ATTRS char __pcpu_unique_##name;  \
^
   include/linux/percpu-defs.h:116:2: note: in expansion of macro 
'DEFINE_PER_CPU_SECTION'
 DEFINE_PER_CPU_SECTION(type, name, "")
 ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: section attribute cannot be specified 
for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:93:44: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 extern __PCPU_ATTRS(sec) __typeof__(type) name;   \
   ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: section attribute cannot be specified 
for local variables
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: weak declaration of 'random_nonce' 
must be public
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'
 static DEFINE_PER_CPU(__u32, random_nonce);
^
   drivers/char/random.c:1134:31: error: declaration of 'random_nonce' with no 
linkage follows extern declaration
 static DEFINE_PER_CPU(__u32, random_nonce);
  ^
   include/linux/percpu-defs.h:95:19: note: in definition of macro 
'DEFINE_PER_CPU_SECTION'
 __typeof__(type) name
  ^
   drivers/char/random.c:1134:9: note: in expansion of macro 'DEFINE_PER_CPU'

Re: [RFC PATCH 3/4] random: Only do mixback once per read

2015-10-16 Thread George Spelvin

If anyone has the same compile pronlem, move the "random_nonce"
definition up 10 lines to before the definition of extract_buf().

It compiles (and boots; I'm running it right now) for me as posted;
I'm not sure what the difference is.  Compiler version?  I'm running
gcc 5.2.1.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[RFC PATCH 3/4] random: Only do mixback once per read

2015-10-15 Thread George Spelvin

Anti-backtracking is only required on read request boundaries, not on
each few bytes of output.

This reduces contention on the pool lock.  Without mixback for each
block of output, some other mechanism must guarantee the hash result
will change each time the pool is hashed.  This is provided by the
CPU ID and a per-CPU counter acting as a nonce.

Although a per-read nonce would be simpler for the current operation,
doing it per-CPU helps later.

This is a draft patch; this change has security implications which I'm
not entirely happy with in its current state, but it serves as a stub
for testing performance improvements.  (The output is, at least, not
so bad as to cause problems in limited deployment for testing.)

Also, allowing concurrent output from a single pool breaks the FIPS
mode anti-repetition test in a fundamental way.  I'm not sure how to
fix that.

Signed-off-by: George Spelvin 
---
 drivers/char/random.c | 70 ---
 1 file changed, 50 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index e62b30ba..cf34e83d 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -966,7 +966,8 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
 
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
  int reserved);
-static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE]);
+static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE],
+   bool mixback);
 
 /*
  * This utility inline function is responsible for transferring entropy
@@ -1028,10 +1029,10 @@ static void _xfer_secondary_pool(struct entropy_store 
*r, size_t nbytes)
while (bytes) {
int i = min_t(int, bytes, EXTRACT_SIZE);
 
-   extract_buf(r->pull, tmp);
+   bytes -= i;
+   extract_buf(r->pull, tmp, bytes == 0);
mix_pool_bytes(r, tmp, i);
credit_entropy_bits(r, i*8);
-   bytes -= i;
}
 
memzero_explicit(tmp, sizeof(tmp));
@@ -1110,31 +,54 @@ retry:
  * extract_entropy_user.
  *
  * Note: we assume that .poolwords is a multiple of 16 words.
+ *
+ * The "mixback" flag enables anti-backtracking.  This need only be
+ * set on the last extract_buf in a contiguous series of requests.
+ * Ensuring distinct outputs is done by including a unique nonce
+ * (consisting of the CPU ID and a per-CPU counter that will not wrap
+ * before a mixback occurs)
+ *
+ * (FIXME: Is one ahsn's worth of mixback sufficient anti-backtracking
+ * protection?  Should we feed back more?)
  */
-static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE])
+static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE],
+   bool mixback)
 {
int i;
union {
__u32 w[5];
-   unsigned long l[LONGS(20)];
+   unsigned long l[LONGS(16)];
} hash;
+   __u32 nonce;
__u32 workspace[SHA_WORKSPACE_WORDS];
-   unsigned long flags;
+   static DEFINE_PER_CPU(__u32, random_nonce);
 
/*
 * If we have an architectural hardware random number
 * generator, use it for SHA's initial vector
 */
sha_init(hash.w);
-   for (i = 0; i < LONGS(20); i++) {
+   for (i = 0; i < LONGS(16); i++) {
unsigned long v;
if (!arch_get_random_long())
break;
hash.l[i] = v;
}
 
+   /* Add the current CPU ID and nonce */
+   hash.w[3] += get_cpu();
+   nonce = __this_cpu_inc_return(random_nonce);
+   put_cpu();
+
+   /*
+* Theoretically, it's possible on a 64-bit system for someone to
+* request EXTRACT_SIZE << 32 bytes in one read.  So force mixback
+* to be true each time the nonce wraps.
+*/
+   hash.w[4] += nonce;
+   mixback |= !nonce;
+
/* Generate a hash across the pool, 16 words (512 bits) at a time */
-   spin_lock_irqsave(>lock, flags);
for (i = 0; i < r->poolinfo->poolwords; i += 16)
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
 
@@ -1146,9 +1170,11 @@ static void extract_buf(struct entropy_store *r, __u8 
out[EXTRACT_SIZE])
 * mixing at least a SHA1 worth of hash data back, we make
 * brute-forcing the feedback as hard as brute-forcing the
 * hash.
+*
+* FIXME: update security analysis in light of reduced mixback.
 */
-   __mix_pool_bytes(r, hash.w, sizeof(hash.w));
-   spin_unlock_irqrestore(>lock, flags);
+   if (mixback)
+   mix_pool_bytes(r, hash.w, sizeof(hash.w));
 
memzero_explicit(workspace, sizeof(workspace));
 
@@ -1177,7 +1203,7 @@ static void extract_buf(struct entropy_store *r, __u8 
out[EXTRACT_SIZE])
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,

[RFC PATCH 3/4] random: Only do mixback once per read

2015-10-15 Thread George Spelvin

Anti-backtracking is only required on read request boundaries, not on
each few bytes of output.

This reduces contention on the pool lock.  Without mixback for each
block of output, some other mechanism must guarantee the hash result
will change each time the pool is hashed.  This is provided by the
CPU ID and a per-CPU counter acting as a nonce.

Although a per-read nonce would be simpler for the current operation,
doing it per-CPU helps later.

This is a draft patch; this change has security implications which I'm
not entirely happy with in its current state, but it serves as a stub
for testing performance improvements.  (The output is, at least, not
so bad as to cause problems in limited deployment for testing.)

Also, allowing concurrent output from a single pool breaks the FIPS
mode anti-repetition test in a fundamental way.  I'm not sure how to
fix that.

Signed-off-by: George Spelvin 
---
 drivers/char/random.c | 70 ---
 1 file changed, 50 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index e62b30ba..cf34e83d 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -966,7 +966,8 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
 
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
  int reserved);
-static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE]);
+static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE],
+   bool mixback);
 
 /*
  * This utility inline function is responsible for transferring entropy
@@ -1028,10 +1029,10 @@ static void _xfer_secondary_pool(struct entropy_store 
*r, size_t nbytes)
while (bytes) {
int i = min_t(int, bytes, EXTRACT_SIZE);
 
-   extract_buf(r->pull, tmp);
+   bytes -= i;
+   extract_buf(r->pull, tmp, bytes == 0);
mix_pool_bytes(r, tmp, i);
credit_entropy_bits(r, i*8);
-   bytes -= i;
}
 
memzero_explicit(tmp, sizeof(tmp));
@@ -1110,31 +,54 @@ retry:
  * extract_entropy_user.
  *
  * Note: we assume that .poolwords is a multiple of 16 words.
+ *
+ * The "mixback" flag enables anti-backtracking.  This need only be
+ * set on the last extract_buf in a contiguous series of requests.
+ * Ensuring distinct outputs is done by including a unique nonce
+ * (consisting of the CPU ID and a per-CPU counter that will not wrap
+ * before a mixback occurs)
+ *
+ * (FIXME: Is one ahsn's worth of mixback sufficient anti-backtracking
+ * protection?  Should we feed back more?)
  */
-static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE])
+static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE],
+   bool mixback)
 {
int i;
union {
__u32 w[5];
-   unsigned long l[LONGS(20)];
+   unsigned long l[LONGS(16)];
} hash;
+   __u32 nonce;
__u32 workspace[SHA_WORKSPACE_WORDS];
-   unsigned long flags;
+   static DEFINE_PER_CPU(__u32, random_nonce);
 
/*
 * If we have an architectural hardware random number
 * generator, use it for SHA's initial vector
 */
sha_init(hash.w);
-   for (i = 0; i < LONGS(20); i++) {
+   for (i = 0; i < LONGS(16); i++) {
unsigned long v;
if (!arch_get_random_long())
break;
hash.l[i] = v;
}
 
+   /* Add the current CPU ID and nonce */
+   hash.w[3] += get_cpu();
+   nonce = __this_cpu_inc_return(random_nonce);
+   put_cpu();
+
+   /*
+* Theoretically, it's possible on a 64-bit system for someone to
+* request EXTRACT_SIZE << 32 bytes in one read.  So force mixback
+* to be true each time the nonce wraps.
+*/
+   hash.w[4] += nonce;
+   mixback |= !nonce;
+
/* Generate a hash across the pool, 16 words (512 bits) at a time */
-   spin_lock_irqsave(>lock, flags);
for (i = 0; i < r->poolinfo->poolwords; i += 16)
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
 
@@ -1146,9 +1170,11 @@ static void extract_buf(struct entropy_store *r, __u8 
out[EXTRACT_SIZE])
 * mixing at least a SHA1 worth of hash data back, we make
 * brute-forcing the feedback as hard as brute-forcing the
 * hash.
+*
+* FIXME: update security analysis in light of reduced mixback.
 */
-   __mix_pool_bytes(r, hash.w, sizeof(hash.w));
-   spin_unlock_irqrestore(>lock, flags);
+   if (mixback)
+   mix_pool_bytes(r, hash.w, sizeof(hash.w));
 
memzero_explicit(workspace, sizeof(workspace));
 
@@ -1177,7 +1203,7 @@ static void extract_buf(struct entropy_store *r, __u8 
out[EXTRACT_SIZE])
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,

Re: [RFC PATCH 3/4] random: Only do mixback once per read

Re: [RFC PATCH 3/4] random: Only do mixback once per read

Re: [RFC PATCH 3/4] random: Only do mixback once per read

Re: [RFC PATCH 3/4] random: Only do mixback once per read

Re: [RFC PATCH 3/4] random: Only do mixback once per read

Re: [RFC PATCH 3/4] random: Only do mixback once per read

[RFC PATCH 3/4] random: Only do mixback once per read

[RFC PATCH 3/4] random: Only do mixback once per read

8 matches

Site Navigation

Mail list logo

Footer information