8311034 2002-04-18 09:45 -0500 /347 rader/ Mauro Lacy <maurol@mail.com>
Sänt av: joel@lysator.liu.se
Importerad: 2002-04-19 04:13 av Brevbäraren
Extern mottagare: bugtraq@securityfocus.com
Mottagare: Bugtraq (import) <21944>
Ärende: Remote Timing Techniques over TCP/IP
------------------------------------------------------------
From: "Mauro Lacy" <maurol@mail.com>
To: bugtraq@securityfocus.com
Message-ID: <20020418144616.97515.qmail@mail.com>
Please consider this paper for publication.
Thanks,
Mauro
P.S.: here is a pdf version
http://maurol.com.ar/security/RTT.pdf
REMOTE TIMING TECHNIQUES
Introduction
This paper describes remote timing techniques based on TCP/IP
intrinsic operation and options. The techniques are used for careful
observation of the TCP/IP data stream to detect timing differences in
the operation of the remote application and relate them to selected
data and/or phenomena.
Basics
The methods will be made clear with a practical example, developed in
this paper.
Suppose that we want to know if a given username exists or not in a
remote system. What we can attempt to do is to carefully look for
processing timing differences in the remote logon process, between
the path taken by the remote application when a given username
exists, and when it doesn't. If we find a statistical difference (no
matter how small) between the two instances, we can determine if the
username exists or not. For this method to work, some conditions
must be met. First of all, a relatively appreciable difference in the
processing times of the two different processing paths must exist.
If this difference exists, the problem now is, how can we get a
detailed estimation of the remote processing times of each processing
path, given such facts as variable network latency and packet loss,
variable loads on the remote system, local factors, and such.
Causes of Appreciable Processing Time Differences
The initial cause of timing differences must be, of course, the
application's different processing paths itself. Now, for this
difference to become appreciable, some slow event must occur in one
of the paths and not in the other. A typical "slow event" in a
computer, is disk access. Other main cause of "slowness" is the
computer itself. The examples in this paper were tested on relatively
"slow" (old) computers, and could not be reproducible in all
environments.
Remote Timing Techniques (RTT)
Timestamps
Timestamps were added to TCP to allow precise estimation of the Round
Trip Time (RTT), which is necessary on high bandwidth networks to
avoid data loss and/or congestion. As a side effect, they also allow
(at least in some implementations), "precise" estimation of remote
processing times, given birth to a series of new techniques, which we
will also denominate RTT (Remote Timing Techniques). For a detailed
description of timestamps, see RFC 1323. The precision of the
estimation depends on the frequency of the timestamp clock, which
according to the RFC can vary from 1ms to 1sec. The implementation
differences in the frequency of this clock are what render the method
useful (or not) with respect to the techniques described here. In
Appendix A you will find a table with the different timestamp clock
frequencies by operating system. Incidentally, timestamps can also
be used in some cases to know the uptime of the remote system, and/or
to distinguish between different systems in a load balanced
environment. See Appendix B for references. Timestamps are a
relatively new addition to the TCP/IP protocols (1992, see RFC 1323),
and are consequently not supported by all operating systems, are also
not enabled by default in some OSs, and lastly, their implementation
make timestamps not always useful with regard to the techniques
described here.
TCP Intrinsic Operation
The other method found, which is in some cases much more "precise"
(and therefore useful) than timestamps to discriminate between two
different remote paths of execution, is related to the intrinsic
operation of the TCP/IP protocol. It is simply the fact that the ACK
and "PUSH" flags can be sent together in the same packet, depending
on if the application layer had passed the data or not to the TCP
stack for delivery before the stack "ACKs" a previously received
segment from the client. That is, if the server stack has something
to ACK and at the same time has some data to send to the client, it
"ACKs" and "PUSH" at the same time (in the same packet), but if the
application is busy doing some other slow thing (like writing to
disk) and didn't pass the data to the TCP stack quickly, the TCP
stack sends a packet with only the pending ACKS (no data) and this
difference can be easily detected on the client side. This technique
is in some cases even better than timestamps, due to the fact that
its "frequency" depends on the implementation of the TCP stack
itself, and must be much faster (I don't know with certainty) than
typical timestamp clocks. Moreover, this "frequency" is probably not
fixed (i.e.: 100/se! c) but depends on the speed of the processor,
and its "precision" increases accordingly when the processing speed
increases. The other advantage of this technique is that is common to
all TCP implementations, and is therefore always "enabled" and
available in all systems with a TCP stack.
Due that the timestamp information and the ACK and PUSH states depend
completely on the operation of the remote system, and are passed to
the client side as a kind of "snapshot" of the remote system, these
methods are completely immune to network latency variations. They are
also statistically immune to packet loss and load variations, and to
other variable factors (disk IO, buffer cache, etc) being anyways
necessary to increase the number of probes in case of small
differences and/or great variations in the aforementioned factors.
Through careful examination of the behavior of the TCP data flow,
observing the TCP headers at the right moments, is possible to
statistically determine (by example) if a given username exists or
not on a remote system, under the particular circumstances detailed
below.
Proof of Concept
This example was tried successfully in two Linux boxes, one with Suse
7.0 (kernel 2.2.16) and the other with RedHat 6.2 with kernel
2.2.12. Both machines are relatively "old" machines, a Pentium II 366
and a Pentium MMX 233, both with standard IDE disks. Many tests
remain to be done, but I dare to say that the essential point seems
to be mostly software related, that is, related to the way the remote
application or service is written, than to the hardware used. The
techniques can be tried on any type of authentication process over
TCP. Other uses of these techniques can also be found. Linux has a
timestamp clock frequency of 1000/s (1ms), which isn't very good, but
is anyways useful. Delays greater than 1ms are typical of hard disks,
and from the point of view of the application they remain
statistically greater than 1ms independently of the buffer cache (at
least with IDE disks). Apropos, Cisco IOS implements a timestamp
clock period of .1ms(!), although timestamps are disabled by default.
Description of Operation
Tcpdump is run in the background to capture the specific data flow (a
telnet logon session) and an automated telnet session is initiated
against the remote system, with a chosen username/password pair. The
password is used as a mark in the stream. The specific point at
which the analysis must be made is detected (using the password
mark), and the script outputs the TCP flags and the remote timestamp
differences at that point. The later is possible due to the fact that
Linux had timestamps enabled by default (2.2.x kernels) and also
because it sends timestamps in both directions (encouraged by the RFC
for simplicity). If you note statistical differences between probes
with a known to exist username (root, bin, lp, sys, etc) and probes
with a known to be un-existent username (i.e.: dskhjgfjh), the remote
system is vulnerable. The number of probes doesn't need to be very
large (between 1 and 20) but in case of small differences, could be
necessary to increase them. The probes will generate logs in the
remote system (indeed, the processing time involved with these logs
could be one of the causes of the timing differences) and, as long as
you made more probes, more logs will be generated.
Statistical Differences Detected
- In this particular example, in case that the username exits on the
remote system, the first packet sent by the remote system after the
password was sent by the client, tends to be an "empty" (no data) ACK
packet. This does not happen always, and some probes need to be done.
Due to the fact that the data arrives almost always just a little bit
later from the application layer to the TCP stack, and is then almost
immediately sent to the client, the difference of the timestamps of
the data packet and the previous ACK packet tends to zero in these
cases.
- In case that the username does not exist, the packet tends to
be a data packet (ACK+"PUSH"). The timestamp differences with the
next packet (typically other ACK+data packet, the next "login:"
banner) tend to be relatively big.
So, when the username exists, the mean of the timestamp differences
of the probes tend to be smaller than the mean of the differences if
the username does not exist. If timestamps are not enabled, you can
detect the difference anyway (!): The number of times you'll see an
"empty" (no application data) ACK packet (again at the right place of
the data stream) will be greater if the username exist than the
number of times you'll see it if the username doesn't exist. Of
course, even without this information, the difference could be
statistically detected anyway. More (maybe many more) probes will be
necessary, to overcome the measurement errors introduced mainly by
network latency variations. On networks with high latency variations,
this could yield the "attack" highly unpractical. The techniques
described here are useful to diminish the measurement errors over TCP
network links, diminishing then the number of probes or samples
necessary to detect a timing difference, thus yielding some otherwise
unfeasible or expensive attacks feasible.
Other Services
Other tested services known to be vulnerable to this kind of "attack"
are:
- rlogin: rlogind also gives us the same information, but after two
passwords are entered. (In the pause between the second password
entry and the "Login incorrect" message. As long as the standard
rlogin command "clears" its standard input before asking for a
password, no automation is possible without replacing it with other
version or reproducing the protocol manually.
- ftp: wu-ftp seems to be vulnerable also, just after entering the
username (after the USER command). A slight difference of around 1ms
was statistically detected using the timestamp information, on the
Suse distribution.
Services that remain to be tested:
- imap
- pop
- rexec
- Auth services over http.
- ssh: ssh (or any other encrypted protocol) is a particular case,
due to the fact that an eavesdropping attack makes sense in these
cases. The techniques described here could be used (by example) to
extend Paul Kocher attack (see References) over a network protocol
(i.e. to make the attack remotely possible).
- ...
All tests were done only on Linux, mainly on the machine with the
Suse distribution. Other operating systems and services remain to be
tested.
Probable cause of the differences
The probable cause (not verified) of the differences in both systems
seems to be the difference in the logging done trough syslog if the
username exists or if not. In the Suse distribution, particularly,
faillog logging is enabled by default, and this logging occurs only
if the username exists (and the logon failed, of course). Other
probable (also unverified) cause of the differences could lie inside
the implementation of the various pam modules on which Linux
authentication depends. If pam were the cause, the same effect would
have to be observable in all the services that relay on pam for
authentication (the default).
Possible Solutions
As long as at least one of the techniques depends on the intrinsic
operation of the TCP stacks, no easy solution seems to be available.
With regard to timestamps, a partial solution would be to increase
the period of the timestamp clock, let's say, to 50ms or more. But
probably, statistical differences would show up in the long term.
The "problem" of the intrinsic operation of the TCP stack would still
remain. The only definitive solution seems to be to modify the code
of the vulnerable services, in order to avoid the "leaking" of timing
information, by example introducing random delays, or better, always
sending data packets to the client with no pending ACKS in them (and
random delays for timestamps). A "send" function with these
characteristics wouldn't be so difficult to write and use.
Other Applications And Uses
I'll quote here a comment by Paul Kocher, who told me in a private
communication
"You might want to try some ... statistical attacks ...
... -- using them, even very tiny differences (<1 us) can
be resolved even if there is quite a lot of measurement error
(>1 ms)... . The general math required
is quite simple - you'd want to look for the difference between
the *average* time when [for example] n bytes of a password
are correct and the average time when n+1 bytes of the password
are correct."
That is, the only necessary thing to detect a timing difference is to take enough samples or to make enough probes for the difference to become statistically appreciable. The number of probes or samples will be directly proportional to the measurement error (that is, to the variance of the measurements), and inversely proportional to the variance of the timing difference to detect (from Kocher paper).
I want to make clear here, before generating unnecessary alarms, that Mr. Kocher is talking about an hypothetical case. At least in Unix, passwords can't be revealed this way due to the fact that in the encryption process the correlation between clear text and encrypted password is lost; an incorrect clear text password "closer" to a correct one, does not yield an encrypted password closer to the real encrypted password. Thus, no "password approximation" is possible.
An obvious practical use of these techniques is as an addition to,
for example, a brute force username/password tester, to avoid trying
username/password combinations with an inexistent username. The
program could start testing username/password pairs normally, at the
same time that it monitors the data flow to statistically detect the
actual username existence or inexistence, changing its behavior
accordingly.
Timestamps could also be used to precisely measure inter keystroke
timings of an interactive encrypted session; so, they can be used, by
example, to greatly improve the efficiency and precision of the
"Herbivore" system (see Wagner et al), especially over networks links
with big latency variations.
Other uses of these techniques could be discovered or
developed. (directory and/or file discovery?, fingerprinting issues?,
...?). Generally speaking, whenever a timing difference is
identified(by source code analysis, by example), RTT could be used to
"measure" or detect that difference remotely over TCP.
Source code
The appendix B contains scripts that will do the hard work for
you. You probably would have to make some manual adjustments, mainly
the interface name(s), needed by tcpdump. The scripts were written
without taking into account security practices (i.e. writing "secure"
code). They are probably even remotely exploitable.
Conclusions
Although the particular example shown here does not yield a great
deal of information (just the knowledge of if a given user exists or
not on a remote system) and is successful only if a series of
conditions are met, the techniques used to know this little bit of
information are new (as far as I know), and probably they could be
used in many other ways. TCP timestamps could yield a "precise"
timing of the remote processing paths, what can be potentially useful
for many different purposes. In particular, some operating systems
seem to have a much more precise timestamp clock than Linux, and this
open new possibilities to experimentation. On the other side, given
the fact that one of the techniques (observing TCP flags) is
intrinsic to TCP operation, its application is feasible wherever a
TCP connection is being used.
Acknowledgments
Thanks to David Wagner, Paul Kocher and Brett McDanel for their
suggestions and comments.
Appendix A: Table of Operating Systems and Timestamp Clock Frequency.
See Bret McDanel Work (Appendix B)
Appendix B: References and Related Works
RFC 1323 http://www.cis.ohio-state.edu/cgi-bin/rfc/rfc1323.html
Bret McDanel Paper on Timestamps http://www.mcdanel.com/bret/research/tcp_timestamp.jsp
Paul Kocher Timing Attack Paper http://www.cryptography.com/timingattack/paper.html
Dawn Xiaodong Song, David Wagner and Xuqing Tian Paper on
Timing Attacks on SSH http://www.usenix.org/publications/library/proceedings/sec01/song.html
PDF Version of this Paper http://www.maurol.com.ar/security/RTT.pdf
Appendix C: Source Code
-------------------------------------------------------------rtt.sh-----------------------------------------------------------------------
#!/bin/bash
# Probe a telnet service using remote timing techniques
# to determine if a user exist or not.
# Proof of Concept code.
# (C) 2002 maurol (maurol@mail.com)
# Customize these if needed:
LOOPBACK=lo
LAN=eth0
#WAN=eth0
WAN=ppp0
# Default interface to listen to
#IFACE=$LAN
IFACE=$WAN
# Default port
PORT=23
# Default number of probes
COUNT=10
# Time in seconds to wait before sending the username. For slow links
# and/or no reverse dns resolution this could be as big as 25.
LAN_SLEEP=1
WAN_SLEEP=6
#SLEEP=$LAN_SLEEP
SLEEP=$WAN_SLEEP
if [ $# -lt 2 ]
then
echo "Usage: $0 <ip> <user> [count] [sleep]"
echo "ip : IP address of remote system."
echo "user : Username to probe."
echo "count: Number of probes."
echo "sleep: Initial sleep in seconds."
exit 1
fi
HOST=$1
USER=$2
[ "$HOST" = "127.0.0.1" ] && IFACE=$LOOPBACK
if echo $HOST | grep -E "^10\.|^192\.168\." >/dev/null
then
IFACE=$LAN
fi
[ "$IFACE" = "$LOOPBACK" ] && SLEEP=$LAN_SLEEP
[ "$IFACE" = "$LAN" ] && SLEEP=$LAN_SLEEP
[ "$IFACE" = "$WAN" ] && SLEEP=$WAN_SLEEP
PASS=zzzzz
export PASS
[ -z "$3" ] || COUNT=$3
[ -z "$4" ] || SLEEP=$4
export IFACE HOST PORT USER
MEAN=./mean
VAR=./var
[ -x $MEAN ] || cc -o mean mean.c
#[ -x $VAR ] || cc -o var -lm var.c
>tests.$USER
c=0
while [ $c -lt $COUNT ]
do
# Launch the capture script in the background
(./capture.sh >/tmp/regs.$$ ; ./dif.sh /tmp/regs.$$ | tee -a tests.$USER; rm -f /tmp/regs.$$) &
# Start telnet session
(sleep $SLEEP; echo $USER; sleep 1 ; echo $PASS ; sleep 3)| telnet $HOST
c=`expr $c + 1`
sleep 1
done
echo
(
cat tests.$USER | egrep -v "^[ ]*$"
echo -n "mean: " ; cat tests.$USER | egrep -v "^[ ]*$" | $MEAN 2 ;echo
#echo -n "var.: " ; cat tests.$USER | egrep -v "^[ ]*$" | ./var.sh 2 ;echo
) | tee stats.$USER ; rm -f tests.$USER
----------------------------------------------------------------capture.sh---------------------------------------------------------------------
#!/bin/bash
# Captures the telnet session and seeks the useful timestamps and flags.
HEX=/usr/bin/hex
TCPDUMP=/usr/sbin/tcpdump
if [ -x $HEX ]
then
PATTERN=`echo $PASS | $HEX -w 3 -g | head -1 | sed "s/^[^ ]* //;s/ //" | cut -c-7| sed "s/[ ]*$//"`
else
PATTERN="7a7a 7a" # "zz z" ;-)
fi
if [ -x $TCPDUMP ]
then
$TCPDUMP -l -n -n -i $IFACE -x port $PORT > /tmp/lst &
else
echo "$TCPDUMP not found or not executable!"
exit 1
fi
sleep 2
while ! grep "$PATTERN" /tmp/lst >/dev/null
do
sleep 1
done
sleep 3
sed -n "/$PATTERN/,\$p" /tmp/lst | grep "$HOST.$PORT >" | sort -u | head -2 | sed "s/^.*$HOST.$PORT >//" | awk '{print $2" "$8" "$9}'
killall tcpdump
rm -f /tmp/lst
--------------------------------------------------------------------dif.sh----------------------------------------------------------------------
#!/bin/bash
FLG1=`head -1 $1 |awk '{print $1}'`
TS1=`head -1 $1 | grep timestamp | awk '{print $3}'`
FLG2=`head -2 $1 |tail -1 |awk '{print $1}'`
TS2=`head -2 $1 |tail -1 | grep timestamp | awk '{print $3}'`
DIF1="-"
[ -z "$TS1" ] || [ -z "$TS2" ] || DIF1=`expr $TS2 - $TS1`
echo "$FLG1 $DIF1"
--------------------------------------------------------------------mean.c----------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define MAXLINE 1024
#define MAXVAL MAXLINE
main(int argc, char **argv)
{
int col=1,c=0,v=0;
float s=0;
float va;
char *line,*pline, *val;
line=(char *)malloc(MAXLINE);
val =(char *)malloc(MAXVAL);
pline=line;
if (argc>1)
col=atoi(argv[1]);
while (line=fgets(line, MAXLINE, stdin)) {
for(v=0;v<col;v++)
val=strsep(&line, " ");
line=pline;
if (val[0] == '\0')
continue;
va=strtod(val,NULL);
s=s+va;
c++;
}
printf("%.6f ", s/c);
}
Source Code Download http://www.maurol.com.ar/security/rtt.tgz
Author
Mauro Lacy (maurol@mail.com)
--
_______________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup
(8311034) /Mauro Lacy <maurol@mail.com>/--(Ombruten)
Kommentar i text 8311037 av Exportören
8314953 2002-04-19 06:06 +0200 /39 rader/ Syzop <syz@dds.nl>
Sänt av: joel@lysator.liu.se
Importerad: 2002-04-19 20:30 av Brevbäraren
Extern mottagare: Mauro Lacy <maurol@mail.com>
Extern mottagare: bugtraq@securityfocus.com
Mottagare: Bugtraq (import) <21955>
Kommentar till text 8311034 av Mauro Lacy <maurol@mail.com>
Ärende: Re: Remote Timing Techniques over TCP/IP
------------------------------------------------------------
From: Syzop <syz@dds.nl>
To: Mauro Lacy <maurol@mail.com>, bugtraq@securityfocus.com
Message-ID: <3CBF97B9.5150735@dds.nl>
Hi,
Mauro Lacy wrote:
> This paper describes remote timing techniques based on TCP/IP intrinsic operation and options. The techniques are used for careful observation of the TCP/IP data stream to detect timing differences in the operation of the remote application and relate them to selected data and/or phenomena.
This reminds me of http://online.securityfocus.com/archive/82/185167
(+see the thread) which also discusses something like this (timing
techniques) and the "additional noise" such as task switches, etc.
> I'll quote here a comment by Paul Kocher, who told me in a private communication
>
> "You might want to try some ... statistical attacks ...
> ... -- using them, even very tiny differences (<1 us) can
> be resolved even if there is quite a lot of measurement error
> (>1 ms)... . The general math required
> is quite simple - you'd want to look for the difference between
> the *average* time when [for example] n bytes of a password
> are correct and the average time when n+1 bytes of the password
> are correct."
I also remember this reply with another aproach to this problem:
(from http://online.securityfocus.com/archive/82/186161 )
Quote:
> Why noise-filtering? Since there seem to be no invalid low numbers,
> just take the minimum of a certain amount of tries (1000, 10000)
> and check whether those give you a clue -- i.e. try to find
> the ones with the lowest noise and compare them.
I didn't read this all yet (it's a bit late), but it looks very
interresting...
Bram Matthys.
(8314953) /Syzop <syz@dds.nl>/------------(Ombruten)
8314975 2002-04-19 05:28 +0400 /28 rader/ Solar Designer <solar@openwall.com>
Sänt av: joel@lysator.liu.se
Importerad: 2002-04-19 20:39 av Brevbäraren
Extern mottagare: Mauro Lacy <maurol@mail.com>
Extern kopiemottagare: bugtraq@securityfocus.com
Mottagare: Bugtraq (import) <21956>
Kommentar till text 8311034 av Mauro Lacy <maurol@mail.com>
Ärende: Re: Remote Timing Techniques over TCP/IP
------------------------------------------------------------
From: Solar Designer <solar@openwall.com>
To: Mauro Lacy <maurol@mail.com>
Cc: bugtraq@securityfocus.com
Message-ID: <20020419052810.A25205@openwall.com>
On Thu, Apr 18, 2002 at 09:45:53AM -0500, Mauro Lacy wrote:
> REMOTE TIMING TECHNIQUES
It's good to see this kind of weaknesses to start being publicized. I
know there's another similar paper to be published soon.
We've been discussing the possibility to apply a variation of
Kocher's attack against SSH clients w/ RSA/DSA authentication (where
a malicious server would obtain the client's private key and be able
to use that against another server) with Markus and Niels of OpenSSH
just recently.
I don't see how a client -> server attack against SSH would be
possible (other than on usernames and such).
The leak of usernames is of course the most obvious example, pretty
much every service is affected. Of course we avoid leaks like that
in our code (popa3d, pam_tcb on Owl), but we haven't fixed our system
libraries (such as glibc's NSS modules) yet and those are used by all
services.
--
/sd
(8314975) /Solar Designer <solar@openwall.com>/(Ombruten)
Kommentar i text 8318473 av stealth <stealth@segfault.net>
8318473 2002-04-20 16:45 +0000 /36 rader/ stealth <stealth@segfault.net>
Sänt av: joel@lysator.liu.se
Importerad: 2002-04-20 21:04 av Brevbäraren
Extern mottagare: Solar Designer <solar@openwall.com>
Extern kopiemottagare: bugtraq@securityfocus.com
Mottagare: Bugtraq (import) <21979>
Kommentar till text 8314975 av Solar Designer <solar@openwall.com>
Ärende: Re: Remote Timing Techniques over TCP/IP
------------------------------------------------------------
From: stealth <stealth@segfault.net>
To: Solar Designer <solar@openwall.com>
Cc: bugtraq@securityfocus.com
Message-ID: <20020420164507.GB5408@segfault.net>
On Fri, Apr 19, 2002 at 05:28:10AM +0400, Solar Designer wrote:
> On Thu, Apr 18, 2002 at 09:45:53AM -0500, Mauro Lacy wrote:
> > REMOTE TIMING TECHNIQUES
>
> It's good to see this kind of weaknesses to start being publicized. I
> know there's another similar paper to be published soon.
>
> We've been discussing the possibility to apply a variation of Kocher's
> attack against SSH clients w/ RSA/DSA authentication (where a malicious
> server would obtain the client's private key and be able to use that
> against another server) with Markus and Niels of OpenSSH just recently.
>
> I don't see how a client -> server attack against SSH would be possible
> (other than on usernames and such).
>
> The leak of usernames is of course the most obvious example, pretty much
> every service is affected. Of course we avoid leaks like that in our
> code (popa3d, pam_tcb on Owl), but we haven't fixed our system libraries
> (such as glibc's NSS modules) yet and those are used by all services.
Probably speaking of
http://stealth.7350.org/epta.tgz which describes timing-weaknesses
in UNIX daemons+libs. ;-)
It also contains some sourcecode which demonstrates that these attacks
are possible.
Maybe one is able to join all the stuff ;-)
regards,
S.
(8318473) /stealth <stealth@segfault.net>/----------