Introducción

Hoy tenemos aquí un crackme de los que te hacen temblar las conexiones neuronales. Estamos acostumbrados al típico serial asociado a un nombre y a veces nos sorprenden.

El crackme data del año 2000, está realizado por aLoNg3x y lo tenéis colgado en crackmes.de. En crackmes.de también disponéis de una solución muy elegante realizada por cronos, pero que no acaba de saciar nuestro afán de descubrir todas las soluciones posibles.

El algoritmo

Abrimos el crackme con Olly y enseguida encontramos la rutina de comprobación junto con los mensajes de éxito y error. Os dejo la rutina comentada como siempre.

004012D7   |.  83C4 08             ADD ESP,8                                 ;  
004012DA   |.  09C0                OR EAX,EAX                                ;  
004012DC   |. /74 16               JE SHORT Zebrone.004012F4                 ;  Salta a Bad boy
004012DE   |. |6A 00               PUSH 0                                    ; /Style = MB_OK|MB_APPLMODAL
004012E0   |. |68 26324000         PUSH Zebrone.00403226                     ; |Title = "Great !!!"
004012E5   |. |68 30324000         PUSH Zebrone.00403230                     ; |Text = "Congratulations, you have cracked the Zebra Crackme ver 1.1"
004012EA   |. |FF75 08             PUSH [ARG.1]                              ; |hOwner = 0011067C ('Zebra - aLoNg3x - 1.1 Version',class='#32770')
004012ED   |. |E8 C6010000         CALL <JMP.&USER32.MessageBoxA>            ; \MessageBoxA
004012F2   |. |EB 14               JMP SHORT Zebrone.00401308
004012F4   |> \6A 00               PUSH 0                                    ; /Style = MB_OK|MB_APPLMODAL
004012F6   |.  68 F8314000         PUSH Zebrone.004031F8                     ; |Title = "Hmmmm :P"
004012FB   |.  68 01324000         PUSH Zebrone.00403201                     ; |Text = "Sorry... The Serial isn't correct :Þ"
00401300   |.  FF75 08             PUSH [ARG.1]                              ; |hOwner = 0011067C ('Zebra - aLoNg3x - 1.1 Version',class='#32770')
00401303   |.  E8 B0010000         CALL <JMP.&USER32.MessageBoxA>            ; \MessageBoxA
00401308   |>  31C0                XOR EAX,EAX
0040130A   |.  40                  INC EAX
0040130B   |.  EB 39               JMP SHORT Zebrone.00401346
0040130D   |>  6A 00               PUSH 0                                    ; /Result = 0
0040130F   |.  FF75 08             PUSH [ARG.1]                              ; |hWnd = 0011067C ('Zebra - aLoNg3x - 1.1 Version',class='#32770')
00401312   |.  E8 89010000         CALL <JMP.&USER32.EndDialog>              ; \EndDialog
00401317   |.  31C0                XOR EAX,EAX
00401319   |.  40                  INC EAX
0040131A   |.  EB 2A               JMP SHORT Zebrone.00401346
0040131C   |>  6A 00               PUSH 0                                    ; /Style = MB_OK|MB_APPLMODAL
0040131E   |.  68 40304000         PUSH Zebrone.00403040                     ; |Title = "Zebra ver. 1.1"
00401323   |.  68 4F304000         PUSH Zebrone.0040304F                     ; |Text = "This is the 1.1 Zebra Crackme, Thanks to Quequero and Koma, to have said me a bug of the previous version. (It was due to an orrible cpu appoximation). As usually you cannot patch this .EXE, you've to find one of the many correct solut"...
00401328   |.  FF75 08             PUSH [ARG.1]                              ; |hOwner = 0011067C ('Zebra - aLoNg3x - 1.1 Version',class='#32770')
0040132B   |.  E8 88010000         CALL <JMP.&USER32.MessageBoxA>            ; \MessageBoxA
00401330   |.  31C0                XOR EAX,EAX
00401332   |.  40                  INC EAX
00401333   |.  EB 11               JMP SHORT Zebrone.00401346
00401335   |>  6A 00               PUSH 0                                    ; /Result = 0
00401337   |.  FF75 08             PUSH [ARG.1]                              ; |hWnd = 0011067C ('Zebra - aLoNg3x - 1.1 Version',class='#32770')
0040133A   |.  E8 61010000         CALL <JMP.&USER32.EndDialog>              ; \EndDialog
0040133F   |.  31C0                XOR EAX,EAX
00401341   |.  40                  INC EAX
00401342   |.  EB 02               JMP SHORT Zebrone.00401346
00401344   |>  31C0                XOR EAX,EAX
00401346   |>  C9                  LEAVE
00401347   \.  C2 1000             RETN 10
================================================================
0040134A   /$  55                  PUSH EBP
0040134B   |.  89E5                MOV EBP,ESP
0040134D   |.  83EC 68             SUB ESP,68
00401350   |.  FF75 08             PUSH [ARG.1]                              ; /x1
00401353   |.  E8 78010000         CALL <JMP.&CRTDLL.atof>                   ; \atof
00401358   |.  DD55 E8             FST QWORD PTR SS:[EBP-18]
0040135B   |.  83EC 08             SUB ESP,8
0040135E   |.  DD1C24              FSTP QWORD PTR SS:[ESP]
00401361   |.  E8 82010000         CALL <JMP.&CRTDLL.floor>
00401366   |.  DD5D F8             FSTP QWORD PTR SS:[EBP-8]
00401369   |.  FF75 0C             PUSH [ARG.2]                              ; /x2
0040136C   |.  E8 5F010000         CALL <JMP.&CRTDLL.atof>                   ; \atof
00401371   |.  DD55 D8             FST QWORD PTR SS:[EBP-28]
00401374   |.  83EC 08             SUB ESP,8
00401377   |.  DD1C24              FSTP QWORD PTR SS:[ESP]
0040137A   |.  E8 69010000         CALL <JMP.&CRTDLL.floor>
0040137F   |.  83C4 18             ADD ESP,18
00401382   |.  DD55 F0             FST QWORD PTR SS:[EBP-10]
00401385   |.  DC4D F8             FMUL QWORD PTR SS:[EBP-8]
00401388   |.  D9EE                FLDZ
0040138A   |.  DED9                FCOMPP                                    ;  floor(x1)*floor(x2)=0 ???
0040138C   |.  DFE0                FSTSW AX                                  ;  <<Store status word
0040138E   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
0040138F   |.  75 07               JNZ SHORT Zebrone.00401398                ;  Si salta todo OK
00401391   |.  31C0                XOR EAX,EAX
00401393   |.  E9 96000000         JMP Zebrone.0040142E                      ;  Bad boy
00401398   |>  DD45 F8             FLD QWORD PTR SS:[EBP-8]                  ;  <<Floating point load
0040139B   |.  DC5D F0             FCOMP QWORD PTR SS:[EBP-10]               ;  x1 = x2 ???
0040139E   |.  DFE0                FSTSW AX                                  ;  <<Store status word
004013A0   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
004013A1   |.  75 07               JNZ SHORT Zebrone.004013AA                ;  Si salta todo OK
004013A3   |.  31C0                XOR EAX,EAX
004013A5   |.  E9 84000000         JMP Zebrone.0040142E                      ;  Bad boy
004013AA   |>  DD45 F8             FLD QWORD PTR SS:[EBP-8]                  ;  <<Floating point load
004013AD   |.  DD5D C8             FSTP QWORD PTR SS:[EBP-38]
004013B0   |.  D9E8                FLD1                                      ;  Carga 1 en el stack
004013B2   |.  DD55 C0             FST QWORD PTR SS:[EBP-40]                 ;  <<Floating point store
004013B5   |.  DC5D C8             FCOMP QWORD PTR SS:[EBP-38]               ;  x1 > 1 ???
004013B8   |.  DFE0                FSTSW AX                                  ;  <<Store status word
004013BA   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
004013BB   |.  77 2D               JA SHORT Zebrone.004013EA                 ;  Si salta bad boy
004013BD   |.  DF2D 38304000       FILD QWORD PTR DS:[403038]                ;  <<Load integer>> 2540BE400 = 10^10
004013C3   |.  DD55 B8             FST QWORD PTR SS:[EBP-48]                 ;  <<Floating point store
004013C6   |.  DC5D C8             FCOMP QWORD PTR SS:[EBP-38]               ;  x1 < 10^10 ???
004013C9   |.  DFE0                FSTSW AX                                  ;  <<Store status word
004013CB   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
004013CC   |.  72 1C               JB SHORT Zebrone.004013EA                 ;  Si salta bad boy
004013CE   |.  DD45 F0             FLD QWORD PTR SS:[EBP-10]                 ;  <<Floating point load
004013D1   |.  DD5D B0             FSTP QWORD PTR SS:[EBP-50]                ;  <<Store and pop
004013D4   |.  DD45 C0             FLD QWORD PTR SS:[EBP-40]                 ;  <<Floating point load
004013D7   |.  DC5D B0             FCOMP QWORD PTR SS:[EBP-50]               ;  x2 > 1 ???
004013DA   |.  DFE0                FSTSW AX                                  ;  <<Store status word
004013DC   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
004013DD   |.  77 0B               JA SHORT Zebrone.004013EA                 ;  Si salta bad boy
004013DF   |.  DD45 B8             FLD QWORD PTR SS:[EBP-48]                 ;  <<Floating point load>> carga 10^10
004013E2   |.  DC5D B0             FCOMP QWORD PTR SS:[EBP-50]               ;  x2 < 10^10 ???
004013E5   |.  DFE0                FSTSW AX                                  ;  <<Store status word
004013E7   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
004013E8   |.  73 04               JNB SHORT Zebrone.004013EE                ;  Salta si menor
004013EA   |>  31C0                XOR EAX,EAX
004013EC   |.  EB 40               JMP SHORT Zebrone.0040142E                ;  Bad boy
004013EE   |>  DD45 F8             FLD QWORD PTR SS:[EBP-8]                  ;  <<Floating point load>> carga x1
004013F1   |.  D9FE                FSIN                                      ;  Sin(x1)
004013F3   |.  DD5D A8             FSTP QWORD PTR SS:[EBP-58]                ;  <<Store and pop
004013F6   |.  DD45 F0             FLD QWORD PTR SS:[EBP-10]                 ;  <<Floating point load>> carga x2
004013F9   |.  D9FE                FSIN                                      ;  Sin(x2)
004013FB   |.  DD5D A0             FSTP QWORD PTR SS:[EBP-60]                ;  <<Store and pop
004013FE   |.  DD45 A8             FLD QWORD PTR SS:[EBP-58]                 ;  <<Floating point load
00401401   |.  DC4D A0             FMUL QWORD PTR SS:[EBP-60]                ;  Sin(x1) * Sin(x2)
00401404   |.  DF2D 30304000       FILD QWORD PTR DS:[403030]                ;  <<Load integer>> 2386F26FC10000 = 10^16
0040140A   |.  DEC9                FMULP ST(1),ST                            ;  10^16 * (Sin(x1) * Sin(x2))
0040140C   |.  83EC 08             SUB ESP,8
0040140F   |.  DD1C24              FSTP QWORD PTR SS:[ESP]                   ;  <<Store and pop
00401412   |.  E8 D1000000         CALL <JMP.&CRTDLL.floor>
00401417   |.  83C4 08             ADD ESP,8
0040141A   |.  DD5D 98             FSTP QWORD PTR SS:[EBP-68]
0040141D   |.  D9EE                FLDZ                                      ;  <<Load 0.0 onto stack
0040141F   |.  DC5D 98             FCOMP QWORD PTR SS:[EBP-68]               ;  10^16 * (Sin(x1) * Sin(x2)) = 0 ???
00401422   |.  DFE0                FSTSW AX
00401424   |.  9E                  SAHF                                      ;  <<Store AH into FLAGS
00401425   |.  75 05               JNZ SHORT Zebrone.0040142C                ;  Si NO salta todo OK
00401427   |.  31C0                XOR EAX,EAX
00401429   |.  40                  INC EAX
0040142A   |.  EB 02               JMP SHORT Zebrone.0040142E
0040142C   |>  31C0                XOR EAX,EAX
0040142E   |>  C9                  LEAVE
0040142F   \.  C3                  RETN

