A Computação e a Boneca Russa

Por: Deadlock Team.

Uma função recursiva é, grosseiramente, uma função que chama a si mesma, normalmente a fim de diminuir o problema inicial, e continuamente dividindo-o em subproblemas até chegar em um retorno dado uma condição de parada. Mas afinal, o que isso tem a ver com uma boneca chamada Matryoshka, conhecida por ter sua origem na Rússia?

Ela é um simples brinquedo infantil, que teve seu inicio de fabricação em 1890. Anos depois, seria citada frequentemente na computação. Quem diria, não é mesmo? O que temos que entender é como esse objeto funciona, e o funcionamento tão simples e tão rústico, é o que dá tanto brilho e traz um significado poderoso diretamente relacionado aos incríveis métodos recursivos.

    //Código em C da Torre de Hanoi
    void TorreHanoi(int origem, int destino, int auxiliar, int quantidade){
      if( quantidade == 1 ){
        printf("Move de %d para %d\n", origem, destino);
        count++;
      }else{
        TorreHanoi(origem, auxiliar, destino, quantidade-1);
        TorreHanoi(origem, destino, auxiliar, 1);
        TorreHanoi(auxiliar, destino, origem, quantidade-1);
      }
    }

Uma boneca Matryoshka consiste em uma boneca que, assim que você abre o brinquedo oco, outra boneca menor aparece e assim “recursivamente” até a última boneca ser encontrada. Eu diria que qualquer criança não passaria mais de 5 minutos com esse negócio, mas diria que um programador passaria a vida toda brincando com ela, e mesmo que seu código seja uma torre de Hanoi com no mínimo 511 movimentos, no fundo – bem lá no fundo mesmo – você ainda está abrindo a sua bonequinha. A ideia que parece arcaica, ainda sustenta o famoso nome de um container de áudio e vídeo, o Matroska Media Container, conhecido também pelo formato mkv.

O CTF e a Boneca

Não deixando de citar os eventos de Capture The Flag, onde Matroshka é quase uma vírgula no meio de tanto desafio que existe relacionado a boneca, os torneios colocam os competidores para desvendar “o que está dentro do que”, e se isso ficou confuso, é porque realmente você pode enfiar qualquer coisa dentro de algo e colocar o nome da boneca, para um conhecedor de challenges, fica claro o que está ocorrendo, porém ainda com suas milhares de variações, podendo conter arquivos quase que infinitamente compactados, camadas diferentes de um QRCode, criptografias escondendo a flag… Enfim, dá pra ir longe abrindo e descobrindo.

O famoso exemplo dos arquivos compactados ilustra bem, você até pode abrir todos os arquivos manualmente – e seria lindo você perder dez horas brincando de boneca enquanto todos os times vencem o seu na competição -, porém obviamente você automatiza o seu problema, com um script que abre automaticamente a boneca em busca de um último arquivo com a flag – ou com muitos outros arquivos com diferentes desafios -.

    # Código para descompactar um arquivo compactado com senha
    # Com outros arquivos compactados com senha dentro dele
    #!/usr/bin/env bash
    
    while [ -e *.zip ]; do
      files=*.zip;
      for file in $files; do
        echo -n "Cracking ${file}… ";
        output="$(fcrackzip -u -l 1-6 -c '1' *.zip | tr -d '\n')";
        password="${output/SENHA ENCONTRADA\!\!\!\!: pw == /}";
        if [ -z "${password}" ]; then
          echo "Erro";
          break 2;
        fi;
        echo "Senha: \`${password}\`";
        unzip -q -P "${password}" "$file";
        rm "${file}";
      done;
    done;

A Boneca e as outras áreas

Como se não bastasse esconder informações na área forense utilizando milhares de barreiras antes de chegar no resultado final, que tal adicionar o conceito em diversas outras áreas? É lógico que isso já ocorre, em desafios de engenharia reversa em que o binário tem que realmente ser cavado para explorá-lo completamente, e reorganizando cada detalhe de challenge que eu estou citando que forma o problema ideal em que trava o desafiante por horas. E quer algo melhor para enfrentar um trabalho em equipe que um desafio Matryoshka? Diversas áreas sendo abordadas, diversas possibilidades e uma longevidade do problema que bate em qualquer time quando bem construído.

Tudo isso enaltece e demonstra o poderoso e simples conceito que é muito bem aproveitado e usado na computação, assim uma função que chama a si mesma, normalmente a fim de diminuir o problema inicial, e continuamente dividindo em subproblemas até chegar em um retorno dado uma condição de parada, finalmente nos traz à mente a imagem entalhada em madeira, da boneca Matryoshka.