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

## 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;
shabuf = k;
shabuf = 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;
natasha_round(l1, r0, l0, k);
uint8_t r2;
natasha_round(r2, l1, r0, k);
uint8_t l3;
natasha_round(l3, r2, l1, k);
uint8_t r4;
natasha_round(r4, l3, r2, k);
const auto l5 = l6;
natasha_round(l5, r4, l3, k);
natasha_round(r6, l5, r4, k);
}

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 = (uint8_t)(first_half >> 16);
key = (uint8_t)(first_half >> 8);
key = (uint8_t)first_half;
key = j;
key = i;
printf("testing last byte\n");
for (auto k = 0u; k < 256; ++k)
{
key = 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;
find_key(key);
std::reverse(std::begin(key), std::end(key));
unsigned char decrypted;
decrypted = 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}
``````