Magic “Nothing Up My Sleeve” Numbers

Introduction

Just to be clear, this post does not endorse any cryptographic algorithms. It will only illustrate using source code how some magic numbers are created in such algorithms.

Nothing Up My Sleeve Numbers (NUMSN) are numeric constants in cryptographic algorithms which include from the designer a reasonable explanation for how they were created.

The purpose of explaining in detail how the numbers were created is intended to diminish any fears among users the numbers have some hidden properties that might purposely introduce a weakness only the designer knows about.

The motivation behind NUMSN is probably related to the Data Encryption Standard (DES) which as some of you know was designed by IBM with assistance from the wonderful NSA 🙂

The design criteria for DES was never published, and it was revealed the NSA changed the s-boxes without any explanation before it was officially made a standard.

So, naturally this change to the s-boxes in addition to reducing the key length from 64-bits to 56-bits provoked accusations of tampering, deliberately introducing weaknesses into the cipher. It was suggested by some in the cryptographic community, DES was weakened sufficiently enough to be compromised by the NSA if they ever needed to.

NSA introducing a weakness beyond reducing the key length from 64-bits to 56-bits was neither proved nor disproved.

It was revealed later, the changes to s-boxes improved resistance to Differential Cryptanalysis, an attack known to IBM designers, but which remained secret until being independently discovered in 1992 by Adi Shamir and Eli Biham.

As shown in Backdoors up my Sleeve by JP Aumasson, using NUMSN doesn’t automatically guarantee the security of a cryptographic algorithm, but any algorithm with numbers absent of a rational explanation or verifiable formula/algorithm, is generally going to be viewed with much more suspicion than if it did.

For example, there’s been suspicion surrounding algorithms part of the Chinese Trusted Platform Module (TPM).

They are as follows:

  • SM2 (Elliptic Curve Algorithm to rival ECDSA-P256)
  • SM3 (Cryptographic Hash to rival SHA-2)
  • SM4 (Block Cipher to rival AES-128)
  • ZUC (Stream Cipher)

All of the above algorithms contain magic numbers absent of any explanation behind their creation, and even though these ciphers remain unbroken by anyone in the public domain, that doesn’t mean they don’t have some weaknesses built-in.

The NUMSN I’ll cover in this post include: MD2, MD4, MD5, SHA-1, SHA-2, BLAKE2, Blowfish, AES, SEED, SAFER, XTEA, Gimli, RC5, RC6, Kuznyechik and ARIA.

If you just want to look at source codes for the above see the repo here.

MD2 cryptographic hash

RFC 1319 published in 1992 by Ron Rivest provides no explanation for how PI was generated beyond the following:

This step uses a 256-byte “random” permutation constructed from the digits of pi. Let S[i] denote the i-th element of this table. The table is given in the appendix.

Eventually someone asked the question on crypto stack exchange: How is the MD2 S-Table constructed from Pi

Señor Crypto (Mike Azo) requests explanation from Rivest via Email, and we finally discover the algorithm used.

