How to recover RSA private key in a coredump of ssh-agent - Sapheads HackJam 2009 Challenge 6

Last week or so I joined CLGT to take part in HackJam 2009 by Sapheads. AFAIK this is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first CTF that Sapheads organizes, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y had done a very good job. To most people's surprise, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 contest attacted quite a lot of teams from around cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 world, and it had quickly become an international competition.

Did I tell you that we're cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 winner? Ha ha ha this is our very first win since cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 name CLGT was born.

BTW, HackJam 2009 was a success because Sapheads had kept cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir promise which is to "provide challenges that greatly resemble real world scenarios and environments, at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same time, adding fun and educational ingredients to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m". We really had fun ^_^, not disturbing pains *_*, in solving cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 challenges. Thank you Sapheads! We're looking forward to HackJam 2010.

I promised to some people in #sapheads that I would release some writeups about cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 challenges after cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 contest ended, and here cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are. Sorry for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 delay, I have been busy working with vendors on this which you may want to read too.

I'll post writeups of challenge 4, 6, 7, 8, 9 on this blog and CLGT's homepage in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 next two weeks. These are cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 challenges that I solved or helped to solve. I leave out challenge 1 and challenge 2 because cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are trivial. I was out or sleeping when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 team solved challenge 3 and 5, so I guess I don't write nothing about cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m eicá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r. You can download all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 binaries in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 contest here.

I hope you enjoy reading cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m as much as I enjoy writing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m.

-------

As cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 title of this entry suggests, this is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 writeup of challenge 6 which is IMHO cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coolest CTF challenge ever :-D. I really like its concept and implementation. Thank you whats ^_^!









For those who didn't take part in HackJam, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se two men are cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 criminals who had stolen and leaked a new album of SNSD (you should check cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se girls out ^_^). All teams are in charged of tracking cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m down.

As you can see in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 comic, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 criminals got a coredump when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y were trying to transfer a MP3 to his server at 67.202.60.164. And that coredump is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 only file given in challenge 6.

So first thing first:

$ file core.6261

core.6261: ELF 32-bit LSB core file Intel 80386, version 1 (SYSV), SVR4-style, from 'ssh-agent'

As you can see, this is a coredump of ssh-agent. This is from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 manpage of ssh-agent:

ssh-agent is a program to hold private keys used for public key aucá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ntication (RSA, DSA). The idea is that ssh-agent is started in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 beginning of an X-session or a login session, and all ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r windows or programs are started as clients to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ssh-agent program.


The manpage doesn't tell where ssh-agent stores private keys, but one can guess that it would store cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m in its memory. When ssh-agent crashes, all of its memory content would be written to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coredump. So I guess cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 idea of challenge 6 is to recover cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 private key of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 criminals stored in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coredump, and use that private key to SSH into 67.202.60.164 which may give me cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 key for challenge 7.

This is why Sapheads challenges are better than ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r CTFs. They don't try to distract us by giving false trails. They give good trails which can be deduced using logical thinking. This challenge also greatly resembles real world scenario which in turn makes it much more interesting than ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r non-sense challenges somehow created only to show that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir authors are smarter than ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rs.

Okie enough bullshit, let's get back to challenge 6. As whats from Sapheads suggests, I take a look at static variables of ssh-agent.c which are defined like below:

typedef struct identity {
TAILQ_ENTRY(identity) next;
Key *key;
char *comment;
u_int death;
u_int confirm;
} Identity;

typedef struct {
int nentries;
TAILQ_HEAD(idqueue, identity) idlist;
} Idtab;

/* private key table, one per protocol version */
Idtab idtable[3];

int max_fd = 0;

/* pid of shell == parent of agent */
pid_t parent_pid = -1;
u_int parent_alive_interval = 0;

/* pathname and directory for AUTH_SOCKET */
char socket_name[MAXPATHLEN];
char socket_dir[MAXPATHLEN];


So right above socket_name are 3 integers, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n comes idtable which contains pointers to Identity structures, which in turn contains pointers to Key structures. This is how a Key structure looks like (it's in openssh/key.h):

struct Key {
int type;
int flags;
RSA *rsa;
DSA *dsa;
};

Ah RSA structure! This is how it looks like (it's in openssl/rsa.h):

struct rsa_st
{
/* The first parameter is used to pickup errors where
* this is passed instead of aEVP_PKEY, it is set to 0 */
int pad;
long version;
const RSA_METHOD *meth;
/* functional reference if 'meth' is ENGINE-provided */
ENGINE *engine;
BIGNUM *n;
BIGNUM *e;
BIGNUM *d;
BIGNUM *p;
BIGNUM *q;
BIGNUM *dmp1;
BIGNUM *dmq1;
BIGNUM *iqmp;
/* be careful using this if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 RSA structure is shared */
CRYPTO_EX_DATA ex_data;
int references;
int flags;

/* Used to cache montgomery values */
BN_MONT_CTX *_method_mod_n;
BN_MONT_CTX *_method_mod_p;
BN_MONT_CTX *_method_mod_q;

/* all BIGNUM values are actually in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following data, if it is not
* NULL */
char *bignum_data;
BN_BLINDING *blinding;
BN_BLINDING *mt_blinding;
};

typedef bignum_st BIGNUM;
struct bignum_st
{
BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */
int top; /* Index of last used d +1. */
/* The next are internal book keeping for bn_expand. */
int dmax; /* Size of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 d array. */
int neg; /* one if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 number is negative */
int flags;
};


As one can expect, a RSA structure contains n, e, d, p, q and some ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r data. We need to get cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se numbers, which are stored in BIGNUM structures, out of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coredump. So cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 next thing to do is know where idtable is in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coredump. I load cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coredump into bless, my favourite hex editor (click on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 image to zoom in):


As you can see, at offset 0x13b0 is socket_name. Based on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 analysis of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 last paragraph, we can guess that max_fd, parent_pid, and parent_alive_interval are stored in 12 bytes between offset 0x13a4 and 0x13af. Then one can ask, what are those 16 null bytes from offset 0x1394 to 0x13a3? I don't know. If you know, please drop me a line. But I know for sure, idtable is stored in 36 bytes from offset 0x1370 to 0x1393, just right before those weird 16 null bytes.

The idtable array has 3 entries, one for each SSH protocol version. Each entry is an structure whose length is 12 bytes (hence 36 bytes for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 whole array). When ssh-agent starts, each Idtab is initiated like this:

TAILQ_INIT(&idtable.idlist);
idtable.nentries = 0;

where TAILQ_INIT is a macro defined in sys/queue.h as following:

#define TAILQ_INIT(head) do {
(head)->tqh_first = NULL;
(head)->tqh_last = &(head)->tqh_first;
} while (/*CONSTCOND*/0)


So after initiation, an Idtab structure would contain 1 zero integer for nentries, 1 null pointer for idlist.tqh_first, and 1 pointer for idlist.tqh_last which points back to idlist.tqh_first. Looking at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 coredump, one can see that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first two Idtab entries of idtable don't contain any key information because cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir nentries is 0. This is as expected, since SSH protocol 1 and 1.1 are long deprecated. The last entry of idtable is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Idtab of SSH protocol version 2. As one can see, its nenetries is 1, and we can guess that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 pointer 0x0806E3B8 is pointing to an identity structure which contains 4 pointers and 2 integers. Let's see if this is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 case:

$ gdb /usr/bin/ssh-agent core.6261

Core was generated by `/usr/bin/ssh-agent'.
[New process 6261]
#0 0xb7f55424 in __kernel_vsyscall ()
(gdb) x/6x 0x0806E3B8
0x806e3b8: 0x00000000 0x0806297c 0x0806e158 0x0806e3a8
0x806e3c8: 0x00000000 0x00000000
(gdb) x/s 0x0806e3a8
0x806e3a8: "id_rsa"

As you can see, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 4th pointer is comment. So cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 3rd pointer should be key, i.e. it should point to a Key structure which contains 2 integers and 2 pointerss:

(gdb) x/4x 0x0806e158
0x806e158: 0x00000001 0x00000000 0x0806e170 0x00000000

If everything is correct, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 pointer 0x0806e170 should point to a RSA structure:

(gdb) x/22x 0x0806e170
0x806e170: 0x00000000 0x00000000 0xb7ed5840 0x00000000
0x806e180: 0x0806e210 0x0806e228 0x0806e240 0x0806e288
0x806e190: 0x0806e270 0x0806e2b8 0x0806e2a0 0x0806e258
0x806e1a0: 0x00000000 0x00000000 0x00000001 0x0000000e
0x806e1b0: 0x00000000 0x00000000 0x00000000 0x00000000
0x806e1c0: 0x0806e950 0x00000000

How to be sure this is a RSA structure? Is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re any known value to test? Fortunately, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 answer is yes. If this is a RSA structure, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 6th pointer 0x0806e228 should point to a BIGNUM structure containing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 value of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 e parameter which should be 0x23, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 default value that ssh-keygen uses for e. Let's see:

(gdb) x/5x 0x0806e228
0x806e228: 0x0806e2e0 0x00000001 0x00000001 0x00000000
0x806e238: 0x00000001
(gdb) x/2x 0x0806e2e0
0x806e2e0: 0x00000023 0xb7d39150

Yay! We got it!

The next step is to extract all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 parameters. It was not as easy as it sounds though. I spent quite a lot of time to read out cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 value of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se parameters due to my ignorant of big-edian and little-edian storage. But I managed to get cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m out eventually. I generated cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 RSA private key from p and q, and used it to SSH into 67.202.60.164 which indeed gave me cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 key for challenge 7. I got my first breakthrough he he he.

That's it. Thanks for reading.

Err...but how to generate RSA private key from n, d, e, p and q? I'm glad that you ask. Tools like openssl can not help in this case. You must write your own tool. I suggest you taking a look at ASN.1. There's a very good tutorial here.

If you understand ASN.1, I'm pretty sure you'd know how to generate RSA private key from its parameters. You can use pyasn1 which is a very good ASN.1 library for Python. I can't release my tool because it's part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 upcoming CTF that I'm organizing. After that CTF, I'll update this post with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tool.

Comments

t1g3r said…
Thank you for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 write-up!
Also, good job in Hackjam :-)

Awesome hacker from Vietnam! ;)