Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1243975 > unrolled thread
| Started by | "George Spelvin" <linux@horizon.com> |
|---|---|
| First post | 2015-10-10 21:00 +0200 |
| Last post | 2015-10-16 10:20 +0200 |
| Articles | 20 on this page of 24 — 5 participants |
Back to article view | Back to linux.kernel
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-10 21:00 +0200
Re: Updated scalable urandom patchkit Theodore Ts'o <tytso@mit.edu> - 2015-10-11 04:40 +0200
Re: Updated scalable urandom patchkit Theodore Ts'o <tytso@mit.edu> - 2015-10-11 05:00 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-11 06:40 +0200
Re: Updated scalable urandom patchkit Theodore Ts'o <tytso@mit.edu> - 2015-10-12 00:30 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-12 02:20 +0200
Re: Updated scalable urandom patchkit Theodore Ts'o <tytso@mit.edu> - 2015-10-12 06:10 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-12 09:50 +0200
Re: Updated scalable urandom patchkit Theodore Ts'o <tytso@mit.edu> - 2015-10-12 16:00 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-12 22:40 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-12 22:40 +0200
Re: Updated scalable urandom patchkit Theodore Ts'o <tytso@mit.edu> - 2015-10-13 04:50 +0200
Re: Updated scalable urandom patchkit Raymond Jennings <shentino@gmail.com> - 2015-10-13 06:30 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-13 10:00 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-13 08:30 +0200
Re: Updated scalable urandom patchkit Andi Kleen <andi@firstfloor.org> - 2015-10-13 18:30 +0200
Re: Updated scalable urandom patchkit "George Spelvin" <linux@horizon.com> - 2015-10-13 23:20 +0200
Re: Updated scalable urandom patchkit Andi Kleen <andi@firstfloor.org> - 2015-10-14 04:20 +0200
[RFC PATCH 0/4] Alternate sclable urandom patchset "George Spelvin" <linux@horizon.com> - 2015-10-16 07:30 +0200
[RFC PATCH 2/4] random: Remove two unused arguments from extract_entropy() "George Spelvin" <linux@horizon.com> - 2015-10-16 07:40 +0200
[RFC PATCH 4/4] random: Make non-blocking mixback non-blocking "George Spelvin" <linux@horizon.com> - 2015-10-16 07:40 +0200
[RFC PATCH 3/4] random: Only do mixback once per read "George Spelvin" <linux@horizon.com> - 2015-10-16 07:40 +0200
Re: [RFC PATCH 3/4] random: Only do mixback once per read kbuild test robot <lkp@intel.com> - 2015-10-16 08:20 +0200
Re: [RFC PATCH 3/4] random: Only do mixback once per read "George Spelvin" <linux@horizon.com> - 2015-10-16 10:20 +0200
Page 1 of 2 [1] 2 Next page →
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-10 21:00 +0200 |
| Subject | Re: Updated scalable urandom patchkit |
| Message-ID | <qi7xa-15U-51@gated-at.bofh.it> |
I'm very very sorry to be so late to the party; I didn't see this thread
until the week-delayed LWN article on the subject drew my attention to it.
There's a fundamental design issue with this patch set that seems
unnecessary to me: multiple nonblocking pools.
I know, I know, that seems like the whole point of it, but hear me out.
Entropy is a holographic property of the pool, not located in any
particular bit position.
And the most basic operation, of reading from the pool, can easily be
done by multiple readers at the same time from the same bit pattern.
They just need to be salted with distinguishing nonces (CPU IDs will do
nicely) to ensure they all get different results. So a reader doesn't
just get hash(pool[]), but hash(unique_nonce, pool[]).
This in turn lets the spin_lock_irqsave() in extract_buf be moved to
after the sha_transform() calls.
I think the whole thing can be done, more elegantly, using a single pool
and judiciously relaxed locking rules. You don't even need reader-writer
locks; it's actually beneficial rather than harmful if there's a race
between a pool reader and writer.
In general, fewer larger pools is better for entropy storage. The only
reason for the current three-pool design is to achieve strict isolation
of the /dev/random pool.
The two operations that require locking are:
1. Entropy accounting. However, that only has to be strict
for /dev/random. For /dev/urandom, it can be late in various ways.
One possibility is to have separate entropy accounding per NUMA
node; only the pool proper has to be shared.
2. Add-back of the output to the pool. This involves writing to pool,
but for non-invertibility, it only has to be do ne byone of a number of
concurrent readers. I think significant cleverness can be applied
here.
There are a lot of things that can be done about this second point:
2a. The obvious one is to batch the add-back. For backtracking
protection, we only need to do one add-back per read, not one per
10 bytes of output. Combined with the above change that locks only
around the add-back and not the pool hashing, this greatly reduces
both the lock window and the number of times it's taken.
2b. Another idea would be to optimize for 16 bytes. I like the basic
concept of having a larger hash internal state than the output, but
would it be possible to output 16 of the 20 bytes of SHA-1 output
rather than the current 10? This is obviously a Ted question (the
current folding is his idea), but even 32 bits is enough to protect
against internal collisions in the hash state.
2c. Another possibility would be to add small separate "salt piles"
which are initialized to the CPU id, and stirred by reads. They only
need to be large enough to not experience birthsay collisions even
assuming a stupid number of reads between stirs of the main pool.
(So 128 bits would be more than ample.) A read would consist of:
hash[5] = { initial values }
sha1(hash, my_salt)
sha1(hash, main_pool)
if (spin_trylock(main_pool)) {
add_back(hash, main_pool);
spin_unlock(main_pool);
} else {
add_back(hash, my_salt);
}
2d. A more complete solution involves noting that, if there are multiple
concurrent readers, only one has to add back its output to prevent
backtracking, because all of the concurrent reads are equivalent
in that sense. (Even though, because they're salted with separate
nonces like the CPU id, they're not identical.)
I'm thinking in terms of a "generation counter" for the pool. (Perhaps
implemented as a seqlock.) The readers of the generation-n pool must
ensure that *someone* is responsible for bumping the generation to n+1
to prevent backtracking of the generation-n state, but only one.
A key point is that the add-back that bumps the generation to n+2 may
actaully be a hash of the generation-n pool state, the generation-n+1
state, or some transient intermedicate state due to races with the
generation-n+1 add-back. It is not necessary for readers to wait for
the pool to be stable, only that it's a non-invertible transformation
based on some earlier generation.
Now, to actually implement that, a "spin lock while checking extra
condition" would be ideal, but I do not want to add Yet Another Locking
Primitive to the kernel.
One possibility would be to accept the possibility of a race condition
breaking anti-backtracking. Another reader will come along soom enough
and fix it.
But if that's not okay, consider the following:
We add a second lock, the "responsibility lock", the holder of which
is responsible for doing anti-backtracking.
After hashing the pool, each reader does the following:
1. (Optional) trylock() the pool lock.
This is a low-load optimization. If it succeeds, go
directly to step 5.
2. Trylock() the responsibility lock.
If this fails, we're done; return.
3. Wait for the pool lock.
4. Drop the responsibility lock. This must be done before
updating the pool proper.
5. Add our anti-backtracking bytes to the pool.
6. Release the pool lock.
(I originally thought I'd need to ping-pong between two responsibility
locks based on the generation counter % 2, but now I don't think so.)
Under high load, you have one processor adding back, a second waiting
to add back, and everyone else just sails right through without
waiting at all.
Details to be filled in:
- Each reader needs some sort of nonce to distinguish multiple reads
if there's no main pool add-back between them. RDTSC, per-cpu
counter, or whatever.
- Entropy accounting. As mentioned, some sloppiness is okay, so I
think it's solvable, but I haven't looked at it yet.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [next] | [standalone]
| From | Theodore Ts'o <tytso@mit.edu> |
|---|---|
| Date | 2015-10-11 04:40 +0200 |
| Message-ID | <qieIh-3cX-1@gated-at.bofh.it> |
| In reply to | #1243975 |
On Sat, Oct 10, 2015 at 02:45:46PM -0400, George Spelvin wrote:
> In general, fewer larger pools is better for entropy storage. The only
> reason for the current three-pool design is to achieve strict isolation
> of the /dev/random pool.
You're absolutely right, and I would like to see if we can get away
with keeping with a single pool design. Your idea of using the CPU id
as a nonce is a good one, and I think we can do something similar that
should be good enough for mixing the hash back into the pool. We can
simply use a hash of the CPU id to change the offset where we do the
mixing, and this should be good enough to avoid collisions when we do
the add-back.
HOWEVER. One downside of this approach is that, especially on a NUMA
system, the costs of the cache coherency across a single pool which is
constantly being modified and shared by all of the NUMA nodes could be
a killer, even if we go completely lockless.
To that end, Andi, can you try benchmarking the scalability of the
patch below? I really hope it will be good enough, since besides
using less memory, there are security advantages in not spreading the
entropy across N pools.
If it isn't, we might be able to play a trick where we sample the
r->add_ptr value before we start hashing the pool, and then check to
see if it's changed afterwards. If it has, we could skip doing the
hash back, which could reduce the cache coherency traffic, since as
you point out:
> 2d. A more complete solution involves noting that, if there are multiple
> concurrent readers, only one has to add back its output to prevent
> backtracking, because all of the concurrent reads are equivalent
> in that sense. (Even though, because they're salted with separate
> nonces like the CPU id, they're not identical.)
However, even if we put in that optimization, the primary question is
how good is Intel's cache coherency protocols on their NUMA systems?
I'm pretty sure this would be a disaster on, say, Sequent's old NUMA
machines, but I'm quite confident all of those servers are dead and
buried by now. :-)
- Ted
commit 3cb51896deab45bddc1b8f571b1103eae8f50e0e
Author: Theodore Ts'o <tytso@mit.edu>
Date: Sat Oct 10 22:03:53 2015 -0400
random: make the reading from the non-blocking pool more scalable
Andi Kleen reported a case where a 4 socket system spent >80% of its
total CPU time contending on the global urandom nonblocking pool
spinlock. While the application could probably have used an own PRNG,
it may have valid reasons to use the best possible key for different
session keys.
Instead of creating separate multiple per-NUMA node non-blocking
pools, use a trick suggested by George Spelvin:
Entropy is a holographic property of the pool, not located in any
particular bit position.
And the most basic operation, of reading from the pool, can easily be
done by multiple readers at the same time from the same bit pattern.
They just need to be salted with distinguishing nonces (CPU IDs will do
nicely) to ensure they all get different results....
We use this trick, and in addition use a hash of the cpu id to change
where we mix the hash back into the pool to avoid collisions.
Since we are already using a lockless technique (cmpxchg) to update
the entropy accounting, we don't need to change this around.
This technique won't be quite as scalable since on a NUMA node we will
still be forcing cache lines to bounce around, but from the
perspective of entropy storage we're much better using a single pool
rather than spreading it across multiple pools.
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
diff --git a/drivers/char/random.c b/drivers/char/random.c
index d0da5d8..be6b315 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -260,6 +260,7 @@
#include <linux/irq.h>
#include <linux/syscalls.h>
#include <linux/completion.h>
+#include <linux/hash.h>
#include <asm/processor.h>
#include <asm/uaccess.h>
@@ -494,7 +495,9 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
{
unsigned long i, tap1, tap2, tap3, tap4, tap5;
int input_rotate;
+ int is_nonblock = (r == &nonblocking_pool);
int wordmask = r->poolinfo->poolwords - 1;
+ int poolbits = r->poolinfo->poolbitshift - 5;
const char *bytes = in;
__u32 w;
@@ -506,6 +509,8 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
input_rotate = r->input_rotate;
i = r->add_ptr;
+ if (is_nonblock)
+ i += hash_32(get_cpu(), poolbits);
/* mix one byte at a time to simplify size handling and churn faster */
while (nbytes--) {
@@ -534,6 +539,8 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
r->input_rotate = input_rotate;
r->add_ptr = i;
+ if (is_nonblock)
+ put_cpu();
}
static void __mix_pool_bytes(struct entropy_store *r, const void *in,
@@ -1090,6 +1097,7 @@ retry:
static void extract_buf(struct entropy_store *r, __u8 *out)
{
int i;
+ int is_nonblock = (r == &nonblocking_pool);
union {
__u32 w[5];
unsigned long l[LONGS(20)];
@@ -1108,9 +1116,12 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
break;
hash.l[i] = v;
}
+ if (is_nonblock)
+ hash.w[0] ^= hash_32(get_cpu(), 32);
+ else
+ spin_lock_irqsave(&r->lock, flags);
/* Generate a hash across the pool, 16 words (512 bits) at a time */
- spin_lock_irqsave(&r->lock, flags);
for (i = 0; i < r->poolinfo->poolwords; i += 16)
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
@@ -1124,7 +1135,10 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
* hash.
*/
__mix_pool_bytes(r, hash.w, sizeof(hash.w));
- spin_unlock_irqrestore(&r->lock, flags);
+ if (is_nonblock)
+ put_cpu();
+ else
+ spin_unlock_irqrestore(&r->lock, flags);
memzero_explicit(workspace, sizeof(workspace));
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Theodore Ts'o <tytso@mit.edu> |
|---|---|
| Date | 2015-10-11 05:00 +0200 |
| Message-ID | <qif1E-3AR-11@gated-at.bofh.it> |
| In reply to | #1244049 |
On Sat, Oct 10, 2015 at 10:31:46PM -0400, Theodore Ts'o wrote: > To that end, Andi, can you try benchmarking the scalability of the > patch below? I really hope it will be good enough, since besides > using less memory, there are security advantages in not spreading the > entropy across N pools. Andi, I forgot to menion --- if you could benchmark using both on your "run get_entropy() in a tight loop" and the actual real-life application --- since if is CPU cache behavior is going to be a large factor in the results, a real application is going to be more representative that a micro-benchmark, that would be much appreciated. Thanks! - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-11 06:40 +0200 |
| Message-ID | <qigAp-5WN-3@gated-at.bofh.it> |
| In reply to | #1244049 |
Damn, I bow before the master. That is a much neater solution than mine; I had assumed a lock was required for writing. While it's good enough for benchmarking, there are a few leftover problems I mention so they don't get missed. One is the final write back of add_ptr on the last line of _mix_pool_bytes. It actually writes i, which includes the per-cpu nonce, and will have it jumping all over without the steady progression that the mixing polynomial assumes. (There's a similar, lesser problem with input_rotate.) The second, less obvious, problem is that by calling _mix_pool_bytes completely lockless, there's the risk that it will race with and overwrite the addition of new seed material to the pool. The add-back is not critical, and races between two writers don't really do any harm. But seed entropy is valuable. And unfortunately, transferring 256 bits (32 bytes) to the output pool will try to write every word, so *any* concurrent add-back is risky; there's no "safe" part of the pool that can be accessed lockless. (The first crude hack that comes to mind is to double the size of the output pool, without increasing its nominal capacity, and do seeding and add-back to different halves. Hopefully there's something more elegant.) Two minor suggestions about is_nonblock: 1) Rather than using (r == &nonblocking_pool), how about !r->limit? 2) Would you mind making is_nonblock bool? I know back before the sacred text of the prophets Kernighan and Ritchie was corrupted by modern heresies, we used "int" for everything, and we liked it. 5 miles in the snow, uphill both ways, yadda yadda. But I like to document range restrictions as much as possible, and "bool" makes it clearer to both the compiler and the reader of the code. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Theodore Ts'o <tytso@mit.edu> |
|---|---|
| Date | 2015-10-12 00:30 +0200 |
| Message-ID | <qixhT-51a-5@gated-at.bofh.it> |
| In reply to | #1244058 |
On Sun, Oct 11, 2015 at 12:35:46AM -0400, George Spelvin wrote: > > One is the final write back of add_ptr on the last line of > _mix_pool_bytes. It actually writes i, which includes the per-cpu nonce, > and will have it jumping all over without the steady progression that > the mixing polynomial assumes. Yep, good catch; I need to subtract that off. > (There's a similar, lesser problem with input_rotate.) I didn't bother messing with input_rotate at all, and I don't think that will be a problem. > The second, less obvious, problem is that by calling _mix_pool_bytes > completely lockless, there's the risk that it will race with and overwrite > the addition of new seed material to the pool. > > The add-back is not critical, and races between two writers don't really > do any harm. But seed entropy is valuable. That's true, but I've been going back and forth about how much it's worth to fix this. After all, the the non-blocking pool is guaranteed to have cryptographic randomness, and so it's a question of how much effort we want to avoid the possibility of losing some seed entropy. One approach might be to use take a reader lock when mixing back entropy, but take an exclusive lock in the case when seeding the non-random pool. Another approach is to have an alternate mechanism for the non-blocking pool which uses the LOCK prefix when XOR'ing into the pool. This would mean that we would have to drop the twisted LFSR and replace it with something simpler but so long as the mixing algothm eventually involves all of the bits in the pool, that will probably be OK. Of course, using the LOCK prefix is CPU architecture specific, and in particular, there is no equivalent on the ARM architecture. The final thing we could do is to just throw in a smp_mb() before the write into the pool, and just call it day, and accept that while we might lose a small amount of entropy due to a race, it will only a byte's worth each time we lose a race (instead of the whole 32 byte cache line). None of the alternatives are all that satisfying, and they will all be a bit more expensive than the first patch. The question is how to weigh these problems against just simply using a separate pool for each NUMA node, and how much scalability are we really need for "realistic" workloads? - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-12 02:20 +0200 |
| Message-ID | <qiz0l-7xX-5@gated-at.bofh.it> |
| In reply to | #1244242 |
TedTs'o wrote: > Yep, good catch; I need to subtract that off. I'm not thrilled with incrementing the pointer from i to len, but mixing at positions i+k to i+k+len. The whole LFSR scheme relies on a regular pass structure. How about this instead: drop the hashed offset, and instead let each writer do an atomic_add_return on the index, then iterate over the "reserved" slots. Concurrent additions will at least do non-overlapping writes until the numer equals the pool size. (Admittedly, if the pool is 32 words and we're adding back 20 bytes per reader, overlap is hard to avoid. Could we do seeding a byte at a time with input rotate, but add-back 32 bits at a time for simplicity and speed?) The other one would be to have separate indexes for add-back and seed addition, with the latter protected by a lock. >> (There's a similar, lesser problem with input_rotate.) > I didn't bother messing with input_rotate at all, and I don't think > that will be a problem. It was more that it's going to do strange non-deterministic things. Personally, I hate the input_rotate. It's not that it's harmful, just that it doesn't do much good compared to the cost; for the number of cycles and context space required there are more efficient mixing operations. But if you want, you can easily compute it on demand. If you avoid reducing r->add_words mod poolwords, then input_rotate = 7*(r->add_words + r->add_words/poolwords) >> The add-back is not critical, and races between two writers don't really >> do any harm. But seed entropy is valuable. > That's true, but I've been going back and forth about how much it's > worth to fix this. After all, the the non-blocking pool is guaranteed > to have cryptographic randomness, and so it's a question of how much > effort we want to avoid the possibility of losing some seed entropy. I worry that with only 32 words of pool, on a large (1K CPUs) machine that's execv()ing and geerating AT_RANDOM vectors a lot, the traffic could be pretty heavy, and the odds of stomping a byte of seed material cound get substantial. Or a small machine with a couple of concurrent /dev/urandom abusers. Remember, it's globally readable, so it has to be resistance to malicious abuse. > One approach might be to use take a reader lock when mixing back > entropy, but take an exclusive lock in the case when seeding the > non-random pool. Even a reader lock is at least one atomic operation. > Another approach is to have an alternate mechanism for the > non-blocking pool which uses the LOCK prefix when XOR'ing into the > pool. This would mean that we would have to drop the twisted LFSR and > replace it with something simpler but so long as the mixing algothm > eventually involves all of the bits in the pool, that will probably be > OK. > > Of course, using the LOCK prefix is CPU architecture specific, and in > particular, there is no equivalent on the ARM architecture. You can add rather than XOR, and we have atomic add primitives. (You could even, if you wanted to preserve the period proof of the mixing function, compute the value which, when added to the original word, would make the XOR change, and then atomically add that.) > The final thing we could do is to just throw in a smp_mb() before the > write into the pool, and just call it day, and accept that while we > might lose a small amount of entropy due to a race, it will only a > byte's worth each time we lose a race (instead of the whole 32 byte > cache line). If you're willing to accept "probably" solutions, just add the seed material twice. If one byte is lost, the other copy will probably survive. Or, if you want to be cleverer, any form of error-correcting code (duplication is just a simple for of it) will add enough redundant information that a few erasures won't lose entropy. But the atomic add seems safer. I don't have a good feel for the fraction of lost entropy a deliberate attack on a large machine could cause and /dev/urandom is not an area where I'm comfortable hoping. > None of the alternatives are all that satisfying, and they will all be > a bit more expensive than the first patch. The question is how to > weigh these problems against just simply using a separate pool for > each NUMA node, and how much scalability are we really need for > "realistic" workloads? There are several possible solutions that don't need separate pools (including separate add-back pools, with a shared seeded pool that is never touched by add-back), so I don't think it's necessary to give up yet. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Theodore Ts'o <tytso@mit.edu> |
|---|---|
| Date | 2015-10-12 06:10 +0200 |
| Message-ID | <qiCAV-4pg-1@gated-at.bofh.it> |
| In reply to | #1244311 |
On Sun, Oct 11, 2015 at 08:16:01PM -0400, George Spelvin wrote: > > I'm not thrilled with incrementing the pointer from i to len, but mixing > at positions i+k to i+k+len. The whole LFSR scheme relies on a regular > pass structure. That part I'm not worried about. We still have a regular pass structure --- since for each CPU, we are still iterating over the pool in a regular fashion. > How about this instead: drop the hashed offset, and instead let each > writer do an atomic_add_return on the index, then iterate over the > "reserved" slots. Concurrent additions will at least do non-overlapping > writes until the numer equals the pool size. One atomic operation per byte that we're mixing in? That's quite expensive. > Personally, I hate the input_rotate. It's not that it's harmful, just > that it doesn't do much good compared to the cost; for the number of cycles > and context space required there are more efficient mixing operations. The input_rotate is useful for the input pool, for things like keyboard code so we can make sure they enter the pool at more points than just the low bits of each word. But for the output pools, it really doesn't make any sense. And we are getting to the point where we may end up having different mixing algorithms for the nonblocking pool, and in that case I have absolutely no trouble dropping the input_rotate part of the mixing algorithm for the non-blocking pool. > Or a small machine with a couple of concurrent /dev/urandom abusers. > Remember, it's globally readable, so it has to be resistance to malicious > abuse. One of the other ways we could solve this is by hanging a struct off the task structure, and if we detect that we have a /dev/urandom abuser, we give that process its own urandom pool, so any pissing that it does will be in its own pool. (So to speak.) Most processes don't actually use that much randomness, and I'm not that worried about in-kernel users of the nonblocking pool. Even with the most exec-heavy workload, setting up a new exec image is heavyweight enough that you're really not going to be contending on the lock. I also have trouble with someone spending $$$$ on a system with 1K cpu cores and wasting all of their CPU power with running shell scripts that fork and exec a lot. :-) The reality is that most processes don't use /dev/urandom or getrandom(2) at all, and those that do, many of them only use it sparingly. So maybe the right answer is to do something simple which takes care of the abusers. > You can add rather than XOR, and we have atomic add primitives. Atomic-add primitives aren't portable either. The representation isn't guaranteed to be 32-bits, and some platforms an atomic int is only 24-bits wide (the top 8 bits being used for locking purposes). > There are several possible solutions that don't need separate pools > (including separate add-back pools, with a shared seeded pool that > is never touched by add-back), so I don't think it's necessary to > give up yet. Hmm, maybe. I'm a bit worried about the amount of complexity that this entails, and the reality is that the urandom pool or pools don't provide anything other than cryptogaphic randomness. At this point, I wonder if it might not be simpler to restrict the current nonblocking pool to kernel users, and for userspace users, the first time a process reads from /dev/urandom or calls getrandom(2), we create for them a ChaCha20 CRNG, which hangs off of the task structure. This would require about 72 bytes of state per process, but normally very few processes are reading from /dev/urandom or calling getrandom(2) from userspace. The CRNG would be initialized from the non-blocking pool, and is reseeded after, say, 2**24 cranks or five minutes. It's essentially an OpenBSD-style arc4random in the kernel. (Arguably the right answer is to put arc4random in libc, where it can automatically handle forks/clones/pthread automatically, but it seems pretty clear *that* train has left a long time ago.) I have a feeling this may be less code and complexity, and it nicely handles the case where we have a /dev/urandom abuser who feels that they want to call /dev/urandom in a tight loop, even on a 4 socket Xeon system. :-) - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-12 09:50 +0200 |
| Message-ID | <qiG1Q-MT-21@gated-at.bofh.it> |
| In reply to | #1244371 |
>> I'm not thrilled with incrementing the pointer from i to len, but mixing
>> at positions i+k to i+k+len. The whole LFSR scheme relies on a regular
>> pass structure.
> That part I'm not worried about. We still have a regular pass
> structure --- since for each CPU, we are still iterating over the pool
> in a regular fashion.
Not if I understand what you are doing.
Suppose CPU 0 has an offset of 0, and CPU 1 has an offset of 12.
(I'll also use a count-up index even though I know it's actually
count-down in the code.)
CPU0 writes 5 words at 0..4, leaving add_ptr = 5.
Then CPU 1 writes 5 words at 17..21, leaving add_ptr = 10
The CPU 0 writes its next word at 10.
Words 5..9 never got mixed at all.
>> How about this instead: drop the hashed offset, and instead let each
>> writer do an atomic_add_return on the index, then iterate over the
>> "reserved" slots. Concurrent additions will at least do non-overlapping
>> writes until the number equals the pool size.
> One atomic operation per byte that we're mixing in? That's quite
> expensive.
Well, for this part, it's one atomic operation per _mix_pool_bytes:
i = (unsigned)atomic_sub_return(nbytes, &r->add_ptr) + nbytes;
However, I *also* have to use atomic_add to write r->pool[i],
which is indeed expensive. PoC diff attached, but I'm not sure if
you'll like it.
> The input_rotate is useful for the input pool, for things like
> keyboard code so we can make sure they enter the pool at more points
> than just the low bits of each word. But for the output pools, it
> really doesn't make any sense. And we are getting to the point where
> we may end up having different mixing algorithms for the nonblocking
> pool, and in that case I have absolutely no trouble dropping the
> input_rotate part of the mixing algorithm for the non-blocking pool.
You're forgetting: keyboard codes don't go into the input pool.
They go into the per-CPU fast pool, which does some quite thorough
mixing and delivers 128 bits with the entropy effectively distributed
across it.
These days, the only thing that goes into the large pools are
the output from other pools and /dev/random writes.
But also, that's what the twist_table achieves. By the time the
pool wraps around, the previous value at a given array posistion
has been read and twisted many times, and is now smeared across
all 32 bits.
If you want larger shifts *and* greater efficiency by removing a table
lookup from the critical path, I'll happily replace it with an Xorshift
structure (will take me a little while; I've generated primitive
polynomials in the past but need to rewrite the code).
>> Or a small machine with a couple of concurrent /dev/urandom abusers.
>> Remember, it's globally readable, so it has to be resistance to malicious
>> abuse.
> One of the other ways we could solve this is by hanging a struct off
> the task structure, and if we detect that we have a /dev/urandom
> abuser, we give that process its own urandom pool, so any pissing that
> it does will be in its own pool. (So to speak.)
Let me make sure we're talking about the same thing here.
Segregating abusers so they don't cause *performance* problems
for other threads is a reasonable optimization.
But the quoted conversation was talking about a *security*
problem that could be created by /dev/urandom abusers if some
of your lock-relaxing ideas were followed.
I was observing that the failure case you were hoping was rare could
be made common by a malicious user.
And for that, I don't think a cacheing wrapper is the way to solve
the problem.
For security, either the underlying pool is robust or fragile. If it's
robust, we don't need this extra layer; abusers will get shitty
performance but won't hurt the quality of the output.
If we need the layer, then we have to ask if we understand the
vulnerability to abuse and have successfully segregated all damaging
forms of abuse. That's more analysis and design effort than simply
eliminating the problem in the first place.
> Most processes don't actually use that much randomness, and I'm not
> that worried about in-kernel users of the nonblocking pool. Even with
> the most exec-heavy workload, setting up a new exec image is
> heavyweight enough that you're really not going to be contending on
> the lock. I also have trouble with someone spending $$$$ on a system
> with 1K cpu cores and wasting all of their CPU power with running
> shell scripts that fork and exec a lot. :-)
But I just re-read Andi's original trouble report, and although he mentions
AT_RANDOM, it's an applicatio reading from /dev/urandom a lot that's
causing the problem *not* execve. My memory may have gotten confused.
I can imagine that one /dev/urandom abuser can minopolize the locck and
cause problems for a shell script.
But yes, for this performance problem, a segregate-the-abusers solution
is quite attractive.
> Atomic-add primitives aren't portable either. The representation
> isn't guaranteed to be 32-bits, and some platforms an atomic int is
> only 24-bits wide (the top 8 bits being used for locking purposes).
No longer true; see Documentation/atomic_ops.txt.
But yes, atomic ops are *ridiculously* expensive on SMP 32-bit SPARC.
Do we care? Is anyone using multiprocessor V7 SPARC in anger these days?
>> There are several possible solutions that don't need separate pools
>> (including separate add-back pools, with a shared seeded pool that
>> is never touched by add-back), so I don't think it's necessary to
>> give up yet.
> Hmm, maybe. I'm a bit worried about the amount of complexity that
> this entails, and the reality is that the urandom pool or pools don't
> provide anything other than cryptogaphic randomness.
Well, *one* add-back pool would also do, and be a quite simple addition
to the code.
> the urandom pool or pools don't
> provide anything other than cryptogaphic randomness.
Well, there's cryptographic and there's cryptographic.
/dev/urandom is deliberately *ridiculosuly* overengineered;
It's not dependent on the security of a single primitive.
I'd rather not downgrade it to depending on the security of AES, or
ChaCha, or Keccak, or any other performance-optimized primitive.
For my own code, sure. But /dev/random is sold as "you *really* don't
have to worry about it".
> At this point, I wonder if it might not be simpler to restrict the
> current nonblocking pool to kernel users, and for userspace users, the
> first time a process reads from /dev/urandom or calls getrandom(2), we
> create for them a ChaCha20 CRNG, which hangs off of the task
> structure. This would require about 72 bytes of state per process,
> but normally very few processes are reading from /dev/urandom or
> calling getrandom(2) from userspace.
Interesting idea, although the loss of backtracking protection for
long-running servers is a significant semantic change.
Remember that making antibacktracking work is the entire problem we're
struggling to solve. If discarding it is on the table, I can solve
the scalability problems extremely easily. Even without giving it up
completely, just put the add-back inside if(trylock()) and the problem
goes away.
I'm also not sure where you get 72 bytes from. You need 32 bytes of
key, 8 bytes of nonce, and 4 or 8 bytes of stream position to form the
ChaCha input block.
Then optionally add 64 bytes of output buffer if you don't want to
discard generated bytes after an unaligned read.
It adds up to 44/48, or 108/112 bytes. Where does 72 come from?
But why bother with even that much? If you're willing to discard
antibacktracking, just have *one* key for the kernel, reseeded more
often, and a per-thread nonce and stream position.
> (Arguably the right answer is to put arc4random in libc, where it can
> automatically handle forks/clones/pthread automatically, but it seems
> pretty clear *that* train has left a long time ago.)
I'm not quite which viatical incident you're alluding to, but yes that
would be the preferred solution.
> I have a feeling this may be less code and complexity, and it nicely
> handles the case where we have a /dev/urandom abuser who feels that
> they want to call /dev/urandom in a tight loop, even on a 4 socket
> Xeon system. :-)
I'm not sanguine about its simplicity; it's a whole other layer.
Might be a good idea anyway. I have a similar patch set in work, but
it's called /dev/frandom because I wasn't willing to suggest such a
semantic change.
But without interfering with legitimate users of /dev/urandom at all,
I'd be quite willing to say that as soon as you read more than 32 bytes
(current request plus recent history) from /dev/urandom, you get a
private ChaCha20 structure to read from.
(This is just enforcing the usage rules from the random(4) man page.
Since I wrote that text, I'm hardly going to object!)
Here's that atomic_t patch I mentioned above.
diff --git a/drivers/char/random.c b/drivers/char/random.c
index e62b30ba..e65357c4 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -260,6 +260,7 @@
#include <linux/irq.h>
#include <linux/syscalls.h>
#include <linux/completion.h>
+#include <linux/hash.h>
#include <asm/processor.h>
#include <asm/uaccess.h>
@@ -423,7 +424,7 @@ struct entropy_store;
struct entropy_store {
/* read-only data: */
const struct poolinfo *poolinfo;
- __u32 *pool;
+ atomic_t *pool;
const char *name;
struct entropy_store *pull;
struct work_struct push_work;
@@ -431,20 +432,20 @@ struct entropy_store {
/* read-write data: */
unsigned long last_pulled;
spinlock_t lock;
- unsigned short add_ptr;
- unsigned short input_rotate;
+ atomic_t add_ptr;
int entropy_count;
int entropy_total;
unsigned int initialized:1;
unsigned int limit:1;
unsigned int last_data_init:1;
+ unsigned char input_rotate;
__u8 last_data[EXTRACT_SIZE];
};
static void push_to_pool(struct work_struct *work);
-static __u32 input_pool_data[INPUT_POOL_WORDS];
-static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
-static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
+static atomic_t input_pool_data[INPUT_POOL_WORDS];
+static atomic_t blocking_pool_data[OUTPUT_POOL_WORDS];
+static atomic_t nonblocking_pool_data[OUTPUT_POOL_WORDS];
static struct entropy_store input_pool = {
.poolinfo = &poolinfo_table[0],
@@ -488,6 +489,10 @@ static __u32 const twist_table[8] = {
* degree, and then twisted. We twist by three bits at a time because
* it's cheap to do so and helps slightly in the expected case where
* the entropy is concentrated in the low-order bits.
+ *
+ * This function is designed to be safe to call without locking the
+ * entropy_store. Race conditions might do strange things, but will
+ * leave the pool valid and not lose entropy.
*/
static void _mix_pool_bytes(struct entropy_store *r, const void *in,
int nbytes)
@@ -496,7 +501,8 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
int input_rotate;
int wordmask = r->poolinfo->poolwords - 1;
const char *bytes = in;
- __u32 w;
+
+ BUILD_BUG_ON(sizeof(int) != sizeof(__u32));
tap1 = r->poolinfo->tap1;
tap2 = r->poolinfo->tap2;
@@ -505,23 +511,31 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
tap5 = r->poolinfo->tap5;
input_rotate = r->input_rotate;
- i = r->add_ptr;
+ i = (unsigned)atomic_sub_return(nbytes, &r->add_ptr) + nbytes;
/* mix one byte at a time to simplify size handling and churn faster */
while (nbytes--) {
- w = rol32(*bytes++, input_rotate);
- i = (i - 1) & wordmask;
+ __u32 v, w = rol32(*bytes++, input_rotate);
/* XOR in the various taps */
- w ^= r->pool[i];
- w ^= r->pool[(i + tap1) & wordmask];
- w ^= r->pool[(i + tap2) & wordmask];
- w ^= r->pool[(i + tap3) & wordmask];
- w ^= r->pool[(i + tap4) & wordmask];
- w ^= r->pool[(i + tap5) & wordmask];
+ i = (i - 1) & wordmask;
+ w ^= atomic_read(r->pool + ((i + tap1) & wordmask));
+ w ^= atomic_read(r->pool + ((i + tap2) & wordmask));
+ w ^= atomic_read(r->pool + ((i + tap3) & wordmask));
+ w ^= atomic_read(r->pool + ((i + tap4) & wordmask));
+ w ^= atomic_read(r->pool + ((i + tap5) & wordmask));
+ w ^= v = atomic_read(r->pool + i);
+ /* Twist the result to mix bits within words */
+ w = (w >> 3) ^ twist_table[w & 7];
- /* Mix the result back in with a twist */
- r->pool[i] = (w >> 3) ^ twist_table[w & 7];
+ /*
+ * Now, to put the result back, we don't have an
+ * atomic_xor operation, but we do have an atomic_add.
+ * Atomically add the value which would cause the desired
+ * change. If there's a race, something strange will happen,
+ * but we won't lose entropy.
+ */
+ atomic_add(w - v, r->pool + i);
/*
* Normally, we add 7 bits of rotation to the pool.
@@ -532,8 +546,13 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
}
- r->input_rotate = input_rotate;
- r->add_ptr = i;
+ /*
+ * Access to input_rotate is not thread-safe, because the
+ * actual value doesn't matter to the security guarantees,
+ * and the fact that it changes is enough for its purpose.
+ * So if there's a race condition, it doesn't matter who wins.
+ */
+ r->input_rotate = (unsigned char)input_rotate;
}
static void __mix_pool_bytes(struct entropy_store *r, const void *in,
@@ -1109,17 +1128,26 @@ retry:
* This function does the actual extraction for extract_entropy and
* extract_entropy_user.
*
+ * For the blocking pools, we lock the pool until we feed back the
+ * extracted entropy, so the next extract_buf will return different
+ * results.
+ *
+ * For the non-blocking pool, concurrent access to the pool is allowed,
+ * and the CPU id is used as a salt to ensure that concurrent readers
+ * will get different results.
+ *
* Note: we assume that .poolwords is a multiple of 16 words.
*/
static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE])
{
int i;
+ bool is_blocking = r->limit;
union {
__u32 w[5];
unsigned long l[LONGS(20)];
} hash;
__u32 workspace[SHA_WORKSPACE_WORDS];
- unsigned long flags;
+ unsigned long flags = flags; /* "initialization" shuts up GCC */
/*
* If we have an architectural hardware random number
@@ -1133,8 +1161,11 @@ static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE])
hash.l[i] = v;
}
+ if (is_blocking)
+ spin_lock_irqsave(&r->lock, flags);
+ else
+ hash.w[0] ^= hash_32(get_cpu(), 32);
/* Generate a hash across the pool, 16 words (512 bits) at a time */
- spin_lock_irqsave(&r->lock, flags);
for (i = 0; i < r->poolinfo->poolwords; i += 16)
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
@@ -1148,7 +1179,10 @@ static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE])
* hash.
*/
__mix_pool_bytes(r, hash.w, sizeof(hash.w));
- spin_unlock_irqrestore(&r->lock, flags);
+ if (is_blocking)
+ spin_unlock_irqrestore(&r->lock, flags);
+ else
+ put_cpu();
memzero_explicit(workspace, sizeof(workspace));
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Theodore Ts'o <tytso@mit.edu> |
|---|---|
| Date | 2015-10-12 16:00 +0200 |
| Message-ID | <qiLNU-LL-19@gated-at.bofh.it> |
| In reply to | #1244453 |
On Mon, Oct 12, 2015 at 03:49:08AM -0400, George Spelvin wrote: > > Suppose CPU 0 has an offset of 0, and CPU 1 has an offset of 12. > (I'll also use a count-up index even though I know it's actually > count-down in the code.) > > CPU0 writes 5 words at 0..4, leaving add_ptr = 5. > Then CPU 1 writes 5 words at 17..21, leaving add_ptr = 10 > The CPU 0 writes its next word at 10. > > Words 5..9 never got mixed at all. Hmm, good point. It *shouldn't* matter if the hash is secure, but the potentially uneven mixing would be a concern. > However, I *also* have to use atomic_add to write r->pool[i], > which is indeed expensive. PoC diff attached, but I'm not sure if > you'll like it. Yeah, that was the part that worried me. Whether we use an atomic add or an atomic xor, it's going to be very expensive. Using an atomic add means that it will work with arm, but there's an explicit loop with arm, so on an arm system, it effectively turns into a more efficient spinlock, except you're spinning on each byte, so instead of bouncing cache lines with the locking granularity of the extract, we would be bouncing cache lines for every single byte of the mixback operation. > You're forgetting: keyboard codes don't go into the input pool. > They go into the per-CPU fast pool, which does some quite thorough > mixing and delivers 128 bits with the entropy effectively distributed > across it. They used to go through the input pool, and when we added the per-CPU fast pool, we didn't revisit the question of whether the input_rotate was still needed. So yes, at this point it might be worthwhile to remove the input_rotate part of the mixing scheme. > Segregating abusers so they don't cause *performance* problems > for other threads is a reasonable optimization. > > But the quoted conversation was talking about a *security* > problem that could be created by /dev/urandom abusers if some > of your lock-relaxing ideas were followed. Segregating abusers solves both problems. If we do this then we don't need to drop the locks from the nonblocking pool, which solves the security problem. And it also means that each process has its own CRNG, which is way faster than /dev/urandom even if you don't have the locking problem, and it provides per-process isolation, which means that process A can't carry out a backtracking attack on process B. > > Most processes don't actually use that much randomness, and I'm not > > that worried about in-kernel users of the nonblocking pool. Even with > > the most exec-heavy workload, setting up a new exec image is > > heavyweight enough that you're really not going to be contending on > > the lock. I also have trouble with someone spending $$$$ on a system > > with 1K cpu cores and wasting all of their CPU power with running > > shell scripts that fork and exec a lot. :-) > > But I just re-read Andi's original trouble report, and although he mentions > AT_RANDOM, it's an applicatio reading from /dev/urandom a lot that's > causing the problem *not* execve. My memory may have gotten confused. > > I can imagine that one /dev/urandom abuser can minopolize the locck and > cause problems for a shell script. Well, that's my point. If we restrict the nonblocking pool to kernel users, then a /dev/urandom abuser won't be able to cause problems for the shell script. And even the most inefficient shell script which is firing off hundreds of processes per second is unlikely to be able to swamp the spin loop, *and* I would hope that someone who spent $$$ on a super-expensive 1K cpu system would also have the wit to actually recode the shell script in a more efficient compiled language, instead of wasting all of that expensive hardware. > Remember that making antibacktracking work is the entire problem we're > struggling to solve. If discarding it is on the table, I can solve > the scalability problems extremely easily. Even without giving it up > completely, just put the add-back inside if(trylock()) and the problem > goes away. The trylock() scheme is a bit dangerous, since we would need to make sure that *all* times when other callers take the lock, the contents of the pool would have changed. Or else, a subseqent call to extract entropy from that CPU will return the same value. And even if that were true today (or we could make it be true) if that ever changed, it would break the code. So it makes it pretty fragile. > I'm also not sure where you get 72 bytes from. You need 32 bytes of > key, 8 bytes of nonce, and 4 or 8 bytes of stream position to form the > ChaCha input block. The ChaCha 20 state block is 64 bytes, and then I was assuming two 4 byte control variables, for the number of cranks and the time since last reseed. We could actually store those control variables into the IV portion of the ChaCha state structure, which would make it be 64 bytes --- or we could generate a new state structure each time and not bother storing the 16 bytes of constants in the state structure, which trades a tiny amount of time and stack space for memory. These are all implementation details, though.... > But why bother with even that much? If you're willing to discard > antibacktracking, just have *one* key for the kernel, reseeded more > often, and a per-thread nonce and stream position. Well, we're not completely discarding backtracking protection. We are discarding backtracking protection between successive reads from a single process, and even there we would be reseeding every five minutes (and this could be tuned), so there is *some* anti-backtracking protection. I'm going to make the claim that if a particular process is reading from /dev/urandom in a tight loop, you probably don't *need* backtracking. You're probably doing something silly such as using /dev/urandom to overwrite a disk, or some such. On the flip side, the time when you might care about anti-backtracing protection is say, when you're generating a new session key for a new connection. So perhaps one approach is to use some kind of ratelimiter algorithm so that if you're using /dev/urandom "carefully" (say, no more than ten times a second), we'll use the non-blocking pool. But once a process exceeds that limit, it will switch over the the CRNG, and then the only performance that abuser process will hurt is its own (because it would be even faster if they were running something like arc4random in userspace). > But without interfering with legitimate users of /dev/urandom at all, > I'd be quite willing to say that as soon as you read more than 32 bytes > (current request plus recent history) from /dev/urandom, you get a > private ChaCha20 structure to read from. Yeah, that's what I was thinking, although I was willing to be a bit more generous about when we switch them over to using the ChaCha pool. I think doing this automatically is going to be much better than creating a new /dev/frandom, since it's going to be hard to get applications to switch over. We're still several years away from swtiching people over to the new getrandom(2) system call, after all. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-12 22:40 +0200 |
| Message-ID | <qiS2Z-1Am-3@gated-at.bofh.it> |
| In reply to | #1244709 |
Theodore Ts'o wrote:
> On Mon, Oct 12, 2015 at 03:49:08AM -0400, George Spelvin wrote:
>> Words 5..9 never got mixed at all.
> Hmm, good point. It *shouldn't* matter if the hash is secure, but the
> potentially uneven mixing would be a concern.
I don't quite follow the "shouldn't matter" part. The problem is that
insufficient input mixing can cause collisions, which are loss of entropy.
The output hash(the secure one) can't fix that.
The whole reason for the 5-tap LFSR is to ensure that each input word
affects a significant number of *other* words before getting stored into
by fresh input.
I just realized a worse problem: suppose CPU 1 has an offset of -1.
It will proceed to *undo* the mixing just done by CPU 0. I don't just
mean that it'll store its input over top, but it will also undo the
LFSR XOR. Ack!
(Maybe I'll retract that "bow before the master" remark. :-))
> They used to go through the input pool, and when we added the per-CPU
> fast pool, we didn't revisit the question of whether the input_rotate
> was still needed. So yes, at this point it might be worthwhile to
> remove the input_rotate part of the mixing scheme.
The fast pools actually just extended an issue which the three-pool
design created: when spilling from one pool to the other, the whole
"expensive output, cheap input" optimization makes no sense.
For raw data and interrupt overhead, yes obviously. But when it's
8 sha_transform() calls to generate 10 bytes, the design of the
subsequent input hash needs some rethinking.
It may make sense to have a separate path for "known high-quality"
input that puts more effort into diffusion.
Idea 1: Given that we do have an entropy estimate with every write to a
pool, what if we did an input hash that did work proportional
to the *entropy* of the input. With some lower bound for
zero-entropy writes like plain /dev/random writes and mixback.)
Idea 2: For input mixing not in interrupt context, which includes all
input to the output pools, it would be smaller and simpler code
to just XOR into the pool, and defer mixing until one whole-pool
mixing pass after the XOR position reched the end of the pool.
Concurrent writers could do a single atomic_add_return to
find an add position, and if that extended past the end of the
buffer, they'd obtain the lock, stir the pool, decrement the add
position (which would permit other concurrent writers) and then
do their XORs.
There's still the risk of races between delayed non-locking
inputters and stirrers, but maybe if non-locking inputters
were limited to non-critical mixbacks, that would be manageable.
>> However, I *also* have to use atomic_add to write r->pool[i],
>> which is indeed expensive. PoC diff attached, but I'm not sure if
>> you'll like it.
> Yeah, that was the part that worried me. Whether we use an atomic add
> or an atomic xor, it's going to be very expensive. Using an atomic add
> means that it will work with arm, but there's an explicit loop with
> arm, so on an arm system, it effectively turns into a more efficient
> spinlock, except you're spinning on each byte, so instead of bouncing
> cache lines with the locking granularity of the extract, we would be
> bouncing cache lines for every single byte of the mixback operation.
Yes. The current ticket spinlocks are little more than a single
atomic_add_return, and the dangers of putting multiple locks in the same
cache line is well known.
> Segregating abusers solves both problems. If we do this then we don't
> need to drop the locks from the nonblocking pool, which solves the
> security problem.
Er, sort of. I still think my points were valid, but they're
about a particular optimization suggestion you had. By avoiding
the need for the optimization, the entire issue is mooted.
I still say a separate firewall is a bad way to *solve* security problems,
but it can avoid preformance pressure to *create* them in the first place.
>> I can imagine that one /dev/urandom abuser can minopolize the locck and
>> cause problems for a shell script.
> Well, that's my point. If we restrict the nonblocking pool to kernel
> users, then a /dev/urandom abuser won't be able to cause problems for
> the shell script.
And I quite agree with that. Sorry, sometimes a discussion goes in
multiple directions and it's hard to keep track of the point of any
particular sentence.
I get fixated on one point and intrepret comments about something else
as if they pertained to the issue I'm thinking about.
> The trylock() scheme is a bit dangerous, since we would need to make
> sure that *all* times when other callers take the lock, the contents
> of the pool would have changed. Or else, a subseqent call to extract
> entropy from that CPU will return the same value. And even if that
> were true today (or we could make it be true) if that ever changed, it
> would break the code. So it makes it pretty fragile.
Sorry, yes, I'm prefectly aware of this, I just glossed over it.
Each extraction has to have a unique nonce; that's non-negotiable, but
not hard to achieve. We'd need to add a per-cpu counter to go along
with the CPU id to make the extraction nonce.
Doing this would be valuable *anyway*, because it would let us
reduce the mixback to once per read() rather than once per 10 bytes.
(Also, what would you say to reducing arch_get_random_long() to 16
bytes, and reserving hash.w[5] for the nonce? That would ensure that
even a malicious arch_get_random_long() couldn't force a collision.)
> The ChaCha 20 state block is 64 bytes, and then I was assuming two 4
> byte control variables, for the number of cranks and the time since
> last reseed. We could actually store those control variables into the
> IV portion of the ChaCha state structure, which would make it be 64
> bytes --- or we could generate a new state structure each time and not
> bother storing the 16 bytes of constants in the state structure, which
> trades a tiny amount of time and stack space for memory. These are
> all implementation details, though....
You have to copy the state *anyway* because you don't want it overwritten
by the ChaCha output, so there's really no point storing the constants.
(Also, ChaCha has a simpler input block structure than Salsa20; the
constants are all adjacent.)
And ChaCha includes a stream position counter itself, so you don't need
a separate one.
(Note: one problem with ChaCha specifically is that is needs 16x32 bits
of registers, and Arm32 doesn't quite have enough. We may want to provide
an arch CPRNG hook so people can plug in other algorithms with good
platform support, like x86 AES instructions.)
>> But why bother with even that much? If you're willing to discard
>> antibacktracking, just have *one* key for the kernel, reseeded more
>> often, and a per-thread nonce and stream position.
> Well, we're not completely discarding backtracking protection. We are
> discarding backtracking protection between successive reads from a single
> process, and even there we would be reseeding every five minutes (and
> this could be tuned), so there is *some* anti-backtracking protection.
Yeah, I realized this a few hours after sending that e-mail.
Anti-backtracking between processes is more important than within.
> I'm going to make the claim that if a particular process is reading
> from /dev/urandom in a tight loop, you probably don't *need*
> backtracking. You're probably doing something silly such as using
> /dev/urandom to overwrite a disk, or some such.
I fully agree.
> On the flip side, the time when you might care about anti-backtracing
> protection is say, when you're generating a new session key for a new
> connection. So perhaps one approach is to use some kind of
> ratelimiter algorithm so that if you're using /dev/urandom "carefully"
> (say, no more than ten times a second), we'll use the non-blocking
> pool. But once a process exceeds that limit, it will switch over the
> the CRNG, and then the only performance that abuser process will hurt
> is its own (because it would be even faster if they were running
> something like arc4random in userspace).
I consider the size of the read at least as much as the rate.
As mentioned in the random(4) man page, I don't think more than 256
bits of computational security even exists. Human Bitcoin mining is
(per http://bitcoincharts.com/) doing 440051 Thash/s, which is 80 bits
per month.
We can extrapolate computational feasibility beyond what's currently
been done. I think 128-bit claims are defensible. But once we get beyond
the square of anything ever attempted (170 bits or so), security claims
really don't know what they're talking about. 256 bits is the *cube*.
That's just crazy talk.
This in turn means that someone asking for more than 256 bits of seed
material is doing something stupid. (In the more diplomatic language of
the man page, "should be taken as a sign that its cryptography is _not_
skillfully implemented." I didn't want to totally condmen quick one-time
hacks.)
>> But without interfering with legitimate users of /dev/urandom at all,
>> I'd be quite willing to say that as soon as you read more than 32 bytes
>> (current request plus recent history) from /dev/urandom, you get a
>> private ChaCha20 structure to read from.
> Yeah, that's what I was thinking, although I was willing to be a bit
> more generous about when we switch them over to using the ChaCha pool.
> I think doing this automatically is going to be much better than
> creating a new /dev/frandom, since it's going to be hard to get
> applications to switch over. We're still several years away from
> swtiching people over to the new getrandom(2) system call, after all.
I worry this might attract the same sort of shitstorm as the SHA-3
proposal to tweak Keccak's preimage resistance (which, for the benefit of
the peanut gallery, was solid cryptographic engineering that belatedly
fixed a stupidity in the original SHA-3 contest rules), but if you're
up for it, I'm not going to object.
I'm not too hung up on the thresholds, as long as we catch bulk
readers on the first read, rather than wait until *after* they've
drained /dev/urandom. I'd prefer a single 64-byte read request would
move to mitigation mode, but I could be talked into 128. (Actually,
it would probably make more sense to have the threshold be a multiple
of EXTRACT_SIZE.)
History is probably best kept in a leaky bucket of some sort. That has a
current level and last update jiffies, and each read, we subtract off
the allowed maximum rate from the level.
(Or would an exponential average be better? That would make the maximum
read rate more strongly dependent on the evenness of the spacing.)
Then add that (scaled somehow?) to the current read size and compare
with the threshold.
The same variables can be used (with different parameters) to decide if
we want to get out of mitigation mode. The one thing to watch out for
is that "cat </dev/urandom >/dev/sdX" may have some huge pauses once
the buffer cache fills. We don't want to forgive after too small a
fixed interval.
Finally, we have the issue of where to attach this rate-limiting structure
and crypto context. My idea was to use the struct file. But now that
we have getrandom(2), it's harder. mm, task_struct, signal_struct, what?
(Post-finally, do we want this feature to be configurable under
CONFIG_EMBEDDED? I know keeping the /dev/random code size small is
a speficic design goal, and abuse mitigation is optional.)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-12 22:40 +0200 |
| Message-ID | <qiS30-1Am-23@gated-at.bofh.it> |
| In reply to | #1245112 |
(BTW, my previous e-mail went out early due to a mis-click. It was almost done, but please excuse any unfinished sentences.) -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Theodore Ts'o <tytso@mit.edu> |
|---|---|
| Date | 2015-10-13 04:50 +0200 |
| Message-ID | <qiXP4-1wY-9@gated-at.bofh.it> |
| In reply to | #1245112 |
On Mon, Oct 12, 2015 at 04:30:59PM -0400, George Spelvin wrote: > > Segregating abusers solves both problems. If we do this then we don't > > need to drop the locks from the nonblocking pool, which solves the > > security problem. > > Er, sort of. I still think my points were valid, but they're > about a particular optimization suggestion you had. By avoiding > the need for the optimization, the entire issue is mooted. Sure, I'm not in love with anyone's particular optimization, whether it's mine, yours, or Andi's. I'm just trying to solve the scalability problem while also trying to keep the code maintainable and easy to understand (and over the years we've actually made things worse, to the extent that having a single mixing for the input and output pools is starting to be more of problem than a feature, since we're coding in a bunch of exceptions when it's the output pool, etc.). So if we can solve a problem by routing around it, that's fine in my book. > You have to copy the state *anyway* because you don't want it overwritten > by the ChaCha output, so there's really no point storing the constants. > (Also, ChaCha has a simpler input block structure than Salsa20; the > constants are all adjacent.) We're really getting into low-level implementations here, and I think it's best to worry about these sorts of things when we have a patch to review..... > (Note: one problem with ChaCha specifically is that is needs 16x32 bits > of registers, and Arm32 doesn't quite have enough. We may want to provide > an arch CPRNG hook so people can plug in other algorithms with good > platform support, like x86 AES instructions.) So while a ChaCha20-based CRNG should be faster than a SHA-1 based CRNG, and I consider this a good thing, for me speed is **not** more important than keeping the underlying code maintainable and simple. This is one of the reasons why I looked at, and then discarded, to use x86 accelerated AES as the basis for a CRNG. Setting up AES so that it can be used easily with or without hardware acceleration looks very complicated to do in a cross-architectural way, and I don't want to drag in all of the crypto layer for /dev/random. > The same variables can be used (with different parameters) to decide if > we want to get out of mitigation mode. The one thing to watch out for > is that "cat </dev/urandom >/dev/sdX" may have some huge pauses once > the buffer cache fills. We don't want to forgive after too small a > fixed interval. At least initially, once we go into mitigation mode for a particular process, it's probably safer to simply not exit it. > Finally, we have the issue of where to attach this rate-limiting structure > and crypto context. My idea was to use the struct file. But now that > we have getrandom(2), it's harder. mm, task_struct, signal_struct, what? I'm personally more inclined to keep it with the task struct, so that different threads will use different crypto contexts, just from simplicity point of view since we won't need to worry about locking. Since many processes don't use /dev/urandom or getrandom(2) at all, the first time they do, we'd allocate a structure and hang it off the task_struct. When the process exits, we would explicitly memzero it and then release the memory. > (Post-finally, do we want this feature to be configurable under > CONFIG_EMBEDDED? I know keeping the /dev/random code size small is > a speficic design goal, and abuse mitigation is optional.) Once we code it up we can see how many bytes this takes, we can have this discussion. I'll note that ChaCha20 is much more compact than SHA1: text data bss dec hex filename 4230 0 0 4230 1086 /build/ext4-64/lib/sha1.o 1152 304 0 1456 5b0 /build/ext4-64/crypto/chacha20_generic.o ... and I've thought about this as being the first step towards potentially replacing SHA1 with something ChaCha20 based, in light of the SHAppening attack. Unfortunately, BLAKE2s is similar to ChaCha only from design perspective, not an implementation perspective. Still, I suspect the just looking at the crypto primitives, even if we need to include two independent copies of the ChaCha20 core crypto and the Blake2s core crypto, it still should be about half the size of the SHA-1 crypto primitive. And from the non-plumbing side of things, Andi's patchset increases the size of /dev/random by a bit over 6%, or 974 bytes from a starting base of 15719 bytes. It ought to be possible to implement a ChaCha20 based CRNG (ignoring the crypto primitives) in less than 974 bytes of x86_64 assembly. :-) - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Raymond Jennings <shentino@gmail.com> |
|---|---|
| Date | 2015-10-13 06:30 +0200 |
| Message-ID | <qiZnQ-3UZ-5@gated-at.bofh.it> |
| In reply to | #1245303 |
On Mon, Oct 12, 2015 at 7:46 PM, Theodore Ts'o <tytso@mit.edu> wrote: > On Mon, Oct 12, 2015 at 04:30:59PM -0400, George Spelvin wrote: >> > Segregating abusers solves both problems. If we do this then we >> don't >> > need to drop the locks from the nonblocking pool, which solves the >> > security problem. >> >> Er, sort of. I still think my points were valid, but they're >> about a particular optimization suggestion you had. By avoiding >> the need for the optimization, the entire issue is mooted. > > Sure, I'm not in love with anyone's particular optimization, whether > it's mine, yours, or Andi's. I'm just trying to solve the scalability > problem while also trying to keep the code maintainable and easy to > understand (and over the years we've actually made things worse, to > the extent that having a single mixing for the input and output pools > is starting to be more of problem than a feature, since we're coding > in a bunch of exceptions when it's the output pool, etc.). > > So if we can solve a problem by routing around it, that's fine in my > book. > >> You have to copy the state *anyway* because you don't want it >> overwritten >> by the ChaCha output, so there's really no point storing the >> constants. >> (Also, ChaCha has a simpler input block structure than Salsa20; the >> constants are all adjacent.) > > We're really getting into low-level implementations here, and I think > it's best to worry about these sorts of things when we have a patch to > review..... > >> (Note: one problem with ChaCha specifically is that is needs 16x32 >> bits >> of registers, and Arm32 doesn't quite have enough. We may want to >> provide >> an arch CPRNG hook so people can plug in other algorithms with good >> platform support, like x86 AES instructions.) > > So while a ChaCha20-based CRNG should be faster than a SHA-1 based > CRNG, and I consider this a good thing, for me speed is **not** more > important than keeping the underlying code maintainable and simple. > This is one of the reasons why I looked at, and then discarded, to use > x86 accelerated AES as the basis for a CRNG. Setting up AES so that > it can be used easily with or without hardware acceleration looks very > complicated to do in a cross-architectural way, and I don't want to > drag in all of the crypto layer for /dev/random. > >> The same variables can be used (with different parameters) to >> decide if >> we want to get out of mitigation mode. The one thing to watch out >> for >> is that "cat </dev/urandom >/dev/sdX" may have some huge pauses once >> the buffer cache fills. We don't want to forgive after too small a >> fixed interval. > > At least initially, once we go into mitigation mode for a particular > process, it's probably safer to simply not exit it. > >> Finally, we have the issue of where to attach this rate-limiting >> structure >> and crypto context. My idea was to use the struct file. But now >> that >> we have getrandom(2), it's harder. mm, task_struct, signal_struct, >> what? > > I'm personally more inclined to keep it with the task struct, so that > different threads will use different crypto contexts, just from > simplicity point of view since we won't need to worry about locking. > > Since many processes don't use /dev/urandom or getrandom(2) at all, > the first time they do, we'd allocate a structure and hang it off the > task_struct. When the process exits, we would explicitly memzero it > and then release the memory. > >> (Post-finally, do we want this feature to be configurable under >> CONFIG_EMBEDDED? I know keeping the /dev/random code size small is >> a speficic design goal, and abuse mitigation is optional.) > > Once we code it up we can see how many bytes this takes, we can have > this discussion. I'll note that ChaCha20 is much more compact than > SHA1: > > text data bss dec hex filename > 4230 0 0 4230 1086 /build/ext4-64/lib/sha1.o > 1152 304 0 1456 > 5b0 /build/ext4-64/crypto/chacha20_generic.o > > ... and I've thought about this as being the first step towards > potentially replacing SHA1 with something ChaCha20 based, in light of > the SHAppening attack. Unfortunately, BLAKE2s is similar to ChaCha > only from design perspective, not an implementation perspective. > Still, I suspect the just looking at the crypto primitives, even if we > need to include two independent copies of the ChaCha20 core crypto and > the Blake2s core crypto, it still should be about half the size of the > SHA-1 crypto primitive. > > And from the non-plumbing side of things, Andi's patchset increases > the size of /dev/random by a bit over 6%, or 974 bytes from a starting > base of 15719 bytes. It ought to be possible to implement a ChaCha20 > based CRNG (ignoring the crypto primitives) in less than 974 bytes of > x86_64 assembly. :-) > > - Ted > > -- > To unsubscribe from this list: send the line "unsubscribe > linux-kernel" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > Please read the FAQ at http://www.tux.org/lkml/ This might be stupid, but could something asynchronous work? Perhaps have the entropy generators dump their entropy into a central pool via a cycbuf, and have a background kthread manage the per-cpu or per-process entropy pools? -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-13 10:00 +0200 |
| Message-ID | <qj2F4-98-1@gated-at.bofh.it> |
| In reply to | #1245333 |
> This might be stupid, but could something asynchronous work? Perhaps
> have the entropy generators dump their entropy into a central pool via
> a cycbuf, and have a background kthread manage the per-cpu or
> per-process entropy pools?
No for two reasons:
(Minor): One of the functions of the mixback is to ensure that the next
reader hashes a *different* pool state. If the mixback is
delayed, the next reader might hash the *same* pool state and
return the same numbers. (There are easy workarounds for this.)
(Major): What do you do when the circular buffer is full? If it's not safe
to skip the mixback, then we have to block and get into the same
lock-contention problem.
But... this suggestion of having a separate thread do the mixback gives
me an idea. In fact, I think it's a good idea.
Ted (or anyone else listening), what do you think of the following?
I think it would solve Andi's problem and be a smaller code change than
the abuse mitigation mode. (Which is still a good idea, but is off the
critical path.)
- Associated with a pool is an atomic "mixback needed" flag.
- Also an optional mixback buffer. (Optional because the mixback
could just recompute it.)
- Dropping the lock requires the following operations:
- Test the mixback needed flag. If set,
- Copy out and wipe the buffer,
- smp_wmb()
- Clear the flag
- smp_wmb()
- Do the mixback, and
- Re-check again before dropping the lock.
(This check before dropping the lock is technically an optional
optimization.)
- Drop the lock.
- smp_mb() (Since it's write-to-read, we can't use _rmb or _wmb.)
- Test the mixback pending flag again.
- If it's set, trylock(). If that succeeds, go do the mixback as above.
- If it fails, return.
Each reader uses already-discussed nonce techniques to safely do concurrent
reads from the same pool. Then, at the end:
- (Optional) trylock() and, if it succeeds,
do mixback directly.
- Copy our mixback data to the buffer (race conditions be damned)
- smp_wmb()
- set the mixback needed flag
- smp_mb() (Since it's write-to-read; or use smp_store_mb())
- trylock()
- If that fails. return
- If that succeeds (and the flag is still set) do the mixback
This is based on the fact that if there are multiple concurrent reads,
we only need one mixback (thus, only one buffer/flag), but the "last one
out the door" has to do it.
Also, we don't care if we mis-count and end up doing it twice.
Each reader sets the flag and *then* does a trylock. If the trylock fails,
it's guaranteed that the lock-holder will see the flag and take care of
the mixback for us.
The writers drop the lock and *then* test the flag.
The result is that readers *never* do a blocking acquire of the pool
lock. Which should solve all the contention problems. Andi's stupid
application will still be stupid, but won't fall off a locking cliff.
(We could also use w[5] as the "mixback needed" flag and just
force it to 1 on the off chance it's zero with negligible loss
of entropy and zero security loss.)
The one thing I worry about is livelock keeping one thread in the
mixback code indefinitely, which can be mitigated by dropping the lock
and waiting before re-testing and re-acquiring if we loop too often.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-13 08:30 +0200 |
| Message-ID | <qj1fX-6Co-11@gated-at.bofh.it> |
| In reply to | #1245303 |
> We're really getting into low-level implementations here, and I think > it's best to worry about these sorts of things when we have a patch to > review..... > it's probably safer to simply not exit it. > I'm personally more inclined to keep it with the task struct, so that > different threads will use different crypto contexts, just from > simplicity point of view since we won't need to worry about locking. > Once we code it up we can see how many bytes this takes, we can have > this discussion. I'm fine with all of these; thank you. > This is one of the reasons why I looked at, and then discarded, to use > x86 accelerated AES as the basis for a CRNG. Setting up AES so that > it can be used easily with or without hardware acceleration looks very > complicated to do in a cross-architectural way, and I haven't looked as deeply, but it didn't look too hard. Is it possible to briefly explain the problem? I assumed you'd have an arch-specific capabilities probe function that would set up an operations structure. That would provide the various buffer sizes required, and setup (kernel_fpu_begin() and key scheduling) CPRNG core, and teardown (kernel_fpu_end()) functions. It there some huge gotcha I'm overlooking? > I don't want to drag in all of the crypto layer for /dev/random. Oh, gods, no; the crypto layer drives me nuts. Truthfully, the main hair of the crypto layer is all the modular cipher modes on top of block ciphers, and the scatterlist stuff to handle arbitrarily fragmented input and output buffers for the benefit of the network layer, but the code is horrible reading. Every time I look, I find something I want to fix (the CTS mode implementation uses 6 blocks worth of stack buffer; I have a patch to reduce that to 3) but then I get lost is the morass of structures and wrappers trying to make the code fit in with the rest. There's a struct crypto_tfm, crypto_alg, crypto_instance, cipher_desc, crypto_type, crypto_template, crypto_spawn... I've been trying to read it and I still have no idea what half of them are for. And I *still* haven't figured out how to get the self-test code to tell me that test X was performed and passed. I ended up writing my own test, which seems wrong. > ... and I've thought about this as being the first step towards > potentially replacing SHA1 with something ChaCha20 based, in light of > the SHAppening attack. Unfortunately, BLAKE2s is similar to ChaCha > only from design perspective, not an implementation perspective. > Still, I suspect the just looking at the crypto primitives, even if we > need to include two independent copies of the ChaCha20 core crypto and > the Blake2s core crypto, it still should be about half the size of the > SHA-1 crypto primitive. Well, the SHAppening doesn't really change much except a slight schedule tweak, but yeah, it's one of those things that would be nice to get around to. I'm not sure what you expect to do with ChaCha, though; it's really an expansion function, not compression, and not easily adapted to be one. BLAKE2 is a bit ugly. I'm generally not liking MD5/SHA-like designs that dribble the message and some round constants in; I'm much preferring the large-state "add a bunch of input all at once" designs like Keccak, SipHash and DJB's SHA-3 entry, CubeHash. Have you seen it? It's quite similar to Keccak, just using a 32x32 = 1024 bit state rather than Keccak's 25*64=1600. The reason it got dumped is because, like Keccak, to get n bits of preimage resistance, it requires 2n bits of "capacity" bits unused each round. When you ask for 512 bits of preimage resistance, you can only import a few bits of message each block. Keccak has the same problem, but it has a big enough block that it can handle it. In Dan's submission, you'll see his usual "this is a stupid request which I'm only paying lip service to", and his "SHA-3-512-formal" proposal was dog-slow. To quote: The "SHA-3-512-formal" proposal is aimed at users who are (1) concerned with attacks using 2^384 operations, (2) unconcerned with quantum attacks that cost far less, and (3) unaware that attackers able to carry out 2^256 operations would wreak havoc on the entire SHA-3 landscape, forcing SHA-3 to be replaced no matter which function is selected as SHA-3. The "SHA-3-512-normal" proposal is aimed at sensible users. For all real-world cryptographic applications, the "formal" versions here can be ignored, and the tweak amounts to a proposal of CubeHash16/32 as SHA-3." If NIST had proposed changing the preimage resistance rules *before* the final decision, things would have gone a lot differently. > And from the non-plumbing side of things, Andi's patchset increases > the size of /dev/random by a bit over 6%, or 974 bytes from a starting > base of 15719 bytes. It ought to be possible to implement a ChaCha20 > based CRNG (ignoring the crypto primitives) in less than 974 bytes of > x86_64 assembly. :-) Yes, not hard. Are you inspired, or would you like me to put together a patch? And should I do moderately evil space-saving things like store the pointer to the crypto state and the leaky bucket in the same task slot, distinguished by the pointer lsbit? -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Andi Kleen <andi@firstfloor.org> |
|---|---|
| Date | 2015-10-13 18:30 +0200 |
| Message-ID | <qjaCB-3wU-5@gated-at.bofh.it> |
| In reply to | #1245303 |
I tested the two proposed patches from earlier this thread on a 4S system. This was just with my (worst case) micro. Unfortunately both patches scale much worse than the duplicated pools, and can be even worse than the baseline (not sure why). The base line peaks at slightly above 200K ops/s with less than 20 CPUs. And the it gets slower until settling around 100K ops/s with more CPUs. Ted's patch peaks at 350K with four CPUs, but then quickly degrades to 50K ops/s at 20+ CPUs. At 144 CPUs it is slightly faster again at ~80K. Spelvin's patch peaks at only 140K at 2 CPUs (so it's slower than base line), stays around 120K upto 20, then degrades quickly to 50K and then slowly improves again to ~80K. The duplicated pool patch is ~200K upto 20 CPus, 400K upto 40, 600K at slightly below 60 CPUs, and then very slowly degrades to 520K at 144. -Andi -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-13 23:20 +0200 |
| Message-ID | <qjf9g-1Mb-23@gated-at.bofh.it> |
| In reply to | #1245886 |
> Ted's patch peaks at 350K with four CPUs, but then quickly degrades to > 50K ops/s at 20+ CPUs. At 144 CPUs it is slightly faster again at ~80K. Good to know, thanks! With its race conditions, it's basically a "best case" for that particular design, which tells me that more significant changes are required. Off hand, do you know how large a read each operation is? I want to reduce mixback from once per 10 bytes to once per read, and the size ratio will give me some idea of how large an improvement to expect. > Spelvin's patch peaks at only 140K at 2 CPUs (so it's slower than base line), > stays around 120K upto 20, then degrades quickly to 50K and then slowly > improves again to ~80K. Sorry to make you go to the trouble; I knew from discussions with Ted that it wasn't going to work. It was mostly just in the form of a patch for the sake of a more concrete discussion. I'll have a patch that I hope will do some good for testing in a couple of hours. > The duplicated pool patch is ~200K upto 20 CPus, 400K upto 40, 600K at > slightly below 60 CPUs, and then very slowly degrades to 520K at 144. Shitty performance is practically a design goal of /dev/urandom. You are NOT supposed to hit it more than once per minute per thread. But since we have a real-world problem with it, Ted's "abusse mitigation mode" idea (where the kernel does what the app should do: seed a private CPRNG and use that) will provide good security at extremely high access rates. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Andi Kleen <andi@firstfloor.org> |
|---|---|
| Date | 2015-10-14 04:20 +0200 |
| Message-ID | <qjjPA-10U-3@gated-at.bofh.it> |
| In reply to | #1246160 |
> Off hand, do you know how large a read each operation is? I want to > reduce mixback from once per 10 bytes to once per read, and the size > ratio will give me some idea of how large an improvement to expect. My test reads 64 bytes using the syscall. -Andi -- ak@linux.intel.com -- Speaking for myself only. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-16 07:30 +0200 |
| Subject | [RFC PATCH 0/4] Alternate sclable urandom patchset |
| Message-ID | <qk5Ky-4QJ-5@gated-at.bofh.it> |
| In reply to | #1246252 |
Sent as separate patches to make things easier to review; the action is all in #4. The first two are minor cleanups I've had in my tree for a while and felt like working on top of rather than backing out. The third I'm not happy with, but will serve as a proof-of-concept stub that I'll rewrite if the rest meets with approval. Since writing it, I've remembered that we already have a per-CPU "nonce pool" in the form of the get_random_int_hash array, and I should take advantage of that. Another thing I don't like is the mixback is only 160 bits, 80 of which are private. I'd rather have twice that, if the read is large enough. But that requires more code refactoring. But it does illustrate the basic idea of using a nonce to avoid the need to do synchronous mixback. We can do many calls to extract_buf, from the same or different processors, without doing mixback. The fourth is where the fun is. The names of things is certainly up for debate; creating a subclass of struct entropy_store called "entropy_store_plus" is not my proudest moment. I also considered just making the extra fields global variables. If someone wants to suggest an arrangement that's good for cache line sharing, that would be appreciated. But I think the nonblocking_mixback() function came out rather nice. This uses two locks, rather that the one in the idea I most recently posted, because add_interrupt_randomness() needs to take the lock, and I didn't want to force it to do an unbounded amount of mixback work. Using two locks avoids the need for interrupt handlers to do any mixback, and for readers to loop and thus possibly livelock. George Spelvin (4): random: Reduce stack usage in _xfer_secondary_pool random: Remove two unused arguments from extract_entropy() random: Only do mixback once per read random: Make non-blocking mixback non-blocking drivers/char/random.c | 218 ++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 184 insertions(+), 34 deletions(-) -- 2.6.1 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Date | 2015-10-16 07:40 +0200 |
| Subject | [RFC PATCH 2/4] random: Remove two unused arguments from extract_entropy() |
| Message-ID | <qk5Ue-51N-11@gated-at.bofh.it> |
| In reply to | #1248341 |
Now that _xfer_secondary_pool doesn't need the magic functionality,
the "min" and "reserved" arguments are always zero, so stop passing
them.
Signed-off-by: George Spelvin <linux@horizon.com>
---
drivers/char/random.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index c8ad49ba..e62b30ba 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1175,7 +1175,7 @@ static void extract_buf(struct entropy_store *r, __u8 out[EXTRACT_SIZE])
* pool after each pull to avoid starving other readers.
*/
static ssize_t extract_entropy(struct entropy_store *r, void *buf,
- size_t nbytes, int min, int reserved)
+ size_t nbytes)
{
ssize_t ret = 0, i;
__u8 tmp[EXTRACT_SIZE];
@@ -1199,7 +1199,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, nbytes);
- nbytes = account(r, nbytes, min, reserved);
+ nbytes = account(r, nbytes, 0, 0);
while (nbytes) {
extract_buf(r, tmp);
@@ -1284,7 +1284,7 @@ void get_random_bytes(void *buf, int nbytes)
nonblocking_pool.entropy_total);
#endif
trace_get_random_bytes(nbytes, _RET_IP_);
- extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
+ extract_entropy(&nonblocking_pool, buf, nbytes);
}
EXPORT_SYMBOL(get_random_bytes);
@@ -1374,7 +1374,7 @@ void get_random_bytes_arch(void *buf, int nbytes)
}
if (nbytes)
- extract_entropy(&nonblocking_pool, p, nbytes, 0, 0);
+ extract_entropy(&nonblocking_pool, p, nbytes);
}
EXPORT_SYMBOL(get_random_bytes_arch);
--
2.6.1
h
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
Page 1 of 2 [1] 2 Next page →
Back to top | Article view | linux.kernel
csiph-web