// The first 722 digits of PI
uint32_t PI[722]=
{0x03, 0x01, 0x04, 0x01, 0x05, 0x09, 0x02, 0x06,
 0x05, 0x03, 0x05, 0x08, 0x09, 0x07, 0x09, 0x03,
 0x02, 0x03, 0x08, 0x04, 0x06, 0x02, 0x06, 0x04,
 0x03, 0x03, 0x08, 0x03, 0x02, 0x07, 0x09, 0x05,
 0x00, 0x02, 0x08, 0x08, 0x04, 0x01, 0x09, 0x07,
 0x01, 0x06, 0x09, 0x03, 0x09, 0x09, 0x03, 0x07,
 0x05, 0x01, 0x00, 0x05, 0x08, 0x02, 0x00, 0x09,
 0x07, 0x04, 0x09, 0x04, 0x04, 0x05, 0x09, 0x02,
 0x03, 0x00, 0x07, 0x08, 0x01, 0x06, 0x04, 0x00,
 0x06, 0x02, 0x08, 0x06, 0x02, 0x00, 0x08, 0x09,
 0x09, 0x08, 0x06, 0x02, 0x08, 0x00, 0x03, 0x04,
 0x08, 0x02, 0x05, 0x03, 0x04, 0x02, 0x01, 0x01,
 0x07, 0x00, 0x06, 0x07, 0x09, 0x08, 0x02, 0x01,
 0x04, 0x08, 0x00, 0x08, 0x06, 0x05, 0x01, 0x03,
 0x02, 0x08, 0x02, 0x03, 0x00, 0x06, 0x06, 0x04,
 0x07, 0x00, 0x09, 0x03, 0x08, 0x04, 0x04, 0x06,
 0x00, 0x09, 0x05, 0x05, 0x00, 0x05, 0x08, 0x02,
 0x02, 0x03, 0x01, 0x07, 0x02, 0x05, 0x03, 0x05,
 0x09, 0x04, 0x00, 0x08, 0x01, 0x02, 0x08, 0x04,
 0x08, 0x01, 0x01, 0x01, 0x07, 0x04, 0x05, 0x00,
 0x02, 0x08, 0x04, 0x01, 0x00, 0x02, 0x07, 0x00,
 0x01, 0x09, 0x03, 0x08, 0x05, 0x02, 0x01, 0x01,
 0x00, 0x05, 0x05, 0x05, 0x09, 0x06, 0x04, 0x04,
 0x06, 0x02, 0x02, 0x09, 0x04, 0x08, 0x09, 0x05,
 0x04, 0x09, 0x03, 0x00, 0x03, 0x08, 0x01, 0x09,
 0x06, 0x04, 0x04, 0x02, 0x08, 0x08, 0x01, 0x00,
 0x09, 0x07, 0x05, 0x06, 0x06, 0x05, 0x09, 0x03,
 0x03, 0x04, 0x04, 0x06, 0x01, 0x02, 0x08, 0x04,
 0x07, 0x05, 0x06, 0x04, 0x08, 0x02, 0x03, 0x03,
 0x07, 0x08, 0x06, 0x07, 0x08, 0x03, 0x01, 0x06,
 0x05, 0x02, 0x07, 0x01, 0x02, 0x00, 0x01, 0x09,
 0x00, 0x09, 0x01, 0x04, 0x05, 0x06, 0x04, 0x08,
 0x05, 0x06, 0x06, 0x09, 0x02, 0x03, 0x04, 0x06,
 0x00, 0x03, 0x04, 0x08, 0x06, 0x01, 0x00, 0x04,
 0x05, 0x04, 0x03, 0x02, 0x06, 0x06, 0x04, 0x08,
 0x02, 0x01, 0x03, 0x03, 0x09, 0x03, 0x06, 0x00,
 0x07, 0x02, 0x06, 0x00, 0x02, 0x04, 0x09, 0x01,
 0x04, 0x01, 0x02, 0x07, 0x03, 0x07, 0x02, 0x04,
 0x05, 0x08, 0x07, 0x00, 0x00, 0x06, 0x06, 0x00,
 0x06, 0x03, 0x01, 0x05, 0x05, 0x08, 0x08, 0x01,
 0x07, 0x04, 0x08, 0x08, 0x01, 0x05, 0x02, 0x00,
 0x09, 0x02, 0x00, 0x09, 0x06, 0x02, 0x08, 0x02,
 0x09, 0x02, 0x05, 0x04, 0x00, 0x09, 0x01, 0x07,
 0x01, 0x05, 0x03, 0x06, 0x04, 0x03, 0x06, 0x07,
 0x08, 0x09, 0x02, 0x05, 0x09, 0x00, 0x03, 0x06,
 0x00, 0x00, 0x01, 0x01, 0x03, 0x03, 0x00, 0x05,
 0x03, 0x00, 0x05, 0x04, 0x08, 0x08, 0x02, 0x00,
 0x04, 0x06, 0x06, 0x05, 0x02, 0x01, 0x03, 0x08,
 0x04, 0x01, 0x04, 0x06, 0x09, 0x05, 0x01, 0x09,
 0x04, 0x01, 0x05, 0x01, 0x01, 0x06, 0x00, 0x09,
 0x04, 0x03, 0x03, 0x00, 0x05, 0x07, 0x02, 0x07,
 0x00, 0x03, 0x06, 0x05, 0x07, 0x05, 0x09, 0x05,
 0x09, 0x01, 0x09, 0x05, 0x03, 0x00, 0x09, 0x02,
 0x01, 0x08, 0x06, 0x01, 0x01, 0x07, 0x03, 0x08,
 0x01, 0x09, 0x03, 0x02, 0x06, 0x01, 0x01, 0x07,
 0x09, 0x03, 0x01, 0x00, 0x05, 0x01, 0x01, 0x08,
 0x05, 0x04, 0x08, 0x00, 0x07, 0x04, 0x04, 0x06,
 0x02, 0x03, 0x07, 0x09, 0x09, 0x06, 0x02, 0x07,
 0x04, 0x09, 0x05, 0x06, 0x07, 0x03, 0x05, 0x01,
 0x08, 0x08, 0x05, 0x07, 0x05, 0x02, 0x07, 0x02,
 0x04, 0x08, 0x09, 0x01, 0x02, 0x02, 0x07, 0x09,
 0x03, 0x08, 0x01, 0x08, 0x03, 0x00, 0x01, 0x01,
 0x09, 0x04, 0x09, 0x01, 0x02, 0x09, 0x08, 0x03,
 0x03, 0x06, 0x07, 0x03, 0x03, 0x06, 0x02, 0x04,
 0x04, 0x00, 0x06, 0x05, 0x06, 0x06, 0x04, 0x03,
 0x00, 0x08, 0x06, 0x00, 0x02, 0x01, 0x03, 0x09,
 0x04, 0x09, 0x04, 0x06, 0x03, 0x09, 0x05, 0x02,
 0x02, 0x04, 0x07, 0x03, 0x07, 0x01, 0x09, 0x00,
 0x07, 0x00, 0x02, 0x01, 0x07, 0x09, 0x08, 0x06,
 0x00, 0x09, 0x04, 0x03, 0x07, 0x00, 0x02, 0x07,
 0x07, 0x00, 0x05, 0x03, 0x09, 0x02, 0x01, 0x07,
 0x01, 0x07, 0x06, 0x02, 0x09, 0x03, 0x01, 0x07,
 0x06, 0x07, 0x05, 0x02, 0x03, 0x08, 0x04, 0x06,
 0x07, 0x04, 0x08, 0x01, 0x08, 0x04, 0x06, 0x07,
 0x06, 0x06, 0x09, 0x04, 0x00, 0x05, 0x01, 0x03,
 0x02, 0x00, 0x00, 0x00, 0x05, 0x06, 0x08, 0x01,
 0x02, 0x07, 0x01, 0x04, 0x05, 0x02, 0x06, 0x03,
 0x05, 0x06, 0x00, 0x08, 0x02, 0x07, 0x07, 0x08,
 0x05, 0x07, 0x07, 0x01, 0x03, 0x04, 0x02, 0x07,
 0x05, 0x07, 0x07, 0x08, 0x09, 0x06, 0x00, 0x09,
 0x01, 0x07, 0x03, 0x06, 0x03, 0x07, 0x01, 0x07,
 0x08, 0x07, 0x02, 0x01, 0x04, 0x06, 0x08, 0x04,
 0x04, 0x00, 0x09, 0x00, 0x01, 0x02, 0x02, 0x04,
 0x09, 0x05, 0x03, 0x04, 0x03, 0x00, 0x01, 0x04,
 0x06, 0x05, 0x04, 0x09, 0x05, 0x08, 0x05, 0x03,
 0x07, 0x01, 0x00, 0x05, 0x00, 0x07, 0x09, 0x02,
 0x02, 0x07, 0x09, 0x06, 0x08, 0x09, 0x02, 0x05,
 0x08, 0x09, 0x02, 0x03, 0x05, 0x04, 0x02, 0x00,
 0x01, 0x09, 0x09, 0x05, 0x06, 0x01, 0x01, 0x02,
 0x01, 0x02, 0x09, 0x00, 0x02, 0x01, 0x09, 0x06,
 0x00, 0x08 };

