Show HN: Keytap2 – acoustic keyboard eavesdropping based on n-gram frequencies | Hacker News Reader

Show HN: Keytap2 – acoustic keyboard eavesdropping based on n-gram frequencies

github.com

168 pointsggerganov39 comments

Hello HN, I've been working for some time on an algorithm for recovering unknown text just by analyzing the recorded audio of a person tapping on their keyboard (i.e. acoustic eavesdropping).

In this post, I present my new approach which I think is quite interesting - it matches detected keystrokes with each other based on their sound similarity and converts the problem of recovering the unknown text into a problem of breaking a substitution cipher! The great advantage of this method is that it does not require prior training - it exploits the n-gram frequencies in the English language.

Would love to hear your thoughts and suggestions about this.

Hey. I've been working on an audio recognition tool that is remarkably similar to this one, and there are a few areas I strongly recommend exploring if you want to improve the classification performance.

For waveform similarity, you may achieve better results by comparing the spectrogram (computed by taking the FFT of each "clack") instead of comparing the time domain signal.

Next, the best performing sound classification algorithms (at least in music note classification, which is a very similar problem to yours) utilise non-negative matrix factorisation[0] to do the comparison against a bank of note templates.

I recommend reading "Real-time Polyphonic Music Transcription with Non-negative Matrix Factorization and Beta-divergence" (Dessein et. al.) for a more comprehensive description of the algorithm[1].

I actually tried applying my algorithm to detect taps on different parts of my laptop for fun, so that I could send keyboard events when e.g. I tap the bottom right corner of my laptop, and it was quite effective. The approach is incredibly accurate for classification of short spectrograms.

Feel free to reach out to me if you want to discuss a bit more.

[0] https://en.wikipedia.org/wiki/Non-negative_matrix_factorizat...

[1] https://www.researchgate.net/publication/220723421_Real-time...

Edit: Also, this is great work. I don't mean to denigrate it at all.

Thank you for these suggestions! The idea for comparing sounds in the frequency domain was something that I was considering, but couldn't figure out a proper way to do it.

I will definitely check the resources that you provided and see if I can utilize this approach in Keytap.

I don't recommend using DFT (FFT) analysis unless you can constrain N to small sizes (<= 256 at 44.1KHz sampling rate perhaps) to reduce time aliasing. Use of wavelets may be a better fit for this application.

I have found that I need to use about 75-100 ms of audio around the keystroke-down peak when comparing waveforms. At the sample rate that I am using - 16kHz, I would probably need samples of size about 1024 - 2048. Not sure if this is feasible, just giving some additional info.

If you want to compute an FFT with fewer bins you can also use STFT and configure the bin count and hop size (essentially computing many FFTs of smaller regions of the signal and computing the average).

A quick side note, 16kHz is quite a low sample rate for your use case, since you won't be able to capture frequencies over 8kHz (the Nyquist frequency), and key clicks at least intuitively I'd imagine to contain a lot of detail at higher frequencies. I have no data to back this up though!

Regarding the sampling rate:

I switched down to 16kHz from 48kHz, because I found that with my approach there wasn't much of a difference in the key-matching performance. At the same time, I gained computational performance.

At some point, I was looking at the spectrum of the key sounds and I think that almost the entire signal is in the lower few kHz. It might be just my keyboard - not sure.

I still have the tool, so I can easily check if there is some high-frequency portion that I am missing.

I believe you, it was only a hunch. Not backed up by evidence! I've been way off about my intuition of frequencies, especially with non-harmonic sounds like key presses :)

I agree, 44.1KHz is a commonly available sampling rate and could provide better temporal resolution regardless of time doamin and frequency domain analysis technique you decide to use.

I don't quite understand what you mean. Do you mean that in general you don't recommend DFT for signal processing? This seems counter to most approaches in the field. Issues (aliasing, spectral leakage, etc) arising from DFT more or less iron out with reasonable use of zero padding, sample rate, and windowing.

Edit: I didn't mean for this to sound so closed minded. I don't know that much about more recent audio processing practices and I think you probably know things I don't. If you have any reading about wavelets vs DFT I'd be very thankful and interested.

The uncertainty principle is is the key concept that I think is relevant here: https://en.wikipedia.org/wiki/Uncertainty_principle#Harmonic...

