Featured Post

Có một Biển Đông trên không gian mạng

Có một Biển Đông trên không gian mạng Thái Dương Mùa hè 2014, giữa lúc người Việt trong nước và hải ngoại đang sôi sục vì Trung Quốc đư...

Thursday, September 24, 2009

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 the first CTF that Sapheads organizes, but they had done a very good job. To most people's surprise, the contest attacted quite a lot of teams from around the world, and it had quickly become an international competition.

Did I tell you that we're the winner? Ha ha ha this is our very first win since the name CLGT was born.

BTW, HackJam 2009 was a success because Sapheads had kept their promise which is to "provide challenges that greatly resemble real world scenarios and environments, at the same time, adding fun and educational ingredients to them". We really had fun ^_^, not disturbing pains *_*, in solving the 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 the challenges after the contest ended, and here they are. Sorry for the 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 the next two weeks. These are the challenges that I solved or helped to solve. I leave out challenge 1 and challenge 2 because they are trivial. I was out or sleeping when the team solved challenge 3 and 5, so I guess I don't write nothing about them either. You can download all the binaries in the contest here.

I hope you enjoy reading them as much as I enjoy writing them.


As the title of this entry suggests, this is the writeup of challenge 6 which is IMHO the coolest CTF challenge ever :-D. I really like its concept and implementation. Thank you whats ^_^!

For those who didn't take part in HackJam, these two men are the criminals who had stolen and leaked a new album of SNSD (you should check these girls out ^_^). All teams are in charged of tracking them down.

As you can see in the comic, the criminals got a coredump when they were trying to transfer a MP3 to his server at And that coredump is the 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 the manpage of ssh-agent:

ssh-agent is a program to hold private keys used for public key authentication (RSA, DSA). The idea is that ssh-agent is started in the beginning of an X-session or a login session, and all other windows or programs are started as clients to the ssh-agent program.

The manpage doesn't tell where ssh-agent stores private keys, but one can guess that it would store them in its memory. When ssh-agent crashes, all of its memory content would be written to the coredump. So I guess the idea of challenge 6 is to recover the private key of the criminals stored in the coredump, and use that private key to SSH into which may give me the key for challenge 7.

This is why Sapheads challenges are better than other 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 other non-sense challenges somehow created only to show that their authors are smarter than others.

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 then 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 *dmp1;
BIGNUM *dmq1;
BIGNUM *iqmp;
/* be careful using this if the RSA structure is shared */
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 the 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 the d array. */
int neg; /* one if the number is negative */
int flags;

As one can expect, a RSA structure contains n, e, d, p, q and some other data. We need to get these numbers, which are stored in BIGNUM structures, out of the coredump. So the next thing to do is know where idtable is in the coredump. I load the coredump into bless, my favourite hex editor (click on the image to zoom in):

As you can see, at offset 0x13b0 is socket_name. Based on the analysis of the 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 the whole array). When ssh-agent starts, each Idtab is initiated like this:

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 the coredump, one can see that the first two Idtab entries of idtable don't contain any key information because their nentries is 0. This is as expected, since SSH protocol 1 and 1.1 are long deprecated. The last entry of idtable is the Idtab of SSH protocol version 2. As one can see, its nenetries is 1, and we can guess that the pointer 0x0806E3B8 is pointing to an identity structure which contains 4 pointers and 2 integers. Let's see if this is the 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, the 4th pointer is comment. So the 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, the 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 there any known value to test? Fortunately, the answer is yes. If this is a RSA structure, the 6th pointer 0x0806e228 should point to a BIGNUM structure containing the value of the e parameter which should be 0x23, the 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 the parameters. It was not as easy as it sounds though. I spent quite a lot of time to read out the value of these parameters due to my ignorant of big-edian and little-edian storage. But I managed to get them out eventually. I generated the RSA private key from p and q, and used it to SSH into which indeed gave me the 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 the upcoming CTF that I'm organizing. After that CTF, I'll update this post with the tool.

Monday, September 14, 2009

Flickr's API Signature Forgery Vulnerability

Flickr's API Signature Forgery Vulnerability

Thai Duong and Juliano Rizzo

Date Published: Sep. 28, 2009

Advisory ID: MOCB-01

Advisory URL: http://netifera.com/research/flickr_api_signature_forgery.pdf

Title: Flickr's API Signature Forgery Vulnerability

Remotely Exploitable: Yes

1. Vulnerability Description

Flickr is almost certainly the best online photo management and sharing application in the world. As of June 2009, it claims to host more than 3.6 billion images. In order to allow independent programmers to expand its services, Flickr offers a fairly comprehensive web-service API that allows programmers to create applications that can perform almost any function a user on the Flickr site can do.