uint32_t md2_rand(uint32_t n) {
    uint32_t        x, y;
    static uint32_t pos = 0;
    
    x = PI[pos]; pos++;
    y = 10;    
    
    if (n > 10) {
      x = (x * 10) + PI[pos]; pos++;      
      y = 100;
    }
    if (n > 100) {
      x = (x * 10) + PI[pos]; pos++;
      y = 1000;
    }
    if (x < (n * (y / n))) {
      return (x % n);
    }
    return md2_rand(n);
}

int main(void)
{
    uint32_t i, j, t, S[256];
    
    // Initialize s-box
    for (i=0; i<256; i++) {
      S[i] = i;
    }
    // Shuffle the S-box
    for (i=2; i<=256; i++) {
        j = md2_rand(i);
        t = S[j];
        S[j] = S[i-1];
        S[i-1] = t;
    }
    // Output the S-box
    bin2hex("MD2 PI sbox", S, 256); 
    return 0;
}

MD4 cryptographic hash

RFC 1320 published in 1992 by Ron Rivest uses 2 unique constants in the compression function.

The value 5A..99 is a hexadecimal 32-bit constant, written with the high-order digit first. This constant represents the square root of 2. The octal value of this constant is 013240474631.

The value 6E..A1 is a hexadecimal 32-bit constant, written with the high-order digit first. This constant represents the square root of 3. The octal value of this constant is 015666365641.

