owned this note
owned this note
Published
Linked with GitHub
# Bro-key-n
## Challenge Overview
We are given a **broken** private key file, which is encoded in Privacy-Enhanced Mail (PEM).
:::spoiler Key_Redacted.pem
```
-----BEGIN RSA PRIVATE KEY-----
MIIJJAIBAAKCAgASUWUVXgOvRLJkI77YJ6BlG5t6en55ysW40HpawMJb9bTyWMIn
NIkWpL7+swa+eddajk+sL32Fkdf38eUAbq/y0y6T/LGlDLW9RJqEhAxx+fC62Zmu
7tUA3DK3CS0LAhrd4oWdU8YE9LFhOID7StpmxaGdoFi8emZGuTXE0ooyG60KObs4
dGV3Xbwq1xhM4iG9Drw94PwOlXS5UqDNfCcY0GlrorKsUSJwjNlkPIoos5FtR7KP
Rsau1+kd8aeCeAObkZciPRqLDojy3cVXZqKO6qpXHk2qfyEy1AKAFaNyt4sEt3WY
ex9qQg9a2W0w12zD01QZnJaKhTkMhdThLHrrBQsbBPQwsjcl7FwT0DQBOPZsas+k
WUYbTr++WvKy1pB7j6eC4WUlFFKf3zQ2Z+aHXX0UmPPYDLdlJFgLbyrwEULxW7EO
kTZt2IL3c4+ywkK0F6Ty4M+lzW/Wtj0ZcpAd9pudXEgXeCSUMJ6AlU0ckOl1WSpH
zORHYZ9aPVt2Ertme7sU4XdJZLFOqXzqN1+Z96GdpUOptOmpeL2/sv/4816OlZdH
OIjLErLv73CNhxSJ592zymSZesb0rSnH4T01ResFai6HLOMvE99ezt0lt73XwyRk
MGRm0uW35Ir5rOioHkKVgas3dGjH8DED73WOrvt5p0BImSb9jyYzT9odZQIDAQAB
AoIB/0WfF5MewOJnN59kPPdRpU6kn0vkRtCg4N6PgntsJ0tdlV+F+mkIRALMJyHn
TrqmXNzSB/9ogKwqpa68tKXwDM______________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________YM4i/wJBudIGNGxwJRfOR9HUI2G/wchfC1772bxdFev5+0YM
PiuBRnypiaHcf2/AAOmDMZJFyrTqrfy8jmxfdwKCAQAMVay1pGR15Pyz/AEqJvO4
lrw09/BHA1xhDTc5uYzlChRuxJEn5ehmc1Lgbawr+jciSkfCnNkEueQYv0+EhPYF
lJBsztrCJX3hzcVEU7qJLR4aAP6Px+G0Fd/kxQVbyrCvCKM1ptmpNPqYZE2IR5Ri
Fzj4eD7rl1qEaBNIEdNs2VRMmsRwhrqIZcgRVbzcOf5cE3agelmTT/JeGFVFF+Ri
knxvhVcSScPKgsfdhpFwcYbeLqbLac7ZQcb1+Qz7XU______________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
______________________________________________________
-----END RSA PRIVATE KEY-----
```
:::
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
::: info
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.
:::warning
There are two forms for length octet:
1. Short form [One byte]. where the most significant bit (MSB) has value "0" and other bits give the length.
2. 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
:::spoiler 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.
```python
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,
```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.
```python=
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.
```python=
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'))
```
:::danger
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!
:::success
FLAG. uiuctf{hidden_in_plain_sight}
:::
