Sapparot

In this note we will describe the algorithm named Sapparot. It is a pseudorandom number generator (PRNG) with good statistical characteristics and performance.

This generator consists of two 32-bit rotors with 32-bit output as a result of exclusive-OR (XOR) rotors confusion. The figure 1 below illustrates a round of Sapparot.

Figure 1: One round of Sapparot

Both A and B denotes rotors and φ ("phi") is a golden ratio constant. The rotors are synchronous and updates as

A = (A + φ) <<< 7
B = ( B ⊕ (¬A) ⊕ (A << 3) ) <<< 7

Rotors swap at the end of round. The output random value is a result of (A ⊕ B). The PRNG seed is a 64-bit value that is the rotor's initial state. There are no weak seed values known for Sapparot at this moment.

Here is the portable C implementation of Sapparot:

unsigned long Sapparot(void)
{
  static unsigned long a = 0, b = 0;

  a += 0x9e3779b9;  a = (a << 7) | (a >> 25);
  b ^= (~a) ^ (a <<3 ); b = (b << 7) | (b >> 25);
  b ^= a; a ^= b; b ^= a;

  return (a^b);
} /* Sapparot */

The test vectors (hexadecimal values):

A = 0, B = 0
C95E78D3 1040CEB8 E65845CE 5D4283D0
5B0C7C04 030FC74F 8B15AAFD BCDAF4EE

A = FFFFFFFF, B = FFFFFFFF
36A3C7AC 0485B0EF 1772A301 E4B98B3D
45FACCBD A747749E EE0D23AB 02EF9BE9

A = 9E3779B9, B = 12345678
88958DAE E5BCAF84 A91FDAD0 50667BB5
0A4F5CB0 DEF039B0 F21A594B 1799BECA

About the name: "Sapparot" is the transliteration of "pineapple" in Thai. Thai is because of few years I spent there and pineapple… well, there is Rambutan as a cipher anyway so why not a pineapple as a PRNG.

Updated on Feb 1, 2005

Despite nice statistical characteristics, Sapparot is cryptographically insecure primitive as pointed by David Wagner:

"Consider the t=32 version. Let (A,B) be one state value, and (A',B') be the next state value (without swap), so that
A' = (A + phi) <<< 7
B' = (B ^ not(A') ^ (A' << 3)) <<< 7
The two corresponding words of keystream output reveal D = A^B and D' = A'^B'.

Naïve attack: Guess A, use D to deduce B, calculate resulting A',B', identify correct guess using equation D' = A'^B'. Then can deduce all other keystream outputs. Workload (of this naïve attack): 2^t work.

There are better attacks that can solve the above two equations for A,B,A',B' given D,D' with O(2^10) (t=32) or O(2^18) (t=64) work, and perhaps even faster if one is more clever still."

Sapparot

Updated on Feb 1, 2005

See also