11 ms·

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

168 points by ggerganov 6y ago

jedimastert 6y ago
All of use with Model Ms and Cherry Blues feeling real weird right now...
ggerganov 6y ago
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.
- cnity 6y ago
  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_factorization https://en.wikipedia.org/wiki/Non-negative_matrix_factorizat... [1] https://www.researchgate.net/publication/220723421_Real-time_Polyphonic_Music_Transcription_with_Non-negative_Matrix_Factorization_and_Beta-divergence https://www.researchgate.net/publication/220723421_Real-time... Edit: Also, this is great work. I don't mean to denigrate it at all.
  - ggerganov 6y ago
    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.
  - waffletower 6y ago
    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.
    - ggerganov 6y ago
      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.
      - cnity 6y ago
        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!
        ggerganov 6y ago
        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.
- raxxorrax 6y ago
  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/ https://unix4lyfe.org/dct-1d/ Otherwise popular libraries like openCV have tools to convert signals, but most are focused on imaging (2d signals).
  - jlokier 6y ago
    > 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.
Raphmedia 6y ago
I just tried it and it works incredibly well. It kind of makes me want to stop using a mechanical keyboard.
seveibar 6y ago
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?
- ggerganov 6y ago
  > 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.
  - seveibar 6y ago
    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 :)
- avh02 6y ago
  I've seen people blur their keyboard on these parts, I figure they'll start bleeping/muting that portion
- SamBam 6y ago
  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.
  - zerd 6y ago
    Well known since at least 2004 https://web.eecs.umich.edu/~genkin/teaching/fall2018/EECS598-12_files/kbdacoustic.pdf https://web.eecs.umich.edu/~genkin/teaching/fall2018/EECS598... https://www.nytimes.com/2004/12/12/magazine/acoustic-keyboard-eavesdropping.html 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 https://dl.acm.org/doi/10.1145/3365366
ffpip 6y ago
This works incredibly well. I hope you realize what you've created (and made available to every person in the world).
- rcoveson 6y ago
  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.
simias 6y ago
Time to bring solenoids back into keyboards to mask the keystrokes: https://youtu.be/sGda5YrqJK8?t=50 https://youtu.be/sGda5YrqJK8?t=50 If your coworkers complain, tell them it's a security feature.
xvector 6y ago
Amazing stuff!
rgovostes 6y ago
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-vibrations-0804 https://news.mit.edu/2014/algorithm-recovers-speech-from-vib...
- ggerganov 6y ago
  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.
- fl0wenol 6y ago
  Yes, this is the fundamental principal of towed-array sonar, or using seismic arrays to pinpoint earthquakes (or locations of nuclear detonations)
- mhh__ 6y ago
  You can also point a laser at a window
redgiraffe 6y ago
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.2078&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.186...
- ggerganov 6y ago
  This looks like a very interesting resource. Thanks for sharing.
jrexilius 6y ago
This is amazing work. Thank you for sharing it!
aarchi 6y ago
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.
lrossi 6y ago
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!
nmstoker 6y ago
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)
- deadmutex 6y ago
  How would you secure this? Also, consider techniques like following: https://news.mit.edu/2014/algorithm-recovers-speech-from-vibrations-0804 https://news.mit.edu/2014/algorithm-recovers-speech-from-vib..., which can leak audio information much farther than audio range.
- core-questions 6y ago
  You've basically reinvented the ultrasonic remote control: https://en.wikipedia.org/wiki/Remote_control#Television_remote_controls 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.
  - nmstoker 6y ago
    Yes, it's basically this applied to a keyboard.

168 points by ggerganov 6y ago

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

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.

cnity 6y ago
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_factorization https://en.wikipedia.org/wiki/Non-negative_matrix_factorizat... [1] https://www.researchgate.net/publication/220723421_Real-time_Polyphonic_Music_Transcription_with_Non-negative_Matrix_Factorization_and_Beta-divergence https://www.researchgate.net/publication/220723421_Real-time... Edit: Also, this is great work. I don't mean to denigrate it at all.
- ggerganov 6y ago
  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.
- waffletower 6y ago
  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.
  - ggerganov 6y ago
    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.
    - cnity 6y ago
      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!
      - ggerganov 6y ago
        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.
raxxorrax 6y ago
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/ https://unix4lyfe.org/dct-1d/ Otherwise popular libraries like openCV have tools to convert signals, but most are focused on imaging (2d signals).
- jlokier 6y ago
  > 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.

Raphmedia 6y ago

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

seveibar 6y ago

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?

ggerganov 6y ago
> 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.
- seveibar 6y ago
  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 :)
avh02 6y ago
I've seen people blur their keyboard on these parts, I figure they'll start bleeping/muting that portion
SamBam 6y ago
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.
- zerd 6y ago
  Well known since at least 2004 https://web.eecs.umich.edu/~genkin/teaching/fall2018/EECS598-12_files/kbdacoustic.pdf https://web.eecs.umich.edu/~genkin/teaching/fall2018/EECS598... https://www.nytimes.com/2004/12/12/magazine/acoustic-keyboard-eavesdropping.html 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 https://dl.acm.org/doi/10.1145/3365366

ffpip 6y ago

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

rcoveson 6y ago
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.

simias 6y ago

Time to bring solenoids back into keyboards to mask the keystrokes: https://youtu.be/sGda5YrqJK8?t=50 https://youtu.be/sGda5YrqJK8?t=50 If your coworkers complain, tell them it's a security feature.

xvector 6y ago

Amazing stuff!

rgovostes 6y ago

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-vibrations-0804 https://news.mit.edu/2014/algorithm-recovers-speech-from-vib...

ggerganov 6y ago
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.
fl0wenol 6y ago
Yes, this is the fundamental principal of towed-array sonar, or using seismic arrays to pinpoint earthquakes (or locations of nuclear detonations)
mhh__ 6y ago
You can also point a laser at a window

redgiraffe 6y ago

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.2078&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.186...

ggerganov 6y ago
This looks like a very interesting resource. Thanks for sharing.

jrexilius 6y ago

This is amazing work. Thank you for sharing it!

aarchi 6y ago

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.

lrossi 6y ago

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!

nmstoker 6y ago

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)

deadmutex 6y ago
How would you secure this? Also, consider techniques like following: https://news.mit.edu/2014/algorithm-recovers-speech-from-vibrations-0804 https://news.mit.edu/2014/algorithm-recovers-speech-from-vib..., which can leak audio information much farther than audio range.
core-questions 6y ago
You've basically reinvented the ultrasonic remote control: https://en.wikipedia.org/wiki/Remote_control#Television_remote_controls 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.
- nmstoker 6y ago
  Yes, it's basically this applied to a keyboard.