Lors de l'épreuve Q2 du CTF Kanxue 2019, un défi particulier de reverse engineering nécessitait non seulement des compétences en analyse de binaires, mais aussi des connaissances en théorie des nombres pour résoudre une équation de Pell non standard. Cet article détaille le processus d'analyse et la résolution mathématique de l'algorithme de validation.

L'anaylse commence par l'identification de la routine de vérification principale en suivant les chaînes de caractères d'erreur. On tombe sur une fonction MFC qui récupère l'entrée utilisateur.

int __thiscall routine_validation_principale(CWnd *pWindow)
{
    CWnd *fenetre = pWindow;
    WCHAR buffer_entree[20];
    char raw_input[32];
    DWORD protection_initiale;
    int resultat_check = 0;

    memset(buffer_entree, 0, sizeof(buffer_entree));
    memset(raw_input, 0, 0x100);

    // Récupération de la clé (16 caractères attendus)
    CWnd::GetDlgItemTextW(fenetre, 1000, buffer_entree, 20);
    
    if (wcslen(buffer_entree) == 16)
    {
        for (int i = 0; i < 16; ++i)
        {
            if (buffer_entree[i] & 0xFF00) return 0;
            raw_input[i] = (char)buffer_entree[i];
        }

        // Modification dynamique du code en mémoire
        if (VirtualProtect(segment_code_dynamique, 0xD17u, PAGE_EXECUTE_READWRITE, &protection_initiale))
        {
            // Restauration ou décryptage du code de vérification réel
            qmemcpy(segment_code_dynamique, donnees_obfusquees, 0x330u);
            VirtualProtect(segment_code_dynamique, 0xD17u, protection_initiale, &protection_initiale);

            typedef int (*Vérificateur)();
            Vérificateur verifier = (Vérificateur)segment_code_dynamique;
            resultat_check = verifier();

            if (resultat_check == 1)
                return CWnd::MessageBoxW(fenetre, L"Félicitations ! Vous avez trouvé !", 0, 0);
        }
    }
    return CWnd::MessageBoxW(fenetre, L"Clé incorrecte !", 0, 0);
}

La particularité ici est que le binaire modifie son propre code en mémoire via VirtualProtect avant d'exécuter la logique de vérification. En extrayant ce segment de code après sa modification (dump mémoire), on peut analyser l'algorithme réel.

int __cdecl verification_algorithmique(char *input_user)
{
    unsigned char cle_xor[16] = {
        0x16, 0x96, 0x8C, 0xE3, 0x81, 0x98, 0x6E, 0x64,
        0x84, 0x08, 0xDC, 0x81, 0xBE, 0x4D, 0x48, 0x4F
    };
    
    unsigned __int64 val_x = 0;
    unsigned __int64 val_y = 0;
    char res_final[17] = {0};

    // Phase 1 : Extraction de X et Y via XOR
    // L'entrée de 16 octets est divisée en deux blocs de 8 octets
    for (int i = 0; i < 8; ++i)
    {
        ((char*)&val_x)[i] = input_user[i] ^ cle_xor[i];
        ((char*)&val_y)[i] = input_user[i + 8] ^ cle_xor[i + 8];
    }

    // Phase 2 : Vérification des contraintes
    // X doit être sur 8 octets mais avec le dernier octet < 0x10
    if ((val_x >> 60) != 0) return 0;

    // Phase 3 : Calcul de précision arbitraire (BigInt manuel)
    // L'algorithme calcule X^2 et 7 * Y^2
    // Puis il vérifie si X^2 - 7*Y^2 == 8
    
    // [Logique simplifiée pour la lecture]
    // if (BigInt_Square(val_x) - 7 * BigInt_Square(val_y) == 8)
    //     return 1;

    return 0;
}

L'algorithme implémente une arithmétique de grands nombres pour vérifier l'équation suivante : x² - 7y² = 8.

Les contraintes sur les variables sont les suivantes :

• X et Y sont des entiers de 64 bits.
• 0x100000000000000 < x < 0x1000000000000000 (X est codé sur 8 octets, le MSB est limité).
• 0x100000000000000 < y < x.

Il s'agit d'une variante de l'équation de Pell. En utilisant un solveur mathématique ou un script basé sur le développement en fractions continues de √7, on identifie les couples (x, y) valides dans l'intervalle donné.

Le couple de solutions correspondant aux contraintes est :

• x = 385044246406735194
• y = 145533045678356702

Enfin, nous appliquons l'opération XOR inverse pour retrouver la chaîne de caractères d'origine (le Flag).

def solve_challenge():
    target_x = 385044246406735194
    target_y = 145533045678356702
    
    xor_mask_1 = 0x646e9881e38c9616
    xor_mask_2 = 0x4f484dbe81dc0884
    
    # Calcul des parties de la clé originale
    part1 = target_x ^ xor_mask_1
    part2 = target_y ^ xor_mask_2
    
    # Conversion en hex et formatage
    hex_str1 = hex(part1)[2:].zfill(16)
    hex_str2 = hex(part2)[2:].zfill(16)
    
    def decode_hex(h):
        return "".join([chr(int(h[i:i+2], 16)) for i in range(len(h)-2, -2, -2)])

    flag = decode_hex(hex_str1) + decode_hex(hex_str2)
    print(f"Flag trouvé : {flag}")

# Résultat : L3mZ2k9aZ0a36DMM