Disclaimer⌗

You’ve heard what they say about rolling your own crypto, right? Don’t do this at home. I would not deploy the program that I have just made into production. It’s not just algorithmic mistakes that you can make: individual implementations have a certain set of assumptions they operate in and for most applications the most stringent security measures are necessary. Leaking information through side channels and variable running times is a show stopper for cryptographic suites. You have been warned.

The idea⌗

I am not a cryptography expert (I never claimed to be), but I know a few things about math and CS. Fortunately, this is largely enough to make something interesting.

My algorithm is based on the NP-hard problem of polynomial reconstruction. Encryption is performed by following these steps:

  • Generate a key from a CSPRNG. The key is 624 32-bit unsigned integers.
  • Chop the message up into 64-byte blocks. Perform the remaining steps for each block.
  • Using MT19937, generate a random permutation of integers from 0 to 128 and a bit vector of 128 bits with exactly a half of the bits randomly set.
  • Treat the message as a set of 8-bit unsigned integers. Interpolate a polynomial (0,1,2,…,63,64,65,…)↦(m0,m1,m2,…,m63,c0,c1,…)(0,1,2,\ldots,63,64,65,\ldots) \mapsto (m_0,m_1,m_2,\ldots,m_{63},c_0,c_1,\ldots) where mm is the message and cc is a vector of 8 random numbers from MT19937 of degree 72 in the Galois field of order 256 using the Lagrange interpolation formula.
  • Evaluate this polynomial at 128 points from [128,256)[128, 256). This gives us a vector of 128 8-bit unsigned integers (which are statistically indistinguishable from noise) from which the original message can be recovered by re-interpolating and and evaluating at the first 64 points.
  • Corrupt 64 of the 128 points with cryptographically secure random numbers from /dev/urandom. Permute the 128 points using the permutation generated earlier.
  • This is the ciphertext. If we know which of the points have been corrupted, we can recover the polynomial by interpolating on the known 64 good points and the 8 random points known by the decoder and derived from the key. The message is then this polynomial evaluated at the first 64 points.

Without knowing the key, the attacker would have to try all the possible methods of eliminating the 64 corruted points, which is computationally infeasible. To my knowledge, there is no faster way because the problem of polynomial reconstruction is NP-hard. There are algorithms to recover the polynomial if the amount of errors is smaller than 32 (e.g. Berlekamp-Massey), but they are not applicable here as we always make 64 errors.

The code⌗ 

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
// Prelude
#define Fi(n, a...)for(int i=0;i<n;i++){a;}
#define Fid(n, a...)for(int i=n-1;i>=0;i--){a;}
#define Fid1(n, a...)for(int i=n-1;i>0;i--){a;}
#define Fj(n, a...)for(int j=0;j<n;j++){a;}
#define XCH(k,x,y){k t=x;x=y;y=t;};
#define _(a...) {return({a;});}
#define S static
#define V void
typedef uint8_t u8;   typedef uint16_t u16;
typedef uint32_t u32; typedef uint64_t u64;
S u8 M[256][256], D[256], LOG[256], EXP[510];   S FILE * rng;
V init() {
  int b = 1;  rng = fopen("/dev/urandom", "r");
  Fi(255, LOG[b] = i;  EXP[i] = EXP[i + 255] = b;
          if ((b <<= 1) >= 256) b = (b - 256) ^ 0x1D)
  Fi(256, Fj(256, if (i && j) M[i][j] = EXP[LOG[i] + LOG[j]]))
  Fi(256, int d = LOG[1] - LOG[i]; D[i] = EXP[d < 0 ? d + 255 : d])}
int cleanup()_(fclose(rng))
typedef struct { u8 p[128], b[16]; u32 mt[624], mti; } key;  S FILE * rng;
S u32 mtn(key * k) {
  u32 y, mag01[2] = { 0, 0x9908b0df };
  if (k->mti >= 624) {
    Fi(227, y = (k->mt[i] & 0x80000000) | (k->mt[i + 1] & 0x7fffffff);
            k->mt[i] = k->mt[i + 397] ^ (y >> 1) ^ mag01[y & 1])
    Fi(396, y = (k->mt[i + 227] & 0x80000000) | (k->mt[i + 228] & 0x7fffffff);
            k->mt[i + 227] = k->mt[i] ^ (y >> 1) ^ mag01[y & 1])
    y = (k->mt[623] & 0x80000000) | (k->mt[0] & 0x7fffffff);
    k->mt[623] = k->mt[396] ^ (y >> 1) ^ mag01[y & 1]; k->mti = 0;
  }
  y = k->mt[k->mti++];         y ^= y >> 11;
  y ^= (y << 7) & 0x9d2c5680;  y ^= (y << 15) & 0xefc60000;
  return y ^ (y >> 18);}
