Onderwerp: New Whitepaper: Anti Brute Force Resource Metering

Hi List,

It's been a couple of months since my last whitepaper, so time for a new
one. This new whitepaper focuses upon a method known as "resource metering"
to actively restrict (and possibly prevent) many brute force guessing attack
vectors that target custom web authentication processes.

The paper is now available from the NGS website:
http://www.ngssoftware.com/papers/NI...ceMetering.pdf

As always, I'm happy to discuss the topic further and would value
discussions about the techniques talked about in the paper.

Abstract:
"Web-based applications authentication processes are frequently vulnerable
to automated brute force guessing attacks. Whilst commonly proposed
solutions make use of escalating time delays and minimum lockout threshold
strategies, these tend to prove ineffectual in real attacks and may actually
promote additional attack vectors.

Resource metering through client-side computationally intensive "electronic
payments" can provide an alternative strategy in defending against brute
force guessing attacks. This whitepaper discusses how such a solution works
and the security advantages it can bring."


Cheers,

Gunter Ollmann

------------------------------------------------------
G u n t e r O l l m a n n, MSc(Hons), BSc
Professional Services Director

Next Generation Security Software Ltd.
First Floor, 52 Throwley Way Tel: +44 (0)208 401 0089
Sutton, Surrey, SM1 4BF, UK Mob: +44 (0)7710 496 714
http://www.nextgenss.com Fax: +44 (0)208 401 0076
------------------------------------------------------

On 21 Mar 2005 at 18:53, Gunter Ollmann (NGS) wrote:

> Hi List,
>
> It's been a couple of months since my last whitepaper, so time for a new
> one. This new whitepaper focuses upon a method known as "resource metering"
> to actively restrict (and possibly prevent) many brute force guessing attack
> vectors that target custom web authentication processes.
>
> The paper is now available from the NGS website:
> http://www.ngssoftware.com/papers/NI...ceMetering.pdf
>
> As always, I'm happy to discuss the topic further and would value
> discussions about the techniques talked about in the paper.
>

Hi Gunter (+BugTraq)

First, nice paper. Well written.

One thing that I think can perhaps be improved is the amount of
persistent data (the seed values) that the system keeps (in memory?).

My thought is to replace the seed value with something a bit more
complex, as following:

The system will indeed generate a seed value, yet it will not store
it. It will send it to the user, and then discard it (so it does not
consume space). The seed will be calculated as following:

let x = random digits ^ ":" ^ date_and_time [microsecond granularity]
seed = x ^ ":" ^ HMAC(key,x)

I also require that the client side changes a bit the way it answers
the challenge. Instead of
alg# ^ ":" ^ seed ^ ":" ^ userID ^ ":" ^ date ^ ":" ^ random data

I require that the attempted password be part of the data:
alg# ^ ":" ^ seed ^ ":" ^ userID ^ ":" ^ PASSWORD ^ ":" ^ date ^ ":"
^ random data

The user submits this string (such that its SHA-1 has the first N
bits zeros), together with the username and the password.

The server verifies that:
1. The last field of the seed is the HMAC with the server key of the
first two fields.
2. The time field in the seed is not too old (e.g. in the last 5
minutes).
3. The username and password that are submitted are indeed embedded
in the hashcash string
4. And of course, that the hashcash string does indeed hash into a
leading N zeros value.

Note that the server, in this suggested scheme, cannot disallow
sending the same seed again and again (during the 5 minutes lifetime
of the seed value). It also has no per-account memory, so there's no
"penalty" for attackers.

It should be noted that with this modified scheme:
a. A calculation done for one username+password pair is useless for
another pair (perhaps with the same username), because both the
username AND the password are part of the hashcash string.
b. Using server signed seed with time limit ensures that a seed
cannot be replayed too many times (and over a long period of time).
This prevents an attack wherein th attacker invests a lot of time in
preparing many "good" strings (in this scheme, for example, the
attacker can calculate hascashes for many usernames with a single
password), then trying those values periodically.

A comparison of the two methods (the original one, and the modified
one):

The original method uses per-account list of seeds.
The modified method uses only a global key.

The original method does keep the password out of the payment system.
The modified method must use the password (thus it somewhat
complicates the process - it's no longer two independent flows).

The original method can alter a specific account behavior.
The modified method (on account of not having a per-account data)
cannot alter a specific account behavior.

We see, therefore, that there is a tradeoff between the original
method (space consuming, more flexible, simpler) and the modified
method (compact, less flexible, somewhat more complex).

Regarding the fact that the password is used in the modified method:
As I said above, this is both less elegant, and in some cases may be
considered less secure (the original method was potentially unexposed
to the password).
However, a simple modification to the modified method ;-) can take
care of this shortcoming. Instead of providing the username and the
password, it is enough to provide, say:

salt ^ ":" ^ HASH(username ^ ":" ^ password ^ ":" ^ salt)

the system can then send a pass/fail status to the "normal"
username+password authentication system, along with the above value,
which the authentication system can (and must) verify. That is, the
system doesn't have to know the username and the password. It is
enough for it to verify that the hashcash was calculated for the
specific username and password that are provided.

While this indeed takes care of the username+password exposure in the
system, it also necessiates a tighter integration with the standard
authentication system (which now must verify the hash value).

Regards,
-Amit

--AXxEqdD4tcVTjWte
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On 2005-03-21 18:53:42 -0000, Gunter Ollmann (NGS) wrote:
> The paper is now available from the NGS website:
> http://www.ngssoftware.com/papers/NI...ceMetering.pdf
[...]
> "Web-based applications authentication processes are frequently vulnerable
> to automated brute force guessing attacks. Whilst commonly proposed
> solutions make use of escalating time delays and minimum lockout threshold
> strategies, these tend to prove ineffectual in real attacks and may actua=
lly
> promote additional attack vectors. =20
>=20
> Resource metering through client-side computationally intensive "electron=
ic
> payments" can provide an alternative strategy in defending against brute
> force guessing attacks. This whitepaper discusses how such a solution wo=
rks
> and the security advantages it can bring."

Interesting paper. For web applications this actually seems to be
feasible. Which brings me to my first quibble: You claim that hashcash
"has already proven to positively reduce the success" of spammers. Is
there any example of hashcash being deployed in e-mail systems? I don't
know any and I can't even offhand think of any feasible method of how it
could be deployed.

The second point is that while you mention that "the client host will
dictate the speed [...] and consequently the electronic payment will be
less for new or high end computers", I think you underestimate the
effects. If for example the hash operation is implemented in Javascript
(which seems to be the most portable solution), you have to make the
computation easy enough that the user with the oldest hardware and the
slowest javascript implementation can still log in. An attacker would of
course use the fastest implementation available - he could even
reimplement the javascript code in hand-optimized C or assembler, if
there is only a small number of algorithms in use. I wouldn't be
surprised if that's 100 times faster on identical hardware. The speed
difference between the slowest and the fastest hardware is at least
another order of magnitude. So you should expect your typical attacker
to be able to compute hashes at least 1000 times faster than your
worst-equipped legitimate user.

hp


--=20
_ | Peter J. Holzer \Beta means "we're down to fixing misspelled commen=
ts in
|_|_) | Sysadmin WSR \the source, and you might run into a memory leak =
if=20
| | | hjp@wsr.ac.at \you enable embedded haskell as a loadable module=
and
__/ | http://www.hjp.at/ \write your plugins upside-down in lisp". --ae@o=
p5.se

--AXxEqdD4tcVTjWte
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQDPAwUBQkGFnVLjemazOuKpAQGywAXLBWcFKmBr+e3nFvX3cl w03Z1LeCdULFIS
8kE+dMzeAgM5awNtsxT8VGDGyoKV4al2nuVyM9aG3/aCtL9WlScfM+JKC8bBwvUd
J9BS1RLvAW7BJ3fVaKTJ6Dwuwrpumxi1obQoPyfX1IrPPpSMVY xY/+HFZYcfdBiY
vA80Uk8kX7BU6eUlzVbRE0yACFBizAKORsxZxDxs9lqqdMIDLK/p2yM7QrEQ5hRX
gqGgN4IPIhD0alIHfvd4oVYf
=zBgv
-----END PGP SIGNATURE-----

--AXxEqdD4tcVTjWte--

Hi Amit Klein (+bugtraq)

> One thing that I think can perhaps be improved is the amount of
> persistent data (the seed values) that the system keeps (in memory?).

Too true - but please bear in mind that the example used to implement
resource metering was really just an example, and was based upon the
anti-spam "hashcash" model. This was purely done to keep things as
simple as possible and for those familiar with that implementation to
quickly see how it could be used in web-based auth.

The core of the paper revolves around the use of client-side
computationally intensive routines that are designed explicitly to cause
a delay in submission to the server. The general criteria for a
solution are:
a) It needs to be client-side.
b) It needs to be controllable - i.e. easy to increase/decrease the
processing requirements.
c) It must be quickly verfiable by the server.
d) It should be appropriate for the application it is helping to protect.

Outside of that, it's fair game - the implementation fine points are
down to the organisation that chooses to make use of an "electronic
payment" resource metering solution. ;-)

