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.
