Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have a list of M=10,000..100,000 items and 32 bytes of sha256 H.
I want to choose N=10..100 items (without order).
Is there an efficient way to do this?
Or should I use something like (sha256hmac(n, H) & 0xFFFFFFFFFFFFFFFF) % N and skip duplicates. (Where n is 0..N-1.)
Is there an efficient way to do this?
32 bytes of "good randomness" provided by hashing some secret value gives much less entropy than required to directly compute a sample of 100 items from a list of 100000. If this is required for any cryptographic purpose, you must use a good CSPRNG to convert your starting entropy into as much randomness as you need.
If by efficient you mean "a one-liner", then probably not
Or should I use something like (sha256hmac(n, H) & 0xFFFFFFFFFFFFFFFF) % N and skip duplicates. (Where n is 0..N-1.)
DO NOT attempt to roll your own CSPRNG to generate what you need
What you are describing (repeated application of an HMAC to a changing value) is approximately an HMAC_DRBG described by NIST. If you want to use something along those lines to generate your bitstream, use that instead as it is far more secure than what you have described.
Furthermore, once you have a strong source of random bytes (e.g. the NIST DRBG), it is NOT enough to simply generate some bits, say $k$ such that $2^k$ is greater than $N = 100000$, take this mod $N$ and be done with it. When doing this, as $N$ will never perfectly divide $2^k$, you are inroducing bias into the random numbers generated; the smaller $2^k$ is in comparison to $N$, the greater the bias. Where $k$ is 64, as in the example you proposed, the bias is approximately $2^{-48}$. This may not seem like a lot, but if we consider the negligible function as $2^{-b}$, where $b$ is the "bits of security" of some cryptographic function, as we often do, then your RNG has only 48 "bits of security". Conseridering we are aiming for closer to 256, I would go as far as to suggest using a full 32 byte word of data from the CSPRNG to generate each of your indices.
This is quite a computationally intensive process, however, and it may be a better idea to, instead of taking a modulus in this manner, just generate the minimal number of bytes required to get a single index between 0 and $N$ and discard those bytes if they are at or above the highest multiple of $N$ smaller than the possible number represented by your bytes. For example, in 3 bytes with a max. possible value of 16777216: if the value is below 16700000, then take that mod $N$ and use the result, otherwise discard it and generate 3 fresh bytes from the CSPRNG stream. This could take theoretically infinite time to complete, but less on average than the previous method.