See Knuth, The Art of Programming, Volume 2 (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley. Table 2, page 660.

0x5a827999 is derived from the square root of 2 multiplied by 2**30
0x6ed9eba1 is derived from the square root of 3 multiplied by 2**30

#pragma intrinsic(fabs,pow,sin)

uint32_t p[2]={2,3};

uint32_t sqrt2int (uint32_t x) {
    uint32_t r;
    r = (uint32_t)(fabs(sqrt((double)p[x]))*pow(2,30));
    return r;
}

int main(void)
{
    int      i;
    uint32_t k[2];
        
    // create K constants
    for (i=0; i<2; i++) {
      k[i] = sqrt2int(i);
    }
    bin2hex("MD4 K constants", k, 2);  
    return 0;
}

MD5 cryptographic hash

RFC 1321 published in 1992 uses 64 unique constants in the compression function. These are calculated by passing 1-64 to the trigonometric sine function. Each result is multiplied by 2**32 before conversion to integer.

#pragma intrinsic(fabs,pow,sin)

uint32_t sin2int (uint32_t i)
{
    uint32_t r;
    r = (uint32_t)(fabs(sin(i)*pow(2,32)));
    return r;
}

int main(void)
{
    int      i;
    uint32_t t[64];

    // create T constants
    for (i=0; i<64; i++) {
      t[i] = sin2int(i+1);
    }
    bin2hex("MD5 T constants", t, 64);  
    return 0;
}

SHA-1 cryptographic hash

Designed by the NSA and published in 1995, this algorithm was definitely inspired by MD4.

The generation of K constants used in SHA-1 are exactly the same as those generated in MD4. There are 2 additional values derived from 5 and 10 respectively.

#pragma intrinsic(fabs,pow,sqrt)

uint32_t p[4]={2,3,5,10};

uint32_t sqrt2int (uint32_t x) {
    uint32_t r;
    r = (uint32_t)(fabs(sqrt((double)p[x]))*pow(2,30));
    return r;
}

int main(void)
{
    int      i;
    uint32_t k[4];
        
    // create K constants
    for (i=0; i<4; i++) {
      k[i] = sqrt2int(i);
    }
    bin2hex("SHA-1 K constants", k, 4);    
    return 0;
}

SHA-2 cryptographic hash

SHA-2 was published in 2001. The K constants are generated similar to how T constants are in MD5, except the first 64 prime numbers are used.

The H values are derived from square root of first 8 primes.
The K values are derived from cube root of first 64 primes.

#pragma intrinsic(fabs,pow,sqrt)

uint32_t p[64] =
{  2,   3,   5,   7,  11,  13,  17,  19, 
  23,  29,  31,  37,  41,  43,  47,  53,
  59,  61,  67,  71,  73,  79,  83,  89, 
  97, 101, 103, 107, 109, 113, 127, 131,
 137, 139, 149, 151, 157, 163, 167, 173, 
 179, 181, 191, 193, 197, 199, 211, 223,
 227, 229, 233, 239, 241, 251, 257, 263, 
 269, 271, 277, 281, 283, 293, 307, 311 };

// square root of integer, return fractional part as integer
uint32_t sqrt2int (uint32_t x) {
    uint32_t r;
    r = (uint32_t)(fabs(sqrt((double)p[x]))*pow(2,32));
    return r;
}

// cube root of integer, return fractional part as integer
uint32_t cbr2int (uint32_t x) {
    uint32_t r;
    r = (uint32_t)(fabs(pow((double)p[x],1.0/3.0))*pow(2,32));
    return r;
}

int main(void)
{
    int      i;
    uint32_t h[8], k[64];
    
    // create H constants
    for (i=0; i<8; i++) {
      h[i] = sqrt2int(i);
    }
    bin2hex("SHA-256 H constants", h, 8);
    
    // create K constants
    for (i=0; i<64; i++) {
      k[i] = cbr2int(i);
    }
    bin2hex("SHA-256 K constants", k, 64);  
    return 0;
}

Blowfish Block Cipher

Designed in 1993 and published in 1994, Blowfish became very popular among people who did not trust the security of DES.

The P and S boxes are derived from 8336 hexadecimal digits of Pi using Bailey–Borwein–Plouffe formula (BBP).

I’ve used code by David Bailey which you can find here.

static double expm (double p, double ak)

/*  expm = 16^p mod ak.  
  This routine uses the left-to-right binary 
  exponentiation scheme. */

{
  int i, j;
  double p1, pt, r;
#define ntp 25
  static double tp[ntp];
  static int tp1 = 0;

/*  If this is the first call to expm, 
  fill the power of two table tp. */

  if (tp1 == 0) {
    tp1 = 1;
    tp[0] = 1.;

    for (i = 1; i < ntp; i++) tp[i] = 2. * tp[i-1];
  }

  if (ak == 1.) return 0.;

/*  Find the greatest power of two less than or equal to p. */

  for (i = 0; i < ntp; i++) if (tp[i] > p) break;

  pt = tp[i-1];
  p1 = p;
  r = 1.;

/*  Perform binary exponentiation algorithm modulo ak. */

  for (j = 1; j <= i; j++){
    if (p1 >= pt){
      r = 16. * r;
      r = r - (int) (r / ak) * ak;
      p1 = p1 - pt;
    }
    pt = 0.5 * pt;
    if (pt >= 1.){
      r = r * r;
      r = r - (int) (r / ak) * ak;
    }
  }

  return r;
}

static double series (int m, int id)

/*  This routine evaluates the series  sum_k 16^(id-k)/(8*k+m) 
    using the modular exponentiation technique. */

{
  int k;
  double ak, p, s, t;
#define eps 1e-17

  s = 0.;

/*  Sum the series up to id. */

  for (k = 0; k < id; k++){
    ak = 8 * k + m;
    p = id - k;
    t = expm (p, ak);
    s = s + t / ak;
    s = s - (int) s;
  }

/*  Compute a few terms where k >= id. */

  for (k = id; k <= id + 100; k++){
    ak = 8 * k + m;
    t = pow (16., (double) (id - k)) / ak;
    if (t < eps) break;
    s = s + t;
    s = s - (int) s;
  }
  return s;
}

unsigned char get_byte(int id)
{
  double y;
  unsigned char first, second;
  double s1 = series (1, id);
  double s2 = series (4, id);
  double s3 = series (5, id);
  double s4 = series (6, id);
  double pid = 4. * s1 - 2. * s2 - s3 - s4;
  
  pid = pid - (int) pid + 1.;

  y = fabs(pid);
  y = 16. * (y - floor (y));
  first = y;
  //y = 16. * (y - floor (y));
  //second = y;
  return first; //(first << 4) | second;
}

// generates digits for blowfish..very slow 😦   
// apparently Fabrice Bellard formula is faster
unsigned int boxes[1024+18];
    
void main(void)
{
    int i, j;
    unsigned int x, *p;
    
    p = (unsigned int*)boxes;
    
    printf ("\nGenerating digits of Pi"
            "\nThis might take a while...\n");
    
    for (i=0; i<(1024+18)*8; i+=8) {    
      x = 0;
      for (j=0; j<8; j++) {
        x <<= 4;      
        x |= get_byte(i+j);
      }
      *p++ = x;    
    }
    printf (" // p-box\n");
    // p-box
    for (i=0; i<18; i++) {
      if ((i & 3)==0) putchar('\n');
      printf (" 0x%08x,", boxes[i]);
    }
    
    // s-box
    for (i=0; i<1024; i++) {
      if ((i & 3)==0) putchar('\n');
      if ((i & 255)==0) { 
        printf(" // sbox-%i\n", (i/256)+1); 
      }
      printf (" 0x%08x,", boxes[i+18]);    
    }  
}

Rijndael Block Cipher

The Advanced Encryption Standard published in 2001 which was designed by Joan Daemen and Vincent Rijmen.

// Multiplication
uint8_t gf_mul(uint8_t x, uint8_t y, uint8_t p)
{
    uint8_t z = 0;

    while (y) {
      if (y & 1) {
        z ^= x;
      }
      x = (x << 1) ^ (x & 0x80 ? p : 0x00);
      y >>= 1;
    }
    return z;
}

int main (void)
{
    uint8_t gf_log[256], s[256], s_inv[256];
    int     i, x;

    for (i=0, x=1; i<256; i++) {
      gf_log[i] = x;
      x ^= gf_mul(2, x, 0x1b);
    }

    s[0] = 0x63;
    
    for (i=0; i<255; i++) {
      x = gf_log[255 - i];
      x |= x << 8;
      x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
      s[gf_log[i]] = (x ^ 0x63);
    }
    
    for (i=0; i<256; i++) {
      s_inv[s[i]] = i;
    }
  
    bin2hex("AES sbox", s, 256);
    bin2hex("AES inverse sbox", s_inv, 256);    
    return 0;
}

SAFER Block Cipher

Secure And Fast Encryption Routine (SAFER) by James Lee Massey was submitted to both AES and NESSIE competitions.

// Modular exponentiation
int powmod (int b, int e, int m)
{
    int r = 1;
    
    while (e > 0) {
      if (e & 1) {
        r = r * b % m;
      }
      b = b * b % m;
      e >>= 1;
    }
    return r;
}

int main(void)
{  
    int      x, i;
    uint8_t  s0[256], s1[256];

    // create sbox
    for (x=0; x<256; x++) {
      s0[x] = powmod(45, x, 257) % 256;            
    }
    // create inverse sbox
    for (i=0; i<256; i++) {
      s1[s0[i]] = i;
    }
    bin2hex("SAFER sbox", s0, 256);
    bin2hex("SAFER inverse sbox", s1, 256);   
    return 0;
}

SEED Block Cipher

SEED was published in 1998 and directly a response by the Korea Information Security Agency to concerns about export restrictions on cryptography imposed by the US government that only allowed 40-bit RC4 encryption at the time 🙂

// matrix used for s-box 1 generation in seed
uint8_t A1[8][8] = {
    {1,0,0,0,1,0,1,0},
    {1,1,1,1,1,1,1,0},
    {1,0,0,0,0,1,0,1},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,1,0,1},
    {0,0,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0}, 
    {0,0,0,1,0,1,0,0}, 
};

