RE: Digest Auth defending against replay

John says:
----------
]
] > However: incrementing nonces only require one challenge per *session*,
] > which is much more efficient, especially for long sessions. (This won't
] > matter for sites where most information doesn't require authentication,
] > but subscription based sites are an important case that lots of people
] > want to support and  they would have almost all pages be authenticated
] > if it were cheap enough.)
]
] Yes, but I thought we had agreed that for a subscription service there
] is no reason not to re-use nonces.  Re-using the nonce is even cheaper
] than incrementing them.

I think I agreed that one could live with it if there
were no cheap or easy alternative. You can get away with reusing nonces
for a while -- but your recommended nonce has a timestamp in it to prevent
theft of a response from being used forever, so I guess you thought that
there should be _some_ limit, too. It's just better if the limit is none.

Note that if you used incrementing nonces, you wouldn't need a timestamp.
Probably comes out about even in expense with incrementing.
Which is why I removed it from the last suggested replacment for the <nonce>
description.

]
] > When using persistent connections, the next expected nonce on that
] > connection can be kept in a per-connection data structure (which
] > the server probably already has and where the authenticated user
] > name would also be kept), and directly accessed, without the
] > overhead of a hash table.
]
] If you don't keep a hash table how do you prevent a replay attack?
] The replay would, of course, be in a different session.

And each new session issue a challenge using a totally new nonce,
and only accept the latest incremented version of it.  All replays
of old ones would just be rejected.

] I thought  that defending against replay was the point of all this.  
You haven't
] yet described how you would implement aging and recycling your hash
] table.

That's because one isn't needed when one is using persistent connections.
You age the hash table by putting an expiration time in each entry,
and freeing the entry when that time has passed.

(The code I posted for when not using persistent connections aged
the table by keeping entries until another client came along whose
username and realm hashed to the same entry. Since it was a one-way
associative direct mapped hash table, it is possible to thrash over
entries. I've updated the code and put it below -- now it times out
entries and uses an 8 way associative hash table. It's grown to 64 lines...)

]
] If what you want is one challenge per session, a good way to implement
] it would be a global hash table of session nonces together with a
] very small per session hash of the response digests kept in the per
] session data structure you mention.  The nonce would not change
] throughout the session.

If the per session has table in N entries, then it will generate a challenge to
the client once every N requests. Which will lead to the problem with browsers
you point out below.

]
] >
] > Lastly, incrementing nonces are compatible with all existing
] > implementations. A server that wasn't expecting the (new) client
] > to modify the nonce will fail to authenticate and reissue the
] > challenge. (A clever client could even notice this and stop
] > incrementing the nonce after a couple of challenges to see if that helped.)
] >
]
] The Microsoft browser I use for testing my implementation of Digest
] Authentication responds to a re-issued challenge by asking the user to
] re-enter the username and password.

Good thing it's in beta; it'll be fixed in the next beta release.
This is a bug for any scheme that reissues challenges in order to 
prevent replay.
That means your one-time responses, you suggestion to use a new nonce 
each time to avoid
incrementing nonces, as well as incrementing nonces and Phil H-B's idea, too.
Or it could be that it is ignoring the "stale=true" flag or the server 
isn't setting it.
(Isn't this exactly what "stale=true" is for?)

The client shouldn't reprompt if the "stale" flag is "TRUE". 
Additionally, the client
could use the heuristic only reprompt for password if it never got a successful
response to a request with a particular Authorization: header value.
If it has received at least one sucessful response, then when 
challenged, it should
recompute the digest and try that before reprompting.

] This is appropriate since it
] assumes that I have mistyped my password.

It shoudln't assume this if the "stale" flag were set.
]  I wouldn't want to do this
] whenever I contact a new server though.  Thus, at the very least, a
] new-server would have to prevent that by recognizing that it was
] talking to an old-client (i.e. the nonce had not been incremented).

Can't do that -- that would be the backward compatibility hole that you 
warned against
earlier.  How many *shipping* (not beta) clients that use Digest are there?
There can't be many servers that insist on Digest, either, otherwise 
they wouldn't
be getting very many hits :-). New-servers have to send "stale=true" 
when reissuing
challenges in order to prevent reprompting.

] Likewise, a new-client would also need a way to distinguish whether the
] re-issued challenge was due to a mis-typed password or an old-server.

Same algorithm as for detecting new-server reissuing a challenge.

Paul

#define NTSIZE 1024		// any size is OK, tune to server load
#define MAXTIME 100;		// max lifetime in seconds

typdef struct {			// entry in 8 way associative hash table
	char * username;	// username of client
	char * realm;		// realm, to support multirealm hosts
	int useuntil;		// latest time this entry can be used
	int seq;		// next sequence number expected from this client
} seq_ent;

seq_ent seqtab[NTSIZE];

seqinit() {
	int i;
	for (i - 0; i < NTSIZE*4; i++) seqtab[i].username = "";
};

// return -1 if seq num OK, else index of entry to (re)fill if not in 
table or expired
int seqcheck(char * username, char * realm, int seq) {
	int h, i, j;
	seq_ent * p;

	h = hash(username) + hash(realm);
	h = (h % (NTSIZE/8)) * 8;			// make it 8 way associative
	for (i=0, j = -1;  < 8; i++) {			// look in each of 8 entries for this hash
		p = &seqtab[h+i];
		if (!*p->username) {			// remember empty entry
			j = h + i;
			continue;
		};
		if (p->useuntil < time(NULL)) { 	// remember expired entry
			j = h + i;
			continue;
		};
		if (strcmp(p->username, username))	// match user name?
			continue;			// no -- try next entry
		if (strcmp(p->realm, realm))		// match realm?
			continue;			// no -- try next entry
		if (p->seq == seq-1)			// expected sequence number?
			return(-1);			// yes -- seq num OK
		return(h+i);				// reuse client's own entry
	};
	return(j < 0 ? h + rand(NULL) % 8 : j);		// no free or expired: pick 
random entry
};

// add a client to the expected sequence number table
seqnew(int h, char * username, char * realm, int seq) {
	if (*seqtab[h].username) {			// if entry is in use
		free(seqtab[h].username);		// free user name and realm
		free(seqtab[h].realm);
	};
	seqtab[h].username = strdup(username);		// copy in username
	seqtab[h].realm = strdup(realm);		// and realm
	seqtab[h].useuntil = time(NULL) + MAXTIME;	// make expiration time
	seqtab[h].seq = seq;				// next expected sequence number
};

// stupid hash...
int hash(char * s) {
	int h;

	for (h = 0; *s; s++) h = (h << 4 ) + (h >> 28) + *s;
	return(h & 0x7fffffff);
};

Received on Monday, 26 February 1996 18:18:14 UTC