We're not using PBKDF2. Were using AES-256, we pad the extra bits and use a random IV for each account. However you can enter a 32 character encryption key and you will get a full 256 bit key for encryption.
It's bad enough that Google's TOTP keys are too short (80 bits, below the required 128 and recommended 160+), especially given the clarity of the spec and the size of their organization, nevermind being the first large-scale rollout. It's also unfortunate that they half-assed their Authenticator app, which hasn't seen an update in over two years. At least they've had the good sense to improve the workflow of regenerating a token for a new device.
I appreciate the problem you're trying to solve and am aware that there tends to be a lot of headache in additional security, but doing this kind of thing provides a false sense of security if not outright lowering the security of what already existed. If I can get access to my MFA tokens by typing in a password, then it's a knowledge factor and not a possession factor. That's one-factor auth with two passwords, like the "security" questions on many banks.
Now our service Authy and it's Tokens are completely different. If you sign-up to Authy.com and use our Tokens, those are:
1. Full 256 bits secret seeds.
2. They are never backed-up.
3. Guaranteed to only exist on 1 phone at any given time.
4. We not only regenerate new tokens for new device, we also allow 1 click remote reset of the device tokens.
5. We have a huge number of improvements over Google Authenticator.
7. Tokens are not 6 but 7 digits long.
This version added support for legacy Authenticator Tokens. The existing Authy tokens like CloudFlare, DNSimple etc are not limited to the Google Authenticator addon.
Google's secret keys are weak but Authy's ones are 256 bits.
And finally, Daniel was wrong about the key derivation, we are actually using PBKDF2. Sorry for the misunderstanding.
I do this manually when setting up the account, I don't do online backups with a third-party service using their crypto code of my google authenticator seeds, though.
Everything I've learned about encryption, I've learned from cperciva. This presentation in particular might be worth your time: http://www.bsdcan.org/2010/schedule/attachments/135_crypto1h...
Recording: http://blip.tv/fosslc/everything-you-need-to-know-about-cryp...
This in particular: "DO: Avoid using passwords whenever possible. DO: Use a key derivation function to convert passwords into keys as soon as possible. DO: Use PBKDF2 if you want to be buzzword-compliant. DO: Use scrypt if you want to be ≈ 2^8 times more secure against serious attackers."
:-(