// matrix used for s-box 2 generation in seed
uint8_t A2[8][8] = {
    {0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,0,1},
    {1,1,1,1,1,1,1,0},
    {0,0,1,0,0,0,0,1},
    {1,0,0,0,1,0,1,0},
    {1,0,0,0,1,0,0,0},
    {0,1,0,0,0,0,1,0},
    {0,0,0,1,0,1,0,0},
};

// Multiplication
uint8_t gf_mul(uint8_t x, uint8_t y, uint8_t p)
{
    uint8_t z = 0;

    while (y) {
      if (y & 1) {
        z ^= x;
      }
      x = (x << 1) ^ (x & 0x80 ? p : 0x00);
      y >>= 1;
    }
    return z;
}

// Exponentiation
uint8_t gf_exp(uint8_t b, uint8_t e, uint8_t p)
{
    uint8_t r = 1;
    uint8_t t = b;
    
    while (e > 0) {
      if (e & 1) {
        r = gf_mul(r, t, p);
      }
      t = gf_mul(t, t, p);
      e >>= 1;
    }
    return r;
}

// Matrix Multiplcation
uint8_t matmul(uint8_t mat[8][8], uint8_t a) {
    uint8_t res = 0;
    int     x, y;
    
    for (x = 0; x < 8; x++) {
      if (a & (1 << (7 - x))) {
        for (y = 0; y < 8; y++) {
          res ^= mat[y][x] << (7 - y);
        }
      }
    }
    return res;
}

