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
- natasha.py (didn’t use this)
Links
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{M33T-in-the-M1dDLe_i5_a_t3cHN1que_/. The full flag therefore is:
cd20{M33T-in-the-M1dDLe_i5_a_t3cHN1que_/that_may_work_against_weak_ciphers!!!!!}