12 ms·

It's easy to say "use bcrypt" or "use scrypt," but I think it's important to acknowledge the challenges of deploying those functions in large scale high perform

• djb_hackernews 12y ago
  What is authenticating millions of users per second? Facebook has 900M monthly users, 30M per day and probably most of those are cookied in. Even if not that's only 350 authentications/sec...
  • proksoup 12y ago
    Maybe each request needs to be authenticated?
    • stanmancan 12y ago
      If you're authenticating with a username and password on every request you're doing something wrong. Once a user is logged in you should be setting a cookie, session, or some other token to identify the user.
      • ryan-c 12y ago
        I believe HTTP basic auth checks the username and password on every request. It's pretty rarely used these days though.
        • artursapek 12y ago
          Only for secret admin tools :D
      • giaour 12y ago
        A fair number of APIs offer basic auth, even in 2015.
        • carbocation 12y ago
          Hell, the Reddit API uses basic auth in 2015.
          • stanmancan 12y ago
            Yikes... I guess I've been pretty lucky with the API's I've had to work with in the past, I can't recall ever coming across this.
    • orthecreedence 12y ago
      Authenticate once, generate a token, and use the token for auth from that point. I can't think of a case where you'd need to send the u/p on each request.
      • proksoup 12y ago
        Does that token not become a new attack vector that also needs a certain level of security or encryption? Or because it expires, the duration means it doesn't matter if it's compromised?
        • toong 12y ago
          Exactly this. I see that token used - sometimes in the http request header - but most of the time as a param in the GET request, over plain http. Does it even matter if my auth was secure ? I just need to get hold of some access logs and I can impersonate everyone ?
          • uxp 12y ago
            If you're writing http headers out to your apache logs on your production server, you're doing it _severely_ wrong. edit: I'm specifically talking about http basic auth with a precomputed "Authentication: base64($username + $passwd)" header, not a GET of "/foobar?api_key=12345abcd". The latter is obvious in it's failures and is not related to http basic auth.
            • toong 12y ago
              Obviously :-) If you're going after basic-auth-headers, you'd probably be sniffing the network. > Authenticate once, generate a token, and use the token for auth from that point. If that token is passed back and forth in the http url, it ends up at places where it's easy to find/intercept. You can use a gazillion bcrypt rounds to store the password: they still send me a link to a page, including their auth-token.
          • toong 12y ago
            Edit: My intention was to get some input on how to properly use auth-tokens.
    • astrodust 12y ago
      Highly unlikely. If you've got an API or site designed around validating passwords on each request you've failed as an engineer.
      • proksoup 12y ago
        Oh --- so this bcrypt stuff does not apply to session tokens? Those are okay to leave unencrypted in memory or on disk or something?
        • tptacek 12y ago
          No, of course not. The CS problem behind a password hash (or KDF) is to exploit time and memory to convert a low-entropy secret into something with the strength of a high-entropy secret. But when you're securing individual HTTP requests with session tokens, you simply use high-entropy secrets, and thus don't have the password hash problem.
          • proksoup 12y ago
            If users picked really good passwords, full sentences with high entropy --- would we not need to encrypt them? Sorry I think you already explained this, I'm just swimming. I probably should have basic CS understanding to be in this conversation ....
            • tptacek 12y ago
              If users picked 128 bit random numbers as their passwords, any hash function would suffice to store authenticators for them. You'd still want to hash them, because presumably users will re-use the same 128-bit random number on several machines. But it would be infeasible to brute force them, so MD4 would do just fine. There is no reason to hash a secure cookie, because they aren't used across several machines. The compromise of a stored session key implies that every system where that cookie is valuable is also compromised.
              • 12y ago
  • nly 12y ago
    You're right, authentication rates are low. But Moxies point of concern with regard to requiring a heavier CPU and memory commitment on the server is still valid, particularly when faced with malicious traffic. You need to make sure your login system can handle malicious clients, brute-force attempts from individual IPs, or against particular accounts, dropping back to CAPCTHAs or some other means of resource control when things look bad. This isn't a particularly easy problem to solve, and if you do it incorrectly you open yourself and your users up to a denial-of-service. IMHO, some of the new fancy password-based authentication protocols, like AugPAKE, which do hashing client-side, might ease this problem... but they're still stateful (SYN floods anyone?) and therefore still depend upon good DoS protection. Edit: Oh poop, you're djb.
    • tptacek 12y ago
      That's not Daniel Bernstein.
      • sarciszewski 12y ago
        I have to admit, when I saw the username, I sorta hoped it was.
    • worklogin 12y ago
      There are separate concerns of brute-force mitigation that people should look into regardless of their hashing technology. Things like exponential-growth cooldowns per IP/user account (with lots of caveats to prevent cooldown-DDoS) should be used. http://stackoverflow.com/questions/549/the-definitive-guide-to-form-based-website-authentication http://stackoverflow.com/questions/549/the-definitive-guide-...
    • IvyMike 12y ago
      > Moxies point of concern with regard to requiring a heavier CPU and memory commitment on the server is still valid, particularly when faced with malicious traffic.h How about this: Save two hashes, one low cost, one high cost--both must pass for login. Don't run the high cost unless the low cost one works first. Note: not a security guy, so I'm probably overlooking something silly. Edit: the two responses below (thus far) are reasons you should not do this. Duh on my part.
  • hackcasual 12y ago
    Not normally, but it does open up a DoS vector that at the very least will prevent legitimate users from logging in.
    • tptacek 12y ago
      It's one of thousands of DoS vectors, all of which are addressed the same way: coarse ad-hoc anomaly filters.
      • mox1 12y ago
        But its a non-obvious (imo) attack vector opened simply by switching to scrypt / bcrypt. In a perfect world, quality web apps have rate limiting built into their auth schemes. But it's important to acknowledge these two algorithms will put a much heavier burden on your CPU.
        • tptacek 12y ago
          Most DoS vectors are non-obvious, so this seems like a very weak reason to change the way you do password hashing.
  • yxhuvud 12y ago
    Think infrastructure rather than appliances like Facebook. What do you think happens if certain state keeping big authentication servers or routers reboot? We have a customer that has more than one million users on a GGSN (which is a glorified router). If that happen to restart every single customer will immediately and automatically try to reconnect. The systems involved actually doesn't tend to handle this many in reality (the ISP in question restrict it to some 20-30k/s to our system). These systems are starting to be better at supporting keeping state through restarts, but there can still be pretty impressive spikes of authentication traffic if the wrong system is rebooted (or crashes!).
