diceware/cointoss initialization

[prusnak]

T2 has display so we can show head/tails or 1-2-3-4-5-6 user interface for cointoss/diceware initialization to generate user entropy.

[Hannsek]

User would have to "throw the dice" many (like 100) times to make it some impact, no?

[prusnak]

"throw the dice" man (like 100) times

One throw of 6-sided dice is log(6)/log(2) = ~2.585 bits of entropy. So for 128 bits you'd need 50 throws, for 256 bits you'd need 100 throws.

One coin toss is 1 bit of entropy. For 128 bits you'd need to toss 128 times, for 256 bits 256 times.

[Hannsek]

Exactly. So, do you think this is something we want to have on the device?

[matejcik]

for the record, the usual way of resolving this is putting 5 (i think?) dice in a box and rolling them all at the same time, for one diceroll per one recovery word

[prusnak]

Exactly. So, do you think this is something we want to have on the device?

You can do 50 dice throws under 3 minutes (assuming 3 seconds per throw), 100 throws under 6 minutes.
Even if you do a mistake (and enter 3 instead of 6 on a device) this does not matter too much - it just adds extra entropy to the mix :-)

I agree this is so much harder to do on a device with no touchscreen since the input is not so straightforward as just showing 6 buttons on a touchscreen.

[mcudev]

I'm interested in helping on this one. I was contemplating making this myself when I found this issue. Here's what I was thinking.

Briefly, I'd want to give the user a workflow that will guide them through:

1. generating unique, unpredictable, unbiased, untamperable entropy, uniformly at random
2. capturing that entropy into their trusted Trezor device
3. verifying that the input entropy accurately maps to the generated BIP39 mnemonic sentence

The T1 and T2 can both easily support a coin toss heads-tails input. The T2 can support a D6 die 1-6 input.

Entropy is a measure of unpredictability. A perfectly biased coin/die is totally predictable, and provides 0 entropy. Thus:
A) 1 toss of a coin, having unknown bias, can provide from 0 to 1 bit of entropy.
B) 1 roll of a D6, having unknown bias, can generate between 0 and log2(6) = ~2.585 bits of entropy.
C) Tossing/rolling a set of coins/dice having unknown bias does not mitigate vulnerability to bias. Not knowing the bias is not the same as there not being bias.

For our purposes, bias is bad. We want to eliminate bias in the generated entropy. The problem is that the bias of users' coins/dice is not known and can not be appraised.
To remove bias from coin and die trials, I prefer a simple, repeatable and verifiable von Neumann process, see references below [1][2][3][4].
The single inequality process in [3] can be applied to both coin and die use.
This particular process is not the most efficient as it may not capture all possible generated entropy. But, I choose to trade that efficiency for predictability, simplicity of understanding, and ease of user verification of the generated mnemonic sentence.

A proposed workflow:

1. User chooses how many words shall be in the generated BIP39 mnemonic sentence: 12, 15, 18, 21, 24 (or, for simplicity, only 12, 15, 24)
   12, 15, and 24 are sensibile options:
   12 words is the smallest mnemonic (128 bits of entropy) that matches the approximate security level (in bits) of the secp256k1 curve
   15 words is the second smallest mnemonic (160 bits of entropy) that has extra security margin over 128 bits in-case somehow the entropy generation was flawed in some minor aspect
   24 words is the maximum strength mnemonic (256 bits of entropy), and may be overkill for some use cases

2. User chooses whether the generated mnemonic sentence is to be stored to flash memory, or wiped and forgotten from memory after the generation and verification process is complete

3. User chooses coin or die input method for entropy generation (the user will input toss/roll trials and the device will determine the outcome of each pair of trials via the von Neumann process)

4. Now we need to input 11 bits per word up to the number of desired words (the last word is a special case due to it containing the checksum).
   a) Provide an input mechanism that is appropriate for coin toss or die roll, as selected previously
   a) As the user enters the coin/die trial result, show the binary result (or indicate no result -- which is common in the von Neumann process)
   b) Every time a valid bit is generated, show the current set of 11 bits for user verification and progress feedback e.g.- 011________
   c) After the 11th bit of each word is input, display the generated word. The user can keep track of the word and verify that it was selected according to the input entropy by looking the word up in a BIP39 wordlist such as [5] (we could show the binary and hex to match the wordlist).
   This supports the request made in [9] for verifiability of the mnemonic sentence against the input entropy.
   d) The entropy input process will cease at the correct point in the final word and then the checksum will be generated to finish out the bits of the final word.

