Time and Tide Wait for No Protocol: The SSH Keystroke Timing Attack of Song, Wagner, and Tianby Richard E. Silverman, author of SSH, The Secure Shell: The Definitive Guide
At the 10th Usenix Security Symposium (Washington D.C., August 2001), U.C. Berkeley researchers Dawn Song, David Wagner, and Xuqing Tian presented a paper titled, Timing Analysis of Keystrokes and Timing Attacks on SSH. The paper describes their research into applying traffic-analysis techniques to interactive SSH connections in order to infer information about the encrypted connection contents. The paper concludes that the keystroke timing data observable from today's SSH implementations reveals a dangerously significant amount of information about user terminal sessions--enough to locate typed passwords in the session data stream and reduce the computational work involved in guessing those passwords by a factor of 50.
Not surprisingly, this paper initiated a great deal of discussion among SSH users, developers, and the security community in general, especially in public forums such as Slashdot. In this article, I will summarize the issues involved, discuss the paper's methods and conclusions, and dispel some of the often-repeated misconceptions in the public's reaction to this research.
The paper revolves around the notion of traffic analysis, and while it uses SSH as a concrete example, the techniques involved are not specific to SSH, but rather apply to most interactive remote-terminal protocols as they are implemented today. The principle of traffic analysis is that there is a lot of useful information to be gleaned from the amount, timing, and direction of network traffic, even if you can't actually read the traffic content itself. Suppose I'm monitoring the network port leading to a system administrator's office. Perhaps I can't read or alter her SSH connections, but I can see:
when those connections are made and torn down, telling me when she arrives at work and leaves for the evening.
the addresses of the connected machines, telling me which hosts she's responsible for (and which ones she's not looking at).
the amount, rate, and timing of traffic going over the SSH sessions (separately in each direction), giving me some information about what she's doing. (For example, I can distinguish between terminal and file-transfer sessions.)
when all the terminal sessions go quiet, suggesting she may be out to lunch and now's a good time to hack her workstation (or break into her office).
These sorts of information leaks are very difficult to prevent. If you control all the physical components in your network and you can ensure that they all use link-level encryption and appropriately random idle-traffic generation, then that would be a start towards preventing traffic analysis--but except for very specific high-security installations, most of us have neither the opportunity nor the benefit of such designs. Considering the expense (or practical impossibility) of such countermeasures, traffic analysis is usually considered an unavoidable risk.
For more on SSH see Richard's Top Ten Secure Shell FAQs.
When accepting this risk, however, we generally assume that the danger is wholly indirect: an observer may be able to guess some useful ancillary information from traffic patterns, but the actual data is safe as long as we're using a good protocol, such as SSH. The disturbing conclusion of the recent Usenix paper is that this is not so; using sophisticated mathematical techniques it is possible to gather significant amounts of information about the contents of an SSH terminal session, by taking advantage of its interactive nature.
Interactive Traffic and Keystroke Timing
The delivery requirements for interactive traffic are different than those for bulk data transfer. When transmitting a file, TCP data can be batched up and sent in large IP datagrams for efficiency. But when you type a character in a terminal session, you expect to see it echoed immediately--not after you type the next thousand or so! Local echo and line editing can address that, but that won't work with curses-style software like Pine, or with the fancy line editing, command matching, recall, and other features of your favorite shell. So programs like Telnet and SSH send terminal data as soon as it becomes available, which means that the TCP connections for these programs transmit many short IP packets containing individual keystrokes and their echoes.
This real-time reflection of the user's typing behavior in the network stream is the basis of the paper's attack. Song, et al., observe that typical transmission latency in LANs, or indeed over the Internet, are negligible when compared with the inter-keystroke delays revealed by timing the arrival of single-keystroke TCP packets. Therefore, measuring packet-arrival times gives an accurate picture of the user's actual gestures at the keyboard.
|What do you think about the SSH Keystroke Timing Attack of Song, Wagner, and Tian? Please share your security experiences with SSH.|
|Post your comments|
The bulk of the paper then goes on to treat a topic that is entirely separate from SSH or network protocols in general, but which has important implications for them. The question is: does human keystroke timing leak significant information about the keys pressed? If so, can that information be used to guess at keystroke sequences? The answer to both questions is unfortunately "yes."
To summarize very broadly, the authors use a statistical technique called a Hidden Markov Model (HMM) to capture a user's keyboard habits, given data gathered from observing typing patterns and used to "train" the model. Then they use a prediction algorithm (a variation of the Viterbi algorithm) to guess at key sequences, given only the inter-keystroke timings together with the previously constructed model. The researchers tested their technique experimentally, using training data from real human subjects. The results suggest that timing data can leak as much as 0.71 bits per character on a typed password, corresponding to a 50-fold reduction in the work required for an offline dictionary attack. To estimate the practical effect of this, they write:
"For example, for a password containing randomly selected, lowercase letter keys and number keys, without timing information, the attacker would need to try 368/2 candidate passwords on average before he finds the right one. Benchmarks indicate that a 840MHz Pentium III can check about 250,000 candidate passwords per second in an offline dictionary attack. Thus, exhaustive search would take about 65 PC-days to crack a password composed of randomly selected, lowercase letter keys and number keys. If the attacker uses the timing information, the computation can be done in 1.3 days...."
On the face of it, this is pretty serious leak. But remember that so far, this is all still a fairly abstract investigation in an ideal, laboratory setting. There is still the question of whether this translates into a real threat when applied to actual network traffic. The paper goes on to address this as well.