int main(void)
{  
    int      x, i;
    uint8_t  s0[256], s1[256];
    uint32_t g = 0x9e3779b9;
       
    for (x=0; x<256; x++) {
      s0[x] = matmul(A1, gf_exp(x, 247, 99)) ^ 169;
      s1[x] = matmul(A2, gf_exp(x, 251, 99)) ^ 56;      
    }

    bin2hex("SEED sbox", s0, 256);
    bin2hex("SEED inverse sbox", s1, 256);

    printf ("\n // SEED constants");
    
    for (i=0; i<16; i++) {
      if ((i & 1)==0) putchar('\n');
      printf (" 0x%08x, ", g);
      g = (g << 1) | (g >> 32-1);
    }
    putchar('\n');    
    return 0;
}

ARIA Block Cipher

Another algorithm designed by the Korea Information Security Agency published in 2003.

This uses a matrix multiplication function from code by Markku-Juhani O. Saarinen which does the same thing.

// matrix used for s-box 1 generation in aria
uint8_t A[8][8] = {
    {1,0,0,0,1,1,1,1}, 
    {1,1,0,0,0,1,1,1},
    {1,1,1,0,0,0,1,1},
    {1,1,1,1,0,0,0,1},
    {1,1,1,1,1,0,0,0},
    {0,1,1,1,1,1,0,0},
    {0,0,1,1,1,1,1,0}, 
    {0,0,0,1,1,1,1,1}, 
};

