- A Genuine Counterfeit - (Hardware 350pts)
- Can't See You - (Misc 200pts)
- md5(coll) - (Misc 200pts)
- Random Tea Party - (Crypto 300pts)
- Text rendering is hard - (Misc 200pts)
Last active
December 21, 2022 07:41
-
-
Save shinmai/a1cace785f1c433b614f17eec715d2b1 to your computer and use it in GitHub Desktop.
INTENT CTF 2022 Writeups
Our product is being counterfeited by someone on the black market.
It is your goal to find out how they are doing it.
The analysis done by our hardware engineers shows that they swapped out the 24LC256 EEPROM chip for a custom chip but the engineers still don't understand how the attack works. When using the fake chip with our software, the software says the product is genuine but it is clearly not.
We have provided you a simulation of the product at this link with a programmable replacement for the 24LC256 EEPROM. You can edit the code for the EEPROM (eeprom-24lc256.chip.c) in order to investigate and attack the product software. The code in sketch.ino is similar to the actual product code but changing it will not change the simulation.
Find how the counterfeiters are tricking our software and implement a POC showing us how it is done. The flag will reveal itself when you are successful.
Navigating to the Wokwi URL there's a basic circuit with an ESP32 board (ESP32-S2-MIN-1, specifically) hooked up to an SSD1306 OLED breakout board and a custom 24LC256 "simulator" breakout, backed by code from eeprom-24lc256.chip.c:
// 24lc256 Wokwi Custom Chip - For information and examples see:
// https://link.wokwi.com/custom-chips-alpha
//
// SPDX-License-Identifier: MIT
// Copyright (C) 2022 Benjamin Meisels / wokwi.com
// !!!!!!!!!!!!!!!!!
// Edit this file
// !!!!!!!!!!!!!!!!!
#include "wokwi-api.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define EEPROM_SIZE 0x8000
const int BASE_ADDRESS = 0x50;
static const char G_AUTHENTICATION_MARKER[] = "INTENT";
static const size_t G_AUTHENTICATION_MARKER_SIZE = 7;
static const uint16_t G_AUTHENTICATION_MARKER_LOCATION = 0x4000;
typedef enum {
IDLE,
ADDRESS_1,
DATA
} eeprom_state_t;
typedef struct {
eeprom_state_t state;
pin_t pin_a0;
pin_t pin_a1;
pin_t pin_a2;
pin_t pin_wp;
uint16_t address_register;
uint8_t mem[EEPROM_SIZE];
uint8_t byte_counter;
} chip_state_t;
static bool on_i2c_connect(void *user_data, uint32_t address, bool connect);
static uint8_t on_i2c_read(void *user_data);
static bool on_i2c_write(void *user_data, uint8_t data);
static void on_i2c_disconnect(void *user_data);
static uint8_t get_addr(chip_state_t *chip) {
uint8_t address = BASE_ADDRESS;
address |= pin_read(chip->pin_a2) << 2;
address |= pin_read(chip->pin_a1) << 1;
address |= pin_read(chip->pin_a0);
return address;
}
void chip_init(void) {
chip_state_t *chip = malloc(sizeof(chip_state_t));
uint8_t address = get_addr(chip);
chip->pin_a0 = pin_init("A0", INPUT);
chip->pin_a1 = pin_init("A1", INPUT);
chip->pin_a2 = pin_init("A2", INPUT);
chip->pin_wp = pin_init("WP", INPUT);
chip->address_register = 0;
memset(chip->mem, 0, EEPROM_SIZE);
chip->state = IDLE;
chip->byte_counter = 0;
const i2c_config_t i2c_config = {
.user_data = chip,
.address = address,
.scl = pin_init("SCL", INPUT),
.sda = pin_init("SDA", INPUT),
.connect = on_i2c_connect,
.read = on_i2c_read,
.write = on_i2c_write,
.disconnect = on_i2c_disconnect, // Optional
};
i2c_init(&i2c_config);
memcpy(
chip->mem + G_AUTHENTICATION_MARKER_LOCATION,
G_AUTHENTICATION_MARKER,
G_AUTHENTICATION_MARKER_SIZE);
// The following message will appear in the browser's DevTools console:
printf("Hello from 24lc256 at address %x \n", address);
}
bool on_i2c_connect(void *user_data, uint32_t address, bool connect) {
return true; /* Ack */
}
uint8_t on_i2c_read(void *user_data) {
static bool double_fetch = false;
chip_state_t *chip = user_data;
uint8_t data = chip->mem[chip->address_register];
chip->address_register = (chip->address_register + 1) & 0x7ffff;
return data;
}
bool on_i2c_write(void *user_data, uint8_t data) {
chip_state_t *chip = user_data;
switch(chip->state)
{
case IDLE:
chip->address_register = (data & 0x7f) << 8;
chip->state = ADDRESS_1;
break;
case ADDRESS_1:
chip->address_register |= data;
chip->state = DATA;
break;
case DATA:
if (chip->byte_counter > 63) {
return false;
}
chip->mem[chip->address_register] = data;
chip->address_register = (chip->address_register + 1) & 0x7ffff;
break;
default:
printf("error");
break;
}
return true; // Ack
}
void on_i2c_disconnect(void *user_data) {
chip_state_t *chip = user_data;
chip->state = IDLE;
}There's also a sketch.ino file that is similar to the code running on the ESP32, but not identical, and editing the file won't change the code running on the board in the simulator.
// SPDX-License-Identifier: MIT
// Copyright (C) 2022 Benjamin Meisels
// !!!!!!!!!!!!!!!!!
// This isn't the code running so don't try and change it
// !!!!!!!!!!!!!!!!!
#include "mbedtls/md.h"
#include <cstring>
#include <stdio.h>
#include <Wire.h>
#include <U8g2lib.h>
#define EEPROM_I2C_ADDRESS 0x50
#define SHA256_DIGEST_SIZE 32
static const char G_AUTHENTICATION_MARKER[] = "INTENT";
static const size_t G_AUTHENTICATION_MARKER_SIZE = 7;
static const byte G_EXPECTED_HASH_RESULT[SHA256_DIGEST_SIZE] = { // "INTENT"
0xc6, 0xa5, 0x99, 0x4d,
0xde, 0xd4, 0xe6, 0xa7,
0x7c, 0x8a, 0x95, 0x91,
0x62, 0x1a, 0xa1, 0xbd,
0x92, 0x17, 0xa4, 0x3b,
0x02, 0x9d, 0xbd, 0x7f,
0xaf, 0x8b, 0x2a, 0x16,
0xe9, 0xb6, 0x81, 0xc1
};
U8X8_SSD1306_128X64_NONAME_HW_I2C display(U8X8_PIN_NONE);
bool is_device_available(uint8_t address)
{
Wire.beginTransmission(address);
uint8_t error = Wire.endTransmission();
return (error == 0);
}
void wait_for_device(uint8_t i2c_device_address) {
while(!is_device_available(i2c_device_address));
}
void eeprom_write_byte(uint8_t i2c_device_address, uint16_t eeprom_data_address, uint8_t data) {
// left out for brevity
}
byte eeprom_read_byte(uint8_t i2c_device_address, uint16_t eeprom_data_address) {
// left out for brevity
}
String eeprom_read_string(uint16_t eeprom_data_address, unsigned int size) {
// left out for brevity
}
bool SHA1_verify(unsigned char * data, size_t data_size) {
// left out for brevity
}
void setup()
{
Wire.begin();
Serial.begin(9600);
while (!Serial);
if (!is_device_available(EEPROM_I2C_ADDRESS))
{
printf("No device was found\n");
while(true);
}
display.begin();
display.setPowerSave(0);
display.clearDisplay();
display.setCursor(0,0);
display.setFont(u8x8_font_pxplusibmcgathin_f);
String authentication_marker = eeprom_read_string(0x4000, G_AUTHENTICATION_MARKER_SIZE);
Serial.println("- Reading authentication marker");
Serial.println(authentication_marker);
byte authentication_marker_buffer[G_AUTHENTICATION_MARKER_SIZE] = {'\0'};
authentication_marker.getBytes(authentication_marker_buffer, G_AUTHENTICATION_MARKER_SIZE);
Serial.println("- Verifying authentication marker");
bool verified = SHA1_verify(authentication_marker_buffer, G_AUTHENTICATION_MARKER_SIZE);
authentication_marker = eeprom_read_string(0x4000, G_AUTHENTICATION_MARKER_SIZE);
Serial.println("- Reading authentication marker");
Serial.println(authentication_marker);
display.setCursor(0,0);
display.print(authentication_marker);
if (verified) {
display.setCursor(0,3);
display.print("Genuine!");
if (authentication_marker != G_AUTHENTICATION_MARKER) {
Serial.println("- Flag Unlocked");
// Censored flag.
// The real flag will be printed when you are successful.
Serial.println("INTENT{PLACEHOLDER}");
}
} else {
display.setCursor(0,3);
display.print("Counterfit!");
}
}
void loop()
{
delay(1000);Running the simulation, the OLED display shows the text "INTENT Genuine!" and there's the following log output is produced
- Reading authentication marker
INTENT
- Verifying authentication marker
- Verification successful
- Reading authentication marker
INTENT
Reading through the Arduino code, it seems that some bytes are read from the EEPROM, an SHA256 hash is produced and compared to an expected result, and the process is repeated to verify.
Just changing the authentication marker being stored into the EEPROM simulator during initialisation (and subsequently returned to the ESP32) will result in an the OLED displaying "Counterfit!" and the log complaining about hash verification failing.
To get the flag we need to pass the first verification, but fail the second one. This can be easily done buy amending the on_ic2_read function, we've alredy bene provided with a handy static boolean variable for it, too.
The modified function could be something like this
uint8_t on_i2c_read(void *user_data) {
static bool double_fetch = false;
chip_state_t *chip = user_data;
if(double_fetch) chip->address_register -= 0x1000;
if(chip->address_register == 0x4006) {
double_fetch = true;
}
uint8_t data = chip->mem[chip->address_register];
chip->address_register = (chip->address_register + 1) & 0x7ffff;
return data;
}Basically we check the read address, and if we're returning the last byte of the authentication marker, we set the boolean to true. On the next read from the chip, we substract 0x1000 from the address requested and return the value in memory at the modified address instead.
This results in "Genuine!" being printed on the OLED, and "Flag Unlocked" in the log.
It's too dark in here, can you help Alice find her way out?
docker run -it g3rzi/rabbit_hole bash
Instead of running the container, I downloaded a frozen image from Docker Hub, untarred it to a folder and began examining.
Interesting files mentioned in the container config: /home/message and /tmp/Wonderland.
/home/message contains the following:
| ,
|\ //
|\\ //(
| \\ // '
' \\ // /
\ )\(( /
)` `/
/ __ \
/ (_O) \
/ \________
_.(_) ) /
(__, / /
\ / /
\_______/ (
\ / \
\ / \
\/ \
/ )
/ /
/ _ o__ /
( (_) //\,\ (
\ ``~---~` )
\ \ /
\ \ /
\ \ /
\____/ \_______/
------------------------------------------------
"...she found herself falling down a very deep well.
Either the well was very deep, or she fell very slowly,
for she had plenty of time as she went down to look about her and to wonder what was going to happen next.
First, she tried to look down and make out what she was coming to, but �[92;40mit was too dark to see anything�[0;0m."
file Wonderland reveals it's a tarball: Wonderland: POSIX tar archive
Untarring it, it looks like another frozen Docker image. Again the entry point cats /home/msg but this time we have a LOT of filesystem layers, almost all with just one file: door which contains a single byte.
The only two other layers are the base filesystem for the image, and the one that houses /home/message.
This time it contains:
__________
| __ __ |
| | || | |
| | || | |
| |__||__| |
| __ __()|
| | || | |
| | || | |
| | || | |
| | || | |
| |__||__| |
|__________|
Oh, now she can see! But what is this place?
"There were doors all round the hall, but they were all locked;
and when Alice had been all the way down one side and up the other,
trying every door, she walked sadly down the middle,
wondering how she was ever to get out again.
Suddenly she came upon a little three-legged table,
all made of solid glass; there was nothing on it except a tiny golden key,
and Alice’s first thought was that it might belong to one of the doors of the hall;
but, alas! either the locks were too large, or the key was too small,
but at any rate it would not open any of them. However, on the second time round,
she came upon a low curtain she had not noticed before,
and behind it was a little door about fifteen inches high: she tried the little golden key in the lock,
and to her great delight it fitted!"
Clearly the answer is in the doors, and it's just about ordering the bytes within. To consolidate this, I decided to extract all the door files, rename them based on their layer to differentiate them and move them to the same place.
I did this with a quick&dirty zsh oneliner for d in */; do cd "$d"; tar xf layer.tar door; mv door "door_$(basename $d)"; cd ..; mv "$d/door_$(basename $d)" doors/; done.
Examining the bytes, it looks like a base64 string, but we need to figure out a correct order for the individual characters. I tried alphabetical order with no success, but my second idea - the order from the config JSON - got me SU5URU5Ue2FfbDE3N2wzX2cwbGQzbl9rM3lfZjByX2FfbDE3N2wzX2QwMHJ9 which decodes to INTENT{a_l177l3_g0ld3n_k3y_f0r_a_l177l3_d00r}, yay!
A picture is worth a thousand words, and a flag too.
We're also provided the source code for the server application:
from socket import timeout
from tkinter.tix import TEXT
from flask import Flask, jsonify, make_response, request, render_template, url_for
import os
import sys
import io
import hashlib
import requests
import tempfile
import subprocess
from PIL import Image, ImageChops, ImageOps
app = Flask(__name__)
FLAG = r"INTENT{flag_goes_here}"
TEXT_SEARCH = "INTENT, give me the flag"
def save_image(im):
if im.format == "GIF":
final_image = im.convert("1")
for frame_num in range(im.n_frames):
im.seek(frame_num)
final_image = ImageChops.logical_and(final_image, im.convert("1"))
im = final_image
else:
im = im.convert("1")
temp_file_path = tempfile.NamedTemporaryFile(suffix='.jpg').name
im = im.resize((im.size[0]*4, im.size[1]*4), Image.ANTIALIAS)
im.save(temp_file_path)
return temp_file_path
@app.route('/')
def index():
img_url = request.args.get("imgurl", "")
if img_url == "":
return render_template('index.html')
else:
out_text = ""
try:
resp = requests.get(img_url, timeout=10, stream=True, verify=False)
img_content = resp.raw.read(int(1024 * 1024 * 0.2))
img_pil = Image.open(io.BytesIO(img_content))
md5_str = hashlib.md5(img_content).hexdigest()
out_text += f"[-] Got {len(img_content)} bytes for image type '{img_pil.format}' with MD5 hash: {md5_str}<br>"
saved_jpg_path = save_image(img_pil)
process = subprocess.Popen(["tesseract", saved_jpg_path, "stdout"], stdout=subprocess.PIPE,
stderr=subprocess.DEVNULL)
image_text = process.stdout.read().decode()
img_processing = f"OCR SAYS: {image_text}"
if not(TEXT_SEARCH.encode().lower() in img_content.lower() and \
TEXT_SEARCH in image_text):
out_text += f"You should include the following string in your GIF -> {TEXT_SEARCH}<br>"
elif md5_str in image_text:
out_text += f"OK take it!: {FLAG}<br>"
else:
out_text += ":((((<br>"
os.remove(saved_jpg_path)
return render_template("index.html", run_results=out_text, img_processing=img_processing)
except Exception as e:
return render_template("index.html", img_processing=f":(((((((((((((((((((")
def main():
with app.app_context():
app.run(host="0.0.0.0", debug=True)
if '__main__' == __name__:
main()Opening the provided URL greets us with a very plain website with a single text-box labeled "Img url" and a submit button:
Reading through the code, the server:
- Downloads the submitted URL
- Reads a maximum of 0.2MB of image data
- Calculates an MD5 hash for the loaded data
- Saves the image data to a JPEG file using Pillow
- Passes the saved JPEG to the tesseract OCR and stores the recognised text
- Checks the image data contains the plaintext "INTENT, give me the flag"
- Checks the OCR output contains the same text
- Checks the OCR output also contains the previously calculated MD5 hash
So we need to produce an image file that contains the phrase "INTENT, give me the flag" both in it's byte content, and as written text on the actual image, as well as it's own MD5 hash written in the image.
This kind of file is known as a hashquine. The website also gives us a hint as to how to approach this, the title is "- Welcome to the impossible GIF -".
GIF is a good candidate because it's based on blocks, which can, in turn, contain several sub-blocks of arbritary length, and one of these block types is a comment which gets ignored during decoding, which means that it's possible to align each block with MD5's 64byte/512bit blocks.
Furthermore, animated GIFs are basically just a big GIF, and then a bunch of other GIFs in the same file, each of which has a position and a delay value for when it is to be drawn at that location.
This coupled with the fact that MD5 is broken in the sense that given a prefix p, it's trivial to find a and b such that md5(p+a) == md5(p+b) enables this task to be viable.
First we make some GIFs: a base GIF we use as a starting point and that contains the text "INTENT, give me the flag" (w/ room for the hash) and the same text in a comment block, and 15 small GIFs, one for each possible hexadecimal digit.
A full explanation of the GIF file-format is beyond the scope of this writeup, but the tl;dr is blocks contain sub-blocks, which are stored as length+data and the previously opened block ends when the first 0 length sub-block is encountered. So a comment block (0x21fe) with a the comment "HI" would be \x21\xfe\x02HI\x00 : the identifier for a comment \x21\xfe + length of the sub-block \x02 + 2 bytes of comment data HI + closing zero length sub-block \x00.
The basic workflow for constructing our GIF is:
- Add a comment block to the end of the current 64 byte block (or append it to the header of the "main" GIF if we're just starting) with the first sub-block pointing some bytes into the next block
- for each hex digit find an MD5 collision between the current 64 byte block and the digit displayed at the current X position
- compare the byte value at the location the previously placed comment sub-block's starting byte points to, and store the collision with the lower value and the length of the prefix used to generate the collisions
- take other collision, append it to the GIF, then pad enough bytes to make it a valid comment block ending at the location indicated by the byte value at the location the previously placed comment sub-block's starting byte points to from the collision stored in step 3
- add a null byte to the GIF to terminate the comment we opened in step 1.
- append the current hex digit frame to the file
- start a new comment block, and pad the GIF to the next 64 byte border
- increment X position by the width of one hex digit
- repeat 1-8 for all 32 digits of an MD5 hash - we now have a GIF file with the base image, with 512 animated frames, each of which is currently contained inside a comment
- calculate the MD5 hash of the resulting GIF
- loop over each digit of the MD5 hash and for each digit take the longer collision appended into the file at step 4. for the character that should be shown there, and replace it with the shorter collision stored in step 3, effectively "uncommenting" it.
- now we have a GIF file with the exact same MD5 hash as in step 10, but with 32 animation frames, each adding one of the digits of the MD5 hash to the image
I used a Python script for the logic, and md5_fastcoll from Marc Stevens' HashClash to generate the collisions.
On my fairly modest PC the process takes about 40 minutes. This is a wholly single-core performance task, since md5_fastcoll is single-threaded and the collisions need to obviously be generated sequentially.
import struct
from hashlib import md5
from tempfile import TemporaryDirectory
from subprocess import run as run_subp
from awesome_progress_bar import ProgressBar
class PadBytes:
def __init__(self):
self.i = -1
def next(self):
self.i += 1
return b'\xde\xad\xbe\xef'[self.i%4].to_bytes(1,'little')
padding = PadBytes()
def loadgif(filename):
with open(f'{filename}', 'rb') as gif_fd:
giffile = {'h': gif_fd.read(61), 'gce': gif_fd.read(8), 'id': gif_fd.read(10), 'data': gif_fd.read(1)}
while True:
giffile['data'] += gif_fd.read(1)
if giffile['data'][-1] == 0: break
giffile['data'] += gif_fd.read(giffile['data'][-1])
return giffile
base = loadgif('base.gif')
chars = {}
for char in '0123456789abcdef':
blocks = loadgif(f'{char}.gif')
chars[int(char, 16)] = blocks['data']
bar = ProgressBar(512, bar_length=50, prefix='Colliding', spinner_type='db', use_eta=True)
gce = base['gce']
hashblocks = {}
gif = base['h'] + b'\x21\xfe\x18INTENT, give me the flag\x00' + gce + base['id'] + base['data'] + b'\x21\xfe'
left = 0
for hash_digit in range(32):
left += 22
imdesc = b'\x2c%s\x00' % struct.pack('<HHHH', left, 5, 22, 30)
for char in range(16):
c_gif = gce + imdesc + chars[char]
align = 64 - (len(gif) % 64)
gif += bytes([align + 122])
for _ in range (align - 1): gif += padding.next()
pad_eob = missing = -1
while pad_eob < 0 or missing < 0:
with TemporaryDirectory() as tmp_path:
p_fn = f'{tmp_path}/p'
a_fn = f'{tmp_path}/a'
b_fn = f'{tmp_path}/b'
with open(p_fn, 'wb') as f: f.write(gif)
run_subp(['md5_fastcoll', '-p', p_fn, '-o', a_fn, b_fn], capture_output=True)
with open(a_fn, 'rb') as f: coll_a = f.read()[len(gif):]
with open(b_fn, 'rb') as f: coll_b = f.read()[len(gif):]
if(coll_a[123] == coll_b[123]): continue
image, comment = (coll_a, coll_b) if coll_a[123] < coll_b[123] else (coll_b, coll_a)
pad_eoc = image[123] - 4
missing = comment[123] - 4
pad_eob = missing - pad_eoc - len(c_gif) - 4
hashblocks[hash_digit, char] = (len(gif), image)
gif += comment
for _ in range (pad_eoc): gif += padding.next()
gif += b'\x00' + c_gif + b'\x21\xfe' + bytes([pad_eob])
for _ in range (pad_eob): gif += padding.next()
bar.iter(f' Collision {hash_digit*16+char+1}')
gif+= b'\x00\x3b'
for i, c in enumerate(md5(gif).hexdigest()):
coll_pos, coll = hashblocks[i, int(c, 16)]
gif = (gif[:coll_pos] + coll + gif[coll_pos + len(coll):])
open('output2.gif', 'wb').write(gif)Here's an example output:
Host the resulting GIF somewhere that doesn't mangle your uploads, feed the URL to the challenge website and with a bit of luck (OCR is a bit hit & miss at the best of times), you should get the flag:
You are sitting in the middle of the Tea party, and the Random Hatter has one new riddle to ask you.
Can you solve the unsolvable and unpredictable riddle?
We are provided a 5.6MB Windows executable RandomTeaParty.exe as well.
The executable has a very conspicuous Python icon, and opening it in a hex editor shows a lot of Python related strings. Tossing the file at binwalkreveals dozens o Zlib compressed blocks.
We can extract these manually, and we'll find all the libraries needed to run Python code, a bunch of Python libraries and the program's "main" code as a .pyc file, but there's a tool just for this job: pyinstxtractor
We command python pyinstxtractor.py RandomTeaParty.exe and all our files are extracted in a subdirectory called RandomTeaParty.exe_extracted.
Inside we find mostly DLL files, some .pyd files, and also the meat and potatoes of this task: RandomTeaParty.pyc.
To finally get to solving the actual crypto task, lets decompile it back to Python code: decompyle3 RandomTeaParty.pyc > RandomTeaParty.py.
RandomTeaParty.py:
# decompyle3 version 3.9.0
# Python bytecode version base 3.7.0 (3394)
# Decompiled from: Python 3.10.8 (main, Nov 4 2022, 09:21:25) [GCC 12.2.0]
# Embedded file name: RandomTeaParty.py
import argparse, hashlib
class LCG(object):
def __init__(self, seed, p, a, c):
self.p = p
self.seed = seed
self.a = a
self.c = c
def next(self):
self.seed = (self.a * self.seed + self.c) % self.p
return self.seed
encrypted_secret = [ 365568652, 495714267, 1358608273, 1529160966, 822619654, 1706526019, 391137561, 2076472716, 1764278540, 734807837, 2073337261, 736054556, 2123830086, 681801730, 1070017952, 1709297869, 1046640222, 667366781, 58152428, 310139563, 640852461, 85665152, 1240055427, 1907395889, 695586467, 750761920, 1239683690, 1137452295, 1250976842, 808635844, 1000374841, 777628850, 1057483327, 89023171, 121647634, 837428821, 1438310703, 548816510, 558030123, 788206776, 562475864, 634461615, 834403405, 1433232113, 209086350, 1784777833, 258061229, 1469928947, 2076352416, 252437757, 598438083, 1401155011 ]
def print_hint():
print('"Indeed, Perhaps you might want one, but its not going to be as easy as looking at the code!" said the March Hare')
super_hard_to_find_hint_that_is_definitely_not_here = 'Vm10V1YxUXhUa1ppUldocFUwaENTMVZ1Y0VaTlZrNVdXa2RHYUZJeFNqQlVNV2h6WVVaa1IxTnVUbFJXVjJoTVdWVmtTMlJHVm5WWGJXeFdUVVphZFZkV1dtOVZNbFp5WWtWb1ZtSllhR2haYkdRMFRWWnNWMkZHVG1wTmJGcFZWVmR3UjJGWFNsWmpSRlpZWWtkU1NGa3llSE5YUms1MVZHMUdWazFHVlRVPQ=='
def main():
parser = argparse.ArgumentParser('Random Tea Party', description='Welcome to the random tea party! hosted by yours truly, the Random Hatter!')
parser.add_argument('--can-i-get-a-hint-please', default=False, action='store_true', help='There is no shame in asking for some help!')
args = parser.parse_args()
if args.can_i_get_a_hint_please:
print_hint()
return
print("'I haven't the slightest idea,' said the Random Hatter.")
print("'Nor I,' said the March Hare. After a long pause the Random Hatter decided to challange me with a second riddle")
print(f"'I have {len(encrypted_secret)} favorite random numbers, can you guess them all?' he said, with a sinister smile on his face")
secret = []
for i, enc in enumerate(encrypted_secret):
guess = int(input(f"My #{i} favorite number is? "))
decrypted = chr((enc ^ guess) % 255)
if not i == 0 or decrypted == 'd':
if not i == 1 or decrypted == 'i':
if not i == 2 or decrypted == 'd':
if not i == 3 or decrypted == ' ':
if not i == 4 or decrypted == 'y':
if i == 5:
if decrypted == 'o':
if not (i == 6 and decrypted == 'u'):
print('Wrong!')
return
secret.append(decrypted)
if hashlib.sha256(''.join(secret).encode()).hexdigest() == '0ecc299684a6063fabd161ac4ee3652195f567c799fccf44c09bf41e97d58288':
print('Impressive, ' + ''.join(secret))
else:
print('Wrong!')
if __name__ == '__main__':
main()
# okay decompiling RandomTeaParty.pycThe script prompts the user for 52 numbers, XORs them with the values in the array and stores the result mod 255 into an array.
It then joins the array into a string, takes the SHA256 hash of the string and compares it to a stored expected value.
There are also individual tests for the first 7 bytes which leak us the expected result of the XOR % modulus equation.
If you know what LCGs are, this task is starting to become clearer, especially considering the name. A Linear Congruential Generator is a PRNG algorithm, where if you initialise it with the same seed, multiplier, increment and modulus, it will always generate the same sequence of values. What we need to do is take the LCG implementation provided, and somehow (*cough*bruteforce*cough*) figure out the correct values.
For details on how to achieve this, I spent sime time researching LCGs and how to attack them. This paper from 2004 by Haldir from Reverse Engineering Team was one of the best resources I found.
I'm also lucky enough to know a few quite briliant scientists who I bugged with random elementary math questions.
The LCG output
So if
Therefore
That's a lot of math for an engineer who barely passed their mandatory math, so let's verify in SageMath:
Due to some number theory stuff I don't understand, taking several random multiples of a number, and finding their greatest common divisor has a rapidly increasing probability that that divisor is the original number.
Let's take the first 7 values from the encrpted_secret array, XOR them with "did you" to get the first 7 values the LCG spat out when the array was originally generated.
To find the modulo p for our seven XOR'd bytes as an array in variable s we can:
diffs = [s[i+1] - s[i] for i in range(len(s)-1)]
t = [diffs[i+2]*diffs[i] - diffs[i+1]*diffs[i+1] for i in range(len(diffs)-2)]
p = functools.reduce(gcd, t)Now that we have the modulo, we need to get the multiplier a.
More math 🤦♀️:
Therefore
So for our seven XOR'd bytes as an array in variable s and the modulo on variable p we can just:
a = (s[2] - s[1]) * modinv(s[1] - s[0], p)There are a lot of ways to get the modinv function, I opted to import the egcd PyPi package for a ready-to-use and allegedly efficient extended Euclidean algorithm implementation and writing my own: modinv = lambda a, b : egcd(a, b)[1] % b
Now it's trivial to get the increment c, for our seven XOR'd bytes as an array in variable s and the modulo on variable p and the multiplier variable a:
c = (s[1] - s[0]*a) % pWe're only missing the seed, and we're going to just straight up brute-force it. No math! YEAH!
To get the seed seed for our seven XOR'd bytes as an array in variable s, the modulo on variable p, the multiplier variable a and the increment variable c:
for seed in range(2**32):
l = LCG(seed, p, a, c)
if all(s==l.next() for s in s):
break # found the seedPutting that all together and adding in the decoding of the secret message we have the following finished script:
from math import gcd
from functools import reduce
from hashlib import sha256
from RandomTeaParty import encrypted_secret, LCG
from egcd import egcd
modinv = lambda a, b : egcd(a, b)[1] % b
def brute_seed(s, p, a, c):
for seed in range(2**32):
secret = []
l = LCG(seed, p, a, c)
if all(s==l.next() for s in s):
return(seed, p, a, c)
brute_c = lambda s, p, a : brute_seed(s, p, a, (s[1] - s[0]*a) % p)
brute_a = lambda s, p: brute_c(s, p, (s[2] - s[1]) * modinv(s[1] - s[0], p) )
def brute_p(s):
diffs = [s[i+1] - s[i] for i in range(len(s)-1)]
t = [diffs[i+2]*diffs[i] - diffs[i+1]*diffs[i+1] for i in range(len(diffs)-2)]
return brute_a(s, reduce(gcd, t))
seed, p, a, c = brute_p([x[1]^ord(x[0]) for x in zip("did you", encrypted_secret)])
lgc = LCG(seed, p, a, c)
flag = "".join([chr((e^lgc.next())%255) for e in encrypted_secret])
assert sha256(flag.encode()).hexdigest() == '0ecc299684a6063fabd161ac4ee3652195f567c799fccf44c09bf41e97d58288'
print(flag)Which gets us the flag in about 3 seconds (if running on pypy, cpython takes a solid half-a-minute 😅):
did you know that at INTENT{n0th1ng_1s_tru1y_rand0m}
Looking for text in the PDF structure is much like looking for the Cheshire Cat. It's almost completely invisible, only leaving trace hints that the file even contains text to those unfamiliar with the structure.
Try to understand how text is stored in PDF files and what happens when you tweak different parts to find the cipher key.
A PDF file Text_rendering_is_hard.pdf is also provided.
Opening the PDF it just has 2 lines of text:
Trying to copy some of the text reveals what the description was about:
Text rendering in PDFs is indeed a bit of a rabbit hole, and both the actual contents of the text and what gets placed on the clipboard when copying gives us good hints on what's going on.
CMAPs or Character Maps are mapping tables that define how the bytes in PDF text blocks map to Unicode character codes, allowing PDF to support many kinds of character encodings without having to re-define how text or fonts are stored in PDF files.
This feautre is (ab)used in the provided PDF to mangle the text. Let's see about getting the text back from weird bytes.
I like using my editor of choice to browse PDF files, and to facilitate this, I'm going to "uncompress" the PDF with pdftk: pdftk Text_rendering_is_hard.pdf output uncompressed.pdf.txt uncompress
Now that we have a "text-only" PDF file, we can dig out the CMAP and the textual data.
The CMAP is as follows:
<<
/Length 1695
>>
stream
/CIDInit/ProcSet findresource begin
12 dict begin
begincmap
/CIDSystemInfo<<
/Registry (Adobe)
/Ordering (UCS)
/Supplement 0
>> def
/CMapName/Adobe-Identity-UCS def
/CMapType 2 def
1 begincodespacerange
<00> <FF>
endcodespacerange
81 beginbfchar
<01> <0061> <15>
<02> <0062> <14>
<03> <0063> <27>
<04> <0064> <28>
<05> <0065> <0E>
<06> <0066> <0A>
<07> <0067> <34>
<08> <0068> <3A>
<09> <0069> <3E>
<0A> <006A> <47>
<0B> <006B> <4A>
<0C> <006C> <49>
<0D> <006D> <2A>
<0E> <006E> <29>
<0F> <006F> <07>
<10> <0070> <39>
<11> <0071> <20>
<12> <0072> <43>
<13> <0073> <4C>
<14> <0074> <03>
<15> <0075> <12>
<16> <0076> <4F>
<17> <0077> <45>
<18> <0078> <01>
<19> <0079> <21>
<1A> <007A> <44>
<1B> <0041> <16>
<1C> <0042> <30>
<1D> <0043> <38>
<1E> <0044> <05>
<1F> <0045> <0D>
<20> <0046> <02>
<21> <0047> <1F>
<22> <0048> <11>
<23> <0049> <06>
<24> <004A> <0C>
<25> <004B> <10>
<26> <004C> <3D>
<27> <004D> <46>
<28> <004E> <2F>
<29> <004F> <31>
<2A> <0050> <04>
<2B> <0051> <1D>
<2C> <0052> <23>
<2D> <0053> <09>
<2E> <0054> <2C>
<2F> <0055> <2B>
<30> <0056> <37>
<31> <0057> <3C>
<32> <0058> <2E>
<33> <0059> <22>
<34> <005A> <0B>
<35> <0031> <40>
<36> <0032> <0F>
<37> <0033> <1C>
<38> <0034> <36>
<39> <0035> <3F>
<3A> <0036> <08>
<3B> <0037> <4E>
<3C> <0038> <48>
<3D> <0039> <13>
<3E> <0030> <1E>
<3F> <0020> <33>
<40> <0021> <50>
<41> <0040> <42>
<42> <0023> <24>
<43> <0024> <49>
<44> <0025> <1B>
<45> <005E> <17>
<46> <0026> <4D>
<47> <002A> <41>
<48> <0028> <1A>
<49> <0029> <51>
<4A> <005B> <4B>
<4B> <005D> <25>
<4C> <007B> <2D>
<4D> <007D> <18>
<4E> <003A> <35>
<4F> <003F> <3B>
<50> <005C> <26>
<51> <002F> <19>
endbfchar
endcmap
CMapName currentdict /CMap defineresource pop
end
endThere are two different kinds of character mappings suppored: ranges and individual characters. This file doesn't include ranges, but they would be defined like
1 beginbfrange
<24> <34> <0024>
endbfrangeWhich would mean bytes randing from 0x24 to 0x34 would be mapped to 0x0024 through 0x0034. This can be useful for mapping entire blocks of special characters like mathematical symbols to a different location to account for font differences, for instance.
But in our file we only have the other type of mapping, individual characters. These are usually defined as
1 beginbfchar
<41> <0061>
endbfcharWhich would map upper-case A to a lower-case a. I've not seen mappings with three values like in our file before, and none of the freely available PDF file format definition mention them either. The actual ISO 32000-1 definition coss 198 Swiss Franks directly from ISO, or 250 US Dollars from the PDF Association, you're free to drop the dough if you care, I'm just here for a flag :P So we'll soldier on despite the unusual format.
The text data of our PDF is defined such:
2 0 obj
<<
/Length 523
>>
stream
0.1 w
q 0 0.028 611.971 791.971 re
W* n
q 0 0 0 rg
BT
56.8 725 Td /F1 11 Tf[<23143f1701133f010c0c3f160512193f17050c0c3f140f3f1301193f2d2f1c2d2e232e2f2e1f3f0d053f0215143f1408053f170913053f0c0914140c053f1b0c0903053f1701133f0e0f143f070f090e073f140f3f040f3f140801143f090e3f013f0815121219>]
TJ
ET
Q
q 0 0 0 rg
BT
56.8 690 Td /F1 11 Tf[<280f3f230c0c3f0c0f0f0b3f06091213143f1308053f130109043f010e043f1305053f170805140805123f0914133f0d01120b05043f1D271b2a3f0f123f062f2c0d2f2c2d400345153f291e030407403f1e291c2818>]
TJ
ET
Q
Q
endstream
endobjThe lines between the BT and TJ are our lines of text, the two numbers at the beginning are X and Y positions and the big string of hex digits are the actual bytes.
With this info, we can whip up a quick Python script to decode the text:
a="".join([chr(c) for c in range(1,0x52)])
b="\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B\x6C\x6D\x6E\x6F\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7A\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x31\x32\x33\x34\x35\x36\x37\x38\x39\x30\x20\x21\x40\x23\x24\x25\x5E\x26\x2A\x28\x29\x5B\x5D\x7B\x7D\x3A\x3F\x5C\x2F"
c="\x15\x14\x27\x28\x0E\x0A\x34\x3A\x3E\x47\x4A\x49\x2A\x29\x07\x39\x20\x43\x4C\x03\x12\x4F\x45\x01\x21\x44\x16\x30\x38\x05\x0D\x02\x1F\x11\x06\x0C\x10\x3D\x46\x2F\x31\x04\x1D\x23\x09\x2C\x2B\x37\x3C\x2E\x22\x0B\x40\x0F\x1C\x36\x3F\x08\x4E\x48\x13\x1E\x33\x50\x42\x24\x49\x1B\x17\x4D\x41\x1A\x51\x4B\x25\x2D\x18\x35\x3B\x26\x19"
line1="\x23\x14\x3f\x17\x01\x13\x3f\x01\x0c\x0c\x3f\x16\x05\x12\x19\x3f\x17\x05\x0c\x0c\x3f\x14\x0f\x3f\x13\x01\x19\x3f\x2d\x2f\x1c\x2d\x2e\x23\x2e\x2f\x2e\x1f\x3f\x0d\x05\x3f\x02\x15\x14\x3f\x14\x08\x05\x3f\x17\x09\x13\x05\x3f\x0c\x09\x14\x14\x0c\x05\x3f\x1b\x0c\x09\x03\x05\x3f\x17\x01\x13\x3f\x0e\x0f\x14\x3f\x07\x0f\x09\x0e\x07\x3f\x14\x0f\x3f\x04\x0f\x3f\x14\x08\x01\x14\x3f\x09\x0e\x3f\x01\x3f\x08\x15\x12\x12\x19"
line2="\x28\x0f\x3f\x23\x0c\x0c\x3f\x0c\x0f\x0f\x0b\x3f\x06\x09\x12\x13\x14\x3f\x13\x08\x05\x3f\x13\x01\x09\x04\x3f\x01\x0e\x04\x3f\x13\x05\x05\x3f\x17\x08\x05\x14\x08\x05\x12\x3f\x09\x14\x13\x3f\x0d\x01\x12\x0b\x05\x04\x3f\x1D\x27\x1b\x2a\x3f\x0f\x12\x3f\x06\x2f\x2c\x0d\x2f\x2c\x2d\x40\x03\x45\x15\x3f\x29\x1e\x03\x04\x07\x40\x3f\x1e\x29\x1c\x28\x18"
t1=str.maketrans(a,b)
print(line1.translate(t1))
print(line2.translate(t1))You'll notice I added the third column of CMAP bytes into the file too, but for now we'll just use the two "standard" ones, and get the exact text printed in the PDF as output:
It was all very well to say SUBSTITUTE me but the wise little Alice was not going to do that in a hurry
No Ill look first she said and see whether its marked CMAP or fURmURS!c^u ODcdg! DOBNx
Now we just need to decode the last 24 characters of the second line.
I won't pretend this was the first, second, or 13th thing I tried, but let's use the 3rd CMAP columnt and map the bytes from there to the ones in the 2nd:
# ... cont from previous script
t2=str.maketrans(c,b)
print(line2[-24:].translate(t2))and we get INTENT{1twa5n0tPo150n3d} as outputl. Whoo, another flag - AND a newfound detesment for the PDF file format. I call that a win-win.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
#writeup-intent-ctf-2022---a-genuine-counterfeit-hardware-350pts
Just adding another character at the end of G_AUTHENTICATION_MARKER (eeprom-24lc256.chip.c) will also do the trick without any further changes.