NeoScrypt, a Strong Memory Intensive Key Derivation Function by John Doering

ABSTRACT. Hereby presented a new password based memory intensive cryptographic solution designed for general purpose computer hardware. A particular 32-bit implementation is described and evaluated.

1. INTRODUCTION

Password based key derivation function (KDF) is a deterministic algorithm used to derive a cryptographic key from an input datum known as a password. An additional input datum known as a salt may be employed in order to increase strength of the algorithm against attacks using pre-computed hashes also known as rainbow tables. The derived key length may be specified usually, and one of the most popular uses of KDFs is key stretching. It increases effective length of a user password by constructing an enhanced key to provide with a better resistance against brute force attacks. Another popular use is password storage. Keeping user passwords in unencrypted form is very undesired as it may be possible for an attacker to gain access to the password file and retrieve the passwords stored immediately. Brute force attacks may be the only possible approach against strong KDFs. This kind of attack can be parallelised usually to a great extent. High requirements on computational resources such as processor time and memory space allow to reduce parallelisation efficiency and keep these attacks expensive far beyond reasonable limits. As the name suggests, NeoScrypt is a further development of Scrypt as described in Percival [1]. It is aimed at increased security and better performance on general purpose computer hardware while maintaining comparable costs and requirements. This document focuses on functional differences between NeoScrypt and Scrypt. v1 26-Jul-2014

2. SCRYPT SPECIFICATIONS

The most popular implementation of Scrypt employed by many cryptocurrencies since 2011 is N = 1024, r = 1, p = 1 abbreviated usually to (1024, 1, 1). N is the primary parameter defining number of memory segments used and must be a power of 2. May be also described through Nfactor. N = (1 << (Nfactor + 1)) Nfactor = lb(N) – 1 The default memory segment size for the 32-bit implementation is 128 bytes. r is the segment size multiplier. p is the computational multiplier. They may be also described through rfactor and pfactor respectively. r = (1 << rfactor) p = (1 << pfactor) A single instance of Scrypt utilises (N + 2) * r * 128 bytes of memory space, i.e. 128.25Kb for the (1024, 1, 1) configuration. Actual data mixing in memory is performed by Salsa20, a stream cipher introduced by Bernstein [2]. A reduced strength 8-round implementation has been chosen (Salsa20/8). Every run of the Scrypt core engine executes it 4 * r * N times, i.e. 4096 times for the (1024, 1, 1) configuration. Every execution of Salsa20 mixes one half of a memory segment with itself. The Scrypt core engine has no provisions for key stretching or compressing as well as salting, therefore additional cryptographic functions need to be deployed. In case of cryptocurrencies, a typical configuration operates with 80 bytes of input data (block header) which is also a salt. It is passed to PBKDF2, a password based KDF [3] capable of deriving variable length keys with salting. It works with SHA-256, a cryptographic hash function delivering digests up to 32 bytes in size through 64 internal rounds. It doesn’t support keyed hashing, therefore a pseudorandom function (PRF) such as HMAC [4] is required, and the whole big endian construction may be called PBKDF2-HMAC-SHA256. It feeds r * 128 bytes of derived data to the Scrypt core and receives it back after mixing to be used as a salt for another PBKDF2-HMAC-SHA256 run which compresses 80 bytes of input data into 32 bytes of hash. v1 26-Jul-2014

3. NEOSCRYPT SPECIFICATIONS

4. CONCLUSIONS

The primary functionality of NeoScrypt and Scrypt has been described and evaluated briefly without much mathematical detail to a cryptography amateur. Certain disadvantages of Scrypt have been outlined. Please refer to the source code and the original Scrypt documentation [1] for additional information should you need any. v1 26-Jul-2014

REFERENCES

1. Colin Percival. Stronger Key Derivation via Sequential Memory-Hard Functions, May 2009
2. Daniel J. Bernstein. The Salsa20 family of stream ciphers, December 2007
3. IETF RFC 2898. PKCS #5: Password-based Cryptography Specification Version 2.0, September 2000
4. FIPS 198-1. The Keyed-Hash Message Authentication Code (HMAC), July 2008
5. Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima. Differential
ryptanalysis of Salsa20/8, January 2007
6. Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier and Christian Rechberger. New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba, December of 2007
7. Zhenqing Shi, Bin Zhang, Dengguo Feng and Wenling Wu. Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha, November 2012
8. Daniel J. Bernstein. ChaCha, a variant of Salsa20, January 2008
9. Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O’Hearn and Christian Winnerlein. BLAKE2: simpler, smaller, fast as MD5, January 2013.
10. Jean-Philippe Aumasson, Luca Henzen, Willi Meier and Raphael C.-W. Phan. SHA-3 proposal BLAKE. Submission to NIST (Round 1/2), 2008. v1 26-Jul-2014