8

As far as I understand the answer at https://security.stackexchange.com/a/3024/13447, client nonces are meant to prevent attackers from amortizing the costs of brute-force hash computations by being able to reuse the computations results

  • for multiple users and/or
  • for multiple servers

However, even in the simplest Digest Authentication variant (qop = none), the username and the realm (supposedly unique per server) and the nonce (more than just unique per server) are included in the data that gets (usually MD5) hashed.

Doesn't this already make reusing of precomputed hashes across users/servers impossible?

So a client nonce would only add to security, if https://www.rfc-editor.org/rfc/rfc2617#section-4.9 is correct:

The ability to choose the nonce is known to make cryptanalysis much easier [8].

But that same section then goes on to say

However, no way to analyze the MD5 one-way function used by Digest using chosen plaintext is currently known.

This is a statement from 1999. Since then, various collision attacks have been published for MD5, but none which would help in this case, if I'm not mistaken.

What am I missing?

Update I guess it makes sense to spell out what we are talking about exactly. In the most basic form of Digest Authentication the client calculates and sends to the server the result of the following:

MD5(MD5(username + ":" + REALM + ":" + password)
    + ":" + NONCE + ":" +
    MD5(http-method) + ":" + uri))

Except for the password, all values are also sent in plain text.

To make it more clear, variables whose values are set by the client are lowercase, whereas variables the client retrieves from the server are in uppercase. (This makes my 'realm and nonce' fallacy above, pointed out by David Wachtfogel immediately obvious, as a MITM can freely choose those uppercase values, assuming the realm is not checked by the client, which, judging from the "sophistication" I've seen in most admin's passwords, would be the norm, rather than the exception).

Btw, the value of the uri is supposed to be an absolute uri, like http://servername/path?query, and thus would globally unique, however, that depends on the client's implementation and whereas Opera implements it that way, the versions of Chrome, IE, Firefox I tested do not, and rather just use '/path?query' (afaict this is in violation of https://www.rfc-editor.org/rfc/rfc2617#section-3.2.2.5).

So whether a precomputed table would be reusable across servers depends on the client implementation, and if the MITM can choose, it will of course prefer the weaker browsers to Opera, if he has a precomputed table.

Community
  • 1
Evgeniy Berezovsky
  • 185
  • 1
  • 6

2 Answers2

7

As described in Thomas Pornin's answer cited in this question, the goal of the client nonce is to prevent a chosen plaintext attack in which the attacker impersonates the server and chooses the challenge. In such a situation the attacker can also choose the realm (since this comes from the server) so the fact that realm is hashed as part of the response doesn't completely prevent this attack. Only if the user is vigilant and checks that the realm is as expected will this prevent the attack.

The username does help in that it requires the attacker to build a precomputed hash table, such as a rainbow table, per username. The problem is that usernames aren't globally unique - the same username will exist on many different servers. In fact some usernames are extremely common and are likely to appear on most servers - a classic example being "admin".

So an attacker can do the following:

  1. One time: build a precomputed hash table for username = "admin", realm = X and challenge = Y (using any value for X and Y)
  2. Interercept connections to any server the attacker wants to attack
  3. If someone connects to the server with username "admin", send real = X and challenge = Y
  4. Lookup the response in the precomputed hash table to reveal the password

The client nonce prevents this kind of attack; since the attacker doesn't control and can't predict this nonce the attacker can't build the precomputed hash table.

Community
  • 1
David Wachtfogel
  • 5,512
  • 21
  • 35
  • Correct me if I'm wrong, but the attacker can collect one Authorization header, do an exhaustive search on e.g. lowercase passwords to find the password in the HA1 value, and using that password he can initiate his own session impersonating the attacked user, generating the cnonce himself. All information needed (besides password) can be found in an Authorization header? – Henning Klevjer Oct 16 '12 at 11:22
  • 2
    Correct, but this would require the attacker to redo the exhaustive search for each password the attacker wants to crack. If it wasn't for the client nonce the attacker could do the exhaustive search operation once per username and build a hash table which could be used to attack the same username on many servers. – David Wachtfogel Oct 16 '12 at 13:00
  • 1
    Ah, right! I'm actually working on this at the moment, so anyone interested, have a look here: http://klevjers.com/projects/div/digest-attack.png – Henning Klevjer Oct 16 '12 at 13:23
  • +1 Thanks for reminding me of that important part of Pornin's answer. – Evgeniy Berezovsky Oct 16 '12 at 23:22
  • @DavidWachtfogel The attack you describe makes the advantage of a cNonce clear. Re: `could be used to attack the same username on many users`, I updated my question with details on `Digest Auth` that make it clear when and how that would work. All `admin` users, to stay in your example, who use Opera would be protected against that form of reuse, – Evgeniy Berezovsky Oct 16 '12 at 23:30
