const time authentication in bozohttpd

[shm]

Hello,

bozohttpd currently checks password using strcmp, which may leak information
about compared data, my patch [1] introduces following countermeasures:

- username / password is now compared using introduced timing safe function
(which run time depends on the known string)
- remove username/password from the memory as it's no longer needed
- avoid username leak by checking all records in the auth file (previously
when we found valid username but user sent invalid password we break from
the loop, so other records from the .htpassword weren't checked, thus an
attacker basing on response time could be able to figure out if username
exists) by checking all records in the file.

This might sounds a bit paranoid, but I've got real world example that the
problem really exists:

192.168.1.105 is a bozohttpd (built from HEAD):

executed by: : /usr/libexec/httpd -d -c cgi-bin -bf -X -I 8080 .
192.168.1.105

***@netbsd-dev ~/www $ cat .htpasswd
bla:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test2:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test3:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test4:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test6:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzO

(password is bla)

Response times from the machine in the same LAN:

For non-existing user:

$ for ((i=0;i<100;i++)) ; do time curl
http://notexists:***@192.168.1.105:8080/ ; done 2> /dev/stdout | grep real |
sort | uniq -c
1 real 0m0.016s
1 real 0m0.017s
3 real 0m0.018s
13 real 0m0.019s
50 real 0m0.020s
4 real 0m0.021s
1 real 0m0.022s
1 real 0m0.023s
2 real 0m0.024s
5 real 0m0.025s
7 real 0m0.030s
3 real 0m0.031s
1 real 0m0.033s
1 real 0m0.034s
2 real 0m0.035s
2 real 0m0.036s
1 real 0m0.037s
1 real 0m0.040s
1 real 0m0.045s

For existing user:

$ for ((i=0;i<100;i++)) ; do time curl http://test3:***@192.168.1.105:8080/ ;
done 2> /dev/stdout | grep real | sort | uniq -c
2 real 0m0.086s
3 real 0m0.087s
3 real 0m0.088s
14 real 0m0.089s
43 real 0m0.090s
11 real 0m0.091s
2 real 0m0.092s
2 real 0m0.093s
2 real 0m0.094s
2 real 0m0.095s
3 real 0m0.096s
1 real 0m0.097s
1 real 0m0.098s
1 real 0m0.101s
1 real 0m0.102s
1 real 0m0.104s
5 real 0m0.106s
1 real 0m0.108s
1 real 0m0.115s
1 real 0m0.130s

For bozohttpd with my patch results are as follows:

For not-existing user:

***@selene ~ $ for ((i=0;i<100;i++)) ; do time curl
http://notexists:***@192.168.1.105:8080/ ; done 2> /dev/stdout | grep real |
sort | uniq -c
2 real 0m0.087s
3 real 0m0.088s
13 real 0m0.089s
51 real 0m0.090s
10 real 0m0.091s
2 real 0m0.093s
2 real 0m0.094s
2 real 0m0.095s
1 real 0m0.096s
1 real 0m0.097s
7 real 0m0.100s
1 real 0m0.102s
1 real 0m0.104s
1 real 0m0.106s
1 real 0m0.114s
1 real 0m0.115s
1 real 0m0.268s


For existing user:

***@selene ~ $ for ((i=0;i<100;i++)) ; do time curl
http://bla:***@192.168.1.105:8080/ ; done 2> /dev/stdout | grep real | sort |
uniq -c
1 real 0m0.087s
12 real 0m0.089s
54 real 0m0.090s
11 real 0m0.091s
2 real 0m0.092s
2 real 0m0.093s
1 real 0m0.094s
2 real 0m0.096s
5 real 0m0.100s
2 real 0m0.101s
1 real 0m0.104s
5 real 0m0.105s
1 real 0m0.115s
1 real 0m0.120s
----

Do you have any thoughts on this? I'd like to commit [1], if there is no
objections.

Kind Regards,
shm@

[1] http://netbsd.org/~shm/patches/bozohttpd/consttime_auth-bozo.diff

[Taylor R Campbell]

Date: Wed, 25 Jun 2014 07:35:12 +0000
From: shm <***@netbsd.org>

bozohttpd currently checks password using strcmp, which may leak information
about compared data, my patch [1] introduces following countermeasures:

A couple general comments first:

- username / password is now compared using introduced timing safe function
(which run time depends on the known string)

The consttime_strcmp you have written does not satisfy the properties
you documented it to have. You say it should not leak anything about
the `unknown' string including its length, but you pass the `unknown'
string to strlen, which runs in time proportional to the length of the
string.

It also doesn't behave like strcmp, in that it returns equal/not-equal
rather than less/equal/greater. For this reason, we chose to adopt
the name consttime_memequal rather than consttime_memcmp or
consttime_bcmp.

- remove username/password from the memory as it's no longer needed

It seems to me there are likely to be other places in memory where
these get stored, particularly stdio buffers. You could use a
separate process to do this, but you should first identify the threat
model that this is defending against, which is not clear to me.

For example, if your threat model includes heartbleed, then you almost
certainly need a separate process. If your threat model includes
remote code execution in the bozohttpd process, even that won't help.

- avoid username leak by checking all records in the auth file (previously
when we found valid username but user sent invalid password we break from
the loop, so other records from the .htpassword weren't checked, thus an
attacker basing on response time could be able to figure out if username
exists) by checking all records in the file.

This seems to be the part you're actually worried about: you want to
prevent an attacker who can make arbitrary HTTP requests over the
network from enumerating the valid usernames.

The loop, as you have written it, is not going to be constant-time,
because it has data-dependent branches in it (if (valid_pass == NULL),
for example).

Here's how you might rewrite it to avoid that. Since you have a
maximum username length, you can use consttime_memequal here. The
call to strlen should run in time independent of the requst assuming
that crypt(3) is sensible (which is an assumption worth scrutinizing,
since crypt(3) is not a shining paragon of crypto engineering).

char htpasswd_user[BUFSIZ], *htpasswd_pass, *hash;
char request_user[BUFSIZ];
unsigned ok = 0;

(void)memset(request_user, 0, sizeof request_user);
(void)strlcpy(request_user, request->hr_authuser, sizeof request_user);
while (fgets(htpasswd_user, sizeof htpasswd_user, fp) != NULL) {
...parse into htpasswd_user and htpasswd_pass and pad htpasswd_user...
hash = crypt(request->hr_authpass, htpasswd_pass);
ok |= consttime_memequal(htpasswd_user, request_user, BUFSIZ) &
consttime_memequal(hash, htpasswd_pass, strlen(hash) + 1);
}

return ok? 0 : bozo_http_error(httpd, 401, "bad auth");

As a minor aside, this lets you have multiple passwords for one
username, which the previous code did not allow -- it required the
first password for any given username. With a little extra work you
could restore the old semantics, but I'm not sure it matters.

[shm]

Thanks for your comments. My goal was to make it const-time between subsequent
requests. You're right that my solution is confusing. I'll try to come up with
something better soon.

Kind Regards,
shm@

[Terry Moore]

Perhaps this is a silly comment; but wouldn't it be easier to simply time
stamp the incoming request, and then spin for any authentication failure
until a suitable fixed time has elapsed after the inbound arrival? Or are
you worried about local cache-interference attacks as well?

--Terry

