Bro-Key-n

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

"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

key_redacted.pem

Solution

A summary of steps to get the flag:

Deobfuscate the private key format
Extract the known bits of private key parameters
Do the math: Using only the high bits of $d mod (p - 1)$ , perform a lattice cryptanalysis to factor $n$ into $p$ and $q$ .
Reassemble the SSH private key from $n, e, d, p, q$
SSH to host and capture the flag

Deobfuscation

The key to be recovered is an RSA private key in the standard PEM format, specified by RFC 8017. 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

The schema of the ASN.1 data is specified in RFC 8017 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
}

Throughout this writeup, we will refer to the private CRT exponent $d mod (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.

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 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 and comparing the offsets as I hover over the INTEGERs.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

To get myself familiar with the PEM format, I generated an RSA private key hopefully similar to key_redacted.pem before redaction:

ssh-keygen -m PEM -t rsa -b 4096 -f sample_4096.pem

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.
-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.

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 and my sample_4096.pem) into raw binary files using this script pem2bin.py:









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, I found $d_{p}$ at offset 1567 (0x61f) using lapo.it. 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.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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}$ :

Expand to see the leaks (? for unknown nibbles)

n = 0x125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227348916a4befeb306be79d75a8e4fac2f7d8591d7f7f1e5006eaff2d32e93fcb1a50cb5bd449a84840c71f9f0bad999aeeed500dc32b7092d0b021adde2859d53c604f4b1613880fb4ada66c5a19da058bc7a6646b935c4d28a321bad0a39bb387465775dbc2ad7184ce221bd0ebc3de0fc0e9574b952a0cd7c2718d0696ba2b2ac5122708cd9643c8a28b3916d47b28f46c6aed7e91df1a78278039b9197223d1a8b0e88f2ddc55766a28eeaaa571e4daa7f2132d4028015a372b78b04b775987b1f6a420f5ad96d30d76cc3d354199c968a85390c85d4e12c7aeb050b1b04f430b23725ec5c13d0340138f66c6acfa459461b4ebfbe5af2b2d6907b8fa782e1652514529fdf343667e6875d7d1498f3d80cb76524580b6f2af01142f15bb10e91366dd882f7738fb2c242b417a4f2e0cfa5cd6fd6b63d1972901df69b9d5c4817782494309e80954d1c90e975592a47cce447619f5a3d5b7612bb667bbb14e1774964b14ea97cea375f99f7a19da543a9b4e9a978bdbfb2fff8f35e8e9597473888cb12b2efef708d871489e7ddb3ca64997ac6f4ad29c7e13d3545eb056a2e872ce32f13df5ecedd25b7bdd7c32464306466d2e5b7e48af9ace8a81e429581ab377468c7f03103ef758eaefb79a740489926fd8f26334fda1d65
e = 65537 = 0x10001
d_p = 0x0c55acb5a46475e4fcb3fc012a26f3b896bc34f7f047035c610d3739b98ce50a146ec49127e5e8667352e06dac2bfa37224a47c29cd904b9e418bf4f8484f60594906ccedac2257de1cdc54453ba892d1e1a00fe8fc7e1b415dfe4c5055bcab0af08a335a6d9a934fa98644d884794621738f8783eeb975a8468134811d36cd9544c9ac47086ba8865c81155bcdc39fe5c1376a07a59934ff25e18554517e462927c6f85571249c3ca82c7dd8691707186de2ea6cb69ced941c6f5f90cfb5d4?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

"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 showed me her paper Recovering cryptographic keys from partial information, by example [1] 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:

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Indeed, Coppersmith's method in section 4.2.7 (Page 18) is what we are looking for: MSB of $d mod (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} mod 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{aligned} d_{p} \equiv d \mod (p - 1) & ⟹ e d_{p} \equiv 1 (\mod (p - 1)) \\ ⟹ e d_{p} = 1 + k_{p} (p - 1) for some 1 \leq k_{p} < e \\ ⟹ e (a + r) = 1 + k_{p} (p - 1) \\ ⟹ e (a + r) - 1 + k_{p} \equiv 0 (\mod p) \\ ⟹ e^{'} (e (a + r) + k_{p} - 1) \equiv 0 (\mod p) \\ ⟹ a + r + e^{'} (k_{p} - 1) \equiv 0 (\mod p) \end{aligned}$

Then let $A = a + e^{'} (k_{p} - 1)$ , then the above equation is reduced to $A + r \equiv 0 (\mod 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 (\mod 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 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 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:


















































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 to reconstruct the key from the parameters:
















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'))

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.

The recovered key (key.pem)

Capture the Flag

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

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

Thoughts

Overall I enjoyed this challenge a lot.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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. 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 and by someone from /bad) 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.

Bro-Key-n

Overview

Challenge Description

Attachments

Solution

Deobfuscation

Parameter extraction

Math time

Summary of methodology

Attack Implementation

Reassembly

Capture the Flag

Solve files

Trivia

Thoughts

References

Read more

Easy Math 3

A public note