• snowwrestler 12y ago
  This makes sense, but--forgive my ignorance--what site needs to process millions of password authentications per second? Don't most sites hash/compare the password once at login, then issue an ephemeral token to maintain the authenticated state? Is Facebook, for example, hashing my actual password for every HTTP request that my Facebook mobile app makes?
• scott_karana 12y ago
  Even though the choice of scrypt might necessitate dedicated authentication servers at "web scale", I don't see any better options on the table. Hardware is cheaper than trust, or litigation. (And there's always rate-limiting)
• enraged_camel 12y ago
  >>but using scrypt or bcrypt server-side at effective difficulty levels will either destroy your L1/L2 cache or exceed your CPU budget. Perhaps this is the real issue: lack of sufficient budget for CPUs that can reliably get the job done is a reflection on the priority organizations place on information security.
  • dsp1234 12y ago
    For an attacker, a great way to cripple an organization that uses scrypt/bcrypt easily is just to attack logins. If each login takes 1 second of work, then it's easy to overwhelm any system system using a host of bots on distributed hosting systems. Say an attacker can hit with a mere 1 req/s from 100 hosts (very easy with aws/digitalocean/hetzner/etc), then that's 100 CPU-seconds of work just for logins. Comparatively, if they hit with 100 req/s for normal front-end data, caches can easily handle that. So really, adding these types of login checks to any publicly available login page ends up creating an on-demand DDOS target. From the password cracking side, the asymmetry comes from the fact that an organization has to have X amount of server resources to service Y number of requests, but an attacker can utilize the same X amount of server resources to service just one thing, breaking the exact password they are looking for. This is further exaggerated by the fact that generally for an organization those X server resources also need to more than just service logins (like actually serve content or API data).
    • nknighthb 12y ago
      If someone can't easily figure out how to create per-IP login attempt throttles, I suspect their application has far more gaping holes in it.
      • pixl97 12y ago
        There are botnets with hundreds of thousands of hosts in them. There are proxies and NATs with hundreds or thousands of users behind them. How do you balance those out?
        • 12y ago
• bradleyjg 12y ago
  I think if the most efficient way to attack the hashes is to buy the same hardware you use to process logins than in some sense you've already won. It's where the attacker can buy GPUs or program an FPGA and dollar for dollar make orders of magnitude more guesses per second than you do verifications per second that you want to avoid. To the larger point, I do agree that some of this starts to look to be a bit of security theater. If a user picks a laughably weak password, and the server is completely compromised, it doesn't much matter what password storage scheme you used, and on the other hand if the user picks a great password, especially if he never reuses it, the consequences of losing that hash is limited.
  • vectorjohn 12y ago
    I think maybe you missed it a bit. If attackers can spend a bunch of money to guess enough passwords to be useful in, say, weeks, then if you make it take 100 times as long, now it's years. And using scrypt with a decent work factor isn't 100 times harder, its tens or hundreds of thousands of times harder. Additionally, I think one of the benefits of scrypt is that it is specfically designed to deter GPU or FPGA attacks because it is memory intensive instead of just CPU.
