brainwagon

While my blog has been dominated by radio related stuff lately, I do continue to be interested in lots of different subjects, including various topics related to computer security and codes. While scanning my feeds today, I found reference to this work, which I hadn’t seen before, but which I find interesting both for its security implications and its use of machine learning. Very cool.

Keyboard Acoustic Emanations Revisited

We examine the problem of keyboard acoustic emanations. 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 labeled 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. Our attack uses the statistical constraints of the underlying content, English language, to reconstruct text from sound recordings without any labeled training data. The attack uses a combination of standard machine learning and speech recognition techniques, including cepstrum features, Hidden Markov Models, linear classification, and feedback-based incremental learning.

You might have noticed if you are a long time reader of this blog that I’m fascinated by codes and ciphers, particularly the kind that were developed before computers really came on the scene.   That’s why I’m finding the M4 Message Breaking Project interesting: they are attempting to break three two as yet unbroken code intercepts that presumably use the Nazi 4-Rotor Naval Enigma machine.

Years ago when Simon Singh’s The Code Book came out, he ran a cipher challenge that invited readers to compete for a $10,000 prize by being the first to break 10 codes.   I broke 7 out of the 10 (all the ones I thought I had a shot) including a 3 rotor Enigma encrypt.   Breaking the 4 rotor variant with a much shorter message is a significant challenge, and they’ve managed to break one of the three already.

I’ve got their distributed client running on my machine.   We shall see how it goes.

[tags]Enigma Machine,Cryptanalysis,Codes,Ciphers,Distributed Computing[/tags]

Xerox printers use a watermarking technique to insert codes onto all printed documents from their Docucolor color laser printers. These identify date, time and printer serial number with a grid of yellow dots which appear in the printout. Presumably these codes are inserted to make the job of the Secret Service simpler in tracking their use in creating counterfeit money. What’s kind of cool though is that the EFF has figured out how to decode them. Interesting bit: the dots are simple to see when viewed under an intense blue light, like one of those blue Photon LEDs.

Sigh. Things like this really depress me. Minnesota court takes dim view of encryption | CNET News.com

A Minnesota appeals court has ruled that the presence of encryption software on a computer may be viewed as evidence of criminal intent.

From the PGP FAQ:

Who uses PGP?
People who value privacy use PGP. Politicians running election campaigns, taxpayers storing IRS records, therapists protecting clients’ files, entrepreneurs guarding trade secrets, journalists protecting their sources, and people seeking romance are a few of the law abiding citizens who use PGP to keep their computer files and their e-mail confidential.

Businesses also use PGP. Suppose you’re a corporate manager and you need to e-mail an employee about his job performance. You may be required by law to keep this e-mail confidential. Suppose you’re a saleswoman, and you must communicate over public computer networks with a branch office about your customer list. You may be compelled by your company and the law to keep this list confidential. These are a few reasons why businesses use encryption to protect their customers, their employees, and themselves.

PGP also helps secure financial transactions. For example, the Electronic Frontier Foundation uses PGP to encrypt members’ charge account numbers, so that members can pay dues via e-mail.

Whether this individual is guilty or not, this seems incredibly ill-conceived.

I’ve been interested in codes and cryptography for quite some time. I find them at the fascinating intersection of history, mathematics and computer science: all topics that I like to read about and experiment with. Let me give you a basic crypto lesson, with a moral at the end.

Let’s say that all your messages are coded just with capital letters, and you remove all spaces. This gives you an alphabet of (suprise!) 26 letters. Let’s say that you wish to encode a message. You think to yourself: golly, I know what I’ll do. I’ll convert each letter its corresponding number in the range of 1-26. That will make it confusing! So my message HELLO will translate into

8-5-12-12-15

But that doesn’t seem very hard. People could crack that pretty simply. What to do… what to do…

Well, I could scramble the letter order. Perhaps if A was represented by 13, and B by 8, and so on, they couldn’t figure it out. But if you do cryptograms in the newspaper, you know that even with a modest amount of code text, you can crack these things pretty easily using frequency analysis and the like.

Let’s go back to our simple code again. Imagine that we had a second text, the same length as the first that we could use as a key. To encode we add the two numbers together, and if the result is greater than 26, we subtract 26. That will certainly jumble up the frequencies, preventing some kinds of analysis, and since the key is long, techniques for polyalphabetic ciphers won’t really work either.

But there is a serious flaw. Imagine that you could guess a word in the cipher text. Perhaps if the message were addressed to me, it would contain BRAINWAGON or even worse VANDEWETTERING. You could try to subtract these words out of the cipher text, and if normal words popped out the other side, you would have a partial decrypt of both the message and the encoding stream. This may seem difficult if all you are used to is normal substitution ciphers, but in fact it is dead simple to break.

One way to avoid this problem is to use what is called a one time pad. If the encoding stream is truly random, then when you can’t recover the encoding stream (it is, after all, perfectly random). One time pads are perfectly secure, with the caveat that you can never, ever, ever reuse a one time pad. Why? Because then you could subtract the two messages, the one time pad data drops out, and you are left with the simple, easy to break case listed above.

Why the cryptography lesson? Because Bruce Schneier (author of the excellent book Applied Cryptography) points out that no less than Microsoft makes this exact error. When you save a Word document, it reencodes it with precisely the same stream, and therefore if you have access to multiple versions of the same document, you can recover the entire document with elementary cryptanalysis.

This is one of the reasons I like open source: you can audit software to find errors like this, and work to correct them quickly.

Anyway, if you like cryptography, privacy and information issues, subscribe to Bruce’s Cryptogram. It’s good stuff.

Interesting link of the day, courtesy of Boing Boing: FM 34-40-2 Basic Cryptanalysis. The truth is this kind of cryptography is pretty much of historical interest only, but I find historic codes to be, well, interesting.

This EFF-funded project sounds very interesting. It attempts to provide anonymity by making traffic analysis difficult by using something called an onion router. I’ll have to read more about it.

Tor: An anonymous Internet communication system

Tor is a toolset for a wide range of organizations and people that want to improve their safety and security on the Internet. Using Tor can help you anonymize web browsing and publishing, instant messaging, IRC, SSH, and more. Tor also provides a platform on which software developers can build new applications with built-in anonymity, safety, and privacy features.

The GCHQ has a bit of a Christmas challenge: break the code they have on their website, and be entered in a drawing for winning a copy of Simon Singh’s latest book. Cool. Check it out! Jeff and I might have something to do over the new year.

Here is an interesting early paper on the justification, implementation, analysis and use of random number generators, written in 1959. The resulting machine generated about 5000 bits per second, not bad!

Via Boing Boing. By the way, random numbers are still cool.