Pre-generating 'secure tokens'

Question

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
   2. Base-64 URL encode it
   3. Store the hash in our database (Scrypt with N=2^15, r=8, P=1)
   4. 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.

Answer 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.

Answer 2

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.

Answer 3

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).