Scientific article on the work: S. Tezuka, P. L’Ecuyer, R. Couture, On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators , ACM TOMACS, 3(4), 315–331, 1993.
Abstract. The add-with-carry (AWC) and subtract-with-borrow (SWB) generators proposed by Marsaglia and Zaman are attractive due to their speed, small memory, and huge periods. However, Teedzuka, L’Ecuyer, and Couture proved that their output sequences are practically identical to the output of a linear congruential generator (LCG) with a very large modulus. This translates the analysis of AWC/SWB into the language of lattices and spectral tests. The main result: when generating a single output from a single machine word (L=1), in dimensions t>r, widely separated hyperplanes with a distance of at least 1/sqrt(3) arise, i.e., a strong geometric correlation. The paper explains why a large period and good uniformity over single words do not guarantee cryptographic security.
Keywords: AWC, SWB, lagged Fibonacci, LCG, spectral test, dual lattice, PRNG cryptanalysis, predictability, RANMAR.
1. Statement of the problem
In 1991, Marsaglia and Zaman introduced AWC and SWB as fast, long-period generators; their state contains r words of base b and one carry or borrow bit. Adding a carry significantly increases the achievable period compared to a conventional additive lagged-Fibonacci generator. However, the task of a cryptographic PRNG differs from that of a simulation: the attacker observes the output, searches for algebraic relations, and reconstructs the internal state, rather than merely checking for frequency uniformity.
Cryptanalytic fact: A long period does not hinder prediction. If the output t-vectors are concentrated around a small number of affine hyperplanes or if the generator is equivalent to an LCG, the observed data has a deterministic structure. This is unacceptable for keys, nonces, IVs, session tokens, and salts.
2. Marsaglia families
Let b be the base, r>s>0 be the delays, x_i belong to {0,…,b-1}, and c_i belong to {0,1}. The indicator I(P) is equal to 1 if the statement P is true, and 0 otherwise.
2.1. Add-with-Carry
x_i = (x_{i-s} + x_{i-r} + c_i) mod bc_{i+1} = I(x_{i-s} + x_{i-r} + c_i >= b)
AWC adds two old words and a carry. For M = b^r + b^s – 1, if M is prime and b is a primitive root modulo M, the full period is M-1 = b^r+b^s-2.
2.2. Subtract-with-Borrow
x_i = (x_{i-s} - x_{i-r} - c_i) mod bc_{i+1} = I(x_{i-s} - x_{i-r} - c_i < 0)
For SWB-I, the associated modulus is M = b^r – b^s + 1; the full period is M-1 under the appropriate prime and primitivity conditions. The complementary variants AWC and SWB-II change the signs or order of subtraction, but do not eliminate the fundamental structural problem.
2.3. Word packing
From L consecutive words a number is constructed on [0,1):
u_i = sum_{j=1}^{L} x_{Li-j+1} b^{-j}, 1 <= L <= r.
For large bases, such as b=2^32, L=1 is typically chosen. This programming-friendly mode is the one that has a universally poor lattice structure in dimensions higher than r.
3. LCG equivalence
The key contribution of the paper is the explicit reduction of AWC/SWB to LCG. For a suitable state X_0 and a prime M, the following is considered:
X_i = A X_{i-1} mod M, A = b^{-1} mod Mw_i = X_i / M.
After synchronization of the initial states, the authors prove for i>=r:
u_i = b^{-L} floor(b^L w_i), |u_i - w_i| <= b^{-L}.
Therefore, AWC/SWB does not create independent “nonlinear” randomness: it is a truncated implementation of an LCG with a huge modulus, based on the L digits of the b-base. Carrying or borrowing is computationally convenient, but does not break the global modular linear relationship.
# Демонстрационный псевдокод AWC (НЕ использовать для криптографии)
def awc_step(state, b, r, s):
x, carry, i = state
z = x[(i-s) % r] + x[i % r] + carry
x[i % r] = z % b
carry = 1 if z >= b else 0
return x[i % r], (x, carry, (i+1) % r)Historical context. This kind of operation economy was especially valuable for PCs in the early 1990s: Marsaglia, Narasimhan, and Zaman described a SWB generator for PCs using 43 stored values and one subtraction operation. Modern cryptography, by contrast, requires a CSPRNG with provably difficult state recovery, not just fast arithmetic recurrences.
4. Gratings and spectral test
Consider the t-dimensional points from successive outputs:
w_{t,i} = (w_i, w_{i+1}, ..., w_{i+t-1}) in [0,1)^t.
For an LCG, all such points belong to the intersection of the unit hypercube with the L_t lattice. Equivalently, the points lie on a family of equally spaced parallel hyperplanes. A good generator for multidimensional modeling should make the gap d_t between these planes small; large empty “layers” of space indicate correlation.
| Indicator | Meaning | Interpretation |
|---|---|---|
| d_t | The distance between adjacent hyperplanes | The smaller it is, the thinner the empty layers and the better the space filling. |
| q_t | The ratio of the lengths of the shortest and longest vectors of the Minkowski-reduced basis | A value around 1 is preferred; a very small q_t indicates an anisotropic, poor lattice. |
| b^{-L} sqrt(t) | Upper bound for the deviation of AWC/SWB from the LCG vector | If it is significantly less than d_t, truncation does not mask the lattice defect. |
5. The bad dimensions theorem
For the L=1 regime, the authors obtain a particularly strong statement. The recurrence of AWC in the associated LCG form implies a modular connection:
X_{i-r} + X_{i-s} - X_i = 0 mod M.
It defines a short vector with square norm 3 in the dual lattice. Therefore, for all t>=r+1:
d_t >= 1 / sqrt(3) ~= 0.577350269.
This is not a small numerical error: a distance of about 0.577 in the normalized hypercube means that the t-dimensional points are located on extremely sparse layers. For SWB and other variants, the proof is the same, with the signs reversed.
6. Analysis of examples
6.1. Small SWB
For SWB-I with (b,s,r,L)=(2,2,9,9), the period is 508. The associated LCG has modulus 509 and multiplier 170; the output pairs almost form a lattice, although truncation makes the lines less than perfectly thin. This is a clear textbook example of how the borrow operation does not make a recurrence cryptographically unpredictable.
6.2. “Cool” AWC
For parameters (6,2,21,L), the modulus M=6^21+6^2-1 is prime, and the period is M-1. The authors showed poor spectral performance for several L, including the particularly unfortunate cases of L=17 and L=19 in low dimensions. Historically, this is an important correction to the intuition that “full period plus nearly uniform r-blocks means a high-quality generator.”
6.3. Recommended SWB
For the parameters (2^32,6,21,1) recommended by Marsaglia and Zaman, a guaranteed defect appears at t>21. Although the subcycle period is enormous, this does not negate the structural relationship between outputs separated by s and r positions.
6.4. RANMAR
RANMAR used SWB-I with (b,s,r,L)=(2^32-5,22,43,1); its full period is written as 2^1376-2^704+1. In the authors’ analysis, d_t does not exceed b^{-1} for t<=43, but becomes equal to 1/sqrt(3) for t>=44. P. L’Ecuyer also noted the spectacular failure of this generator on the birthday spacing test: the example shows that popularity and a colossal period are not a certificate of suitability for statistically sensitive problems.
7. Cryptanalysis
A spectral test isn’t a key recovery attack per se, but it does reveal the precise geometric reason why a generator is distinguishable from an ideal source. In cryptographic applications, such a distinguisher is already dangerous: secret values must not only be uniform individually but also computationally unpredictable as a sequence.
| Observation | Cryptanalytic investigation | Practical risk |
|---|---|---|
| AWC/SWB is close to LCG with an error of no more than b^{-L} | Algebraic and lattice methods for linear model analysis are available. | Predicting future outputs after state recovery/narrowing. |
| The connection X_{ir}+X_{is}-X_i = 0 mod M | Multivariate observations are not independent; there is a short dual lattice relation. | Probability bias in protocols using linked random values. |
| L=1 and t>r | The hyperplanes have a distance of at least 1/sqrt(3). | A reliable statistical distinguisher on blocks of sufficiently large dimension. |
| Small memory and deterministic update | Compromising the state reveals past/future values unless there is cryptographic protection of the state. | Leak of nonce, identifiers, session parameters. |
An important distinction. It’s not possible to claim that the theorem alone automatically implies a practical, fixed-difficulty attack on any specific seed. The correct conclusion is stronger and more accurate: the family does not satisfy the requirements of a CSPRNG because its output has a provable linear-lattice structure, and its state transition is not based on cryptographic one-wayness.
8. Life examples
- Scientific simulations of the 1990s. SWB was advantageous on low-end PCs due to the lack of multiplications and its long period. This is a legitimate engineering goal, but not a model for countering an active attacker.
- RANMAR in computational physics. Historical application in modeling illustrates the difference between a “fast enough source for old software” and a source for secrets; the identified birthday-spacing failure demonstrates that an applied test can detect the flaw before cryptanalysis.
- Incorrect nonce generation. If a web application generates nonce signatures, reset tokens, or session identifiers from AWC/SWB, an observer can collect sequential values and exploit deterministic relationships. Even the lack of an immediate recovery formula doesn’t justify the risk: the generator doesn’t provide the required cryptographic guarantee.
- Bitcoin/ECDSA. For ECDSA, the nonce must be secret and unpredictable; repeating or unpredicting the nonce can reveal the private key. Therefore, using AWC/SWB for nonces is unacceptable: a system-wide CSPRNG or a deterministic RFC 6979-like mechanism implemented by a trusted library should be used.
9. Practical recommendations
- Do not use AWC, SWB, RANMAR, LCG, or regular lagged-Fibonacci generators for keys, seeds, nonces, salts, session IDs, OTPs, or cryptographic protocols.
- For application code, use the system cryptographic source: Python
secrets/os.urandom, Linuxgetrandom(), Web Cryptocrypto.getRandomValues(), PHPrandom_bytes(). - For modeling, evaluate the generator in the relevant dimension using spectral and empirical tests; a huge period does not replace the analysis of the structure.
- If AWC/SWB is needed for a reproducible legacy model, isolate it from safety mechanisms and document the state, parameters (b,r,s,L) and applicability limitations.
# Python: криптографически безопасный токен
import secrets
session_token = secrets.token_urlsafe(32)
# 256-битное случайное значение
nonce_material = secrets.token_bytes(32)10. Conclusion
The work by Tezuka, L’Ecuyer, and Couture established a fundamental fact: AWC/SWB is practically an LCG with a huge modulus, realized through words, carries, and truncations. This makes the lattice theory of LCGs applicable to Marsaglia generators, and for L=1 in dimensions higher than r, their geometric defect has a universal lower bound: d_t>=1/sqrt(3).
Therefore, AWC/SWB should be considered historically important fast generators for certain modeling tasks, but not as cryptographic generators. The presence of short linear relations, a detectable lattice structure, and the lack of a computational one-sidedness mechanism make them unsuitable for generating secret values.
Literature
Lattice structure of AWC/SWB generators: https://allbi.ru/lattice-structure-of-awc-swb-generators/
- Tezuka, S., L’Ecuyer, P., Couture, R. On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators. ACM Transactions on Modeling and Computer Simulation , 3(4), 315–331, 1993. DOI: 10.1145/159737.159749.
- Marsaglia, G., Zaman, A. A New Class of Random Number Generators. Annals of Applied Probability , 1(3), 462–480, 1991. DOI: 10.1214/aoap/1177005878.
- James, F. A Review of Pseudorandom Number Generators. Computer Physics Communications , 60, 329–344, 1990.
- Knuth, DE The Art of Computer Programming, Vol. 2: Seminumerical Algorithms . Addison-Wesley.
- L’Ecuyer, P. Testing Random Number Generators. Proceedings of the 1992 Winter Simulation Conference , 305–313.