La primera dificultad que podemos encontrar es que utiliza instrucciones FPU y coma flotante, ya que si no tenemos la vista entrenada nos puede resultar un engorro. Superado esto, la rutina de comprobación se puede resumir así:

  • x1 * x2 != 0
  • x1 != x2
  • x1 > 1 y < 10^10
  • x2 > 1 y < 10^10
  • Floor[10^16 * sin(x1) * sin(x2)] = 0

A priori no parece que tenga mucha dificultad, pero vamos a analizarlo más concienzudamente. Necesitamos que la parte entera del resultado de la multiplicación sea 0, algo que parece sencillo, pero fíjate que la constante 10^16 nos obliga a su vez, a que el resultado del seno sea muy pequeño, cosa que como comprobaréis limita mucho los resultados satisfactorios.

Repasando trigonometría

Cuando nos enseñó nuestro profesor la función del seno nos hizo el siguiente dibujo:

circunferencia_e

Partiendo de la circunferencia unitaria, podemos concluir que el seno de alpha es igual a la altura x. Como lo que nos interesa a nosotros es que el seno sea muy pequeño, en realidad estamos buscando que la x sea lo más pequeña posible. Llegamos entonces a la conclusión de que las soluciones para enteros entre 1 y 10^10 van a ser muy reducidas. Además nos percatamos que el ángulo alpha va a tener que estar muy proximo a 0º – 360 (0 – 2π) y a 180º (π). En el siguiente gráfico queda claro el estrecho margen en el que nos movemos.

circunferencia_angulos_e

Si habéis leído la solución de cronos ahora le encontraréis algo más de sentido a por que él utilizó fracciones continuas de π y cogió como resultado los numeradores más cercanos a 10^10, en su caso 245850922 y 411557987.

Análisis operacional

Vamos a analizar un ejemplo operacional.

sin( x rad)
sin(245850922) = 6,1180653830011163142712109862972e-9
sin(411557987) = 2,536716051963676479648989773448e-9

sin(245850922)*sin(411557987) = 1,5519794664022230015882605365808e-17

10^16 * 1,5519794664022230015882605365808e-17 = 0,15519794664022230015882605365808

Floor(0,15519794664022230015882605365808) = 0

Como veis, el exponente negativo (^-17) debe ser mayor que el positivo (^16) para tener éxito.

Fuerza bruta

Lo que vamos a hacer a continuación es buscar todos los senos con exponente negativo ^-8 ó ^-9 de enteros entre 1 y 10^10, y vamos a cruzar los resultados para determinar todos los resultados válidos.

Preparamos el programa y le dejamos trabajar. En principio vamos a filtrar todos los resultados que tengan exponente negativo y luego ya aislaremos los que nos interesan. Esto lo hago por curiosidad.

aprox

La fuerza bruta nos arroja 63663 resultados con exponente negativo entre ^-5 y ^-9, de los cuales solamente nos quedamos con 65, que son los comprendidos a exponentes de entre ^-8 y ^-9. Los números mágicos son los siguientes:

magicnumbers

Los rojos son exponentes ^-9, el resto ^-8.

La mayoría de estos números solo valen con ciertas combinaciones, de hecho, ninguno vale para todos. Esto se debe, a parte del propio exponente, a que hay senos positivos y negativos y para hacer válido a un seno negativo hay que combinarlo con otro negativo. Esto último se debe únicamente a la interpretación que hace el crackme.

 Finalmente cruzamos los resultados y obtenemos 44 combinaciones de seriales válidos que si obviamos repeticiones se reducen a la mitad.

 checker

Combinaciones válidas:

seriales

Conclusiones

Podemos concluir que para cada 10^10 enteros hay 22 soluciones posibles. Finalmente comentar que si aLoNg3x no hubiera puesto el límite en 10^10, habría soluciones infinitas.

Links


Warning: This challenge is still active and therefore should not be resolved using this information. Aviso: Este reto sigue en
El reto Se nos proporciona la imagen anterior y se nos invita a resolver la ecuación para el menor entero
Libros Hacker Épico La apacible existencia de Ángel Ríos da un vuelco cuando una antigua compañera de clase, de la
http://youtu.be/c4CNY902SAE Versión de texto Lista de reproducción

Warning: This challenge is still active and therefore should not be resolved using this information.
Aviso: Este reto sigue en activo y por lo tanto no se debería resolver utilizando esta información.

Introducción

El cifrado XOR es uno de los algoritmos más utilizados en el mundillo de la encriptación. Aunque por sí solo no es seguro, suele formar parte de cifrados más complejos e incluso si sois aficionados a los crackmes os habréis dado cuenta de que raro es el crackme que no lo utiliza.

Hoy vamos a hacer un recorrido sobre los retos de encriptación que nos propone yoire.com, que aunque son muy sencillos, nos proporcionan una estupenda base para iniciarnos en este tipo de retos.

/challenges/crypt/xor/0_chall_very_easy

En este primer reto, el autor te da directamente la solución, ya que, nos da un texto cifrado y nos dice que está cifrado con la clave 10. Lo que el autor no indica es que la clave es hexadecimal, mas adelante ya aprendereis a fijaros en esos detalles.

