OpenSSH and keystroke timings

By Jake Edge
September 17, 2008

Theoretical security weaknesses have a tendency to move from the realm of theory to that of practice over time. Sometimes it is the result of more compute power being applied or better algorithms being developed, but a weakness is certainly not going to get stronger. So when Kevin Neff started discussing fixing a weakness in OpenSSH on the openbsd-misc mailing list, the folks writing it off as "theoretical" may have been jumping the gun.

When it is in interactive mode—a user typing into a terminal session for example—ssh sends each key pressed by the user in a separate packet. By observing the timing between packets, an observer may be able to determine something about what was typed just by using traffic analysis, without attempting to break the encryption. Researchers found that the inter-packet timing correlated well with the inter-keystroke timing, so that using statistical techniques they were able to reduce the search space for cracking a password by a factor of 50.

This weakness was outlined in a 2001 paper entitled Timing analysis of keystrokes and timing attacks on SSH" [PDF] which looked specifically at the timing-based attack:

In this paper we study users' keyboard dynamics and show that the timing information of keystrokes does leak information about the key sequences typed. Through more detailed analysis we show that the timing information leaks about 1 bit of information about the content per keystroke pair. Because the entropy of passwords is only 4-8 bits per character, this 1 bit per keystroke pair information can reveal significant information about the content typed.

The paper looked at the now-deprecated SSH1 protocol, which led some to conclude that it substantially invalidated the weakness. Damien Miller pointed out that it was likely to still be valid:

There is no reason to believe that keystroke timing attacks will be impossible against protocol 2 where they work against protocol 1. They might just be a little more tricky.

Pointing at the paper and discounting it because it is ssh1 only is sticking your head in the sand. It is usually easier to research attacks on simpler protocols and work up to more complicated ones later.

There is a fair amount of information that can be gleaned just by looking at the traffic generated over an encrypted session, especially if the attacker can gather a sizable amount of it. There are fairly clear patterns in interactive sessions that can be extracted and used alongside the inter-keystroke timing information to potentially garner lots of useful information. Darrin Chandler describes it this way:

The reason why I think it's a weakness is that you can gather statistics on typing and use those to infer things. I.e., you can extract meaningful information from the encrypted session. If you're snooping on ssh and see a short burst of typing followed by another ssh session from the remote machine you can guess they typed 'ssh host.example.com' by the length of typing and the host connected to. Nice crib. Oh, after than connect was there another short burst? Probably the password. How many keystrokes can probably be inferred. Perhaps stats on interkey timing can be used to make some intelligent guesses, such as the 4th char is NOT punctuation because is followed char 3 too closely. Or whatever.

Overall, the reception to making OpenSSH less susceptible to this kind of analysis was positive. It is clearly a difficult attack to mount, logistically if nothing else, but it is not impossible either. Better timing information or analysis techniques might make it easier over time as well and that is enough of a reason to look at ways to fix it.

Index entries for this article
Security	OpenSSH

OpenSSH and keystroke timings

