|Anti brute force resource metering : Whitepapers : Home|
Anti Brute Force Resource Metering
Helping to Restrict Web-based Application Brute Force Guessing Attacks through Resource Metering
For most web-based applications that require customers to uniquely identify themselves prior to granting access to key functional aspects of the online system, a solid and reliable authentication process is the primary security barrier. When these applications are providing online services to a large and/or diverse customer base, the authentication process must be able to withstand an increasing number of malicious attack vectors. Poorly designed or implemented authentication processes are easily exposed and as a consequence are likely to result in subsequent exploitation resulting in an increase in adverse public scrutiny and a concomitant decrease in customer confidence.
A critical element to any successful online authentication solution is the way in which account lock-out processes are implemented. In particular, how the application handles an attacker attempting to guess the login credentials of customers and prevents access during automated brute-force guessing attacks. For an attacker, authentication solutions that unintelligently lock-out access to customer accounts after a specific threshold has been reached (typically three attempts) can be easily turned into a highly successful denial of service attack. By quickly reaching the threshold limit of bad password attempts, the attacker can cycle through customer names or account numbers and lock-out each in turn.
The speed at which these attacks can be conducted can be remarkable. It is not uncommon for attackers to conduct as many as 200 login attempts per second over standard DSL connections. In some cases, when applications have very simple single-tier authentication processes and the attacker has good network access to the host, they can achieve many simultaneous parallel connections – rates of between 1500-10,000 login attempts per second can be achieved.
While various solutions for handling authentication processes and account lock-out policy have been suggested in an attempt to manage these attack vectors, it is left to each individual organisation to carefully weigh up the pro’s and con’s of each option before arriving at a compromise solution.
One frequently considered compromise is to link authentication failures to a specific IP address and to conduct multiple actions based upon this information. Unfortunately, due to the use of ISP proxies and network address translation, it is highly likely that legitimate customers will seek to access an application from behind these devices and that therefore their connections will appear to come from the same IP address. Subsequently, any automated response to block or otherwise inhibit IP addresses associated with an attack may consequently prevent legitimate customers from accessing the application.
However, the use of IP address information as part of an automated defence strategy can still be valuable. Instead of focusing upon the outright blocking of an attackers IP address, organisations may wish to adopt a strategy capable of slowing down an automated attack to such a degree that it becomes an unviable attack vector and therefore forces an attacker to direct their attention to alternative “softer” targets – preferably some other organisation. By requiring an “electronic payment” for each login attempt, the application can enforce a computational overhead (and subsequent time delay) upon the submitting host which can then be used as a form of resource metering. A similar strategy has proved successful in reducing email-based Spam attacks – where the “electronic payment” overhead is referred to as “hashcash”.
Resource metering is a technique designed to restrict the repetition frequency of data submission to an application or host system. The ability to reduce the frequency of data submissions can play an important role in controlling an attacker’s ability to conduct an automated brute force guessing attack. To be successful, a resource metering solution should enforce restrictions at the client-side and not consume additional resources at the server-side.
The most practical method of implementing resource metering is through the use of cryptographic hashes. The use of a cryptographic hash in this fashion is sometimes referred to as requiring an “electronic payment” before processing the customer’s submission. In essence, the server-side application requires the customer’s client to compute a value that is computationally intensive, but easy to validate, before processing the submitted data.
The principles are based upon the fact that there are numerous mathematical problems that are easier to verify than they are to compute. For example, the calculation of square roots of a large number is a complex and processor intensive task – but is easy to validate since:
While the concept of using square root computations sounds appealing, unfortunately computers are very fast and therefore to be conducive to resource metering the number would have to be 1000’s of digits long. Given the HTTP medium, it would probably take longer for the transmission of the data than the time taken to compute the values.
Learning from Spam
Email has been around longer than the web – consequently there are a number of security solutions that have had a longer gestation period in which to mature and prove their worth. The implementation of resource metering in the fight against email-based Spam has already proven to positively reduce the success of these automated intrusions – normally resulting in Spammers seeking softer or alternative targets.
The most important resource metering solution within the SMTP domain is commonly referred to as “hashcash”. By requiring the attacker’s email agent to conduct a computationally intensive process as part of each email submission, the spammer incurs a delay with each email delivery and greatly reduces the effectiveness of their intrusion. Whilst not completely eliminating the threat, “hashcash” helps to restrict the flow of Spam and can force the malicious spammer to seek a more vulnerable system.
Borrowing heavily from the concept of “hashcash” within email services, it is a relatively simple process to include a similar level of resource metering within a web-based applications authentication process – the purpose being to greatly reduce the effectiveness of an automated brute force guessing attack.
Originally proposed by Cynthia Dwork and Moni Naor in 1992, and independently invented in May 1997 by Adam Back, the concept of hashcash was introduced as a way of installing a resource metering solution (referred to as an “electronic payment”) capable of throttling the systematic abuse of services such as email and anonymous re-mailers.
As mentioned previously, there are a number of mathematical problems that are far easier to verify than they are to initially compute. “Hashcash” makes use of a mathematical principle called “partial hash-collisions”. These partial hash-collisions require smaller variables than those required for the equivalent resource metering by square root calculations (making them more convenient for inclusion in server responses), are substantially faster to verify, and often simpler to program.
“Hashcash” traditionally computes hash-collisions based upon the email recipients address, date and some random seed data.
A hash function is a one-way cryptographic function that transforms a string of characters, usually into a shorter fixed-length value or key, based upon the assumption that it is extremely difficult and time consuming to find two strings capable of producing the same output. Given a change in the input string, the resultant hash also changes. Common hash functions include MD5 and SHA-1. “Hashcash”, as implemented in numerous anti-spam email solutions, makes use the SHA-1 hash function.
Hash functions such as SHA-1 have been designed to be collision resistant – i.e. two distinct input strings should not produce that same hash value. In fact, the SHA-1 cryptographic function is not expected to result in the same hash result for two distinct input strings for 2160 different values.
In theory, calculating a full “hash-collision” is computationally infeasible – requiring great computing resources and extended timescales (although shortcut vectors for finding collisions have been announced in the common hashing functions: SHA-0, SHA-1, MD4, MD5, HAVAL-128, and RIPEMD).
“Hashcash” makes use of partial hash-collisions (sometimes referred to as n-bit collisions). Instead of requiring the hashed value from one string to be completely the same as the hashed value of a different string (or indeed calculating the same string), only parts of the two hash values need to be identical. By defining how much of the first hash value must match the other, it is possible to control how much computational time must be expended in evaluating a correct answer.
For example, using an online “hashcash” demo supplied by Lapo Luchini and implemented in Java, calculation of the first 21 most significant bits takes around 4 seconds on a 3GHz processor desktop computer – while calculating the first 27 most significant bits takes a little over 2 minutes.
Web-Authentication Resource Metering
The purpose of introducing an “electronic payment” to the authentication process is to provide a degree of time control over which customers may submit their login credentials to the application server – therefore providing a mechanism for resource metering. Additionally, by forcing a computational overhead to occur at the client-side host, the application server is free to process other application processes.
A well-discussed and increasingly popular strategy for handling automated brute force guessing attacks against an application’s authentication process is through the use of incremental timeouts. Essentially, with each failed login attempt, the application server takes longer to respond to the attacker (or customer).
Consider an authentication process that requires the customer to fill in their user ID and password on an HTML-based form and submit this data to the application for authentication. If the login credentials are incorrect, the server redirects the customer to the original login page after a couple of seconds telling them that they have failed and must retry. If the customer supplies incorrect login details a second time, the response from the server takes 4 seconds longer – and so on until some maximum threshold is reached (typically no more than 2 minutes). This incremental timeout strategy may be combined with a maximum login attempt threshold – at which, after say 6 incorrect login attempts, the customer account is locked out and no longer available.
There are a number of problems with this incremental timeout strategy:
Understanding Web-Authentication Resource Metering
Typically, in order to implement a resource metering solution, it is necessary for the client browser to be capable of performing mathematical functions via a scripting language. Therefore, resource metering cannot be used in the authentication process for web-based applications designed specifically not to require client-side scripting.
The sequence of events in this process is:
If the “electronic payment” value is missing or incorrect, a number of options exist for handling the customer and probable attacker:
Design Decisions with Resource Metering
A number of options exist when selecting and building a resource metering solution designed specifically to protect the web-based authentication process. Dependant on the nature of the application and the likely customer audience, a number of design considerations should be made:
Hashcash in Web Authentication
Extending the lessons learned in implementing anti-spam “hashcash” solutions, it is a trivial task to adopt similar formatting and cryptographic algorithms and use them as the key resource metering process for web-based application authentication systems. The following example shows one way in which “hashcash” could be implemented.
It is important to note the following about this sample “hashcash” implementation:
Resource Metering Recommendations
Should an organisation choose to implement a resource metering solution, the following recommendations are made:
Resource Metering and Brute Force Attack Vectors
Resource metering can provide a valuable method of preventing or otherwise limiting the susceptibility of a web application’s authentication process to multiple brute force guessing attack vectors. Unlike implementations that rely on incremental timeouts being enforced at the server-side or enforcing access threshold limitations, the use of client-side computationally intensive “electronic payments” can provide a more elegant and robust solution. Key points to a resource metering solution include:
Why not use Mandatory Server-side Timeouts?
Some organisations may have chosen to adopt a mandatory server-side timeout strategy to implement a form of resource metering against brute force attacks. In these schemes, the application server forces all authentication submissions to wait some period of time before responding (e.g. the customer clicks “submit” – the data is sent to the server – the server processes the data and waits 4 seconds before issuing any response to the customer). However, there are a number of limitations to this strategy which may be overcome through the use of client-side imposed resource metering.
Most importantly, by forcing computationally intense processes to occur at the client-side (not just a wait or sleep-type function) it becomes almost impossible to conduct a multi-threaded brute force attack. Consider an application that enforces a 4 second delay at the server-side for each submission. If an attacker opens 1000 simultaneous connections to the server and submits a different customer authentication to each one, after 4 seconds 1000 responses are received by the attacker – corresponding to 250 guessing attempts per second. Using the earlier “hashcash” example but with a 4-second computational load, if the attacker makes 1000 simultaneous connections to the server, it will take approximately 4000 seconds to submit all the guesses – corresponding to 0.25 attempts per second.
Finally, by shifting the onus away from the server environment and on to the client, valuable resources are freed up (including processing overheads, threads, memory allocations and open TCP ports).
The enforcement of resource metering through the use of “electronic payments” is likely to provide valuable protection against many forms of brute force guessing attack vectors commonly employed against web-based authentication systems.
Implementing a system capable of enforcing “electronic payments” is a relatively simple process and likely to result in an immediate strengthening of an application’s security robustness. Implementation lessons learned from anti-spam solutions such as “hashcash” provide a valuable insight in selecting and tuning a resource metering solution. Strategies which incorporate partial “hash-collision” calculations provide an effective granular control over the necessary “electronic payments”, without incurring greater server-side and application functionality overheads.
As an anti brute force guessing protection system, resource metering provides several advantages over more traditional strategies such as fixed or incremental time-outs and account lock-out thresholds. In almost all cases, the system would appear transparent to the customer (and certainly cause no more delays than a traditional submission time delay solution) and is capable of severely limiting automated attacks.
Resource metering through “electronic payments” is recommended for web-based applications that have large customer bases, and/or are likely to be targeted for attack with automated brute force guessing tools. Similarly, organisations that have encountered problems through account lock-out denial of service attacks are also encouraged to review the possible benefits of implementing a resource metering solution.
Web - http://www.hashcash.org/papers/hashcash.pdf