Fun with Words: How Many YubiKey Presses Would It Take to Write Shakespeare?
For those unfamiliar, YubiKeys are OTP generators plugged into USB ports that, when pressed, output a fixed-size string. I have one for work with a hair trigger. Looking at it wrong will output a random string followed by a newline. Here’s the culprit in question:
Why do I mention the newline? Because in most text input interfaces that newline will send a message/execute an action. I’ve sent enough gibberish messages and meeting invites to wonder, “What are the chances a YubiKey press outputs a word?” More importantly, does it take more monkeys with typewriters or YubiKey presses to write Shakespeare?
Method (i.e., How to Take a Silly Question Seriously)
There are 3 questions I want to answer:
- How likely is it to get an English word?
- Likelihood of a given word
- Likelihood of generating any word
- What is the likelihood of \(w\) words being generated in a given press?
- The titular question: can we Shakespeare?
Each question above requires a slightly different approach. That said, there is significant overlap. We first need a way to estimate the probabilities of the characters a YubiKey will generate, then a vocab of words/phrases we want to measure the likelihood of, and finally a statistical method to calculate the likelihood of a given event or word. The code used in this post can be found on GitHub.
Estimation of Character Probabilities
First, let’s discuss the finer points of YubiKey text generation. A YubiKey press produces only a subset of the Latin alphabet:
c, b, d, e, f, g, h, i, j, k, l, n, r, t, u, v.
Each press contains 32 randomly generated characters from this subset, terminated by a newline. Note that we ignore that newline for the analysis.
To estimate the probabilities of a word, we can represent the generation process using its start probabilities for the character set and transition probabilities between those characters. The initial distribution and transitions are estimated from 200 sampled presses. This gives us 200 start probs and 6200 transition probabilities. Visually, the transition probabilities look like this:
The more eagle-eyed amongst you will notice the distribution is not uniform. I just mashed the YubiKey non-stop for a while, so some external factors (e.g., non-stop mashing at one time of day) or the limited sample size might be skewing the results. With enough presses, my guess is the probabilities will converge towards a truly uniform distribution. I make this assumption because a predictable distribution seems like a potential security issue (lol maybe not, idk not a security guy). For now, I just used sample probabilities, but the code can be run with uniform probabilities as well.
Building the Vocab
This subset of characters limits what words we can generate. Any word list or passage needs to be filtered accordingly. I used a filtered vocab derived from wordfreq, only keeping entries that use the YubiKey’s 16 letters, are longer than 3 letters, have a Zipf score above 2.5, and contain 32 or fewer letters. Those criteria leave only 2,146 words. This vocab is used to answer questions 1 and 2. Shakespeare will require a different method, further described in that section.
Words containing words will count as multiple finds instead of just one. Words that contain others tend to be longer, and given how rare longer words are, I felt like this approach was sensible.
Methods for Estimating Probabilities
For tasks 1.* and 3, we can just directly measure the probability of a given sequence of chars (i.e., a word or phrase) being generated.
- Monte Carlo method: use the probability of generating a specific char, simulate a large number of runs, and then measure the number of occurrences of a word or phrase.
- Calculate p(w): see formula below
The probability of generating a word \(w\) is given by:
\[p(w) = \sum_{j=1}^{32 - m + 1} q_j(w)\]where \(q_j(w)\) is given by
\[q_j(w)=\pi_j(w_1)\prod_{i=1}^{m-1}T_{w_i,w_{i+1}}, \qquad \pi_j=\pi_1 T^{j-1},\]\(\pi_j\) is the distribution of the character at position \(j\) (essentially the starting probability), and \(T_{a,b}\) is the transition probability of generating character \(b\) given \(a\) (aka transition probability). A word of length \(m\) has \(32-m+1\) possible starting positions, which dictates the terms of the summation. Adding the probabilities for those positions gives the expected number of occurrences.
Task 2 is different. There are 2 approaches that come to mind:
- Poisson (i.e., Fish) Distribution
- Monte Carlo method (we can reuse the same simulation as above)
Caveats
I think explicitly stating limits of this work is important, but it breaks up the flow of the text too much IMO. It's minimized; feel free to expand it now or come back to it later.
The start and transition probabilities are estimated from just 200 real presses, so take
the estimated probabilities with a grain of salt. It’s unclear if this is the “real” distribution.
I didn’t optimize the simulation code, so I could only really run 200 million simulations. To simulate rare events, tens of billions (or more) trials would have been required. At the current scale, the Monte Carlo analysis mostly served as a sanity check for the other methods.
There is a technique for question 2 that I think is more comprehensive/accurate, but I’m still not quite sure how to best implement it. Rather than use a statistical approximation or simulation, we could generate all possible multiword phrases (or a templated version), group these templates based on the number of words contained, and then calculate the likelihood (summing the likelihood of each individual output). I think it’s easier to exhaustively list words rather than all possible combinations (i.e., Monte Carlo).
Statistical methods make assumptions that need to be respected; otherwise, their results can be misleading. The methods used all have these. Rather than detail them, I’ll point out the biggest one that is likely to be violated: our definition of a word.
1,246 of the 2,146 vocab words (58.06%) “contain” another word. Looking at the image below, we see this overlap tends to occur for longer words.
For a Poisson distribution, the fact that a word can contain others will be an issue. This is definitely a weakness, but looking at the distribution of word overlap coupled with the likelihood of generating overlapping words, Poisson might be a cheap way of approximating the probability of N words for smaller N. It is more accurate for shorter (more frequent) words and gives a lower bound to longer words. If you have a different vocab, you will need to check the distribution of words to understand if Poisson is appropriate.
Probability of Generating Words
The following subsections will use a combination of \(p(w)\), Monte Carlo, and Poisson to answer questions 1.* and 2.
Probability of a Given Word
Below are the probabilities of some sampled words, both approximated and simulated. Mean presses are given by \(1/p\), using unrounded probabilities.
| Word | \(p(w)\) % | \(p(w)\) Mean # of Presses | Monte Carlo % | Monte Carlo Mean # of Presses |
|---|---|---|---|---|
glib |
0.099034% | 1,010 | 0.0991995% | 1,008 |
beer |
0.080563% | 1,241 | 0.0801205% | 1,248 |
give |
0.021582% | 4,633 | 0.021632% | 4,623 |
giver |
0.00164601% | 60,753 | 0.001677% | 59,630 |
never |
0.00321534% | 31,101 | 0.003258% | 30,694 |
little |
0.0001105% | 904,777 | 0.000119% | 840,336 |
believe |
\(7.60\times10^{-6}\)% | 13,156,794 | \(8.50\times10^{-6}\)% | 11,764,706 |
intelligence |
\(1.09\times10^{-11}\)% | \(9.19\times10^{12}\) | 0% | — |
unintelligible |
\(4.77\times10^{-14}\)% | \(2.10\times10^{15}\) | 0% | — |
glib was the most frequently observed word in the simulation and according to \(p(w)\) as well.
The longest word is unintelligible, but it doesn’t appear in the simulation.
This is a consequence of a core limitation of simulating with such rare events.
It is worth noting that this simulation only found 1,720 of 2,146 words.
Probability of Any Word
~26.44 million presses of the 200 million simulated had at least one word; in other words, it would take an average of 7.56 presses to get a word. This aligns with the sum of \(p(w)\) over all \(w\), which estimates 7.56 presses would be required to generate a string containing a word. Poisson gives a slightly different answer, but this discrepancy could be accounted for by the violations of the model’s independence assumption. More on that below.
Probability of Generating W Words
Finding one word is fun, but how many words can a single press give us? The quick and dirty way is to use a Poisson distribution. Given that we have already calculated the likelihood of getting a single word, we can use that as our \(\lambda\). Our distribution is given by: \(P(W=w) \approx \frac{e^{-\lambda}\lambda^w}{w!}, \qquad \lambda=0.146320255.\)
| Words in one press | Monte Carlo mean presses | Monte Carlo probability | Poisson mean presses | Poisson probability |
|---|---|---|---|---|
| 0 | 1.15 | 86.779389% | 1.16 | 86.388100% |
| 1 | 8.37 | 11.940552% | 7.91 | 12.640329% |
| 2 | 86.19 | 1.160218% | 108.14 | 0.924768% |
| 3 | 915.08 | 0.109280% | 2,217.09 | 0.0451041% |
| 4 | 10,332.71 | 0.009678% | 60,609.34 | 0.00164991% |
| 5 | 122,850.12 | 0.000814% | 2,071,119.12 | 0.0000482831% |
| 6 | 1,481,481.48 | 0.0000675% | 84,928,192.21 | 0.00000117747% |
| 7 | 66,666,666.67 | 0.0000015% | 4,062,987,352.43 | 0.0000000246124% |
The same Monte Carlo simulation was reused, but in this case the number of words that occurred was recorded. Poisson is relatively close to the simulation or \(p(w)\) estimate when it comes to single-word presses. So for a quick and dirty estimate, it may be reliable enough. The higher end, due to word overlap, is where Poisson struggles. This error grows larger as the number of words in a press grows (see caveats), growing from less than 0.5% to several orders of magnitude for 7 words. The visual below should help make the change in error rate clearer.
OK, but can a YubiKey write Shakespeare?
A complete Shakespearean work is impossible given the YubiKey’s limited alphabet. Instead, we’ll pull sections of his works and measure our ability to generate those. Project Gutenberg’s Shakespeare collection is used as a starting corpus. For context, it is a collection of his entire works (according to Project Gutenberg) and is line-separated with a large amount of metadata such as page numbers, scene instructions, or character information built in (really noising up the dialogue). Lines are sentences or parts of them, so a line is a natural unit to use for this type of analysis (naively at least).
A script is used to extract only the dialogue and poems and format that into a new file. Each line is then lowercased, and all punctuation is removed. For example, I'll becomes ill.
This approach left 169 lines, with only 45 unique multiword spans. Instead, I decided to take a different tack by filtering the entire corpus for producible spans.
A word containing an unavailable letter ends the span. This leaves 7,442 unique spans with multiple words, significantly more than the other approach.
The longest run is 28 letters, so no need to chunk runs.
Below is a sample of these extracted spans and the probability of generating them in a single press.
| Phrase | Letters | Chance per press | Average presses until a match |
|---|---|---|---|
i did |
4 | 0.053758849% | 1,860 |
if it be |
6 | 0.00018530148% | 539,661 |
never believe it |
14 | \(2.889\times10^{-14}\)% | \(3.462\times10^{15}\) |
ill give thee friend |
17 | \(2.409\times10^{-18}\)% | \(4.150\times10^{19}\) |
never never never never never |
25 | \(1.464\times10^{-27}\)% | \(6.829\times10^{28}\) |
then kill kill kill kill kill kill |
28 | \(7.812\times10^{-34}\)% | \(1.280\times10^{35}\) |
The likelihood of generating Shakespeare is slightly less grim if we consider all phrases in aggregate.
| Target | Different target strings | Chance per press | Average presses until any match |
|---|---|---|---|
| Any producible multiword complete line | 45 | 0.062066341% | 1,611 |
| Any extracted multiword run of at least 12 letters | 1418 | \(4.133\times10^{-9}\)% | 24,197,124,290 |
| The longest producible run, at 28 letters | 1 | \(7.812\times10^{-34}\)% | \(1.280\times10^{35}\) |
Can a YubiKey write a Shakespearean phrase? Sure. Will it take a while? Even in the best case, yes. If you want a really threatening King Lear-esque message, it will likely take longer than Earth has existed. Assuming a YubiKey press takes about a second, you’re looking at 4.05616187 × 10^27 years. Given my experience generating a 200 press sample, this feels conservative. Would monkeys with typewriters be faster? Probably.