Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

scrypt

From Wikipedia, the free encyclopedia

2009 password-based key derivation function
Not to be confused withScript (disambiguation).
scrypt
General
DesignersColin Percival
First published2009
Cipher detail
Digest sizesvariable
Block sizesvariable
Roundsvariable

Incryptography,scrypt (pronounced "ess crypt"[1]) is a password-basedkey derivation function created byColin Percival in March 2009, originally for theTarsnap online backup service.[2][3] The algorithm was specifically designed to make it costly to perform large-scalecustom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published byIETF as RFC 7914.[4] A simplified version of scrypt is used as aproof-of-work scheme by a number ofcryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix andLitecoin soon after.[5]

Introduction

[edit]

A password-basedkey derivation function (password-based KDF) is generally designed to be computationally intensive, so that it takes a relatively long time to compute (say on the order of several hundred milliseconds). Legitimate users only need to perform the function once per operation (e.g., authentication), and so the time required is negligible. However, abrute-force attack would likely need to perform the operation billions of times, at which point the time requirements become significant and, ideally, prohibitive.

Previous password-based KDFs (such as the popularPBKDF2 fromRSA Laboratories) have relatively low resource demands, meaning they do not require elaborate hardware or very much memory to perform. They are therefore easily and cheaply implemented in hardware (for instance on anASIC or even anFPGA). This allows an attacker with sufficient resources to launch a large-scale parallel attack by building hundreds or even thousands of implementations of the algorithm in hardware and having each search a different subset of the key space. This divides the amount of time needed to complete a brute-force attack by the number of implementations available, very possibly bringing it down to a reasonable time frame.

The scrypt function is designed to hinder such attempts by raising the resource demands of the algorithm. Specifically, the algorithm is designed to use a large amount of memory compared to other password-based KDFs,[6] making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of parallelism an attacker can use, for a given amount of financial resources.

Overview

[edit]

The large memory requirements of scrypt come from a large vector ofpseudorandom bit strings that are generated as part of the algorithm. Once the vector is generated, the elements of it are accessed in a pseudo-random order and combined to produce the derived key. A straightforward implementation would need to keep the entire vector in RAM so that it can be accessed as needed.

Because the elements of the vector are generated algorithmically, each element could be generatedon the fly as needed, only storing one element in memory at a time and therefore cutting the memory requirements significantly. However, the generation of each element is intended to be computationally expensive, and the elements are expected to be accessed many times throughout the execution of the function. Thus there is a significant trade-off in speed to get rid of the large memory requirements.

This sort oftime–memory trade-off often exists in computer algorithms: speed can be increased at the cost of using more memory, or memory requirements decreased at the cost of performing more operations and taking longer. The idea behind scrypt is to deliberately make this trade-off costly in either direction. Thus an attacker could use an implementation that doesn't require many resources (and can therefore be massively parallelized with limited expense) but runs very slowly, or use an implementation that runs more quickly but has very large memory requirements and is therefore more expensive to parallelize.

Algorithm

[edit]
Function scryptInputs:This algorithm includes the following parameters:       Passphrase:                Bytesstring of characters to be hashedSalt:                      Bytesstring of random characters that modifies the hash to protect againstRainbow table attacks       CostFactor (N):            IntegerCPU/memory cost parameter – Must be a power of 2 (e.g. 1024)       BlockSizeFactor (r):       Integerblocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used)       ParallelizationFactor (p): IntegerParallelization parameter. (1 .. 232-1 * hLen/MFlen)       DesiredKeyLen (dkLen):     IntegerDesired key length in bytes                                           (Intended output length in octets of the derived key;                                             a positive integer satisfying dkLen ≤ (232− 1) * hLen.)       hLen:                      IntegerThe length in octets of the hash function (32 for SHA256).       MFlen:                     IntegerThe length in octets of the output of the mixing function (SMix below). Defined as r * 128 in RFC7914.Output:       DerivedKey:                Bytesarray of bytes, DesiredKeyLen longStep 1. Generate expensive salt    blockSize ← 128*BlockSizeFactor// Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)Treat the result as an array ofp elements, each entry beingblocksize bytes (e.g. 3 elements, each 1024 bytes)    [B0...Bp−1] ←PBKDF2HMAC-SHA256(Passphrase,Salt, 1, blockSize*ParallelizationFactor)Mix each block inB Costfactor times usingROMix function (each block can be mixed in parallel)for i ← 0to p-1do       Bi ← ROMix(Bi, CostFactor)All the elements of B is our new "expensive" salt    expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1// where ∥ is concatenationStep 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generatedreturn PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

WherePBKDF2(P, S, c, dkLen) notation is defined in RFC 2898, where c is an iteration count.

This notation is used by RFC 7914 for specifying a usage of PBKDF2 with c = 1.

Function ROMix(Block, Iterations)CreateIterations copies ofX   X ← Blockfor i ← 0to Iterations−1do      Vi ← X      X ← BlockMix(X)for i ← 0to Iterations−1do      j ← Integerify(X) mod Iterations       X ← BlockMix(Xxor Vj)return X

