Oliver Chambers puts forward a puzzle that lies at the intersection of statistics and espionage.
Proposition: given only the audio of a person typing on their computer can you determine what they are writing?
Surprisingly the answer to this question is yes, and with some rather remarkable accuracy. Below is the abstract from the article Keyboard Acoustic Emanations Revisited which explains what can be recovered from only the sound of keystrokes
We present a novel attack taking as input a 10-minute sound recording of a user typing English text using a keyboard, and then recovering up to 96% of typed characters. There is no need for a labelled training recording. Moreover, the recognizer bootstrapped this way can even recognize random text such as passwords: In our experiments, 90% of 5-character random passwords using only letters can be generated in fewer than 20 attempts by an adversary; 80% of 10- character passwords can be generated in fewer than 75 attempts…
Perhaps the most surprising feature of this discovery is that the sound of individual keys being pressed are each distinct enough that they may be clustered into a sufficient number of groups that English words could be recovered. The authors of the article found that if the sound wave from each key press is decomposed into a vector of energy levels (Fourier coefficients) via a generalisation of a Fourier Transform call Mel-Frequency Cepstrum, then these vectors can be reliably clustered into similar groups using known statistical techniques. This is illustrated in the graph below:
The clustering algorithm places the different key strokes into $K$ different classes. They use slightly more classes than there are keys on the keyboard – so the $K$ classes do not represent a one-to-one mapping from sound to key pressed, but rather $K$ random variables each with a different distribution of which key was pressed. The benefit of this approach is that it allows them to consider the correlation between the classes. For instance, if one class could be the letter t or y with equal probability, and another class could be g or h, then whenever the first class precedes the other in text the combination “th” should be a much more likely outcome.
As of yet, the algorithm cannot handle special key combinations (e.g. shift key) or backspaces, which means we are probably safe from audio snooping for the immediate future. Nonetheless, it does hint at some scary possibilities in the future.
Further reading for those interested:
Now for something completely unrelated: this month’s puzzle…
You have a $$N$$ stones in a bag and you wish to calculate the weight of the heaviest stone. You do this by randomly pulling the stones from the bag one at a time (without replacement) and weighing it. Each time the weight of the stone is the heaviest so far you record its weight. Assuming that the weights of each stone is identically distributed, what is the expected number of times that you will record the weight of a stone?
For your chance to win $50, send your solutions to ActuariesMag@actuaries.asn.au
The Critical Volume 18 – Solution and Winner
Here is the link to the Volume 18 puzzle.
The prize goes to the first correct submission, Preetham Arvind.
And the solution is:
NEED A DRIVER REVIVER? FREE COFFEE ON SIDE ROAD IN FORTY KMS. YOU HAVE EARNED IT! KEEP YOUR EYE’S ON THE ROAD
Thanks to everyone who submitted solutions and apologies to everyone who pointed out that EYE’S should indeed be EYES.
CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.