Subject: Re: [Cfrg] Big-key cryptography

From: "Grigory Marshalko" <[email-masked]>
Date: Thu, 10 Dec 2015 21:58:21 +0000

This approach seems to have a lot of drawbacks in real life, since secure generation, distribution and storage of keys are usually the main problems, and for big keys they could grow exponentially. 

	Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru

---

From: Aaron Zauner <[email-masked]>
Date: Thu, 10 Dec 2015 23:11:59 +0100

Grigory Marshalko wrote:
> This approach seems to have a lot of drawbacks in real life, since
> secure generation, distribution and storage of keys are usually the main
> problems, and for big keys they could grow exponentially. 
>  

Please re-read the proposal.

Aaron

---

From: "Grigory Marshalko" <[email-masked]>
Date: Fri, 11 Dec 2015 07:57:06 +0000

I've read :) 
I mean that regardless the specific application of this idea it may be a problem of creating initial key/state/pool large enough. That's the point. But theoretically the whole approach is clear and could used in different mechanisms. That's ok.

Regards,
Grigory Marshalko,
expert,

---

From: Aaron Zauner <[email-masked]>
Date: Sat, 12 Dec 2015 16:04:49 +0100

Hi Grigory,

> I mean that regardless the specific application of this idea it may be a problem of creating initial key/state/pool large enough. That's the point. But theoretically the whole approach is clear and…

I'm not sure that I follow. What specific issues to you see with key
generation? What kind of pool do you have in mind?

Aaron

---

From: "Grigory Marshalko" <[email-masked]>
Date: Sat, 12 Dec 2015 18:20:35 +0000

Hi Aaron,

I mean that when we speak about key generation we should always control the amount of entropy. So the bigger the key the more entropy we need. That is the main problem in this approach - how to generate the initial key/state (By pool I mean entropy pool like in Fortuna RBG). 
Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
12 декабря 2015 г., 18:04, "Aaron Zauner" <[email-masked]> написал:
> Hi Grigory,
> 
> Grigory Marshalko wrote:
> 
>> I've read :)
>> I mean that regardless the specific application of this idea it may be a problem of creating
>> initial key/state/pool large enough. That's the point. But theoretically the whole approach is
>> clear and could used in different mechanisms. That's ok.
>

---

From: Aaron Zauner <[email-masked]>
Date: Tue, 15 Dec 2015 13:48:28 +0100

Hi Grigory,

See also Ryan's reply.

> I mean that when we speak about key generation we should always control the amount of entropy. So the bigger the key the more entropy we need. That is the main problem in this approach - how to gen…

Generation of "randomness" is not really a big issue anymore (at least
on Linux - probably pretty similar on other Operating Systems). These
days modern Intel Chips come with a RDRAND instruction that is mixed
into the pool (with many other inputs, e.g. IRQs). RDRAND

```
The RDSEED instruction was added to Intel Secure Key for seeding another
pseudorandom number generator,[16] available in Broadwell CPUs. The
entropy source for the RDSEED instruction runs asynchronously on a
self-timed circuit and uses thermal noise within the silicon to output a
random stream of bits at the rate of 3 GHz.
``` -- https://en.wikipedia.org/wiki/RdRand

If you're really clever you could do something like how BoringSSL seeds:
```
TLS servers that are pushing lots of AES-CBC need the RNG to be really
fast because each record needs a random IV. Because of this, if
BoringSSL detects that the machine supports Intel's RDRAND instruction,
it'll read a seed from urandom, expand it with ChaCha20 and XOR entropy
from RDRAND. The seed is thread-local and refreshed every 1024 calls or
1MB output, whichever happens first.
``` -- https://www.imperialviolet.org/2015/10/17/boringssl.html

HTH,
Aaron

---

From: Hanno Böck <[email-masked]>
Date: Tue, 15 Dec 2015 13:59:22 +0100

On Sat, 12 Dec 2015 18:20:35 +0000
"Grigory Marshalko" <[email-masked]> wrote:

> I mean that when we speak about key generation we should always
> control the amount of entropy. So the bigger the key the more entropy
> we need. That is the main problem in this approach - how to generate
> the initial key/state (By pool I mean entropy pool like in Fortuna
> RBG).

This is just wrong.

If you have once initialized your RNG with a proper seed (128 bits is
enough, 256 is already pretty much overkill) you have all the entropy
you need for the rest of your live as long as your PRNG is reasonably
properly designed.

The idea of having to re-seed your RNG is very pervasive, but it's
outright nonsense. There is no need to do something like this. If there
would be that would implicitly mean the function you're using for your
PRNG is broken.

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: "Grigory Marshalko" <[email-masked]>
Date: Wed, 16 Dec 2015 19:39:09 +0000

Hi, Aaron,

I agree that with developmnets in hardware the problem is going to be less serious on the one hand, but on the other hand we would always have enough room for suspicions :)  E.g.  https://www.alchemistowl.org/pocorgtfo/pocorgtfo03.pdf p.20 shows how linux random generation could fail in case of backdored RDRAND.

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
15 декабря 2015 г., 15:48, "Aaron Zauner" <[email-masked]> написал:
> Hi Grigory,
> 
> See also Ryan's reply.
> 
> Grigory Marshalko wrote:
> 
>> Hi Aaron,
>> 
>> I mean that when we speak about key generation we should always control the amount of entropy. So
>> the bigger the key the more entropy we need. That is the main problem in this approach - how to
>> generate the initial key/state (By pool I mean entropy pool like in Fortuna RBG).
>> Regards,
>

---

From: "Grigory Marshalko" <[email-masked]>
Date: Wed, 16 Dec 2015 19:44:30 +0000

This is not always true. See, for example, McGrew article http://eprint.iacr.org/2012/623/ This is obvously the case of no reseeding in block cipher-based RBGs.
Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
15 декабря 2015 г., 15:59, "Hanno Böck" <[email-masked]> написал:
> http://hboeck.de
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Alexandre Anzala-Yamajako <[email-masked]>
Date: Wed, 16 Dec 2015 23:34:40 +0100

Reseeding a prng is not nonsense if your threat model accounts for an
adversary that can reveal your internal state.

-- 
Alexandre Anzala-Yamajako

---

From: Aaron Zauner <[email-masked]>
Date: Thu, 17 Dec 2015 13:11:43 +0100

Hi Grigory,

> I agree that with developmnets in hardware the problem is going to be less serious on the one hand, but on the other hand we would always have enough room for suspicions :)  E.g.  https://www.alche…

Yes, that's why I've referred to the BoringSSL solution.

Aaron