On Thu, 17 May 2001, Klaus Frank wrote:
> Is it possible to average the measured durations of a huge amount of
> connection attempts until the differences from memcmp() add to a peak
> that exceeds the added random part of the additional delay?
In theory: yes. In practice: it may be possible but it is probably not as
feasible as it might look at the first glance. (*) Even if the probes are
sent by a local user, they still have to pass through too much other
software. The signal--the differences in memcmp() timings--is measured in
few CPU clock ticks but the noise is much higher--tens, hundreds, maybe
even thousands of clock ticks (or more if no ultra-high precision clock is
available). I myself have done some experiments (using Pentium built in
tick counter) and the measurements appear to be too perturbed to provide
any clue about the number of correct bytes. (**) Perhaps some smart
noise-filtering techniques might make the results look better?
(*) There is a story about an operating system having a call that required
a password--whose address was passed as one of its argument. The
implementation verified the given password by comparing it the correct
one, byte after byte and exiting as soon as a difference was found, i.e.
there was the same kind of information leak. But as far as remember, the
actual attack against the system invoked the call with a password crossing
a page boundary, with the second page swapped out (ergo any access to
it would cause a page fault), to amplify timing differences.
(**) The tests were made on an idling Pentium III on 800 MHz with 1/2 GB
of RAM running RH Linux 6.2.
A. pure memcpy() timings (10000 runs per line)
#bytes average minimum
0 102 102 #bytes...number of equal bytes
1 107 107 average...arithmetic average
2 113 113 minimum...minimal value
3 118 118
4 123 123
5 127 127
6 132 132
7 150 137
8 141 141
9 145 145
10 151 151
11 155 155
12 159 159
13 171 171
14 175 175
15 179 179
16 146 146
B. minimalistic XOpenDisplay() timings (100000 runs per line)
#bytes average minimum
0 68459 46202
1 71950 39300
2 70821 39830
3 72978 46287
4 69965 39671
5 76345 39763
6 74225 46337
7 74782 46346
8 72634 40095
9 71672 45933
10 71245 40109
11 71815 39472
12 70889 39875
13 71629 40195
14 73565 40026
15 77627 39237
16 73978 39935
C. the programs I used:
memcmp.c (memcmp() test):
<--snip-->
#include <stdio.h>
#include <string.h>
/* taken from Linux kernel */
#define rdtsc(low, high) \
__asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high))
#define sub64(xlow, xhigh, ylow, yhigh) \
__asm__("subl %2,%0\n\tsbbl %3,%1" \
:"=a" (xlow), "=d" (xhigh) \
:"g" (ylow), "g" (yhigh), \
"0" (xlow), "1" (xhigh))
unsigned long
measure(const void *p1, const void *p2, size_t s)
{
unsigned long startlo, starthi;
unsigned long endlo, endhi;
rdtsc(startlo, starthi);
memcmp(p1, p2, s);
rdtsc(endlo, endhi);
sub64(endlo, endhi, startlo, starthi);
if (endhi) return ~0; /* argh */
return endlo;
}
int
main()
{
char a[16], b[16];
int i, j, count;
unsigned long ta, tmin, t1;
for (j = 0; j < sizeof(a); ++j)
a[j] = j;
for (i = 0; i <= sizeof(a); ++i) {
for (j = 0; j < i; ++j) b[j] = a[j];
for (; j < sizeof(a); ++j) b[j] = ~a[j];
count = 10000;
ta = 0; tmin = ~0UL;
for (j = 0; j < count; ) {
t1 = measure(a, b, sizeof(a));
if (t1 >= ~0UL/count) continue;
if (t1 < tmin) tmin = t1;
ta += t1;
++j;
}
printf("%2d %10lu %10lu\n", i, ta/count, tmin);
}
return 0;
}
<--snip-->
cookie.c (X11 test):
<--snip-->
#include <stdio.h>
#include <string.h>
#include <sys/uio.h>
#include <sys/socket.h>
#include <sys/un.h>
/* taken from Linux kernel */
#define rdtsc(low, high) \
__asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high))
#define sub64(xlow, xhigh, ylow, yhigh) \
__asm__("subl %2,%0\n\tsbbl %3,%1" \
:"=a" (xlow), "=d" (xhigh) \
:"g" (ylow), "g" (yhigh), \
"0" (xlow), "1" (xhigh))
unsigned long
measure(int dpy, const char *cookie)
{
unsigned long startlo, starthi;
unsigned long endlo, endhi;
int s, r;
char c;
struct iovec vec[4];
struct sockaddr_un sun;
vec[0].iov_base = "l\0\v\0\0\0\22\0\20\0\0\0";
vec[0].iov_len = 12;
vec[1].iov_base = "MIT-MAGIC-COOKIE-1";
vec[1].iov_len = 18;
vec[2].iov_base = "\0\0";
vec[2].iov_len = 2;
vec[3].iov_base = (char *) cookie;
vec[3].iov_len = 16;
s = socket(AF_UNIX, SOCK_STREAM, 0);
if (s < 0) return ~0UL;
sun.sun_family = AF_UNIX;
sprintf(sun.sun_path, "/tmp/.X11-unix/X%d", dpy);
r = connect(s, (struct sockaddr *) &sun, sizeof(sun));
if (r < 0) { close(s); return ~0UL; }
rdtsc(startlo, starthi);
(void) writev(s, vec, 4);
(void) read(s, &c, 1);
rdtsc(endlo, endhi);
sub64(endlo, endhi, startlo, starthi);
close(s);
if (endhi) return ~0UL; /* argh */
return endlo;
}
int
main()
{
char a[16], b[16];
int i, j, count;
unsigned long ta, tb, tmin, t1;
for (j = 0; j < sizeof(a); ++j)
a[j] = j;
for (i = 0; i <= sizeof(a); ++i) {
for (j = 0; j < i; ++j) b[j] = a[j];
for (; j < sizeof(a); ++j) b[j] = ~a[j];
count = 100000;
ta = tb = 0; tmin = ~0UL;
for (j = 0; j < count; ) {
t1 = measure(99, b);
if (t1 == ~0UL) continue;
if (t1 < tmin) tmin = t1;
tb += t1 % count;
if (tb >= count) { ++ta; tb -= count; }
ta += t1 / count;
++j;
}
printf("%2d %10lu %10lu\n", i, ta, tmin);
}
return 0;
}
<--snip-->
X11 test helper script:
<--snip-->
#!/bin/sh
rm -f auth
export XAUTHORITY=auth
xauth add kunhuta.dcit.cz/unix:99 MIT-MAGIC-COOKIE-1 \
0102030405060708090a0b0c0d0e0f10
xauth add kunhuta.dcit.cz:99 MIT-MAGIC-COOKIE-1 \
0102030405060708090a0b0c0d0e0f10
Xvfb :99 -auth auth >/dev/null 2>&1 &
xvfb=$!
xmessage -display :99 x & # to prevent Xvfb resets
./cookie
kill $xvfb
<--snip-->
--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."
This archive was generated by hypermail 2b30 : Mon May 21 2001 - 21:06:17 PDT