>
>It should be noted that with this modified scheme:
>a. A calculation done for one username+password pair is useless for
>another pair (perhaps with the same username), because both the
>username AND the password are part of the hashcash string.
>
I would not normally recommend the use of passwords in this manner.
Basically, a password mapped to a user/customer should not really be
stored anywhere at the server end - instead a hash of the password is
stored (therefore, should anyone gain access to the database - they do
not have the passwords). In practical terms, this means that when a
customer submits their auth details to the server, it calculates the
hash of the submitted password and compares it to the hash it has stored
in the backend database.

For your proposal, the server would need access to the real password to
verify the hashcash. Perhaps if the client-side sends a hashed value of
their password instead?

Cheers,

Gunter

In-Reply-To: <20050321182737.81B6B15F507@mail.ngssoftware.com >


>Resource metering through client-side computationally intensive "electronic
>payments" can provide an alternative strategy in defending against brute
>force guessing attacks.


The first question I had was,
Why not just use a turing test. It's simple and, theoretically, only humans can distinguish the passphrase. It requires much less overhead. Obviously this would be used in addition to a password. That's my two cents.

On Thu, Mar 24, 2005 at 07:33:40PM -0000, Jason W wrote:
>
> >Resource metering through client-side computationally intensive "electronic
> >payments" can provide an alternative strategy in defending against brute
> >force guessing attacks.
>
> The first question I had was,
> Why not just use a turing test. It's simple and, theoretically, only humans can distinguish the passphrase. It requires much less overhead. Obviously this would be used in addition to a password. That's my two cents.

True, but this is not foolproof. If you work hard enough, you can get a
program to recognize text in an image, even if some lines are crossed
in-between. Other 'Turing tests' have similar practical problems,
requiring either a human to check the response (which in practice means
a human adds a decidedly finite amount of possibilities into the
application) or being solvable by a good coder with nothing better to
do (which is a pretty accurate description of a hacker, come to think of
it... ;-) )

Of course, one might use these two together - the above might cost
enough computing power to qualify as 'electronic payment'...

Joachim

Hi Gunter+BugTraq

See my comment below.

Thanks,
-Amit

On 23 Mar 2005 at 10:23, Gunter Ollmann wrote:

> >
> >It should be noted that with this modified scheme:
> >a. A calculation done for one username+password pair is useless for
> >another pair (perhaps with the same username), because both the
> >username AND the password are part of the hashcash string.
> >
> I would not normally recommend the use of passwords in this manner.
> Basically, a password mapped to a user/customer should not really be
> stored anywhere at the server end - instead a hash of the password is
> stored (therefore, should anyone gain access to the database - they do
> not have the passwords). In practical terms, this means that when a
> customer submits their auth details to the server, it calculates the
> hash of the submitted password and compares it to the hash it has stored
> in the backend database.
>
> For your proposal, the server would need access to the real password to
> verify the hashcash. Perhaps if the client-side sends a hashed value of
> their password instead?
>

Exactly! Which is what I suggested in my email (the "modification to
the modified method"). Here's the text from the bottom of my original
email:

<FROM_ORIGINAL_EMAIL>

Regarding the fact that the password is used in the modified method:
As I said above, this is both less elegant, and in some cases may be
considered less secure (the original method was potentially unexposed
to the password).
However, a simple modification to the modified method ;-) can take
care of this shortcoming. Instead of providing the username and the
password, it is enough to provide, say:

salt ^ ":" ^ HASH(username ^ ":" ^ password ^ ":" ^ salt)

the system can then send a pass/fail status to the "normal"
username+password authentication system, along with the above value,
which the authentication system can (and must) verify. That is, the
system doesn't have to know the username and the password. It is
enough for it to verify that the hashcash was calculated for the
specific username and password that are provided.

While this indeed takes care of the username+password exposure in the
system, it also necessiates a tighter integration with the standard
authentication system (which now must verify the hash value).

</FROM_ORIGINAL_EMAIL>


Regards,
-Amit

On Thu, Mar 24, 2005 at 07:33:40PM -0000, Jason W wrote:
>In-Reply-To: <20050321182737.81B6B15F507@mail.ngssoftware.com >
>
>
>>Resource metering through client-side computationally intensive "electronic
>>payments" can provide an alternative strategy in defending against brute
>>force guessing attacks.
>
>
>The first question I had was,
>Why not just use a turing test. It's simple and, theoretically, only humans can distinguish the passphrase. It requires much less overhead. Obviously this would be used in addition to a password. That's my two cents.

Be certain that your turing test does not rule out certain classes of
humans, eg. a text displayed as an image would be undecipherable by a
blind user.

Regards,
L.

--
Luca Berra -- bluca@comedia.it
Communication Media & Services S.r.l.
/"\
\ / ASCII RIBBON CAMPAIGN
X AGAINST HTML MAIL
/ \