RTM: Verify entropy collector works

RESOLVED FIXED in mozilla0.9.2

Status

P3
normal
RESOLVED FIXED
18 years ago
2 years ago

People

(Reporter: lord, Unassigned)

Tracking

1.0 Branch
mozilla0.9.2
x86
Other
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [kerh-coz] no checkin required) needs verification)

Attachments

(4 attachments)

(Reporter)

Description

18 years ago
We need to verify that the entropy collector in Mozilla is (a) collecting enough
entropy and (b) is stirring it into the PRNG on a regular basis.
(Reporter)

Comment 1

18 years ago
-> 2.0
-> P1
Priority: -- → P1
Target Milestone: --- → 2.0

Comment 2

18 years ago
Assigning to javi.
Assignee: ddrinan → javi

Comment 3

18 years ago
How exactly do I "verify" the entropy collector is working?  It's getting
called, but from earlier threads, that doesn't seem to be enough to verify.
Javi, here's a suggestion.  Put in some code that's ifdef TRACE, or 
something like that, that uses printf to print to stderr every time
the collector is called.  Printf should print the number of bytes 
being fed to the collector.  You might be able to accomplish the same
thing with a debugger (one certainly could with dbx).

Comment 5

18 years ago
I'm more concerned with what kind of test is sufficient for us to declare we're
getting enough entropy.

Comment 6

18 years ago
Is the number of bytes sufficient or do the byte values influence the entropy?
In other words do we need a random distrib for the values?
There are two separate issues here:

1. Is the entropy collector working?  (Javi's original question).
2. Does the data being collected contain sufficient entropy?

For the first question, it suffices to know the number of bytes being
input and the frequency of input operations.

For the second question, it is necessary to treat the input as a stream
of bits (not bytes or larger values) and measure the average value and 
variance of each bit in the input over multiple runs.  Ian McGreer has
written code to do this.  Ask him.

P.S. There are several bugs in bugzilla that seem to be asking the same 
questions.  Maybe some of them should be marked as duplicates.

Comment 8

18 years ago
Created attachment 39187 [details] [diff] [review]
patch that shows bytes sent to the RNG and when they arrived
Thanks Ian.  Would you add the perl script (or whatever it was) that 
analyzes this output as another attachment?

Updated

18 years ago
Depends on: 80841

Comment 10

18 years ago
Created attachment 39205 [details]
c code to analyze data from rng output

Comment 11

18 years ago
Here's how to use it:

gcc -o analyze analyze.c -lm

Build the browser with the #ifdef'ed code from the previous patch compiled in.

Then launch the browser and quit several times (10, say).  Each time, copy the
"rngoutput" file to something like "rngoutput0", "rngoutput1", etc.

once you have that set of data, do:

./analyze rngoutput*

You should see something like:

0.00 < entropy < 0.10 ] : 34395
0.10 < entropy < 0.20 ] : 0
0.20 < entropy < 0.30 ] : 50
0.30 < entropy < 0.40 ] : 28
0.40 < entropy < 0.50 ] : 54
0.50 < entropy < 0.60 ] : 0
0.60 < entropy < 0.70 ] : 157
0.70 < entropy < 0.80 ] : 130
0.80 < entropy < 0.90 ] : 179
0.90 < entropy < 1.00 ] : 0
1.00 < entropy < 1.10 ] : 175

Here's what is being measured.  Each bit sent to the RNG is compared across
multiple launches of the browser.  Here is an example showing 3 data sets:

       Run 0   Run 1  Run 2
Bit 0    1       1      1
Bit 1    0       1      1
Bit 2    0       0      0
...

In this example, Bits 0 and 2 did not contribute any entropy because they were
the same after each launch, i.e. they are predictable.  Bit 1 contributed some
entropy.  The parameter is measured by:

entropy = 1 - (2 * |0.5 - mean|)

For Bits 0 and 2, it is obvious that entropy = 0.  For Bit 1, the entropy is
2/3.  The data set from this example would be:

0.00 < entropy < 0.10 ] : 2
0.10 < entropy < 0.20 ] : 0
0.20 < entropy < 0.30 ] : 0
0.30 < entropy < 0.40 ] : 0
0.40 < entropy < 0.50 ] : 0
0.50 < entropy < 0.60 ] : 0
0.60 < entropy < 0.70 ] : 1
0.70 < entropy < 0.80 ] : 0
0.80 < entropy < 0.90 ] : 0
0.90 < entropy < 1.00 ] : 0
1.00 < entropy < 1.10 ] : 0

