Reverse engineering, Windows internals, x86 magic, low level programming, and everything else I feel like writing about.

CrySyS SecChallenge 2020: Meet NataSHA

NataSHA is a block cipher that has a 6-round Feistel structure and its round function is based on the SHA-1 hash function. The block size of NataSHA is 40 bytes and its key length is 48 bits (6 bytes). The encryption operation is illustrated in the figure below, where | means concatenation of byte strings and [+] denotes the XOR operation:

X = L0|R0

     L0                    R0
     |                     |
     |     +-----+         |
     |     |     |<--- K0  |
    [+]<---| SHA |<--------+
     |     |     |<--- K0  |
     |     +-----+         |
     |                     |
     |         +-----+     |
     |  K1 --->|     |     |
     +-------->| SHA |--->[+]
     |  K1 --->|     |     |
     |         +-----+     |
     |                     |
     |     +-----+         |
     |     |     |<--- K2  |
    [+]<---| SHA |<--------+
     |     |     |<--- K2  |
     |     +-----+         |
     |                     |
     |         +-----+     |
     |  K3 --->|     |     |
     +-------->| SHA |--->[+]
     |  K3 --->|     |     |
     |         +-----+     |
     |                     |
     |     +-----+         |
     |     |     |<--- K4  |
    [+]<---| SHA |<--------+
     |     |     |<--- K4  |
     |     +-----+         |
     |                     |
     |         +-----+     |
     |  K5 --->|     |     |
     +-------->| SHA |--->[+]
     |  K5 --->|     |     |
     |         +-----+     |
     |                     |
     L6                    R6

Y = R6|L6

So, the input block X is first divided into 2 halves, L0 and R0, 20 bytes each. The right half R0 is hashed together with the first byte K0 of the key (see figure), the result SHA(K0|R0|K0) is XORed with the left half L0, and then the two halves are swapped. This makes up one round. The same operation is repeated in the remaining 5 rounds, except that the swap of the two halves is omitted at the end of the last round, and each round uses the next byte from the key, i.e., K1, K2, … K5. We obtain the output Y by concatenating the two halves at the end.

A Python implementation of this 6-round NataSHA block cipher is provided for your convenience in natasha.py. It is written in Python 3 and it uses the SHA-1 implementation and string XORing from the PyCryptodome package as a dependence.

A 2-block plaintext was encrypted in ECB mode (i.e., the 2 blocks were encrypted independently, one after the other) with an unknown key, and the resulting ciphertext in hex format is:

cd4700ce168ef912fa04eb7ebce33ce960896c8dcc29b101559208b10304328fe1d0852f017ce119
3bf1ce3e4dfc6598895558deec6d9d003df5206f46be754ca806a140a9724da22d371764c36f0e6f

We somehow learned that the second plaintext block in ASCII is (without apostrophes):

'that_may_work_against_weak_ciphers!!!!!}'

What could be the first block?

