Do emergency scratch codes have enough entropy even when default rate limit is used?

[sudomain]

This is my first time doing math on GH, sorry if it's messy: The current scratch codes are numeric and of length 8 so each scratch code has 10^8 or 100,000,000 key space possibilities. The default of generating 5 of these codes means that a brute-forcing attacker has to (on average) guess (10^8)/5 or 2(10^7) or 20,000,000 possibilities before finding a valid scratch code. The default rate limiting setting is to limit guesses to "no more than 3 login attempts every 30s." which equates to 1 attempt per 10 seconds. If 1 attempt can be made per 10 seconds, then it will take (on average) 2(10^7) 10 or 2(10^8) seconds for the attacker to find a valid scratch code. 2*(10^8) seconds is about 6.34 years. So it would take ~6 years for a brute forcing adversary to go through the first 20% of the key space possibilities and a maximum of ~31 years to search through all of key space (though they will on average find a valid scratch code way before this).

I personally don't use the defaults (no scratch codes, paper only backups of my secret key, ...), but given these numbers, I think the scratch codes should increase in length and pool of characters allowed.

EDIT: yes, I realize this also assumes that the attacker has compromised other authentication material, such as ssh keys

[ThomasHabets]

The bigger problem is the normal codes. At least scratch codes are 8 digits. Without extra brute force protection that's three valid codes at any point in time, one try every 10 seconds. Average of 1000000/3/2*10/86400=19 days.

Probably the right thing to do here is to create a new PAM module that you can place between the password and the OTP. Something like:

… pam_unix
… pam_increment_and_deny_if_too_high
… pam_google_authenticator
… pam_reset_counter

Of course that doesn't help if the attempts are careful to not trigger the counter between valid logins.

[sudomain]

I hadn't thought about the entropy of the one time codes. A bit off-topic, but may I open an issue/feature request to allow letters and or symbols in the OTP? As far as I can tell, the TOTP RFC(6238) makes no mention of the requirement that the one time codes be strictly numeric. It defers to the HOTP RFC in which section 4 R4 reads:

R4 - The value displayed on the token MUST be easily read and entered by the user: This requires the HOTP value to be of reasonable length. The HOTP value must be at least a 6-digit value. It is also desirable that the HOTP value be 'numeric only' so that it can be easily entered on restricted devices such as phones.

Expanding the character pool of the OTP will allow more entropy while keeping the length short. Plus it's hard for me to imaging a PAM module being used with "restricted devices such as phones". Maybe numeric codes can be the default and alphanumeric with symbols can be opt-in using a --otp-chars CHARS flag?

[ThomasHabets]

Changing the number of digits would be one thing. At least enabling 8 digits, as I believe some apps do that. But changing to alphanumeric seems infeasible. If we change it here in the PAM module it would require adding that to the Key URI protocol, and adding it to all the apps. I wouldn't want to do this without buy-in from at least some of the app developers.

And for such an effort it seems to be that it'd be better to switch to U2F.