How to draw words randomly from a physical dictionary?

Question

Suppose I have a real physical dictionary, and I want to draw words from it randomly, using dices. How should I do it?

Maybe it's easier to work with a coin since it's easier to convert binary to a decimal, but whatever, if I use dice, then I can generate a number in base 6 with some dice throws.

The problem is that the dictionary does not have a index number for each word, so I think that picking a random page number then a random word on that page is not uniformly distributed. If some page has more words than the others, then I guess it's not uniform.

By the way, on a dictionary with 20.000 words is it ok for me to get only 4 truly random words to use as a additional passphrase to my bitcoin seed? I just want it to be really hard to crack for the next 5 years on a AWS machine such that it will not cost more than $100.000 for the entire attack.

I don't want to use the bip selected words because they are not in my main language

Answer 1

How to draw words randomly from a physical dictionary, using dices?

Assuming we know the total number of pages $p$ in the dictionary, and can estimate some $w$ so that no page has more than $w$ words on it, we can use rejection sampling for exact equidistribution:

• find the smallest $k$ with $6^k\ge p$, and the largest $d\in\{1,2,3\}$ with $6^k\ge d\,p$
• find the smallest $\ell$ with $6^\ell\ge w$, and the largest $e\in\{1,2,3\}$ with $6^\ell\ge e\,w$
• for each of the 4 words to choose
  • repeat
    • $i:=0$
    • repeat $k$ times
      • draw a dice value $v$ in $[1,6]$
      • $i:=6i+v-1$
    • $i:=\lfloor i/d\rfloor+1$, which is uniformly random in $[1,6^k/d]$
    • if page $i$ exists in the dictionary and contains at least one word
      • $j:=0$
      • repeat $\ell$ times
        • draw a dice value $v$ in $[1,6]$
        • $j:=6j+v-1$
      • $j:=\lfloor j/e\rfloor+1$, which is uniformly random in $[1,6^\ell/e]$
      • if there are at least $j$ words on page $i$
        • pick the $j^\text{th}$ word of page $i$ and exit the repeat loop

We can get away with $w$ perhaps a little too small, e.g. $w$ at least $2W/p$, where $W$ is the approximate number of words in the dictionary, as long as words past index $w$ in their page (which can't be chosen) are only a small fraction of the words.

---

on a dictionary with 20.000 words is it OK for me to get only 4 truly random words to use as a additional passphrase to my bitcoin seed?

This gives $4\log_2(20000)\approx57$ bit of entropy. That's sufficient, or not, to deter brute force search, depending of the key stretching used to change the 4 words into a key.

It's been cited BIP39, which uses PBKDF2 with $2^{11}$ iterations and HMAC-SHA-512. The cost of searching all the keys would be dominated by $2^{57+11+1}=2^{69}$ SHA-512 hashes, which is uncomfortably few (I don't want to go as far as estimating how that would be best done with AWS, or worse extrapolating that in 5 years). I suggest using Argon2 instead of PBKDF2 HMAC-SHA-512, and bumping the cost parameters to 10 seconds of calculation, and then that's plenty safe enough.