Dear archeologists,

Please review changes in the following branch:

http://www.fossil-scm.org/index.html/timeline?r=dmitry-security

The more eyes the better, as it touches login code.

I try to protect against timing attacks on login, cookies, and sync by using 
the constant-time comparison function.

What do these attacks do? Basically, they try to guess passwords/cookies by 
measuring how long it took the server to respond to the wrong result. For 
example, we have the following password stored in the database (let's forget 
about hashes for now):

"PASSWORD"

The attacker begins guessing by sending the following value:

"AAAAAAAAA"

The server compares it with the stored password:

  if COMPARE("AAAAAAAAA", "PASSWORD")  == TRUE then
     success
  else
     failure

When this COMPARE function is implemented like memcpy/strcpy, that is, compares 
values byte-by-byte, but when sees the first wrong result ('A' != 'P'), it 
immediately returns FALSE, it turns out, it is possible to time the result of 
such comparisons to make better guesses.

For example,

COMPARE("AAAAAAAAA", "PASSWORD") returns FALSE in 0.1 msec, but
COMPARE("PAAAAAAAA", "PASSWORD") returns FALSE in 0.3 msec, because it did two 
comparisons:

'P' == 'P'
'A' == 'A'
'A' != 'S'

Now the attacker knows that the first two bytes are correct.

To prevent such attacks, one should use a constant-time comparison function, 
which always compares _each_ byte, and returns result only after all bytes have 
been compared.

More information:

http://codahale.com/a-lesson-in-timing-attacks/
http://rdist.root.org/2010/01/07/timing-independent-array-comparison/
http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/

Examples of constant-time comparison functions written by crypto experts
(basically, they are the same):

http://golang.org/src/pkg/crypto/subtle/constant_time.go?s=503:544#L2
http://code.google.com/p/spiped/source/browse/trunk/lib/crypto/crypto_verify_bytes.c
https://github.com/jeremywohl/nacl/blob/master/crypto_verify/32/ref/verify.c

Oh, and there's no need to panic, this is a difficult and (yet) unusual attack 
;-)

--
Dmitry Chestnykh

_______________________________________________
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users

Reply via email to