<commit_before>NOELKDF
=======

My attempt at an efficient memory-hard key stretching algorithm based on scrypt

Goals
-----

- Simplicity -- the KISS rule
- Faster hashing, increaseing area*time because we'll be able to fill more RAM
- Protect the key with user-selectable initial rounds of SHA-256 and then clear the
  password
- Operate well in a deniable mode, meaning only random parameters like salt can be stored
- Benefit from 64-bit CPU widths without trashing 32-bit performance

We simultaneously fill memory and hash.  When we're done filling memory, we're done.  This
is more friendly for users who want to pick a time to run, rather than specifying the
memory.

Scrypt relies on Salsa20/8, which is a well known algorithm.  It's fast, but still several
times slower than just filling memory with a counter.  At the same time, there seems to be
little need for such a secure RNG.  It has only three goals, AFAIK:

- It should generate data efficiently on a CPU, so we can make memory bandwidth the
  bottleneck, just like it is for an attacker
- It should not allow an attacker easily to compute V(i), without first computing
  V(0)...V(i-1).  Here V is memory and i is the ith memory location.
- It should have a large state, so the attacker can't just cache RNG states, and must fill
  memory instead.

Faster hashing should make use of 64-bit data paths without killing the performance on
32-bit machines.  It should focus on speed over proven security, but make it simple to
prove property 2.

Since we fill memory as we go, in addition to the salt, we could store a stop parameter,
of say from 128 to 256 bits.  When we see the stop parameter matches a thread key, we
would stop hashing.  This has not been implemented, but it is an intended mode of the
algorithm.  This could be particularly usefule for TrueCrypt or any other tool which
supports deniability.

License
-------

I, <NAME>, place this code into the public domain.  There are no hidden back-doors or
intentional weaknesses, and I blieve it violates no patents.  I will file no patents on
any material in this project.  I have included sha.c and sha.h which I copied from the
scrypt project, and which is available through the BSD license.

TODO
----

Use the parallelism parameter for both max threads and SIMD.  Dynamically adapt number of
threads to maximize speed.<commit_msg>Updates to README<commit_after>NOELKDF
=======

This is my attempt at an efficient memory-hard key stretching algorithm based on scrypt.
Various members of the community at password-hashing.net have contributed so generously to
NoelKDF, that it is hard to claim as my own.  The best ideas I've simply "borrowed".

Features
--------

- Memory hard Key Derivation Function for password protection
- Simplicity -- the KISS rule at it's best
- Ultra-fast hashing, approaching the speed of memmove
- Avoids cache timing attacks
- User selectable parallelism, through threads and SIMD
- "client independent update" to make server hashes more secure
- Server relief support - hashing can be split between client and server
- Friendly to crypto-systems that need deniability, such as TrueCrypt.
- User-selectable initial rounds of hashing

Credit for Features "Borrowed"
------------------------------

Alexander, aka Solar Designer, is he brains behind escript.  He has been over-the-top
helpful.  Three ideas he fed me include the  parallelism parameter to limit parallelism on
purpose, the power-of-two sliding window, and random segment hashing with a "page".  He
also helped me understand modern CPU memory performance and SIMD capabilities, which has
an enourmous impact.

<NAME>, the inventor of Catena, showed me how to avoiding timing attacks through
fixed addessing access pattern, and how to believe it works through pebble proofs.  Also,
doubling memory and not just time with t_cost to provide "client independent update".
Catena helped make the Server Relief idea mainstream.

Scrypt, the basis for the whole thing.  Scrypt is awesome, and there are many ideas
carried over.

License
-------

I, <NAME>, place this code into the public domain.  There are no hidden back-doors or
intentional weaknesses, and I blieve it violates no patents.  I will file no patents on
any material in this project.  I have included sha.c and sha.h which I copied from the
scrypt project, and which is available through the BSD license.

TODO
----

Dynamically adapt number of threads to maximize speed.
{'fraction_non_alphanumeric': 0.05548068283917341, 'fraction_numerical': 0.005166217430368374, 'mean_word_length': 3.7984913793103448, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5148869', 'n_tokens_mistral': 1196, 'n_tokens_neox': 1123, 'n_words': 690}