Texto cifrado: uqci0t~7d0ie0dxy~{

Clave: 10

challenges_crypt_xor_0_chall_very_easy

/challenges/crypt/xor/1_chall_easy

Esta vez disponemos de un texto cifrado pero sin pistas. Si nos fijamos en el código fuente veremos que la clave utilizada esta vez es 20 y decimal.

<?php
include("../../../core.php");
print Website::header(array("title"=>"The XOR Chall - Easy"));
print Challenges::header();
?>
Convierte la solución que está cifrada con una clave XOR para obtener la respuesta a este reto:
<br><br>
<?php

$solution_xored="m{a4s{`4}`5";
$key           = sprintf("%2x",20);
$solution      = Crypt::XorData($solution_xored,$key);

print "La solución es: ".$solution_xored;

print "<br><br>";
print Challenges::solutionBox();
print Challenges::checkSolution(Crypt::XorData($solution_xored,$key));
?>

challenges_crypt_xor_1_chall_easy

/challenges/crypt/xor/2_chall_mid

En esta ocasión debemos ojear el código fuente para averiguar como solucionar el reto. En esta ocasión y como de lo que se trata es de aprender, este lo dejaré sin solucionar.

<?php 
include("../../../core.php");
print Website::header(array("title"=>"The XOR Chall - Mid"));
print Challenges::header();
?>
Convierte la solución que está codificada y cifrada con una clave XOR para obtener la respuesta a este reto:
<br><br>
<?php

foreach (
        preg_split("/\./","2.4.10.71.3698") 
        as $something
        ) 

$value=pow($something,2);

$key            = dechex($value);
$solution_xored = base64_decode("ucSnos+lo8Oqtw==");
$solution       = Crypt::XorData($solution_xored,$key);

print Challenges::solutionBox();
print Challenges::checkSolution(Crypt::XorData($solution_xored,$key));
?>
<a href="<?=$_SERVER["PHP_SELF"]?>?showSource">Ver código fuente</a>

<?php
if(Common::getString("showSource")!==false) {
    print "<hr>";
    highlight_file(__FILE__);
}
print Website::footer();
?>
  • Lo primero es mediante un compilador online de PHP, obtener la variable $key.
  • Decodificar la clave xoreada «ucSnos+lo8Oqtw==«.
  • Solución = base64_decode(«ucSnos+lo8Oqtw==») XOR $key

Venga que casi lo tienes.

/challenges/crypt/xor/3_chall_average

En este reto nos indican que el código fuente está encriptado. Cuando nos enfrentamos a XOR en texto grandes y teniendo un indicio de lo que puede contener el código desencriptado es sencillo encontrar lo que buscamos. En este caso en concreto podemos intuir que seguramente el texto contenga la palabra «php«, una vez llegamos a esa conclusión la solución llega sola. Este método no deja de ser un ataque por fuerza bruta.

Código encriptado

lo 8 p]Z9>3<%45xr~~~~~~3?"5~ 8 ryk]Z "9>$p52#9$5jj85145"x1""1)xr$9

lt;5rmnr85pp81<$p81<<5>75#jj85145"xyk]Zon]Z1"535p!%5p5$5p81p#94?p396"14?~~~p%===~~~p$5>4"±#p!%5p1&5"97%1"p3£=?p 1"1p?2$5>5"p<1p"5# %5#$1p1p5#$5p"5$?j]Zl2"nl2"n]Zlo 8 ]Z]Zt;5)ppppppppppppmpre`rk]Zt=5pppppppppppppmp69<575$3?>$5>$#xyk]Zt=5(?"54pppppppmp") $jj?"1$1xt=5|t;5)yk]Z]Z "9>$p81<<5>75#jj#?<%$9?>?(xyk]Z "9>$p81<<5>75#jj3853;?<%$9?>xr3````aryk]Zon]Zl1p8"56mrlomtrr onolom%"<5>3?45x") $jj?"1$1xr#8?'?%"35r|t;5)yyonrn5"p3£497?p6%5>$5l1n]Z]Zlo 8 ]Z96x?==?>jj75$$"9>7x") $jj?"1$1xr#8?'?%"35r|t;5)yyqmm61<#5yp+]ZY "9>$prl8"nrk]ZY "9>$pt=5(?"54k]Z-]Z "9>$p52#9$5jj6??$5"xyk]Zon]Z

Código desencriptado

challenges_crypt_xor_3_chall_average

/challenges/crypt/xor/4_chall_hard

En este último reto nos aparece un mensaje que nos dice «La solución es: 7b1a4147100a155a0f45574e0f58«. Nos fijamos en el código fuente y vemos que en la encriptación interviene una cookie llamada «PHPSESSID«.

Código fuente

<?php 
include("../../../core.php");
print Website::header(array("title"=>"The XOR Chall - Hard"));
print Challenges::header();
?>
Convierte la solución que está codificada y cifrada con una clave XOR para obtener la respuesta a este reto:
<br><br>
<?php

$sessid             = isset($_COOKIE["PHPSESSID"])?$_COOKIE["PHPSESSID"]:">hi!|m¬_ö_Ó_;m'`ñ·$\"<";
$key                = Encoder::asc2hex($sessid);
$hiddenSolution     = file_get_contents(Config::$challsHiddenData."crypt_xor_average.solution");
$hex_xored_solution = Encoder::data2hex(Crypt::XorData($hiddenSolution,$key));

print "La solucion es: ".$hex_xored_solution;

print "<br><br>";

print Challenges::solutionBox();
print Challenges::checkSolution($hiddenSolution);
?>
<a href="<?=$_SERVER["PHP_SELF"]?>?showSource">Ver código fuente</a>

<?php
if(Common::getString("showSource")!==false) {
    print "<hr>";
    highlight_file(__FILE__);
}
print Website::footer();
?>

Desde Firefox vamos a usar una extensión muy interesante llamada Advanced Cookie Manager que nos permitirá visualizar y modificar dicha cookie.

challenges_crypt_xor_4_chall_hard_02

Una particularidad de la encriptación XOR es que si realizamos «algo XOR 0 == algo«, por lo que un ataque típico sería anular la cookie. La modificamos poniendo como valor 0 y guardamos. Recargamos la web con F5 y ahora nos fijamos que el valor de la solución ha cambiado a «7e5f4410435f1058514254100a19«. Finalmente y teniendo en cuenta que el texto que tenemos es hexadecimal, hacemos fuerza bruta marcando la opción Output First y clickamos en Search.

crypt_xor_4_chall_hard_2

En el mismo directorio donde tenemos el programa se genera un archivo llamado «XOR_enumeration.txt«, que contiene todos los resultados, echamos un vistazo y hemos tenido suerte.

crypt_xor_4_chall_hard_3

Enlaces

El reto

Se nos proporciona la imagen anterior y se nos invita a resolver la ecuación para el menor entero positivo que representa cada fruta. La solución del reto es concatenar «Flag-» a la suma de los valores de las tres frutas.

Análisis inicial

El enunciado es breve pero ya nos adelanta que existen varias soluciones y que además sólo quieren los números más pequeños que podamos encontrar.

Las frutas están muy bien y son muy sanas pero a nosotros se nos hace más sencillo plantear la ecuación con letras.

\begin{align}
&  \frac{x}{y+z}+\frac{y}{x+z}+\frac{z}{x+y}=4\\
\end{align}

Para arrojar algo de luz veamos la representación gráfica en 2D y 3D con la ayuda de Desmos.

3D

Las gráficas más que luz nos traen oscuridad de modo que preguntemos a ChatGPT.

ChatGPT

resuelve: (x/y+z)+(y/x+z)+(z/x+y)=4 para enteros positivos

Dado que las variables x, y, z son enteros positivos, podemos intentar encontrar una solución para la ecuación bajo estas condiciones. Sin embargo, encontrar una solución exacta puede ser complejo debido a la naturaleza no lineal de la ecuación. Aun así, podemos intentar algunos enfoques:

  • Prueba y error: Podemos probar diferentes combinaciones de valores enteros positivos para x, y, z y ver si satisfacen la ecuación.
  • Análisis de casos específicos: Podemos comenzar analizando casos más simples, como cuando dos de las variables son iguales, y luego ampliar nuestra búsqueda desde allí.
  • Análisis gráfico o numérico: Utilizando herramientas gráficas o numéricas, podríamos identificar posibles soluciones y luego verificar si son enteros positivos.

Voy a realizar un análisis numérico con un rango limitado de valores para ver si encontramos alguna solución que cumpla con las condiciones. Vamos a probar con valores de 1 a 10 para cada variable.

El análisis numérico para valores de en el rango de 1 a 10 no ha encontrado ninguna solución que satisfaga la ecuación. Esto sugiere que, dentro de este rango, no existen combinaciones de enteros positivos que cumplan con la ecuación.

Dado que la ecuación es bastante compleja y no lineal, es posible que las soluciones, si existen, se encuentren fuera del rango considerado o que requieran un enfoque diferente para ser identificadas. Si tienes un rango específico de valores en mente o si hay alguna otra restricción o contexto relevante, por favor házmelo saber para poder ajustar el análisis en consecuencia.

Básicamente nos está invitando a utilizar prueba y error para encontrar una solución, y el prueba y error de las matemáticas no es más que la fuerza bruta en programación.

El código

Partiendo del problema anterior dame un código en python que realice una comprobación recursiva de todas las variables con un rango de 1 a 999.

soluciones = []
rango_valores_x = range(1, 999)
rango_valores_y = range(1, 999)
rango_valores_z = range(1, 999)

for x in rango_valores_x:
    for y in rango_valores_y:
        for z in rango_valores_z:
            # Calculamos el valor de la expresión para cada combinación de x, y, z
            valor = x / (y + z) + y / (x + z) + z / (x + y)
            # Comprobamos si el valor es igual a 4 y agregamos la solución a la lista
            if abs(valor - 4) < 1e-6:  # Usamos una pequeña tolerancia para evitar errores de precisión
                soluciones.append((x, y, z))

print(soluciones)

Dejo resaltada la línea 12 del código ya que en ella reside el problema. Está comprobando con un margen de tolerancia de 10-6 ya que el resultado de las diferentes fracciones no da como resultado exacto 4. Esto es un problema ya que nosotros necesitamos que de exactamente 4 para validar los valores enteros de x, y y z. Pongo un ejemplo para el que se haya perdido con una solución válida para la tolerancia 10-6 siendo x=2, y=264 y z=993.

\begin{align}
&  \frac{2}{264+993}+\frac{264}{2+993}+\frac{993}{2+264}=4.000000429\\
\end{align}

En otras palabras, ChatGPT nos ha brindado una solución aproximada que no sirve para nuestro propósito. Seguimos probando con el código anterior quitando la tolerancia y con rangos mayores hasta que en 106 paro. Me acaba de quedar claro que con la fuerza bruta no vamos a ninguna parte, o más bien, no tenemos capacidad de computación para resolverlo de ésta manera.

¿Qué está pasando?

Lo que pasa es que estamos ante una ecuación algebraica de 3 incógnitas que deben ser enteros positivos cuya solución se alcanza mediante la teoría de curvas elípticas.

Curvas elípticas

Las curvas elípticas son fundamentales en matemáticas avanzadas, representadas por la ecuación y2=x3+Ax+B, donde A y B son constantes. Estas curvas son un punto de encuentro entre la geometría, la teoría de números y el álgebra, ofreciendo un campo rico para la exploración y el análisis. En este CTF, nos enfocaremos en los puntos racionales de las curvas elípticas. Utilizando el método tangente-secante, un procedimiento geométrico iterativo, buscaremos ampliar un conjunto finito de soluciones conocidas a la ecuación de la curva. Este método nos permite indagar en la estructura de las soluciones racionales, que potencialmente pueden ser infinitas. Además, estableceremos una conexión entre las soluciones enteras de las ecuaciones diofánticas y los puntos racionales en las curvas elípticas partiendo de la ecuación (1) especificada en el análisis inicial. A pesar de su aparente simplicidad, esta ecuación es conocida por presentar soluciones mínimas de gran tamaño.

Adecuación

Antes de nada, necesitamos saber el grado de la ecuación, de modo que planteamos la ecuación en forma polinómica estándar deshaciéndonos de los denominadores.

\begin{align}
\begin{split}
n(a+b)(b+c)(c+a)=a(a+b)(c+a)+b(b+c)(a+b)+c(c+a)(b+c)
\end{split}
\end{align}

Ahora necesitamos expandir y simplificar para llegar a la conclusión de que estamos ante una ecuación diofántica de grado 3. Este proceso es engorroso por la cantidad de términos a manejar así que vamos a utilizar Mathematica como software de respaldo para finalmente obtener el polinomio en la forma de Weierstrass según la ecuación 4.

\begin{align}
&  y^2=x^3+109x^2+224x\\
\end{align}

donde:

\begin{align}
x = \frac{−28(a+b+2c)}{(6a+6b−c)}\\
y = \frac{364(a−b)}{(6a+6b−c)}
\end{align}

Las relación entre la ecuación 3 y los puntos de la curva elíptica se establecen mediante la ecuación 4. Las transformaciones entre las soluciones (a, b, c) y los puntos (x, y) en la curva elíptica vienen dados por las ecuaciones 5 y 6. Con estas transformaciones, cada solución de la ecuación diofántica se puede representar como un punto en la curva elíptica, y las operaciones de suma de puntos en la curva elíptica pueden usarse para encontrar nuevas soluciones de la ecuación diofántica.

Mathematica

El código que tenéis a continuación pertenece al gran trabajo de Aditi Kulkarni [7], que además nos da el resultado para cualquier valor de n. Ojo porque para n=4 el resultado tiene 81 dígitos, para n=6 tiene 134, para n=10 tiene 190 y para n=12 asciende a 2707 dígitos.

(* Asignar un valor numérico a n *)
n = 4;
(* Definir la ecuación de una curva elíptica en términos de n *)
curve4 = y^2 == x^3 + (4*n^2 + 12*n - 3)*x^2 + 32*(n + 3)*x;
(* Encontrar un punto racional en la curva que no sea (4,0) *)
P4 = {x, y} /. First[FindInstance[curve4 && x != 4 && y != 0, {x, y}, Integers]];
(* Función para calcular la pendiente entre dos puntos en la curva, 
   o la derivada en el punto si son iguales *)
Slope4[{x1_, y1_}, {x2_, y2_}] := 
  If[x1 == x2 && y1 == y2, 
     ImplicitD[curve4, y, x] /. {x -> x1, y -> y1}, 
     (y2 - y1)/(x2 - x1)];
(* Función para calcular la intersección en y de la línea entre dos puntos 
   o la tangente en el punto si son iguales *)
Intercept4[{x1_, y1_}, {x2_, y2_}] := y1 - Slope4[{x1, y1}, {x2, y2}]*x1; 
(* Función para encontrar el siguiente punto racional en la curva *)
nextRational4[{x1_, y1_}, {x2_, y2_}] := 
  {Slope4[{x1, y1}, {x2, y2}]^2 - CoefficientList[curve4[[2]], x][[3]] - x1 - x2, 
   -Slope4[{x1, y1}, {x2, y2}]^3 + Slope4[{x1, y1}, {x2, y2}]*(CoefficientList[curve4[[2]], x][[3]] + x1 + x2) - Intercept4[{x1, y1}, {x2, y2}]};
(* Función para convertir un punto en la curva elíptica a una solución diofántica *)
ellipticToDiophantine[n_, {x_, y_}] := 
  {(8*(n + 3) - x + y)/(2*(4 - x)*(n + 3)), 
   (8*(n + 3) - x - y)/(2*(4 - x)*(n + 3)), 
   (-4*(n + 3) - (n + 2)*x)/((4 - x)*(n + 3))};
(* Usar nextRational4 para iterar desde P4 hasta encontrar una solución 
   válida y positiva para la ecuación diofántica *)
