Are there any security measures that are resistant to a brute force attack?

Question

I'm not talking in particular about encryption, but security as a whole. Are there any security measures that can be put in place to protect data and/or a system that can withstand even a hypothetical amount of resources being pitted against it over a hypothetical amount of time?

I think the answer is no, but I thought I'd double check before saying this out loud to people because I'm no security expert.

I should point out, I'm not asking this because I need to implement something. It's idle curiosity. I should also mention that I'm ok dealing with hypotheticals here. Feel free to bring things like quantum computing into the equation if there's any relevance.

Answer 1

One-Time Pad and Shamir's Secret Sharing are two examples of cryptographic algorithms, where some secret value is involved, and which are nonetheless immune to brute force, even against attackers with unlimited computing abilities. Their key feature is "lack of key redundancy": there is no way to filter out "bad" keys. This shows in the fact that OTP requires the secret key to be as long as the encrypted data, and for Shamir's Secret Sharing the total size of the "shares" is even longer than the shared data.

Probabilistically speaking, you get the same property from an AES encryption, as long as you encrypt a single block, and use a key larger than that (e.g. AES-256 for encrypting a single 128-bit data element). The idea is that for a given ciphertext, any plaintext can match (given C and P, there are quite a few keys K such that AES_K(P) = C). Hence the attacker cannot choose the "right" plaintext, even if exploring the whole key space. Of course, reusing the same key for anything else, even encrypting another 128-bit block with AES, would give to the attacker all the redundancy he needs to filter out keys, making brute force viable again (for our hypothetical attacker with a computer bigger than a galaxy, that is).

Algorithms which resist brute force have limited applicability, precisely because of the need for very long keys. In practice, against attackers with earth-based technology, brute force attacks are thwarted by using "long enough" keys. If you consider than an attacker may muster enough computing power to perform 2ⁿ "elementary operations", then you use keys of at least n bits; if you fear quantum computers, you use 2n bits (for anything symmetric, like symmetric encryption or hashing, a quantum computer may theoretically explore a key space of size N with effort sqrt(N), but no better; hence, it suffices to use a twice larger key). Traditionally, we set n=80 but constant progress in technology availability is beginning to force us to bump that value a bit, if we want to keep a convincingly large security margin. Since powers of two are good, it is now customary to use n=128, although the actual limit for Mankind as a whole (in an improbable sci-fi scenario in which all humans cooperate and work for that goal) can be estimated to be somewhere between 90 and 100.

Asymmetric algorithms (asymmetric encryption, signatures...) are much weaker, in that there are known attacks which are much better than "brute force" -- and a quantum computer makes the attacks trivial, for most of them. But since this is not brute force anymore, it is out of scope of your question.

Answer 2

Copying my answer from the question on SO:
Yes, of course there are.

Brute force attacks can accomplish two things: "guessing" some sort of secret (e.g. password, encryption key, etc), and overwhelming resources (i.e. flooding, or Denial of service - DoS).

Any countermeasures aimed at preventing any other form of attack, would be irrelevant to bruteforce.

For example, take the standard reccomendations to protect against SQL Injection: input validation, stored procedures (or parameterized queries), command/parameter objects, and the like. What would you try to bruteforce here? If code was written correctly, there is no "secret" to guess.

Now, if you're asking, "How to prevent brute force attacks?", well the answer would depend on what the attacker is trying to brute force. Assuming that we're talking about bruteforcing a password / login screen, there several options: strong password policy (to make it harder), account lockout (to limit rate of bruteforce attempts), throttling (again limits the attempt rate), and more.

Answer 3

One answer - not really facetious - is "yes, there are many"

One caveat: define resistant

My take on this is that if you can put defences in place that make a brute force attack take long enough for it to be detected and mitigated against, then you have successfully resisted that attack.

In the classic security world, this requires defence in depth. Work out how long an expected worst case attack will take at a particular layer. If your detection process will pick it up within that timeframe then you can do something about it.

Can you slow an attack down? When trying to brute force attacks on passcodes on mobile devices, if the device uses a really slow algorithm then you delay the attack. Whether or not this is helpful depends on your next steps. If you have a process to disable the mobile device then a couple of hours may be enough delay.

If by resistant you mean "will not ever break" then my answer would have to be No. :-)

Answer 4

Well, brute force attacks essentially come down to a probabilistic calculation. Certain variables in the calculation can be controlled to reduce the likelihood of a successful attack, e.g. maximum number of attempts(account lockout), size of search space (password complexity) etc. Ultimately however, if given theoretical complete control (as you mention in your question) over other variables (time) then the probability ultimately return to 1. So in the real world, yes there are some very effective methods for reducing the practicality of a brute force attack, however theoretically a negligible remote statistical chance will remain of successful exploitation.

The above is intended to be specific for the remote brute-forcing of authentication systems.

Answer 5

Are we talking about brute forcing a login screen or a password hash?

If we are talking about a login screen it can be set to disable your account after 10 tries and that is it. After 10 tries not even the right password will unlock it.

If they have the password hash then they can throw as much resources as you want against it. Even $100 in AWS, amazon's compute engine, will buy way more computer time than you could afford to have on site.

People say things like this will take longer than the age of the universe to compute with existing technologies. I am a firm believer that the technologies to come will make future generations laugh at our ignorance. Quantum computers are very limited right now most only have a few bits, and maybe 20-30 at the high end. When it is perfected and we can have 1000's of bits that will be a game changer. There will be more game changers after that.