Re: [PATCH] hwrng: alea - Add support for Araneus Alea I USB RNG

[Clemens Ladisch]

Bob Ham wrote:
> Adds support for the Araneus Alea I USB hardware Random Number
> Generator.  This RNG creates entropy at a high rate, about 100kb/s.
>
> Signed-off-by: Bob Ham 
> ---
>
> +++ b/drivers/char/hw_random/alea.c

Why didn't you just add the device ID to chaoskey.c?
(Because that one is hidden in drivers/usb/misc? ;-)


Regards,
Clemens
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v2 1/6] SP800-90A Deterministic Random Bit Generator

[Clemens Ladisch]

Stephan Mueller wrote:
 This is a clean-room implementation of the DRBG defined in SP800-90A.

Why?  I guess it's for certification?

 +static bool drbg_fips_continuous_test(struct drbg_state *drbg,
 +  unsigned char *buf)
 ...
 + ret = memcmp(drbg-prev, buf, drbg_blocklen(drbg));
 + ...
 + /* invert the memcmp result, because the test shall pass when the
 +  * two compared values do not match */
 + if (ret)
 + return true;
 + else
 + return false;

This looks strange.  The return value of memcmp() is not really
a boolean, and the code appears not to match the comment because the
numeric value of ret is not actually inverted.  How about this:

ret = memcmp(...);
...
/* the test shall pass when the compared values are not equal */
return ret != 0;


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Clemens Ladisch]

Rafael Aquini wrote:
 This patch introduces changes to the random_write method so it can split the
 given seed and completely stir the output pools with different halves of it,
 when seed lenght allows us doing so.

 - ret = write_pool(blocking_pool, buffer, count);
 + ret = write_pool(pool1, buffer, count1);
   if (ret)
   return ret;
 - ret = write_pool(nonblocking_pool, buffer, count);
 + ret = write_pool(pool2, buffer + offset, count2);

Doesn't this assume that both halves of the buffer contain some
(uncredited) entropy?  In other words, wouldn't this result in worse
randomness for pool2 if the second half of the buffer contains just zero
padding?


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
 Rafael Aquini wrote:
 This patch introduces changes to the random_write method so it can
 split the given seed and completely stir the output pools with
 different halves of it, when seed lenght allows us doing so.

 -   ret = write_pool(blocking_pool, buffer, count);
 +   ret = write_pool(pool1, buffer, count1);
 if (ret)
 return ret;
 -   ret = write_pool(nonblocking_pool, buffer, count);
 +   ret = write_pool(pool2, buffer + offset, count2);

 Doesn't this assume that both halves of the buffer contain some
 (uncredited) entropy?  In other words, wouldn't this result in worse
 randomness for pool2 if the second half of the buffer contains just
 zero padding?

 [...]
 Coming back to your concern: sure, the caller can pad any data injected
 into /dev/?random with zeros.