-----Original Message-----
Sent: Wednesday, June 25, 2014 02:35
Subject: const time authentication in bozohttpd
Hello,
bozohttpd currently checks password using strcmp, which may leak information
- username / password is now compared using introduced timing safe function
(which run time depends on the known string)
- remove username/password from the memory as it's no longer needed
- avoid username leak by checking all records in the auth file (previously
when we found valid username but user sent invalid password we break from
the loop, so other records from the .htpassword weren't checked, thus an
attacker basing on response time could be able to figure out if username
exists) by checking all records in the file.
This might sounds a bit paranoid, but I've got real world example that the
executed by: : /usr/libexec/httpd -d -c cgi-bin -bf -X -I 8080 .
192.168.1.105
bla:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test2:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test3:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test4:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzP
test6:$sha1$22983$EVXICHNn$wnulZLsEKwnbZTwGRD0vi/8n5rzO
(password is bla)
$ for ((i=0;i<100;i++)) ; do time curl
sort | uniq -c
1 real 0m0.016s
1 real 0m0.017s
3 real 0m0.018s
13 real 0m0.019s
50 real 0m0.020s
4 real 0m0.021s
1 real 0m0.022s
1 real 0m0.023s
2 real 0m0.024s
5 real 0m0.025s
7 real 0m0.030s
3 real 0m0.031s
1 real 0m0.033s
1 real 0m0.034s
2 real 0m0.035s
2 real 0m0.036s
1 real 0m0.037s
1 real 0m0.040s
1 real 0m0.045s
$ for ((i=0;i<100;i++)) ; do time curl
done 2> /dev/stdout | grep real | sort | uniq -c
2 real 0m0.086s
3 real 0m0.087s
3 real 0m0.088s
14 real 0m0.089s
43 real 0m0.090s
11 real 0m0.091s
2 real 0m0.092s
2 real 0m0.093s
2 real 0m0.094s
2 real 0m0.095s
3 real 0m0.096s
1 real 0m0.097s
1 real 0m0.098s
1 real 0m0.101s
1 real 0m0.102s
1 real 0m0.104s
5 real 0m0.106s
1 real 0m0.108s
1 real 0m0.115s
1 real 0m0.130s
sort | uniq -c
2 real 0m0.087s
3 real 0m0.088s
13 real 0m0.089s
51 real 0m0.090s
10 real 0m0.091s
2 real 0m0.093s
2 real 0m0.094s
2 real 0m0.095s
1 real 0m0.096s
1 real 0m0.097s
7 real 0m0.100s
1 real 0m0.102s
1 real 0m0.104s
1 real 0m0.106s
1 real 0m0.114s
1 real 0m0.115s
1 real 0m0.268s
uniq -c
1 real 0m0.087s
12 real 0m0.089s
54 real 0m0.090s
11 real 0m0.091s
2 real 0m0.092s
2 real 0m0.093s
1 real 0m0.094s
2 real 0m0.096s
5 real 0m0.100s
2 real 0m0.101s
1 real 0m0.104s
5 real 0m0.105s
1 real 0m0.115s
1 real 0m0.120s
----
Do you have any thoughts on this? I'd like to commit [1], if there is no
objections.
Kind Regards,
[1] http://netbsd.org/~shm/patches/bozohttpd/consttime_auth-bozo.diff

[shm]

Post by Terry Moore
Perhaps this is a silly comment; but wouldn't it be easier to simply time
stamp the incoming request, and then spin for any authentication failure
until a suitable fixed time has elapsed after the inbound arrival? Or are
you worried about local cache-interference attacks as well?

It might be a solution, but I don't see any reasonable implementation, i.e.
it would be hard to guess how long the code will run. I'm not worried about
local cache-interference, I want to countermeasure attackers from the remote.

Kind Regards,
shm@

[Terry Moore]

Here's how it's typically done.

Choose a time (say one second) (call this delta_t). Get the system clock
before you start authentication (call this t_mark). After any failure on the
authentication path, delay responding until t_now >= t_mark+delta_t. (The
overflow-safe way to compute this (t_now - t_mark >= delta_t).

You can delay by CPU spins, or by using one of the apis that let you yield
the CPU. If you're spinning, and 1-second granularity is acceptable, you
can just use the time(3) function, as long as delta is 2 or greater. (I
wouldn't use a delta of one with any time-dleay algorithm because you're
generally only guaranteed that the delay will be in the range (n-1, n)
units.)

Delaying the response to an authentication failure also slows down some
brute-force attacks -- those which don't try to do things in parallel with
multiple connections.

Best regards,
--Terry

-----Original Message-----
Sent: Wednesday, June 25, 2014 10:10
To: Terry Moore
Subject: Re: const time authentication in bozohttpd

Post by Terry Moore
Perhaps this is a silly comment; but wouldn't it be easier to simply time
stamp the incoming request, and then spin for any authentication failure
until a suitable fixed time has elapsed after the inbound arrival? Or are
you worried about local cache-interference attacks as well?

It might be a solution, but I don't see any reasonable implementation, i.e.
it would be hard to guess how long the code will run. I'm not worried about
local cache-interference, I want to countermeasure attackers from the remote.
Kind Regards,

[J. Lewis Muir]

Post by Terry Moore
Here's how it's typically done.
Choose a time (say one second) (call this delta_t). Get the system
clock before you start authentication (call this t_mark). After any
failure on the authentication path, delay responding until t_now >=
t_mark+delta_t. (The overflow-safe way to compute this (t_now -
t_mark >= delta_t).

Hi, Terry.

How do you choose delta_t? Don't you have to be sure that delta_t
is always greater than or equal to the time needed to authenticate?
(Otherwise the times for a successful authentication and an unsuccessful
authentication could differ thereby leaking information, right?) How
can you choose delta_t in a portable way?

I thought the way authentication is typically done is to be sure you
do the same amount of work for both a successful authentication and an
unsuccessful authentication. Then you don't need to choose a delta_t.
Authentication takes however long it takes, but the key property is that
it takes the same amount of time regardless of whether it is successful
or unsuccessful.

Lewis

[Terry Moore]

Well, if authentication succeeds, then the user is in, and has successfully
guessed a login and password (and it ostensibly an "authorized user").

The problem I thought the patch was addressing is that there are (at least)
two response paths.

1) Remote system failed quickly -- the username is invalid
2) Remote system failed slowly -- the user name is valid, but the password
is invalid.

