# Bro-Key-n
_"a math researcher fixing a rusty lock at a chalkboard cartoon style"_
Writeup by: Kevin He (name on team: `cupr1c`)
Team: Phiat Lux
## Overview
- CTF: UIUCTF 2022
- Category: Crypto
- Points: 408
- Solves: 14
- Tags: crypto, **extreme**
## Challenge Description
I tried to save my SSH key, but it seems that some of it has gotten removed! If there are any data recovery experts out there, hopefully they can recover my key...if you can, try to connect to my server to reach back to me.
`ssh user@bro-key-n.chal.uiuc.tf -p 1337`
author: Husnain
## Attachments
:::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-----
```
:::
## Solution
A summary of steps to get the flag:
1. Deobfuscate the private key format
2. Extract the known bits of private key parameters
3. Do the math: Using only the high bits of $d \bmod (p-1)$, perform a lattice cryptanalysis to factor $n$ into $p$ and $q$.
4. Reassemble the SSH private key from $n,e,d,p,q$
5. SSH to host and capture the flag
### Deobfuscation
The key to be recovered is an [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) private key in the standard PEM format, specified by [RFC 8017](https://datatracker.ietf.org/doc/html/rfc8017). The body of the key contains a Base64 encoding of ASN.1 data.
First, replace all the redacted parts (underscores: `_`) with `A` so that it becomes valid Base64 with zeros in place of unknown parts. The key at this step looks like [key_00.pem](https://gist.githubusercontent.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec/raw/495fe621da5090b9124302e569ea7ae6ab730dd8/key_00.pem)
The schema of the ASN.1 data is specified in [RFC 8017 Appendix A.1.2](https://datatracker.ietf.org/doc/html/rfc8017#appendix-A.1.2):
```
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
}
```
:::warning
Throughout this writeup, we will refer to the private CRT exponent $d \bmod (p-1)$ as $d_p$ for brevity.
:::
ASN.1 is a Tag-Length-Value encoding, where every value is preceded by a tag --- describing its type (Ex. `SEQUENCE`, `INTEGER`, etc.) --- and the length of the value. Tag and length are crucial information for the decoder to know the boundaries between values. Unfortunately, some tags and lengths are redacted out, so the key is not directly readable with existing ASN.1 decoders, including a very useful tool with nice visualizations: [lapo.it](https://lapo.it/asn1js/).
### Parameter extraction
Although _precise_ solutions are not available due to some length information being erased, it is often the case that we can find _approximate_ solutions to our problem, as it is in the case of data recovery via [File Carving](https://en.wikipedia.org/wiki/File_carving) and digital forensics in general.
My intuition tells me that two different RSA private keys of the same size will likely have the same parameters in "close" offsets in the file. For example, if key A has $p$ at offset 0x800 in the file, key B might have $p$ at offset 0x805. If that is the case, then we can _guess_ where a parameter starts and ends with the help of another key of the same length.
I validated my idea by generating two RSA PEM keys of the same size, pasting both into [lapo.it](https://lapo.it/asn1js/) and comparing the offsets as I hover over the `INTEGER`s.
 
To get myself familiar with the PEM format, I generated an RSA private key hopefully similar to `key_redacted.pem` before redaction:
```bash
ssh-keygen -m PEM -t rsa -b 4096 -f sample_4096.pem
```
:::info
Some Explanation for the command line:
- `-m PEM`: `key_redacted.pem` is in PEM format so we better do the same, or OpenSSH defaults to [its own format](https://coolaj86.com/articles/the-openssh-private-key-format/).
- `-t rsa`: Generate an RSA key
- `-b 4096`: Make the public modulus $n$ 4096 bits long. See the paragraph below for how I came up with this number
- `-f sample_4096.pem`: Output to file `sample_4096.pem`
:::
Here is my generated [sample_4096.pem](https://gist.githubusercontent.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec/raw/84763e38a204958a3fbe6fa755080de4e08fe560/sample_4096.pem).
A curious reader might ask how I came up with the key length of 4096 bits. It turns out that I had no idea what the key length of `key_redacted.pem` was, but surely a larger key means a larger file! So through trial and error I generated keys of common sizes like 2048, 3072, 4096. Only the 4096-bit key roughly matches the size of `key_redacted.pem` (both have 50 lines of Base64 encoded data)
Unfortunately, the rest of this is a very manual process. I first converted the Base64 part of the PEM format (both [key_00.pem](https://gist.githubusercontent.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec/raw/495fe621da5090b9124302e569ea7ae6ab730dd8/key_00.pem) and my [sample_4096.pem](https://gist.githubusercontent.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec/raw/84763e38a204958a3fbe6fa755080de4e08fe560/sample_4096.pem)) into raw binary files using this script `pem2bin.py`:
```python=
import base64
import sys
# usage: python3 pem2bin.py /path/to/key.pem
with open(sys.argv[1]) as pf:
lines = list(pf)
b64 = ''.join((line[:-1] for line in lines[1:-1]))
bys = base64.b64decode(b64)
with open(f'{sys.argv[1]}.bin', 'wb') as bf:
bf.write(bys)
```
This way I can copy data at specific offsets in the file with a hex editor.
The true boundaries between parameters can sometimes be fuzzy since some lengths are redacted. However, we can "carve out" the boundaries by looking for sequences of the form `02 82` denoting the start of a large `INTEGER` value in ASN.1. It will be explained later why it is the case.
For example, we cannot determine the end of $q$ i.e. the start of $d_p$ since the start of $q$ is redacted. Looking at my [sample_4096.pem](https://gist.githubusercontent.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec/raw/84763e38a204958a3fbe6fa755080de4e08fe560/sample_4096.pem), I found $d_p$ at offset 1567 (0x61f) using [lapo.it](https://lapo.it/asn1js/). Indeed there is a sequence `02 82` at offset 0x61c, which is _very close_ to 0x61f, so that is likely the start of the tag value of the object.
:::info
:information_source:
The highlighted part (`02 82 01 00`) denotes a tag + length pair for the ASN.1 integer $d_p$:
`02`: Tag telling this is of type `INTEGER`
`82`: If this value is less than 128/0x80, then it is the length of the data. Unfortunately, SSH parameters are very big integers and the length exceeds 7 bits, so the length value is encoded in the 0x82 - 0x80 = 2 bytes the follows
`01 00`: Interpreted as a big-endian integer, the value of the integer is stored in the following 0x100 = 256 bytes
:::
The actual _value_ of $d_p$ starts with `0C 55 AC B5....`
Using the manual method described above, I extracted the complete public key parameters $n$, $e$, and the upper 1532 out of 2048 bits (**~75%**) of $d_p$:
<p><details><summary>Expand to see the leaks (? for unknown nibbles) </summary>
```
n = 0x125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227348916a4befeb306be79d75a8e4fac2f7d8591d7f7f1e5006eaff2d32e93fcb1a50cb5bd449a84840c71f9f0bad999aeeed500dc32b7092d0b021adde2859d53c604f4b1613880fb4ada66c5a19da058bc7a6646b935c4d28a321bad0a39bb387465775dbc2ad7184ce221bd0ebc3de0fc0e9574b952a0cd7c2718d0696ba2b2ac5122708cd9643c8a28b3916d47b28f46c6aed7e91df1a78278039b9197223d1a8b0e88f2ddc55766a28eeaaa571e4daa7f2132d4028015a372b78b04b775987b1f6a420f5ad96d30d76cc3d354199c968a85390c85d4e12c7aeb050b1b04f430b23725ec5c13d0340138f66c6acfa459461b4ebfbe5af2b2d6907b8fa782e1652514529fdf343667e6875d7d1498f3d80cb76524580b6f2af01142f15bb10e91366dd882f7738fb2c242b417a4f2e0cfa5cd6fd6b63d1972901df69b9d5c4817782494309e80954d1c90e975592a47cce447619f5a3d5b7612bb667bbb14e1774964b14ea97cea375f99f7a19da543a9b4e9a978bdbfb2fff8f35e8e9597473888cb12b2efef708d871489e7ddb3ca64997ac6f4ad29c7e13d3545eb056a2e872ce32f13df5ecedd25b7bdd7c32464306466d2e5b7e48af9ace8a81e429581ab377468c7f03103ef758eaefb79a740489926fd8f26334fda1d65
e = 65537 = 0x10001
d_p = 0x0c55acb5a46475e4fcb3fc012a26f3b896bc34f7f047035c610d3739b98ce50a146ec49127e5e8667352e06dac2bfa37224a47c29cd904b9e418bf4f8484f60594906ccedac2257de1cdc54453ba892d1e1a00fe8fc7e1b415dfe4c5055bcab0af08a335a6d9a934fa98644d884794621738f8783eeb975a8468134811d36cd9544c9ac47086ba8865c81155bcdc39fe5c1376a07a59934ff25e18554517e462927c6f85571249c3ca82c7dd8691707186de2ea6cb69ced941c6f5f90cfb5d4?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
```
</details></p>
Yes, `key_redacted.pem` contains bits and pieces of private key parameters other than $d_p$ which I did not bother extracting, because (perhaps surprisingly) $n,e,d_p$ turns out to be _sufficient_ to factor $n$. See the next section for why.
### Math time
_"A rusty shattered padlock with math equations in a dark background"_
The setup of this challenge brought me back to the day where professor [Nadia Heninger](https://cseweb.ucsd.edu/~nadiah/) showed me her paper [_Recovering cryptographic keys from partial information, by example_](https://eprint.iacr.org/2020/1506.pdf) [[1]](#References) during an office hour.
Among all the private key parameters, $d_p$ has the largest fraction of bits leaked. My intuition tells me there is probably a way to recover the entire private key using such information detailed somewhere in the paper.
The paper is designed to be easy to navigate. In addition to the textual table of contents, there is a nice visual one on _Page 5_ containing every known method of inferring the private key based on partial information:
Indeed, Coppersmith's method in section 4.2.7 (Page 18) is what we are looking for: MSB of $d \bmod (p-1)$ a.k.a. $d_p$
A motivated reader should read the section in the paper to get a full understanding of how the attack works. I will present a short summary of the idea behind this attack.
#### Summary of methodology
Let $a$ be $d_p$ except with 0's in place of the unknown bits. Let $l$ be the number of unknown bits ($l = 2048 - 1532 = 516$ for this specific challenge). Therefore, there exists some unknown $r < 2^l$ such that $a + r = d_p$. Let $e' = e^{-1} \bmod n$, note this means $e'$ is an inverse of $e$ mod $p$ as well, so this trick allows us to construct an inverse without knowing $p$.
\begin{equation}
\begin{split}
d_p \equiv d \mod (p - 1) &\implies ed_p \equiv 1 \pmod{(p-1)}\\
&\implies ed_p = 1 + k_p (p - 1) \qquad \text{ for some } 1 \leq k_p < e\\
&\implies e(a + r) = 1 + k_p (p - 1) \\
&\implies e(a + r) - 1 + k_p \equiv 0 \pmod p\\
&\implies e' ( e(a + r) + k_p - 1) \equiv 0 \pmod p\\
&\implies a + r + e' (k_p - 1) \equiv 0 \pmod p\\
\end{split}
\end{equation}
Then let $A = a + e' (k_p - 1)$, then the above equation is reduced to $A + r \equiv 0 \pmod p$.
It is a simple linear equation of one variable (mod $p$), yet the big problem is that we don't know $p$. However, we do know that $n \equiv 0 \pmod p$, and it turns out that fact is sufficient to convert this to a shortest vector problem (SVP) in a 3D lattice + solving a quadratic equation, both of which can be solved efficiently. Section 4.2.2 of the paper contains the lattice construction to solve this problem, including an explanation of why it works.
#### Attack Implementation
[SageMath](https://www.sagemath.org/) is a powerful computer algebra library for Python. It has a lot of useful algorithms built-in so we don't have to implement them from scratch, including [LLL](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm) which is used to quickly solve SVP in low-dimensional lattices. One nice thing about the paper is that it includes a small test case to help me debug my code every step along the way, so `print()` is all we need to verify if my code is correct up to a point.
My solve script `attack.py`:
```python=
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
## Parameters
e = 65537
N_ = 0x125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227348916a4befeb306be79d75a8e4fac2f7d8591d7f7f1e5006eaff2d32e93fcb1a50cb5bd449a84840c71f9f0bad999aeeed500dc32b7092d0b021adde2859d53c604f4b1613880fb4ada66c5a19da058bc7a6646b935c4d28a321bad0a39bb387465775dbc2ad7184ce221bd0ebc3de0fc0e9574b952a0cd7c2718d0696ba2b2ac5122708cd9643c8a28b3916d47b28f46c6aed7e91df1a78278039b9197223d1a8b0e88f2ddc55766a28eeaaa571e4daa7f2132d4028015a372b78b04b775987b1f6a420f5ad96d30d76cc3d354199c968a85390c85d4e12c7aeb050b1b04f430b23725ec5c13d0340138f66c6acfa459461b4ebfbe5af2b2d6907b8fa782e1652514529fdf343667e6875d7d1498f3d80cb76524580b6f2af01142f15bb10e91366dd882f7738fb2c242b417a4f2e0cfa5cd6fd6b63d1972901df69b9d5c4817782494309e80954d1c90e975592a47cce447619f5a3d5b7612bb667bbb14e1774964b14ea97cea375f99f7a19da543a9b4e9a978bdbfb2fff8f35e8e9597473888cb12b2efef708d871489e7ddb3ca64997ac6f4ad29c7e13d3545eb056a2e872ce32f13df5ecedd25b7bdd7c32464306466d2e5b7e48af9ace8a81e429581ab377468c7f03103ef758eaefb79a740489926fd8f26334fda1d65
a = 0xc55acb5a46475e4fcb3fc012a26f3b896bc34f7f047035c610d3739b98ce50a146ec49127e5e8667352e06dac2bfa37224a47c29cd904b9e418bf4f8484f60594906ccedac2257de1cdc54453ba892d1e1a00fe8fc7e1b415dfe4c5055bcab0af08a335a6d9a934fa98644d884794621738f8783eeb975a8468134811d36cd9544c9ac47086ba8865c81155bcdc39fe5c1376a07a59934ff25e18554517e462927c6f85571249c3ca82c7dd8691707186de2ea6cb69ced941c6f5f90cfb5d4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
UNKNOWN_BITS = 516 # 64 * 8 + 4 bits, (64 bytes and a nibble)
# Test case from the paper
# e = 65537
# N_ = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5
# a = 0x25822d06984a06be5596fc00000000 # Assume R >= sqrt(p), more than 25% exposed
# UNKNOWN_BITS = 32
R_: int = 2 ** UNKNOWN_BITS
R2 = R_ ** 2
## Attack Start
e_inv = pow(e, -1, N_)
for kp in range(1, e + 1):
if kp % 100 == 0:
print(f'{kp} / {e}', flush=True) # progress
A = a + e_inv * (kp - 1)
B = IntegerLattice([
[R2, R_*A, 0],
[0, R_, A],
[0, 0, N_]
], lll_reduce=False) # shortest_vector() will automatically do LLL reduce, so don't duplicate the work here
v0, v1, v2 = B.shortest_vector(update_reduced_basis=False)
assert v0 % R2 == 0
assert v1 % R_ == 0
quad_a = v0 // R2
quad_b = v1 // R_
quad_c = v2
ZP = ZZ['x']
# Solve quadratic: a*x^2 + b*x + c = 0
for r, _ in ZP([quad_c, quad_b, quad_a]).roots():
p = gcd(A + r, N_)
if p != 1 and p != N_:
assert N_ % p == 0
q = N_ // p
print('ANSWER!')
print(f'{p = }')
print(f'{q = }')
assert is_prime(p)
assert is_prime(q)
assert p * q == N_
sys.exit()
```
The script ran for about 2 minutes on my AMD Ryzen 7 laptop to factor $n$:
```
$ time python3 attack.py
100 / 65537
200 / 65537
300 / 65537
400 / 65537
...
28100 / 65537
ANSWER!
p = 3627991603884808062736141310447106260943326330899396275199779984022462194376994246446102117532813224234792046840726872009503786329408256663119027353255969224649727885389580250774873824390822482215139013309728202469835336298188620697403248917907049738004864552884412233025397042416703298163382725246031075810130222032765486555500736412969415261015967808462136504839813036078699995347830504646364842806157413675646357345753021818180743963892741139070590339137165833818468345693182851348835784086931651709553805159969447778964285167310407227065749316889692916103874856521269259363246539154909931419853080560118329293059
q = 20598369222871626043072216357111854496024645053994263979092523658841340015618093953301403603006820017599326657242822459672261069591757161666583903417748632127452902462416407108216272232046821496547425743893487370083414071869503963944576753877699674625320223980514728077608176436018469521820069344910135073178779460798798070288038908901616872195433430227246973421982015955456791648994934658395900842039051221873444228459558128608404028483977743648206193560549325892128792059229756408316058150451063406159514445706989869623611544592427409034225334586140215511798730646848775635621896189852877392621164908264378996645751
real 1m52.553s
user 1m51.100s
sys 0m3.471s
```
With the factorization of $n$, we have all the necessary information to efficiently construct a complete private key.
### Reassembly
The easiest way (without needing an ASN.1 encoder) is to use [PyCryptodome's RSA module](https://www.pycryptodome.org/src/public_key/rsa) to reconstruct the key from the parameters:
```python3=
import os
from Crypto.PublicKey import RSA
n = 0x125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227348916a4befeb306be79d75a8e4fac2f7d8591d7f7f1e5006eaff2d32e93fcb1a50cb5bd449a84840c71f9f0bad999aeeed500dc32b7092d0b021adde2859d53c604f4b1613880fb4ada66c5a19da058bc7a6646b935c4d28a321bad0a39bb387465775dbc2ad7184ce221bd0ebc3de0fc0e9574b952a0cd7c2718d0696ba2b2ac5122708cd9643c8a28b3916d47b28f46c6aed7e91df1a78278039b9197223d1a8b0e88f2ddc55766a28eeaaa571e4daa7f2132d4028015a372b78b04b775987b1f6a420f5ad96d30d76cc3d354199c968a85390c85d4e12c7aeb050b1b04f430b23725ec5c13d0340138f66c6acfa459461b4ebfbe5af2b2d6907b8fa782e1652514529fdf343667e6875d7d1498f3d80cb76524580b6f2af01142f15bb10e91366dd882f7738fb2c242b417a4f2e0cfa5cd6fd6b63d1972901df69b9d5c4817782494309e80954d1c90e975592a47cce447619f5a3d5b7612bb667bbb14e1774964b14ea97cea375f99f7a19da543a9b4e9a978bdbfb2fff8f35e8e9597473888cb12b2efef708d871489e7ddb3ca64997ac6f4ad29c7e13d3545eb056a2e872ce32f13df5ecedd25b7bdd7c32464306466d2e5b7e48af9ace8a81e429581ab377468c7f03103ef758eaefb79a740489926fd8f26334fda1d65
e = 65537
p = 3627991603884808062736141310447106260943326330899396275199779984022462194376994246446102117532813224234792046840726872009503786329408256663119027353255969224649727885389580250774873824390822482215139013309728202469835336298188620697403248917907049738004864552884412233025397042416703298163382725246031075810130222032765486555500736412969415261015967808462136504839813036078699995347830504646364842806157413675646357345753021818180743963892741139070590339137165833818468345693182851348835784086931651709553805159969447778964285167310407227065749316889692916103874856521269259363246539154909931419853080560118329293059
q = 20598369222871626043072216357111854496024645053994263979092523658841340015618093953301403603006820017599326657242822459672261069591757161666583903417748632127452902462416407108216272232046821496547425743893487370083414071869503963944576753877699674625320223980514728077608176436018469521820069344910135073178779460798798070288038908901616872195433430227246973421982015955456791648994934658395900842039051221873444228459558128608404028483977743648206193560549325892128792059229756408316058150451063406159514445706989869623611544592427409034225334586140215511798730646848775635621896189852877392621164908264378996645751
assert p * q == n
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
key = RSA.construct((n, e, d, p, q))
os.umask(0o077) # Avoid OpenSSH complaining about permissions being too open
with open('key.pem', 'wb') as kf:
kf.write(key.export_key('PEM'))
```
:::info
Note: Since our goal is to log into an SSH server and steal the flag, we are only trying to construct **any** valid key, not trying to recover the exact same key as the challenge author intends. Specifically, this means the order of $p$ and $q$ does not matter and it is entirely possible for the intended key to have $p$ and $q$ in a different order.
:::
:::spoiler The recovered key (key.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/9ogKwqpa68tKXwDM3f2iidRpMKu7WiCaegO6z3Sv7iDjvTg8DBLACB
37D3TyYGz9Anl3k+jO/20kRJO89hV+LCjoHOtOwZBUQO8zF//y/ePLdVrlEA8y3g
WXvd/l2So+SMOXc0lW/JnWNjfTXS6tsuhepqdXtR2vAfKP2JgjLXTtNBLeVcu6oT
z5cSjqO5t7Nqinf7xodOX77RWQfY4ZQ8mPRsPMHzC43GsHRTJw3GPC5PyBcU/UdP
HLOGFN41WG//uCzELRBrmbA8XvAJ0v17iHMK3xK+nAqKho4S32HDfpfHf7C3+Kg6
aRDBOrYolhdA/SIf2M4/b5z10JjRi51tBNKe3T4a0uBV1aIBdQF+T9XFmdGGGWN9
555OIfHyEZMHPGnUx95L8DxA6lzdYqvJq0GvNqZ3iMlLBPu0tRmRWlalr2EENxSb
qTrb6r3ptk9u0cDtCpexqTzgb+NJ1s1hJDFpbARKeK2e6QRC8gyjkdKis6U2799a
UUlRLDNmNvXbR9icbDQ3q5NIvZxOJNs9xAprJzyVWcae+Ha7Qr9vaPz8mnZrquUL
QMdjRKWeWPh7qz8pcMoVmyaiZ5FJuq7f8WUImnnNzwtWtP0CggEAHL0+Ixq9i5cI
Fzua/uiuctf/hidden/in/plain/sight///0nw3crWsTXmP0JYEVjhNATT3RvGE
rxD3lsHqi08gVxL/3Q2wREGX5pkukfsdeuUjZIlVS+/fVRY59tONxtsttYi7H0vB
y9umHxBHcRtU5Me2WeeXZ/8M9iTyTLZTo9BkShOdHbWXp7v6oUOEtw+bHwak91l2
XwqpL+IWqpVlqToESts2pXvxu2YR+Z6lkTu/34g/hKpgndoqamVmTeSJprvaDfvw
X/PCNMGiw2X33Uj6GXioANlEJI1olvmDiy1Rh7zSo5ysmgYD2vW0c1HnkSQS3KdZ
jBrFHyi5AwKCAQEAoyum3YCJ47ZzLeBUu5ISrpcR9Hngc2dhaBXCIS1kKuhcG7hI
9FDAnFsxowfG2T2vU4gFKqdleMQSMWEhOMhGBpYmA3s9xvzo9VzCUnoKDZ2Ostir
JtDaniCJ6HAjk6OrWBKlisTfzlSn2tif1cugDK4UR4nLmFdzii1MzGlWHqWsA7xT
Jr8vG1yp69lsJ/RqkfD3aqCVkKyAh0kQsxwjOcx/mAIbJVFrZ4lSUfwbWkwvb4Sn
VeFtuQA2OfeHo3zNYM4i/wJBudIGNGxwJRfOR9HUI2G/wchfC1772bxdFev5+0YM
PiuBRnypiaHcf2/AAOmDMZJFyrTqrfy8jmxfdwKCAQAMVay1pGR15Pyz/AEqJvO4
lrw09/BHA1xhDTc5uYzlChRuxJEn5ehmc1Lgbawr+jciSkfCnNkEueQYv0+EhPYF
lJBsztrCJX3hzcVEU7qJLR4aAP6Px+G0Fd/kxQVbyrCvCKM1ptmpNPqYZE2IR5Ri
Fzj4eD7rl1qEaBNIEdNs2VRMmsRwhrqIZcgRVbzcOf5cE3agelmTT/JeGFVFF+Ri
knxvhVcSScPKgsfdhpFwcYbeLqbLac7ZQcb1+Qz7XUnrZIsv5LBSEC+6/wP7YKBa
/QjFEO1GwWJZ+uYkSgz5v12V/n1fpMtDLZtm/+3nrE0msaCRysnNqoXkfBjeprvB
AoIBACbfVmB8p9z88VGjmOwar6KyUM+6XVOA9H60eEwpISzrsE3WSGMT/d8CBsA9
MQ0+Gc+/nuN7f7wWkfL7ncuGQtB84s9/g8ctJ16U26KEenKl74ICBjw4E20KeXBL
jt40ZrSTtKZropnoJxkG9IUdfqKmsiQc2skPRHJNuncUPTUN6P321qRrdZCCMeUD
JjYaj2z3SCo52Yfe4LvaF0VkVawGYPtYvRjV3c2LtHXdprKLZd2eb7MRAm/JciG7
K7AyIkeGtGWmJvxa4amJj+n2UulfPrezKNjEoIf39+32ZwK69hH7rRz+hkzBlC46
xmoBuG8/MkcT/tZ85U/P3yfa/58CggEABV0xA9M2IooKWwAlXah4Ff69hdiMXGm5
vCbJ2DKHJlSaaVQTR6boiINb8n3jFr32QQB9+0e43QPHNRpH5yoU+ij54p0K3q4n
Rp1Q+v8Q32SOVbmtXFusXQTp6a57yA0LSwZc7LbB3V+CiNxfbcSr5UgXaYqA3WQn
qRGqPf/Wr8nKTJgFG1A8YYEZRAsE9IjhZHRDxTIjtR4hkTE1MGD/HJxqZkt1uCgl
iZoKtTj3kUZygpfBT8/99gAm1Gmm4vxEUqpZ3hxybBGGmE1J41gN/kPdyOuoM+S3
y6IZWpdwDrjZI8GJWqQE8xSzuWdKKFU6e+/rQumzIFYN/zTYJdnZxw==
-----END RSA PRIVATE KEY-----
```
:::
### Capture the Flag
:sunglasses: Finally, SSH using the key to steal the flag!
```!
$ ssh -i key.pem user@bro-key-n.chal.uiuc.tf -p 1337
Congratulations! You found my key - if you take a look at it carefully, you'll find the flag - replace slashes in the key with underscores to get your flag...:
uiuctf{hidden_in_plain_sight}
Connection to bro-key-n.chal.uiuc.tf closed.
```
## Solve files
[A list of files used to solve this challenge in a GitHub Gist](https://gist.github.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec)
## Trivia
The flag is **indeed** hidden in plain sight as its content suggests. If you search for `uiuctf` in the recovered key, you should see this (regardless of the order of $p$ and $q$):
This shows up on line 24 of the recovered key: [key.pem](https://gist.github.com/kevin-he-01/3e094654e0469226f1f62f75c46a6aec#file-key-pem-L24)
## Thoughts
Overall I enjoyed this challenge a lot. :tada: Kudos to the challenge author Husnain, and many thanks to Micheli and Heninger for their paper. I like the fact that the challenge requires a balanced mix of skills including OSINT (decoding ASN.1), crypto, math, and replicating the result of a paper (at least my solution).
This challenge reminded me of another crypto challenge that I authored for SDCTF 2022: [Key Recovery](https://github.com/acmucsd/sdctf-2022/tree/main/crypto/medium%20-%20key%20recovery). The idea behind both challenges is that you are given a partial SSH private key, but the goal of this challenge is more realistic: demonstrate the private key is compromised by logging into a real SSH server. The SDCTF challenge is easier in terms of the math needed and the difficulty lies in reconstructing the key the _exact_ same way as it is before redaction. Based on my experience doing CTF support, that is the part that annoys a lot of people.
As far as I know, the approach other people took (Ex. by [someone from idek](https://hackmd.io/cqdzQizWRvSzCwY926S1ZA) and by [someone from /bad](https://imp.ress.me/blog/2022-08-01/uiuctf-2022/#bro-key-n)) all use at least one part of a private key parameter other than $d_p$. Requiring only $n$, $e$, and $d_p$, my solution minimizes the amount of _manual_ parameter extractions.
This writeup is a demonstration of the power of lattice cryptanalysis, and how academic publications can be used as a CTF "tool".
## References
\[1\] Micheli, G.D., & Heninger, N. (2020). Recovering cryptographic keys from partial information, by example. _IACR Cryptol. ePrint Arch., 2020_, 1506.
Sign in with Wallet
Connect another wallet