(Whitebox Crypto) Using ChaCha20, is it safe to reduce the nonce length in a single block cipher?

Question

I am willing to write a Whitebox Crypto unit using ChaCha20 algorithm (Bernstein, D. 2008) for an input consisting of a single block. The fact it is going to be a single block cipher is of special importance here, as otherwise, the simple algorithm below wouldn't apply.

The principle is quite simple and reuses some logic from Chow et al: transform all inner block (formed by a series of 8 quarterround() functions looped 10 times) into a lookup table that takes the nonce as input. Notice that here, again, I am not considering more than one block of input, otherwise what I am proposing here wouldn't make sense, as a second round of the algorithm would have different x[0]..x[3].

In other terms, this is what I am trying to do. As in RFC 7539, instead of:

      chacha20_block(key, counter, nonce):
         state = constants | key | counter | nonce
         working_state = state
         for i=1 upto 10
            inner_block(working_state)
            end
         state += working_state
         return state
         end

I am willing to do something like:

      chacha20_1st_block(nonce):
         return lookup_tables(nonce)
         end

precomputing lookup tables where the counter is always 0 (or any other constant), and dimensioning the nonce such as the table size doesn't get too long, complementing the other bits with zero. For instance, if we consider nonces consisting of 13 bits, it is possible to generate 8192 tables containing 16 words of 32 bits, or exactly 512kB. Other sizes may be obtained by adjusting the nonce size.

I'm afraid I am making obvious questions here, but:

1. Am I considerably reducing the complexity of finding the original key this way?
2. Am I increasing attack chances?

EDIT 1: I left an implementation of the algorithm above in https://github.com/balena/chacha20-whitebox.

Answer 1

Am I considerably reducing the complexity of finding the original key this way?

No. If key was only used as input of chacha20_block(key, counter=0, nonce) when preparing the lookup_tables, then finding the original key is demonstrably at least as hard as breaking chacha20 (the algorithm) in its intended usage.

Am I increasing attack chances?

Depends comparing to what, and under what threat model. Most obvious issue: the nonce becomes predictable with sizable probability.

I'm looking for ways to increase the nonce length without exploding the memory size.

If we stick to producing the same results as chacha20_block(key, counter=0, nonce), modeling that only as a strong PRF of nonce, then demonstrably memory size in bits is at least: number of possible nonces × output width in bits.

On the other hand, it is possible to increase the nonce length. One trivial way is to have a normal-width nonce with only the low-order bits changing.

With some increase in memory, it is possible to use arbitrary and normal-width nounces, and even to hide their value until use: in the black box store F(nounce) where F is a public PRF such that collision among actually used nounces does not occur (either make F wide enough to have little collisions for random nounces, or restrict actually used nounces to avoid collision); and at each use compute F(nounce) and use the output to decide which tabulated value should be output.

---

Note: I'm not seeing the whole thing as true white box cryptography, because the would-be box is so severely limited in what it can compute. It is more like a One Time Pad with true randomness replaced by strong-pseudo randomness generated by a cryptographically strong PRNG which key is known to only one side. I see nothing this can achieve that plain symmetric crypto with diversified keys does not also achieve, with the later having the advatage of not requiring massive storage.