Re: Is there a hidden channel in X authentication?

[Pavel Kankovsky <peak () bobanek nowhere cz>]

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."