RE: Is there a hidden channel in X authentication?

[Michael Wojcik <Michael.Wojcik () merant com>]

> From: Klaus Frank [mailto:klausf () Pool Informatik RWTH-Aachen DE]
> Sent: Thursday, May 17, 2001 5:01 AM

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

A timing attack against memcmp - nice idea.  I suspect it may be difficult
to use in practice, particularly across a network, and particularly with a
small length like 16; cache effects would easily dominate the memcmp time,
for example.  And AFAIK pretty much all modern general-purpose CPUs compare
multiple bytes per cycle.  That would make the memcmp time proportional to
length/n (where n is the number of bytes compared per cycle and / is integer
division).  Alignment will affect memcmp implementations that do multibyte
compares too, which might throw the results off.

That said, I just ran a little test on a SPARCstation 10 here (I know, not
the most modern of CPUs), and memcmp does appear to be linearly proportional
to the length of the matching prefix.  (I did 1e6 iterations at each length
from 0 to 16, where 16 was the comparison length.  The tests at length 16 -
ie. a successful match - were slightly faster than the tests at length 15,
interestingly.)  Whether the difference is detectable with tools available
to the attacker with only one comparision rather than one million is another
matter.

In any case, it's easy enough to mask the time by using a hand-coded
comparison loop that always compares all the bytes and sets a flag if any of
them differ.

Michael Wojcik             michael.wojcik () merant com
MERANT
Department of English, Miami University