lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <20140506144357.GA588@bolet.org> Date: Tue, 6 May 2014 16:43:57 +0200 From: Thomas Pornin <pornin@...et.org> To: discussions@...sword-hashing.net Subject: Re: [PHC] Hashing password while typing On Tue, May 06, 2014 at 07:53:33AM -0400, Bill Cox wrote: > Here's a dumb idea for reducing the pain associated with long password > hashing runtimes. Simply hash the password while the user is typing it. > I'm sure it's an old idea, but I haven't heard it before, so just in case, > I thought I'd post it here before someone patents it. Unfortunately, this idea means that cost sharing becomes possible. Namely, the password hashing function for your idea must be such that it uses a _state_: - Initial state value is S_0 (possibly salt-dependent) - Processing letter i is computing S_{i+1} = f(S_i) (there again, the salt may appear) - After processing n letters (n is the password length), the final hash value is g(S_{n+1}) for some function g() (again, the salt may be used within g()). The core of your idea is that the cost of each f(), and the cost of the finalizer function g(), can be small, sinc what matters would be the overall cost of the processing for all the letters. The problem is that it is wrong: if the attacker has hashed password 'Ultr4Str0ngP@...0rdA' with a cost of 20 times the cost of f() (plus 1 evaluation of g()), then he can compute the hash of 'Ultr4Str0ngP@...0rdB' for considerably less, namely only 1 evaluation of f() and 1 of g(): the attacker can start the computation for the second password with state S_19 (just after processing the 'd'). The general case may depend on the dictionary on which the attacker is working, but we can assume that the cost for the attacker will be mostly reduced, on average, to the processing which follows the last letter. Sure, you have some free CPU time while the user is typing, but your security against the attacker will have to rely on the processing time which happens necessarily _after_ the last password letter was entered. This does not mean that your idea has no merit, but it cannot lead to a significant increase in security. (In a network context, the sending of each letter would leak the password length -- not something which I find really critical, but some people are nervous about it.) > However, the time between typing the last character in his password > and hitting Enter is time well used for hashing. That time is typically very small. Remember that we have two concurrent notions of time: 1. The CPU/memory that the computer can afford on the computation. 2. The user's patience. The cost on the computer is completely unchanged by your idea: regardless of when the computation occurs, the computer still has to to it whole, and that's the cost which defeats attackers. The user's patience is limited to, say, one or two seconds (some people who work in the smart card industry told me that a complete payment operation must be done within 8 seconds, otherwise the user loses patience and panics or becomes angry or both). The count-down for user patience starts when he types the "Enter" key. This calls for two comments: - The password being typically typed "blindly" (there are only '*' characters on the screen), the user has no feedback on what he types. Therefore, he has no reason whatsoever to wait between the last password character, and the "Enter" key. In my case, the time between the last two keystrokes (last charater, then "Enter") is well below 0.1s (the large size of the "Enter" key helps in reducing that delay). Thus, this extra time will contribute to the "patience window" less than +10%. - The extra time to "do computations" is worth anything only if the user's patience was indeed the bottleneck. This does not necessarily apply to any authentication system, in particular a busy system. For instance, suppose that a system has to sustain an average of N user authentications per second. The total amount of CPU that the system can devote to any specific user is then 1/N. Whether the system can start 0.1s earlier does not change much: it won't give it more available power to do its N hashings per second. To some extent, peak loads can be managed by trading latency against CPU: when there are too many authentication requests in a given time frame, we just make clients wait a bit longer, so as to push them into the later times, after the peak. This is sustainable only if the peak is indeed a peak (which stops soon), and the extra latency is not intolerable to the user. To sum up, the gain offered by the use of computational time between the last two keystrokes must be measured against the overall user's patience, and, in that scale, it is very small. > In a challenge-response system, each password guess could hash memory > differently, thwarting precomputation of prefixes. In a challenge-response system: - either the attacker could observe a challenge and the corresponding response, and thus can virtually repeat the experience on his own machines with always the same challenge; - or the attacker cannot see a challenge/response pair and instead must try to respond to a given challenge (an "online dictionary attack"), in which case the password hashing function is completely out of scope. Thus, I don't exactly understand what you are trying to say here. --Thomas Pornin
Powered by blists - more mailing lists