Re: [fossil-users] Protection against timing attacks
On Thu, Sep 29, 2011 at 8:00 PM, Dmitry Chestnykh
wrote:
> The more eyes the better, as it touches login code.
> ...COMPARE("A", "PASSWORD") returns FALSE in 0.1 msec, but
> COMPARE("P", "PASSWORD") returns FALSE in 0.3 msec, because it did
> two comparisons:
>
Given the relatively high overhead fossil has when it opens a db or runs a
query, and network latency, i cannot imagine that someone could accurately
time the difference of a memcmp() operation on 8 or 10 bytes. The number of
factors involved before and after COMPARE is called are just too great. As
was written in the post about sha1 collisions someone linked to earlier: the
chances are higher that all of the members of your dev team will be killed
by wolves in separate incidences on the same night.
If ALL fossil did was accept a request and run a memcmp on one GET
parameter, i might believe it, but given the huge number of variables,
especially network latency, CGI startup time, and db open/query time, the
only way i'll believe that these steps are necessary is if someone actually
breaks a password this way.
All that said - i wouldn't object to this being added (as if my vote
matters! ;), i just think it's overly paranoid.
--
- stephan beal
http://wanderinghorse.net/home/stephan/
___
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Thu, Sep 29, 2011 at 08:15:55PM +0200, Stephan Beal wrote:
> On Thu, Sep 29, 2011 at 8:00 PM, Dmitry Chestnykh
> wrote:
>
> > The more eyes the better, as it touches login code.
> > ...COMPARE("A", "PASSWORD") returns FALSE in 0.1 msec, but
> > COMPARE("P", "PASSWORD") returns FALSE in 0.3 msec, because it did
> > two comparisons:
> >
>
> All that said - i wouldn't object to this being added (as if my vote
> matters! ;), i just think it's overly paranoid.
I totally agree. I don't object, but I consider this either paranoid or simply
thinking an excuse to play with fossil authentication code. :)
Regards.
___
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Sep 29, 2011, at 20:15 , Stephan Beal wrote: > Given the relatively high overhead fossil has when it opens a db or runs a > query, and network latency, i cannot imagine that someone could accurately > time the difference of a memcmp() operation on 8 or 10 bytes. The number of > factors involved before and after COMPARE is called are just too great. As > was written in the post about sha1 collisions someone linked to earlier: the > chances are higher that all of the members of your dev team will be killed by > wolves in separate incidences on the same night. I posted a link about this concern: http://rdist.root.org/2010/01/07/timing-independent-array-comparison/ "The other misconception is that jitter is too great to get anything useful out of the measurements, especially in a network. There is an excellent paper by Crosby and Wallach* that debunks this myth by carefully analyzing noise and its causes as well as how to filter it. They conclude that an attacker can reliably detect processing differences as low as 200 nanoseconds on a LAN or 30 microseconds on a WAN given only 1000 measurements. If your server is hosted somewhere an attacker can also buy rackspace, then you are vulnerable to LAN timing attacks." *) http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf -- Dmitry Chestnykh ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Thu, Sep 29, 2011 at 09:07:37PM +0200, Stephan Beal wrote: > On Thu, Sep 29, 2011 at 8:57 PM, Dmitry Chestnykh > wrote: > > > I posted a link about this concern: > > http://rdist.root.org/2010/01/07/timing-independent-array-comparison/ > > > So why not simply add the following logic to server mode: > > A) fetch config option "add-random-sleep" (integer, default=0) > B) if ((A)>0) AND user is nobody, sleep for random 1..(A) ms. (This attack > would seem to be useless for anyone but the nobody user. If you're logged > in, you've got your password, and anonymous gets a random password). > I think that you are adding white noise. It can be averaged out. Isn't the code from dmitry more reliable and simple? Well, if someone has studied those attacks, and the code by dmitry looks fine and works based on some heavier studies than our first thoughts on that, let's use it. No? Regards, Lluís. ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
> So why not simply add the following logic to server mode: > > A) fetch config option "add-random-sleep" (integer, default=0) > B) if ((A)>0) AND user is nobody, sleep for random 1..(A) ms. (This attack > would seem to be useless for anyone but the nobody user. If you're logged in, > you've got your password, and anonymous gets a random password). Point 2 on that linked article :-) Random numbers have some distribution, most commonly, uniform. Given enough measurements, you can get rid of randomness. -- Dmitry Chestnykh ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Thu, Sep 29, 2011 at 8:57 PM, Dmitry Chestnykh wrote: > I posted a link about this concern: > http://rdist.root.org/2010/01/07/timing-independent-array-comparison/ So why not simply add the following logic to server mode: A) fetch config option "add-random-sleep" (integer, default=0) B) if ((A)>0) AND user is nobody, sleep for random 1..(A) ms. (This attack would seem to be useless for anyone but the nobody user. If you're logged in, you've got your password, and anonymous gets a random password). That variance is far, far higher than: to filter it. They conclude that an attacker can reliably detect processing > differences as low as 200 nanoseconds on a LAN or 30 microseconds on a WAN > given only 1000 measurements. or am i missing an important detail (that can't be ruled out!)? -- - stephan beal http://wanderinghorse.net/home/stephan/ ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
2011/9/29 Lluís Batlle i Rossell > Well, if someone has studied those attacks, and the code by dmitry looks > fine > and works based on some heavier studies than our first thoughts on that, > let's > use it. No? > i can't object, i just think it's paranoid :). -- - stephan beal http://wanderinghorse.net/home/stephan/ ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 09/29/2011 07:57 PM, Dmitry Chestnykh wrote: > I posted a link about this concern: > http://rdist.root.org/2010/01/07/timing-independent-array-comparison/ This is also why introducing a random delay to mask the timing doesn't really solve the problem (but it does make the attacker need more samples to average it out)! People who make crypto smartcards have to really worry about issues like this, as the smartcard will be in the hands of attackers, who will feed it multiple carefully-crafted authentication requests while monitoring response time, power consumption, spikes on the power lines caused by transistor switching... and maybe even feed the same request through again and again while bombarding the card with radiation to try and cause random bit flips within its circuitry and seeing how this affects the result. ABS - -- Alaric Snell-Pym http://www.snell-pym.org.uk/alaric/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk6Fj0EACgkQRgz/WHNxCGpR4gCfbcjC9EeCTz9KNobUEl+o+Q3B n/IAn0qXg0EUwAiGC9zAO5o5Quhm63B2 =mEdU -END PGP SIGNATURE- ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
> 2011/9/29 Lluís Batlle i Rossell
> Well, if someone has studied those attacks, and the code by dmitry looks fine
> and works based on some heavier studies than our first thoughts on that, let's
> use it. No?
>
> i can't object, i just think it's paranoid :).
Well, it is paranoid, yes :-) I'm overly paranoid about everything concerning
security. Evidence: it was unnecessary to do constant-time comparison of hashes
in xfer.c.
I'm mostly concerted about cookies, as it's impossible to time non-plain-text
passwords -- the attacker simply cannot supply passwords which, when hashed,
have a few bytes of hash modified (that is, when you supply "password", the
server looks for "5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8" in the database,
it's impossible [at least now, with SHA-1] to supply such password which hash
has, say, "5baa61" in the beginning, but a different ending).
However, due to the use of plain-text passwords in the old versions and
compatibility with them, it is currently possible to supply password hash (if
you know project-id) instead of the password:
uid = db_int(0,
"SELECT uid FROM user"
" WHERE login=%Q"
" AND length(cap)>0 AND length(pw)>0"
" AND login NOT IN ('anonymous','nobody','developer','reader')"
" AND (pw=%Q OR pw=%Q)",
zUsername, zPasswd, zSha1Pw
);
Once we get rid of plain-text passwords, we no longer need constant-time
comparison functions in password-handling code. That leaves cookies, which are
just a 25-byte random blob + project-code + login, and Fossil searches for that
blob in database.
--
Dmitry Chestnykh
___
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Fri, Sep 30, 2011 at 12:43 PM, Dmitry Chestnykh wrote: > However, due to the use of plain-text passwords in the old versions and > compatibility with them, it is currently possible to supply password hash > (if you know project-id) instead of the password: > if i'm not mistaken you need both the project ID and the captcha secret (which is random by default). Once we get rid of plain-text passwords, we no longer need constant-time > comparison functions in password-handling code. That leaves cookies, which > are just a 25-byte random blob + project-code + login, and Fossil searches > for that blob in database. > To allow multiple logins for a given user (required for JSON usability reasons) i will eventually need to move the login entries into a separate table (currently stored in the user table). i will wait on any pending changes from you in this area before i do that, since we will probably touch the same code here. -- - stephan beal http://wanderinghorse.net/home/stephan/ ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
I think this is a good patch and that it should be merged into trunk. On Fri, Sep 30, 2011 at 7:07 AM, Stephan Beal wrote: > On Fri, Sep 30, 2011 at 12:43 PM, Dmitry Chestnykh < > dmi...@codingrobots.com> wrote: > >> However, due to the use of plain-text passwords in the old versions and >> compatibility with them, it is currently possible to supply password hash >> (if you know project-id) instead of the password: >> > > if i'm not mistaken you need both the project ID and the captcha secret > (which is random by default). > > Once we get rid of plain-text passwords, we no longer need constant-time >> comparison functions in password-handling code. That leaves cookies, which >> are just a 25-byte random blob + project-code + login, and Fossil searches >> for that blob in database. >> > > To allow multiple logins for a given user (required for JSON usability > reasons) i will eventually need to move the login entries into a separate > table (currently stored in the user table). i will wait on any pending > changes from you in this area before i do that, since we will probably touch > the same code here. > > -- > - stephan beal > http://wanderinghorse.net/home/stephan/ > > ___ > fossil-users mailing list > fossil-users@lists.fossil-scm.org > http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users > > -- D. Richard Hipp d...@sqlite.org ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
> I think this is a good patch and that it should be merged into trunk. Is it too early to get rid of plain-text password support? I think hashed passwords appeared about 1.5 years ago. If we remove it, we can leave "pw=%Q", I think. The only code left susceptible to timing attacks will be for cookie handling. -- Dmitry Chestnykh ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Fri, Sep 30, 2011 at 6:43 AM, Dmitry Chestnykh wrote: > I'm mostly concerted about cookies, as it's impossible to time non-plain-text > passwords -- the > attacker simply cannot supply passwords which, when hashed, have a few bytes > of hash > modified (that is, when you supply "password", the server looks for > "5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8" in the database, it's impossible > [at least > now, with SHA-1] to supply such password which hash has, say, "5baa61" in the > beginning, > but a different ending). Actually, you can do this with a hash. When it comes to comapring 2 hashes, they are still strings of charcters. If anything, the timing attack would save even more time since, for purposes of camparing 2 strings, the hash is just a much longer password. The question then is, is the hash long enough to make the timing attack impractical? ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
> Actually, you can do this with a hash. When it comes to comapring 2
> hashes, they are still strings of charcters. If anything, the timing
> attack would save even more time since, for purposes of camparing 2
> strings, the hash is just a much longer password. The question then
> is, is the hash long enough to make the timing attack impractical?
The attacker cannot supply hash, he supplies password. To do timing attack, the
attacker have to find a such string, for which the hash has a few bytes changed.
For example, say, our password is "bird", and we store sha1("bird") in the
database: 9cba2b7ebbf67f6e455af28f8445796e20ca288f.
When a user supplies password, we hash it and compare with the stored hash.
Let's image that the attacker supplies password "ocelot".
Server does sha1("ocelot") = 1d735415a0c1e05302657bb6d916f3bcd7a80385
and compares it with the stored value:
9cba2b7ebbf67f6e455af28f8445796e20ca288f !=
1d735415a0c1e05302657bb6d916f3bcd7a80385
This comparison is not constant-time, so the attacker notices that the first
byte is incorrect, and continues guesing by providing the next password: "lion".
sha1("lion") = 972b2f351f9b17a5f49a14a90fcd8a72b0eaecb4
9cba2b7ebbf67f6e455af28f8445796e20ca288f !=
972b2f351f9b17a5f49a14a90fcd8a72b0eaecb4
But now it took server a bit longer to calculate the result (9=9, c != 7). The
attacker notices the short response time, so he's confident he guessed that the
first byte is "9". Now, to continue attack he needs to find such password, for
which the hash starts with "9"…
And this is where it's practically impossible to continue.
(Actually, one hash byte is the two hex numbers, but anyway).
This is for logins. But cookies currently compare hashes, not hash and a string
hashed on the server, so they are timeable.
--
Dmitry Chestnykh
___
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Fri, Sep 30, 2011 at 2:27 PM, Dmitry Chestnykh wrote: > The attacker cannot supply hash, he supplies password. To do timing attack, > the > attacker have to find a such string, for which the hash has a few bytes > changed. You and I seem to be talking about different use cases, There are scenarios where both the client and server generate hashes. The client sends its has to the server and the server compares the hashes. Of course, another protection against attacks is to limit the time window before a whole new set of hashes needs to be computed. ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
Re: [fossil-users] Protection against timing attacks
On Oct 1, 2011, at 9:24 , Ron Wilson wrote: > On Fri, Sep 30, 2011 at 2:27 PM, Dmitry Chestnykh > wrote: >> The attacker cannot supply hash, he supplies password. To do timing attack, >> the >> attacker have to find a such string, for which the hash has a few bytes >> changed. > > You and I seem to be talking about different use cases, There are > scenarios where both the client and server generate hashes. The client > sends its has to the server and the server compares the hashes. This is correct, yes. -- Dmitry Chestnykh ___ fossil-users mailing list fossil-users@lists.fossil-scm.org http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
