Hail Zeus (300 pts)

Question:

Asking Hermes to gath'r intel on the foe, he recover'd the blueprint of their transmitt'r bef're getting captur'd.

It’s been ov'r a month of radio silence. but wait... all hail Zeus, as they restart'd communication when he strok'd them with a lightning:

11111010101010010101011010100011110101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010010110101111111100000111100101010111001010010111011100101111100001101000111111000101100110110011001111001001011101011011110110110101010000101101100001101010111101000010101000001100010111110000011111100100001000111111011010010010010100101011100011000000111001101010000001111111111010000111110001011001010110100001001100010111010101010000001111000011010101010101000011110000110101000111101000011010010010101111100101011111001111010001001101010000000010011000010110000011111000011001100011011001101011001111001001000110111100000101111000100100010100101000111101011011110010010011011110010001000001011101010001000000001100011001110011011100101100010001001001100100011111000011110000001100111011010000010100001100011000101010110010000010001000011100100101100001111100100001010101111010010111010010111100110110110111110100100101100011010000001000000000010000111010001010110111100100100110000100110011011110000010110001111000001111100100111000111011000101010001001111010011110010111000111100100000110000000110101110110001010000011010100001110100100111001110110101111011011111110000100010000101100011101000111100001000001001001100011001000000000100010111000100101101111100100111010000110101010111000010011000100101000101101010110101010010110001100110010110100010010100011011000010010101011100100101000001011001101101000011001010011110100110100000110111000010100010110010011110010010010100010111001111011000010100100111110001011010111011101010001010001101001110100100101001011010010001110110100011100011100000011011001100100100010011000110110000010100100011000111010001011110101001001101010000001110101000011100010110001000111101010000101011000001011101001101000001101000001100010001100100110100100101001010011100000111000011111110000110101101110001011010100001101000011000000110100101101000001011000110111001101001001100010011110010011100000110110100110100011111110101111000001001000011010010001111001011001100101000101111000001101010001100010001100000011000100100101101111110100111011101101101001011000101010010011100010010110010100110011111100000000100001010000000111001010010001111010000001100000001000101001111011101010001111100111101100010110100111100000111011001110100010000010001010110100001100111001001101001001010001011101000011010000011100000001010110101100001011010000110010010101000001111010101111101000101011111011000011100001110000011110000011110110111100000011100000100100000111011001110010010010001010011000011010000010001001001000001001011010011010011101000010111010010111010001100001011000011010010010110101011000000010010100010111001011101101111010101111000010101000011111000001000110111110101101101011001010011111000101101001011001000110100101011001001111101110010000010101000011000000110101000111001000101010001111110011110100010010100010011000010110000111010101101000101011101000001000010100000001101010110111000100100000100100000011011010111001010110011001110100111110100001001101100011001011010111001110110110010110101000100100110100101111110001010110010000011110010111010011000110110100001101000000110010011110100110110010011000100111110100001001001110010011111000100001000011100010111100001110101000111010001011101001001000000000000001101100110010000100101000001100000111010000011000010010000010010100110000000001000000000000001101110000000000011100000000001100101000000011111011000000001010001000000000110010000000000010011000000010001000000000011010010000000001011010000000010000...

Write-Up:

In telecommunication, Hamming codes are used for error detection and correction. To enhance the code's ability in the face of burst errors, techniques such as interleaving are common.

This challenge, written in Shakespearean language and involving various Greek gods, sets the stage for a day-to-day scenario: A message, sent over a noisy channel, is corrupted by a severe burst error (e.g., Zeus' lightning!). We also have only part of the message. How to recover the originally transmitted message (at least, partially)?

The goal is to guess the number of columns and rows of the helical scan interleaver. We simply try all possible values (smaller than 30, as pointed out in the blueprint). After deinterleaving, the number of errors detected by the Hamming decoder is computed. We pick the columns and rows with minimal number of errors, decode the message, and retrieve the flag.

The following MATLAB code implements this idea:

% r: Hamming code parameter. We have (2^r-1, 2^r-r-1)-Hamming code
% Z: transmitted message as a string
function Receiver(r, Z)

Z = double(Z=='1');
lenZ = length(Z);
n = 2^r-1;
k = n - r;

R = -1;
C = -1;
minE = Inf;
Z4 = [];

for rows = 2:30
    for cols = 1:30

        rc = rows*cols;
        lenZ_ = ceil(lenZ / rc) * rc;
        Z_ = Z;
        Z_(lenZ_) = 0;        
        z3 = zeros(1, lenZ_);

        for i = 1:rc:lenZ_
            z3(i:i+rc-1) = helscandeintrlv(Z_(i:i+rc-1), rows, cols, 1);
        end

        len = floor(lenZ_/n)*n;
        [z4, err] = decode(z3(1:len), n, k, 'hamming/binary');
        err = sum(err);

        if err < minE
            minE = err;
            R = rows;
            C = cols;
            Z4 = z4;
        end

    end
end

len = floor(length(Z4)/8)*8;
v = Z4(1:len);

m = char(bin2dec(num2str(reshape(v,8,[])'))');

display(strcat('"', m, '"'));

You should call it as:

Receiver(r, Z)

where r = 5 is the -Hamming parameter, and Z is the transmitted binary message.

The result is as follows (some parts are unreadable thanks to Zeus' lightning!):

-------------------------------------------------
"   h@t h    `   h    d         ( råly weighs you down and torments you with regret. Drawing rooms, gossip, balls, SharifCTF{4412e6635c6eafaad08574d77ab4d301}, vanity, and triviality --- these are the enchanted circle I cannot escape from. I am now going to the war, the greatest war there ever was, and I know nothing and am fit for nothing. I am very amibPn`  a` ` aup4ic wit."
-------------------------------------------------

and the flag can be recovered from SharifCTF{4412e6635c6eafaad08574d77ab4d301}.

By the way, the above quote is from Tolstoy's War and Peace.

Source Code

Receiver.m.