[core] bMAC draft for constraint nodes

[Pascal Urien <[e-mail]>]

More details in https://tools.ietf.org/html/draft-urien-core-bmac-00

The goal of the bijective MAC (bMAC) is to compute an integrity value,
which cannot be guessed by off-line malicious software.
For classical keyed MACs, MAC is computed according to a fixed order. In
the bijective MAC, the content of N addresses (A[0]...A[N-1]) (N = #FLASH+
#SRAM…) is hashed according to a hash function H and a permutation P (i.e.
bijective application in [0,N-1]) so that :
bMAC(A, P) = H( A[P(0)] || A[P(1)] ... || A[P(N-1)]
The bMAC key is the permutation P. The number of permutations for N
addresses is N!, as an illustration 35! is greater than 2**128. So the
computation of the bMAC requires the knowledge of the whole memory; this is
trivial for genuine software, but it may be very difficult for corrupted
software.
Why is it difficult for a malicious software to compute bMAC?. Because it
must maintains a copy of the original software, what can be impossible if
the whole memory space is required for bMAC computation, especially in
harward architecture.
We build permutations in [1,q-1], with q prime, q being greater than N+1.
In Z/pZ, numbers prime with p-1 are called generators (gi), i.e. gi**x with
x in [1,q-1] is a permutation in [1,q-1]; so there are phi(p-1) generators
phi being the Euler number. This entropy may be increased by the
composition of multiple permutations, for example P(s2,g2,s1,g1)(x) =
s2.(g2 ** (s1.g1**x)) with s1, s2 in [q-1] and g1,g2 generators.
If the memory size is less than 2**16 calculations work with 32 bits
numbers; if the memory size is less than 2**32, calculations work with 64
bits numbers. For example with 8 bits (AVR) processors and clock in 12/16
MHz range the computing time (for P(s2,g2,s1,g1) is about 1ms/byte.

Here is a simple code for bMAC calculation. H is a SHA3-256 KECCAK hash
function, the address space is N= 9664, the prime number q is 9733. With a
8 bits processor, 12MHz clock, the bMAC is computed in about 10s, i.e. 1ms
per byte. Computations are performed with 32 bits numbers.

uint32-t x,y,bitn,v,gi[13];
uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator;
bool tohash;

PRIME =9733;
H.reset();

gi[0]= g2;
for (int n=1;n<=13;n++)
gi[n] = (gi[n-1] * gi[n-1]) % PRIME;

x= s1;

for(int i=1;i<PRIME;i++)
  { tohash = false
    x = (x*g1) % PRIME;
    bitn=x;
    y=1;
    for (int n=1;n<=14;n++)
    { if ( (bitn & 0x1) == 0x1)  y = (y*gi[n-1]) % PRIME;
      bitn = bitn >>1;
    }
    v = (y-1);
    // if address v exists, read the v address content A(v)
    // tohash=true ;
    if (tohash) H.update(A(v));
  }
  H.dofinal();

thoughts ?