Rejection Sampling

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.

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?