Oct 18, 2004

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.

one 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 the 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

  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 a pineapple… well, there is already Rambutan as a cipher so why not be a pineapple as a PRNG.

Updated on Feb 1, 2005

Despite good 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."

See also

Contact Us




Regular Mail

22 Sin Ming Lane #06-76
Midview City
Singapore 573969