Method for securing password and user credentials
Publication Date: 2015-Jan-30
The IP.com Prior Art Database
The user password is combined with a global salt value which could be any pre-selected high entropy bit string. A one way function such as a cryptographic hash function is applied to the result. The second value in turn is combined with a user-specific salt (not stored anywhere) that is generated per-user based on any arbitrary criteria (such as a combination of the last few bits in the user's password, user-id, date of user creation, etc). This salt combined with the prior value and hashed using a one way function such as a slow cryptographic hash function such as sha-256 (also selected per user based on arbitrary criteria.). This process may be repeated for key strengthening and increasing stored key entropy. K <= g(P,G) S <= f(user_info) Z <= h(K,S) where P is the user password, G is the global salt, g is the entropy function, f is the user specific salt generation function and h is the user-specific hash function.
Page 01 of 6
Secure Credential Storage
(408) 235 5711
CA-116 Santa Clara
Background of the invention
The prior art for secure storing of credentials consists of appending the user's password with a randomly selected bit string called salt and computing its hash and storing the hash value along with the salt in the credential database. The security of the system does not depend on the salt from being a secret.
Leaks and attacks
The password file or database may fall into the hands of an attacker, usually due to human error but sometimes due to intrusion. The attacker then can perform various forms of attacks on the password data at his leisure and with sufficient hardware power, compromise many credential stores.
Hash dictionaries, chains and Rainbow tables
Hash dictionaries are precomputed reverse lookups for the most common hashes. Large dictionaries for common hash function values of common passwords exist
Hash dictionaries however, are too large to store in memory, so an attacker can use a hash chains or rainbow tables to compact the amount of memory used, which allows for a larger set of hashes to be held in memory.
Hash chains and Rainbow tables in brief
Hash chains and rainbow tables work similarly to reduce memory footprint and we treat them similarly here for simplicity. The basic idea behind both is to create chains of candidate passwords and their hashes and then collapse each chain, retaining only the endpoints. The idea is that the chain is constructable and as long as an endpoint is found, the attacker can replay the chain's computation and recover the password.
If h() is the hash function and p() is the psuedorandom map function, a possible chain on a 3 character password space may look like Fig. 1.
Page 02 of 6
h(aba) p(2a36) h(cjk) p(f347) aba
The chain shown in Fig. 1 is collapsed by storing only the end-points:
tyu ⇒ aba
This reduces storage size for the hash chain. When a hash is found, say f347, the chain can be replayed until tyu is found. At this point, computation retraces from aba until the value that produces f347 is obtained. Therefore the password would be ckj.
Rainbow tables are similar but use different pseudorandom functions at each level to reduce collisions.
Salting and Key stretching
Salting and Key stretching can greatly reduce the effectiveness of broad based rainbow table attacks but does not eliminate the possibility of an attacker creating a rainbow table to attack select accounts such as root, administrator, etc.
For example, our three character password hash chain above is equivalent to a hash chain for one character salt plus a two character password. With some minor modifications, the attacker can still determine in the replay example above that the salt is c and the user's password is kj. A sufficiently large salt slows the attacker but does not impede the use of rainbow tables.
Summary of invention
The invention attempts to block this form of attack...