A New Class of Random Number Generators: AWC and SWB in Light of Cryptanalysis

Research paper : George Marsaglia, Arif Zaman, A New Class of Random Number Generators , The Annals of Applied Probability , 1(3), 462–480, 1991. DOI: 10.1214/aoap/1177005878 .

Marsaglia and Zaman’s 1991 work introduced the Add-With-Carry (AWC) and Subtract-With-Borrow (SWB) families of pseudorandom generators. They develop the ideas of lagged-Fibonacci generators: a one-bit carry or borrow state is added to two delayed words. This small extension dramatically changes the algebraic structure: the sequence is related to modular arithmetic and can have a period of the order of a power of the base, preserving compact state and simple machine arithmetic.

The main cryptanalytic conclusion is fundamental: a long period, uniformity of complete cycles, and successful statistical tests do not guarantee cryptographic security. AWC/SWB are effective generators for modeling, but their linear (in a suitable representation) structure, finite internal state, and deterministic recursion make them unsuitable for generating secret keys, nonces, salts, session tokens, and bits for cryptographic protocols.

Historical context

By the early 1990s, practical computing required generators with long periods, small memory, and high speed. Conventional additive and subtractive lagged-Fibonacci schemes were fast, but their analysis and periodic properties did not always provide sufficient guarantees for long-term simulations. Marsaglia and Zaman proposed accounting for carry/borrow using just one additional bit of state.

This line of thought later became important for the Multiply-With-Carry (MWC) family, where carry is preserved under multiplication. In the engineering history of PRNGs, this is an example of a fruitful transition from “word arithmetic” to analysis through residual classes and rational p-adic representations.

Model and designations

Let the basis of the representation be equal to $b$ , usually $b = 2^{32}$ or $b = 2^{64}$ ; words $x_{i}$ belong ${0, \dots, b - 1}$ The delay parameters are satisfactory. $0 < r < s$ The state consists of $s$ last words and hyphenation/borrowing flag $c_{i} \in {0, 1}$ . $x_{i} = (x_{i - s} + x_{i - r} + c_{i}) mod b, c_{i + 1} = ⌊ \frac{x_{i - s} + x_{i - r} + c_{i}}{b} ⌋ .$

This is the AWC form: the new word is the least significant part of the sum, and $c_{i + 1}$ — its senior part. For SWB, subtraction and borrowing are defined as follows: otherwise $x_{i} = (x_{i - s} - x_{i - r} - c_{i}) mod b, c_{i + 1} = {\begin{cases} 1, & x_{i - s} - x_{i - r} - c_{i} < 0, \\ 0, & otherwise . \end{cases}$

Practical interpretation . $b = 2^{32}$

AWC adds two 32-bit words and carries; SWB subtracts two words and borrows. Therefore, the implementation naturally falls within the processor’s carry/borrow instructions.

Period and modulus

The key theoretical idea of the paper is to reduce the AWC/SWB behavior to multiplication by $b$ in a finite multiplicative group. For AWC, the essential modulus is $m_{A W C} = b^{s} + b^{r} - 1.$

For SWB a linked module is used $m_{S W B} = b^{s} - b^{r} + 1.$

For a suitable feasible initial state, the period is associated with a multiplicative order $b$ modulo $m$ : $T = {ord}_{m} (b), b^{T} \equiv 1 (\mod m) .$

If $m$ simple and $b$ — primitive root modulo $m$ , the full period is achieved $T = m - 1$ . It is the choice of parameters through factorization $m - 1$ , primality check $m$ and the antiderivative test turns the search for good parameters into a meaningful number theory problem, rather than a search for “lucky” lags.

Why is the period huge?

In classical additive recursion without carry, the state space is bounded by approximately $b^{s}$ , but the cycle structure can be significantly narrowed. Carry/borrow changes the state representation so that the maximum periods of AWC and SWB are close to the values $b^{s}$ The authors present configurations that can generate orders of magnitude $2^{1751}$ bits, $2^{1376}$ 32-bit integers or $2^{931}$ real numbers with 24-bit fractional part.

However, the phrase “period of order $2^{1376}$ ” means only that the state is extremely far away from being repeated during a sequential traversal of the loop. It says nothing about the computational difficulty of reconstructing the state from the observed output.

Uniformity of complete cycles

The article considers the uniformity of complete sequences and the connection of discrete words with fractional expansions in base $b$ Intuitively, a full cycle uniformly covers the admissible states/residues to the extent permitted by the modular construction. This is an important property for Monte Carlo: over a long full cycle, there is no systematic preference for one value over another.

But the uniformity of one-dimensional frequencies is a weak security criterion. A generator can produce perfectly balanced words and simultaneously be predictable after state recovery. Cryptographic pseudorandomness requires that an effective adversary be unable to distinguish a stream from a truly random one and be unable to predict the next bit with a non-zero advantage.

Contact MWC

MWC generalizes the carry mechanism: instead of adding two delayed words, it multiplies the word by a factor with carry. A typical scheme is $t_{i} = a x_{i - r} + c_{i}, x_{i} = t_{i} mod b, c_{i + 1} = ⌊ \frac{t_{i}}{b} ⌋ .$

Like AWC/SWB, MWC is analyzed using modular arithmetic; the period quality is determined by the properties of a specifically chosen module. The genetic connection here is conceptual: carry is not a side effect of the implementation, but rather part of the mathematical state that governs the period and structure of the sequence.

Cryptanalytic fact

Fact: AWC/SWB are not CSPRNGs. Their state is finite, the transition is deterministic, and the recurrence relations impose strong algebraic constraints on the observed words. A long period does not create a one-way function and does not replace cryptographic proof or reduction to a difficult problem.

Historically, the problem of predictable PRNGs has manifested itself repeatedly in network and application systems: predictable values have been used for TCP sequence numbers, session identifiers, passwords, and keying material. A classic developer lesson: an algorithm designed for statistical modeling cannot be transferred to a security-sensitive context simply because of its speed or claimed period.

State recovery mechanism

If the attacker receives consecutive full words $x_{i}$ , it knows the left-hand sides of the recursions. In AWC, unknown carry takes only two values, and in SWB, borrow is also binary. By checking the consistency of equalities over a window of length $s$ , the attacker restores the flags and the contents of the ring buffer; after this, any subsequent value is calculated using the same transition as the victim.

With truncated output, the problem is more difficult, but does not automatically become cryptographically hard: modulo constraints are used. $b$ , carries/borrows, SAT/SMT, integer programming, and state search. Correct threat assessment depends on which bits of each word are exposed, how many observations there are, and how the state is initialized.

Study code: AWC

Below is minimal demo code. It is intended solely for reproducible experiments and should not be used for secrets.

class AWC:
    def __init__(self, seed, r=24, s=55, base=2**32, carry=0):
        if len(seed) != s or not any(seed):
            raise ValueError("Нужно s слов; состояние не должно быть нулевым")
        self.x, self.r, self.s = list(seed), r, s
        self.base, self.carry, self.i = base, carry, 0

    def next_word(self):
        j = self.i
        t = self.x[(j - self.s) % self.s] + self.x[(j - self.r) % self.s] + self.carry
        self.x[j] = t % self.base
        self.carry = t // self.base
        self.i = (j + 1) % self.s
        return self.x[j]

A historical and applied example. This code is appropriate for a reproducible numerical experiment where the seed is published along with the paper: another researcher can replicate the Monte Carlo trajectory. In a cryptographic protocol, publishing or leaking approximately one output window would allow an adversary to continue the flow, so a CSPRNG from the OS or a ChaCha20/AES-based construction is needed.

Study code: SWB

class SWB:
    def __init__(self, seed, r=24, s=55, base=2**32, borrow=0):
        if len(seed) != s or not any(seed):
            raise ValueError("Нужно s слов; состояние не должно быть нулевым")
        self.x, self.r, self.s = list(seed), r, s
        self.base, self.borrow, self.i = base, borrow, 0

    def next_word(self):
        j = self.i
        t = self.x[(j - self.s) % self.s] - self.x[(j - self.r) % self.s] - self.borrow
        self.borrow = 1 if t < 0 else 0
        self.x[j] = t % self.base
        self.i = (j + 1) % self.s
        return self.x[j]

Archived example. Subtractive generators with lags have become widespread in scientific software due to their simplicity and speed; the subtract-with-carry variant was also used in Scheme implementations. This confirms their engineering value for insecure modeling, but does not change their cryptographic status: a deterministic model without a hidden key does not provide forward secrecy, backtracking resistance, or unpredictability.

What should not be confused

Property	AWC/SWB	CSPRNG requirement
Long period	Can be extremely large with good parameters	Useful, but not sufficient by itself
Statistical uniformity	Proved/studied for complete cycles	Necessary, but does not guarantee unpredictability
Hidden state	It is not the purpose of the design	Restoring the state must be computationally infeasible
Reversibility and prediction	Deterministic recursion allows the flow to continue after state recovery	Resilience to state compromise and protection against prediction are needed
Acceptable use	Modeling, testing, reproducible experiments	Keys, nonces, tokens, salt, and adversarial model draw

Safe to use

For cryptographic tasks, randomness should be obtained from a system CSPRNG: in Python, secrets or os.urandom(); in Linux, the kernel interface getrandom(); in a browser, crypto.getRandomValues(). For deterministic streams that require a key and reproducibility, use a DRBG or a stream cipher, such as ChaCha20, with a key obtained from a high-quality entropy source.

# Python: генерация 256-битного ключевого материала
import secrets
key = secrets.token_bytes(32)

# Публичный идентификатор/nonce, если протокол допускает случайный nonce
nonce = secrets.token_bytes(12)

An example from cryptanalysis. Even if AWC produces billions of unique 32-bit words, a token of the form hex(awc.next_word()) remains a bad idea: an observed series of tokens reveals data for state reconstruction. A CSPRNG’s output must be computationally unpredictable precisely in the active observer model.

Audit methodology

Determine the source of each random value: OS, library, user seed, time, PID, or PRNG.
Separate modeling from security loops: test generators should not be included in the production code of keys and tokens.
Check the volume and nature of the expanded output: full words, least significant bits, timestamp, and parallel instances.
Assess the state compromise: can the attacker predict future values or reconstruct past ones.
Replace the non-cryptographic PRNG with a system-wide CSPRNG and ensure protocol-specific nonce uniqueness.

Conclusions

Marsaglia and Zaman’s paper is a landmark work in generator theory and engineering: AWC/SWB elegantly combines lagged recursions, carry/borrow, and finite modular arithmetic. It explains how to achieve very long periods with little memory and simple operations.

For a cryptanalyst, the most valuable lesson is the distinction between statistical and cryptographic quality. An algebraically structured generator may be an excellent modeling tool, but in an adversary’s system, that same structure becomes an attack surface. Therefore, AWC/SWB and related MWCs should be viewed as general-purpose PRNGs, not as sources of cryptographic entropy.

Sources

New class of random number generators: AWC and SWB: https://seckey.ru/new-class-of-random-number-generators-awc-and-swb/

Marsaglia, G.; Zaman, A. (1991). A New Class of Random Number Generators . The Annals of Applied Probability, 1(3), 462–480. DOI: 10.1214/aoap/1177005878 .
Marsaglia, G.; Zaman, A.; Tsang, W. W. (1990). Toward a universal random number generator . Statistics & Probability Letters, 9(1), 35–39.
Klapper, A.; Goresky, M. (1997). Feedback Shift Registers, 2-Adic Span, and Combiners with Memory . Journal of Cryptology, 10, 111–147.
NIST SP 800-90A Rev. 1. Recommendation for Random Number Generation Using Deterministic Random Bit Generators .