Note that the last bin is really only for cases where the entropy = 1.0, but
rounding/floating point gave numbers greater than 1.0 sometimes.  It should
really be "entropy = 1.0 ] : 0".

This only measures one kind of predictability: patterns across multiple
executions.  It doesn't catch patterns within an execution.

I would say that we could claim the number of bits for which this entropy
measurement is > 0.5 "count" as contributing entropy to the RNG.  Nelson, do you
agree?

Comment 12

18 years ago
I forgot to mention - to test the entropy collector Javi wrote that captures
mouse movements and feeds them to the RNG, use the browser for a while before
quitting.  You should see a few bytes in rngoutput every few seconds.

Comment 13

18 years ago
Ugh.  Note also that the first "<" should be "<=".
In answer to Ian's question about which bits "count", I'd compute the 
total entropy this way (using Ian's example data above):

0.00 * 34395 =   0
0.10 * 0     =   0
0.20 * 50    =  10
0.30 * 28    =   8.4
0.40 * 54    =  21.6
0.50 * 0     =   0
0.60 * 157   =  94.2
0.70 * 130   =  91
0.80 * 179   = 143.2
0.90 * 0     =   0
1.00 * 175   = 175
----------     -----
total          543.4

We need an absolute minimum of 160 bits.  Some would say more.
1024 would be very good.

Comment 15

18 years ago
PDT for PSM
Whiteboard: PDT

Comment 16

18 years ago
PDT+ as per Steve Elmeer 6/20/2001
Whiteboard: PDT → PDT+

Updated

18 years ago
Whiteboard: PDT+ → PDT+; (no checkin required)

Comment 17

18 years ago
whiteboard-> needs verification
Whiteboard: PDT+; (no checkin required) → PDT+; (no checkin required) needs verification

Comment 18

18 years ago
Who needs to do the verification?  Javi?   
Summary: Verify entropy collector works → RTM: Verify entropy collector works
(Reporter)

Comment 19

18 years ago
In the ideal case, the verification would be done by someone on the NSS team. 
wtc: is that doable?
What about the buffered entropy collector design?
We had it in PSM 1.x.
It took Mark Welch about a day (or less) to implement.
It decouples the cost of collection from the cost of processing and
reduces the cost of processing (N collections per processing event).

Is that no longer a goal of this bug?

If not, please create a new bug report about that.
The numbers in the table just above add up to 314.3 bits.
That number is more than 160, which is the absolute bare minimum.
And I believe it's sufficiently conservative to be believed. 
So, I approve this entropy change based on these numbers.
Oops, that last comment went into the wrong bug report.  Sorry.

Comment 23

18 years ago
Javi, this is PDT+ bug. Tomorrow, on Tuesday, we'll try to build the first RTM
candidate. It would be good, if this could be resolved ASAP.

Comment 24

18 years ago
I ran Mozilla 0.9.2 on Windows 2000 twenty times.
The output of the 'analyze' program on the rngoutput*
files is:

0.00 < entropy < 0.10 ] : 135697
0.10 < entropy < 0.20 ] : 1
0.20 < entropy < 0.30 ] : 20
0.30 < entropy < 0.40 ] : 18
0.40 < entropy < 0.50 ] : 5
0.50 < entropy < 0.60 ] : 60
0.60 < entropy < 0.70 ] : 128
0.70 < entropy < 0.80 ] : 156
0.80 < entropy < 0.90 ] : 384
0.90 < entropy < 1.00 ] : 0
1.00 < entropy < 1.10 ] : 179

The total entropy is:

0.00 * 135697 =   0
0.10 * 1      =   0.1
0.20 * 20     =   4
0.30 * 18     =   5.4
0.40 * 5      =   2
0.50 * 60     =  30
0.60 * 128    =  76.8
0.70 * 156    = 109.2
0.80 * 384    = 307.2
0.90 * 0      =   0
1.00 * 179    = 179
----------      -----
total           713.7

Comment 25

18 years ago
Created attachment 41094 [details]
A gzipped tar file (win2k.tar.gz) containing 20 rngoutput* files from running mozilla0.9.2 on Windows 2000

