Skip to content

Bias in dice based entropy #435

Description

@crwatkins

I believe there is a bias in the diced based entropy entry method (perhaps in some of the other non-base 2 methods also). I believe that the code is using the dice to create a base 6 number and then simply discarding some bits (base 2) to create the entropy to be used for the seed. This results in an uneven distribution in the result. There are various methods to deal with this bias.

NIST addresses a similar problem (NIST is going from modulo 2 entropy to module N while this is going from modulo N to modulo 2) in their Digital Signature Standard (section B.1.1) by requiring an additional 64 random bits to minimize the bias. In our case, that would mean about an extra 25 rolls of the die.

One method to remove the bias would be to simply ignore throws of 4 and 5, and use two bits of entropy from throws 1, 2, 3, and 6. This would provide an average of 1.33 bits per roll.

A slight variation on that method is that instead of discarding 4 and 5, use one bit of entropy from 4 and 5 in addition to the two bits from 1, 2, 3, and 6. That results in an average of 1.66 bits per roll. This is obviously more efficient than the previous method, but I mentioned both because the previous method is easier to think about to start with.

The above method allows deriving discreet entropy from a single die roll. This can also be applied in conjunction with aggregation (creating a larger base 6 number as is done now) for differing efficiencies (the efficiency varies based on the difference between the power of 2 and the power of 6 being used).

One other potentially related issue: There may be some other errors in the entry or display process. Entering the single digit 5 in base 6 mode claims to provide 3 total bits, which is not possible.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions