Re: [Proposal] Table-level Transparent Data Encryption (TDE) and Key Management Service (KMS)

Hey everyone,

Here is my input regarding nonces and randomness.

> As I understand it, the NIST recommendation is a 96-bit *random* nonce,

I could not find that exact requirement in the NIST documents, though given
the volume of that library it would be possible to miss. The
recommendation I repeatedly saw for the nonce was unique. There is also an
important distinction that the nonce is not the Initialization Vector (IV),
it can be used as part of the IV, more on that later.

The most succinct definition for nonce I found was in SP-800-38A [1] page
4: "A value that is only used once."
SP-800-90A [2] (page 6) expands on the definition: "A time-varying value
that has at most a negligible chance of repeating, e.g., a random value
that is generated anew for each use, a timestamp, a sequence number, or
some combination of these."

The second definition references randomness but does not require it. [1]
(pg 19) reinforces the importance of uniqueness: "A procedure should be
established to ensure the uniqueness of the message nonces"

> That's certainly interesting, but such a brute-force with every key
> would allow it, where, if you use a random nonce, then such an attack
> would have to start working only after having access to the data, and
> not be something that could be pre-computed
> to talk about IV's not being secret

An unpredictable IV can be generated using a non-random nonce including a
counter, per [1] (pg 20):

"The first method is to apply the forward cipher function, under the same
key that is used for the encryption of the
plaintext, to a nonce. The nonce must be a data block that is unique to
each execution of the
encryption operation. For example, the nonce may be a counter, as described
in Appendix B, or
a message number. The second method is to generate a random data block
using a FIPS approved
random number generator."

A unique nonce gets passed through the cipher with the key, the uniqueness
of the nonce is the strength with this method and the key + cipher handle
the randomness for the IV. The second method listed above does require
a random number generator and if chosen those must conform to [2].

> I'm not a fan of the idea of using something which is predictable as a
> nonce. Using the username as the salt for our md5 password mechanism
> was, all around, a bad idea. This seems like it's repeating that
> mistake.

Yeah that MD5 stuff wasn't the greatest. With MD5 and the username as a
salt, the salt is known and you only need to work out the password. In
reality, you only need to find a collision with that password, the high
collision rate with MD5 (2^64) [3] made things really bad. That
(collisions) is not a significant problem today with AES to the best of my
knowledge.

Further, knowing the nonce gets you nowhere, it isn't the salt until it is
ran through the forward cipher with the encryption key. Even with the
nonce the attacker has doesn't know the salt unless they steal the key, and
that's a bigger problem.

The strictest definition of nonce I found was in [2] (pg 19) defining
nonces to use in the process of random generation:

"The nonce shall be either:
a. A value with at least (security_strength/2) bits of entropy, or
b. A value that is expected to repeat no more often than a
(security_strength/2)-bit random
string would be expected to repeat."

Even there it is randomness (a) or uniqueness (b).

[1]
https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38a.pdf
[2]
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
[3]
https://stackoverflow.com/questions/8852668/what-is-the-clash-rate-for-md5

Thanks,

Ryan Lambert
RustProof Labs