CTF Team at the University of British Columbia

[TAMUCTF 2022] Lost in the Void

17 Apr 2022 by - desp


Author: Addison

Help! I’ve lost my private key somehow, and I need you to–

Okay, look, I was going to make a meaningful and CTF-y story for this challenge, but the scenario really wasn’t making sense. You just need to decrypt enc.bin. Here’s the source code we used to generate the challenge and a memory dump; good luck!


Understanding the challenge

We are given a core dump file, along with a rust source file for this challenge. The code is quite simple:

use rand::SeedableRng;
use rand_chacha::ChaChaRng;
use rsa::{PaddingScheme, PublicKey, RsaPrivateKey, RsaPublicKey};
use tokio::fs::File;
use tokio::io::{AsyncReadExt, AsyncWriteExt};
use tokio::process::Command;
use zeroize::Zeroizing;

async fn main() -> anyhow::Result<()> {
    let mut rng = ChaChaRng::from_entropy();
    let key = RsaPrivateKey::new(&mut rng, 4096)?;
    let pubkey = RsaPublicKey::from(&key);

        let mut plaintext = Zeroizing::new(Vec::new());
        File::open("flag.txt").await?.read_to_end(&mut plaintext).await?;

        let ciphertext = Zeroizing::new(pubkey.encrypt(&mut rng, PaddingScheme::PKCS1v15Encrypt, &plaintext)?);



We can see that it generates a random RSA key pair with the cryptographically secure ChaCha20 algorithm, reads the flag and encrypts it using the generated public key, then generates a core dump.

One thing of note here is that both the plaintext and ciphertext is zeroizing, and the scope ended before the gcore command is invoked - this means that we are highly unlikely to be able to obtain the flag in the core dump itself, and we will actually have to obtain the key pair to solve this challenge. Grepping for the flag proves this right:

$ grep 'gigem' core.4179

To reconstruct a RSA private key in most languages, we would need the modulus n, the public exponent e, and the private exponent d. Since n is made of 2 very large primes p and q, we can use a prime finder and recover the rest of the data using some maths.

Or alternatively, we can just figure out how rust structures work and grab the components ourselves. Totally not because I didn’t even think of that method until I talked with the author Addison himself after the ctf ended. Yep.

Rust & Structs

To be able to understand where to obtain the data directly from the core dump, we first need to know how the data is represented in memory. Since we only have the source code, not a compiled binary, the first thing to do is to compile it - with a quick run of cargo init, copy main.rs to the src directory, and add the required dependencies to Cargo.toml:

rand = "0.8"
rand_chacha = "0.3"
tokio = {version = "1.17.0", features = ["full"]}
anyhow = "1"
rsa = "0.5"
zeroize = "1"

We can then run cargo build and obtain the resultant binary. Note that this binary is probably not identical to the one used to generate the core dump due to potential version differences, but the data structures should be similar enough for us to identify a pattern. Let’s breakpoint at right after the key is generated, and run it in a debugger to see what it looks like:


Hmm, seems like v29 is the variable we want, but yikes - what even is gap0? Even with DWARF debug information, it is not doing much good for us:

v29 - core::result::Result<rsa::key::RsaPrivateKey,rsa::errors::Error>:

But wait - if we look closer at the hex view, it looks like there are multiple pointers in the struct. Will those be pointing to what we are looking for, and why is it just a giant blob of data even with DWARF? Turns out, gap0 represents all dynamically changing data types that might have different data types in it depending on situation. For example, std::Result can store either a rsa::key::RsaPrivateKey or a rsa::errors::Error blob, even though we don’t really care about data containing the error type usually. If we can fix the struct declaration to the one we want to analyse, we can most likely obtain the correct values and their offset without needing to guess, which we can then map to that in the core dump.

Luckily for us, there is a cheat sheet for some of the common internal representations of rust structures. From there, we can see that std::Result basically prepends a usize tag, which is 8 bytes in a 64 bit system, to the data that it stores if it succeeded, which is rsa::key::RsaPrivateKey for our case.

In IDA, we can achieve this by first utilizing expand struct type to expand by 8 byte (size of __int64) and converting it into data, set type to __int64, then select struct var on gap0 to convert it to rsa::key::RsaPrivateKey (field_0 and gap_0 has also been renamed to tag and keydata for clarity):


Looking much more structural now! It also matches the struct layout defined in the official source code for rsa::key::RsaPrivateKey and rsa::key::RsaPublicKey:

pub struct RSAPublicKey {
    n: BigUint,
    e: BigUint,

/// Represents a whole RSA key, public and private parts.
#[derive(Debug, Clone)]
    feature = "serde",
    derive(Serialize, Deserialize),
    serde(crate = "serde_crate")
pub struct RSAPrivateKey {
    /// Public components of the private key.
    pubkey_components: RSAPublicKey,
    /// Private exponent
    pub(crate) d: BigUint,
    /// Prime factors of N, contains >= 2 elements.
    pub(crate) primes: Vec<BigUint>,
    /// precomputed values to speed up private operations
    #[cfg_attr(feature = "serde", serde(skip))]
    pub(crate) precomputed: Option<PrecomputedValues>,

However, some of the data is still not yet matched with the same gap0 issue, especially the ones that are of the SmallVecData<u64_ 4> type, which holds the component data. At this point we can already vaguely guess what the values and pointers are for, but just to be safe, let’s go a step further and fix that too.

As defined in the smallvec source code, it has a 1 byte tag, along with either inlined data up to 4 u64 ints, or a u64 heap pointer (usize) and a usize capacity int:

pub struct SmallVec<A: Array> {
    // The capacity field is used to determine which of the storage variants is active:
    // If capacity <= Self::inline_capacity() then the inline variant is used and capacity holds the current length of the vector (number of elements actually in use).
    // If capacity > Self::inline_capacity() then the heap variant is used and capacity holds the size of the memory allocation.
    capacity: usize,
    data: SmallVecData<A>,


#[cfg(feature = "union")]
union SmallVecData<A: Array> {
    inline: MaybeUninit<A>,
    heap: (*mut A::Item, usize),

Since everything is a u64 on 64 bit systems, we can just set it to an __int64* u64[4] pointer array with an __int64 tag at the front in IDA for a good enough generalization that shows both literal values and a portion of the dereferenced values. With that, we can finally obtain a good view of what each value means:


From the memory location column, we can infer the following:

To verify if we set the struct correctly, let’s debug print the private key generated by adding the line println!("{:?}", key); in the source and compiling, and compare it with the debugging values we obtain from the struct data in IDA:


(omitted unrelated data and slightly reformatted for clarity.)

4959635403563789489 is 0x44D42A1F4CDEECB1, 65537 is 0x10001, and 11540142137781311521 is 0xA026D221CBF8D821

Yep - looks the same to me! With that, we can finally move on to applying the offsets to the core dump itself.

Pointer chasing

Firing up gdb, we can see which function frame we are currently at, along with the register values:

Core was generated by `./target/release/lost-in-the-void'.
#0  0x00007fbd96c0376d in ?? ()
[Current thread is 1 (LWP 4179)]
Use `info auto-load python-scripts [REGEXP]' to list them.
(gdb) i r
rax            0xfffffffffffffe00  -512
rbx            0x7fbd96c03750      140452254725968
rcx            0x7fbd96c0376d      140452254725997
rdx            0x1                 1
rsi            0x80                128
rdi            0x7fbd96aea458      140452253574232
rbp            0x3c0               0x3c0
rsp            0x7ffc61daa4a8      0x7ffc61daa4a8
r8             0xffffffffffffffff  -1
r9             0x7fbd96aea438      140452253574200
r10            0x0                 0
r11            0x246               582
r12            0xf7474439f8b86d68  -628458607218234008
r13            0x7fbd96aea458      140452253574232
r14            0x55f5c67068c0      94514084604096
r15            0x55f5c6706500      94514084603136
rip            0x7fbd96c0376d      0x7fbd96c0376d
eflags         0x246               [ PF ZF IF ]
cs             0x33                51
ss             0x2b                43
ds             0x0                 0
es             0x0                 0
fs             0x0                 0
gs             0x0                 0

Since it calls gcore by invoking Command::spawn, along with potential version differences, we cannot guarantee that the variable offsets from the stack pointer is gonna be the same. However, it should be in a similar offset from rsp as v29 is, aka $rsp+0x2D0 - we can just look around that general location for the tag and capacity values that will not change since the key sizes are fixed.

(gdb) x/64xb $rsp+0x2D0
0x7ffc61daa778: 0x93    0x5a    0x5d    0x9c    0xfb    0xfc    0x7c    0xc6
0x7ffc61daa780: 0xe9    0xd1    0x6d    0x27    0x4b    0x83    0x31    0x7b
0x7ffc61daa788: 0x0e    0xc2    0x27    0x57    0x7c    0xb7    0x75    0x32
0x7ffc61daa790: 0xe0    0x05    0x00    0x00    0x00    0x00    0x00    0x00
0x7ffc61daa798: 0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7ffc61daa7a0: 0x41    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7ffc61daa7a8: 0x01    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7ffc61daa7b0: 0x60    0xf0    0x6f    0xc6    0xf5    0x55    0x00    0x00

Hey, doesn’t 0x7ffc61daa798 look like the start of the struct, with tag 0, capacity 41 and tag 1? Let’s go to the offsets and grab the data we need.

(gdb) x/g 0x7ffc61daa798+0x18
0x7ffc61daa7b0: 0x000055f5c66ff060
(gdb) x/512xb 0x000055f5c66ff060
0x55f5c66ff060: 0x79    0x7c    0xfa    0x9c    0x7a    0xdc    0x07    0xfb


0x55f5c66ff258: 0x88    0x15    0x6b    0x82    0x16    0x2d    0xaf    0xd9
(gdb) x/g 0x7ffc61daa798+0x78
0x7ffc61daa810: 0x000055f5c6700450
(gdb) x/512xb 0x000055f5c6700450
0x55f5c6700450: 0x0d    0xb7    0x5c    0x2a    0x4d    0x2b    0xd2    0x08


0x55f5c6700648: 0xee    0xd8    0x4d    0xb5    0xf7    0x1d    0x60    0x4d

Seems like all 512 bytes (4096 bit as set in the RSAPrivateKey constructor) for both n and d are populated, which is exactly what we want to see! Time to whip up a script using the bytes we got and try to decrypt enc.bin:

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from base64 import b64encode, b64decode

# from dereferencing 512 bytes at rsp+0x2F0 + 0x18
n = bytes([0x79, 0x7c, 0xfa, 0x9c, 0x7a, 0xdc, 0x07, 0xfb, 0xc6, 0x7a, 0x55, 0xe0, 0x91, 0x07, 0xee, 0x58,
0xba, 0x0f, 0x85, 0x60, 0xae, 0x79, 0x2c, 0x24, 0x6d, 0xd4, 0x32, 0x5c, 0x23, 0x63, 0xb3, 0xf0,
0x23, 0xa6, 0x04, 0x46, 0xca, 0xb8, 0x7f, 0xb9, 0x41, 0xf2, 0xc9, 0x12, 0xdc, 0x75, 0x71, 0x18,
0x0c, 0xf0, 0x56, 0x5b, 0x1b, 0xc6, 0xe0, 0x94, 0x9b, 0x08, 0x58, 0x86, 0x02, 0xf6, 0xfa, 0x0c,
0x55, 0x0c, 0x1c, 0x3b, 0x65, 0xcd, 0x22, 0xcc, 0x6b, 0xa3, 0x37, 0x8b, 0x6c, 0x47, 0x6d, 0xb1,
0xca, 0x5f, 0x78, 0xc6, 0x60, 0x1c, 0x57, 0x88, 0x04, 0xfa, 0x39, 0xb7, 0x7e, 0xcc, 0x22, 0x0c,
0x92, 0x61, 0xfa, 0x51, 0xf0, 0xd4, 0x99, 0xbb, 0x07, 0xfd, 0x47, 0xbd, 0x43, 0x06, 0xc4, 0x0f,
0xf0, 0xd3, 0x3d, 0x88, 0x37, 0x6e, 0x8c, 0x0d, 0x31, 0xdc, 0xef, 0xea, 0x18, 0x3f, 0x2b, 0x9a,
0x0c, 0x97, 0x16, 0x3e, 0xa3, 0xce, 0x46, 0xee, 0xc2, 0xeb, 0x17, 0xc0, 0xc6, 0x58, 0x18, 0x4e,
0x4e, 0xcd, 0x07, 0x31, 0xf9, 0x1e, 0xc3, 0xa1, 0xf6, 0xe9, 0xe0, 0xa3, 0xc7, 0x05, 0x9c, 0x9e,
0x76, 0xd4, 0x16, 0x64, 0x6a, 0x82, 0xa0, 0xc1, 0xf2, 0xd9, 0xa9, 0x7e, 0x39, 0x0c, 0x75, 0xaa,
0xf4, 0x36, 0x7d, 0xe6, 0xac, 0x1e, 0xdc, 0xf3, 0x2c, 0x24, 0xeb, 0x43, 0x8d, 0xe7, 0x11, 0xc3,
0xc5, 0x75, 0x2b, 0xea, 0x78, 0x81, 0x37, 0x38, 0x02, 0x12, 0xd3, 0x60, 0xd9, 0x0c, 0x25, 0x01,
0x3a, 0xbe, 0x00, 0x75, 0xa0, 0xb4, 0x1c, 0xfc, 0xff, 0xb7, 0x0f, 0x25, 0x18, 0xe3, 0x3e, 0x44,
0x3e, 0xe8, 0x75, 0x20, 0x9e, 0x63, 0x80, 0x2a, 0xc7, 0xe2, 0x53, 0x5b, 0xd1, 0x33, 0x44, 0x2c,
0x60, 0x19, 0x1b, 0xe8, 0x29, 0x85, 0xb1, 0xff, 0x8e, 0x70, 0x4b, 0xc5, 0xc8, 0xfd, 0x06, 0x54,
0xa8, 0x3d, 0x20, 0xb8, 0x67, 0x8c, 0xf8, 0x64, 0x50, 0x31, 0x17, 0x34, 0xc7, 0x46, 0xc8, 0x07,
0xfe, 0xd5, 0x82, 0x99, 0xc2, 0xa9, 0xa5, 0xb8, 0xb3, 0x3b, 0x36, 0xf7, 0x06, 0x68, 0x12, 0x6b,
0xfa, 0x4c, 0x5d, 0x5d, 0x62, 0x02, 0x0f, 0x81, 0xae, 0x2a, 0xc7, 0x2e, 0xab, 0x1b, 0xf6, 0x79,
0xe8, 0x7c, 0xf3, 0x3e, 0x78, 0x6e, 0x87, 0x9a, 0xec, 0x8b, 0x93, 0x46, 0x80, 0x6e, 0xae, 0x3a,
0x04, 0xc3, 0xd6, 0x1b, 0xbb, 0x6a, 0x16, 0x3f, 0x93, 0x4c, 0x2d, 0xcc, 0x81, 0xb2, 0x15, 0xbf,
0xa6, 0x7b, 0xb7, 0xa4, 0x3b, 0xb4, 0x72, 0x61, 0xd9, 0x01, 0x4d, 0x03, 0x73, 0x5d, 0xb8, 0x9b,
0x8a, 0x8d, 0x7c, 0x13, 0x86, 0x06, 0x11, 0xa3, 0x7d, 0x05, 0x9a, 0x06, 0xfe, 0xbd, 0x28, 0x52,
0x64, 0x3c, 0x32, 0xae, 0xf9, 0x60, 0x3e, 0x57, 0x56, 0x6c, 0xa8, 0xca, 0xe6, 0xf9, 0x7a, 0x02,
0x56, 0x4c, 0xab, 0xce, 0xb2, 0xf0, 0x99, 0x83, 0xc1, 0x0e, 0x28, 0x33, 0x94, 0xbc, 0x16, 0xd7,
0x22, 0xc2, 0x5e, 0x72, 0x76, 0x6a, 0xef, 0xd7, 0x85, 0xc2, 0x7e, 0x6d, 0xa9, 0xa8, 0x38, 0xab,
0x13, 0x2d, 0x4a, 0x26, 0xe2, 0xde, 0xa0, 0x4a, 0xf3, 0xda, 0x09, 0x78, 0x04, 0x4a, 0xe0, 0x47,
0xc6, 0x13, 0x5a, 0xe7, 0x9b, 0x27, 0x6e, 0x0b, 0x6f, 0xe9, 0x51, 0xab, 0x5b, 0x29, 0x86, 0xc0,
0xb3, 0x5e, 0xdd, 0x23, 0x12, 0x70, 0xc6, 0x4c, 0x19, 0x53, 0xb4, 0xce, 0x1c, 0x6b, 0x24, 0xdf,
0x8c, 0x1b, 0x7a, 0x1c, 0x73, 0x3c, 0xdf, 0x51, 0x7c, 0xa2, 0x30, 0x00, 0xae, 0x57, 0x2d, 0x02,
0xe1, 0xbc, 0x97, 0x10, 0x7a, 0x47, 0x1e, 0xc0, 0xae, 0xc2, 0xf5, 0xb1, 0xe8, 0x48, 0xa2, 0x83,
0x18, 0xcb, 0xa5, 0x20, 0xc0, 0x67, 0x28, 0x1e, 0x88, 0x15, 0x6b, 0x82, 0x16, 0x2d, 0xaf, 0xd9])

# from dereferencing 512 bytes at rsp+0x2F0 + 0x78
d = bytes([0x0d, 0xb7, 0x5c, 0x2a, 0x4d, 0x2b, 0xd2, 0x08, 0xd5, 0xb4, 0xd1, 0x95, 0x3a, 0xd3, 0xaf, 0xb5,
0xf3, 0xe8, 0x35, 0xa4, 0x7b, 0x05, 0x00, 0xe4, 0xe9, 0xba, 0x94, 0xb3, 0x9e, 0x6b, 0xa0, 0x98,
0xaa, 0x0a, 0x58, 0x6e, 0x36, 0x3b, 0xe6, 0xb3, 0x75, 0x69, 0xf2, 0xbb, 0xc0, 0x25, 0x88, 0x4a,
0x5c, 0x3c, 0x04, 0x4b, 0xa4, 0x56, 0xd9, 0xc2, 0x8c, 0x7e, 0xc6, 0xf7, 0xb8, 0x8d, 0x85, 0x1d,
0x05, 0x34, 0x31, 0x97, 0xc1, 0xb5, 0xca, 0xf1, 0xa0, 0x6d, 0x0a, 0xd3, 0xd7, 0x4a, 0xf7, 0xde,
0x98, 0x5a, 0x4c, 0x18, 0xf3, 0x0d, 0xc2, 0x3d, 0x58, 0x24, 0xc2, 0x25, 0x93, 0x3f, 0x34, 0x02,
0xa8, 0xe9, 0x38, 0x54, 0x33, 0x52, 0x6e, 0xc4, 0xfa, 0xa3, 0x87, 0x73, 0x97, 0xed, 0x82, 0x12,
0x7f, 0xec, 0x88, 0x02, 0x85, 0x31, 0xf1, 0x9c, 0xc1, 0xea, 0xdb, 0x87, 0xef, 0x91, 0xc6, 0x20,
0xa3, 0x89, 0x3b, 0xa0, 0x5a, 0x71, 0x42, 0x13, 0x82, 0xff, 0xeb, 0x2e, 0xb6, 0x05, 0xe5, 0xcd,
0xa2, 0xf4, 0x9d, 0xd6, 0x9f, 0x03, 0xd4, 0x2c, 0x1a, 0x02, 0x00, 0x79, 0x83, 0x83, 0x47, 0x72,
0xae, 0x88, 0x33, 0x4d, 0xd1, 0x67, 0xf0, 0xf2, 0xa6, 0x31, 0x04, 0xa3, 0x27, 0x68, 0x72, 0x8e,
0x63, 0xe9, 0x17, 0xd8, 0xa5, 0x05, 0xe1, 0xb3, 0x56, 0x97, 0x94, 0x79, 0x50, 0x31, 0x40, 0x39,
0xb2, 0x96, 0xe8, 0x52, 0x96, 0x42, 0x9e, 0x4d, 0xf9, 0xd9, 0x25, 0xbc, 0x1e, 0x68, 0xf4, 0xfe,
0x81, 0xc4, 0x9d, 0x71, 0xc7, 0xf2, 0xd9, 0xf6, 0x3b, 0x5f, 0x10, 0xf3, 0x72, 0xad, 0x31, 0xca,
0x2d, 0xca, 0xe8, 0x7b, 0xd2, 0x56, 0x32, 0x5b, 0x54, 0xf6, 0x8f, 0x9b, 0x0a, 0xe1, 0x0e, 0x38,
0x42, 0x15, 0xae, 0xd3, 0xae, 0x79, 0x2d, 0x00, 0x39, 0xaa, 0xee, 0xfc, 0x83, 0x97, 0xef, 0x79,
0x6b, 0x76, 0x5e, 0x47, 0xad, 0x0a, 0x43, 0xea, 0x50, 0x78, 0x1f, 0x92, 0x9d, 0xf6, 0xc2, 0x32,
0x03, 0x44, 0x8b, 0xa4, 0x43, 0xde, 0x6e, 0x4c, 0x80, 0x5a, 0x82, 0xf5, 0x56, 0x1c, 0x91, 0x03,
0x84, 0xb3, 0x7b, 0x19, 0x52, 0xdb, 0x77, 0xf9, 0xb9, 0xe3, 0xaa, 0xb9, 0x4a, 0x04, 0x95, 0xfd,
0xdc, 0x28, 0x96, 0x25, 0x52, 0x2a, 0x6b, 0x5f, 0x96, 0x2f, 0x93, 0xfc, 0x02, 0x2e, 0x96, 0x98,
0x41, 0x25, 0x3a, 0x16, 0xf0, 0x01, 0xea, 0xb6, 0xef, 0x53, 0x1b, 0xfa, 0xf6, 0x76, 0x67, 0x80,
0xde, 0x49, 0x5e, 0x4a, 0xf3, 0x34, 0xab, 0x2f, 0x1f, 0x14, 0x3c, 0x48, 0x7d, 0x3c, 0x02, 0xb1,
0xcd, 0x06, 0x06, 0x2c, 0x61, 0x76, 0xdf, 0xf3, 0x99, 0xaf, 0xbf, 0x09, 0x9b, 0x84, 0xc5, 0xa4,
0x0a, 0xc8, 0x3a, 0x65, 0xb7, 0xfa, 0x82, 0xda, 0x29, 0x6a, 0xb0, 0xa9, 0x72, 0x66, 0xe7, 0x4d,
0xa4, 0xf8, 0xd2, 0x1c, 0xf1, 0x81, 0x04, 0xb3, 0x01, 0x08, 0x15, 0x02, 0x86, 0xef, 0x6b, 0x4e,
0xe6, 0x51, 0xbd, 0xea, 0x73, 0xc5, 0x74, 0x7d, 0xc7, 0x53, 0xdf, 0x4d, 0x63, 0x43, 0x58, 0x35,
0x71, 0x9b, 0x4a, 0x9c, 0x6f, 0xe8, 0x29, 0xfc, 0x69, 0xa4, 0x60, 0x64, 0x46, 0xe8, 0x28, 0x8a,
0x9d, 0xdd, 0x0f, 0x40, 0x91, 0x03, 0x15, 0x19, 0x8c, 0x76, 0x1c, 0xfc, 0x6d, 0x70, 0xbf, 0x7f,
0xfc, 0x06, 0xd0, 0x85, 0xdd, 0x7c, 0x32, 0xc0, 0xfe, 0xea, 0xd6, 0x5f, 0x86, 0x72, 0x68, 0xa0,
0x5c, 0x57, 0xf4, 0xf3, 0xb7, 0xba, 0xe5, 0x4d, 0xb8, 0x40, 0xd9, 0x08, 0x8a, 0x79, 0x73, 0xa2,
0x71, 0x9c, 0x1a, 0x43, 0x51, 0xd9, 0xf8, 0x29, 0xa3, 0x31, 0x9b, 0x78, 0xbe, 0xf5, 0x89, 0x36,
0x28, 0xb5, 0x63, 0x19, 0x77, 0xca, 0x41, 0x74, 0xee, 0xd8, 0x4d, 0xb5, 0xf7, 0x1d, 0x60, 0x4d])

# default e is 65537
rsa_key = RSA.construct((int.from_bytes(n, 'little'), 65537, int.from_bytes(d, 'little')))
cipher = PKCS1_v1_5.new(rsa_key)
raw_cipher_data = open('enc.bin', "rb").read()
print(cipher.decrypt(raw_cipher_data, None))

There we go - gigem{a_familiar_treasure_hunt}!