Merge branch 'fix-tweakey-m4'

6 files changed, 77 insertions, 26 deletions

diff --git a/src/add_felicsref/tweakey.c b/src/add_felicsref/tweakey.c
index 18a7792..47badde 100644
--- a/src/add_felicsref/tweakey.c
+++ b/src/add_felicsref/tweakey.c
@@ -81,11 +81,10 @@ static void _multiply(uint8_t TKj[LANE_BYTES], matrix_multiplication alpha)
 
 void tweakey_state_update(uint8_t TK[TWEAKEY_BYTES])
 {
-    /* Skip lane 0, as it is multiplied by the identity matrix. */
-
-    _multiply(TK + 1*LANE_BYTES, _multiply_M);
-    _multiply(TK + 2*LANE_BYTES, _multiply_M2);
-    _multiply(TK + 3*LANE_BYTES, _multiply_M3);
+    _multiply(TK + 0*LANE_BYTES, _multiply_M);
+    _multiply(TK + 1*LANE_BYTES, _multiply_M2);
+    _multiply(TK + 2*LANE_BYTES, _multiply_M3);
+    _multiply(TK + 3*LANE_BYTES, _multiply_M4);
 
 #if LANES_NB >= 5
     _multiply(TK + 4*LANE_BYTES, _multiply_MR);
diff --git a/src/add_python/lilliput/multiplications.py b/src/add_python/lilliput/multiplications.py
index a5faa55..09eaa08 100644
--- a/src/add_python/lilliput/multiplications.py
+++ b/src/add_python/lilliput/multiplications.py
@@ -23,8 +23,11 @@ from functools import reduce
 from operator import xor
 
 
+def _shl(xi, n):
+    return (xi << n) & 0xff
+
 def _Sl(n):
-    return lambda xi: (xi<<n) & 0xff
+    return lambda xi: _shl(xi, n)
 
 def _Sr(n):
     return lambda xi: xi>>n
@@ -36,16 +39,25 @@ def _0(xi):
     return 0
 
 def _M1(xi):
-    return (xi<<3 ^ xi>>3) & 0xff
+    return _shl(xi, 3) ^ xi>>3
 
 def _M2(xi):
-    return (xi<<6 ^ (xi&0b11111000) ^ xi>>6) & 0xff
+    return _shl(xi, 6) ^ xi&0b11111000 ^ xi>>6
 
 def _M3(xi):
-    return xi & 0b00011111
+    return _shl(xi>>3, 6) ^ xi>>6<<3
 
 def _M4(xi):
-    return ((xi<<2) & 0xff) >> 3
+    return _shl(xi, 2) >> 3
+
+def _M5(xi):
+    return _shl(xi, 5) ^ xi>>3<<2
+
+def _M6(xi):
+    return xi & 0b00011111
+
+def _M7(xi):
+    return _shl(xi, 2) >> 3
 
 
 M = (
@@ -81,6 +93,17 @@ M3 = (
     ( _0,     _0,    _Id,     _0,     _0,     _0,  _0,  _0),
 )
 
+M4 = (
+    ( _0,     _0, _Sl(6),    _M1,    _Id,     _0,     _0,  _0),
+    ( _0,     _0,     _0,    _M2,    _M1,    _Id,     _0,  _0),
+    ( _0, _Sl(2),     _0,    _M3,    _M2,    _M1,    _Id,  _0),
+    ( _0,    _M4, _Sl(2),     _0,     _0, _Sr(6), _Sr(3), _Id),
+    (_Id,     _0, _Sl(5), _Sl(2),     _0,     _0,     _0,  _0),
+    ( _0,    _Id,     _0,    _M5, _Sl(2),     _0,     _0,  _0),
+    ( _0,     _0,    _Id,     _0,     _0,     _0,     _0,  _0),
+    ( _0,     _0, _Sl(3),    _Id,     _0,     _0,     _0,  _0),
+)
+
 # NB: shift directions are reversed with respect to the specification
 # for powers of M_R, since the specification reverses the byte order
 # for those matrices.
@@ -99,7 +122,7 @@ MR = (
 MR2 = (
     ( _0,  _0, _Id,     _0,     _0,     _0,     _0,     _0),
     ( _0,  _0,  _0,    _Id, _Sr(3),     _0,     _0,     _0),
-    ( _0,  _0,  _0,     _0,    _Id, _Sr(3),    _M3,     _0),
+    ( _0,  _0,  _0,     _0,    _Id, _Sr(3),    _M6,     _0),
     ( _0,  _0,  _0,     _0,     _0,    _Id, _Sl(3),     _0),
     ( _0,  _0,  _0, _Sl(2),     _0,     _0,    _Id, _Sl(3)),
     ( _0,  _0,  _0,     _0, _Sl(2),     _0,     _0,    _Id),
@@ -109,8 +132,8 @@ MR2 = (
 
 MR3 = (
     (    _0,  _0,  _0,    _Id, _Sr(3),     _0,     _0,     _0),
-    (    _0,  _0,  _0,     _0,    _Id, _Sr(3),    _M3,     _0),
-    (    _0,  _0,  _0,    _M4,     _0,    _Id,    _M1,    _M3),
+    (    _0,  _0,  _0,     _0,    _Id, _Sr(3),    _M6,     _0),
+    (    _0,  _0,  _0,    _M7,     _0,    _Id,    _M1,    _M6),
     (    _0,  _0,  _0, _Sl(2),     _0,     _0,    _Id, _Sl(3)),
     (_Sl(3),  _0,  _0,     _0, _Sl(2),     _0,     _0,    _Id),
     (   _Id,  _0,  _0,     _0,     _0, _Sl(2), _Sl(5),     _0),
@@ -135,10 +158,10 @@ def _multiplication(m, reverse=True):
 
 
 ALPHAS = (
-    list,                       # Identity.
     _multiplication(M),
     _multiplication(M2),
     _multiplication(M3),
+    _multiplication(M4),
     _multiplication(MR, reverse=False),
     _multiplication(MR2, reverse=False),
     _multiplication(MR3, reverse=False)
diff --git a/src/add_threshold/tweakey.c b/src/add_threshold/tweakey.c
index 8f531d9..7822564 100644
--- a/src/add_threshold/tweakey.c
+++ b/src/add_threshold/tweakey.c
@@ -90,10 +90,11 @@ void tweakey_state_extract(
 
 typedef void (*matrix_multiplication)(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES]);
 
-static const matrix_multiplication ALPHAS[6] = {
+static const matrix_multiplication ALPHAS[7] = {
     _multiply_M,
     _multiply_M2,
     _multiply_M3,
+    _multiply_M4,
     _multiply_MR,
     _multiply_MR2,
     _multiply_MR3
@@ -102,16 +103,14 @@ static const matrix_multiplication ALPHAS[6] = {
 
 void tweakey_state_update(uint8_t TK_X[TWEAKEY_BYTES], uint8_t TK_Y[KEY_BYTES])
 {
-    /* Skip lane 0, as it is multiplied by the identity matrix. */
-
-    for (size_t j=1; j<TWEAK_LANES_NB; j++)
+    for (size_t j=0; j<TWEAK_LANES_NB; j++)
     {
         uint8_t *TKj_X = TK_X + j*LANE_BYTES;
 
         uint8_t TKj_old_X[LANE_BYTES];
         memcpy(TKj_old_X, TKj_X, LANE_BYTES);
 
-        ALPHAS[j-1](TKj_old_X, TKj_X);
+        ALPHAS[j](TKj_old_X, TKj_X);
     }
 
     for (size_t j=0; j<KEY_LANES_NB; j++)
@@ -124,7 +123,7 @@ void tweakey_state_update(uint8_t TK_X[TWEAKEY_BYTES], uint8_t TK_Y[KEY_BYTES])
         memcpy(TKj_X_old, TKj_X, LANE_BYTES);
         memcpy(TKj_Y_old, TKj_Y, LANE_BYTES);
 
-        ALPHAS[j-1 + TWEAK_LANES_NB](TKj_X_old, TKj_X);
-        ALPHAS[j-1 + TWEAK_LANES_NB](TKj_Y_old, TKj_Y);
+        ALPHAS[j + TWEAK_LANES_NB](TKj_X_old, TKj_X);
+        ALPHAS[j + TWEAK_LANES_NB](TKj_Y_old, TKj_Y);
     }
 }
diff --git a/src/add_tweakeyloop/multiplications.h b/src/add_tweakeyloop/multiplications.h
index 45b9eaa..650373b 100644
--- a/src/add_tweakeyloop/multiplications.h
+++ b/src/add_tweakeyloop/multiplications.h
@@ -55,6 +55,17 @@ static void _multiply_M3(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES])
     _multiply_M(M2_x, y);
 }
 
+static void _multiply_M4(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES])
+{
+    uint8_t M_x[LANE_BYTES];
+    uint8_t M2_x[LANE_BYTES];
+    uint8_t M3_x[LANE_BYTES];
+    _multiply_M(x, M_x);
+    _multiply_M(M_x, M2_x);
+    _multiply_M(M2_x, M3_x);
+    _multiply_M(M3_x, y);
+}
+
 static void _multiply_MR(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES])
 {
     y[0] = x[1];
diff --git a/src/ref/multiplications.h b/src/ref/multiplications.h
index 4de1848..c0645b9 100644
--- a/src/ref/multiplications.h
+++ b/src/ref/multiplications.h
@@ -71,6 +71,26 @@ static void _multiply_M3(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES])
     y[0] = x[5];
 }
 
+static void _multiply_M4(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES])
+{
+    uint8_t a_5  = x[5]<<3  ^ x[4];
+    uint8_t a_4  = x[4]>>3  ^ x[3];
+    uint8_t b_5 = a_5<<3 ^ a_4;
+    uint8_t b_4 = a_4>>3 ^ x[2];
+
+    uint8_t c_4 = b_4>>3 ^ x[6]<<2 ^ x[1];
+    uint8_t c_5 = b_5<<3 ^ b_4;
+
+    y[7] = b_5;
+    y[6] = c_5;
+    y[5] = c_5<<3 ^ c_4;
+    y[4] = c_4>>3 ^ x[5]<<2 ^ x[0];
+    y[3] = a_5<<2 ^ x[7];
+    y[2] = b_5<<2 ^ x[6];
+    y[1] = x[5];
+    y[0] = a_5;
+}
+
 static void _multiply_MR(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES])
 {
     y[0] = x[1];
diff --git a/src/ref/tweakey.c b/src/ref/tweakey.c
index 2f357ca..510f35a 100644
--- a/src/ref/tweakey.c
+++ b/src/ref/tweakey.c
@@ -63,10 +63,11 @@ void tweakey_state_extract(
 
 typedef void (*matrix_multiplication)(const uint8_t x[LANE_BYTES], uint8_t y[LANE_BYTES]);
 
-static const matrix_multiplication ALPHAS[6] = {
+static const matrix_multiplication ALPHAS[7] = {
     _multiply_M,
     _multiply_M2,
     _multiply_M3,
+    _multiply_M4,
     _multiply_MR,
     _multiply_MR2,
     _multiply_MR3
@@ -75,15 +76,13 @@ static const matrix_multiplication ALPHAS[6] = {
 
 void tweakey_state_update(uint8_t TK[TWEAKEY_BYTES])
 {
-    /* Skip lane 0, as it is multiplied by the identity matrix. */
-
-    for (size_t j=1; j<LANES_NB; j++)
+    for (size_t j=0; j<LANES_NB; j++)
     {
         uint8_t *TKj = TK + j*LANE_BYTES;
 
         uint8_t TKj_old[LANE_BYTES];
         memcpy(TKj_old, TKj, LANE_BYTES);
 
-        ALPHAS[j-1](TKj_old, TKj);
+        ALPHAS[j](TKj_old, TKj);
     }
 }