Posted Sep 18, 2008 3:17 UTC (Thu) by flewellyn (subscriber, #5047) [Link] (2 responses)

Overall, the reception to making OpenSSH less susceptible to this kind of analysis was positive.

It was? When last I checked the thread logs on Kerneltrap, the general sense I saw was that most of the OpenSSH and OpenBSD folks were unconcerned to the point of hostility to the idea of preventing this kind of attack. Has that changed in the last day or so?

OpenSSH and keystroke timings

Posted Sep 18, 2008 14:47 UTC (Thu) by smoogen (subscriber, #97) [Link] (1 responses)

One thing I have noticed is that the types of hostility that OpenXXX people have can be interpreted to the amount of support they have towards an idea. And while they attract an audience that likes to add in on the hostility, you have to know who the key people are and what flames they are emitting to see which way things go. I think if Damien Miller is saying that it needs to be looked at.. then it will probably be done.

OpenSSH and keystroke timings

Posted Sep 19, 2008 6:02 UTC (Fri) by djm (subscriber, #11651) [Link]

heh, % free_time :)

OpenSSH and keystroke timings

Posted Sep 18, 2008 3:35 UTC (Thu) by bronson (subscriber, #4806) [Link] (8 responses)

ssh could buffer up the password until the user hits return, then send it all in on packet. I presume it doesn't do this because it doesn't want to keep track of a password mode? It will just let the remote machine handle the username/password prompting?

And inserting a random delay between keystrokes would be pretty annoying when typing your user name... Yeah, I guess that's not an easy problem to solve!

OpenSSH and keystroke timings

Posted Sep 18, 2008 4:38 UTC (Thu) by shapr (subscriber, #9077) [Link] (1 responses)

Yeah, my first thought was, "send the password all at the same time."

My next thought is "try to use backspace in your password." Though that could also be found out if you always use backspace in the same position.

I suspect that use of dvorak or some other non-qwerty keyboard might make this a tetch more difficult.

Back to line-by-line input...

Posted Sep 18, 2008 5:30 UTC (Thu) by eru (subscriber, #2753) [Link]

My next thought is "try to use backspace in your password."

Suppose ssh introduced a line-by-line mode, where editing like backspace can be done locally by the ssh client? This would of course require that all software you are trying to feed passwords to will co-operate in setting the line-mode. Maybe this would even need a new stty mode?

In the age of dinosaurs, these kinds of line-by-modes were normal on non-Unix systems. In fact it was quite uncommon for apps to react to individual characters from terminals. Editing was handled by "smart terminals" or front-end machines, which fed complete lines (or even complete filled forms) to The Real Computer.

OpenSSH and keystroke timings

Posted Sep 18, 2008 4:54 UTC (Thu) by jimbo (guest, #6689) [Link] (1 responses)

I'm not a network expert, but aren't the SSH packets themselves encrypted?

It might be practicable to add noise into the plain text of a short packet, encrypt the whole thing (including the noise). The packet can then be decrypted, and the actual data extracted for use by the application.
--
Jimbo

OpenSSH and keystroke timings

Posted Sep 18, 2008 7:15 UTC (Thu) by bboissin (subscriber, #29506) [Link]

The problem is the timing between packets, not the encryption.

not really

Posted Sep 18, 2008 7:20 UTC (Thu) by dlang (guest, #313) [Link] (2 responses)

how would ssh know that you are sending a password?

do you _really_ want your transport layer to start guessing at what strings may be password prompts that should shift you into line-based mode instead of character mode? what if that string shows up in the middle of an image while you are playing a game, do you really want it to start buffering all your keystrokes (and not showing you) until you hit enter?

the only fix for this is to waste bandwidth by sending garbage packets.

my solution, try to sidestep the problem by using hardware token based authentication wherever possible rather then passwords (even over encrypted links)

not really

Posted Sep 18, 2008 8:53 UTC (Thu) by epa (subscriber, #39769) [Link] (1 responses)

how would ssh know that you are sending a password?

Password prompts already send special magic characters to the tty to turn off echoing. It would need only a small extension to su(1) or ssh(1) to make them echo a new sequence meaning 'I am reading a password now'. The remote ssh client would note this and batch up a whole line of input to send at once.

not really

Posted Sep 18, 2008 18:18 UTC (Thu) by djm (subscriber, #11651) [Link]

Actually OpenSSH already defends against this case: we detect when echo is turned off and send fake echo (SSH2_MSG_IGNORE) packets back in responses to keystrokes. This makes it more difficult for an attacker to tell when the user is actually typing in a password.

OpenSSH and keystroke timings

Posted Sep 18, 2008 15:52 UTC (Thu) by docwhat (guest, #40373) [Link]

Wouldn't do anything useful; ssh may already do this.

The problem is that if you ssh from a to b. Then ssh from b to c. If someone eavesdrops on your a-b connection, they will see the password for c being typed.

Ciao!

One more reason...

Posted Sep 18, 2008 8:02 UTC (Thu) by alex (subscriber, #1355) [Link] (1 responses)

...to be using key-based logins

One more reason...

Posted Sep 18, 2008 18:21 UTC (Thu) by djm (subscriber, #11651) [Link]

That's not the problem. Passwords typed during authentication are already quite secure - they are not sent keystroke by keystroke, rather in their entirety and padded up to the nearest 2^n in length (to hide their real length).

The problem is keystrokes typed once the session is up, e.g. your password after running "sudo". We already have measures in place to make it difficult for an eavesdropper to know when you are typing such a password, but they could still perform traffic analysis on the entire session.

Buffer keys at 100 ms intevals

Posted Sep 18, 2008 15:23 UTC (Thu) by felixfix (subscriber, #242) [Link] (6 responses)

Only send keystroke packets every 100 ms (of course this interval would have to be configurable). If that is no keys, no packet. If that is 1 key, one packet. If it is 10 keys, one packet.

It would introduce some weird latency. But I think it would be fairly easy to try, and some experimenting would show whether an interval small enough to be bother-free would send multiple keys.

You could even make it a lower and upper bound, and it would choose a random interval between them for each packet.

I wonder how much difference this would make in the entropy.

I personally don't think a 100 ms interval would be very obnoxious. The weird part would be its burstiness, which might make 100ms too hard to get used to. But if you pick an interval that sometimes sends two or even three keys, that should be enough. Well, but then you might have packets every interval for several intervals, then skip one or two, then a few more, and that might be a clue that the skipped packets were due to quickly typed keys having been combined in the previous or next packets :-)

Buffer keys at 100 ms intevals

Posted Sep 18, 2008 15:55 UTC (Thu) by docwhat (guest, #40373) [Link] (2 responses)

Adding chaff might be easier and less disruptive. Have SSH randomly send non-keystroke keystroke-like packets every so often. Latency wouldn't be effected much.

You could also randomly time shift keys characters by a 1ms or two every so often. I don't think a user would notice that.

Ciao!

Buffer keys at 100 ms intevals

Posted Sep 18, 2008 18:17 UTC (Thu) by felixfix (subscriber, #242) [Link] (1 responses)

Those are both better ideas :-) The chaff one is fun, but the time shifting sender is the best, since it produces no chaff for the receiver to have to discard. My batching idea might also require a receiver change, if keystroke packets can only have single keys now. The time shifter can be done entirely on the sender side and the receiver will never know the difference.

Buffer keys at 100 ms intevals

Posted Sep 18, 2008 19:29 UTC (Thu) by docwhat (guest, #40373) [Link]

Sure. Implement the key jitter-time-shift idea now. Then later you can add stuff that requires the receiver to understand it's chaff.

Ideally, the packets should be the same size, so keys and chaff should both be the same structure except that the chaff has an extra bit saying it's chaff.

An alternative that may be implementable now (I don't know much about the SSHv2 protocol) is to use a bogus encryption key so that it is rejected on the receiving side. That'll add additional confusion to anyone trying to break the stream as they'll have to separate the differently encrypted packets from one another.

Ciao!

Buffer keys at 100 ms intevals

Posted Sep 18, 2008 18:22 UTC (Thu) by djm (subscriber, #11651) [Link] (2 responses)

Yes, this is essentially the idea I had: quantise the packet sending time to some interval, and send chaff for some interval after the last keystroke. Unfortunately this is quite difficult to implement in OpenSSH's crufty mainloop :(

Buffer keys at 100 ms intevals

Posted Sep 19, 2008 0:20 UTC (Fri) by gmaxwell (guest, #30048) [Link] (1 responses)

Tricks like this sound nice but try proving that they actually stop the information leak. As far as I'm aware nothing short of padding to a full constant information rate has ever been proven to stop information leaks from timing in systems where they have been considered (anonymous remailers, onion networks).

Since we're already talking about a somewhat obscure (though, no doubt, real) vulnerability it's probably not worth adding complexity for a half solution which can not be proven to completely close the hole.

To me the obvious solution to this would be to extend ssh agent to supporting more types of authentication, and allowing programs other than SSH to make use of that functionality. Timing attack immunity would fall out as a nice side-effect but greater robustness against compromised jump hosts would also be a benefit, as well as the ability to provide things like smart-card authentication across multi-hop ssh connections.

Beyond the basic SSH-via-SSH or SUDO-(PAM)-via-SSH) cases it would take some time for applications to be updated to take advantage of this functionality, so it wouldn't be an overnight fix, but we've lived with this vulnerability this long so a bit longer waiting for the right fix shouldn't kill anyone.

Buffer keys at 100 ms intevals

Posted Sep 19, 2008 6:00 UTC (Fri) by djm (subscriber, #11651) [Link]

SSH isn't like an Onion network or a remailer - those seek to hide the identities of disparate users, whereas SSH just needs to mask inter-keystroke timings and run lengths. It's quite a different (and much simpler, thankfully) problem.