Key stretching

Last updated

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 (time and possibly space) 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. [1]

Contents

There are several ways to perform key stretching. One way is to apply a cryptographic hash function or a block cipher repeatedly in a loop. For example, in applications where the key is used for a cipher, the key schedule in the cipher may be modified so that it takes a specific length of time to perform. Another way is to use cryptographic hash functions that have large memory requirements – these can be effective in frustrating attacks by memory-bound adversaries. [2]

Process

Key stretching algorithms depend on an algorithm which receives an input key and then expends considerable effort to generate a stretched cipher (called an enhanced key[ citation needed ]) mimicking randomness and longer key length. The algorithm must have no known shortcut, so the most efficient way to relate the input and cipher is to repeat the key stretching algorithm itself. This compels brute-force attackers to expend the same effort for each attempt. If this added effort compares to a brute-force key search of all keys with a certain key length, then the input key may be described as stretched by that same length. [1]

Key stretching leaves an attacker with two options:

If the attacker uses the same class of hardware as the user, each guess will take the similar amount of time to process as it took the user (for example, one second). Even if the attacker has much greater computing resources than the user, the key stretching will still slow the attacker down while not seriously affecting the usability of the system for any legitimate user. This is because the user's computer only has to compute the stretching function once upon the user entering their password, whereas the attacker must compute it for every guess in the attack.

This process does not alter the original key-space entropy. The key stretching algorithm is deterministic, allowing a weak input to always generate the same enhanced key, but therefore limiting the enhanced key to no more possible combinations than the input key space. Consequently, this attack remains vulnerable if unprotected against certain time-memory tradeoffs such as developing rainbow tables to target multiple instances of the enhanced key space in parallel (effectively a shortcut to repeating the algorithm). For this reason, key stretching is often combined with salting. [1]

Hash-based

Many libraries provide functions which perform key stretching as part of their function; see crypt(3) for an example. [4] PBKDF2 is for generating an encryption key from a password, and not necessarily for password authentication. PBKDF2 can be used for both if the number of output bits is less than or equal to the internal hashing algorithm used in PBKDF2, which is usually SHA-2 (up to 512 bits), or used as an encryption key to encrypt static data. [5]

Strength and time

These examples assume that a consumer CPU can do about 65,000 SHA-1 hashes in one second. Thus, a program that uses key stretching can use 65,000 rounds of hashes and delay the user for at most one second.

Testing a trial password or passphrase typically requires one hash operation. But if key stretching was used, the attacker must compute a strengthened key for each key they test, meaning there are 65,000 hashes to compute per test. This increases the attacker's workload by a factor of 65,000, approximately 216, which means the enhanced key is worth about 16 additional bits in key strength.

Moore's law asserts that computer speed doubles roughly every 2 years. Under this assumption, every 2 years one more bit of key strength is plausibly brute-forcible. This implies that 16 extra bits of strength is worth about 16×2 = 32 years later cracking, but it also means that the number of key stretching rounds a system uses should be doubled about every 2 years to maintain the same level of security (since most keys are more secure than necessary, systems that require consistent deterministic key generation will likely not update the number of iterations used in key stretching. In such a case, the designer should take into consideration how long they wish for the key derivation system to go unaltered and should choose an appropriate number of hashes for the lifespan of the system).

CPU-bound hash functions are still vulnerable to hardware implementations. Such implementations of SHA-1 exist using as few as 5,000 gates, and 400 clock cycles. [6] With multi-million gate FPGAs costing less than $100, [7] an attacker can build a fully unrolled hardware cracker for about $5,000.[ citation needed ] Such a design, clocked at 100 MHz can test about 300,000 keys/second. The attacker is free to choose a good price/speed compromise, for example a 150,000 keys/second design for $2,500.[ citation needed ] The key stretching still slows down the attacker in such a situation; a $5,000 design attacking a straight SHA-1 hash would be able to try 300,000÷216 ≈ 4.578 keys/second.[ citation needed ]

Similarly, modern consumer GPUs can speed up hashing considerably. For example, in a benchmark, a Nvidia RTX 2080 SUPER FE computes over 10 billion SHA1 hashes per second. [8]

To defend against the hardware approach, memory-bound cryptographic functions have been developed. These functions access a lot of memory in a way that makes caching ineffective. Since large amounts of low latency memory are expensive, potential attackers are discouraged from pursuing such attacks.

History

The first deliberately slow password-based key derivation function "CRYPT" was described in 1978 by Robert Morris for encrypting Unix passwords. [9] It used an iteration count of 25, a 12-bit salt and a variant of DES as the sub-function. (DES proper was avoided in an attempt to frustrate attacks using standard DES hardware.) Passwords were limited to a maximum of eight ASCII characters. While it was a great advancement for its time, CRYPT(3) is now considered inadequate. The iteration count, designed for the PDP-11 era, is too low, 12 bits of salt is an inconvenience but does not stop precomputed dictionary attacks, and the eight-character limit prevents the use of stronger passphrases.

Modern password-based key derivation functions, such as PBKDF2, use a cryptographic hash, such as SHA-2, a longer salt (e.g. 64 bits) and a high iteration count. The U.S. National Institute of Standards and Technology (NIST) recommends a minimum iteration count of 10,000. [10] : 5.1.1.2  "For especially critical keys, or for very powerful systems or systems where user-perceived performance is not critical, an iteration count of 10,000,000 may be appropriate.” [11] : 5.2 

In 2009, a memory-intensive key strengthening algorithm, scrypt, was introduced with the intention of limiting the use of custom, highly parallel hardware to speed up key testing. [12]