• j_s 12y ago
  What are the downsides of avoiding this by using scrypt/bcrypt client-side (for a web app)?
  • bradleyjg 12y ago
    There may be other downsides, but the one that immediately comes to mind is that some of your client's devices may well be extremely resource constrained. The obvious type of device that comes to mind is mobile phones but there's also set top boxes and many other non-full-blown-PC web clients around. What ever work factor downtuning you need to do to conserve server resources may well be dwarfed by the downtuning you need to do to get bcrypt to run in a reasonable amount of time on a mid range smartphone.
    • aetherson 12y ago
      Is this still true? I see some articles suggesting it from around the time that Android 2.1 or lower was a "mid range" smartphone. It doesn't seem like it ought to be true. Running bcrypt in Ruby with default settings takes small fractions of a second on a few-years-old Macbook Pro. Even if the smartphone is 100x slower, it should be within the realm of reason to run a process that might take 1-2s once every thirty minutes or so. Now, I'll buy that if your target device is not a mid-range smartphone, but "the very bottom of the smartphone market," bcrypt might be too expensive.
  • zwegner 12y ago
    Correct me if I'm wrong (I'm no crypto expert), but doesn't client-side hashing take away the main point of hashing passwords in the first place? If a password database is compromised, the hashes don't even need to be cracked, they can just be sent straight to the server for authentication. The only thing it seems to help with for the client<->server case is password reuse between websites, and that's only if they don't use the same client-side hashing scheme. Moxie seemed to hint at this problem by mentioning local bitcoin wallets--client-side hashing only makes sense if you're not sending the hash anywhere.
    • 12y ago
• deleted 12y ago
  [deleted]
• tptacek 12y ago
  1. Empirically: most of the applications I reviewed that used bcrypt simply used the defaults. 2. Even with a lower work factor, bcrypt is drastically better than salted SHA. 3. Companies with auth loads so high that they really need to tune bcrypt should also be using dedicated auth servers, which (a) improve security in other ways and (b) allow for a lot of flexibility in handling work factors.
  • hackcasual 12y ago
    If they're using dedicated hardware, why not use smartcards to salt the hash. From the article, even 74kh/s is going to tear through a lot of passwords, but with a secure element in the mix, offline attacks go nowhere.
    • tptacek 12y ago
      The purpose of a password hash is to protect the password authenticators in the event the database is compromised. If you define away the possibility of a database compromise, just store them in plaintext.
      • hackcasual 12y ago
        I'm not trying to define away the possibility of a database compromise, I'm integrating a secure element into the hashing scheme that can compute an HMAC without exposing its key.
        • tptacek 12y ago
          Wherever you're storing the key, where it's inaccessible to attackers, just store the password. I'm not even saying that keyed hashes are a bad idea. I'm saying they're orthogonal to the question being discussed on the thread.
  • mtrimpe 12y ago
    > 1. Empirically: most of the applications I reviewed that used bcrypt simply used the defaults. Isn't that a security risk of it's own though? Wouldn't creating a rainbow table for (non-salted) passwords hashed with the default bcrypt settings then make sense again?
