Bro-key-n

Challenge Overview

We are given a broken private key file, which is encoded in Privacy-Enhanced Mail (PEM).

Key_Redacted.pem

About half of the file is redacted, and our goal is to recover the file. Then use it to connect the server and capture the flag.

Solution

Reveal Leakage

First of all, we need to investigate how the file is generated. The private key contains the information

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Then we apply Distinguished Encoding Rules (DER) to encode those info into binary data. Basically, all data will be encoded into following form

ASN.1 Tag + Length Octet + Data Content + End-of-Contents Octets

Finally, PEM file is created by encoding DER with Base64. Let's use the broken file to explain the details. The first line is

3082092402010002820200125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227

The first byte is \(0x30\) indicating the data is SEQUENCE, and it follows \(0x82\), which means the length of data is given in the next \(2\) bytes, say \(0x0924\). Now, we move to the data wrapped in the SEQUENCE.

The next byte is \(0x02\), which means the first data is an integer. The length is \(0x01\) and the value is simply \(0x00\). Note that it's a little different to what we do above.

There are two forms for length octet:

Short form [One byte]. where the most significant bit (MSB) has value "0" and other bits give the length.
Long form [Two or more bytes (at most 127)]. MSB of first octet has value 1 and remaining bits give the number of additional octets. Second and following octets give the length.

Keep doing, we will find the partial values! This is left as an exercise to the reader :P

Leakage

n = 0x125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227348916a4befeb306be79d75a8e4fac2f7d8591d7f7f1e5006eaff2d32e93fcb1a50cb5bd449a84840c71f9f0bad999aeeed500dc32b7092d0b021adde2859d53c604f4b1613880fb4ada66c5a19da058bc7a6646b935c4d28a321bad0a39bb387465775dbc2ad7184ce221bd0ebc3de0fc0e9574b952a0cd7c2718d0696ba2b2ac5122708cd9643c8a28b3916d47b28f46c6aed7e91df1a78278039b9197223d1a8b0e88f2ddc55766a28eeaaa571e4daa7f2132d4028015a372b78b04b775987b1f6a420f5ad96d30d76cc3d354199c968a85390c85d4e12c7aeb050b1b04f430b23725ec5c13d0340138f66c6acfa459461b4ebfbe5af2b2d6907b8fa782e1652514529fdf343667e6875d7d1498f3d80cb76524580b6f2af01142f15bb10e91366dd882f7738fb2c242b417a4f2e0cfa5cd6fd6b63d1972901df69b9d5c4817782494309e80954d1c90e975592a47cce447619f5a3d5b7612bb667bbb14e1774964b14ea97cea375f99f7a19da543a9b4e9a978bdbfb2fff8f35e8e9597473888cb12b2efef708d871489e7ddb3ca64997ac6f4ad29c7e13d3545eb056a2e872ce32f13df5ecedd25b7bdd7c32464306466d2e5b7e48af9ace8a81e429581ab377468c7f03103ef758eaefb79a740489926fd8f26334fda1d65
e = 0x010001
d_high_bits = 0x459f17931ec0e267379f643cf751a54ea49f4be446d0a0e0de8f827b6c274b5d955f85fa69084402cc2721e74ebaa65cdcd207ff6880ac2aa5aebcb4a5f00cc0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
q_low_bits = 0x60ce22ff0241b9d206346c702517ce47d1d42361bfc1c85f0b5efbd9bc5d15ebf9fb460c3e2b81467ca989a1dc7f6fc000e983319245cab4eaadfcbc8e6c5f77
dp_high_bits = 0x0c55acb5a46475e4fcb3fc012a26f3b896bc34f7f047035c610d3739b98ce50a146ec49127e5e8667352e06dac2bfa37224a47c29cd904b9e418bf4f8484f60594906ccedac2257de1cdc54453ba892d1e1a00fe8fc7e1b415dfe4c5055bcab0af08a335a6d9a934fa98644d884794621738f8783eeb975a8468134811d36cd9544c9ac47086ba8865c81155bcdc39fe5c1376a07a59934ff25e18554517e462927c6f85571249c3ca82c7dd8691707186de2ea6cb69ced941c6f5f90cfb5d4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Here, the unknown hex digits are replaced by \(0\).

Key Recovery

As we have low bits of the factor \(q\), it's easy to find the low bits of \(p\) as well.

p_low_bits = (n % m) * pow(q_low_bits, -1, m) % m # m=2^512

On the other hand, by definition, \[dp \equiv d \pmod{p-1}\] Multiply both sides by \(e\), we get \[e \times dp \equiv e \times d \equiv 1 \pmod{p-1} \] since \(e\) is the multiplicative inverse of \(d\) w.r.t to \((p-1)(q-1)\) Thus, there exists an integer \(k\) less than \(e\) so that \[e \times dp = k(p-1) + 1\] Because we have partial values of \(dp\) and \(p\), we should rewrite the equation as \[ e \times (dp_{high\_bits} + j \times m + dp_{l}) = k(p_h + p_{low\_bits} - 1)+1 \] for some \(j < 16\) (Because there are \(129\) zeros in the end, dp_high_bits = dp % (4 * m). We need to add \(j \times m\)). Here \(x_h, x_l\) represents high and low bits of \(x\). In python,

x_h = x - (x % m)
x_l = x % m

Take \(\pmod{m}\), the equation becomes \[e \times dp_l \equiv k(p_l-1)+1 \pmod{m}\] And we deduce the low bits value of \(dp\): \[dp_l \equiv dp_l \equiv e^{-1} (k(p_l-1)+1) \pmod{m} \]

This give us one factor \[p = \frac{e \times dp - 1}{k}\] We decide whether this is true \(p\) by checking n % p == 0. For completeness, here is my script.




















from output import * # store the leakage as output.py
from Crypto.Util.number import *

k = 512
m = 1 << k

p_low_bits = (n % m) * pow(q_low_bits, -1, m) % m 

for i in range(1, e):
    dp_low_bits = (i * (p_low_bits - 1) + 1) * pow(e, -1, m) % m
    for j in range(16):
        dp = dp_high_bits + j * m + dp_low_bits	

        p = ((dp * e - 1) // i) + 1
        if isPrime(p):
            if n % p == 0:
                print(f"Found!")
                print(p)
                print(n // p)
                exit()

Capture The FLAG

Now, it suffices to recover the PEM file.












from output import *
from result import * # p = ...
from Crypto.PublicKey import RSA

q = n // p

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
key = RSA.construct([n, e, d])

with open("key.pem", "wb") as f:
        f.write(key.export_key('PEM'))

Use the command chmod 600 key.pem to change permission! Or you may fail to connect to the server …

Finally, type ssh user@bro-key-n.chal.uiuc.tf -p 1337 -i key.pem on the terminal and press enter!

FLAG. uiuctf{hidden_in_plain_sight}

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.