The Flickr's API consists of a set of callable methods, and some API endpoints. To perform an action using the Flickr's API, you need to select a calling convention, send a request to its endpoint specifying a method and some arguments, and will receive a formatted response.

Many methods require the user to be logged in. At present there is only one way to accomplish this. Users should be authenticated using the Flickr Authentication API. Any applications wishing to use the Flickr Authentication API must have already obtained a Flickr's API Key. An 8-byte long 'shared secret' for the API Key is then issued by Flickr and cannot be changed by the users. This secret is used in the signing process, which is required for all API calls using an authentication token. In addition, calls to the flickr.auth.* methods and login URLs pointing to the auth page on Flickr must also be signed. For more details, please read the Flickr Authentication API Spec [1].

This advisory describes a vulnerability in the signing process that allows an attacker to generate valid signatures without knowing the shared secret. By exploiting this vulnerability, an attacker can send valid arbitrary requests on behalf of any application using Flickr's API. When combined with other vulnerabilities and attacks, an attacker can gain access to accounts of users who have authorized any third party application. Additionally, if an application uses PHPFlickr >= 1.3.1, an attacker can trick users of that application to visit arbitrary web sites. This may apply for other Flickr's API libraries and applications as well.

2. Vulnerable Web Services

A lot of other web sites provide API service whose architecture is the same as Flickr's API. They are potentially vulnerable. We don't have a complete list, but here are some notable web sites:

* DivShare http://www.divshare.com/

* iContact http://www.icontact.com/

* Mindmeister http://www.mindmeister.com/

* Myxer http://www.myxer.com/

* Remember The Milk http://www.rememberthemilk.com/

* Scribd http://www.scribd.com/

* Vimeo http://www.vimeo.com/

* Voxel http://www.voxel.net/

* Wizehive http://www.wizehive.com/

* Zooomr http://www.zooomr.com/

Please note that we haven't tested these web sites. They are included here because they describe the same signing process in their API documentation.

3. Vendor Information

An initial notification was sent to Yahoo! Flickr on Sep. 5, 2009. A copy of this advisory was sent to Yahoo! Flickr on Sep. 13, 2009. Yahoo! Flickr replied on Sep. 14, 2009 to acknowledge the vulnerability. Yahoo! Flickr sent us an email on Sep. 23, 2009 to say that they were going to deploy a fix in the same week.

An initial notification was sent to the vendors listed in Section 2 on Sep. 17, 2009. Another copy of this advisory was sent to them on Sep. 24, 2009. Here are the responses from some of them:

* Remember The Milk said that they have investigated and confirmed that the Remember The Milk API is not vulnerable to this particular known issue.

* Vimeo tried to fix the issue by making sure that the first parameter after sorting is always api_key and failing if it isn't. This fix doesn't work because we can make the first parameter be api_key and still append new data to the request.

No other vendor provided details about their plans to deploy fixes.

4. Credits

This vulnerability was found and researched by Thai Duong from VNSecurity/HVAOnline and Juliano Rizzo from Netifera. Greeting to all members of VNSecurity, HVAOnline and Netifera.

The authors would like to thank Huong L. Nguyen, rd, Gunther, Bruce Leidl, and Alex Sotirov for reading and editing the draft of this advisory.

5. Technical Description

In Section 5.1 we introduce Flickr's API request signing process and its vulnerabilities. In Section 5.2 we describe the length-extension attack against Merkle-Damgård hash. In Section 5.3 we describe our attack against Flickr's API. In Section 5.4 we discuss some exploitations, and finally in Section 5.5 we suggest some solutions that may help to fix the vulnerability.

5.1 Flickr's API Request Signing Process

Flickr requires that all API calls using an authentication token must be signed. In addition, calls to the flickr.auth.* methods and the URLs that bring users to the application authorization page must also be signed. The process of signing is as follows.

* Sort your argument list into alphabetical order based on the parameter name.

* e.g. foo=1, bar=2, baz=3 sorts to bar=2, baz=3, foo=1

* concatenate the shared secret and argument name-value pairs

* e.g. SECRETbar2baz3foo1

* calculate the md5() hash of this string

* append this value to the argument list with the name api_sig, in hexadecimal string form, e.g. api_sig=1f3870be274f6c49b3e31a0c6728957f

There are two vulnerabilities in this signing process:

  • As there are no delimiters between the keys and values, the signature for "foo=bar" is identical to the signature for "foob=ar"; moreover, the signature for "foo=bar&fooble=baz" is the same as the signature for "foo=barfooblebaz". See [2] for a similar vulnerability of Amazon Web Service.

  • As MD5 is vulnerable to length-extension attack (see Section 5.2), one can append arbitrary data to the request yet still can generate valid signature without knowing the secret key. When combining with the first vulnerability, one can easily forge any request on behalf of any Flickr application.

5.2 Length-Extension Attack On MD5

In short, the length-extension attack on one-way hash construction is that you can, given h(m) and len(m), you are able to compute h(m||pad(m)||m') for any m' (|| stands for concatenation), even if you don't know the entire m. This attack works on all Merkle-Damgård hash (see [4, 5]) such as MD0-MD5 and SHA0-SHA2. This is also called "message extension" or "padding" attack (see [6]). The rest of this section describes how this attack works on Flickr's API's MD5 signature. What follows is technical. You may want to skip reading it until you need it.

MD5 ([3]) follows the Merkle/Damgård iterative structure, where the hash is computed by the repeated application of a compression function to successive blocks of the message. (See Figure 1.) For MD5, the compression function takes two inputs — a 128-bit chaining value and a 512-bit message block — and produces as output a new 128-bit chaining value, which is input into the next iteration of the compression function. The message to be hashed is first padded to a multiple of 512 bits, and then divided into a sequence of 512-bit message blocks. Then the compression function is repeatedly applied, starting with an initial chaining value and the first message block, and continuing with each new chaining value and successive message blocks. After the last message block has been processed, the final chaining value is output as the hash of the message.

Figure 1. Merkle-Damgård hash construction (copied from Wikipedia)

According to [7], because of the iterative design, it is possible, from only the hash of a message and its length, to compute the hash of longer messages that start with the initial message and include the padding required for the initial message to reach a multiple of 512 bits. (See Figure 2.) Applying this to Flickr's API request signature, it follows that from MD5 (SECRET||m), one can compute MD5 (SECRET||m') for any m' that starts with m||p, where p is the Merkle-Damgård padding on SECRET||m. To compute p, one just needs to know the length of SECRET||m, which is easy to calculate in Flickr's API's case. In other words, from the signature of m, one can forge the API signature of m||p||x for any x, without even knowing the shared secret key, and without breaking MD5 in any sense.

Figure 2. Length-extension attack on MAC = MD(KEY||msg) (copied from [9])

5.3 Our Attack

As described in Section 5.2 we require a message m and its signature to produce a longer message with a valid signature. It is easy to obtain a request signed by the target third party application provider.

Flickr and many other Web 2.0 sites allows users to share data with third party applications without divulging the user's credentials. Users are transported to the Flickr web site where they are asked whether he/she wants to allow the application to access their data. To achieve this the application providers ask the user to follow a link like this:


The api_key 16 bytes value identifies the application asking for permissions and api_sig is the signature of the request calculated using the secret shared between the application's developer and Flickr. This link is called login URL and is also a signed message which is all we need to perform the attack.

And we start working on our message forgery code, let's see what we have:

Message: SECRETapi_key[api_key]permsread (sorted and concatenated without '&=')
Signature: [api_sig]
Length: Length of Message + Length of SECRET

SECRET is the shared secret that Flickr and application owner don't want to share with us and that we don't need anyway.

Although the length of the padding is always between 9 and 64 bytes we need to know the exact size of the hashed data to reconstruct the sequence used as padding because this value is included in the ending 64 bits. Based on the API documentation we can assume that the secret is 16 bytes.

We can append anything to the request and calculate its signature but we must keep the same prefix including the padding, fortunately we have a simple way to avoid that prefix being a limitation. We can use the first char of the first variable as a variable name and all the rest of the original request including the hash padding as its value:


The annoying padding that includes non alphanumeric values and always contains null bytes becomes part of a variable that will be ignored. The only limitation is that we cannot use new variable names that after sorting fall before the 'a' variable but this is not a problem in practice because 'a' is the first letter of the alphabet and there isn't any numeric API parameter name being used.

5.4 Exploitations

There are many ways one can exploit this vulnerability for fun and profit. Below are what we have come up with. Others may have better ways to exploit this vulnerability. Please note that what we write here apply only for Flickr's API. This vulnerability may become much more-or-less dangerous in the context of other Flickr copycat API services. However, it would be up to those who have more time and/or interest than us to test these services.

First off, an attacker can send arbitrary yet valid requests on behalf of any third party application. This can be exploited to send requests using commercial API key which is AFAWK the same as non-commercial keys at the moment but this may change in the future. This may also make the application be blocked by Flickr if the attacker sends abusive requests that violating TOS of Flickr's API.

It is important to stress that this vulnerability alone doesn't give an attacker immediately access to accounts of Flickr users, but being able to send arbitrary requests on behalf of any application brings him much closer to that goal. In order to compromise the account of an user, the attacker needs to capture a 'frob' or an 'auth_token' from that user. He can do that by attacking either the third party application or the user using techniques such as network sniffing or ARP/DNS spoofing or as simple as phishing. Google may help too, as always.