A Discrete Fourier Transform (DFT/FFT) balances frequency vs time resolution based upon its parameterization. In this application, I think that frequency differentiation is less important than time differentiation for events. To get an advantage from utilizing spectral analysis, I think that the STFT can be used with very small overlapping analysis windows. (https://en.wikipedia.org/wiki/Short-time_Fourier_transform) However, due to the importance of transients I would consider use of wavelet transforms instead (https://en.wikipedia.org/wiki/Wavelet_transform) since they can resolve temporal characteristics better than a DFT.

I've been working on something similar to both but also distinct.

Very interesting problem. Naively I would have thought every keystroke sounds the same aside from special keys like space or enter. Apparently this is not the case.

Like the other comment suggested, a frequency analysis might help.

Here is a good explanation you could quickly use in C++:

https://unix4lyfe.org/dct-1d/

Otherwise popular libraries like openCV have tools to convert signals, but most are focused on imaging (2d signals).

> Naively I would have thought every keystroke sounds the same

Even if the keystroke sounds were identical at source, the acoustic environment between the key and mics (key position, shape of the surrounding keyboard area, position of hands, screen etc.) adds its own unique reverb signature too.

Speaking of mics - a lot of laptops have stereo mics. That's enough to start locating the acoustic source spatially by phase, in addition to the other characteristics.

Awesome work. I always wondered if this is possible, perhaps using two or three carefully placed microphones that could identify the source location of a given sound.

See also: recovering speech by filming the vibrations of a plastic bag on the other side of soundproof glass.

https://news.mit.edu/2014/algorithm-recovers-speech-from-vib...

Using more mics can potentially not only help with identifying the source location but also reduce the background noise by merging the signals.

I got a ReSpeaker Mic Array which has 4 mics and have been planning to do some experiments with it.

Yes, this is the fundamental principal of towed-array sonar, or using seismic arrays to pinpoint earthquakes (or locations of nuclear detonations)

You can also point a laser at a window

Not sure if I mentioned this last time this topic came up, but I wondered about the idea of making a keyboard that had keys that deliberately sounded detectably different. Then you could make it wireless and battery free simply by using the computers mic and perhaps a simplified version of these methods, as the challenge would be reduced by the more distinct key sounds. It wouldn't really need much of the key signal electronics either. More a thought experiment than a practical device I suspect!

Presumably the trick would be finding a non-annoying way for the sounds to differ (perhaps if it was beyond human hearing). Of course it would be totally insecure, so not safe for Twitch videos without redacting the audio (but a tool could know what to remove that detail too)

How would you secure this? Also, consider techniques like following: https://news.mit.edu/2014/algorithm-recovers-speech-from-vib..., which can leak audio information much farther than audio range.

You've basically reinvented the ultrasonic remote control:

https://en.wikipedia.org/wiki/Remote_control#Television_remo...

My grandma's TV had one of these - you'd press a button and it would basically mechanically impact a tuning fork to make the needed frequency.

Yes, it's basically this applied to a keyboard.

You may find this interesting - the technique has been used before to do unsupervised recovery of keystrokes:

"Cracking Passwords using Keyboard Acoustics and Language Modeling"

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.186...

This looks like a very interesting resource. Thanks for sharing.

This is a bit scary for coding livestreamers who may have to answer the call from sudo now and again. I'm curious how the maintainer feels about the usage of this application. What drove you to continue the development of the software? What kind of people are part of the community in a broad sense?

> What drove you to continue the development of the software?

The same things that drive security researchers to explore different security exploits. I don't condone anyone using this for malicious purposes.

It's important work, thanks! Don't let people like me being afraid of a bad actors stop the process of publicizing exploits if it leads to a safer future :)

I've seen people blur their keyboard on these parts, I figure they'll start bleeping/muting that portion

I believe the technology has existed for quite some time. I think perhaps the idea was even mentioned in Cryptonomicon. So I think that making it more available/open should hopefully make people more aware that it's a danger.

That said, it significantly lowers the barrier for entry, much like script kiddie hacking.

Well known since at least 2004 https://web.eecs.umich.edu/~genkin/teaching/fall2018/EECS598... https://www.nytimes.com/2004/12/12/magazine/acoustic-keyboar...

More recent one that works well over VoIP: https://dl.acm.org/doi/10.1145/3365366

This attack and Van Eck phreaking are why Edward Snowden, while typing passwords and other sensitive information, would pull a blanket over himself and his laptop.

This works incredibly well.

I hope you realize what you've created (and made available to every person in the world).

I'm reasonably confident that this capability was already available to some people in the world. Expanding that "some" to "all" is a great service. It's impossible to develop armor against a category of weapon of which you have no examples.

All of use with Model Ms and Cherry Blues feeling real weird right now...

I remember an episode from a TV show with a Canadian cop doing this manually based on a recording. This memory from my childhood stuck with me, since I have seen an interview with the actor saying that was one of the most ridiculous scripts they played—he was saying something like this is impossible. I guess he was wrong!

I just tried it and it works incredibly well. It kind of makes me want to stop using a mechanical keyboard.

Time to bring solenoids back into keyboards to mask the keystrokes: https://youtu.be/sGda5YrqJK8?t=50

If your coworkers complain, tell them it's a security feature.

This is amazing work. Thank you for sharing it!

Amazing stuff!

Reply on news.ycombinator.com