In 2013, a Password Hashing Competition was held to select an improved key stretching standard that would resist attacks from graphics processors and special purpose hardware. The winner, Argon2, was selected on July 1, 2015. [13]

Some systems that use key stretching

See also

Related Research Articles

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

<span class="mw-page-title-main">Brute-force attack</span> Cryptanalytic method for unauthorized users to access data

In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key which is typically created from the password using a key derivation function. This is known as an exhaustive key search. This approach doesn't depend on intellectual tactics; rather, it relies on making several attempts.

A passphrase is a sequence of words or other text used to control access to a computer system, program or data. It is similar to a password in usage, but a passphrase is generally longer for added security. Passphrases are often used to control both access to, and the operation of, cryptographic programs and systems, especially those that derive an encryption key from a passphrase. The origin of the term is by analogy with password. The modern concept of passphrases is believed to have been invented by Sigmund N. Porter in 1982.

Articles related to cryptography include:

<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 guessing passwords protecting a computer system. 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.

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

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.

The following outline is provided as an overview of and topical guide to cryptography:

There are various implementations of the Advanced Encryption Standard, also known as Rijndael.

In cryptography, scrypt is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.

Microsoft Office password protection is a security feature that allows Microsoft Office documents to be protected with a user-provided password.

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, the Salted Challenge Response Authentication Mechanism (SCRAM) is a family of modern, password-based challenge–response authentication mechanisms providing authentication of a user to a server. As it is specified for Simple Authentication and Security Layer (SASL), it can be used for password-based logins to services like LDAP, HTTP, SMTP, POP3, IMAP and JMAP (e-mail), XMPP (chat), or MongoDB and PostgreSQL (databases). For XMPP, supporting it is mandatory.

<span class="mw-page-title-main">VeraCrypt</span> Free and open-source disk encryption utility

VeraCrypt is a free and open-source utility for on-the-fly encryption (OTFE). The software can create a virtual encrypted disk that works just like a regular disk but within a file. It can also encrypt a partition or the entire storage device with pre-boot authentication.

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.

In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security", where n-bit security means that the attacker would have to perform 2n operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 is designed to offer a 128-bit security level, which is considered roughly equivalent to a RSA using 3072-bit key.

This is a list of cybersecurity information technology. Cybersecurity is security as it is applied to information technology. This includes all technology that stores, manipulates, or moves data, such as computers, data networks, and all devices connected to or included in networks, such as routers and switches. All information technology devices and facilities need to be secured against intrusion, unauthorized use, and vandalism. Additionally, the users of information technology should be protected from theft of assets, extortion, identity theft, loss of privacy and confidentiality of personal information, malicious mischief, damage to equipment, business process compromise, and the general activity of cybercriminals. The public should be protected against acts of cyberterrorism, such as the compromise or loss of the electric power grid.

References

  1. 1 2 3 Kelsey, John; Schneier, Bruce; Hall, Chris; Wagner, David A. (1997). "Secure Applications of Low-Entropy Keys". In Okamoto, Eiji; Davida, George I.; Mambo, Masahiro (eds.). Information Security, First International Workshop, ISW '97, Tatsunokuchi, Japan, September 17-19, 1997, Proceedings. Lecture Notes in Computer Science. Vol. 1396. Springer. pp. 121–134. doi:10.1007/BFb0030415. ISBN   978-3-540-64382-1.
  2. ↑ Reinhold, Arnold (July 15, 1999). "HEKS: A Family of Key Stretching Algorithms" (PDF).
  3. ↑ McMillan, Troy (2022-07-07). CompTIA Advanced Security Practitioner (CASP+) CAS-004 Cert Guide. Pearson IT Certification. ISBN   978-0-13-734870-1.
  4. ↑ crypt(3)  –  FreeBSD Library Functions Manual
  5. ↑ Moriarty, Kathleen (2017). "PKCS #5: Password-Based Cryptography Specification, Version 2.1".
  6. ↑ O'Neill, Máire. "Low-cost SHA-1 Hash Function Architecture for RFID Tags" (PDF). Archived from the original (PDF) on 2012-03-19.
  7. ↑ "New 90nm Xilinx Spartan-3 FPGAs Reshape Semiconductor Landscape (0333) : Xilinx Press Releases". Archived from the original on 2011-07-16. Retrieved 2010-08-08.
  8. ↑ https://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d , PBKDF2-HMAC-SHA1 with 1,000 iterations costs 2,002 SHA-1 hashes at a speed of 5,164.9 kH/s which comes to 10,340,129,800 SHA-1 hashes per second.
  9. ↑ Morris, Robert; Thompson, Ken (1978-04-03). "Password Security: A Case History". Bell Laboratories. Archived from the original on 2003-03-22. Retrieved 2011-05-09.
  10. ↑ Grassi Paul A. (June 2017). SP 800-63B-3 – Digital Identity Guidelines, Authentication and Lifecycle Management. NIST. doi:10.6028/NIST.SP.800-63b.
  11. ↑ Meltem Sönmez Turan, Elaine Barker, William Burr, and Lily Chen (December 2010). SP 800-132 – Recommendation for Password-Based Key Derivation, Part 1: Storage Applications. NIST. doi:10.6028/NIST.SP.800-132.{{cite book}}: CS1 maint: multiple names: authors list (link)
  12. ↑ Percival, Colin (2009). scrypt: A new key derivation function. BSDCan 2009. Archived from the original on 2024-06-29.
  13. ↑ Password Hashing Competition
  14. ↑ "7z Format".
  15. ↑ KBDF 4
  16. ↑ KeePassXC—Creating Your First Database
  17. ↑ Drepper, Ulrich. "Unix crypt using SHA-256 and SHA-512".
  18. ↑ RFC 4880
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.