Boston Key Party CTF 2013 – MITM

Boston Key Party CTF 2013 - MITM - task description

Ohne weitere Informationen erhalten wir bei dieser Challenge (MITM) nur eine Textdatei, die folgenden Inhalt besitzt.

message 1:  QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=
encrypted:  THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=
message 2:  RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=
encrypted:  01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=
ciphertext: s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=

Demnach handelt es sich offensichtlich um drei Nachrichten, von denen die ersten beiden in Klar- und Schlüsseltext vorliegen. Die letzte Nachricht (ciphertext) liegt nur in verschlüsselter Form vor, was diese zum primären Ziel der Challenge macht.

Zunächst sehen wir uns die Klartexte der beiden Nachrichten indem wir sie mit BASE64 dekodieren.

rup0rt@lambda:~/BkP2013$ echo "QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=" | base64 -d
AES-256 ECB mode twice, two keys
rup0rt@lambda:~/BkP2013$ echo "RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=" | base64 -d
Each key zero until last 24 bits

Wir erhalten zwei Hinweise:

  • Zum Verschlüsseln der Nachrichten wurde zweifachse AES-256 ECB verwendet
  • Der Schlüssel besteht jeweils aus Nullen – bis auf die letzten drei Zeichen


Die Nachrichten wurden also wie folgt verschlüsselt:

KLARTEXT —> AES-256 ECB (Key1) —> AES-256 ECB (Key2) —> CIPHERTEXT

Da die Schlüssel (Key1, Key2) größtenteils Null sind, können wir über einen Brute Force vorgehen. Dabei verschlüsseln wir den Klartext und entschlüsseln den Ciphertext mit allen Möglichkeiten. Im Ergebnis sollte ein Schlüsseltext vorkommen, der nach Ent- und Verschlüsselung gleich ist.

KLARTEXT —> AES (Key1) === ????? === AES (Key2) <— CIPHERTEXT

Da dies im Versuch mit einem einzigen Programm sehr sehr (sehr) viel Zeit in Anspruch genommen hat, habe ich mich entschlossen, auf ein Zwischenspeichern der Daten auszuweichen.

Folgendes Python-Skript verschlüsselt dabei den ersten Klartext:

#!/usr/bin/python

import base64
from Crypto.Cipher import AES

# AES-256 ECB mode twice, two keys
# Each key zero until last 24 bits

msg1 = base64.b64decode("QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=")
enc1 = base64.b64decode("THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=")
msg2 = base64.b64decode("RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=")
enc2 = base64.b64decode("01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=")
ciph = base64.b64decode("s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=")

# one round is enough, maybe it saves time ;)   
msg1 = msg1[:16]
enc1 = enc1[:16]

keybase = "\x00" * 29

file=open("middle.txt", "w")

for a in range(256):
  print a
  for b in range(256):
    for c in range(256):

      key = keybase + chr(a) + chr(b) + chr(c)
      obj=AES.new(key, AES.MODE_ECB)
      middle=obj.encrypt(msg1)

      file.write(middle.encode('hex') + "\n")

Der Text wird dabei mit jedem möglichen Schlüssel (wobei 29 Bytes Null sind) verschlüsselt und das Ergebnis in der Datei “middle.txt” abgelegt. (Der Schlüssel muss insgesamt 32 Bytes lang sein, da wir mit AES 256(!) arbeiten sollen.)

Nach Ausführung ist eine circa 500 Megabytes große Datei entstanden. An diese fügen wir mit dem folgenden Python-Skript die Ergebnisse der Entschlüsselung des Ciphertextes an:

#!/usr/bin/python

import base64
from Crypto.Cipher import AES

# AES-256 ECB mode twice, two keys
# Each key zero until last 24 bits

msg1 = base64.b64decode("QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=")
enc1 = base64.b64decode("THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=")
msg2 = base64.b64decode("RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=")
enc2 = base64.b64decode("01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=")
ciph = base64.b64decode("s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=")

