Yet another key extraction challenge (C++)

[dila]

The correct key will decrypt some fixed ciphertext into fixed plaintext. The known plaintext is apparently the digits of pi as hex digits.

#include <iostream>
#include <sstream>
#include <stdint.h>

int main(int argc, char* argv[])
{
  if (argc != 2) {
    std::cout << "Usage: " << argv[0] << " <key>" << std::endl;
    return 0;
  }

  uint64_t k;
  std::stringstream ss;
  ss << argv[1];
  ss >> std::hex >> k;
  if (!ss) {
    std::cout << "Invalid key!" << std::endl;
    return 0;
  }

  uint32_t s = 0;
  for (int i = 0; i < 10000; ++i) {
    s = s * 1664525 + 1013904223;
    int j = s % 64;
    uint64_t a = (k >> j) & 1;
    uint64_t b = (k & 1) << j;
    k ^= a ^ b;
  }

  uint64_t r = k ^ 0x1221777f1c3e4341;
  if (r == 0x3141592653589793) {
    std::cout << "Correct key!" << std::endl;
  } else {
    std::cout << "Wrong key!" << std::endl;
  }

  return 0;
}

[ArC]

The keys are 0x45584554CF4F4C52 and 0x455845544F4F4C53.


SPOILERS AHEAD


The key observation is that each round has the following transformation pattern:

0...0 -> 0...0       k_n -> k' (with k_n being the key for round n and k' := a ^ b in the original algorithm)
  0...0 -> 0...0       k_n -> k_{n+1} (with k_{n+1} := k_n ^ k')

1...0 -> 0...1
  1...0 -> 1...1

0...1 -> 1...0
  0...1 -> 1...1

1...1 -> 1...1
  1...1 -> 0...0

So in other words, after each round k_n(s_n) = k_n(0) (with s_n being the amount to shift for round n). k_{n-1} can be deduced from k_n(s_n) (or k_n(0)) and k_n(s_{n-1}) by matching the patterns outlined in the table above. For k_0 we can then match two patterns which is why there're two valid keys.

Some special care needs to be taken for rounds with zero shifts as these are effectively NOPs.

[SMH17]

Could you give a sample of the ciphertext encrypted?

[Syoma]

The ciphertext here is 0x3141592653589793 ^ 0x1221777f1c3e4341.
Forward step is k[i][j] = k[i][0] = k[i-1][j] ^ k[i-1][0], where j = gamma[i]. Simplify and you will see the bit 0 on the current step is result of comparison of bits on the previous step.
Reverse step was explained by @ArC: build the bitlogic operation table and use it to restore source bits. You need to know 2 steps to restore the bit value.

[dila]

Congrats ArC for getting the key(s).

I forgot to post my solution program here before:

#include <iostream>
#include <sstream>
#include <stdint.h>
#include <vector>
#include <set>

int main(int argc, char* argv[])
{
  /* identity matrix */
  int bits[64][64] = {0};
  for (int i = 0; i < 64; ++i) {
    bits[i][i] = 1;
  }

  /* build the parity check matrix */
  uint32_t s = 0;
  for (int i = 0; i < 10000; ++i) {
    s = s * 1664525 + 1013904223;
    int j = s % 64;
    for (int i = 0; i < 64; ++i) {
      int t = bits[0][i];
      bits[0][i] ^= bits[j][i];
      bits[j][i] ^= t;
    }
  }

  /* right-hand side "known" vector */
  uint64_t r = 0x3141592653589793 ^ 0x1221777f1c3e4341;
  int rv[64] = {0};
  for (int i = 0; i < 64; ++i) {
    rv[i] = (r >> i) & 1;
  }

  /* initialize row permutation lookup table */
  int p[64] = {0};
  for (int i = 0; i < 64; ++i) {
    p[i] = i;
  }

  /* run gaussian elimination */
  std::set<int> bf;
  std::set<int> pbf;
  for (int i = 0; i < 64; ++i) {
    bool ok = false;
    for (int j = i; j < 64; ++j) {
      if (bf.find(p[j]) != bf.end()) {
        continue;
      }
      if (bits[p[j]][i]) {
        int t = p[i];
        p[i] = p[j];
        p[j] = t;
        ok = true;
        break;
      }
    }
    if (!ok) {
      /* system is singular */
      /* reduce it from an NxN system to a (N-1)x(N-1) system */
      pbf.insert(p[i]); /* brute force this bit later */
      bf.insert(i);
      continue;
    }
    for (int j = i+1; j < 64; ++j) {
      if (pbf.find(p[j]) != pbf.end()) {
        continue;
      }
      if (bits[p[j]][i]) {
        for (int k = 0; k < 64; ++k) {
          bits[p[j]][k] ^= bits[p[i]][k];
        }
        rv[p[j]] ^= rv[p[i]];
      }
    }
  }

  std::vector<int> bfv;
  bfv.insert(bfv.end(), bf.begin(), bf.end());

  /* back-substitute to solve */
  std::set<int> solved;
  int bf_max = 1 << bf.size();
  for (int bfc = 0; bfc < bf_max; ++bfc) {
    int v[64] = {0};
    for (size_t i = 0; i < bfv.size(); ++i) {
      v[bfv[i]] = (bfc >> i) & 1; /* insert the bits we are brute forcing */
      solved.insert(bfv[i]);
    }
    for (int i = 0; i < 64; ++i) {
      int j = 64 - i - 1;
      if (bf.find(j) != bf.end()) {
        continue; /* we are guessing this */
      }
      int s = -1;
      int t = rv[p[j]];
      for (int k = 0; k < 64; ++k) {
        if (bits[p[j]][k]) {
          if (solved.find(k) != solved.end()) {
            t ^= v[k];
          } else {
            s = k;
          }
        }
      }
      if (s != -1) {
        /* solved one bit */
        v[s] = t;
        solved.insert(s);
      }
    }

    /* copy the solution to an int */
    uint64_t sol = 0;
    for (int i = 0; i < 64; ++i) {
      sol |= (uint64_t(v[i]) << i);
    }

    /* run the original algorithm */
    uint64_t key = sol;
    uint32_t s = 0;
    for (int i = 0; i < 10000; ++i) {
      s = s * 1664525 + 1013904223;
      int j = s % 64;
      uint64_t a = (key >> j) & 1;
      uint64_t b = (key & 1) << j;
      key ^= a ^ b;
    }

    /* test the soluton */
    r = key ^ 0x1221777f1c3e4341;
    if (r == 0x3141592653589793) {
      std::cout << std::hex << sol << std::endl;
    }

    /* repeat to find all keys */
    solved.clear();
  }

  return 0;
}