BFD56

5 minutes to read

We are given the Python source code to encrypt the flag:

from secret import pt,key,block_length
import random

alph = "ABCDEFGHIKLMNOPQRSTUVWXYZ"

def strmask(msg,mask):
    mask = (mask * ((len(msg)//len(mask)) + 1))
    return "".join([alph[(alph.index(i) + alph.index(j)) % 25] for i,j in zip(msg, mask)])

def strunmask(msg,mask):
    mask = (mask * ((len(msg)//len(mask)) + 1))
    return "".join([alph[(alph.index(i) - alph.index(j)) % 25] for i,j in zip(msg, mask)])

def encrypt_block(pt, indices, characters):
    res = [-1] * len(pt) * 2
    for i,c in enumerate(pt):
        res[i],res[i+len(pt)] = indices[c][0],indices[c][1]
    ret = ""
    for i in range(0,len(res),2):
        ret += characters[str(res[i]) + str(res[i+1])]
    return ret

def encrypt(plaintext, key, block_length):
    iv = "".join([random.sample(list(alph), 1)[0] for i in range(block_length)])
    
    indices = {}
    characters = {}
    for i,c in enumerate(key):
        indices[c] = str(i//5) +  str(i%5)
        characters[str(i//5) +  str(i%5)] = c

    plaintext_blocks = [plaintext[i : i + block_length] for i in range(0, len(plaintext), block_length)]  

    ciphertext = ""
    cmask = iv
    for block in plaintext_blocks:
        block_enc = encrypt_block(strmask(block,cmask),indices,characters)
        ciphertext += block_enc
        cmask = block_enc

    return iv,ciphertext

with open('ciphertext.txt', 'w') as f:
    f.write(str(encrypt(pt,key,block_length)))

We also have the ciphertext.txt file:

('GOAQXASQ', 'UMAYACISLGYWQWEFDSWAZPEXCVZMGLDVPDHNKWBOHQBFLLIQXVGGIGSCTCYDBTOQZGUWIVMNYHFZNONRBZPGYEWSBRHHEXENIWPTVELRGREXCXGXYZAYGBXGCTDMCOLXPOWRHUFLOLWUDMAGBYEMBOLIMNRICBPIUSQIHSNAWEPGKKKFHGQUWAWVYCXAHKLOFBZNSOKUBXTNMIQGODSHPOAAUMXCEHSGSFMPPTDDKLUINZFFHIPBIAGBLXVUOKRSIVUUBDUGMGZTXTXVHNTIBMUGURFGXBVNQFETEHXAWXMORWDCHBCLYETCYXMKEPYT')

Cipher analysis

First of all, we notice that although block_length (also known as period) comes from a secret module, we already know it is 8 because the IV has 8 characters:

    iv = "".join([random.sample(list(alph), 1)[0] for i in range(block_length)])

Moreover, after skimming through the code, we can be sure that the key must contain all uppercase letters (25, the J does not appear) to create mappings called indices and characters.

In fact, we are dealing with Bifid cipher (see the examples to understand the cipher). There are some projects on Bifid cryptanalysis, but probably those won’t be enough to solve the challenge. Also, the challenge description talkes about Delastelle, who designed the Bifid cipher.

Encryption

Actually, the cipher implementation is not a pure Bifid cipher, because it has some CBC inspiration. In fact, we can draw the encryption process as follows:

BFD56 1

The function strmask alters the plaintext block that will enter the Bifid cipher, and the resulting ciphertext block feeds the next strmask block.

Decryption

Although there is no decryption implementation, we can simply reverse the encryption algorithm and use strunmask instead of strmask:

BFD56 2

The attack

As said before, there is a project that tries to break the Bifid cipher. It is written in C (in order to be as fast as possible).

The Bifid cipher looks messy at first glance, but the way it works is actually simple. However, the cryptanalysis techniques for this cipher are based on frequency analysis and probabilistic approaches (for more information, you can take a look at this paper).

To solve this challenge, we must implement the “CBC Bifid cipher” in C and then use the rest of the project to apply the cryptanalysis technique. For those who already know how to program in C (presumably reversers and pwners), this is fairly easy.

These are the relevant functions:

void strunmask(char* message, char* mask) {
        int i;
        int a, b;

        for (i = 0; i < PERIOD; i++) {
                a = (int) (index(ALPHABET, message[i]) - ALPHABET);  
                b = (int) (index(ALPHABET, mask[i]) - ALPHABET);

                message[i] = ALPHABET[(25 + a - b) % 25];
        }
}

void decrypt_block(char* key, char* ct_block, char* pt_block) {
        int i;
        int a_ind, b_ind;
        int a_row, b_row;
        int a_col, b_col;
        char a, b;

        for (i = 0; i < PERIOD; i++) {
                a = ct_block[i / 2];
                b = ct_block[(PERIOD + i) / 2];

                a_ind = (int) (index(key, a) - key);
                b_ind = (int) (index(key, b) - key);

                a_row = a_ind / 5;
                b_row = b_ind / 5;
                a_col = a_ind % 5;
                b_col = b_ind % 5;

                if (i % 2 == 0) {
                        pt_block[i] = key[5 * a_row + b_row];
                } else {
                        pt_block[i] = key[5 * a_col + b_col];
                }
        }
}

void bifid_decrypt(char* key, char* iv, char* ct, char* pt) {
        while (*ct) {
                decrypt_block(key, ct, pt);
                strunmask(pt, iv);

                iv = ct;
                ct += PERIOD;
                pt += PERIOD;
        }
}

Sorry if it looks a bit weird… I used some pointer magic to be more efficient, although the code has lost readability…

Anyway, this is the main function:

int main(int argc, char** argv) {
        char* iv;
        char* ciphertext;

        if (argc != 3) {
                printf("[-] Usage: %s <iv> <ciphertext>\n", argv[0]);  
                return 1;
        }

        iv = argv[1];
        ciphertext = argv[2];

        int length = strlen(ciphertext);
        char* plaintext = malloc(length + 1);
        char key[] = "ABCDEFGHIKLMNOPQRSTUVWXYZ";

        bifid_crack(key, iv, ciphertext, length);
        bifid_decrypt(key, iv, ciphertext, plaintext);

        printf("[*] Key: %s\n[+] Plaintext: %s\n", key, plaintext);

        free(plaintext);

        return 0;
}

In order to compile it, we must have qgr.h:

$ gcc solve.c -O3 -o bifid -lm

$ ./bifid
[-] Usage: ./bifid <iv> <ciphertext>

Flag

If we run the binary, we will get the plaintext message in a few seconds:

$ ./bifid GOAQXASQ UMAYACISLGYWQWEFDSWAZPEXCVZMGLDVPDHNKWBOHQBFLLIQXVGGIGSCTCYDBTOQZGUWIVMNYHFZNONRBZPGYEWSBRHHEXENIWPTVELRGREXCXGXYZAYGBXGCTDMCOLXPOWRHUFLOLWUDMAGBYEMBOLIMNRICBPIUSQIHSNAWEPGKKKFHGQUWAWVYCXAHKLOFBZNSOKUBXTNMIQGODSHPOAAUMXCEHSGSFMPPTDDKLUINZFFHIPBIAGBLXVUOKRSIVUUBDUGMGZTXTXVHNTIBMUGURFGXBVNQFETEHXAWXMORWDCHBCLYETCYXMKEPYT  
[*] Key: CUQHEYKWZSFMOBILTAXGDVRPN
[+] Plaintext: BIFIDISPRETTYCOOLBUTINTWENTYTWENTYWEKNOWTHATELECTRONICCODEBOOKMODEISPRETTYWEAKGOODTHINGWEHAVECIPHERBLOCKCHAININGTOSAVETHEDAYIBETBECAUSEIUSEDSUCHANAWESOMEANDMODERNTECHNIQUENOBODYWILLEVERBEABLETOCRACKTHISBUTIFTHEYDOISUPPOSETHEYDESERVEANHTBFLAGWHICHISTHESEWORDSSEPARATEDBYUNDERSCORESANYTHINGISABLOCKCIPHERIFYOUTRYHARDENOUGH

After parsing the text, we have this:

BIFID IS PRETTY COOL BUT IN TWENTY TWENTY WE KNOW THAT ELECTRONIC CODEBOOK
MODE IS PRETTY WEAK GOOD THING WE HAVE CIPHER BLOCK CHAINING TO SAVE THE DAY  
I BET BECAUSE I USED SUCH AN AWESOME AND MODERN TECHNIQUE NOBODY WILL EVER
BE ABLE TO CRACK THIS BUT IF THEY DO I SUPPOSE THEY DESERVE AN HTB FLAG
WHICH IS THESE WORDS SEPARATED BY UNDERSCORES ANYTHING IS A BLOCK CIPHER IF
YOU TRY HARD ENOUGH

And the flag is:

HTB{ANYTHING_IS_A_BLOCK_CIPHER_IF_YOU_TRY_HARD_ENOUGH}

The full script can be found in here: solve.c.