# one round is enough, maybe it saves time ;)
msg1 = msg1[:16]
enc1 = enc1[:16]

keybase = "\x00" * 29

file=open("middle.txt", "a")

for a in range(256):
  print a
  for b in range(256):
    for c in range(256):

      key = keybase + chr(a) + chr(b) + chr(c)
      obj=AES.new(key, AES.MODE_ECB)
      middle=obj.decrypt(enc1)

      file.write(middle.encode('hex') + "\n")

Nachdem aus dieses Ausgeführt wurde, ist die Datei “middle.txt” auf circa 1.1 Gigabytes angewachsen und enthält nun alle Ergebnisse von Ver- und Entschlüsselung des Klar- bzw. Schlüsseltextes. Dabei muss eine Zeichenfolge doppelt vorkommen, nämlich genau das Ergebnis zwischen beiden Verschlüsselungen.

Um dieses zu erhalten nutzen wir simple Dateioperationen.

rup0rt@lambda:~/BkP2013$ sort middle.txt > middle2.txt 
rup0rt@lambda:~/BkP2013$ uniq -d middle2.txt 
a92dbc3989cb7f805f0f6dd6edb9f8b9

Wir sortieren die Datei zunächst mittels “sort”, da dies zur Bestimmung doppelter Einträge erforderlich ist. Anschließend nutzen wir “uniq” um mit “-d” die doppelten Einträge zu erhalten. Die Ausgabe ist das mittlere Schlüsselergebnis.

Nun können wir die beiden AES-Schlüssel direkt berechnen. Dazu dient folgendes Python-Skript:

#!/usr/bin/python

import base64
from Crypto.Cipher import AES

# AES-256 ECB mode twice, two keys
# Each key zero until last 24 bits

msg1 = base64.b64decode("QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=")
enc1 = base64.b64decode("THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=")
msg2 = base64.b64decode("RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=")
enc2 = base64.b64decode("01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=")
ciph = base64.b64decode("s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=")

# one round is enough, maybe it saves time ;)
msg1 = msg1[:16]
enc1 = enc1[:16]

res = "a92dbc3989cb7f805f0f6dd6edb9f8b9".decode('hex')

keybase = "\x00" * 29

for a in range(256):
  print a
  for b in range(256):
    for c in range(256):

      key = keybase + chr(a) + chr(b) + chr(c)
      obj=AES.new(key, AES.MODE_ECB)
      middle=obj.encrypt(msg1)

      if (middle == res):
        print key.encode('hex')

Als Ausgabe erhalten wir:

00000000000000000000000000000000000000000000000000000000009ae807

Analog können wir nun durch Anpassung des Skriptes auch den zweiten Schlüssel bestimmen.

0000000000000000000000000000000000000000000000000000000000ff3f45

Anschließend benötigen wir nun noch ein Skript zur Entschlüsselung:

#!/usr/bin/python

import base64
from Crypto.Cipher import AES

msg1 = base64.b64decode("QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=")
enc1 = base64.b64decode("THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=")
msg2 = base64.b64decode("RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=")
enc2 = base64.b64decode("01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=")
ciph = base64.b64decode("s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=")

key1 = "00000000000000000000000000000000000000000000000000000000009ae807".decode('hex')
key2 = "0000000000000000000000000000000000000000000000000000000000ff3f45".decode('hex')

obj1=AES.new(key2, AES.MODE_ECB)
obj2=AES.new(key1, AES.MODE_ECB)

middle=obj1.decrypt(ciph)
res=obj2.decrypt(middle)

print res

Bei Ausführung erhalten wir:

rup0rt@lambda:~/BkP2013$ ./decrypt.py 
This time I didn't include sol'n

Die Lösung lautet somit “This time I didn’t include sol’n“.

One thought on “Boston Key Party CTF 2013 – MITM

Leave a Reply

Your email address will not be published.