Rejection sampling is a method for turning raw random values into an unbiased result within a target range. Values that would distort the distribution are discarded and regenerated until the output is fair. It is commonly used when password or token generation must avoid the skew created by naive modulo reduction.
What Rejection Sampling Does
Rejection sampling is a simple way to remove bias from generated values. Instead of mapping every raw random value directly into a target range, the method discards values that would distort the distribution and keeps sampling until the result is uniform.
This matters because naive techniques such as modulo reduction can make some outcomes slightly more likely than others. Rejection sampling avoids that skew by accepting only values that fit the target space evenly, which is especially important when the output is used for passwords, tokens, or other security-sensitive randomness.
Why It Produces Unbiased Results
The core idea is to separate the source of randomness from the final accepted output. A generator may produce numbers across a larger space, but only the values that can be cleanly divided into the target range are accepted. The rest are rejected and replaced with fresh draws.
That acceptance rule is what preserves fairness. If the source space is not an exact multiple of the target size, some values would otherwise occur more often than others. Rejection sampling trims away the uneven remainder so each valid output has the same probability.
Where It Is Used in Security Engineering
Rejection sampling is commonly used when a system must derive unbiased values from a lower-level random source. Typical uses include password generation, token generation, random identifiers, and any routine that needs values distributed uniformly across a bounded range.
It is also a useful pattern in cryptographic and protocol-adjacent code because many security failures begin with small statistical bias. Even when the bias is subtle, repeated use at scale can make outputs easier to predict or can weaken assumptions about fairness and entropy.
For that reason, rejection sampling is often preferred over shortcuts that are easier to implement but less accurate. The extra sampling cost is usually small compared with the security value of keeping the distribution clean.
How It Differs from Naive Range Reduction
Naive range reduction takes a random number and compresses it into a smaller range, often with a modulus operation. That approach is fast, but it can create uneven frequencies unless the source range is already an exact multiple of the target range.
Rejection sampling adds one more step, but that step is the difference between approximate and exact uniformity. The method may occasionally redraw, yet it avoids the silent distortion that can appear when developers assume any mapping from a large random domain to a smaller one is automatically fair.
For security-sensitive outputs, the trade-off is usually worth it. A slightly slower algorithm that preserves uniformity is better than a faster one that introduces hidden bias.
Risk and Threat Considerations
Bias in random selection can become a security weakness when the output is used for secrets, tokens, or other values that should be hard to predict. An attacker does not need the bias to be dramatic, only consistent enough to narrow the search space or make some outputs more likely than others.
Failure mechanism: A flawed range-mapping method, such as naive modulo reduction, can overweight certain values whenever the source space and target range do not align evenly. Over many generations, that imbalance creates measurable skew instead of uniform randomness.
Impact: The resulting outputs can be easier to guess, easier to brute force, or less trustworthy as security material, especially when the generation process is repeated at scale.
Standards & Framework Alignment
This section maps relevant standards and security frameworks to the operational risks and controls described in this guidance.
NIST SP 800-53 Rev 5, NIST SP 800-63 and CIS Controls v8 set the governance and control requirements practitioners need to meet.
| Framework | Control / Reference | Relevance |
|---|---|---|
| NIST SP 800-53 Rev 5 | IA-5 — Authenticator Management | Covers secure handling of generated secrets and authenticators that depend on unbiased randomness. |
| SC-13 — Cryptographic Protection | Supports the need for correct cryptographic generation processes without introducing statistical bias. | |
| SI-10 — Information Input Validation | Relates to rejecting values that do not meet the required range before acceptance. | |
| Recommendation — Use IA-5 to generate and manage authenticators with uniform, non-biased randomness. Apply SC-13 to ensure cryptographic material is produced with sound randomness handling. Use SI-10 to validate generated values before accepting them into the target range. | ||
| NIST SP 800-63 | Digital Identity Guidelines | Covers unbiased generation expectations for secrets and authenticators used in digital identity workflows. |
| Recommendation — Follow the guidance to keep generated authenticators and secrets unpredictable and uniformly selected. | ||
| CIS Controls v8 | CIS-5 — Account Management | Uniform token and secret generation supports trustworthy account and access mechanisms. |
| Recommendation — Apply CIS-5 to keep account-related secrets and tokens generated from sound randomness. | ||
Practitioner Guidance
Why practitioners should care: Rejection sampling is a practical safeguard whenever uniformity matters more than raw speed. It is most important in code that emits passwords, API tokens, session-like values, or bounded random selections that must not drift toward predictable outcomes.
Common misunderstanding: A random source is not automatically unbiased after it is remapped into a smaller range. The fairness property has to survive the transformation step, and that is exactly where rejection sampling earns its value.
Practitioner takeaway: If the output must be uniformly distributed, treat the sampling step as part of the security control, not just an implementation detail.
Related resources from NHI Mgmt Group
- How should internal audit teams reduce reliance on manual sampling in multi-ERP environments?
- What do organisations get wrong about sampling-based data discovery?
- When does telemetry sampling create more risk than it reduces?
- Who should own changes to sampling and routing rules in telemetry pipelines?