5. After the desired number of words have been generated, the user can scroll back through the words for re-verification.

A note on design choice and efficiency: I see that a competitor product uses SHA-256 for randomness extraction from D6 rolls. I assume that decision was made in order to more efficiently extract closer to ~2.585 bits per roll.
That process does not account for dice bias (which likely increases when using low quality dice). Also, by using SHA-256 to extract randomness, I believe that they're reducing the strength of the extracted entropy by some unkown amount. That is, I believe that process is not reliably getting "full entropy" in the output [6][7][8]. To reliably achieve full entropy out of SHA-256, that process would have to input twice the output block size, which would mean 512 bits of entropy.

References
[1] https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin
[2] https://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor
[3] https://gist.github.com/atoponce/c594f6463cdf067ea8cabd899939c24f#file-inequality-2-md
[4] https://crypto.stackexchange.com/a/52682
[5] https://github.com/Coldcard/wordlist-paper/blob/master/wordlist.pdf
[6] https://crypto.stackexchange.com/a/75706
[7] https://crypto.stackexchange.com/a/58168
[8] Section 6.4.2.2 https://csrc.nist.gov/csrc/media/publications/sp/800-90b/draft/documents/draft-sp800-90b.pdf
[9] #1293 (comment)

EDIT:
The above von Neumann process gives us a fair coin/die from a likely imperfect coin/die. That is, the coin/die itself yields a result with unbiased, equal probability. However, the process of how the coin/die is tossed/rolled still should be as unpredictable as possible in order to generate unpredictable trial observations, and thus good result "entropy". That is, we should not encourage devices that, for example, replicate closely the energy imparted and launch angle of the coin/die.

Also, the math that gives us equal probability from the 2-trial pairs of tosses/rolls:
P(heads) = H
P(tails) = 1 - H = T
Total probability from 2 trials = HH + TH + HT + TT

We don't know what the probabilities of H and T actually are (that is, we don't know how fair/unfair the coin/die actually is).
We do know that TH and HT are equal (commutative property of multiplication) and that HH and TT are likely unequal (unless the coin/die is already perfectly fair). Thus, we discard in the 2 cases having likely unequal probability (HH and TT).

To generalize this across both coin and die for the process shown in [3]:
HH and TT cases become E (for equal to) (discard)
HT becomes L (for less than) (return 0)
TH becomes G (for greater than) (return 1)

Thus, the GUI on the T2 device could simply display an input keyboard like 1/H, 2/T, 3, 4, 5, 6 if it is desirable to remove the step of letting the user choose which type of input to use. A shared input keyboard would also allow a user to generate using a coin and a die in different 2-trial pairs which could be good for final result unpredictability. The key to removing bias though is to only use a single source of randomness per 2-trial pair.

[mcudev]

I'm thinking something like the flow below.
The UI is open for design.

For trial input, the GUI may use a 1-6 number pad where one button has an H and another has a T (for heads and tails).
The coin and die process can use the same input mechanism because bit generation is based on inequality in both cases. Perhaps if H/T is selected for trial A, then only the buttons for H/T are active for trial B of a pair.
As long as a single coin or die is used for a single A/B trial pair, users could even safely use different dice/coins for different trials.
If that is too confusing, add another parameter to the process initiating message that specifies coin/die input and use a 1-6 number pad for die, and a pair of H/T buttons for coin.

How bits and words are "indicated" during the process are to be determined. The goal is to allow the user to keep track as the process progresses, for verification purposes, to assure them that the input is exactly what is being used to generate the words. As they go, they want to know whether a 0, 1, or nothing was generated. Then they want to see the 11 bits + the word that the bits map to for wordlist verification. It's a high work, high verification, high assurance process. If space for 11 bits and the number pad can fit on a single screen, that would be great. As they progress, bits could fill in and the number pad could be temporarily replaced by a word when one is completed.

[mcudev]

