El tema era como volver a darle permisos de ejecución si le sacamos estos permisos al chmod. En los comentaros se publicaron respuestas relacionadas con usar lenguajes de scripting (en el enunciado decia que no se podía compilar) pero la idea era ser un poco más creativos.
La primer solución que encontre fue:
cp otro_ejecutable xxx
cat /bin/chmod > xxx
mv xxx /bin/chmod
Lo interesante de esto es que los permisos de ejecucion de la copia original se mantienen al 'llenar' el archivo con otro contenido.
Isart, quien me propuso el acertijo, encontró otra un poco mas simple que es:
cp otro_ejecutable xxx
cp --no-preserve=mode /bin/chmod xxx
mv xxx /bin/chmod
Yo sabía que tenía que haber otra forma de ejecutar un archivo a la fuerza, y me encontré con esto:
/lib/ld-linux.so.2 /bin/chmod
Si lo dejamos estrictamente en el enunciado del acertijo, cualquiera de las tres sirve para cambiar los permisos de un archivo sin que el chmod sea ejecutable, pero la última me llamo mucho la atención porque incluso la puedo usar como un usuario normal sin ningún privilegio.
¿Puede ser esto una falla de seguridad?
No creo que sea demasiado grave porque no encontre la forma de cambiar el propietario de un archivo a root con un usuario común, pero hay que tener en cuenta que un usuario comun puede ejecutar cosas sin importar los permisos que tengan los archivos (bueno, por lo menos tiene que tener lectura)