If pattern 2 is observed, you've successfully guessed a name, and you can
switch to guessing passwords (the search space is much reduced -- and
knowledge of a valid username itself may have value for chained attacks,
perhaps on related systems or subsystems, or even for phishing or other
social engineering attacks).

Of course, I'm making an assumption, because this wasn't explicitly stated
in the original mail. But that looks like a threat to me. This is analogous
to returning a different error message based on whether the username is
invalid, as opposed to if the username is valid but the password is invalid.
That's been known to be a bad idea for at least 30 years.

By delaying in the "non-authenticated case", you can deny the adversary the
knowledge of whether it's case 1 or case 2.

The delay time can be any time you like, as long as the minimum delay is
greater than the longer of path (1) and path (2). You are going to disclose
the fact that user+password are invalid, in any case; but you should not
disclose more info than that.

Randomizing the delay (as mind@ suggested) will disguise the algorithm
you're using to hide the info, but the basic idea is to hide the info. I'm
not sure what else randomizing the delay will add (defense-wise) but I
imagine that I'm overlooking something.

It's also possible that I've totally misunderstood the original message! But
certainly, it's a bad idea to disclose whether you took path (1) or path (2)

Best regards,
--Terry

-----Original Message-----
Sent: Wednesday, June 25, 2014 15:04
To: Terry Moore
Subject: Re: const time authentication in bozohttpd

Post by Terry Moore
Here's how it's typically done.
Choose a time (say one second) (call this delta_t). Get the system
clock before you start authentication (call this t_mark). After any
failure on the authentication path, delay responding until t_now >=
t_mark+delta_t. (The overflow-safe way to compute this (t_now -
t_mark >= delta_t).

Hi, Terry.
How do you choose delta_t? Don't you have to be sure that delta_t
is always greater than or equal to the time needed to authenticate?
(Otherwise the times for a successful authentication and an unsuccessful
authentication could differ thereby leaking information, right?) How
can you choose delta_t in a portable way?
I thought the way authentication is typically done is to be sure you
do the same amount of work for both a successful authentication and an
unsuccessful authentication. Then you don't need to choose a delta_t.
Authentication takes however long it takes, but the key property is that
it takes the same amount of time regardless of whether it is successful
or unsuccessful.
Lewis

[Terry Moore]

[Apologies for using wrong message-quoting style. Resending for consistency]

Post by J. Lewis Muir
How do you choose delta_t? Don't you have to be sure that delta_t
is always greater than or equal to the time needed to authenticate?
(Otherwise the times for a successful authentication and an unsuccessful
authentication could differ thereby leaking information, right?) How
can you choose delta_t in a portable way?
I thought the way authentication is typically done is to be sure you
do the same amount of work for both a successful authentication and an
unsuccessful authentication. Then you don't need to choose a delta_t.
Authentication takes however long it takes, but the key property is that
it takes the same amount of time regardless of whether it is successful
or unsuccessful.

Well, if authentication succeeds, then the user is in, and has successfully
guessed a login and password (and it ostensibly an "authorized user").

The problem I thought the patch was addressing is that there are (at least)
two response paths.

1) Remote system failed quickly -- the username is invalid
2) Remote system failed slowly -- the user name is valid, but the password
is invalid.