Where RFC 7914 definesIntegerify(X) as the result of interpreting the last 64 bytes of X as alittle-endian integer A1.

Since Iterations equals 2 to the power of N, only thefirstCeiling(N / 8) bytes among thelast 64 bytes of X, interpreted as alittle-endian integer A2, are actually needed to computeIntegerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations.

Function BlockMix(B):The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)    r ← Length(B) / 128;Treat B as an array of 2r 64-byte chunks    [B0...B2r-1] ← B    X ← B2r−1for i ← 0to 2r−1do        X ← Salsa20/8(X xor Bi)// Salsa20/8 hashes from 64-bytes to 64-bytes        Yi ← Xreturn ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

WhereSalsa20/8 is the 8-round version ofSalsa20.

Cryptocurrency uses

[edit]

Scrypt is used in many cryptocurrencies as aproof-of-work algorithm (more precisely, as the hash function in theHashcash proof-of-work algorithm). It was first implemented for Tenebrix (released in September 2011) and served as the basis forLitecoin andDogecoin, which also adopted its scrypt algorithm.[7][8] Mining ofcryptocurrencies that use scrypt is often performed on graphics processing units (GPUs) since GPUs tend to have significantly more processing power (for some algorithms) compared to the CPU.[9] This led to shortages of high end GPUs due to the rising price of these currencies in the months of November and December 2013.[10]

Utility

[edit]
scrypt encryption utility
Developer(s)Colin Percival
Stable release
1.3.3[11] Edit this on Wikidata / 14 February 2025; 45 days ago (14 February 2025)
Repositorygithub.com/Tarsnap/scrypt
Websitewww.tarsnap.com/scrypt.html

The scrypt utility was written in May 2009 by Colin Percival as a demonstration of the scrypt key derivation function.[2][3] It's available in mostLinux andBSD distributions.

See also

[edit]

References

[edit]
  1. ^"Colin Percival".Twitter.Archived from the original on 17 February 2019.
  2. ^ab"The scrypt key derivation function".Tarsnap.Archived from the original on 28 May 2019. Retrieved21 January 2014.
  3. ^ab"SCRYPT(1) General Commands Manual".Debian Manpages.Archived from the original on 2 March 2022. Retrieved2 March 2022.
  4. ^Percival, Colin; Josefsson, Simon (August 2016)."The scrypt Password-Based Key Derivation Function". RFC Editor.Archived from the original on 13 December 2021. Retrieved13 December 2021.
  5. ^Alec Liu (29 November 2013)."Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies".Archived from the original on 13 June 2018. Retrieved8 July 2017.
  6. ^Percival, Colin."Stronger Key Derivation Via Sequential Memory-Hard Functions"(PDF).Archived(PDF) from the original on 14 April 2019. Retrieved11 November 2022.
  7. ^Andreas M. Antonopoulos (3 December 2014).Mastering Bitcoin: Unlocking Digital Cryptocurrencies. O'Reilly Media. pp. 221, 223.ISBN 9781491902646.
  8. ^"History of cryptocurrency".litecoin.info wiki. 7 February 2014. Archived fromthe original on 11 June 2016. Retrieved27 June 2014.
  9. ^Roman Guelfi-Gibbs.Litecoin Scrypt Mining Configurations for Radeon 7950. Amazon Digital Services.Archived from the original on 24 October 2016. Retrieved11 September 2017.
  10. ^Joel Hruska (10 December 2013)."Massive surge in Litecoin mining leads to graphics card shortage". ExtremeTech.Archived from the original on 12 December 2017. Retrieved1 January 2014.
  11. ^"Release 1.3.3". 14 February 2025. Retrieved28 February 2025.
  12. ^Shelley, Johnny; Stolarczyk, Philip."Bcrypt – Blowfish File Encryption (homepage)".Sourceforge.Archived from the original on 29 August 2015. Retrieved8 April 2024.
  13. ^"bcrypt APK for Android – free download on Droid Informer".droidinformer.org.Archived from the original on 15 February 2020. Retrieved2 March 2022.
  14. ^"T2 package – trunk – bcrypt – A utility to encrypt files".t2sde.org.Archived from the original on 28 October 2017. Retrieved2 March 2022.
  15. ^"Oracle® GoldenGate Licensing Information".Oracle Help Center.Archived from the original on 6 March 2024. Retrieved8 April 2024.

External links

[edit]
Common functions
SHA-3 finalists
Other functions
Password hashing/
key stretching functions
General purpose
key derivation functions
MAC functions
Authenticated
encryption
modes
Attacks
Design
Standardization
Utilization
General
Mathematics
Technology
Consensus mechanisms
Proof of work currencies
SHA-256-based
Ethash-based
Scrypt-based
Equihash-based
RandomX-based
X11-based
Other
Proof of stake currencies
ERC-20 tokens
Stablecoins
Other currencies
Inactive currencies
Crypto service companies
Related topics
Retrieved from "https://en.wikipedia.org/w/index.php?title=Scrypt&oldid=1283221890"
Categories:
Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp