Show HN: Hackea a tu rival con un juego de mesa de ensamblador RISC-V

 (punkx.org)
3 puntos por GN⁺ 2023-10-01 | 1 comentarios | Compartir por WhatsApp
  • PROJEKT: OVERFLOW es un juego educativo que convierte el ensamblador RISC-V y el desbordamiento de búfer en reglas de juego de mesa, para seguir directamente la manipulación de memoria, stack y direcciones de retorno
  • Los jugadores comparten la misma memoria y el mismo programa, y compiten con un esquema de scheduling preventivo que ejecuta solo 10 instrucciones por turno, sin memoria virtual
  • La partida se decide al copiar instrucciones existentes para crear shellcode y sobrescribir la return address del rival para enviarlo a game_over()
  • Los accesos inválidos a memoria, las lecturas/escrituras no alineadas y las instrucciones ilegales provocan crashes y la ejecución de un manejador de excepciones; cambiar la dirección de trap y hacer monkeypatch con nop son variables estratégicas clave
  • Ofrece juego web, tablero imprimible y helpers de juego para ESP32 y móviles, pero algunas reglas aún se están ajustando, así que se parece más a un rompecabezas experimental de hacking

Objetivo del juego y modelo de ejecución

  • PROJEKT: OVERFLOW es un proyecto que lleva el ensamblador RISC-V y el desbordamiento de búfer a un juego de mesa
  • El objetivo central es copiar instrucciones existentes para crear un pequeño shellcode en memoria, saltar a ese código mediante un desbordamiento de búfer y luego sobrescribir la return address del rival para que llame a la función game_over()
  • La estrategia va más allá de la simple ejecución de código e incluye configurar manejadores de excepciones y hacer monkeypatch
  • Todos los jugadores comparten la misma memoria y el mismo programa, y usan el mismo procesador mediante división de tiempo
    • En un turno se ejecutan 10 instrucciones
    • El stack pointer de cada jugador empieza en una ubicación distinta
    • No hay memoria virtual

Flujo de build y generación del tablero

  • El código se compila para RV32 con riscv64-unknown-elf-gcc
    • Entre las opciones principales están -march=rv32g, -mabi=ilp32, -ffreestanding, -nostdlib, -nostartfiles, -O0, entre otras
    • Gracias a -O0, el código máquina queda verboso, pero fácil de seguir
  • Los materiales para el tablero se generan parseando la salida de riscv64-unknown-elf-objdump -S -l -fd game
    • Se modifican las instrucciones ▲ y ✎
    • Los offsets de salto se convierten de hexadecimal a decimal
    • Se limpia el ensamblador y se lo empareja con el código fuente
    • Se crea un SVG y luego se convierte a PDF con Inkscape

Impresión y materiales

Reglas básicas y desarrollo de los turnos

  • El estado inicial es el siguiente
    • Todos los registros empiezan en 0, pero el registro de return address ra empieza en 1000
    • El sp del Player 1 se inicializa en 2244 y el sp del Player 2 en 3844
    • El pc de ambos jugadores empieza en 1000, la dirección inicial de la función main
    • La ficha de trap se coloca en la dirección 1000
    • Todas las direcciones de memoria, excepto el programa precargado, están en 0
    • La ficha de instrucción nop no se coloca en el tablero al inicio
  • En un turno se deben ejecutar 10 instrucciones, y los saltos como jal y beq también deben seguirse tal cual
  • Un jugador puede detener su turno después de ejecutar al menos 1 instrucción y transferir la cantidad de instrucciones restantes a su siguiente turno
    • El máximo de instrucciones acumulables es 20

Monkeypatch y condiciones de victoria

  • Al inicio de cada turno, después de ejecutar exactamente 1 instrucción, se puede mover la ficha de instrucción nop a cualquier dirección de una función que los jugadores actuales no estén ejecutando
  • Cuando el pc llega a esa dirección, la instrucción se comporta como no-operation
  • Si se mueve la ficha nop, se pierden el turno actual y el siguiente, y el rival puede ejecutar hasta 20 instrucciones en su siguiente turno
  • La regla de monkeypatch todavía no está balanceada, así que cambia ligeramente cada pocos días
  • En modo difícil, el juego termina si hackeas al rival para que llame a la función game_over()
  • Si ninguno de los dos puede enviar al otro a game_over(), hay empate
  • En modo fácil, gana el primer jugador que ejecute ret en main y salga del loop principal

Símbolos especiales y manejo de excepciones

  • ✎ permite elegir cualquier número de 12 bits, de 0 a 4095, como valor immediate de la instrucción li
  • ▲ permite elegir un valor dentro de un rango de ±128 bytes respecto del propio stack pointer en una instrucción load
    • Por ejemplo, si sp es 2180, se puede elegir entre 2052 y 2308
  • Las acciones prohibidas provocan un crash del programa
    • Sobrescribir una dirección de memoria menor que 1192
    • Lecturas o escrituras no alineadas en direcciones que no sean múltiplos de 4
    • Ejecutar instrucciones ilegales
  • Si ocurre un crash, se ejecuta el manejador de excepciones y se salta a la dirección de trap
    • La dirección de trap inicialmente es 1000, pero puede sobrescribirse en la función set_trap()
    • Cuando ocurre una excepción, el program counter se configura con un valor específico y la ejecución continúa
  • Si se detecta trampa o un error, se restablecen el estado del programa, la memoria y los registros de ese jugador

Reglas de expansión para 3 o 4 jugadores

  • El sp del Player 3 se configura en 2116
  • El sp del Player 4 se configura en 3716
  • Con 3 o más jugadores, el símbolo ▲ solo puede usarse en un rango ubicado a -128 bytes del stack pointer
  • Con más de 2 jugadores, el juego se vuelve bastante inestable y se corrompe rápidamente
  • Llegar a una condición de victoria se vuelve más difícil, pero la partida se vuelve más divertida y caótica

Ejemplos de estrategias de hacking

  • Un crash puede usarse como estrategia de ataque para frenar el avance del rival
  • Si cambias el trap handler a la función game_over, el primer jugador que crashee pierde
    • En este estado, la ficha nop se vuelve muy poderosa
    • Si el rival pone nop sobre el ret de la función que estás ejecutando, puedes perder
  • Si en la función bug() haces overflow con un index de 400 o -400, puedes acceder al stack del rival y sobrescribir su return address
    • Por ejemplo, para ir de la dirección 3784 a la 2184, (3784 - 2184) / 4 = 400, así que se necesita el index -400
  • Con la función copy() puedes copiar instrucciones específicas para crear un shellcode corto en memoria
    • Un shellcode de ejemplo realiza una escritura arbitraria con la combinación li a4, ✎, li a5, ✎, sw a4, 0(a5), ret
    • Si copias la instrucción ret, la return address se configura en el inicio del shellcode y se crea un loop infinito
  • Si en la función bug() configuras el index en 6, puedes escribir la variable value sobre la return address guardada en el stack, en 28(sp)
    • Al retornar desde bug(), el valor de 28(sp) se copia al registro de return address
    • Si pones ahí la dirección del shellcode que creaste, puedes saltar a la memoria

Interpretación de instrucciones y cambios

  • Todos los saltos son relativos al program counter actual, aunque en el disassembler parezcan direcciones absolutas
    • Por ejemplo, el código máquina 1903 de jal a4, 0 se convierte en un loop infinito al ejecutarse
  • La lista de instrucciones válidas del juego está organizada a partir de instrucciones RV32 JRI con códigos máquina de 0 a 4095 que usan a0, a4, a5, sp, ra, etc.
  • El changelog 0.0.6 incluye el cambio de usar while(*prun) en lugar de while(run)
    • Ahora el rival puede inducir una desreferenciación no alineada para forzar un crash
    • La regla de NOP cambió para que solo pueda colocarse en funciones que no estén en ejecución

Diseño y materiales de aprendizaje

  • Los cuadrados a izquierda y derecha del tablero son un mensaje binario codificado en ASCII
    • Los cuadrados blancos son 1 y los negros son 0
  • Los colores usados son solo rojo, azul, negro y blanco, para abaratar la impresión y mejorar la legibilidad en impresoras en blanco y negro
  • No se usa resaltado de sintaxis
    • Es una decisión para evitar que, según el tema, algunas partes del código parezcan más importantes, y para concentrarse juzgando por cuenta propia
  • Entre los materiales para aprender ensamblador RISC-V están riscv-programming.org, cs3410 risc-v interpreter y rvcodecjs de luplab
  • Como material para aprender C se usa la primera parte de Beej's Guide to C Programming
  • Se ofrecen PDFs imprimibles de ejercicios de ensamblador que cubren variables, llamadas a funciones, punteros, strings, structs, arrays y recursión, junto con una versión de “assembly hangman” para completar espacios en blanco

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-10-01
Opiniones de Hacker News

  • Realmente impresionante. En especial, lo más notable me parece que logró que su hija de 12 años jugara esto con él.
    ¿Para cuándo podemos esperar una versión CHERI? :-D

    • Como “CHERI tiene tres objetivos de diseño centrales para mejorar mucho la seguridad del TCB moderno del lenguaje C mediante soporte del procesador para protección de memoria de grano fino y aislamiento de software escalable, y los requisitos, que a veces entran en conflicto, exigieron una cuidadosa coordinación en el diseño”, creo que una versión CHERI sería difícil :)
    • A los 12 años escribía ensamblador 6502. En el entorno informático actual no es fácil que alguien de 12 haga eso.
    • En la época de los 8 bits, esa era una edad común para iniciarse en la computación.

  • Core War es un juego que se desarrolla en una arena de memoria de una máquina virtual que admite un lenguaje ensamblador simulado simple. Lo vi por primera vez en Scientific American en 1984 y, como para entonces ya llevaba unos 15 años programando, reconocí que estaba inspirado en Darwin, un juego más antiguo de Bell Labs.
    Darwin se creó en 1961 y corría en un IBM 7090. Los programas competían por recursos, y ganaba el programa que lograba replicarse y tomar control de todo el espacio asignado. No duró mucho después de que Robert Morris Sr. creara un programa imposible de vencer. Ver [2].
    A mediados de los años 70, Software Practice and Experience era una de mis revistas favoritas de ciencias de la computación, y publicaba con frecuencia la columna Computer Recreations, escrita bajo el seudónimo Aleph-Null. Durante el posgrado disfruté implementando varios de los juegos que aparecían en esa columna. La revista es cara, pero si eres estudiante universitario, es probable que puedas encontrarla en la biblioteca de tu universidad, como hice yo. Los números de los años 70 tenían temas como compiladores Pascal, Algol 68 y programación concurrente; eran fáciles y entretenidos de leer, y gracias a los artículos de N. Wirth conocí Module[3,4] y, más tarde, Oberon[5].
    [1] https://en.wikipedia.org/wiki/Core_War
    [2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
    [3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...

  • Tenía un amigo que decía que le gustaban los juegos pero que no tenía cabeza para programar; con Human Resource Machine terminó programando en la práctica, y algunas de sus soluciones eran mejores que las mías, pese a que yo tenía años de experiencia.

    • A veces una perspectiva nueva ayuda mucho más de lo que uno imagina.
      Mi hijo de 12 años odia las matemáticas, pero es sorprendentemente bueno en Human Resource Machine y SpaceChem. Me hace preguntarme si las matemáticas de la secundaria y las matemáticas de la programación son fundamentalmente distintas.

  • Muy interesante. Considerando el tamaño de la memoria de las computadoras actuales, siempre he sentido que los mnemónicos cortos son una mala decisión de ingeniería.
    También aquí, lo primero que hay que hacer es aprender y recordar qué hace cada instrucción. Si los nombres se cambiaran por formas más descriptivas, sería mucho más fácil aprenderlos, recordarlos y leer el código. Me resulta sospechoso que la gente no lo haga más seguido.
    También creo que el hecho de que este tipo de vulnerabilidad sea posible apunta a una falla de diseño de todo el sistema. Eso no significa que no sea un juego divertido ni una buena forma de aprender, pero en ingeniería se aceptan con demasiada facilidad problemas estructurales. La mayoría ni siquiera llega a ver ese defecto estructural.

    • La primera versión tenía un pseudoensamblador mucho más legible, y también consideré ir en esa dirección. Pero al final quería que mi hija se sintiera cómoda leyendo la salida de objdump, y no creo que aprender unos cuantos mnemónicos sea un gran problema.
      Creo que los niños responden muy bien cuando uno no los subestima. Al menos así fue con mi hija.
      ¿Crees que hay alguien que no considere las lecturas y escrituras arbitrarias como un defecto estructural? Hay miles de personas trabajando en ese problema, y han logrado bastantes avances. Al mismo tiempo, sigo pensando que peek y poke son divertidos.

  • Esto es realmente genial. Quiero probarlo en la empresa.

  • Se ve bastante divertido. ¿Para qué rango de edad crees que es adecuado?

    • La condición de victoria fácil, es decir, salir del bucle principal con un desbordamiento de búfer rápido en bug(), creo que puede hacerla alguien de 10 a 15 años.
      Mi hija tiene 12 años y nos estamos divirtiendo jugándolo juntos. La condición de victoria difícil, es decir, hacer que el rival salte a la función game_over(), es más complicada, pero creo que podría llegar a eso en 5 o 6 meses.
      En adultos no estoy seguro. Algunas personas le tienen tanto miedo al ensamblador, como si lo hubiera creado el diablo, que quizá sea más difícil hacerlas jugar que a los niños.

  • Lo interesante es que tendemos a ver el mundo como un espejo de nosotros mismos.
    Si a mí me interesan los desbordamientos de búfer y la programación, ¿qué tan probable es que mi hija también esté naturalmente muy interesada? Si además es la primera hija y la segunda es mujer, la probabilidad parece aún menor, pero aun así veo a muchos papás insistir.
    Me pregunto si, al hacer este tipo de proyecto, fue consciente de que al menos en cierta medida era un proyecto de vanidad. En cualquier caso, a mí sí me interesan estas cosas, así que me alegra que lo haya publicado.

    • Lo más interesante es con qué facilidad la gente hace suposiciones enormes para que su argumento parezca razonable.
      Insinúas que el creador del proyecto está obligando a su hija a hacerlo por vanidad propia, ¿pero en qué te basas? Revisé varias páginas del sitio y no vi nada que sugiriera eso; al contrario, había varias expresiones suaves de que su hija se divierte y está muy interesada.
      ¿Por qué descartas la posibilidad de que todo haya empezado porque la hija quería saber una y otra vez qué hacía su papá en la computadora? Pudo haber empezado pequeño y luego crecer como un proceso bidireccional entre alguien que comparte un interés y una joven coexploradora.
      Yo tampoco sé cómo fue en realidad, pero tú tampoco. Por mi experiencia de varios años en educación, los niños son aprendices mucho más capaces de lo que suele creerse. La estructura escolar puede ser una razón, pero en el fondo quizá también haya creencias limitantes como esta. Aplaudo a este padre por intentar compartir sus intereses y pasiones con su hija y con el mundo.
    • Como padre, simplemente intento enseñarle todo lo que puedo. A veces es programación, a veces combate, a veces meditación.
      Algunas de esas cosas tendrán valor y otras no. Las probabilidades siempre están en contra. Así es la vida.

  • Cuando la ruta de código RISC-V de 64 bits se estabilice, funcione lo suficientemente bien y hasta desaparezcan los “desbordamientos de búfer”, ¿qué van a hacer con la obsolescencia planificada si C/C++ no siempre les cambia la sintaxis? Pobres almas…

  • Un momento.
    ¿Un juego de mesa con programación en ensamblador? ¿Cómo no se me ocurrió antes? :D

  • PL/I hizo bien cosas como la comprobación de límites en strings/arreglos y una pila que crece hacia arriba en lugar de hacia abajo.
    https://www.acsac.org/2002/papers/classic-multics.pdf