If pattern 2 is observed, you've successfully guessed a name, and you can
switch to guessing passwords (the search space is much reduced -- and
knowledge of a valid username itself may have value for chained attacks,
perhaps on related systems or subsystems, or even for phishing or other
social engineering attacks).

Of course, I'm making an assumption, because this wasn't explicitly stated
in the original mail. But that looks like a threat to me. This is analogous
to returning a different error message based on whether the username is
invalid, as opposed to if the username is valid but the password is invalid.
That's been known to be a bad idea for at least 30 years.

By delaying in the "non-authenticated case", you can deny the adversary the
knowledge of whether it's case 1 or case 2.

The delay time can be any time you like, as long as the minimum delay is
greater than the longer of path (1) and path (2). You are going to disclose
the fact that user+password are invalid, in any case; but you should not
disclose more info than that.

Randomizing the delay (as mind@ suggested) will disguise the algorithm
you're using to hide the info, but the basic idea is to hide the info. I'm
not sure what else randomizing the delay will add (defense-wise) but I
imagine that I'm overlooking something.

It's also possible that I've totally misunderstood the original message! But
certainly, it's a bad idea to disclose whether you took path (1) or path (2)

Best regards,
--Terry

[J. Lewis Muir]

Post by Terry Moore
The delay time can be any time you like, as long as the minimum delay
is greater than the longer of path (1) and path (2). You are going to
disclose the fact that user+password are invalid, in any case; but you
should not disclose more info than that.

Hi, Terry.

It still isn't clear to me how to choose a delay time that is portable
and usable. That's why I'm asking how you would actually choose it. To
be more specific, how do you determine the time for path (1) and path
(2)? Is that time the same on all hardware? I bet not. Is that time
the same under various system loads? I don't know. How do you make it
portable?

Maybe you choose the delay time to be so long that you are sure that,
regardless of hardware, load, or any other factors, it will be equal to
or longer than the greater of path (1) and path (2). Is the delay time
actually reasonable at this point, or is it so long that it hurts the
usability of the authentication?

I'm just trying to understand how your method would work. I can
understand, for example, introducing a random delay to defend against
a timing attack based on the analysis of the timing of network packets
corresponding to keyboard key presses of a user typing their password.
In that case, we can determine roughly how fast an average user might
type, and we can introduce a random delay that would disrupt timing
analysis. What I'm not clear on is how you can do the same thing in a
portable way for computer hardware.

Best,

Lewis

[J. Lewis Muir]

My suggestion only changes the timing of the *failed* authentication
path. I don't know of any reason why you would want that to be fast,
especially if authenticating for a computer as the client.

Hi, Terry.

Ah, I see now. I was thinking the timing for all authentication paths,
successful and failure, needed to be indistinguishable, but I see
now that that's not the case. The successful path can be as fast as
possible, but all *failure* paths need to be indistinguishable so as to
avoid leaking. Now I get it. Sorry for being slow on this. Thank you
for your continued explanation and patience.

Is there a reason that "fast authentication denial" is desirable?

For me, no.

Best,

Lewis

[Terry Moore]

Hi Lewis,

Thank you for your continued explanation and patience.

Thank you in turn for getting me to clarify my thoughts. (It's an
interesting question -- how best to discourage these kinds of attacks.)

--Terry

[Michael Richardson]

Post by Terry Moore

Thank you for your continued explanation and patience.

Thank you in turn for getting me to clarify my thoughts. (It's an
interesting question -- how best to discourage these kinds of attacks.)

I'm a little surprised at the techniques.

I'd think that the right answer is, whenever it fails for any reason
at all, that it should perform sleep(base+rand()) before answering. One
could even time all of the various failures and adjust base to be the
average time it has failed, if one had a stable place outside of a single
process to store the running average.

It seems that the mechanisms used simply penalize legitimate users
with code that isn't optimized well.

--
] Never tell me the odds! | ipv6 mesh networks [
] Michael Richardson, Sandelman Software Works | network architect [
] ***@sandelman.ca http://www.sandelman.ca/ | ruby on rails [

[Jean-Yves Migeon]

Post by Michael Richardson

Post by Terry Moore