Comment 26

18 years ago
I ran Mozilla 0.9.2 on Red Hat Linux 6.2 (with DISPLAY set to
a remote machine) twenty times.  The output of the 'analyze'
program on the rngoutput* files is:

0.00 < entropy < 0.10 ] : 24926
0.10 < entropy < 0.20 ] : 0
0.20 < entropy < 0.30 ] : 15
0.30 < entropy < 0.40 ] : 3
0.40 < entropy < 0.50 ] : 10
0.50 < entropy < 0.60 ] : 16
0.60 < entropy < 0.70 ] : 22
0.70 < entropy < 0.80 ] : 44
0.80 < entropy < 0.90 ] : 118
0.90 < entropy < 1.00 ] : 0
1.00 < entropy < 1.10 ] : 62

The total entropy is:

0.00 * 24926 =   0
0.10 * 0     =   0
0.20 * 15    =   3
0.30 * 3     =   0.9
0.40 * 10    =   4
0.50 * 16    =   8
0.60 * 22    =  13.2
0.70 * 44    =  30.8
0.80 * 118   =  94.4
0.90 * 0     =   0
1.00 * 62    =  62
----------     -----
total          216.3

Comment 27

18 years ago
Created attachment 41096 [details]
A gzipped tar file (linux.tar.gz) containing 20 rngoutput* files from running mozilla0.9.2 on Red Hat Linux 6.2.

Comment 28

18 years ago
wtc suggests that although the entropy is ok for RTM, we should keep this bug
open for 2.1 to allow for review by Nelson Bolyard, and possible improvements.

I agree.

target->2.1
Target Milestone: 2.0 → 2.1

Comment 29

18 years ago
Removing PDT+ - no checkin required
Whiteboard: PDT+; (no checkin required) needs verification → no checkin required) needs verification

Updated

18 years ago
Priority: P1 → P3

Comment 30

18 years ago
Mass assigning QA to ckritzer.
QA Contact: junruh → ckritzer

Comment 31

18 years ago
Move to future. Won't have time to fix these for 2.1
Target Milestone: 2.1 → Future

Updated

18 years ago
QA Contact: ckritzer → junruh
I just made a test with a 1.0 branch build in order to verify we are still
receiving entropy.

As we are meanwhile delaying the load of PSM/NSS until it is actually required,
it was necessary to do at least one crypto operation, in order to reach the
entropy dumping code.

I ran 6 sessions. Here is the output from the analyze tool:

0.00 < entropy < 0.10 ] : 33682
0.10 < entropy < 0.20 ] : 0
0.20 < entropy < 0.30 ] : 0
0.30 < entropy < 0.40 ] : 1638
0.40 < entropy < 0.50 ] : 0
0.50 < entropy < 0.60 ] : 0
0.60 < entropy < 0.70 ] : 4061
0.70 < entropy < 0.80 ] : 0
0.80 < entropy < 0.90 ] : 0
0.90 < entropy < 1.00 ] : 0
1.00 < entropy < 1.10 ] : 2859

This was on Linux.

Updated

17 years ago
Blocks: 157812
Mass reassign Javi's old PSM bugs to nobody
Assignee: javi → nobody
QA Contact: junruh → nobody
Target Milestone: Future → ---

Updated

14 years ago
Component: Security: UI → Security: UI
Product: PSM → Core
Is it still necessary to verify entropy collector works, or can we mark this as fixed?
Whiteboard: no checkin required) needs verification → [kerh-coz] no checkin required) needs verification

Comment 35

13 years ago
This bug can be marked fixed.  You should also
do something about the bug it depends on and blocks.

Verifying entroy collector works is ongoing work.
This bug was created specifically for some Mozilla
(0.9.2?) or Netscape (6.0?) release around June
or July 2001.
Status: NEW → RESOLVED
Last Resolved: 13 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla0.9.2

Comment 36

13 years ago
What exactly fixed this bug?  A checkin to another bug?  I don't see any patches here for this one.

If things "just changed", or are otherwise verified as now working, it should be WORKSFORME.  Only FIXED if some specific, referenced, code was checked in that corrected this.

Updated

11 years ago
Version: psm2.0 → 1.0 Branch
Product: Core → Core Graveyard
You need to log in before you can comment on or make changes to this bug.