2

the username and the realm (supposedly unique per server)

This is not correct. The realm is a value specified by the service provider to describe the protection realm, so it's only a name, not a global identifier.

In your second quote I think they refer to the "one-way-ness" of MD5 not being broken. The most effective way to find a preimage (i.e. go from the value Y = MD5(x) to find x) requires 2123.4 operations.

the cnonce "is an opaque string provided by the client and used by both client and server to avoid chosen plaintext attacks, to provide mutual authentication, and to provide some message integrity protection."[RFC] Together with the nonce, it facilitates sustained mutual authentication: authentication of the client to the server and vice versa.

Henning Klevjer
  • 1,815
  • 15
  • 20
  • Re: realm - Sure, it's a value chosen by whoever implements / administers the service, and as such not necessarily unique, but in my case, I have control over this, and I chose something that is so unlikely to be used by any other server. So I don't worry about a rainbow table for that realm flying around. – Evgeniy Berezovsky Oct 16 '12 at 08:05
  • Hmm... still mulling over your *mutual authentication* comment. I don't see how the random cnonce helps providing authentication of the client to the server and a bit of searching still leaves me clueless. Would you care to elaborate or do you have a helpful link, perhaps? – Evgeniy Berezovsky Oct 16 '12 at 08:26
  • Still the nonce value acts as a seed on the final response value, randomizing it so that a unique realm name has no benefit. The cnonce itself provides continuous authentication of the server. Say a user generates a cnonce using MD5 on some secret he has and a timestamp: cnonce = MD5(secret_val:(POSIX_time%cnonce_lifetime)). He then calculates "response" and passes it to the server. Later, when the server passes 200 OK on an authorized GET, he shows the client that he knows his cnonce, thus proving (somewhat weakly) that he is the same server as before. – Henning Klevjer Oct 16 '12 at 09:08
  • Thanks for the `realm` comment. Just updated the question. In terms of the cnonce: So what you are saying is that the client could be `stateless` and would still be able to check if the cnonce originated from it? Otherwise, as the cnonce is sent as plaintext, it is not a shared secret or anything with even a minimum hurdle for an attacker to figure out. – Evgeniy Berezovsky Oct 16 '12 at 09:24
  • The cnonce is not a shared secret, no. It is "opaque" to the server, meaning that it has no clue what to do with it (as it's hashed or random, or maybe encrypted?), but the client *could* verify it, by i.e. decrypting or comparing hashes (local gen. and received cnonce). The client could do whatever really, use it for ..transportation, etc ;). HTTPDigAuth is stateless in itself, as all HTTP methods contain an Authorization header to authenticate the user (RFC confuses Authorization with authentication here, IMO). (PS. Attackers would need the password to generate a correct response). – Henning Klevjer Oct 16 '12 at 09:33
  • Additional info if you need it: nonces and cnonces die on timeout from the server (Apache: 300s = 5min), on which the server responds with 401 Authorization Required (as is normal initially, or when the password is wrong), with the `stale` flag set. – Henning Klevjer Oct 16 '12 at 09:36
  • Re: `mutual auth` I can follow the [RFC](http://tools.ietf.org/html/rfc2617#section-3.2.3): `the "response-auth" directive supports mutual authentication -- the server proves that it knows the user's secret, and with qop=auth-int also provides limited integrity protection of the response`, according to which **mutual auth is provided by the password, not the cnonce**. – Evgeniy Berezovsky Oct 17 '12 at 01:35
  • The cnonce is of course mainly used only to restrict the *replayablity* of an Authorization header. However, it also contributes to *sustained* authentication, in that the server continually proves to the user that it has the cnonce. I was a little unclear on the top, I'm sorry for that. – Henning Klevjer Oct 17 '12 at 05:52