Additionally, if an application uses PHPFlickr >= 1.3.1, an attacker can trick users of that application to visit arbitrary web sites. The login url accepts an undocumented 'extra' parameter which is passed back by Flickr to the calling applications after the users finish authorizing the application. PHPFlickr >= 1.3.1 will automatically treat the 'extra' parameter as an URL, and redirect the users to it.

So if users click on a link like this:


where api_key belongs to some third party application using PHPFlickr, they'll be immediately redirected to http://evil.com if they have already authorized that application. This may lead to phishing or browser exploitation attacks.

You can see how this works by following these steps (this may not work anymore if Yahoo! has fixed the issue):

* Authorize Preloadr which is an application that uses PHPFlickr >= 1.3.1. You can do that by access this link:


*Then click on this link:


would redirect you to http://vnsecurity.net.

This vulnerability may apply for other Flickr's API libraries and applications as well. Developers often use this 'extra' parameter to implement a dynamic callback mechanism. This may lead to total users' accounts compromise if the developers also pass the 'frob' they acquire from Flickr onto the 'extra' URL. Some sites include the original user's request URL as 'extra' value, which allows attackers to get signed login URLs containing arbitrary strings in the 'extra' field.

5.5 Suggested Fixes

This attack could be detected and blocked using the padding bytes as signature, so a short term workaround is to deny all API calls containing 0x80 or 0x00. But filtering 0x80 or 0x00 would stop applications from sending requests containing Unicode text, so you may consider our next suggestion.

A long term solution is to switch to some other secure MAC implementations such as HMAC-SHA1 (see [8]). As most of the programming languages used both in the server and client side to work with web services provide access to HMAC functions, there isn't a good reason to use the message digest algorithms directly to generate a precarious signature. The extension problem can be solved using a secure HMAC implementation but also is important to conserve the query structure in the signing input string.

As suggested by Alex Sotirov, we want to stress that some sites have a similar API that's not vulnerable to our attack because they put the SECRET at the end rather than the beginning. Facebook is one example, see http://wiki.developers.facebook.com/index.php/Verifying_The_Signature. Please note that although Facebook signing scheme is not vulnerable to length-extension attack, we do not recommend it because it may be vulnerable to other known attacks (see [10]).

6. Conclusion

Length-extension attack on MAC implementation based on MD hash construction has been known in crypto academic community as early as 1992 (see [6]). After 17 years, however, we still have a large number of systems vulnerable to this simple attack. What is even more surprising is the fact that we were the first to identify this vulnerability in such popular system like Flickr.

Since August 2009 we have been carrying out a research in which we test-run a number of identified practical crypto attacks on random widely-used software systems. To our surprise, most, if not all, can be attacked by one or more of well-known crypto bugs. This case is just one example.

We hope that publishing this vulnerability and other future results from our research would encourage the security community in taking a more serious look at crypto bugs in software system which is as pervasive as SQL Injection or XSS in early 2000.

We hope you enjoy reading this advisory as much as we enjoy writing it.

7. References

[1] Cal Henderson et al. Flickr Authentication API Spec. Retrieved September 6, 2009, from http://www.flickr.com/services/api/auth.spec.html.

[2] Colin Percival. AWS signature version 1 is insecure. Retrieved September 6, 2009, from http://www.daemonology.net/blog/2008-12.html.

[3] R. Rivest. RFC 1321: The MD5 Message-Digest Algorithm. RSA Data Security, Inc., April 1992.

[4] I.B. Damgård. A design principle for hash functions. In G. Brassard, editor, Advances in Cryptology: Proceedings of CRYPTO ‘89, volume 435 of Lecture Notes in Computer Science, pages 416–427. Springer-Verlag, New York, 1990.

[5] R. Merkle. One way hash functions and DES. In G. Brassard, editor, Advances in Cryptology: Proceedings of CRYPTO ‘89, volume 435 of Lecture Notes in Computer Science, pages 428–446. Springer-Verlag, New York, 1990.

[6] G. Tsudik. Message authentication with one-way hash functions. ACM Computer Communications Review, 22(5):29–38, 1992.

[7] B. Kaliski and M. Robshaw. Message Authentication with MD5. RSA Labs' CryptoBytes, Vol. 1 No. 1, Spring 1995.

[8] M. Bellare, R. Canetti, and H. Krawczyk. RFC 2104 HMAC: Keyed-Hashing for Message Authentication, February 1997.

[9] H. Travis. Web 2.0 Cryptology, A Study in Failure. OWASP, 2009. Retrieved September 13, 2009, from http://www.subspacefield.org/security/web_20_crypto.pdf.

[10] B. Preneel, P.C. van Oorschot. MDx-MAC and building fast MACs from hash functions. Advances in Cryptology, Lecture Notes in Computer Science 963, D. Coppersmith, Ed., Springer-Verlag, 1995, pp. 1-14.