Mais um blog inútil.

May 4, 2009

Malbolge desmistificado

Filed under: Arvorezinha,Coding,lulz,Useless — mirage @ 22:42

Bem-vindos. Espicaçado pelas inutilidades que o falso e o Dcoder fizeram em malbolge, e ainda mais depois de o falso ter afirmado peremptoriamente que era impossível fazer uma arvorezinha à mão nesta linguagem diabólica, decidi, fatalmente, jogar mãos à obra.

O segredo do falso em relação ao malbolge é que todo o código dele é gerado por bruteforce. As optimizações do Dcoder limitaram-se a correr o bruteforce durante mais tempo para procurar soluções mais curtas. Neste post proponho um método real, analítico e bastante simples para criar um programa de malbolge que imprima qualquer sequência de caracteres, com a limitação de ser curta. E sim, a arvorezinha é suficientemente curta. ;-) Para facilitar a programação, criei vários utilitários, baseados no malbolge.c original, que constituem o malbolge SDK disponível aqui. Eis uma curta explicação de cada programa:

  • malbolgec: Compila uma source não obfuscada de malbolge (extensão .mbs), transformando-a na versão obfuscada executável (extensão .mb). São admitidos comentários na source, começando com ";".
  • malbolged: Uma variação do malbolge.c standard que imprime o estado da VM à medida que executa o código. Muito útil para debugging.
  • malbolgedis: O inverso do malbolgec. Dado um programa executável de malbolge, mostra o seu código desobfuscado.
  • malbolgeconstant: Descobre a sequência mais curta para calcular o valor desejado. Mais abaixo será mostrado como o utilizar, já que é uma peça fulcral no método apresentado.
  • malbolgevalid: Mostra os valores válidos num programa de malbolge no intervalo de memória especificado. Útil para procurar valores directos para usar em jumps.
  • malbolgestring: Um proof-of-concept que gera um programa de malbolge que imprima a string especificada. Apenas aceita strings muito curtas (uma arvorezinha completa não cabe, por exemplo, mas "lol jews" sim).
  • Um dos problemas da programação em malbolge é que que o code pointer e o data pointer começam ambos a 0 no início do programa, ou seja, estão sobrepostos. Por isso, o meu plano começa por separar claramente a zona de código da zona de dados. Assim sendo, a primeira coisa que faço é avançar o D para qualquer sítio mais à frente, com a instrução "j". Devido à obfuscação que a o malbolge obriga no input, esta instrução na posição 0 de memória corresponde a um salto do D para o valor 41. Temos agora 40 bytes de código disponíveis pela frente, sem mais complicações, antes de voltar a tropeçar nos dados.

    Outro dos problemas é a alteração sofrida nas instruções depois de serem executadas, e também dos dados depois de serem usados pelos operadores. Para minimizar estes problemas optei por uma abordagem naïve mas suficientemente eficaz para o problema em questão, que consiste em ter todo o código e dados a correr linearmente, excepto a configuração inicial da área de dados descrita anteriormente.

    Talvez a limitação mais severa seja a dos caracteres que podemos usar como input inicial no malbolge, o que dificulta tremendamente o uso de valores pré-definidos, como sejam os caracteres da nossa string. Isto obriga-nos a calcular praticamente todos os valores desejados e imprimi-los, um por um. O malbolge apenas oferece duas instruções de cálculo, o trinary rotate e a trinary op a.k.a. crazy operation. Felizmente para nós, qualquer valor ASCII é calculável usando estas operações com um máximo 3 operações seguidas com valores específicos nos dados (por vezes antecedidas de nops, é certo, para aceder aos dados necessários que, como é sabido, variam consoante a sua posição em memória). Para ajudar, não precisamos de ter o valor exacto no A, basta um A tal que A & 0xFF seja o caracter que queremos (os registos são unsigned short e o print só usa os primeiros 8 bits). Para descobrir a menor sequência de operações necessárias e respectivos valores nos dados fiz o malbolgeconstant (tal como referi acima, pertence ao SDK).

    Para exemplificar, vamos criar um programa que imprima "Oi". Usaremos os símbolos reais para as instruções e não a versão executável, que depois compilaremos com o malbolgec. Primeiro avançamos o D para a posição 41:

    jv

    Agora calculamos o caracter "O" (ASCII 79) com o malbolgeconstant (tem como input o valor do D, o valor que procuramos e o valor actual do A, que no início do programa é zero):

    ./malbolgeconstant 41 79 0
    EUREKA! code=p pos=42 data=p (r)
    EUREKA! code=* pos=41 data=p (s)

    OK, esta efusão de felicidade conta-nos que devemos usar as operações "*" e "p", com o input "p" e "p" respectivamente (que correspondem a "r" e "s" em código obfuscado, mas vamos aqui trabalhar com código normal). De notar que o pos (a posição de memória onde devem estar os dados) começa a 41, que foi a posição inicial que especificámos. Poderia ser 42 ou mais, o que significaria que precisávamos de inserir nops no código (e nos dados, mas aqui não é obrigatório serem nops) antes de executar as instruções especificadas. Por vezes os valores necessários às operações só estão disponíveis mais à frente na memória, devido à forma como o malbolge obriga a codificar as sores. Adiante, o nosso programa tem agora este aspecto:

    j*p<voooooooooooooooooooooooooooooooooooopp

    Recapitulando: avançamos o D, calculamos "O" (o seu valor fica no registo A) e imprimimo-lo com "< ", terminando o programa com o "v". A sequência de "o" (nops) no meio é apenas para encher choriços, já que não chegam a ser executados. Estão cá apenas para chegar à posição 41 e 42, onde temos o input necessário às nossas instruções. Vamos compilar este programa e corre-lo no malbolged para ver a evolução dos registos:

    ./malbolgec example.mbs example.mb && ./malbolged example.mb
    CODE: j MEM: 040 (() A: 00000 C: 00000 D: 00000
    CODE: * MEM: 115 (s) A: 00000 C: 00001 D: 00041
    CODE: p MEM: 114 (r) A: 19721 C: 00002 D: 00042
    CODE: < MEM: 29416 (è) A: 09807 C: 00003 D: 00043
    O CODE: v MEM: 114 (r) A: 09807 C: 00004 D: 00044

    Como podem ver, quando o programa termina, o registo A tem o valor 9807 e o D tem 44. Vamos usar estes valores como base para calcular a próxima constante de que necessitamos, que é a letra "i" (ASCII 105):

    ./malbolgeconstant 44 105 9807
    EUREKA! code=p pos=45 data=j (Y)
    EUREKA! code=* pos=44 data=/ (I)

    Mais uma vez só precisamos de duas operações. Temos assim o seguinte:

    j*p<*p<voooooooooooooooooooooooooooooooooppo/j

    Notem o "o" entre os dois grupos de dados: é para compensar o avanço do D gerado pela instrução que imprime o caracter. Poderia ser qualquer outro símbolo, já que não está a ser usado.

    Vamos terminar com um \n, para ficar com um output decente:

    ./malbolgec example.mbs example.mb && ./malbolged example.mb
    CODE: j MEM: 040 (() A: 00000 C: 00000 D: 00000
    CODE: * MEM: 115 (s) A: 00000 C: 00001 D: 00041
    CODE: p MEM: 114 (r) A: 19721 C: 00002 D: 00042
    CODE: < MEM: 119 (w) A: 09807 C: 00003 D: 00043
    O CODE: * MEM: 073 (I) A: 09807 C: 00004 D: 00044
    CODE: p MEM: 089 (Y) A: 19707 C: 00005 D: 00045
    CODE: < MEM: 29477 (%) A: 09833 C: 00006 D: 00046
    i CODE: v MEM: 088 (X) A: 09833 C: 00007 D: 00047

    ./malbolgeconstant 47 10 9833
    EUREKA! code=p pos=49 data=* (T)
    EUREKA! code=p pos=48 data=v (!)
    EUREKA! code=* pos=47 data=i (3)

    Chegamos por fim ao programa desejado:

    mirage@arda ~/malbolge-sdk-1.0 $ cat example.mbs
    j*p<*p<*pp<voooooooooooooooooooooooooooooppo/joiv*
    mirage@arda ~/malbolge-sdk-1.0 $ ./malbolgec example.mbs example.mb
    mirage@arda ~/malbolge-sdk-1.0 $ cat example.mb
    (&<`#9]~65YF876543210/.-,+*)('&%$#"!~}|{zsrwIYt3!T
    mirage@arda ~/malbolge-sdk-1.0 $ ./malbolge example.mb
    Oi

    Vamos agora à prova dos nove: a arvorezinha! Note-se que esta arvorezinha tem \n na última linha, como manda o RFC. Tal como as arvorezinhas anteriores em malbolge, não usa ciclos. Ocupa 99 caracteres (incluí no SDK uma versão sem a última newline com apenas 95 caracteres). Como verão, usei dois incrementos ao D, porque a arvorezinha não coube em 40 caracteres de código. Ainda assim, foi necessário usar o próprio valor em 44, que é um < , para imprimir um caracter da árvore, e simultaneamente servir de input para o segundo "j". Reparem:

    ./malbolgevalid 44 44
    44: 037 (v) 054 (i) 055 (<) 073 (/) 089 (*) 090 (j) 112 (p) 118 (o)

    O "< ", por coincidência a instrução de print, resulta no valor 55, bastante simpático para o novo início dos dados. Atenção que, na listagem que se segue, o nº de linha N corresponde à posição de memória N-1. Sem mais paleio, aqui vai:

    j ; avançar dados para o 41
    o ; estes nops são para diminuir o resultado do próximo j
    o
    o
    j ; avançar ainda mais, para o 56
    p ; calcular "*" com "pp" com os dados 56 e 57
    p
    < ; imprime-o
    * ; agora calcula o "\n" com dados do 59 ao 61
    p
    p
    < ; imprime-o
    * ; calcula novamente "*"
    p
    p
    < ; desta vez imprime dois
    <
    p ; calcula "\n" de novo e assim sucessivamente até completar a arvorezinha
    p
    <
    p
    p
    <
    <
    <
    p
    p
    <
    *
    p
    p
    <
    <
    <
    <
    p
    p
    <
    p
    p
    < ; print dos últimos 5 asteriscos
    < ; posição de dados usado no D=56, e simultaneamente faz um print ;-)
    <
    <
    <
    *
    p
    p
    < ; printa "\n" no fim, como manda o RFC, seus batoteiros
    v ; fim do código
    o ; nops a encher choriço até começarem os dados úteis
    o
    o
    o
    o
    o
    j ; dados do cálculo do primeiro "*"
    *
    o ; nop para compensar o "<" desse "*"
    i ; dados do cálculo do primeiro "\n"
    p
    i
    o ; nop idem
    i ; etc, dados dos cálculos até ao final
    <
    *
    o
    o
    o
    p
    o
    *
    <
    o
    o
    o
    o
    i
    o
    /
    p
    j
    o
    o
    o
    o
    *
    o
    o
    p
    j
    o
    o
    o
    o
    o
    p
    /
    j
    

    Rapidamente, a versão prêt-à-porter:

    (CBA$98\}54Xy10TS-,P*)MLK%$Hi!~DCBAyx>vu;:987Xnm3~ponmlkNLh'`%d##D`_^W\>yYXWVsT&L5PONM/KJC,GFEDC<r$

    E assim chegamos ao fim do post. Espero que tenham perdido tanto tempo a lê-lo como eu perdi a escrevê-lo. ;-) Feliz programação em malbolge!

    Este post é dedicado à memória do fravia, o Deus do cracking, e do Vasco Granja, o Rei do lulz importado da antiga checoslováquia.

    11 comentários a “Malbolge desmistificado”

    1. falso says:

      amei o artigo sir! acho que é o melhor do blol ate hoje!
      o palavreado rico, epa, mesmo do belo!!!!

      vou agora experimentar fazer eu qualquer coisa em malbolge com o sdk !

    2. madinfo says:

      Lindo mesmo, fiquei sem palavras...

    3. dcoder says:

      Acabaste de derrotar o último boss da Internet.

      É impossível superar isto.

      (Provavelmente vou arrepender-me de ter dito isto, *novamente*...)

    4. Mário Gamito says:

      tanta inutilidade que até dói

    5. falso says:

      o que eu e o dcoder usamos foi isto: http://www.cs.uit.no/~johnm/code/hacks/

    6. fuck says:

      vcs mereciam morrer
      em vez de se dedicarem a salvar criancinhas no darfur andam a fazer estas inutilidades
      tsss tsss

      :P

    7. falso says:
          ja acabei o malbolge sdk posso sair da cave?
                        /
                ,==.              |~~~
               /  66\             |
               \c  -_)         |~~~
                `) (           |
                /   \       |~~~
               /   \ \      |
              ((   /\ \_ |~~~
               \\  \ `--`|
               / / /  |~~~
      
               ^^ mirage
      
    8. Drune says:

      Parabens mirage, esta foi mesmo inutil! gostei bastante :D

    9. +&#JOnhy,.. says:

      Porra não entendi nada mas esclareceu como essa porra de ponteirose celulas de memoria não funcionam funciona

    10. [...] for those brave enough to try to program in this thing there is a SDK available – http://blol.org/735-malbolge-desmistificado But the documentation is in [...]

    11. [...] Malbolge SDK - A collection of programs to make your life easier when coding in Malbolge (In Portugu... [...]

    Comentar

    widgeon
    widgeon
    widgeon
    widgeon