Thank you for your continued explanation and patience.

Thank you in turn for getting me to clarify my thoughts. (It's an
interesting question -- how best to discourage these kinds of attacks.)

I'm a little surprised at the techniques.
I'd think that the right answer is, whenever it fails for any reason
at all, that it should perform sleep(base+rand()) before answering. One
could even time all of the various failures and adjust base to be the
average time it has failed, if one had a stable place outside of a single
process to store the running average.
It seems that the mechanisms used simply penalize legitimate users
with code that isn't optimized well.

That depends on the way you implement failure/success checks.

On one hand when you are doing hash-style checks (like HMACs), validity
is essentially a check on the resulting value: legitimate users are
_always_ penalized because a naive strcmp() will always run to
completion before returning 0 (full string check), whereas an invalid
hash will return != 0 result before reaching the end of the byte string
where they differ.

In that scenario illegitimate users have a lower computation time than
legitimate ones because their computation will end earlier. Constant
time checks is good because it penalizes illegitimate accesses without
adding too much computation time for legitimate ones (it forces the full
string check even when the first byte is invalid).

On the other hand there are other systems (challenge based ones) where
legitimate/illegitimate accesses can be designed so that illegitimate
accesses get increasing penalty (zero knowledge proofs can have
increasing round checks which require computation on the side of the
prover). Out of scope there.

IMHO adding sleep(base + rand()) here is not productive. After all bozo
is in the situation of comparing two byte strings (~= hash check), so
the legimitate user is already penalized by bozo when it has to validate
the entire string. Randomizing the sleep just increases the signal/noise
ratio. IMHO constant time checks is better.

You are right on the indistinguishability of the error (good example is
CVE-2008-5161).

Cheers all,

[David Laight]

Post by Jean-Yves Migeon
IMHO adding sleep(base + rand()) here is not productive. After all bozo
is in the situation of comparing two byte strings (~= hash check), so
the legimitate user is already penalized by bozo when it has to validate
the entire string. Randomizing the sleep just increases the signal/noise
ratio. IMHO constant time checks is better.

The 'cost' of any memory compare will be absolutely minimal compared
to the cost of actually sending a TCP packet.

Is the time taken to do the password hash check actually measureable
on a remote system?
Go through a couple of routers and you'll get jitter.
Even the ethernet MAC's interrupt mitigation could well add enough jitter.

Of course, if you have to do another lookup against some database server
then that will add add a measurable delay.

David

[matthew green]

Post by David Laight
The 'cost' of any memory compare will be absolutely minimal compared
to the cost of actually sending a TCP packet.
Is the time taken to do the password hash check actually measureable
on a remote system?

see the original post for details. :-)


.mrg.

[Jean-Yves Migeon]

Post by David Laight

Post by Jean-Yves Migeon
IMHO adding sleep(base + rand()) here is not productive. After all bozo
is in the situation of comparing two byte strings (~= hash check), so
the legimitate user is already penalized by bozo when it has to validate
the entire string. Randomizing the sleep just increases the signal/noise
ratio. IMHO constant time checks is better.

The 'cost' of any memory compare will be absolutely minimal compared
to the cost of actually sending a TCP packet.
Is the time taken to do the password hash check actually measureable
on a remote system?
Go through a couple of routers and you'll get jitter.
Even the ethernet MAC's interrupt mitigation could well add enough jitter.
Of course, if you have to do another lookup against some database server
then that will add add a measurable delay.

Sorry for such a late answer, I was hiking in places where Internet
access is... well, inexistant. Yes, even in 2014 this still happens :)

All your remarks about jitter and latency added by network components
are true; however counting on it to "hide" side channels is a bit
optimistic. We never know how the server might be used, or even how its
code could be cargo-culted someplace else.

Hash/HMAC checks should be using constant time code paths between
valid/invalid states when these are used for authentication/signature
purposes. Google's keyczar made this mistake a while back, and they
fixed it with the classic "return XOR computation" (for good).

Granted timing attacks over a network are more complicated than
localhost ones but are still doable. Usually the noise added by all the
network components are roughly comparable to white noise which can be
filtered out when you have enough samples and time at your disposal. See
[1] as a good example (a bit outdated though).

[1] http://crypto.stanford.edu/~dabo/pubs/papers/ssl-timing.pdf

