Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

If you enable 2FA for Google Apps the shared secret is 160 bits. The google_authenticator PAM module on the other hand seems to use 80 bits for the shared secret.

According to RFC 4226:

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.

Note "MUST" not "SHOULD". So that makes Google Authenticator non compliant.

What's the rationale behind doing this?

share|improve this question
10  
Great question! I opened an issue on the google-authenticator project page about this. code.google.com/p/google-authenticator/issues/… –  Terry Chia Nov 7 '13 at 2:53
    
I can only speculate that someone judged it good enough as a tradeoff to get the benefit of fitting the secret inside a smaller QR code. Of course that doesn't answer the question why one would risk potentially sacrificing security for convenience. –  pyramids Dec 20 '13 at 14:14

2 Answers 2

up vote 11 down vote accepted
+50

The initial commit for this code already includes the "80 bits" secret key length. It was not changed afterwards.

Now let's analyze things more critically. HOTP is specified in RFC 4226. Authentication uses a "shared secret", which is the value that we are talking about. What does RFC 4226 says about it ? Essentially, there is a a requirement in section 4:

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.

And then section 7.5 explains at length various methods for generating the shared secret.

Now the google_authenticator code generates an 80-bit shared secret with /dev/urandom and then proceeds to encode this secret with Base32: this encoding maps each group of 5 bits to a printable character. The resulting string thus consists of 16 characters, which are written "as is" in a file, with ASCII encoding, meaning that in the file the shared secret has length... 16 bytes, i.e. 128 bits. It is thus possible that the initial confusion comes from that: what is stored has a length which can be seen, in a way, to comply with requirement R6 of RFC 4226.

Of course, the RFC talks about the "shared secret" by calling it "K" in section 5.1 and then proceeds to using it as key for HMAC (section 5.3, step 1). With the shared secret generated with the command-line tool in google_authenticator, what enters HMAC really is a sequence of 80 bits, not 128 bits, even though these 80 bits happen to be encoded as 128 bits when stored (but they are decoded back to 80 bits upon usage). Thus, this 80-bit secret cannot really, in a legalistic way, comply with requirement R6 of RFC 4226. However, the confusion on "length" (after or before encoding) may explain this feature of google_authenticator.

Note, though, that this is just for the command-line tool which can be used to generate the secret as an initial step. The rest of the code supports longer secret values.

(Another theory is that the author wanted to test his code, and, in particular, test the situation in which there is no QR code. In that case, the user must type the code, and an 80-bit secret is easier to type than a 128-bit or 160-bit secret. Possibly, the author first used a short secret to ease development, and subsequently forgot to set it back to its nominal length afterwards. This sort of mishap happens quite often.)


Is it critical ? With my cryptographer's hat, I must answer: no. An 80-bit secret key is still quite strong against brute force, because even with a lot of GPU, 279 evaluations of HMAC/SHA-1 will still take quite some time (with an 80-bit key, average cost of brute force is that of trying half the possible keys, i.e. 279 evaluations). Indeed, HMAC/SHA-1 is deemed "cryptographically strong", meaning that the best known attack is brute force on the key. Let's put figures on it:

HMAC/SHA-1 uses two SHA-1 invocation. So the attack cost is, on average, the cost involved by calling SHA-1 280 times. This page shows benchmarks at 2.5 billions of SHA-1 calls per second for a good GPU. If you are mounting a cracking farm, you will usually use a "middle range" GPU, not a top-notch model, because you will get more power-per-dollar that way. Let's assume that you use 100$ GPU that can do 231 SHA-1 per second (that's a bit more than 2 billions). With a budget of one billion dollars you can have ten millions of such GPU, and they will run the attack in an average of... 652 days.

Of course, 10 millions of GPU take quite some room and, more importantly, use a substantial amount of power. If we suppose that each GPU can run in 50W (a quite optimistic figure), then each attack run will need a bit less than 8 TW.h (terawatt-hours). I live in Canada, province of Québec, where electricity is known to be very cheap due to huge dams and substantial government subventions, resulting in a price of about 0.05$ per kW.h (see the prices). With this price, each attack run will cost around 400 millions of dollars on electricity alone. This does not include cooling prices, because all this energy will become heat and will have to be dissipated (to some extent, a Canadian winter can help). Also, notice that all the GPU will collectively draw 500 MW, a non-discreet amount (that's about half of a nuclear power plant...).

What this amounts to is the following: in practice, an 80-bit key is strong enough. I would be nervous if an 80-bit key protected the launch code for nuclear missiles; however, if the strategic dissuasion was protected by Google's 2FA, I would also be quite nervous for... other reasons.

So we can say that while this 80-bit secret is non-compliant and academically "a bit short", it still is quite strong and does not mandate immediate and drastic actions. It would be cool if the code was fixed; the World won't stop spinning if it is not.

share|improve this answer
1  
It's not just HMAC/SHA-1, but a modulo 10^6 of the actual hash. The attack scenario for a HOTP token generating 6-digit codes is an attacker using previously known codes to arrive at the shared secret, which, considering this truncation, makes the attacker's job even more difficult due to increased chance of collisions. –  mricon Dec 23 '13 at 19:49
    
"The rest of the code supports longer secret values." To be explicit: there is no such limit in the PAM module itself, it will accept any (> 1 byte, and subject to a sanity-check maximum file size of 64kiB) shared secret size. It is only the local secret generation tool that has this (trivially modifiable) limit. FWIW, the most recent source (v2.21) for the Android app has a lower limit of 80 bits (MIN_KEY_BYTES). –  mr.spuratic Dec 24 '13 at 14:54

Like I mentioned in my comment, I have already opened an issue on the Google Authenticator repository. However, there has been no official replies from the developers on it. It appears that the activity on the repository is pretty stagnant.

While there is probably no good explanation for why Google opted for 80 bits instead of the recommended 160 bits as per the RFC, there is a pretty easy fix if this is an important issue.

As far as I can tell, the size of the secret is solely defined in libpam/google-authenticator.c on line 39.

#define SECRET_BITS               80          // Must be divisible by eight

Changing the value from 80 to 160 works and breaks nothing as far as I can tell. This might be viable if you really want the PAM module to be compliant with the RFC.

share|improve this answer
2  
-1 This doesn't answer the question. This just provides a fix (a very obvious one) in effort to rep-whore the bounty. It's much better left as a comment as it doesn't really add anything. This answer basically is "Here's my previous comment + rant about repo + I have no answer + here's something that should be a comment + please gimme da bountiii" –  Adnan Dec 18 '13 at 11:07
3  
adnan, you are being too harsh here. As your question currently stands, it can only be answered by the Google employee that was involved with this. As for the bounty... 50 rep is not going to please any repwhore.... –  Lekensteyn Dec 18 '13 at 11:36
1  
@Lekensteyn Rules are rules. Just because Terry is our friend and we like him, it doesn't mean we look the other way when he provides a non-answer as an answer. If the question can only be answer by a Google employee, then it's probably not best asked here and should be closed not non-answer answered. –  Adnan Dec 18 '13 at 12:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.