Hint: It begins with ‘cd20{‘ (without apostrophes).

Submit the full plaintext cd20{…} as the solution to this challenge!

Categories

Cryptography, Offensive

Files

Solution

Meet in the middle attack: I chose to pregenerate a map for first three key bytes, then scan for the last two, and after it’s found bruteforce the fourth by running the whole encryption.

const uint8_t known_ciphertext[] = {
  0x3b, 0xf1, 0xce, 0x3e, 0x4d, 0xfc, 0x65, 0x98, 0x89, 0x55, 0x58, 0xde,
  0xec, 0x6d, 0x9d, 0x00, 0x3d, 0xf5, 0x20, 0x6f, 0x46, 0xbe, 0x75, 0x4c,
  0xa8, 0x06, 0xa1, 0x40, 0xa9, 0x72, 0x4d, 0xa2, 0x2d, 0x37, 0x17, 0x64,
  0xc3, 0x6f, 0x0e, 0x6f
};
const uint8_t known_cleartext[] = "that_may_work_against_weak_ciphers!!!!!}";
const uint8_t unknown_ciphertext[] = {
  0xcd, 0x47, 0x00, 0xce, 0x16, 0x8e, 0xf9, 0x12, 0xfa, 0x04, 0xeb, 0x7e,
  0xbc, 0xe3, 0x3c, 0xe9, 0x60, 0x89, 0x6c, 0x8d, 0xcc, 0x29, 0xb1, 0x01,
  0x55, 0x92, 0x08, 0xb1, 0x03, 0x04, 0x32, 0x8f, 0xe1, 0xd0, 0x85, 0x2f,
  0x01, 0x7c, 0xe1, 0x19
};

void natasha_round(uint8_t* d, const uint8_t* s, const uint8_t* sd, uint8_t k)
{
  uint8_t shabuf[22];
  shabuf[0] = k;
  shabuf[21] = k;
  memcpy(shabuf + 1, s, 20);
  mbedtls_sha1_ret(shabuf, 22, d);
  for (auto i = 0u; i < 20; ++i)
    d[i] ^= sd[i];
}

void natasha_full(
  const uint8_t* l0,
  const uint8_t* r0,
  uint8_t* l6,
  uint8_t* r6,
  uint8_t* k
)
{
  uint8_t l1[20];
  natasha_round(l1, r0, l0, k[0]);
  uint8_t r2[20];
  natasha_round(r2, l1, r0, k[1]);
  uint8_t l3[20];
  natasha_round(l3, r2, l1, k[2]);
  uint8_t r4[20];
  natasha_round(r4, l3, r2, k[3]);
  const auto l5 = l6;
  natasha_round(l5, r4, l3, k[4]);
  natasha_round(r6, l5, r4, k[5]);
}

void find_key(uint8_t* key)
{
  std::map<std::array<uint8_t, 20>, uint32_t> reverse_map;
  const auto l0 = known_cleartext;
  const auto r0 = known_cleartext + 20;
  for (auto i = 0u; i < 256; ++i)
  {
    std::array<uint8_t, 20> l1;
    natasha_round(l1.data(), r0, l0, i);
    for (auto j = 0u; j < 256; ++j)
    {
      std::array<uint8_t, 20> r2;
      natasha_round(r2.data(), l1.data(), r0, j);
      for (auto k = 0u; k < 256; ++k)
      {
        std::array<uint8_t, 20> l3;
        natasha_round(l3.data(), r2.data(), l1.data(), k);
        reverse_map[l3] = (i << 16) | (j << 8) | k;
      }
    }
  }
  const auto r6 = known_ciphertext;
  const auto l6 = known_ciphertext + 20;
  for (auto i = 0u; i < 256; ++i)
  {
    std::array<uint8_t, 20> r4;
    natasha_round(r4.data(), l6, r6, i);
    for (auto j = 0u; j < 256; ++j)
    {
      std::array<uint8_t, 20> l3;
      natasha_round(l3.data(), r4.data(), l6, j);
      const auto res = reverse_map.find(l3);
      if (res != end(reverse_map))
      {
        const auto first_half = res->second;
        key[0] = (uint8_t)(first_half >> 16);
        key[1] = (uint8_t)(first_half >> 8);
        key[2] = (uint8_t)first_half;
        key[4] = j;
        key[5] = i;
        printf("testing last byte\n");
        for (auto k = 0u; k < 256; ++k)
        {
          key[3] = k;
          std::array<uint8_t, 20> my_l6, my_r6;
          natasha_full(l0, r0, my_l6.data(), my_r6.data(), key);
          if (memcmp(my_l6.data(), l6, 20) == 0
            && memcmp(my_r6.data(), r6, 20) == 0)
          {
            printf("found: ");
            for (auto l = 0u; l < 6; ++l)
              printf("%02X ", key[l]);
            printf("\n");
          }
        }
        break;
      }
    }
  }
}

int main()
{
  uint8_t key[6];
  find_key(key);
  std::reverse(std::begin(key), std::end(key));
  unsigned char decrypted[41];
  decrypted[40] = 0;
  natasha_full(
    unknown_ciphertext,
    unknown_ciphertext + 20,
    decrypted + 20,
    decrypted,
    key
  );
  printf("%s\n", decrypted);
}

The key is revealed to be FE 98 3D CD 19 7C with first part ending up as cd20{REDA. The full flag therefore is:

cd20{REDACTED}