World Library  
Flag as Inappropriate
Email this Article

Scrypt

Article Id: WHEBN0036464065
Reproduction Date:

Title: Scrypt  
Author: World Heritage Encyclopedia
Language: English
Subject: Coinye, Dogecoin, Cryptocurrency, Key stretching, Cryptocurrencies
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Scrypt

In cryptography, scrypt is a password-based key derivation function created by Colin Percival, originally for the Tarsnap online backup service.[1] The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2012, the scrypt algorithm was published by IETF as an Internet Draft, intended to become an informational RFC, which has since expired.[2] A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies first implemented by Litecoin.[3]

Introduction

A password-based key 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, a brute-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 popular PBKDF2 from RSA 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 an ASIC or even an FPGA). 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,[4] 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

The large memory requirements of scrypt come from a large vector of pseudorandom 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 random-access memory so that it can be accessed as needed.

Because the elements of the vector are generated algorithmically, each element could be generated on 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 in order to get rid of the large memory requirements.

This sort of time–memory trade-off often exists in computer algorithms: you can increase speed at the cost of using more memory, or decrease memory requirements 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

The algorithm includes the following parametres:

  • MFLen - Length of block mixed by SMix() , in octets.
  • hLen - Length of output produced by HMAC_SHA256() , in octets.
  • dkLen - Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (232− 1) * hLen.
  • N - CPU/memory cost parameter.
  • p - Parallelization parameter; a positive integer satisfying p ≤ (232− 1) * hLen / MFLen.

Function scrypt(Passphrase,Salt,N,p,dkLen):

(B0 ... Bp−1) ← PBKDF2HMAC_SHA256(Passphrase, Salt, 1, p * MFLen)
for i = 0 to p-1 do
    Bi ← SMix(Bi,N)
end for
Output ← PBKDF2HMAC_SHA256(Passphrase, B0 || B1 ... Bp−1, 1, dkLen)

Function SMix(B,N):

X ← B
for i = 0 to N − 1 do
    Vi ← X
    X ← BlockMix(X)
end for
for i = 0 to N − 1 do
    j ← Integerify(X) mod N
    X ← BlockMix(X ⊕ Vj)
end for
Output ← X

Integerify() is a bijective function from {0, 1}k to {0,...,2k− 1}.

Function BlockMix(B):

(B0, ... , B2r-1) ← B
X ← B2r−1
for i = 0 to 2r − 1 do
    X ← H(X ⊕ Bi)
    Yi ← X
end for
Output ← (Y0, Y2, ... , Y2r−2, Y1, Y3, ... , Y2r−1)

Proof-of-work in cryptocurrency operations

Scrypt has been used in many cryptocurrencies since Tenebrix first implemented it as an alternate proof-of-work algorithm in September 2011.[5] Mining of cryptocurrencies that use scrypt as a proof-of-work function is often performed on graphics processing units (GPUs) since GPUs tend to have significantly more processing power compared to the CPU.[6] This led to shortages of high end GPUs due to the rising price of these currencies in the months of November and December 2013.[7]

As of May 2014, specialized ASIC mining hardware is available for scrypt-based cryptocurrencies.[8]

Implementations, wrappers, and distributions

  • C#: cryptsharp
  • Clojure: scrypt
  • Go: scrypt, easy-scrypt
  • Java: scrypt, scrypt (non-static)
  • NodeJS: scrypt, js-scrypt
  • PHP: php-scrypt (wrapper)
  • Ruby: scrypt
  • Perl: Crypt::Scrypt, Crypt::ScryptKDF
  • Python: pyscrypt
  • C: libscrypt
  • R: rscrypt

Scrypt is also available as stand alone executable

See also

References

  1. ^ "scrypt page on the Tarsnap website". Retrieved 21 January 2014. 
  2. ^ C. Percival, S. Josefsson (2012-09-17). "The scrypt Password-Based Key Derivation Function".  
  3. ^ Alec Liu. "Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies". 
  4. ^ Stronger Key Derivation Via Sequential Memory-Hard Functions, Colin Percival
  5. ^ "History of cryptocurrency". Retrieved 27 June 2014. 
  6. ^ Roman Guelfi-Gibbs. Litecoin Scrypt Mining Configurations for Radeon 7950. Amazon Digital Services. 
  7. ^ Joel Hruska (10 December 2013). "Massive surge in Litecoin mining leads to graphics card shortage". ExtremeTech. 
  8. ^ Caleb Chen (21 May 2014). "Zeusminer Delivers Lightning, Thunder, and Cyclone Scrypt ASICs For Litecoin And Dogecoin Mining". 

External links

  • The scrypt page on the Tarsnap website.
  • The original scrypt paper.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.