Salt (cryptography)

Last updated

In cryptography, a salt is random data fed as an additional input to a one-way function that hashes data, a password or passphrase. [1] Salting helps defend against attacks that use precomputed tables (e.g. rainbow tables), by vastly growing the size of table needed for a successful attack. [2] [3] [4] It also helps protect passwords that occur multiple times in a database, as a new salt is used for each password instance. [5] Additionally, salting does not place any burden on users.

Contents

The way salting is typically done is that a new salt is randomly generated for each password. The salt and the password (or its version after key stretching) are concatenated and fed to a cryptographic hash function, and the output hash value is then stored with the salt in a database. The salt does not need to be encrypted, because knowing the salt would not help the attacker. [5]

Salting is broadly used in cybersecurity, from Unix system credentials to Internet security.

Salts are related to cryptographic nonces.

Example

Without a salt, identical passwords will map to identical hash values, which could make it easier for a hacker to guess the passwords from their hash value.

UsernameString to be hashedHashed value = SHA256
user1password123EF92B778BAFE771E89245B89ECBC08A44A4E166C06659911881F383D4473E94F
user2password123EF92B778BAFE771E89245B89ECBC08A44A4E166C06659911881F383D4473E94F

Instead, a salt is generated and appended to each password, which causes the resultant hash to output different values for the same original password.

UsernameSalt valueString to be hashedHashed value = SHA256 (Password + Salt value)
user1D;%yL9TS:5PalS/dpassword123D;%yL9TS:5PalS/d9C9B913EB1B6254F4737CE947EFD16F16E916F9D6EE5C1102A2002E48D4C88BD
user2)<,-<U(jLezy4j>*password123)<,-<U(jLezy4j>*6058B4EB46BD6487298B59440EC8E70EAE482239FF2B4E7CA69950DFBD5532F2

The salt and hash are then stored in the database. To later test if a password a user enters is correct, the same process can be performed on it (appending that user's salt to the password and calculating the resultant hash): if the result doesn't match the stored hash, it could not have been the correct password that was entered.

In practice, a salt is usually generated using existing data such as a user's ID. If a completely random salt is created instead, it is stored in the hash (such as by prepending it, appending it, replacing every nth character with it, or so on) so the system can later recover it.

Common mistakes

Salt re-use

Using the same salt for all passwords is dangerous because a precomputed table which simply accounts for the salt will render the salt useless.

Generation of precomputed tables for databases with unique salts for every password is not viable because of the computational cost of doing so. But, if a common salt is used for all the entries, creating such a table (that accounts for the salt) then becomes a viable and possibly successful attack. [6]

Because salt re-use can cause users with the same password to have the same hash, cracking a single hash can result in other passwords being compromised too.

Salt length

If a salt is too short, an attacker may precompute a table of every possible salt appended to every likely password. Using a long salt ensures such a table would be prohibitively large. [7] [8]

Benefits

To understand the difference between cracking a single password and a set of them, consider a file with users and their hashed passwords. Say the file is unsalted. Then an attacker could pick a string, call it attempt[0], and then compute hash(attempt[0]). A user whose hash stored in the file is hash(attempt[0]) may or may not have password attempt[0]. However, even if attempt[0] is not the user's actual password, it will be accepted as if it were, because the system can only check passwords by computing the hash of the password entered and comparing it to the hash stored in the file. Thus, each match cracks a user password, and the chance of a match rises with the number of passwords in the file. In contrast, if salts are used, the attacker would have to compute hash(attempt[0] || salt[a]), compare against entry A, then hash(attempt[0] || salt[b]), compare against entry B, and so on. This prevents any one attempt from cracking multiple passwords, given that salt re-use is avoided. [9]

Salts also combat the use of precomputed tables for cracking passwords. [10] Such a table might simply map common passwords to their hashes, or it might do something more complex, like store the start and end points of a set of precomputed hash chains. In either case, salting can defend against the use of precomputed tables by lengthening hashes and having them draw from larger character sets, making it less likely that the table covers the resulting hashes. In particular, a precomputed table would need to cover the string [salt + hash] rather than simply [hash].

The modern shadow password system, in which password hashes and other security data are stored in a non-public file, somewhat mitigates these concerns. However, they remain relevant in multi-server installations which use centralized password management systems to push passwords or password hashes to multiple systems. In such installations, the root account on each individual system may be treated as less trusted than the administrators of the centralized password system, so it remains worthwhile to ensure that the security of the password hashing algorithm, including the generation of unique salt values, is adequate.[ citation needed ]

Another (lesser) benefit of a salt is as follows: two users might choose the same string as their password. Without a salt, this password would be stored as the same hash string in the password file. This would disclose the fact that the two accounts have the same password, allowing anyone who knows one of the account's passwords to access the other account. By salting the passwords with two random characters, even if two accounts use the same password, no one can discover this just by reading hashes. Salting also makes it extremely difficult to determine if a person has used the same password for multiple systems. [11]

Unix implementations

1970s–1980s

Earlier versions of Unix used a password file /etc/passwd to store the hashes of salted passwords (passwords prefixed with two-character random salts). In these older versions of Unix, the salt was also stored in the passwd file (as cleartext) together with the hash of the salted password. The password file was publicly readable for all users of the system. This was necessary so that user-privileged software tools could find user names and other information. The security of passwords is therefore protected only by the one-way functions (enciphering or hashing) used for the purpose. Early Unix implementations limited passwords to eight characters and used a 12-bit salt, which allowed for 4,096 possible salt values. [12] This was an appropriate balance for 1970s computational and storage costs. [13]

1980s–

The shadow password system is used to limit access to hashes and salt. The salt is eight characters, the hash is 86 characters, and the password length is effectively unlimited, barring stack overflow errors.

Web-application implementations

It is common for a web application to store in a database the hash value of a user's password. Without a salt, a successful SQL injection attack may yield easily crackable passwords. Because many users re-use passwords for multiple sites, the use of a salt is an important component of overall web application security. [14] Some additional references for using a salt to secure password hashes in specific languages or libraries (PHP, the .NET libraries, etc.) can be found in the external links section below.

See also

Related Research Articles

<span class="mw-page-title-main">Password</span> Used for user authentication to prove identity or access approval

A password, sometimes called a passcode, is secret data, typically a string of characters, usually used to confirm a user's identity. Traditionally, passwords were expected to be memorized, but the large number of password-protected services that a typical individual accesses can make memorization of unique passwords for each service impractical. Using the terminology of the NIST Digital Identity Guidelines, the secret is held by a party called the claimant while the party verifying the identity of the claimant is called the verifier. When the claimant successfully demonstrates knowledge of the password to the verifier through an established authentication protocol, the verifier is able to infer the claimant's identity.

In cryptanalysis and computer security, a dictionary attack is an attack using a restricted subset of a keyspace to defeat a cipher or authentication mechanism by trying to determine its decryption key or passphrase, sometimes trying thousands or millions of likely possibilities often obtained from lists of past security breaches.

<span class="mw-page-title-main">John the Ripper</span> Password cracking software tool

John the Ripper is a free password cracking software tool. Originally developed for the Unix operating system, it can run on fifteen different platforms. It is among the most frequently used password testing and breaking programs as it combines a number of password crackers into one package, autodetects password hash types, and includes a customizable cracker. It can be run against various encrypted password formats including several crypt password hash types most commonly found on various Unix versions, Kerberos AFS, and Windows NT/2000/XP/2003 LM hash. Additional modules have extended its ability to include MD4-based password hashes and passwords stored in LDAP, MySQL, and others.

Unix security refers to the means of securing a Unix or Unix-like operating system. A secure environment is achieved not only by the design concepts of these operating systems, but also through vigilant user and administrative practices.

In computer security, challenge–response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to be authenticated.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

<span class="mw-page-title-main">Key derivation function</span> Function that derives secret keys from a secret value

In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.

In cryptanalysis and computer security, password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system in scrambled form. A common approach is to repeatedly try guesses for the password and to check them against an available cryptographic hash of the password. Another type of approach is password spraying, which is often automated and occurs slowly over time in order to remain undetected, using a list of common passwords.

passwd Tool to change passwords on Unix-like OSes

passwd is a command on Unix, Plan 9, Inferno, and most Unix-like operating systems used to change a user's password. The password entered by the user is run through a key derivation function to create a hashed version of the new password, which is saved. Only the hashed version is stored; the entered password is not saved for security reasons.

The Security Account Manager (SAM) is a database file in Windows XP, Windows Vista, Windows 7, 8.1, 10 and 11 that stores users' passwords. It can be used to authenticate local and remote users. Beginning with Windows 2000 SP4, Active Directory authenticates remote users. SAM uses cryptographic measures to prevent unauthenticated users accessing the system.

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

LAN Manager is a discontinued network operating system (NOS) available from multiple vendors and developed by Microsoft in cooperation with 3Com Corporation. It was designed to succeed 3Com's 3+Share network server software which ran atop a heavily modified version of MS-DOS.

In cryptography, PBKDF1 and PBKDF2 are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.

A directory traversal attack exploits insufficient security validation or sanitization of user-supplied file names, such that characters representing "traverse to parent directory" are passed through to the operating system's file system API. An affected application can be exploited to gain unauthorized access to the file system.

A rainbow table is a precomputed table for caching the outputs of a cryptographic hash function, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of an attacker, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a key derivation function that adds a "salt" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash.

In a Windows network, NT LAN Manager (NTLM) is a suite of Microsoft security protocols intended to provide authentication, integrity, and confidentiality to users. NTLM is the successor to the authentication protocol in Microsoft LAN Manager (LANMAN), an older Microsoft product. The NTLM protocol suite is implemented in a Security Support Provider, which combines the LAN Manager authentication protocol, NTLMv1, NTLMv2 and NTLM2 Session protocols in a single package. Whether these protocols are used or can be used on a system which is governed by Group Policy settings, for which different versions of Windows have different default settings.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

<span class="mw-page-title-main">Password strength</span> Resistance of a password to being guessed

Password strength is a measure of the effectiveness of a password against guessing or brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly. The strength of a password is a function of length, complexity, and unpredictability.

crypt is a POSIX C library function. It is typically used to compute the hash of user account passwords. The function outputs a text string which also encodes the salt, and identifies the hash algorithm used. This output string forms a password record, which is usually stored in a text file.

In cryptography, a pepper is a secret added to an input such as a password during hashing with a cryptographic hash function. This value differs from a salt in that it is not stored alongside a password hash, but rather the pepper is kept separate in some other medium, such as a Hardware Security Module. Note that the National Institute of Standards and Technology refers to this value as a secret key rather than a pepper. A pepper is similar in concept to a salt or an encryption key. It is like a salt in that it is a randomized value that is added to a password hash, and it is similar to an encryption key in that it should be kept secret.

References

  1. ↑ Fenton, James L.; Grassi, Paul A.; Garcia, Michael E. (June 2017). "NIST Special Publication 800-63-3" (PDF). NIST Technical Series Publications.
  2. ↑ Anderson, Ross (2020). Security engineering: a guide to building dependable distributed systems (Third ed.). Indianapolis, Indiana. ISBN   978-1-119-64281-7. OCLC   1224516855.{{cite book}}: CS1 maint: location missing publisher (link)
  3. ↑ Godwin, Anthony (10 September 2021). "Passwords Matter". The Bug Charmer (Blog). Retrieved 2016-12-09.
  4. ↑ Boneh, Dan; Shoup, Victor (January 4, 2020). A Graduate Course in Applied Cryptography (PDF). pp. 693–695.
  5. 1 2 Rosulek, Mike (January 3, 2021). "Chapter 11: Hash Functions" (PDF). The Joy of Cryptography. pp. 204–205.
  6. ↑ "Secure Salted Password Hashing - How to do it Properly". crackstation.net. Retrieved 2021-03-19.
  7. ↑ Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. (1997). Handbook of Applied Cryptography. CRC Press. p. 288. ISBN   0-8493-8523-7.
  8. ↑ "Secure Salted Password Hashing - How to do it Properly".
  9. ↑ "Password Storage - OWASP Cheat Sheet Series". cheatsheetseries.owasp.org. Retrieved 2021-03-19.
  10. ↑ "How Rainbow Tables work". kestas.kuliukas.com.
  11. ↑ Stallings, William; Lawrie Brown (2015). Computer security: principles and practice (Third ed.). Boston. ISBN   978-0-13-377392-7. OCLC   874734678.{{cite book}}: CS1 maint: location missing publisher (link)
  12. ↑ Morris, Robert; Thompson, Ken (1978-04-03). "Password Security: A Case History". Bell Laboratories . Archived from the original on 2013-08-21.
  13. ↑ Simson Garfinkel; Gene Spafford; Alan Schwartz (2003). "How Unix Implements Passwords". Practical UNIX and Internet Security (3rd ed.). O'Reilly Media. ISBN   9780596003234.
  14. ↑ "ISC Diary – Hashing Passwords". Dshield.org. Retrieved 2011-10-15.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.