[Cryptech Tech] Seeking comments on a proposal for changes to the Cryptech RNG design.

[Manuel Domke]

Hi,

this is my first comment on this project. Don't have an Alphaboard to
play around with (yet).
But I have a special interest on the random number generation, as I
thought of making a version of the Cryptech HSM using modular entropy
multiplication. (in the far future).

I see there is a need to make it smaller/faster but I don't think its a
good option to "downgrade" to SHA-256.
From the (long-term) security perspective I'd prefer using SHA-3
(Keccak-1600) instead of SHA-2, like its done in my favorite entropy
source - the Infinite Noise TRNG - but whitening is fully implemented in
software.

Maybe Blake2s is a good option to go for now? Especially when you have
an (partial) implementation.
Its also been an SHA-3 finalist just like the winner Keccak-1600.

My plan was to work on a hardware implementation of Keccak-1600 used
together with modular entropy multiplication.
The principle of modular entropy multiplication also enables easier ways
to verify/monitor the proper function of the entropy source, as you have
this slight correlation of adjacent bits. Its a very unusual approach -
but I think its one of the best ways to collect entropy with confidence.

My background:
I'm software developer at DENIC eG and I've had the (personal) plan to
build an own HWRNG and also an open-hardware HSM - until I found the
Infinite Noise and the Cryptech project. I've founded a small business
to bring some open hardware projects to the market.

Currently I'm focusing on spreading the word about modular entropy
multiplication - and will start a crowdfunding campaign to sell some
Infinite Noise very soon. So I won't have the time to work much on this
project soon - but its on my todo list.
I stumbled upon the Cryptech project on Crowdsupply when looking for a
respectable/trustworthy crowdfunding platform, some month ago.

Greetings,

Manuel Domke


Am 22.03.2018 um 12:52 schrieb Joachim Strömbergson:
> Aloha!
>
> I'm considering changing part of the Cryptech RNG and would like
> feedback on it. The note below tries to explain why, how etc.
>
>
> Replacing the mixer in the Cryptech RNG
> =======================================
> 1. Intro:
> This is a short note about a possible change of the mixer stage in the
> Cryptech RNG. The note tries to describe the current solution, what we
> want to change and why. The note contains three possible solutions and
> then discuss the security implications.
>
>
> 2. Current architecture:
> The random number generator in Cryptech [1] currently consists of a
> chain comprising of three major stages:
>
> 1. A set of separate entropy sources. Currently one entropy source
>    external to the FPGA and one internal entropy source.
>
> 2. A stateful entropy mixer that generates seeds.
>
> 3. A deterministic random bit generator (DRBG)
>
> Between stage 2 and 3 there is also a FIFO capable of storing a few
> output words from the mixer. There are three reasons for the mixer:
>
>   1. Ensure that the entropy collected from the sources are mixed to
>   block bias in one source to dominate, affect the generated seed.
>
>   2. Ensure that an attack on the entropy sources at a given time does
>   not propagate to the seeds generated. This is due to the fact that
>   seeds generated does not only depend on entropy collected at a given
>   time, but also on an internal state.
>
>   3. Decouple the entropy collection and seed generation from the random
>   number generation. This allows the seed generation to continue
>   independently, updating the internal state. And when the random bit
>   generator is to be reseeded the seeds needed are ready.
>
> The last reason is both for security, but also for efficiency. The
> decoupled mixer allows us to reseed with very little affect on the
> random number generation performance. And compared to today, we probably
> want to reseed more frequently than today [1].
>
> The stateful entropy mixer consumes 32-bit words from the entropy
> sources selected in round-robin order. The mixer treats the words as
> being part of a continuous message. The words are combined into message
> blocks and hashed using SHA-512 (NIST FIPS 180-4) one block at a
> time. The output from the mixer is the updated message digest given by
> the consumed block and the previous hash state. This means that the
> output depends both on the consumed entropy words in a given block, but
> also on the digest state from all previous message blocks.
>
> The mixer message block size is 1024 bits. The internal state is 512
> bits and the output is 512-bits.
>
> The extracted 512-bit words are used in pairs to seed the DRBG. The DRBG
> is the stream cipher ChaCha with 256 bit key, 64 bit IV, 64 bit counter
> initial value and 256 bit input data block. In total 896 bits are used
> to seed the DRBG to its initial state.
>
>
> 3. Problem definition:
> There are two drivers for the change we want to do:
>
>   1. Decrease the FPGA resources used by the RNG.
>   2. Remove a major obstacle for running the Cryptech FPGA at 100 MHz.
>
> SHA-512 is a big core. In Xilinx Artix-7 the core requires 1575 Slices
> and 3918 registers. This is bigger than the ChaCha core that requires
> 1076 slices and 1949 registers.
>
> The SHA-512 core can be clocked at 96 MHz in Artix-7. This is just below
> a target frequency of 100 MHz. But to comfortably meet this clock, we
> would need a margin. Getting that margin would a redesign (pipelining of
> the round function) and basically halve the performance thus nullifying
> any performance gained by the increased clock speed.
>
>
> 4. Possible solutions:
> I see three possible solutions:
>
> 4.1 Replace with SHA-256
> Cryptech has a SHA-256 core in the repo. The core is well tested and
> used in several designs besides Cryptech. The SHA-256 core
> requires 688 Slices and 1929 regsisters. Basically halving the size of
> mixer.
>
> The difference in block size and digest size requires some
> adaptations. Using SHA-256 would require generating double the number of
> digests to seed ChaCha. The block size would change, but
> the rate of entropy consumption would stay the same. The internal state
> would decrease from 512 to 256 bits.
>
>
> 4.2 Replace with Blake2s
> The Blake2s hash function is much faster than SHA-256. In other
> respects the changes in block size, internal state would be the same as
> for SHA-256. I have a partial Blake2s core that could be completed if
> this is the direction chosen. Blake2s also supports key based hashing
> which would allow per-device unique mixing.
>
>
> 4.3 Replace with SipHash
> SipHash [3] is a short message PRF. The block size is 64 bits and
> SipHash generates digests of 128 bits. SipHash is really compact in
> hardware and is also very fast. SipHash is primarily used as hash
> function in FreeBSD, OpenDNS, Perl, Ruby, and Rust.
>
> I have a HW implementation of SipHash [4]. That core requires 432 Slices
> and 789 registers in Xilinx Artix-7. The core is capable of running at
> 173 MHz. In terms of size and clock speed, this core is really
> attractive.
>
> With SipHash the mixer would have to change quite a bit more. The
> solution I have in mind is to:
>
>   I. Process in total of 256 bits of entropy as a separate message and
>      generate a 128 bit digest for that message. This means that each
>      message is four blocks. Each block contains one 32-bit word from
>      each entropy source. No round-robin collector is needed.
>
>
>  II. Every odd message is used to generate a 128 bit key. The key is
>      used to generate the digest for the next message. Every even
>      message (generated by the key from the previous message) is used as
>      seed for the CSPRNG.
>
> This means that the 128 bit key is the internal state of the mixer.
>
> The FIFO between the mixer and the CSPRNG could also decrease in size
> since the seed word size would decrease from 512 to 128 bits.
>
>
> 5. Discussion:
> - From a technical point of view it would be quite easy to replace the
> SHA-512 core with another hash core (SHA-256 or Blake2s) or even
> SipHash). The difference in block size and digest size requires some
> adaptations. Using SHA-256 for example would require generating double
> the number of digests to seed ChaCha. The block size would change, but
> the rate of entropy consumption would stay the same.
>
> The SipHash based solution would be the more radical change. It would
> provide the biggest reduction in FPGA resources used. It would also
> change and simplify entropy collection.
>
> The big question is how the different solutions affects the security of
> the RNG chain. As I see it, this is mainly due to the size of the internal
> state. SHA-256 has an internal state of 256 bits. Blake2s in comparison
> has an internal state of 512 bits. With SipHash the state is given by
> the key and would be 128 bits.
>
> - From a high level perspective. We consume a large number of entropy bits
> to end up with a ChaCha key of 256 bits (we also set IV and initial
> value of the counter. But the security of the CSPRNG is in the key. With
> SHA-512, SHA-256 or SHA-512 the internal state is either bigger or equal
> to 256 bits. With SipHash the internal state is 128 bits.
>
> Another question with SipHash is if the 128 bit digests can be
> considered independent enough to be concatenated into a 256 bit key?
>
> Should we replace SHA-512 with something else? If so, under Which
> conditions? What core should we use instead?
>
> I personally think that Blake2s would be interesting, but that would
> require more work than SHA-256. SipHash is very tiny and very fast. But
> feels like a bigger change security wise.
>
>
>
> 6. Other changes considered
> I have a list of other changes that we might want to consider to do in
> the near term.
>
> 1. Feedback from CSPRNG to mixer. Basically extract the first N words
> from the CSPRNG and send back to the mixer as a third entropy
> source. These N words would not be provided to the applications. This
> adds another internal state that makes it harder for an attacker to
> control.
>
>
> 2. Change the seed FIFO into a mutator queue. Instead of simply hold a
> number of seed words and signal to the CSPRNG that there are seed words
> available, the queue would act as a mutator ring buffer. The mixer can
> keep on inserting words and inserted words are XOR:ed into the seed
> words stored in the buffer.
>
>
> 3. Add entropy monitors to the entropy providers. Currently the entropy
> providers perform warm-up before providing words. But the quality (or
> lack thereof) of the entropy generated is not checked. The proposed idea
> since way back is to add some AIS31 [5] tests to detect that the
> entropy sources at least are not totally broken and react if that
> happens.
>
>
>
> 7. References
> [1] Cryptech project. The Cryptech TRNG repoistory.
>     https://trac.cryptech.is/browser/core/rng/trng
>
>
> [2] Bernstein, D. J. "Fast-key-erasure random-number generators"
>     2017-07-23. https://blog.cr.yp.to/20170723-random.html
>
>
> [3] Aumasson, J-P. Bernstein, D. J. SipHash: a fast short-input PRF.
>     https://www.131002.net/siphash/
>
>
> [4] Strombergson. J. SipHash Verilog Implementation.
>     https://github.com/secworks/siphash
>
>
> [5] Bundesamt für Sicherheit in der Informationstechnik (BSI). "A
>     proposal for: Functionality classes and evaluation methodology for
>     true (physical) random number generators"
>
> https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_31_Functionality_classes_evaluation_methodology_for_true_RNG_e.pdf?__blob=publicationFile
>
> _______________________________________________ > Tech mailing list > Tech at cryptech.is >
https://lists.cryptech.is/listinfo/tech
-- 
13-37.org electronics
Manuel Domke
Adelheidstr. 59

65185 Wiesbaden

Mobile:     +49 163 1604329
Fax:        +49 611 8802 6666
Web:        https://13-37.org
VAT Nr:     DE313047369
WEEE-Reg:   DE86896758

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cryptech.is/archives/tech/attachments/20180322/c24ca8c6/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: OpenPGP digital signature
URL: <https://lists.cryptech.is/archives/tech/attachments/20180322/c24ca8c6/attachment-0001.sig>