Hannes Frederic Sowa wrote: > A lockdep test should still be done. ;) Adding might_lock() annotations will improve coverage a lot. > Yes, that does look nice indeed. Accounting for bits instead of bytes > shouldn't be a huge problem either. Maybe it gets a bit more verbose in > case you can't satisfy a request with one batched entropy block and have > to consume randomness from two. The bit granularity is also for the callers' convenience, so they don't have to mask again. Whether get_random_bits rounds up to byte boundaries internally or not is something else. When the current batch runs low, I was actually thinking of throwing away the remaining bits and computing a new batch of 512. But it's whatever works best at implementation time. >>> It could only mix the output back in every two calls, in which case >>> you can backtrack up to one call but you need to do 2^128 work to >>> backtrack farther. But yes, this is getting excessively complicated. > >> No, if you're willing to accept limited backtrack, this is a perfectly >> acceptable solution, and not too complicated. You could do it phase-less >> if you like; store the previous output, then after generating the new >> one, mix in both. Then overwrite the previous output. (But doing two >> rounds of a crypto primtive to avoid one conditional jump is stupid, >> so forget that.) > Can you quickly explain why we lose the backtracking capability? Sure. An RNG is (state[i], output[i]) = f(state[i-1]). The goal of backtracking is to compute output[i], or better yet state[i-1], given state[i]. For example, consider an OFB or CTR mode generator. The state is a key and and IV, and you encrypt the IV with the key to produce output, then either replace the IV with the output, or increment it. Either way, since you still have the key, you can invert the transformation and recover the previous IV. The standard way around this is to use the Davies-Meyer construction: IV[i] = IV[i-1] + E(IV[i-1], key) This is the standard way to make a non-invertible random function out of an invertible random permutation. >From the sum, there's no easy way to find the ciphertext *or* the plaintext that was encrypted. Assuming the encryption is secure, the only way to reverse it is brute force: guess IV[i-1] and run the operation forward to see if the resultant IV[i] matches. There are a variety of ways to organize this computation, since the guess gives toy both IV[i-1] and E(IV[i-1], key) = IV[i] - IV[i-1], including running E forward, backward, or starting from both ends to see if you meet in the middle. The way you add the encryption output to the IV is not very important. It can be addition, xor, or some more complex invertible transformation. In the case of SipHash, the "encryption" output is smaller than the input, so we have to get a bit more creative, but it's still basically the same thing. The problem is that the output which is combined with the IV is too small. With only 64 bits, trying all possible values is practical. (The world's Bitcoin miners are collectively computing SHA-256(SHA-256(input)) 1.7 * 2^64 times per second.) By basically doing two iterations at once and mixing in 128 bits of output, the guessing attack is rendered impractical. The only downside is that you need to remember and store one result between when it's computed and last used. This is part of the state, so an attack can find output[i-1], but not anything farther back. > ChaCha as a block cipher gives a "perfect" permutation from the output > of either the CRNG or the CPRNG, which actually itself has backtracking > protection. I'm not quite understanding. The /dev/random implementation uses some of the ChaCha output as a new ChaCha key (that's another way to mix output back into the state) to prevent backtracking. But this slows it down, and again if you want to be efficient, you're generating and storing large batches of entropy and storing it in the RNG state. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
