One-Time-Passwords resist against bruteforce attacks? Immune Alternative?

Question

1. Does a One-Time-Password like Google Authenticator or YubiKey protect against brute force attacks with unlimited computer power?

2. If not, what algorithems are immune to bruteforce attacks against static data on a HHD or USB-Stick? Consider the data is stored on an USB-Storage and you loose the USB-Storage to the attacker who has unlimited computer power available to brute force the password.

Answer 1

You have two different questions. To answer your first question...

Does a One-Time-Password like Google Authenticator or YubiKey protect against brute force attacks with unlimited computer power?

When talking about brute force attacks you have to differentiate between online and offline attacks.

When considering online brute force attacks, I refer you to RFC 4226 Section 7.3.

Truncating the HMAC-SHA-1 value to a shorter value makes a brute force attack possible. Therefore, the authentication server needs to detect and stop brute force attacks.

We RECOMMEND setting a throttling parameter T, which defines the maximum number of possible attempts for One-Time Password validation. The validation server manages individual counters per HOTP device in order to take note of any failed attempt. We RECOMMEND T not to be too large, particularly if the resynchronization method used on the server is window-based, and the window size is large. T SHOULD be set as low as possible, while still ensuring that usability is not significantly impacted.

Another option would be to implement a delay scheme to avoid a brute force attack. After each failed attempt A, the authentication server would wait for an increased T*A number of seconds, e.g., say T = 5, then after 1 attempt, the server waits for 5 seconds, at the second failed attempt, it waits for 5*2 = 10 seconds, etc.

The delay or lockout schemes MUST be across login sessions to prevent attacks based on multiple parallel guessing techniques.

Good implementations of HOTP and TOTP, which are the algorithms used in Google Authenticator should throttle login attempts, thwarting online bruteforce attacks.

When it comes to offline brute force attacks, the attacker has to guess the shared secret used.

RFC 4226 Section 4 has this to say about the secret.

R6 - The algorithm MUST use a strong shared secret. The length of the shared secret MUST be at least 128 bits. This document RECOMMENDs a shared secret length of 160 bits.

Brute force attacks against keys of that length is considered to be impossible.

Moving on to your second question...

If not, what algorithems are immune to bruteforce attacks against static data on a HHD or USB-Stick? Consider the data is stored on an USB-Storage and you loose the USB-Storage to the attacker who has unlimited computer power available to brute force the password.

Ordinary drives do not encrypt their content in any way. Loosing the drive means revealing all the data on it. You must encrypt the data on the drive if you are to have any hopes of it remaining secure. Some drives have encryption built in while you can use software like Truecrypt to encrypt others.

Assuming that the encryption is sound (AES with a proper mode of operation and all that...), it comes down to the password you use to derive the key from. In that situation, the encryption is only as strong as your password. Choosing a long, random password makes it very unlikely that an attacker will be able to guess it.

This is of course assuming that the attacker is computationally bounded which is what you will face in reality. Against attackers with unlimited computing power, you will need a very special class of algorithms known to be information theoretic secure. Some examples of such algorithms are the One Time Pad and Shamir's Secret Sharing.

Answer 2

I assume in my answer that the OP talks about online attacks, since its not quite possible to use OTPs for offline encryption or harddrives.

For the first question, it depends on if you use time-based, event-based or challenge-based OTPs. Im going to talk about the standarized method of 6 digits OTP (HOTP, TOTP, OCRA) variants of authentication now:

Time-based: They are secure against bruteforcing, since the attacker only have 30 seconds to enumerate all codes, provided you do NOT have any synchronization window, and provided you have your TOTP tokens set to change code each 30 second. Even adding a delay on 0.5 second on each login attempt (regardless of if successful or not), which is basically unnoticable to a normal user, will only give the attacker a ability to guess the code with a propability of 1/16666, which is far more harder than guessing a ATM pin with 3 retries, which has a success chance of 1/3333. After 30 seconds, the TOTP code is changed, forcing the attacker to begin from the beginning again. I would still recommend a captcha to prevent bruteforcing since the attacker could strike the 1/16666 by luck.

Event-based: They are NOT secure against bruteforcing, since the same static code is used all the time, until a correct code is presented. The only way to secure a event-based login is to either lock the account and require 2 successive codes to unlock, or use a captcha. A way could be to use both. The 2 successive code system would not be noticable to the end user, since the user would on the attempt to login to his locked account, just simply get "Invalid OTP code, try again with the next code." (like users who really typed their OTP wrong get), user would naturally press the button again to generate the next code. After his enter this second code, the account would have been presented with 2 successive HOTP codes and be unlocked, without the user noticing the account was locked, and without a attacker noticing he entered the correct HOTP (since the account would be locked on first try, thus the attacker would need to have enter 2 successive code, but the attacker could never find out when he entered the first code correctly). Requiring 2 successive codes would immediately reduce the attacker to having to guess something out ot 1/1000000000000 chance, which is equvalient of a 6 character password with A-Z a-z and 0-9. Also, if the attacker enters the first code successfully but the second incorrectly, he would have to begin on the beginning again of all those 1000000000000 codes since the first code is invalidated.

Challenge-based: Here, its dependant on the design. Since the response is proportional to the challenge, its important here to make challenges one-use and expiring. If you program your challenge system to only allow one valid challenge for a account at one time, make sure each challenge is one-use (eg the challenge is invalidated each retry, regardless of correct OTP specified or not), and make sure the challenge is expired when its not used for a time, then the system will basically be infinitely secure against bruteforcing since each attempt would cause the system to change the access code. However, the attacker could strike a 1/1000000 out of luck simply, like winning joker on a exact 6-digit lotto number, why you should have captcha on such logins too.

Google authenticator, when used with Google or Facebook, is a TOTP token, eg time-based OTP, but can also be loaded with HOTP profiles (event-based).

---

When talking about yubikey, using their internal 44-char key or disabling the public identifier giving a 32 char key, the key length, even if its event-based, makes it practically impossible to brute-force a yubikey-protected system, since bruteforcing a yubikey response would be equvalient of bruteforcing a 128 bit (32 hex chars) AES key. So regardless of if you bruteforce the response, or bruteforce the internal yubikey storage key, your work will be as hard as both. A attacker would want to bruteforce the internal key instead since it would gain a greater success.

On your question 2, I do not quite understand what you mean, since its technically impossible to use OTPs if the authenticator Oracle is not completely secure. This means that the process or item that verifies OTPs must be trusted, and using OTPs in a offline scenario just means the attacker could modify the offline process to allow reuse of old OTPs and unlimited attempts.

Answer 3

Nothing in this world is invulnerable to unlimited computer power. Good to know that does not exist such a system.

1. On a real attack scenario, the attack on a OTP protected system depends on how much attempts the attacker can make in the timeframe of the OTP token (generally one minute). If you employ rate limiting on your authentication scheme, employing a fixed delay on every authentication session, you are pretty safe.

2. There are no algorythm immune to offline attack. There are very resistent ones, taking very long times to be broken (billions of years) but nothing is unbreakable. If the attacker can bruteforce your password offline with enough computing power, the security depends on your password. Any data encrypted with a very secure algorythm and protected by a trivial key will be easily decrypted.

Answer 4

1. Yes. Assuming the offline bruteforcing is successful and they have discovered your password, they still cannot log into the system without the one-time auth token. They will not have the opportunity to bruteforce the one-time auth token.

2. N/A because of the 'if not'