// matrix used for s-box 2 generation in aria
uint8_t B[8][8] = {
    {0,1,0,1,1,1,1,0}, 
    {0,0,1,1,1,1,0,1},
    {1,1,0,1,0,1,1,1},
    {1,0,0,1,1,1,0,1},
    {0,0,1,0,1,1,0,0},
    {1,0,0,0,0,0,0,1},
    {0,1,0,1,1,1,0,1}, 
    {1,1,0,1,0,0,1,1}, 
};

// Multiplication
uint8_t gf_mul(uint8_t x, uint8_t y, uint8_t p)
{
    uint8_t z = 0;

    while (y) {
      if (y & 1) {
        z ^= x;
      }
      x = (x << 1) ^ (x & 0x80 ? p : 0x00);
      y >>= 1;
    }
    return z;
}

// Exponentiation
uint8_t gf_exp(uint8_t b, uint8_t e, uint8_t p)
{
    uint8_t r = 1;
    uint8_t t = b;
    
    while (e > 0) {
      if (e & 1) {
        r = gf_mul(r, t, p);
      }
      t = gf_mul(t, t, p);
      e >>= 1;
    }
    return r;
}

uint8_t matmul8(uint8_t m[8][8], uint8_t x)
{
    int i, j;
    uint8_t y;
    
    y = 0;
    for (i = 0; i < 8; i++) {	
      if (x & (1 << i)) {
        for (j = 0; j < 8; j++)
          y ^= m[j][i] << j;
      }
    }	
    return y;
}

// modular inverse
uint8_t gf_inv(uint8_t a) {
    uint8_t j, b = a;
    for (j = 14; --j;)
        b = gf_mul(b, j & 1 ? b : a, 0x1b); 
    return b;
}

int main(void) 
{
    int     i, p, x;
    uint8_t s1[256], s1_inv[256], s2[256], s2_inv[256];

    for (x=0; x<256; x++) {
      // generate s-box 1 
      s1[x] = matmul8(A, gf_inv(x)) ^ 0x63; 
      // generate s-box 2
      s2[x] = matmul8(B, gf_exp(x, 247, 0x1b)) ^ 0xE2; 
    }
    for (i=0; i<256; i++) {
      s1_inv[s1[i]] = i;
      s2_inv[s2[i]] = i;
    }    
    bin2hex("ARIA s1", s1, 256);    
    bin2hex("ARIA inverse s1", s1_inv, 256);    
    
    bin2hex("ARIA s2", s2, 256);    
    bin2hex("ARIA inverse s2", s2_inv, 256);    
    return 0;
}

Kuznyechik “GrassHopper” Block Cipher

GOST R 34.12-2015 is an algorithm designed by the Russian government to replace their legacy standard GOST 28147-89

Although no design criteria for the sboxes was published, some cryptographers managed to reverse engineer the algorithm.
Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1

The following code was provided by the authors.

uint8_t inv[16]   = 
{0x0,0x1,0xc,0x8,0x6,0xf,0x4,0xe,0x3,0xd,0xb,0xa,0x2,0x9,0x7,0x5};

uint8_t nu_0[16]  = 
{0x2,0x5,0x3,0xb,0x6,0x9,0xe,0xa,0x0,0x4,0xf,0x1,0x8,0xd,0xc,0x7};

uint8_t nu_1[16]  = 
{0x7,0x6,0xc,0x9,0x0,0xf,0x8,0x1,0x4,0x5,0xb,0xe,0xd,0x2,0x3,0xa};

uint8_t sigma[16] = 
{0xc,0xd,0x0,0x4,0x8,0xb,0xa,0xe,0x3,0x9,0x5,0x2,0xf,0x1,0x6,0x7};

uint8_t phi[16]   = 
{0xb,0x2,0xb,0x8,0xc,0x4,0x1,0xc,0x6,0x3,0x5,0x8,0xe,0x3,0x6,0xb};

