Is there a hidden channel in X authentication?

[Klaus Frank <klausf () Pool Informatik RWTH-Aachen DE>]

X servers authenticate their clients by means of the MIT-MAGIC-COOKIE-1
protocol. It is assumed that the duration of a brute force attack grows
exponentially with the length of the magic cookie. Hence, a cookie length
of 16 is considered secure enough.

However, at least one X server uses the memcmp() library function to
compare the stored cookie with the cookie sent by the client. This func-
tion is optimized for speed. In particular, the execution time of memcmp()
is proportional to the position of the first non-matching byte in the two
cookies.

This means that the duration of the handling of an connection attempt by
the X server differs slightly depending on the amount of correct bytes at
the beginning of the magic cookie. I was wondering if this could be
exploited by an attacker who is able to measure these differences.

Something similar could be true about the interval from sending a connection
setup request to receiving the reply that contains the success flag. There
are additional random delays from code running in kernel mode (context switch
and network stack, for example).

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?

If yes, each byte of the magic cookie can be guessed by trying the already
known prefix with one of the 256 candidate bytes (and enough more to make
up 16 bytes) and comparing their time. (If the length of the cookie isn't 16,
it will be rejected before calling memcmp(); the length could be tested by
brute force, too.) The duration of an brute force attack may be unrealistic
long, but it could be proportional to the length of the magic cookie...

Let's start with the assumption that the machine of the X server isn't busy
and that an attacker already has access to an account of it.

Klaus Frank