Assume that the userspace of an embedded device wants to do the same
kind of initialization that a call to add_device_randomness() does, and
that it has some data like char serial_number[256].  The padding
wouldn't be done intentionally, it's just a property of the data (and it
wouldn't have mattered before this patch).

 But as writing to the character files is allowed to every user, this
 per definition must not matter (e.g. an attacker may simply write
 zeros or other known data into the character file). And the random.c
 driver handles that case appropriately by not increasing the entropy
 estimator when receiving data.

The problem is not with the entropy estimate.

 All the patch tries to achieve is to ensure that both pools are not
 always mixed with the same values.

Before this patch, both pools got mixed with the same values.  After
this patch, both pools indeed get mixed with different values, but now
one pool gets mixed with a known value if one half of the buffer happens
to be known.


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Freitag, 10. Januar 2014, 12:37:26 schrieb Clemens Ladisch:
 Stephan Mueller wrote:
 Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
 Rafael Aquini wrote:
 This patch introduces changes to the random_write method so it can
 split the given seed and completely stir the output pools with
 different halves of it, when seed lenght allows us doing so.

 - ret = write_pool(blocking_pool, buffer, count);
 + ret = write_pool(pool1, buffer, count1);

   if (ret)
   
   return ret;

 - ret = write_pool(nonblocking_pool, buffer, count);
 + ret = write_pool(pool2, buffer + offset, count2);

 Doesn't this assume that both halves of the buffer contain some
 (uncredited) entropy?  In other words, wouldn't this result in worse
 randomness for pool2 if the second half of the buffer contains just
 zero padding?

 [...]
 Coming back to your concern: sure, the caller can pad any data
 injected into /dev/?random with zeros.

 Assume that the userspace of an embedded device wants to do the same
 kind of initialization that a call to add_device_randomness() does, and
 that it has some data like char serial_number[256].  The padding
 wouldn't be done intentionally, it's just a property of the data (and
 it wouldn't have mattered before this patch).

 But as writing to the character files is allowed to every user, this
 per definition must not matter (e.g. an attacker may simply write
 zeros or other known data into the character file). And the random.c
 driver handles that case appropriately by not increasing the entropy
 estimator when receiving data.

 The problem is not with the entropy estimate.

 All the patch tries to achieve is to ensure that both pools are not
 always mixed with the same values.

 Before this patch, both pools got mixed with the same values.  After
 this patch, both pools indeed get mixed with different values, but now
 one pool gets mixed with a known value if one half of the buffer
 happens to be known.

 Do you imply in your example above that the serial number is unknown?
 Anything that unprivileged user space tries to inject into /dev/?random
 should be considered data with known value.

Like the kernel's add_device_randomness() function, this example assumes
that there is no persistent storage with a saved seed (or that it isn't
yet available), and that mixing a device-specific value at least
prevents multiple device instances from generating identical random
numbers.

This indeed helps only against attackers that do not know that serial
number.

If the data written by unprivileged users to /dev/?random were
considered known to *all* attackers, then it wouldn't make sense to
allow such writes at all.


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Mittwoch, 13. November 2013, 12:51:44 schrieb Clemens Ladisch:
 (And any setting that increases accesses to main memory is likey to
 introduce more entropy due to clock drift between the processor and the
 memory bus.  Or where do you assume the entropy comes from?)

 You nailed it. When I disable the caches using the CR0 setting, I get a
 massive increase in variations and thus entropy.

Now this would be an opportunity to use the number of main memory
accesses to estimate entropy.  (And when you're running out of the
cache, i.e., deterministically, is there any entropy?)

 XOR is a bijective operation.

 Only XOR with a constant, which is not what you're doing.

 If you want to regain the full 64 bit input bit stream, then you are
 right.

 But still, XOR is bijective with respect to the two bits that go into
 the operation.

Please look up what bijective actually means:
http://en.wikipedia.org/wiki/Bijection

 folding based on XOR is an appropriate way to collapse the string and
 yet retain entropy.

Correct, but the reason for that is not being bijective.

 If the observations are not independent, you cannot just assume that
 the estimate is off by a certain factor.  It means that the estimate
 is not applicable _at all_.

 Well, I am not so sure here.

So, what is the factor that you are saying is large enough?

 The RNG has the following safety margins where it is more conservative than
 measurements indicate:

 You _cannot_ measure entropy by looking at the output.  How would you
 differentiate between /dev/random and /dev/urandom?

 I think regarding the independence you can very well draw the conclusion
 based on the output, because any dependencies will ultimately form a
 pattern.

The output of a pure PRNG (such as /dev/urandom without entropy) is
dependent on the internal state, but there are no patterns detectable
from the output alone.

 In addition, we need to keep in mind that the independence claim is
 relative

No, independence is a property of the process that generates the
samples.

 If you have an output string that has no detectable patterns, i.e. looks
 like white noise, you can only assume that the observations are
 independent of each other. If there are patterns, you know that there
 are dependencies.

 That statement may *not* apply any more if you look at the internals of
 the RNG. In such a case, you may have even strong dependencies.

 The best example on this matter are deterministic RNGs with a
 cryptographic output function. When you see the output string, you only
 see white noise. As you cannot detect a pattern, you have to assume that
 the string provides independent observations. At least for you who looks
 from the outside cannot draw any conclusions from observing some output
 bit stream which would be the future bit stream. Yet, when you know the
 state of the RNG, you entire future output bit stream has no
 independence.

You cannot restrict the analysis to observations from the outside;
there are many people who can know about the CPU's internal structure.

 Coming back to the jitter RNG: I applied a large array of statistical
 tests and all of them concluded that the output is white noise, as
 explained in the documentation. That means when looking from the
 outside, there are no dependencies visible. Now you may say that this
 conclusion does not mean that there are no dependencies -- but I reply
 again, if there would be any, none of the array of statistical tests can
 detect it. So, how would an attacker detect patterns?

An attacker would not try to detect patterns; he would apply knowledge
of the internals.

Statistical tests are useful only for detecting the absence of entropy,
not for the opposite.


All your arguments about the output of the CPU jitter RNG also apply to
the output of /dev/urandom.  So are you saying that it would be a good
idea to loop the output of /dev/urandom back into /dev/random?


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Donnerstag, 14. November 2013, 11:51:03 schrieb Clemens Ladisch:
 An attacker would not try to detect patterns; he would apply knowledge
 of the internals.

 I do not buy that argument, because if an attacker can detect or deduce
 the internals of the CPU, he surely can detect the state of the
 input_pool or the other entropy pools behind /dev/random.

With internals, I do not mean the actual state of the CPU, but the
behaviour of all the CPU's execution engines.

An Intel engineer might know how to affect the CPU so that the CPU
jitter code measures a deterministic pattern, but he will not know the
contents of my memory.

 Statistical tests are useful only for detecting the absence of entropy,
 not for the opposite.

 Again, I fully agree. But it is equally important to understand that
 entropy is relative.

In cryptography, we care about absolute entropy, i.e., _nobody_ must be
able to predict the RNG output, not even any CPU engineer.


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Sonntag, 10. November 2013, 21:28:06 schrieb Clemens Ladisch:
 Many CPUs allow to disable branch prediction, but this is very vendor
 specific (try to find MSR documentation).  The biggest offender probably
 is the out-of-order execution engine, which cannot be disabled.

 For x86, I have not found a way to disable the unit.

My AMD processor can do this in the IC_CFG/DC_CFG MSRs.  (See the BKDG.)

The Intel Core family has other settings (such as data prefetching) that
are configurable in the IA32_MISC_ENABLE MSR.

(And any setting that increases accesses to main memory is likey to
introduce more entropy due to clock drift between the processor and the
memory bus.  Or where do you assume the entropy comes from?)

BTW: MFENCE is not guaranteed to flush the instruction pipeline; you
need CPUID for that.

 XOR is a bijective operation.

Only XOR with a constant, which is not what you're doing.

 There are so many assessments on entropy I make, I am surprised that I
 am said to have no entropy assessment.

 Again: Shannon entropy assumes that you have a sequence of independent
 and identically distributed random variables.  And you cannot prove
 these properties from the output; you need to know the process that
 generates the values.

 I am absolutely on your side here. And as we cannot (yet?) fully conclude that
 the observations are independent, a safety margin must always be considered.

If the observations are not independent, you cannot just assume that the
estimate is off by a certain factor.  It means that the estimate is not
applicable _at all_.

 The RNG has the following safety margins where it is more conservative than
 measurements indicate:

You _cannot_ measure entropy by looking at the output.  How would you
differentiate between /dev/random and /dev/urandom?


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Samstag, 9. November 2013, 23:04:49 schrieb Clemens Ladisch:
 Stephan Mueller wrote:
 Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o:
 On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote:
 That's unfortunate, since it leaves open the question of whether this
 jitter is something that could be at least somewhat predictable if you
 had a lot more information about the internal works of the CPU or
 not

 I do not understand that answer: I thought we are talking about the
 search of non-predictable noise sources. If you cannot predict the
 sequence even if you have the state of the CPU, that is what we are
 looking for, is it not?

 I was asking the question about whether someone who knew more about
 the internal _workings_ of the CPU, note of the state of the CPU.
 This is not necessarily the NSA guy, but someone who knows more
 about the internal workings of the Intel CPU (such as an Intel
 engineer --- and I've had Intel express misgivings about approaches
 which depend on CPU jitter approaches), or just someone who has
 spent a lot more time trying to examine the black box of the Intel CPU
 from the outside.

 I try to get more information from my contacts to other vendors. But I
 am wondering what shall we do if the answer is (maybe even proven with
 some test results) that they see the same issue themselves and have no
 handle on it?

 I mean, what is it that I would need to test and demonstrate to prove or
 disprove my RNG?

 You need to prove that the CPU will never get into an internal state
 where the loop execution times happen to form a predictable pattern.
 Alternatively, detect this so that the measurements can be thrown away.

 That statement sounds very nice, and I would love to prove it. But I do not
 see any way to do that except applying statistical tests on a large number of
 different systems

Then you cannot say anything about unknown future CPU models.

 But we have to keep requirements to my RNG in league with the research applied
 to other noise sources. Let us look at physical noise sources we all know and
 love:

 - The conclusion that radioactive decay is random is based on the quantum
 theory. That theory contains a number of formulas which were all validated
 with a plethora of measurements. Yet, there is no proof (in the mathematical
 sense) that the formulas are correct.

But we assume that the unpredictability of quantum mechanics is a limit
for _everyone_.  In the case of CPUs, the jitter you observe in delta
times results in part from the complexities of the inner state, and in
part from real random noise.  The first part is deterministic and might
be predicted by anyone who has enough knowledge about the CPU's
internals.

Additionally, physical noise sources allow us to estimate the entropy of
our measurements.  There is no such estimate for the CPU jitter RNG.

(BTW, the entropy calculations in the paper are meaningless, because the
Shannon formula assumes the values are created independently.  Entropy
calculation always depends on the process that created those values.
For example, the entropy of 110010011101101010100010001000 is
zero if you know that this is just pi.  To take a more relevant example,
assume a completely deterministic CPU where each measuring loop takes
exactly one timer tick; the delta times would look like this:
  1 1 1 1 1 1 1 1 1 1 1 1 ...
Now assume that the timer runs at a speed of 4/3 relative to the CPU,
i.e., every third loop, another tick has accumulated:
  1 1 2 1 1 2 1 1 2 1 1 2 ...
Now assume that in every fourth loop iteration, the instruction decoder
falls behind and stalls the pipeline for the same time as one loop
iteration:
  1 1 2 2 2 1 1 3 1 2 1 3 ...
This sequence still has zero entropy.)

 For software:

 - The noise sources of interrupts, HID events, HDD fluctuations are all based
 on deductive science. There is even no formulas or other mathematical model
 behind them to state that they are good for RNGs.

Indeed.  However, in the absence of a 'real' RNG, these are the best
that the kernel has.  And at least these events come from multiple
sources and are mostly independent.

 We can certainly test very much, but one thing we cannot prove, and
 that is the fundamental jitter, provided it is a result of quantum
 fluctuations. Just as with any other noise source, basic fundamental
 principles are hard if not impossible to test.

 You cannot test if the noise source was replaced with fake hardware.
 But if you know the characteristics of the noise source, you can test
 for likely failure modes, such as the output value being stuck or
 oscillating.

 And here I am asking for help!  [...]
 When you ask for testing of stuck values, what shall I really test for?
 Shall I test adjacent measurements for the same or alternating values?

Same or alternating delta time values happen even on random CPUs.  You
need a theory of how random and non-random CPUs work, and how

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Sonntag, 10. November 2013, 17:31:07 schrieb Clemens Ladisch:
 In the case of CPUs, the jitter you observe in delta
 times results in part from the complexities of the inner state, and in
 part from real random noise.  The first part is deterministic and might
 be predicted by anyone who has enough knowledge about the CPU's
 internals.

 Right, and that is why I tried to eliminate the CPU mechanisms that may be
 having a deterministic impact. If I miss a mechanism or your have other
 suggestions, please help me.

Many CPUs allow to disable branch prediction, but this is very vendor
specific (try to find MSR documentation).  The biggest offender probably
is the out-of-order execution engine, which cannot be disabled.

 When you ask for testing of stuck values, what shall I really test for?
 Shall I test adjacent measurements for the same or alternating values?

 Same or alternating delta time values happen even on random CPUs.  You
 need a theory of how random and non-random CPUs work, and how this
 difference affects the delta times, before you can test for that.

 Are you telling me that I should invent a formula and apply it?

I was not implying that the theory has nothing to do with the physical
device.  It must correctly _describe_ the relevant physical processes.

 The test for the same values is caught with the Von-Neumann unbiaser.

 No, the von Neumann unbiaser is run on the whitened bitstream, i.e.,
 _after_ the folding operation.

 The folding is whitened? How do you reach that conclusion? Yes, the folding is
 my (very simple) post-processing. But I am not calling it whitened as all
 statistical problems the underlying variations have *will* be still visible in
 the folded value.

If you don't want to call it whitening, call it randomness extraction
instead.  But its input is a series of delta times like this:
  01010011
  10011010
  01011011
  01100100
  10111000
and the purpose of the folding is to remove these zero patterns.

 What would you expect me to do when I should do to come up with an entropy
 estimate that I not already have done?

I do not expect you (or anybody) to be able to come up with a correct
entropy estimate for CPU jitter.

 There are so many assessments on entropy I make, I am surprised that I
 am said to have no entropy assessment.

Again: Shannon entropy assumes that you have a sequence of independent
and identically distributed random variables.  And you cannot prove
these properties from the output; you need to know the process that
generates the values.


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Donnerstag, 7. November 2013, 02:03:57 schrieb Nicholas Mc Guire:
 On Wed, 06 Nov 2013, Stephan Mueller wrote:
 Besides, how on earth shall an attacker even gain knowledge about the
 state of the CPU or disable CPU mechanisms? Oh, I forgot, your NSA
 guy. But if he is able to do that, all discussions are moot because
 he simply disables any noise sources by flipping a bit, reads the
 memory that is used to hold the state of the RNG or just overwrites
 the memory locations where data is collected, because the general
 protection mechanisms offered by the kernel and the underlying
 hardware are broken.

 No need to gain knowledge of the internal CPU state itt would be
 sufficient to be able to put the CPU in a sub-state-space in which
 the distribution is shifted. it may be enough to reduce the truely
 random bits of some key only by a few bits to make it suceptible to
 brute force attacks.

 Note, the proposed RNG contains an unbias operation (the Von-Neumann
 unbiaser) which is proven to remove any bias when it is established that
 the individual observations are independent. And the way the
 observations are generated ensures that they are independent.

Independent does not mean that your own code avoids reusing data from
the previous loop iteration; it means that the _entire_ process that
generates the bits is not affected by any memory of the past.

The observations are derived from the internal CPU state, which is *not*
reset between measurements.


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Clemens Ladisch]

Stephan Mueller wrote:
 Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o:
 On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote:
 That's unfortunate, since it leaves open the question of whether this
 jitter is something that could be at least somewhat predictable if you
 had a lot more information about the internal works of the CPU or not

 I do not understand that answer: I thought we are talking about the
 search of non-predictable noise sources. If you cannot predict the
 sequence even if you have the state of the CPU, that is what we are
 looking for, is it not?

 I was asking the question about whether someone who knew more about
 the internal _workings_ of the CPU, note of the state of the CPU.
 This is not necessarily the NSA guy, but someone who knows more
 about the internal workings of the Intel CPU (such as an Intel
 engineer --- and I've had Intel express misgivings about approaches
 which depend on CPU jitter approaches), or just someone who has
 spent a lot more time trying to examine the black box of the Intel CPU
 from the outside.

 I try to get more information from my contacts to other vendors. But I
 am wondering what shall we do if the answer is (maybe even proven with
 some test results) that they see the same issue themselves and have no
 handle on it?

 I mean, what is it that I would need to test and demonstrate to prove or
 disprove my RNG?

You need to prove that the CPU will never get into an internal state
where the loop execution times happen to form a predictable pattern.
Alternatively, detect this so that the measurements can be thrown away.

 We can certainly test very much, but one thing we cannot prove, and
 that is the fundamental jitter, provided it is a result of quantum
 fluctuations. Just as with any other noise source, basic fundamental
 principles are hard if not impossible to test.

You cannot test if the noise source was replaced with fake hardware.
But if you know the characteristics of the noise source, you can test
for likely failure modes, such as the output value being stuck or
oscillating.

In the case of CPU jitter measurements, you do not have direct access to
the noise source; you measure it indirectly through the CPU's internal
state.  So you need to know how the delta times of a noisy CPU are
different from the delta times of a CPU without or with unsuitable
noise source.


Regards,
Clemens
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html