[Terry Moore]

Post by J. Lewis Muir
Maybe you choose the delay time to be so long that you are sure that,
regardless of hardware, load, or any other factors, it will be equal to
or longer than the greater of path (1) and path (2). Is the delay time
actually reasonable at this point, or is it so long that it hurts the
usability of the authentication?

My suggestion only changes the timing of the *failed* authentication path. I
don't know of any reason why you would want that to be fast, especially if
authenticating for a computer as the client.

If there is some reason why you would want a "fast authentication denial"
for a computer, then (of course) my approach is not useful. I don't know of
any application (computer or human) where the speed of getting an
authentication denial is important. It possibly gets the socket closed more
quickly, which might reduce DoS vulnerability, but there are well known ways
(such as rate limiting connect acceptance) for mitigating that, and I think
one has to do that anyway. (If I recall correctly, if the opponent hasn't
acked previous messages transmitted to the opponent, the socket has to
linger for a while. And if you're transmitting a denial message, instead of
just closing the socket, I believe you're further at risk for DoS
scenarios.)

If we assume that "slow authentication denial" is acceptable, I would choose
a large number (such 5 seconds). Of course, I'm assuming that the crypto
checks can be done in that interval, but if not then this is moot. If
necessary: during startup, run a dummy authentication and time it. Path 2 is
obviously more work than Path 1, so you just time that. Set your delay to
the larger of 2 ticks of time and 10 * path 2.

Is there a reason that "fast authentication denial" is desirable?

--Terry

[Mindaugas Rasiukevicius]

Post by Terry Moore
Perhaps this is a silly comment; but wouldn't it be easier to simply time
stamp the incoming request, and then spin for any authentication failure
until a suitable fixed time has elapsed after the inbound arrival? Or are
you worried about local cache-interference attacks as well?

Why fixed time? Make it random time.

[Joerg Sonnenberger]

Post by Mindaugas Rasiukevicius

Post by Terry Moore
Perhaps this is a silly comment; but wouldn't it be easier to simply time
stamp the incoming request, and then spin for any authentication failure
until a suitable fixed time has elapsed after the inbound arrival? Or are
you worried about local cache-interference attacks as well?

Why fixed time? Make it random time.

Random noise can be filtered out moderately easy.

Joerg

[Mindaugas Rasiukevicius]

Post by Joerg Sonnenberger

Post by Mindaugas Rasiukevicius

Post by Terry Moore
Perhaps this is a silly comment; but wouldn't it be easier to simply
time stamp the incoming request, and then spin for any authentication
failure until a suitable fixed time has elapsed after the inbound
arrival? Or are you worried about local cache-interference attacks as
well?

Why fixed time? Make it random time.

Random noise can be filtered out moderately easy.

If you add it on top of the memcmp(), then yes. Not if you make the total
time random (take a timestamp from before the operation), just need ensure
that it is above the upper bound.

[Lars Heidieker]

Post by Mindaugas Rasiukevicius

Post by Joerg Sonnenberger

Post by Mindaugas Rasiukevicius

Post by Terry Moore
Perhaps this is a silly comment; but wouldn't it be easier to simply
time stamp the incoming request, and then spin for any authentication
failure until a suitable fixed time has elapsed after the inbound
arrival? Or are you worried about local cache-interference attacks as
well?

Why fixed time? Make it random time.

Random noise can be filtered out moderately easy.

If you add it on top of the memcmp(), then yes. Not if you make the total
time random (take a timestamp from before the operation), just need ensure
that it is above the upper bound.

But just making the compare const runtime does the job of not leaking
any information about the compare, which is of use if the hash compare
is used in a different context.
Making the whole authentication-process bound by an random time seems to
me as good as making it bound by static time (both above the upper
bound) as both will hide any runtime differences.

just my 2 cents...

[Joerg Sonnenberger]

Post by shm
bozohttpd currently checks password using strcmp, which may leak information

Personally, I would find it much more useful to allow using cdbr(3) for
indexed access. Pad the username to the maximum length found and it all
boils down to the user having consistent crypt(3) hash settings. Even
without the latter, you can't distinguish a valid username from an
invalid one, just that you have a set of accounts using shared hash
settings.

Joerg