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
This archive was generated by hypermail 2b30 : Thu May 17 2001 - 09:43:02 PDT