Also, I just remembered that it's likely more desirable to have this process reachable from the UI without having to attach it to a host. In that case, then substitute a button somewhere in the UI for the DiceCoinGenerate message. Then add a screen at the beginning to let the user input the desired word count. The user could decide whether to persist the words in the screen that shows all the generated words near the end.

[mcudev]

I haven't used the following process in practice yet, but it seems like it would make the coin based process much more user friendly. With tossing just one coin, the whole process is not time efficient (can easily take 100+ minutes). Because of that, it's prone to being interrupted, causing work to be lost. Here's one way to speed a coin based process up:

get N pennies (a roll of 50 is $0.50)
use a sharpie marker to sequentially number each penny on both sides 1 to N

until you have the desired number of bits of entropy
  mix and dump all coins together (todo: what is a great way to mix a bunch of pennies all at once? shake in a box? tumbler? plastic bag?)
  separate coins into two groups: heads group and tails group
  separately mix and dump the two groups of coins (keep the 2 groups separated)
  for i in range(1, N + 1)
    find coin i
    if found in the heads group and tails is showing, store a 0 bit
    elif found in the tails group and heads is showing, store a 1 bit
    else skip coin
  end for
end until

Dice may be a better choice with respect to ease of mixing and dumping. Even/odd would equate to heads/tails in the previous process. However, dice would not be as cheap, and would be more painful to label so that you know which die is which when you go to sequentially read them after the 2nd trial. If they are not labeled, I don't know of a great, unbiased way to process them. The predetermined sequential ordering makes that part of the process obviously fair.

[mcudev]

Also, here's a quick little script that one can run in a tails equivalent environment to try out a coin based process. You'll need to populate the wordlist in the script from the bip39 english wordlist since I removed most of it for brevity below.

#!/usr/bin/env python3
# usage:
#   python3 coin_generate.py

wordlist = [
'abandon',
'ability',
...
'zero',
'zone',
'zoo'
]

import sys
import hashlib

def main(args):
  # see https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
  valid_inputs = ['128', '160', '192', '224', '256']
  strength = int(user_prompt('How many bits of entropy to generate? ({}): '.format(', '.join(valid_inputs)), valid_inputs), 10)
  generate_bip39_mnemonic(strength)
  return 0

def generate_bip39_mnemonic(strength):
  entropy = []
  words = []
  temp = []
  while len(entropy) < strength:
    entropy.append(generate_bit())
    temp.append(str(entropy[-1]))
    print('bit: {}'.format(temp[-1]))
    print('word bits: {}'.format(''.join(temp)))
    if len(temp) == 11:
      temp.clear()
      words.append(wordlist[bits_to_bin(entropy[-11:])])
      print('word {}: {}'.format(len(words), words[-1]))
  print('entropy {}: {}'.format(len(entropy), ''.join(map(str, entropy))))
  checksum_byte = hashlib.sha256(bits_to_bytes(entropy)).digest()[0]
  checksum_bits = [(checksum_byte >> (7 - i)) & 1 for i in range(11 - strength % 11)]
  print('checksum: {}'.format(''.join(map(str, checksum_bits))))
  entropy += checksum_bits
  print('word bits: {}'.format(''.join(map(str, entropy[-11:]))))
  words.append(wordlist[bits_to_bin(entropy[-11:])])
  print('word {}: {}'.format(len(words), words[-1]))
  print('final mnemonic sentence: {}'.format(' '.join(words)))

def bits_to_bin(bits):
  result = 0
  for b in bits:
    result = (result << 1) | b
  return result

def bits_to_bytes(bits):
  return bytearray([ bits_to_bin(bits[i : i + 8]) for i in range(0, len(bits), 8) ])

def generate_bit():
  valid_inputs = ['h', 't']
  while True:
    a = user_prompt('1st toss (h or t): ', valid_inputs)
    b = user_prompt('2nd toss (h or t): ', valid_inputs)
    if a == b:
      print('no bit')
    elif a < b:
      return 0
    elif a > b:
      return 1

def user_prompt(prompt, valid_inputs):
  while True:
    result = input(prompt)
    if result in valid_inputs:
      return result

if __name__ == "__main__":
  sys.exit(main(sys.argv))