2

In our web app we make good use of single use tokens. For example, when somebody creates any of the three "accounts", resets their password, or any other number of things that require random single-use tokens, we:

  1. Generate 32 random bytes from the OS' CSPRNG
    1. Base-64 URL encode it
    2. Store the hash in our database (Scrypt with N=2^15, r=8, P=1)
    3. Give the user the single-use token (usually in the form of a URL)

This all works fine. However, through profiling we've noticed that some of our API calls can take a couple seconds because they have to both verify and create tokens. Some API calls will use Scrypt three or more times.

While it's not terrible, we'd like to speed up the API calls if possible.

I've floated the idea of pre-generating some random tokens, but I'd like a second opinion before I go head and start on this.

There are two ways I think we could go about this. First, we'd simply create (token, hash, salt) triples and store them in-memory. The down side to this is we'd have the unencrypted tokens just sitting there, and an attacker could get them and use them. However, that'd require access to the specific AWS instance and single-use tokens would be the least of our concerns in that situation.

The second would be to use a vault of some kind, so the tuples are still sitting in-memory, but are encrypted. This sounds safer, but still requires the password to the vault to be sitting somewhere and so the attacker still would have access to it if she had access to the AWS instance.

Thoughts? I'm a little wary of this idea, but I'd really like to cut down some API calls from three seconds down to less than one second.

  • 1
    With the operation being so slow, it may be possible for a single user (or small number of users) to implement a denial of service attack on your site. That may be impossible due to other security features of your site, but it becomes a concern. – Neil Smithline Mar 11 '16 at 23:56
  • @NeilSmithline that is true! We rate limit and have some other security features to prevent this. But thanks! – Eric Lagergren Mar 12 '16 at 0:11
  • You don't mention having a TTL, so I want to add that it is generally appropriate to have a relatively short lifespan on such tokens. Generally a few hours to a few days. I didn't put this in my answer as it's not directly related to your question, but I wanted to mention it. – Neil Smithline Mar 12 '16 at 0:12
  • @NeilSmithline we have a 20 minute TTL for most sensitive (e.g. Password) tokens. Longer for stuff like account creation – Eric Lagergren Mar 12 '16 at 0:24
1

Summary: There is no need to use scrypt on truly random data like yours. Just use a secure hash like SHA256 and you'll be fine.

Explanation: Hashes like SHA256 are, to the best of our knowledge, irreversible. The only way to go from a hash to the original text is to use a combination of precomputation and brute-forcing. It turns out that pre-computation is very successful at storing passwords because people choose weak and predictable passwords. This is why the whole science of password hashes needed to be created.

However, has 256-bits of entropy in it. It is unfeasible to generate a rainbow table (we don't have room to store it on this planet) or brute force (the sun will blow up before we get halfway through) a simple SHA256 hash over such a large input space.

So use the speedy SHA256 on your random data and rest assured that it is uncrackable.

  • I think this is probably the best solution. I originally chose Scrypt because I was already using it and didn't want to have a bunch of different crypto for different purposes, but I think this is the route I may have to go. Thanks! – Eric Lagergren Mar 12 '16 at 0:12
  • So, went and updated the code today. API calls are now at around ~200ms, down from ~3 seconds before. Thanks for letting me rubber duck debug (kinda, sorta) and telling me what I should've done in the first place! – Eric Lagergren Mar 14 '16 at 0:31
  • @eric_lagergren happy to help! – Neil Smithline Mar 14 '16 at 0:34
0

Rather than running scrypt on a random token, for these sorts of situations I'd generate an hmac. Here's an example from reddit's open-source email unsubscribe token code:

def generate_notification_email_unsubscribe_token(user_id36, user_email=None,
                                                  user_password_hash=None):
    """Generate a token used for one-click unsubscribe links for notification
    emails.
    user_id36: A base36-encoded user id.
    user_email: The user's email.  Looked up if not provided.
    user_password_hash: The hash of the user's password.  Looked up if not
                        provided.
    """
    import hashlib
    import hmac

    if (not user_email) or (not user_password_hash):
        user = Account._byID36(user_id36, data=True)
        if not user_email:
            user_email = user.email
        if not user_password_hash:
            user_password_hash = user.password

    return hmac.new(
        g.secrets['email_notifications'],
        user_id36 + user_email + user_password_hash,

If you need to make sure it's only used once, you can additionally insert that value into your database and delete it once used, as you're doing currently.

  • I think an HMAC is a clever idea, but I'm unclear what you are proposing running the HMAC over. – Neil Smithline Mar 11 '16 at 23:52
  • It should probably include some data specific to the user, as well as a secret that's only used for that particular purpose (so you can't re-use an hmac from, say, email unsubscribe for password reset). In this particular example, it also includes the user's password hash so that it becomes invalid when the password is changed. – Xiong Chiamiov Mar 12 '16 at 1:18
0

You say that you worry about attackers getting access to the tokens if you pre-generate them. Although this does technically give them a larger window, it would be much harder for an attacker to monitor your secure token being generated anyway.

The reason we hash passwords is so future breaches in the years to come don't reveal passwords. In this case, only 1 minute into the past breaches are an issue. If someone breaches you 1 minute ago, they can probably breach you know as well.

My suggestion is this:

  • Have a program that generates, say, 600 secure tokens. Isolate this program's memory from other programs and processes as best you can. (For example, make it a different user than your other stuff.)
  • Any process can request a token from the program. When a token is requested, it is removed from the pool.
  • Depending on how paranoid you are, have the program discard the 10 oldest tokens every second and generate 10 new ones. This way, any token can only last a minute.

Neil's answer is also correct (if for some reason Sha256 is acting slow for you, you can use the above).

  • I think the token is just a random bit string that is cheap to generate. It's the scrypt that is used for secure storage that is slow. – Neil Smithline Mar 13 '16 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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