Index

• Quick Start
• What's in a name?
• Usage
  • Command Line
  • Library
• How Draupnir Works
  • The Sponge Construction
  • Draupnir's State Change Function
  • Draupnir's Output
  • Draupnir's Input
  • Odds and Ends
• Dieharder Results
• FAQs
  • What Systems does Draupnir Work on?
  • Is Draupnir Cryptographically Secure?
  • How Fast is Draupnir?
  • Is Draupnir Recommended for Password Hashing?
  • Are there any Test Vectors Available?
  • Can I Use Draupnir in my Commercial Project?
• Contributing
• License

---

Quick Start

In order to clone the repository, just do:

git clone 'https://github.com/mariano-perez-rodriguez/draupnir.git'

or

git clone 'git@github.com:mariano-perez-rodriguez/draupnir.git'

this will create a directory called draupnir under the current one, containing the repository.

From there, just do:

cd draupnir
make

to build the draupnir binary; you can use make mode=debug for a debug build. If everything went well, you will see a new release/bin directory. To run draupnir, use:

release/bin/draupnir

and you're done! See the usage section for more information.

What's in a Name?

Draupnir is a mythologcal artifact mentioned in the Norse mythos. To quote Wikipedia:

In Norse mythology, Draupnir (Old Norse "the dripper") is a gold ring possessed by the god Odin with the ability to multiply itself: every ninth night, eight new rings 'drip' from Draupnir, each one of the same size and weight as the original.

We took Draupnir's ability to multiply itself as a metaphor for the RNG in question to split according to different sub-salts given. In all truth, this is a property of the sponge construction, not specific to Draupnir itself, but since the name is as cool as the hypothetical son of James Bond and Lagertha would be, it kinda stuck.

Incidentally, Draupnir's symbol is the Othala rune, commonly associated with Odin (the owner of the ring in qustion).

Usage

• Command Line
• Library

Draupnir can be used either as a standalone command line program, or as a library component in your own programs (either in source form or as a pre-compiled object).

Command Line

See doc/MANUAL.md for more information.

Library

In order to use Draupnir in your projects, you must simply include Draupnir.h and the "Draupnir Module" header file (these are named DraupnirXXX.h, where XXX identifies the module).

Now you can write:

#include "Draupnir.h"

Draupnir::CrcSponge64 r = Draupnir::CrcSponge64Builder();

for the default configuration, or, for instance:

#include "Draupnir.h"

Draupnir::CrcSponge64 r = Draupnir::CrcSponge64Builder().initialState(Draupnir::invGamma);

to have Draupnir initialized with 1 / γ.

If you're running C++11 or above and want to use the auto type specifier you'll need to write:

#include "Draupnir.h"

auto r = Draupnir::CrcSponge64Builder().build();

or

#include "Draupnir.h"

auto r = Draupnir::CrcSponge64Builder().initialState(Draupnir::invGamma).build();

note the .build() method call added; otherwise, r's type will be deduced to be Draupnir::CrcSponge64Builder instead of Draupnir::CrcSponge64 (but, this may be what you want: having a pre-specified builder).

Actually, Draupnir acts as a staging namespace, providing named constants (eg. Draupnir::invGamma) and typedefs. We provide named constructors (eg. Draupnir::CrcSponge64Builder) where these in turn act as named parameter realizations of the "actual" Draupnir generator (eg. Draupnir::CrcSponge64) objects.

See doc/MANUAL.md for more information.

How Draupnir Works

• The Sponge Construction
• Draupnir's State Change Function
• Draupnir's Output
• Draupnir's Input
• Odds and Ends

Draupnir is based off of the concept of a Cryptographic Sponge (see: The Sponge Functions Corner): a construction that allows for a reseedable and splittable RNG to be built; note though, that Draupnir is not a cryptographic sponge in the strictest sense: its "input rate state-space" and "output rate state-space" are not identical.

One of Draupnir's most central objectives is to be easy to understand and allow for a clean implementation.

The Sponge Construction

A detailed analysis of the sponge construction is provided in the link above, but, just in case you're lazy, here's a quick summary.

A cryptographic sponge consists of two elements:

• A state : a state is just that, a structure of a given size in bits (call it t ), which is divided in two "parts": the rate (call it r ), and the capacity (call it c ).
• A state change function : a state change function is just a function (call it f ) that, given a state s, produces a new state s' = f(s).

Now one can perform two operations on one such sponge:

• Soaking: to soak the sponge in a datum d means to replace the "rate" portion of the state with (a suitable padding of) d, and apply the state change function to the resulting state.
• Squeezing: to squeeze the sponge means to extract the "rate" portion of the state, and apply the state change function to the current state.

As an example of the generality of this construction (see the link above for many, many, more) note that by having two identical copies of a sponge, and soaking each on a different piece of data, one gets two sponges whose squeeze outputs differ from that point on (this is the property we call "split").

Draupnir's State Change Function

Draupnir's general design allows for a state change function parameterized by a hash function. A hash function H : 2^✱ → 2^k (where 2 represents the set containing the numbers 0 and 1) is used to construct a (k × k)-bit state. The only restriction is that k must be an even number.

In its current implementation, Draupnir only supports the crc64 hash, which takes an arbitrary length string and transforms it into a 64 bit hashed result (nb. we're working on adding additional hashes to Draupnir's repertoire).

Given the hash function H, and the (k × k)-bit state S, Draupnir generates a new (k × k)-bit state T as follows:

• let T be a "temporary" (k × k)-bit state,
• for 0 ≤ i < k, do:
• apply H to the i-th row of S, store the result as the i-th column of T,
• overwrite S with T.

(nb, rows are numbered from 0 up to k - 1 inclusive) That's it!

What this state change function does is calculate the hash by rows and store it by columns, nothing more. If you dont't believe me, take a look at the next picture:

Simple, right? (do note, though, that in the diagram we're displaying an (8 × 8)-bit state, not a byte-per-byte representation of a 64-bit version of Draupnir).

Draupnir's Output

Draupnir's output is k bits long, and is computed thus:

• the output bit at position i, when i is odd, is the i-th bit of the i-th row of S,
• the output bit at position i, when i is even, is the i-th bit of the (k - i - 1)-th row of S,

(nb, both rows and bits are numbered from 0 up to k - 1 inclusive) if that sounded complicated, here's a picture:

Note that it simply amounts to taking alternating bits from the NE and SE diagonals of S (note, though, that in the diagram we're displaying an (8 × 8)-bit state, not a byte-per-byte representation of a 64-bit version of Draupnir).

After outputting a value, the state change function is applied a configurable number of times (just once by default).

Draupnir's Input

When soaking data into Draupnir's sponge, the the first thing to do is pad the data using a multi-rate padding scheme: a string of the form 1 0^p 1 is appended to the data, choosing a 0 ≤ p < k - 2 that would make the length of the so padded data a multiple of k. Now each block of k bits is fed into S thus:

• the input bit at position i, when i is even, overwrites the i-th bit of the i-th row of S,
• the input bit at position i, when i is odd, overwrites the i-th bit of the (k - i - 1)-th row of S,

(nb, both rows and bits are numbered from 0 up to k - 1 inclusive) if that sounded complicated, here's a picture:

Note that this is the same operation used for output, using the diagonal bits not used then (note, though, that in the diagram we're displaying an (8 × 8)-bit state, not a byte-per-byte representation of a 64-bit version of Draupnir).

After inputting each block, the state change function is applied a configurable number of times (8, by default).

Odds and Ends

There's one last detail to consider (and specify for): if the hash function H happens to be able to output a "partial" input hash efficiently, then one may consider running H in continuous mode, generating a hash when needed but considering all the given input data as one big, continuous, stream. So we have:

• Discrete mode: the hash function is applied to each value independently (ie. as if that value was the totality of the stream to hash).
• Continuous mode: the hash function is applied to each value incrementally (ie. as f that value was just the next "segment" in a continuous stream of data).

In its current implementation, Draupnir works in continuous mode, which effectively increases the state space by the hash function's state size.

Dieharder Results

Draupnir (in its default configuration) has been tested with dieharder 3.31.1, using the following line:

dieharder -a -k 2 -Y 1 -g 201 -f draupnir.samples.bin

This asks for all tests (-a), using the "ks" flag indicating maximum precision (-k 2), with a "resolve ambiguity" strategy (-Y 1), for a "generator" to be read from a binary file (-g 201), which is called draupnir.samples.bin (-f draupnir.samples.bin), this file is a 1GiB binary file generated by Draupnir.

Draupnir eventually (we say eventually because in ambiguity resolution mode, a single test may be run multiple times until a non-ambiguous determination is reached) passes all the dieharder tests in their default configuration.

Here are the results in a table:

Test Name	N	t samples	p samples	p-value	Assesment
diehard_birthdays	0	100	100	0.63064540	PASSED
diehard_operm5	0	1000000	100	0.03515999	PASSED
diehard_rank_32x32	0	40000	100	0.99366480	PASSED
diehard_rank_6x8	0	100000	100	0.81220479	PASSED
diehard_bitstream	0	2097152	100	0.95534811	PASSED
diehard_opso	0	2097152	100	0.94393360	PASSED
diehard_oqso	0	2097152	100	0.98087088	PASSED
diehard_dna	0	2097152	100	0.95769403	PASSED
diehard_count_1s_str	0	256000	100	0.49225429	PASSED
diehard_count_1s_byt	0	256000	100	0.88281751	PASSED
diehard_parking_lot	0	12000	100	0.43004782	PASSED
diehard_2dsphere	2	8000	100	0.51435477	PASSED
diehard_3dsphere	3	4000	100	0.28920569	PASSED
diehard_squeeze	0	100000	100	0.67876168	PASSED
diehard_sums	0	100	100	0.66044170	PASSED
diehard_runs	0	100000	100	0.04674612	PASSED
diehard_runs	0	100000	100	0.98217621	PASSED
diehard_craps	0	200000	100	0.49183776	PASSED
diehard_craps	0	200000	100	0.46006937	PASSED
marsaglia_tsang_gcd	0	10000000	100	0.20904964	PASSED
marsaglia_tsang_gcd	0	10000000	100	0.01648035	PASSED
sts_monobit	1	100000	100	0.48969331	PASSED
sts_runs	2	100000	100	0.39693806	PASSED
sts_serial	1	100000	200	0.49587339	PASSED
sts_serial	2	100000	200	0.19663377	PASSED
sts_serial	3	100000	200	0.43291004	PASSED
sts_serial	3	100000	200	0.18233658	PASSED
sts_serial	4	100000	200	0.96692485	PASSED
sts_serial	4	100000	200	0.56005169	PASSED
sts_serial	5	100000	200	0.87878990	PASSED
sts_serial	5	100000	200	0.74775083	PASSED
sts_serial	6	100000	200	0.86294971	PASSED
sts_serial	6	100000	200	0.85268807	PASSED
sts_serial	7	100000	200	0.37983973	PASSED
sts_serial	7	100000	200	0.10117355	PASSED
sts_serial	8	100000	200	0.15770631	PASSED
sts_serial	8	100000	200	0.41611920	PASSED
sts_serial	9	100000	200	0.93148930	PASSED
sts_serial	9	100000	200	0.90275330	PASSED
sts_serial	10	100000	200	0.58921179	PASSED
sts_serial	10	100000	200	0.58830610	PASSED
sts_serial	11	100000	200	0.62760477	PASSED
sts_serial	11	100000	200	0.70437632	PASSED
sts_serial	12	100000	200	0.92911851	PASSED
sts_serial	12	100000	200	0.19846138	PASSED
sts_serial	13	100000	200	0.88282809	PASSED
sts_serial	13	100000	200	0.72430544	PASSED
sts_serial	14	100000	200	0.58871871	PASSED
sts_serial	14	100000	200	0.47935487	PASSED
sts_serial	15	100000	200	0.14544557	PASSED
sts_serial	15	100000	200	0.53219509	PASSED
sts_serial	16	100000	200	0.13139076	PASSED
sts_serial	16	100000	200	0.57874754	PASSED
rgb_bitdist	1	100000	100	0.42567409	PASSED
rgb_bitdist	2	100000	100	0.55714722	PASSED
rgb_bitdist	3	100000	100	0.66063937	PASSED
rgb_bitdist	4	100000	100	0.26377560	PASSED
rgb_bitdist	5	100000	100	0.12805612	PASSED
rgb_bitdist	6	100000	100	0.47967016	PASSED
rgb_bitdist	7	100000	100	0.14175432	PASSED
rgb_bitdist	8	100000	100	0.97145223	PASSED
rgb_bitdist	9	100000	100	0.40135356	PASSED
rgb_bitdist	10	100000	100	0.32587425	PASSED
rgb_bitdist	11	100000	100	0.98519018	PASSED
rgb_bitdist	12	100000	100	0.29674658	PASSED
rgb_minimum_distance	2	10000	1000	0.76972901	PASSED
rgb_minimum_distance	3	10000	1000	0.93211566	PASSED
rgb_minimum_distance	4	10000	1000	0.39127666	PASSED
rgb_minimum_distance	5	10000	1000	0.11212254	PASSED
rgb_permutations	2	100000	100	0.72450965	PASSED
rgb_permutations	3	100000	100	0.22921651	PASSED
rgb_permutations	4	100000	100	0.34243965	PASSED
rgb_permutations	5	100000	100	0.60468421	PASSED
rgb_lagged_sum	0	1000000	100	0.81703915	PASSED
rgb_lagged_sum	1	1000000	100	0.45637948	PASSED
rgb_lagged_sum	2	1000000	100	0.95207442	PASSED
rgb_lagged_sum	3	1000000	100	0.80228102	PASSED
rgb_lagged_sum	4	1000000	100	0.39828888	PASSED
rgb_lagged_sum	5	1000000	100	0.20938165	PASSED
rgb_lagged_sum	6	1000000	100	0.56671011	PASSED
rgb_lagged_sum	7	1000000	100	0.08812106	PASSED
rgb_lagged_sum	8	1000000	100	0.17108848	PASSED
rgb_lagged_sum	9	1000000	100	0.31404455	PASSED
rgb_lagged_sum	10	1000000	100	0.98738722	PASSED
rgb_lagged_sum	11	1000000	100	0.51733467	PASSED
rgb_lagged_sum	12	1000000	100	0.91767471	PASSED
rgb_lagged_sum	13	1000000	100	0.33031728	PASSED
rgb_lagged_sum	14	1000000	100	0.32253236	PASSED
rgb_lagged_sum	15	1000000	100	0.53337340	PASSED
rgb_lagged_sum	16	1000000	100	0.67937772	PASSED
rgb_lagged_sum	17	1000000	100	0.25573759	PASSED
rgb_lagged_sum	18	1000000	100	0.60761161	PASSED
rgb_lagged_sum	19	1000000	100	0.22868094	PASSED
rgb_lagged_sum	20	1000000	100	0.46505306	PASSED
rgb_lagged_sum	21	1000000	100	0.56312916	PASSED
rgb_lagged_sum	22	1000000	100	0.48896176	PASSED
rgb_lagged_sum	23	1000000	100	0.06160357	PASSED
rgb_lagged_sum	24	1000000	100	0.71473587	PASSED
rgb_lagged_sum	25	1000000	100	0.98301624	PASSED
rgb_lagged_sum	26	1000000	100	0.20179028	PASSED
rgb_lagged_sum	27	1000000	100	0.86533400	PASSED
rgb_lagged_sum	28	1000000	100	0.63597088	PASSED
rgb_lagged_sum	29	1000000	100	0.70753809	PASSED
rgb_lagged_sum	30	1000000	100	0.21715355	PASSED
rgb_lagged_sum	31	1000000	100	0.00699472	PASSED
rgb_lagged_sum	32	1000000	100	0.57913639	PASSED
rgb_kstest_test	0	10000	1000	0.50575968	PASSED
dab_bytedistrib	0	51200000	1	0.52505240	PASSED
dab_dct	256	50000	1	0.60605756	PASSED
dab_filltree	32	15000000	1	0.16824354	PASSED
dab_filltree	32	15000000	1	0.04785636	PASSED
dab_filltree2	0	5000000	1	0.09302336	PASSED
dab_filltree2	1	5000000	1	0.10770671	PASSED
dab_monobit2	12	65000000	1	0.07515807	PASSED

Where only the last result of an ambiguity resolution run is shown.

See doc/RESULTS.md for more.

FAQs

• What Systems does Draupnir Work on?
• Is Draupnir Cryptographically Secure?
• How Fast is Draupnir?
• Is Draupnir Recommended for Password Hashing?
• Are there any Test Vectors Available?
• Can I Use Draupnir in my Commercial Project?

Here we present some frequently asked questions about Draupnir.

What Systems does Draupnir Work on?

Draupnir has been compiled and developed with only Linux in mind, specifically for the gcc compiler, although the design per se is, obviously, platform independent, we do not provide support for other operating systems or environments.

Is Draupnir Cryptographically Secure?

To be completely honest, we don't know. Some people will feel nervous about the linearity of the operations used in Draupnir, and right they should. Some people will point out that there's a deliberate information loss in Draupnir when soaking in new input data, and right they are. The point is that we don't know.

One way or another, it is important to point out that there are very few cases when you actually need a cryptographically secure RNG, most of the times, a pseudorandom confusion sequence does the job just fine, so you could just use Draupnir in these cases and wait until some brave soul determines whether it constitutes a cryptographically secure RNG or not.

How Fast is Draupnir?

In its current implementation (and on my laptop), Draupnir can output roughly between 1Mb and 1.3Mb per second. We're working on making Draupnir faster though.

Note though, that a hardware implementation would be orders of magnitude faster, since most of the transition operations are heavily parallelizable.

Is Draupnir Recommended for Password Hashing?

A thousand times NO.

Password hashing is a delicate matter, and there are a lot of things to take into account. Draupnir, even with its relatively slow throughput, is far too fast to provide an adequate time barrier for attacks, furthermore, Draupnir's throughput can be dramatically increased in an ASIC implementation.

You should use one of the hashes tailored for that role: pbkdf2, bcrypt or scrypt (for a detailed analysis of the password hashing problem see: Salted Password Hashing - Doing it Right by Defuse.ca).

tl;dr: NO.

Are there any Test Vectors Available?

Here are the first 1024 bytes generated using the default configuration (64 bits, ECMA generator, all-1s initial value, all-1s xoring mask, 8 soaking rounds, 1 squeezing round, and π initial state):

6f60f4f0 a8909e47 edfe5bac 31d1057d 21bf17a1 70154574 dba6fba7 aa7a75d6
09bd6301 33b534cb b9c1038d 57f5f72d 7e08ef5a 9b147a51 402df398 1ad3f669
67a098f6 56d37e6f 936dec6b 59111010 ce2d74a3 18b10ff4 2b380072 00c04cf1
2c353bb7 84fc798c eaf7662a ff20f383 67b6a1eb 5f4eb59e ba1b5f2e 1ad09b1c
b2636438 dd6e9616 fa866131 68005b9a 69d9eea2 b2655f6b 2234cc0f e77dcb37
a1a2c1c1 1dd59835 b2ce42c2 947665f0 bfef306a 9aa77759 ba1e57d3 27a10281
f8d24598 e6b61354 93faffa0 ff82d09c 86abee74 a22e3850 4f44db41 52300256
1d97a271 e6f21292 129dc83f ecf465c0 e9ebaab7 2a090f49 4a535139 fa0fa739
00ee1551 6756ef89 16e95962 5ba94ebc e50e3fb9 3a335199 022d8a9d 3fb50fbc
2ff954b0 0f588015 8c98acb7 c58db2f7 8727e42f 260025ad 43843075 8282c9dc
609a3052 8e71c42a 37c62aba 95e15792 d26079e4 dfaf41ae 1b02b608 e06c3529
cec44b7a d0f866bb 2a2aa4ef 3dea9d06 b68e6f3b 1b0d05bf 533daa7c dec2e98f
b831c530 44df4a1f 871e97bd 1399721e 98c35b39 b14babd7 f5cdf09f 5c29c30e
1076e409 f9e82015 711fc0d8 02cc4c7a 2e2d0cfe f237c614 9d697803 3839256c
dffde3b0 10dfa6cd 62bee1a0 bca9edc5 d0038145 28d7bab6 0443430a ef6bf16c
87288399 76cc9b5f 8ce1a73a 9235cdf9 bad41483 a95aad35 f6e174a7 6d0021f0
f3ca8462 cf18beed 06ccffff 60b9d16b f1cda774 e8492459 ea68fb6e 80c7b931
0b1fb35e 39bc5ef2 f2713262 aafe0fed 0319f677 17f92168 9a481526 888cf7f3
7f6cc77a 631907f6 cf186d31 23ce972d b75e5b05 90527ee0 cf219155 9a855373
ca6383a9 34bafe91 94883d03 65ed4d1f 8bf36934 3d0ecb16 75724d02 d4baeb68
94ed9173 968549a4 0dfe73c6 fdbc0294 07c5bcfa 481d1858 0c643c62 8d9da082
4a3574f5 96a95c34 0d96351f 476cda9a 1331f36c abf255f8 3e780f4f 23ba1cbc
11c7e9c8 caefa821 c4ab8269 fdbc3956 acae2208 cd0507fb ca72d0e6 52e2c069
f9559380 47c72f6f a52bdbc8 246ad5e2 d15f694d add0dc67 276f3d66 f0215bd5
35c742e0 8f8ef55b 69e9b883 923f8fd6 351a8f03 a28cf6c7 8f5e59fc 771fcd94
77928d42 435f7ef5 4629157e 2a710bce a0c8af6d 0c619f9f bcae35f2 37763114
a66d7f23 7d7bcdb2 312ee495 8500144a aeb4c31b fec4ac0a c7c33783 b46194e3
75649902 e56f33ce 7b90bbc4 2b833dda 55ec2967 5db5503a 517a1ac1 56ed382b
511dea3c f11fa280 23f932d5 54b5a6ef a0172394 1e26f4e3 bdffd6f9 48e65f96
9022b3b6 b70fb714 e0c73276 1a8728b4 832566b8 8a10fe65 ee8f97ab a891b63c
658cf4ec ec8db780 9773bb7c c6349618 e686c705 894e6ba3 46d61bb1 303bcf90
4e399c0d f7a7fdef 20ba8e24 a0c885a6 eea4b561 7ee3d124 9fc9cfd0 a46f2016

grouped in bundles of 32 bits.

See doc/TESTVECTORS.md for more.

Can I Use Draupnir in my Commercial Project?

A priori, yes, but see the full text of the AGPLv3 (GNU Affero General Public License, version 3) for applicable conditions.

Contributing

There are a number of ways you can contribute to Draupnir's development:

• Propose new features (in the GitHub issue system).
• Report bugs (in the GitHub issue system, I'm sure there are a lot of these lurking in the shadows).
• Fix bugs (by submitting a pull request).
• Port Draupnir to another platform (although not officially supported now, if portability is not too much of a hassle, it can be provided).
• Attack it! Attacking RNGs is the only sure way we can be certain of their concrete strengths (and weaknesses). Even breaking Draupnir would allow us to further our understanding of the techniques involved.

For a detailed discussion of this last point, see the entry on "strength" on Ritter's Crypto Glossary and Dictionary of Technical Cryptography.

See CONTRIBUTING.md for contribution guidelines.

License

Draupnir is free software, distributed under the GNU Affero General Public License, version 3, or (at your option) any later version.

See the file LICENSE.md for the full text.