Literatecode

This note describes the algorithm named Sapparot. It is a pseudo-random number generator (PRNG) with good statistical characteristics and performance. This generator consists of two 32-bits rotors with 32-bits 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

At the end of round rotors swaps around. Output random value produces as a result of (AÅB). The seed of PRNG is an initial state of the rotors and it is a 64-bits value. There are no weak seed values known for this generator.

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

Test vectors (hexadecimal values):

• A=0, B=0, Output=C95E78D3 1040CEB8 E65845CE 5D4283D0 5B0C7C04 030FC74F 8B15AAFD BCDAF4EE
• A=FFFFFFFF, B=FFFFFFFF, Output=36A3C7AC 0485B0EF 1772A301 E4B98B3D 45FACCBD A747749E EE0D23AB 02EF9BE9
• A=9E3779B9, B=12345678, Output=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 spent there and pineapple.. well, there is Rambutan as a cipher anyway so why not pineapple as a PRNG.

Update on Feb 1, 2005
Despite its great statistical characteristics Sapparot generator is cryptographically insecure on itself as it was shown by Dave 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'. Naive 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 naive 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."