Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Am Samstag, 9. November 2013, 23:04:07 schrieb Clemens Ladisch: Hi Clemens, > 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. In the other email, I explained the different types of tests I performed. All of these tests show proper statistical results. Now, I also performed these tests without the Von-Neumann unbiaser. All of the statistical tests results still showed a white noise (note, in the next code release, I will have an allocation flag added that you can use to very simply deactivate the Von-Neumann unbiaser for testing). So, the Von-Neumann unbiaser is to be considered a line of defence against (not yet observed, but potential) skews. Similarly, the optional whitening (non-cryptographic) function of jent_stir_pool is yet another line of defence. So, bottom line: I fully concur that using two separate measurements may not imply that they are independent. But testing shows that it does not matter. > > The observations are derived from the internal CPU state, which is *not* > reset between measurements. > > > Regards, > Clemens Ciao Stephan -- | Cui bono? | -- 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
Am Samstag, 9. November 2013, 23:04:49 schrieb Clemens Ladisch: Hi Clemens, > 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 and by disabling CPU features -- as I have done. I am fully aware that statistical tests cannot prove the conclusion that the noise source is proper. 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. These formulas are based on deductive science but *not* inductive science (like math). - Oscillators: Again, the conclusion of oscillators being appropriate depends on deductive science. - Shot noise, Johnson noise, etc. of resistors, transistors is again based on deductive science. 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. So, there was never a proof in the sense of an inductive science of any noise source. That means I cannot be expected to show a full formulated proof based on inductive science of the noise source I offer here. Yet, I meet the deductive science approach with my RNG as I base my conclusions on a large array of measurements. And I give the tools to perform the measurements to everybody. So, everybody can easily redo the testing, or, if possible, prove me wrong! You may look into [1] and [2]. [1] mentions that inductive methods cannot reach absolute proof. > > > 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! What did I do so far: - Test the CPU in kernel and user mode. - Selectively and mutually disable CPU features (see appendix F.46 of my documentation). - Tested on quiet and heavily loaded CPUs. - Testing on the same physical system / CPU with different operating systems. What else can I do? 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? The test for the same values is caught with the Von-Neumann unbiaser. If I test for alternating values, other people may come in and ask to check for pattern x or y. But then, section 4.3 of my document contains an analysis of patterns. As I do not use a whitener, any pattern WILL be visible with the Chi-Square test result. All tests
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
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
[PATCH] CRYPTO: async_tx: Fixed a couple of typos
Fixed 2 typos in async_xor.c
---
crypto/async_tx/async_xor.c |4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/crypto/async_tx/async_xor.c b/crypto/async_tx/async_xor.c
index 8ade0a0..bcaa1e9 100644
--- a/crypto/async_tx/async_xor.c
+++ b/crypto/async_tx/async_xor.c
@@ -48,7 +48,7 @@ do_async_xor(struct dma_chan *chan, struct page *dest, struct
page **src_list,
int xor_src_cnt = 0;
dma_addr_t dma_dest;
- /* map the dest bidrectional in case it is re-used as a source */
+ /* map the dest bidirectional in case it is re-used as a source */
dma_dest = dma_map_page(dma->dev, dest, offset, len, DMA_BIDIRECTIONAL);
for (i = 0; i < src_cnt; i++) {
/* only map the dest once */
@@ -175,7 +175,7 @@ do_sync_xor(struct page *dest, struct page **src_list,
unsigned int offset,
* xor_blocks always uses the dest as a source so the
* ASYNC_TX_XOR_ZERO_DST flag must be set to not include dest data in
* the calculation. The assumption with dma eninges is that they only
- * use the destination buffer as a source when it is explicity specified
+ * use the destination buffer as a source when it is explicitly specified
* in the source list.
*
* src_list note: if the dest is also a source it must be at index zero.
--
1.7.10.4
--
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
