or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
zer0tp - zer0pts CTF 2022
tags:
writeup
zer0pts CTF 2022
web
Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9
Overview
Application Overview
Essential Point
Leak the secret:
Solution
TL; DR
You can leak the secret from the following:
Summary
You can enforce DEFLATE to compress with the dynamic Huffman codes mode using the well-created username such as de Bruijn Sequence. In this mode, the first byte of the DEFLATE compression (=third byte of the Zlib compression, since the first two bytes are the header) contains the information for the max length of the repeating sequence. Using this, you can extract the keys one by one. You can reverse the md5 in the seconds by brute force using the lack of entropy of the structure of DEFLATE.
Details
This problem is divided into two main parts: the first part is to reverse md5; the second part is to leak the secret using the Zlib compression. For the sake of brevity, we will explain the second part first.
Speed learning: DEFLATE
DEFLATE is the format for the compression. Usually, it forms from multiple blocks, but in the case of this task, you will not see such kind of situation since data is too small. The block has 3 types; Non-compressed, fixed Huffman, and dynamic Huffman. Other than non-compressed block uses the dictionary-based coding, which records the pair of offset and length instead of the actual string. This information is also coded by Huffman code. The actual character of the strings and the length is represented using the same Huffman code.
The following is a pseudo-parser of the part essential for this problem.
You can earn more infomations by looking at RFC1951 - DEFLATE Compressed Data Format Specification version 1.3.
Speed learning: Zlib
Zlib is just the wrapper of DEFLATE. Zlib generated by default
zlib.compress
has the following format:CMF
andFLG
is always same as long as you are using the default settings.ADLER32
is the checksum.Second Part
First, consider how to force
zlib.compress
to use dynamic Huffman mode. To beat the efficiency of fixed Huffman, you need to have a few character types as possible appear in as many as possible with no large repetition. With some experiments, you can find that more than 3 characters of repetition will be compressed. Therefore, we look for the string with the fewest number of characters that appear in a string that has no repetitions of length more than 3. Luckily, this kind of string has a name, which is de Bruijn Sequence. Using this, you can accomplish the goal.Next, let's find out an oracle that can be used to leak the secret characters one by one. The third byte[1] of compressed data contains the size of the Huffman code for the character and the length. This is 257[2] if there are no repetitions, and more than 258 if there are. Thus, we can detect whether there are repetitions or not. With the observation that more than 3 bytes of repetitions will be compressed, you can leak the entire secret.
First Part
If we tally up the possible bits of each semantic unit[3] are, we find that there are only about a \(10^6\) possible combinations. With this level of number, we can brute force to reverse the md5.
Exploit
structure of first 3 bytes are: 2 bytes for constant + 1 bit for is_final + 2 bit for block_type + 5 bit for the length of huffman code we need ↩︎
Need to use
256: End of the Block
at the end of stream ↩︎chunks read by read_bits in above pseudo-parser ↩︎