// Key
key kc_keygen()_(key k; Fi(624, k.mt[i] = fgetc(rng)); k.mti = 0; k)
#define KEY_SHUF Fid1(128, int j = mtn(k)%(i+1); XCH(u8, k->p[i], k->p[j]))
S V kc_nextkey(key * k) {
  Fi(128, k->p[i] = i)  Fi(16, k->b[i] = 0) KEY_SHUF
  Fi(64, k->b[k->p[i] >> 3] |= 1 << (k->p[i] & 7)) KEY_SHUF}
// Polynomial
S V kc_lagrange72(u8 * x, u8 * y, u8 * c) {
  u8 li[72] = { 0 }; li[0] = 1;
  Fi(72, memset(li, 0, 72); li[0] = 1; Fj(72, 
    if (i == j) continue;
    u8 d = D[x[i] ^ x[j]];
    Fid1(72, li[i] = li[i - 1] ^ M[li[i]][x[j]])
    li[0] = M[li[0]][x[j]];
    Fi(72, li[i] = M[li[i]][d]))
  Fj(72, c[j] ^= M[li[j]][y[i]]))}
S V kc_lagrange64(key * k, u8 * x, u8 * y, u8 * c) {
  u8 aX[72], aY[72]; memcpy(aX, x, 64); memcpy(aY, y, 64);
  Fi(8, aX[64 + i] = 64 + i; aY[64 + i] = mtn(k) % 256)
  kc_lagrange72(aX, aY, c);}
S u8 kc_horner71(u8 * c, u8 x)_(u8 r=c[71];Fid(71,r=M[r][x]^c[i])r)
// Encrypt/decrypt
S V kc_block_encrypt(key * k, u8 in[64], u8 out[128]) {
  kc_nextkey(k); u8 id[64], tmp[128]; Fi(64, id[i] = i) u8 c[72] = { 0 };
  kc_lagrange64(k, id, in, c); Fi(128, tmp[i] = kc_horner71(c, 128 + i))
  Fi(128, if (k->b[i >> 3] & (1 << (i & 7))) tmp[i] = fgetc(rng))
  Fi(128, out[i] = tmp[k->p[i]])}
S V kc_block_decrypt(key * k, u8 in[128], u8 out[64]) {
  kc_nextkey(k);  u8 c[128], x[64], y[64], j = 0;
  { u8 ip[128]; Fi(128, ip[k->p[i]] = i) Fi(128, c[i] = in[ip[i]]) }
  Fi(128, if (!(k->b[i >> 3] & (1 << (i & 7)))) x[j] = 128 + i, y[j++] = c[i])
  memset(c, 0, 72);  kc_lagrange64(k, x, y, c); Fi(64, out[i] = kc_horner71(c, i))}
u64 kc_encrypt(key * k, u8 * in, u8 * out, u64 sz) {
  u8 * base = out;
  for(; sz > 64; in += 64, out += 128, sz -= 64) kc_block_encrypt(k, in, out);
  u8 tmp[64] = { 0xAA };  memcpy(tmp, in, sz); tmp[63] = sz;
  kc_block_encrypt(k, tmp, out);  return out - base + 128;}
u64 kc_decrypt(key * k, u8 * in, u8 * out, u64 sz) {
  u8 * base = out;
  for (; sz > 128; in += 128, out += 64, sz -= 128) kc_block_decrypt(k, in, out);
  if (sz != 128) return 0; u8 tmp[128];  kc_block_decrypt(k, in, tmp); sz = tmp[63];
  memcpy(out, tmp, sz);  memset(out + sz, 0, 64 - sz);  return out - base + sz;}
// Driver.
int main(V) {
  init();
  key k = kc_keygen();  key copy = k;
  FILE * inf = fopen("book1", "rb");
  u8 * buf = malloc(768771);
  fread(buf, 1, 768771, inf);
  fclose(inf);
  u8 * enc = malloc(1537542), * dec = malloc(768771);
  u64 encsz = kc_encrypt(&k, buf, enc, 768771);
  u64 decsz = kc_decrypt(&copy, enc, dec, encsz);
  printf("Decryption %s.\n", memcmp(buf, dec, 768771) ? "failed" : "successful");
  FILE * outf = fopen("book1.enc", "wb");
  fwrite(enc, 1, encsz, outf);
  fclose(outf);}

Feedback⌗

Think that this code sucks? Found a fatal flaw that I missed? Shoot me an e-mail.