sol4 = ellipticToDiophantine[n, 
   NestWhile[nextRational4[#, P4] &, P4, 
     ! AllTrue[ellipticToDiophantine[n, #], Function[item, item > 0]] &]];
(* Escalar la solución para obtener enteros mínimos *)
MinSol4 = sol4*(LCM @@ Denominator[sol4])
(* Suma de las tres variables*)
Total[MinSol4]

Solución

Concatenando Flag- con el resultado de Mathematica tenemos la ansiada flag.

Flag-195725546580804863527010379187516702463973843196699016314931210363268850137105614

Conclusiones

ChatGPT ha demostrado ser eficaz en el análisis y la resolución de problemas, siempre que se le proporcione el contexto adecuado. Sin embargo, es importante ser conscientes de que la respuesta proporcionada puede ser aproximada, especialmente si la solución requiere una gran cantidad de recursos computacionales. Por ejemplo, al trabajar con una ecuación diofántica y valores específicos para (x) e (y), ChatGPT puede ayudar a calcular puntos como (P), (2P), (3P), etc., pero hay que tener en cuenta que los resultados para estos puntos pueden ser estimaciones.

Finalmente, os invito a leer la solución de Mingliang Z. [4], en la que se resuelve el problema por completo y de forma muy detallada.

Enlaces

Libros

Hacker Épico

La apacible existencia de Ángel Ríos da un vuelco cuando una antigua compañera de clase, de la que siempre ha estado enamorado, le pide ayuda para descifrar un misterioso archivo. A partir de entonces, Ángel se verá envuelto en una intriga relacionada con el contenido del archivo, que complicará su vida y lo expondrá a un grave peligro. En el camino hacia la verdad, únicamente contará con sus sorprendentes conocimientos de hacking y el apoyo de su peculiar amigo Marcos. Técnicas de hacking web, sistemas y análisis forense son algunos de los temas que se tratan con total rigor en esta mezcla de novela negra y manual técnico.

Web oficial

La Caza de Hackers: Ley y Desorden en la Frontera Electrónica

En 1990, la caída del sistema del día de Martin Luther King, que afecto a la compañía telefónica AT&T y dejó sin comunicaciones a millones de norteamericanos, desencadenó la persecución y detención de decenas de hackers, acusados de causar el hundimiento, que hasta ese momento era ignorados por la policía y las leyes. Bruce Sterling, considerado uno de los mayores expertos en el género del ciberpunk, nos ofrece un apasionante reportaje desde el principio de la era de internet, los ordenadores personales, y la frontera electrónica partiendo de la base de ese hecho inaudito. Con una entretenida prosa novelesca, Sterling nos lleva a conocer a todos los implicados en el asunto, desde los primeros activistas de internet hasta los policías encargados del caso, que cimentó los pilares de lo que hoy es la libertad de expresión en Internet. 25 años después de los sucesos del día de Martin King, «La Caza de Hackers», se ha convertido en un libro de culto y un documento histórico imprescindible para comprender y entender la transformación y el impacto de las nuevas comunicaciones en el Siglo XXI.

Cybersecurity for the Home and Office

El título de este libro anima a que tomes control de la ciberseguridad no solo en tu trabajo, sino también para tus asuntos personales. La ciberdelincuencia es una industria delictiva que mueve miles de millones de dólares al año y cuyos actores apenas temen a las fuerzas del orden. Los incidentes siguen creciendo, y más allá de la protección en los lugares de trabajo, también es necesario protegernos a nosotros mismos y a nuestras familias.

Web oficial

Messing with the Enemy: Surviving in a Social Media World of Hackers, Terrorists, Russians, and Fake News

Clint Watts, un ex agente especial del FBI, oficial del Ejército de Estados Unidos y destacado experto en ciberseguridad, ofrece una mirada devastadora y esencial a las campañas de desinformación, las noticias falsas y las operaciones de espionaje electrónico que se han convertido en la vanguardia de la guerra moderna. También ofrece consejos para protegernos en nuestro día a día.

Cybersecurity: An Essential Guide to Computer and Cyber Security for Beginners, Including Ethical Hacking, Risk Assessment, Social Engineering, Attack and Defense Strategies, and Cyberwarfare

Con multitud de ejemplos, este libro le mostrará que Internet no es simplemente una forma de ver vídeos de gatos monos; es un campo de batalla, un invento militar que se descubrió accidentalmente que era capaz de dominar cualquier amenaza económica, digital y políticamente.
Desde los foros más burdos hasta los servicios en línea más sofisticados, hay una guerra en marcha y, lo quieras o no, estás implicado por el mero hecho de estar aquí, así que mejor ármate de conocimientos.

Hackstory.es

Historia de la comunidad hacker en España, centrada en la década de los 90, cuando aparecen los primeros grupos y nace la cultura hacker. El libro narra el quién fue quién, así como sus hazañas, anécdotas y colectivos e individuales más punteros. Este ingente trabajo de investigación nació en 2009, con la puesta en marcha de un wiki, al estilo wikipedia, llamado Hackstory.net y donde en estos años la autora ha ido creando fichas, accesibles al público, que le han permitido escribir este libro, sin parangón en Europa. La comunidad hacker ha revisado los textos así como apoyado a la autora, tanto a la hora de aportar información, como en una campaña de «crowdfunding» con la que se consiguió una respetable cantidad para tener el tiempo suficiente de escribir el libro. Además de ser sus principales mecenas, protagonistas y aportadores de información, los hackers españoles han participado en todos los aspectos organizativos relacionados con la producción y distribución del libro.

Documentales

Hackers wanted

Documental narrado por Kevin Spacey que explora los orígenes y la naturaleza de los hackers y los piratas informáticos.
Sigue las aventuras de Adrián Lamo, un célebre hacker y periodista estadounidense, conocido por haber delatado a Chelsea Manning, el soldado que presuntamente filtró a WikiLeaks el vídeo que mostraba a soldados americanos asesinando a civiles en
Afganistán.

Hackers are people too

Este documental tiene como objetivo retratar de forma exhaustiva la comunidad hacker. En un esfuerzo por cuestionar las ideas preconcebidas y los estereotipos de los medios de comunicación, HACKERS ARE PEOPLE TOO permite a los hackers hablar por sí mismos y presentar su comunidad al público.

Hackers in Wonderland

Hackers in Wonderland es un documental del año 2000, producido y dirigido por Russell Barnes.
Se centra en los hackers del Reino Unido, y contiene entrevistas con ellos donde revelan lo que les impulsa a hackear y sus opiniones sobre el hacktivismo.

Hackers: Wizards of the electronic age

Este documental sobre la comunidad de hackers incluye imágenes de una conferencia de hackers y entrevistas con algunos de los programadores que crearon la revolución de los ordenadores personales, como Bill Atkinson, Bill Budge o Doug Carlston.
Convertido ya en un clásico sobre la revolución de los ordenadores, las entrevistas fueron grabadas durante un largo fin de semana en una conferencia de hackers
de 1984.

Podcast

conCISOS

Programa en el que se conversa con grandes profesionales del mundo de la seguridad para conocer su visión sobre la situación actual y la ciberseguridad.

Spotify | Ivoox

Brigada OSINT

El único Podcast en español íntegramente dedicado al OSINT (Open Source Intelligence), conjunto de técnicas y herramientas para recopilar información pública, correlacionar los datos y procesarlos. Está dirigido por el Analista y Consultor OSINT David Sanz y son episodios de menos de una hora donde se habla de casos reales, herramientas, noticias, libros y documentales.

Web Oficial

Ciberseguridad sin censura

Ciberseguridad sin censura, es el podcast del Instituto de Ciberseguridad en el que se tocan temas relacionados a la tecnología y seguridad, de forma objetiva y sin censura.
Su visión es que a través de este podcast, puedas encontrar noticias, entrevistas y temas de tecnología y seguridad en general desde un punto de vista completamente imparcial.

Spotify

The social engineer

Podcast centrado en ingeniería social. Entender cómo interactuamos, nos comunicamos y transmitimos información puede ayudarnos a proteger, mitigar y comprender este tipo de ataques.

Spotify

401 access denied

Cada quince días, el hacker ético de Delinea Joseph Carson y los expertos en formación en ciberseguridad deCybrary comparten sus puntos de vista con invitados especiales en este interesante podcast sobre la actualidad en materia de ciberseguridad.

Web oficial

Videojuegos

else Heart.Break ()

Sebastian acaba de conseguir su primer trabajo en la lejana ciudad de Dorisburg. Se traslada allí para
comenzar su vida adulta y averiguar quién quiere ser realmente.
Entre una extraña colección de personas, hackers y activistas, encuentra algunos verdaderos amigos, e incluso el amor. Pero, ¿podrán detener los terribles actos de la gente que gobierna la ciudad?
Else Heart.Break () es una vuelta de tuerca del juego de aventuras: una historia fantástica ambientada en un mundo totalmente dinámico e interactivo.

Steam

Hackmud

Hackmund es un simulador de hacking multijugador basado en texto para ordenadores personales compatibles con Intel.
En este emocionante videojuego, los jugadores pueden descifrar sistemas protegidos y resolver rompecabezas mientras exploran la abandonada Internet del futuro. Además, pueden escribir scripts para proteger sus ganancias y engañar a otros jugadores.

Steam | Web oficial

TIS-100

En este juego de programación desarrollado por Zachtronics Industries, puedes desarrollar un código de lenguaje ensamblador simulado para realizar ciertas tareas en un ordenador ficticio virtualizado de la década de 1970.

Steam | Web oficial

Pelis

Algorithm

Will es un experto en seguridad informática que trabaja como consultor y hacker independiente en San Francisco.
Su vida da un vuelco cuando es contratado por un hombre que quiere pruebas de la infidelidad de su mujer. En su investigación, descubre un misterioso programa informático del gobierno, un aterrador sistema de identificación y tracking de personas.

23 – Nichts ist so wie es scheint («Nothing is what it seems»)

Hannover, finales de los años ochenta. El huérfano Karl Koch invierte su herencia en un ordenador personal. Al principio lo usa para captar noticias sobre discusiones de teorías conspirativas inspiradas en su novela favorita, “Illuminatus”, de R.A. Wilson, pero pronto Karl y su amigo David empiezan a introducirse en ordenadores del gobierno y del ejército.
Esta apasionante historia real sobre unos jóvenes alemanes, obtuvo reconocimientos a premios importantes dentro de su país de origen.

Johnny Mnemonic

Película de 1995 que tiene a Keanu Reeves como protagonista.
Corre el año 2021 y la mitad de la población sufre de una enfermedad llamada “síndrome de atenuación de los nervios”. Johnny es un mensajero de información, una persona que lleva los datos más importantes del siglo XXI directamente implantados en su cerebro. Su información será muy valiosa para una gran corporación, que no parará hasta dar con él.
A pesar de no haber recibido buenas críticas en su momento, su visionado futurista resulta entretenido.

Who Am I: ningún sistema es seguro

Benjamin se siente invisible, pero esto cambia cuando conoce al carismático Max. Aunque aparentemente no podrían ser más diferentes, ambos comparten el mismo interés: la piratería informática.
Junto con los amigos de Max, forman un grupo subversivo de hackers que desafía al sistema y Benjamin se siente parte de algo por primera vez en su vida.
Pero la cosa se pone seria de repente, cuando el grupo es incluido en la lista de buscados de la policía alemana y la Europol.

Hackers (Piratas Informáticos)

Dade acaba de mudarse con su madre a la ciudad de Nueva York. En su primer día de escuela conocerá a un grupo de jóvenes cuya afición es piratear sistemas informáticos por diversión. Dadee se unirá a ellos, pero todo se complica cuando descubren que están siendo vigilados por las autoridades. Cuando el grupo se entera de la existencia de un plan para liberar un peligroso virus en la Red, todos deberán utilizar sus habilidades informáticas para conseguir pruebas de ello mientras el Servicio Secreto y el malvado genio de los ordenadores que ha creado el virus les pisan los talones.

La Red Social

Película biográfica dirigida por David Fincher, estrenada el 24 de septiembre de 2010, en el Festival de Cine de Nueva York. Esta narra un drama de tribunales, sobre las implicaciones morales del entonces ascendente Mark Zuckerberg (interpretado por Jesse Eisenberg), cuyas peripecias lo encaminaron en la construcción de un imperio billonario, y de cómo alguien poco sociable logró conectar a cientos de millones de personas a través de su creación, Facebook.

La Red

El primer día de sus vacaciones, una programadora de ordenadores recibe un extraño disquet para que lo investigue. Se lo guarda y descubre que posee una clave para acceder al control de las bases de datos protegidas de Estados Unidos. A la vez ve cómo todos los datos de su vida que figuran en archivos informáticos son suprimidos o tergiversados.

Blackhat – Amenaza en la red

Thriller cibernético en el que varios agentes norteamericanos y chinos, con ayuda de un convicto liberado, se unen para detener a un misterioso hacker. Todo comienza cuando los gobiernos de Estados Unidos y China se ven obligados a cooperar por el bien de la seguridad nacional de ambas potencias. El motivo: una fuerte amenaza informática está poniendo en riesgo las vidas y el futuro de la población. Delitos informáticos de alto nivel para los que deberán recurrir a sus mejores agentes de campo si quieren llegar a tiempo para evitar lo peor.

The Matrix

Representa un futuro distópico en el que la humanidad está atrapada sin saberlo dentro de una realidad simulada llamada Matrix, que las máquinas inteligentes han creado para distraer a los humanos mientras usan sus cuerpos como fuente de energía en campos de cultivo.​ Cuando el programador informático Thomas Anderson, bajo el alias de hacker «Neo», descubre la incómoda verdad, se une a una rebelión contra las máquinas junto con otras personas que han sido liberadas de Matrix. Siendo estrenada en los Estados Unidos el 31 de marzo de 1999, es la primera entrega de la franquicia Matrix, de la que derivan (dado su éxito) una serie de videojuegos, cortos animados y cómics, llegando a ser un claro ejemplo del subgénero cyberpunk.

Juegos de guerra

Un joven informático, con una gran habilidad para falsificar notas, entra en una compañía de juegos de ordenador para probarlos y consigue poner en jaque al Departamento de Defensa de los Estados Unidos y provocar la III Guerra Mundial.

Snowden

La épica historia del hombre que en 2013 puso en jaque a los EE.UU. Cuando Edward J. Snowden desveló los documentos del programa de vigilancia mundial secreto de la NSA abrió los ojos del mundo y cerró las puertas de su propio futuro. Se vio obligado a renunciar a su carrera, a su novia de toda la vida y a su patria. ¿Fue un patriota o un traidor?

Series

Eye Candy

Esta serie de televisión estadounidense está basada en una novela y tiene como protagonista a Lindy Sampson, una solitaria hacker que tiene un blog en el que expone todo tipo de cosas: desde planes terroristas hasta presuntos asesinos.
Un día, Lindy se convierte en el blanco de un peligroso acosador cibernético y asesino en serie, que se obsesiona con ella. A partir de entonces, Lindy se sumerge en la investigación policial para capturar al asesino, utilizando su especial habilidad.

Mr. Robot

Esta aclamada serie de cuatro temporadas ha sido nominada durante varios años seguidos tanto a los Globos de Oro como a los Emmy y ha sido destacada por muchos críticos como una de las mejores series de los últimos años.
El protagonista es Elliot Anderson, interpretado por un estupendo Rami Malek. Un brillante programador con problemas para las relaciones sociales que durante el día trabaja como técnico de ciberseguridad y por la noche es un desinteresado justiciero cibernético, que se ve envuelto en una oscura trama.

Devs

Lily es una joven ingeniera informática que decide investigar a la empresa de tecnología para la que trabaja, pues cree que está detrás de la desaparición de su novio.
A medida que avanza la investigación, descubre que la empresa está desarrollando un código que desafía las leyes del espacio y el tiempo.
El director de Ex_Machina firma este hipnótico thriller que habla sobre el uso indiscriminado del Big Data, reflexiona sobre el determinismo, (alegando que ninguno de nuestros actos es libre), y diseña una interesante radiografía sobre las relaciones humanas.

Silicon Valley

Richard es un tímido programador que vive con sus tres únicos amigos y descubren un importante algoritmo que supondrá una batalla con intereses y falsas amistades. Además, una chica se cruza por primera vez en la vida de Richard.