uint8_t alpha[8][8] = {
    {0,0,0,0,1,0,0,0},
    {0,1,0,0,0,0,0,1},
    {0,1,0,0,0,0,1,1},
    {1,1,1,0,1,1,1,1},
    {1,0,0,0,1,0,1,0},
    {0,1,0,0,0,1,0,0},
    {0,0,0,1,1,0,1,0},
    {0,0,1,0,0,0,0,0},
};

uint8_t omega[8][8] = {
    {0,0,0,0,1,0,1,0},
    {0,0,0,0,0,1,0,0},
    {0,0,1,0,0,0,0,0},
    {1,0,0,1,1,0,1,0},
    {0,0,0,0,1,0,0,0},
    {0,1,0,0,0,1,0,0},
    {1,0,0,0,0,0,1,0},
    {0,0,0,0,0,0,0,1},
};

// multiplcation by matrix over GF(2)
uint8_t matmul(uint8_t a, uint8_t mat[8][8]) {
  uint8_t res = 0;
  int x, y;
  
  for (x = 0; x < 8; x++)
    if (a & (1 << (7 - x)))
      for (y = 0; y < 8; y++)
        res ^= mat[y][x] << (7 - y);
  return res;
}

uint8_t gf_mul(uint8_t a, uint8_t b) {
  uint8_t p = 0;
  
  while (b) {
    if (b & 1) 
      p ^= a;
    if (a & 0x8)
      a = (a << 1) ^ 0x19;  // x^4 + x^3 + 1
    else
      a <<= 1;
    b >>= 1;
  }
  return p;
}

int main(int argc, char *argv[]) {
    int i, x, y, l, r, n, z;
    uint8_t pi[256], pi_inv[256];
    uint8_t *p;   
 
    // generate sbox 
    for(x = 0; x < 256; x++) {
        y = matmul(x, alpha);
        l = (y >> 4) & 0xf;
        r = y & 0xf;
        l = (r == 0) ? nu_0[l] : nu_1[gf_mul(l, inv[r])];
        r = sigma[gf_mul(r, phi[l])];
        y = matmul((l << 4) | r, omega);
        pi[x] = y;
    }
    // generate inverse sbox
    for (i=0; i<256; i++) {
      pi_inv[pi[i]]=i;
    }
    
    bin2hex("Kuznyechik sbox", pi, 256);
    bin2hex("Kuznyechik inverse sbox", pi_inv, 256);
    return 0;
}

Salsa / ChaCha Stream ciphers

Salsa published in 2005 and ChaCha in 2008 are both designed by Daniel Bernstein.

The 128-bit key version uses the string “expand 16-byte k” to initialize state.
The 256-bit key version uses the string “expand 32-byte k” to initialize state.

SipHash PRF

Pseudo Random Function (PRF) SipHash by Aumasson and Bernstein

Initializes the state with string “somepseudorandomlygeneratedbytes” big-endian encoded.

Various Algorithms

Block ciphers RC5, RC6, XTEA, Serpent, and more recently the permutation function Gimli all use Golden Ratio in hexadecimal format: 0x9E3779B9

RC5 and RC6 use euler constant minus 2: 0xB7E15163

uint32_t golden_ratio(void) {
    uint32_t r;
    r = (uint32_t)(fabs((sqrt((double)5)-1)/2)*pow(2,32));
    return r;
}

uint32_t euler_number(void) {
    uint32_t r;
    r = (uint32_t)(fabs(exp((double)1)-2)*pow(2,32)+1);
    return r;
}

int main(void)
{
  printf ("\nEuler Number = %08X\n", euler_number());  
  printf ("\nGolden Ratio = %08X\n", golden_ratio());
  return 0;
}

Summary

Wasn’t that fun? 😛 Now it all makes sense, right?

Although most of what I posted here is just source code, I wanted to compile various algorithms used to generate NUMSN values in one place.

There are still many algorithms out there the designers refuse to explain the source of inspiration for their magic numbers, and this inevitably means people will distrust the algorithm.

For source code to all of the algorithms mentioned above, see here

Advertisements
This entry was posted in cryptography, encryption, programming and tagged , , , , , , , , , , , , , . Bookmark the permalink.

One Response to Magic “Nothing Up My Sleeve” Numbers

  1. Pingback: Blowfish block cipher | crypto on x86 and ARM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s