Assume I have a physical RNG module that generates $n$-bit random numbers that pass randomness tests such as the Dieharder suite. As it is a black box device with an unknown source of randomness, let us also assume it has potentially been partially compromised: an attacker who knows the workings of the RNG module, given a single previous state, can correctly guess the next state in $2^{n-m}$ steps for $1 \leq m \leq n$.
Let us also assume that I have access to another, verifiably uncompromised but otherwise poor quality entropy source giving $x - p$ bits of entropy per $x$ bits of output for $0 < p < x$. Let us also assume that this source of entropy is significantly slower than the aforementioned RNG module.
- To "launder" the first RNG source so that it produces truly unpredictable numbers, how much work will I have to do?
- To cancel the effects of $m$ on the output number, how many bits of entropy will I have to distill and provide from the entropy source?
- Which operations will I have to perform to ensure that I do not get a compromised number out? Will concatenation + hashing with a cryptographically secure hash function "do the trick"?
- Conversely, which operations will I have to avoid if I want the tampering to be "laundered" away?
- How much truncation will I have to do?
- Assuming that $m$ is sufficiently large/close to $n$, would it be better to just extract random bits from the second source and concatenate them into one number, bypassing the use of the potentially compromised module?
My assumptions:
I will have to use $m$ bits of uncompromised random output, concatenate it with the first output and hash that. I think truncating the concatenated output or the input number will not help too much if I don't know exactly which bits are compromised, or if I don't know the probabilities of which bit is compromised. I should avoid XORing the inputs before applying the hash.
I assume the "laundering" is reasonable up to $m = n/2$, beyond which I should probably just extract randomness from the second source and concatenate the random bits into a $n$-bit number, bypassing the potentially compromised module altogether.