[cryptography] Twitter security backup codes

Simon Josefsson simon at josefsson.org
Sun Aug 11 15:52:54 EDT 2013


There is a nice article about improvements to Twitter logins:

https://blog.twitter.com/2013/login-verification-on-twitter-for-iphone-and-android

The general idea to "bless" new login attempts using one of your devices
that you carry with you seems like a cost-effective idea to improve
security for large sites.  I'm only surprised it took us this long to
see it happen...

But what caught my eye was the following paragraph about backup codes
(used when you forget your device, or more interestingly, when your
device doesn't have network connectivity, which could suggest it will
end up being used more often than for device recovery):

    To make the backup code work without sharing secrets, we use an
    algorithm inspired by S/KEY. During enrollment, your phone generates
    a 64-bit random seed, SHA256 hashes it 10,000 times, and turns it
    into a 60-bit (12 characters of readable base32) string. It sends
    this string to our servers. The phone then asks you to write down
    the next backup code, which is the same seed hashed 9,999
    times. Later, when you send us the backup code to sign in, we hash
    it one time, and then verify that the resulting value matches the
    value we initially stored. Then, we store the value you sent us, and
    the next time you generate a backup code it will hash the seed 9,998
    times.

The S/KEY system security was O(2^64) because hash truncation was to 64
bits, and to mount an attack you can pre-compute a table and there is a
space/time-tradeoff if you want to reduce O(2^64) storage.  (See for
example https://www.miknet.net/security/otp-weakness for details, you
could have O(2^42) storage and O(2^22) work.)

Twitter appear to truncate to 60 bits.  Does this lead to
precomputable/compressable O(2^60) security of their system, or am I
missing something in the still too-warm-to-think summer wheater...?

/Simon


More information about the cryptography mailing list