We heard hellman encrypted the flag using his super secure keygen. Break it!
Summary: RSA with the lower half of the secret exponent bits leaked.
Here we are given a bunch of files: client.pub, flag.enc, ssh-keygen and log.txt. Easy to see that we have a public key, an encrypted flag, a key generator and some log. Let’s look into the log:
Generating public/private rsa key pair. Enter file in which to save the key (/home/hellman/.ssh/id_rsa): client client already exists. Overwrite (y/n)? y Enter passphrase (empty for no passphrase): Enter same passphrase again: Your identification has been saved in client. Your public key has been saved in client.pub. The key fingerprint is: b9:17:c9:d3:06:4c:91:9d:4f:08:62:66:62:9e:97:33 hellman@phd The key's randomart image is: +--[ RSA 1024]----+ |.o*@.o+ /&^&SB@.^| |Xoo#^%=^=SBB@=#%+| |=X^##OX+B/oS.**..| |=/@*^+=o=O+ O#BS+| | X^^*X &OO+Soo%S=| |XS%/X*#*%^&/=+&%*| |+%%X@X@/.@==B^#@&| |o^S//B=o.^S^= O%/| |O#X^ ^/.&B=.#=#**| +-----------------+ |
If you have ever used an ssh-keygen, you should notice a quite different randomart:
(original ssh-keygen randomart) +--[ RSA 2048]----+ | .oo.... | | . . | | . . | | o + E.. | | = S . oo | | . . .= | | o o + . o | | o . * . | | . +o.. | +-----------------+ |
Surely much information is hidden into it. By the way if you look closer on the challenge name, you’ll see RSART, that is also a small hint.
So we need to reverse ssh-keygen to find out what’s hidden in randomart image. Luckily it’s 32 bit and even not stripped.
We can quickly find this call:
v50 = key_fingerprint(v44, SSH_FP_MD5, SSH_FP_RANDOMART); |
and the function itself:
char *__cdecl key_fingerprint(Key_0 *k, fp_type dgst_type, fp_rep dgst_rep) { int v3; // ecx@11 char *result; // eax@11 u_int dgst_raw_len; // [sp+20h] [bp-18h]@1 char *retval; // [sp+24h] [bp-14h]@1 u_char *dgst_raw; // [sp+28h] [bp-10h]@1 retval = 0; dgst_raw = key_fingerprint_raw(k, dgst_type, &dgst_raw_len); if ( !dgst_raw ) fatal("key_fingerprint: null from key_fingerprint_raw()"); if ( dgst_rep == 1 ) { retval = key_fingerprint_bubblebabble(dgst_raw, dgst_raw_len); } else if ( (unsigned int)dgst_rep < 1 ) { retval = key_fingerprint_hex(dgst_raw, dgst_raw_len); } else { if ( dgst_rep != 2 ) fatal("key_fingerprint: bad digest representation %d", dgst_rep); retval = key_fingerprint_randomart(dgst_raw, dgst_raw_len, k); } memset(dgst_raw, 0, dgst_raw_len); xfree(dgst_raw); result = retval; return result; } |
In key_fingerprint_raw:
switch ( k->type ) { ... case 3: // we can find that k->type = 3 via debugging secret = k->rsa->d; if ( secret ) { len = (BN_num_bits(k->rsa->d) + 7) / 8; blob = (u_char *)xmalloc(len); BN_bn2bin(k->rsa->d, blob); *dgst_raw_length = len; result = blob; } |
So we see that fingerprint is simply a secret exponent! Now let’s see how it’s encoded (in key_fingerprint_randomart):
... i = 2 * (dgst_raw_len + 0x7FFFFFFF) + 1; for ( y = 0; y <= 8; ++y ) { for ( x = 0; x <= 16; ++x ) { input = dgst_raw[i >> 1]; if ( !(i & 1) ) input >>= 4; *(&v26[9 * x - 157] + y) = input & 0xF; --i; } } v3 = key_size(k); v4 = key_type(k); snprintf(retval, 0x11u, "+--[%4s %4u]", v4, v3); p = strchr(retval, 0); v5 = p - retval; for ( ia = p - retval - 1; ia <= 0x10; ++ia ) *p++ = '-'; *p = '+'; v6 = (p + 1); *v6 = '\n'; pa = v6 + 1; for ( ya = 0; ya <= 8; ++ya ) { *pa = '|'; pb = pa + 1; for ( xa = 0; xa <= 16; ++xa ) { v7 = *(&v26[9 * xa - 157] + ya); if ( v7 > len ) v7 = len; *pb++ = a_oBox_Se[v7]; //.rodata:08071566 a_oBox@Se db ' .o+=*BOX@%&#/^SE', 0 } *pb = '|'; v8 = pb + 1; *v8 = '\n'; pa = v8 + 1; } *pa = '+'; pc = pa + 1; for ( ib = 0; ib <= 0x10; ++ib ) *pc++ = '-'; *pc = '+'; |
Easy to see, the digest is simply encoded using alphabet ' .o+=*BOX@%&#/^SE' for one hex digit, starting from the lower bits. Let’s count how many bytes we have: field is 9×17 = 153, each item is 4 bits, so total is 153*4 = 612 bits of 1024 bits RSA key. Eh, we have no full secret exponent :(
But there are some attacks on partial key exposure! One of them follows from the Coppersmith attacks and requires only quarter of secret bits to be known. This attack utilizes lattice reduction algorithms.
Actually, since we have more than a half of the bits, there’s much easier solution. Consider some equations:
$$ed \equiv 1 \pmod{ \phi (n) } \Leftrightarrow ed = 1 + k\phi(n)$$
$$k\phi(n) < ed < e\phi(n)$$ We have k < e: so only e candidates for k. Once we know k, we can make a good approximation for d by replacing unknown $\phi(n)$ with simply n:
$$d = (kn + 1) / e$$
The error is bounded nearly by $3\sqrt{n}$ so we have half of the high bits for d! Combine them together with half leaked from the randomart and you have the key.
You can read more about these attacks in an awesome paper “Twenty Years of Attacks on the RSA Cryptosystem” by Dan Boneh (page 11).
Here we have e=65537 which is not small but we can still quickly check all 65537 candidates for d. Here’s a script to factorize the number:
$ time pypy wu.py q IMG 0x55c4c146b1de0e8c7da704efe1246ddfe2b9ce64491d9898aa35ab34dbea5c58daf84fa22f377b085ee803f6c70374243e59d411551f2d6387cce843ac4966f4e4aec228e196fbebd03219521L 0 1000 ... 29000 GOOD 29900 66981711648561817647162799268438619575991949356382917499253420453136066884671347654438607085853025948105234481703945619805567825842732647537889470172719586081456028493295380668797680184579081491775843195434869231517037901533803019865410036066174722316607296984306543734880383026849755152418241102394855363873 p 0xf37f62143e4a031da426809de691f7a0c082444c65b4da421105af27f6bb9430934a80607f8f8c4cb6bd112c85a537dad1799892af63c406deb812ab0ee33f23L q 0xdbce90bb9d573056742432f0bcbcbc1005c0fe361171477edd03a6c1c67fbd6fa95d181fbbf5c9442c87b7a4873bce2d9221290365779b12df1686bffe37400dL real 15m13.060s user 15m12.381s sys 0m0.112s |
Only 15 minutes!
Now we can craft a private key (use sources from this nice writeup by Stalkr).
And finally:
$ openssl rsautl -decrypt -inkey private.pem -in TASK/flag.enc rsandom_4rt |
It’s very sad nobody solved it, though some teams were very close.