• mrb 12y ago
  > I think this is just a fundamental asymmetry Actually the Password Hashing Competition has shown this asymmetry can be exploited to the server's advantage: one of the ideas being studied is called server relief. For example instead of storing the scrypt hash on the server you store the SHA256 hash of the scrypt hash (and the salt alongside), and ask the client to send the scrypt hash to authenticate. This way the per authentication cost to the client is expensive (one scrypt hash) but the cost to the server is cheap (only one SHA256 hash). Attackers cannot take shortcuts. They cannot send random scrypt hashes to the server while skipping the scrypt computation step, because the space of possible scrypt hashes is just too large to brute force. The only downside of server relief is that you need custom code on the client-side to do the computation. So it works with javascript in browsers, but not with traditional clients like an IMAP or POP3 mail app. Edit: @__david__: yes you could SHA256() only the hash part of the scrypt hash, as opposed to the hash & salt parts. It is an implementation detail --not really important. And regardless of how you do it, if the DB get stolen the SHA256 hashes are useless to authenticate. Edit: @espadrine: no, breaking a SHA256(scrypt()) hash is no easier than breaking a scrypt() hash. Server relief with SHA256 introduces no weaknesses. It is strictly more secure than standard scrypt hashes. Edit: @plantbased: I recommend against MD5(scrypt()), because it is likely preimage attacks will be found on MD5 in the near future, so someone stealing your database of MD5(scrypt()) hashes will be capable of computing an arbitrary scrypt hash that authenticates to a given user. But you could certainly do MD5-crypt(scrypt()) with MD5-crypt being the salted & iterated version by PHK.
  • __david__ 12y ago
    I like that idea. But why do you store the salted SHA256 of the scrypt hash and not the scrypt hash directly? Edit: Thinking about it more, I'm guessing it is for the case where your DB gets stolen. With the salted hashes, attackers can't just send the direct scrypt hash down to the server to get authenticated.
    • plantbased 12y ago
      The whole idea of salts is to prevent rainbow table attacks i.e. you can't use precomputed hashes. In this case you'd need to precompute an SHA256 of a dictionary of scrypt hashes which would have been computed from a dictionary of english words. In practical terms, if you steal the DB and wanted to reverse passwords, you'd need to scrypt lets say 100 million words, then SHA256 them, then compare them to what's in the DB. The original blog entry argues (or maybe it was the post on the same site that linked to) that we should use more compute intensive hashing algorithms, rather than relying on salts. scrypt is definitely more compute intensive. So if you didn't use a salt and wanted to throw a 100M word dict at this, how long would that take on decent hardware to create the rainbow table of 100M words which could be used repeatedly against stolen dictionaries? On a decent GPU you can do around 1.2 billion SHA256 hashes per second. So the SHA256 step is trivial. ASIC bitcoin hardware can do around 4.5 million scrypt hashes per second: https://bitcoinmagazine.com/13000/new-benchmark-scrypt-mining/ https://bitcoinmagazine.com/13000/new-benchmark-scrypt-minin... So you could create your rainbow table to attack the non-salted version of this in around 25 seconds. A salted version of this same system would need the scrypt to be salted because SHA256 is so fast. If you just salted the SHA256 you'd be able to use a precomputed scrypt rainbow table and then you only have to compute the salted SHA256's which as you can tell from my benchmark above is very fast. So clearly the salt is needed and you need to compute scrypt(salt + password) -->> send to server and then SHA256(scryptHash). Note that you don't need to add the salt on the SHA256 side because you've already defeated a rainbow table attack by your initial salting. So how fast could you attack a salted system like this using GPU's for your SHA256 and ASICS for your scrypt based on the benchmarks above? You can pretty much ignore the SHA256 step because it's so fast, so you'd get around 4.5 million guesses per second using ASICS doing scrypt. Compared to 1.2 billion guesses using a GPU for SHA256, that's not too bad.
• jjarmoc 12y ago
  You raise a good point, but one that's probably an issue to a minority of those implementing applications that require an authentication component. Sure, the Twitbooks, GooSofts and FaceLinks of the world that deal with large numbers of concurrent authentications have to think a bit more about this, and that's fine; I would expect that they would be well equipped to do so, and likely also run dedicated authentication servers and carefully considered systems. I can probably count on one hand the number of times I've seen an application use bcrypt or scrypt and define their work factors. The common case seems to be sticking to the defaults that their chosen library ships with. While these may be somewhat less than ideal, it's universally true that these schemes are stronger than salted passwords fed to a fast cryptographic hash.
• erkkie 12y ago
  Examples of sites where this is an issue? Serious question, where does scrypt/bcrypt overhead get to be important enough compared to the rest of the traffic the site has to handle?
• NKCSS 12y ago
  It's been said before in previous discussions, but have not seen it here: Just make your own 'password cracking cluster' to make sure you can handle the auth workload with ease.
• zaroth 12y ago
  Moxie hit the nail on the head. It's absolutely a fundamental asymmetry. Slow hashes can protect strong passwords, and not much else. And if you use a password manager to generate strong passwords, then you are going to throw that password out anyway. In the time it takes for your users to give up on the hourglass, assume their login request is hung, and start double-clicking submit, you have now DDoS'd yourself. That's about 750ms I think... Also, try this sometime -- clear your cookies and try to login to Google, or Twitter, or Facebook. Time how long it takes before you see the first byte of a session cookie. Hint: Not Long Enough. Password hashing is embarrassingly parallel. The botnets don't cost the attackers anything to hash your password on 100,000 CPUs all at once, after they've decided to target you. Moore's law? Also not helping. We need something better. I'm working on just that, I'm sure it will have more than it's share of naysayers, but I'm giving it my best.