Saturday 22 October 2016

Hack.lu CTF 2016 "redacted" write-up (bruteforce approach)

I'm a member of CTF team  woyouyizhixiaomaol.
This is our write-up for the "redacted" challenge held during Hack.lu CTF 2016
by FluxFingers.

Challenge description:

Someone gave a nice presentation with some redacted ssh keys, I extracted them for you, the seem to belong to berlin@cthulhu.fluxfingers.net on port 1504.
Good Luck

Attachment: redacted



So, some parts of the RSA private we received were redacted.

$ cat redacted_6175ab865421ca2c83b7c77d7ee521f3
-----BEGIN RSA PRIVATE KEY-----
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/0qc146UXXbxxxxxxxxxxxxxxWe9
AR1kOzxxxxxxxxxxxxxxxxxxxxxxxMSSCxxxxxxxxxxxxxxxx8cCovIcAOZxFEaF
cja1wxEG5MHT7lvXx4U0Kq22p9F2337ct84deN/pkoV+GjRzB1YYbKTCAN7CqX8z
s2x4n9e7WGb71o6D2CPq5kyeLXQPLwnQODs51RqusZCFjoo7atnLq42TWqG9AdHL
uiOK9N+EVdfXicce5gkfcR52b2M6BCD1MK23BJUGYHCgcHP8sB0hzC/VZI2fVHXX
aWl9PjJYaDFauOUOc1APTC0LhUjOOOATOClOgQIDAQABAoIBADBbgjpOT03t/c07
AFXZ/5SUZrtovlhwGngfkdeykEbpR7Lemd9LYqd9lgWPgRqPNzFHah81SFKAOTjV
ext1kpsVVtLF6w3mMm6pPNqOJn2Rbp+c/YVaAYH0/9dDskqFvzeL+7zfqxPOoSpb
fvSb8EsFC4mjG5cAY2nEWukCkpHjD3ibP9PatM07O4i3SJCzV+7A8AdTWyVYxXYE
reNlIsOc/iK6ukOUB0eAWdYwdH11LfUh+I9EoP7SiNmOJUhAolm0bUUbuOFg8llG
hexo/2zvLbtWMTT0TesObUZ+jr+VUW1R76exC7sPIKSmzZxSWZ1nBj3IwHoKSFic
9exaMoECgYEA5N26lsHLxPQSBO5vwW4UgwQ4ru5LvSGvXOiN/SWhLyqaJplO76Dm
vtBKwuKb9jm0yPl1rYhvMRXsXjhMxowf19fbY8xj9jRhUoCccdImIj19aZDK5k38
FvF0+hpu5Gslr6/885NqYdPyxp1s7plP7/jy8KcGOEIBENMD0HWrFtMCgYEA3uVZ
mJR7/bdcfjSbx2oWc6jEG2KSnCQsDj0MgIc4lyUY+GOTBLM0DWqIUQzFJON5Y6Qt
Bjj2BVcqp7k+2gfcKUVxGPqamQBi8F0AJdVGfT7fjbRIzxLtSrZ5Z75wwqVhezCF
0OFRNX1jseyktTdG/L5YbNyKRAXPr3GfPwETGNsCgYAGGrPjWX/p3OiuIP3yFtGN
PQuV/t0eSku3GqzO17YY3/YEmYo1cgE1jbCwygKG6rsbsSumWUE9+eu4B6Bkm1Au
HZ/IZac05ejCnpONpaFGwIUbz7TZt7LFmeMY2KOkjAcRTIxeosvvmAudqI1DP+uV
5vnz2UCdN4V3wWkUok7R6QKBgHxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxT6C7P
llmidv5e20lDU/1K7c8W2AwcL/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxVOq/
qAoRtxxxxxxxxxxxxxxxxxxxxxxxxxxOCmw5gRCOaV1FWYgL/yLIaxpveyvDQqJO
D7Txxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx4hURSon01
inkWPUeuxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx3viEr8n
6D/CGT26DVZNh0Y3+ol1IKap3z6EP6s8BRJWECcj7x3+0XmDrQ0=
-----END RSA PRIVATE KEY-----


The redacted part were replaced by sequences of "xxxx". Interpreted as base64
"xxxx" gives the following output:

$ echo xxxxxxxx | base64 -d - | xxd -p
c71c71c71c71


Parsing the redacted file was impossible with regular tools:

$ openssl asn1parse -i \
-in redacted_6175ab865421ca2c83b7c77d7ee521f
    0:d=0  hl=2 l=  28 prim: priv [ 7 ]
Error in encoding
3682970277520:error:0D07207B:asn1 encoding routines:ASN1_get_object:header too long:asn1_lib.c:157:


We then decided to reconstruct a valid key based of the valid information we
could extract from the redacted key.
But first we needed to know how a valid key should be like.

Let's generate one, with almost the same size as the redacted one.

$ openssl genrsa -out bla.key 2048
Generating RSA private key, 2048 bit long modulus
.........................................................................+++
...........................................+++
e is 65537 (0x10001)

$ ls -l
-rw-r--r-- 1 user users  1675 Oct 22 10:02 redacted_6175ab865421ca2c83b7c77d7ee521f3
-rw-r--r-- 1 user users  1679 Oct 22 10:07 bla.key


Sizes are quite similar.

The generated RSA private key looks like this:

$ openssl asn1parse -in bla.key -i
    0:d=0  hl=4 l=1188 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
    7:d=1  hl=4 l= 257 prim:  INTEGER           :ED11C233B0D54CD077206B1CE80F0D356C276E1751B0C3B03844E74BB6FE3C1BE60D2DB28120B9A993A93D83F1DD7B77893D95534BD4A3F53AACD987F520AAD7C1BF44807552B88F7E5F252F474591D2BBD5B7AAE13F02576C14F535BADA3175A91EA8714F0D96FD5273684045BA52A6E8C20E1EA19D437D4669BB4D0C4E08D76C484DA671C2B034C73DFE280CAB0887F3B8487702C6C62BA57580C0648AF071EE46A84CBB9FD24501CE31AC6967447D8906648E0F1239839E16D99A0965C5B0FEEFB2D1B78B85AA873524918464C0E64B510D3CEB5F87A055A400BE5B3660C705D0B9369AB101AA2C61D7951765242FAE0E71EBDF19427B5B6B570421DF6855
  268:d=1  hl=2 l=   3 prim:  INTEGER           :010001
  273:d=1  hl=4 l= 257 prim:  INTEGER           :93403B9325DC6758F9158ED2A6A56ABBEB10D6C5EF3CCF5FEEA385D336B7D598329DAEEBB85F1E53615F76D134F33054804F5B2820EAD46866E8A439599DCFE031FCDECCB79309064025531079C191A10680EA135ED3675DEBC95CC1E1ECD359D51130E92884356BE5C1BF5864B725CD7CB7C4536C69255973DA0AB801D39A931A27C3BBA8E9A2D589A217706FB8D4F2D35FEAF2BA4227C7F7BA4EBE106A59B4138F44E67C774F2614DBACB198987FEBE8379B6A26327425F2F66BA2686F70DE366F0C92E2B61EB442E986A25AC69CFF406BAA9417A5B6924C1B75D8170B29436C4120B44620EA1D959BD2F3FD5CF885F39C47C864FE562EEC28310F98137DA5
  534:d=1  hl=3 l= 129 prim:  INTEGER           :F84059ABC615AD3A6A6E5401FC687EB8460790AC8F0616C1CCB8438605AC2AFD130F157C2DD04F511E29B4821B40C683474634DAB6774B7426A5D4D44E9623D21E90DF25CE7705281B72E3041AADA36A815375BF57C22E9EA79AD620038EE46612A7FA2C2946083A94D177A861327EA4ACCC27D3042092871F8CED4DAFEED643
  666:d=1  hl=3 l= 129 prim:  INTEGER           :F4780F065B85CBC5FE0D9F33E918FBD484D3B69C5A876325DAD013DD2B3E125C2D5F54243E5BCE35768521184931B3ACEA6EE48B4B7ED5E2314646A1578FBC594CAB414FC88C4066091692CE15B8C06F458777E8D33D7771CB07664D6FE706C2D51B8BD5A1601B0F291F7C856D93130035930AC20538B9BB47AA7C0D6332B987
  798:d=1  hl=3 l= 129 prim:  INTEGER           :EDABEE2DDE7F7251B303DDB9E905C20C7A3F53EB6122DB36BFE0CA04CDF97F4EBBA87D515E2B4944C833F5757AD2113C2E48B0E1943FB22589BACA80589CB5BEBD34C5EF5433EEE3EF2396E49F060EA6311ACE685A84B64D7EF966774FF0C60A53622EC988DA5B967A53F0D36BFB03F474DB20658E5600F30CE9C767D1404031
  930:d=1  hl=3 l= 128 prim:  INTEGER           :3E49A0BA63F3511A1F42E53F5AB2CCE736F8A25C700C72CCA055C7D9E03CAE7CE1EA9A0BA9FFC628850C22848791AC4FF06354C3D0F67E1465AD9C2D5B9BF9C75EEB7B769288799805D4C48ED1A60311D6CB4F57F90A7E36761E6A886C6C96A2699DDD210F3EE766137A3C45DAC7505E0B486DC34585507D512334FC4C3C0E5D
 1061:d=1  hl=3 l= 128 prim:  INTEGER           :578704B51A02D8753087092AFA954B0097AAC263FFBFD7A3340DD1C06FEA09CB341AF56C66D2F344643646C2A9DDA2AB26CC6E8FF7959D83F8A5E73777969224CAACF9B5F54B56F78E95584129B48C1DD657E510AC9F6A9C736477189F777A247F5F7FB109D137F4EE9A87246CC52CA881DED6914FB55F87F700D246DB804CEF
 

From ASN1 point of view, it's a SEQUENCE of INTERGERs. The "-i" argument helps understanding the structure by indenting the output.

Here is a more human readable representation of the generated key:

$ openssl rsa -in bla.key -text -noout
Private-Key: (2048 bit)
modulus:
    00:ed:11:c2:33:b0:d5:4c:d0:77:20:6b:1c:e8:0f:
    [...]
    2f:ae:0e:71:eb:df:19:42:7b:5b:6b:57:04:21:df:
    68:55
publicExponent: 65537 (0x10001)
privateExponent:
    00:93:40:3b:93:25:dc:67:58:f9:15:8e:d2:a6:a5:
    [...]

    85:f3:9c:47:c8:64:fe:56:2e:ec:28:31:0f:98:13:
    7d:a5
prime1:
    00:f8:40:59:ab:c6:15:ad:3a:6a:6e:54:01:fc:68:
    [...]

    94:d1:77:a8:61:32:7e:a4:ac:cc:27:d3:04:20:92:
    87:1f:8c:ed:4d:af:ee:d6:43
prime2:
    00:f4:78:0f:06:5b:85:cb:c5:fe:0d:9f:33:e9:18:
    [...]

    29:1f:7c:85:6d:93:13:00:35:93:0a:c2:05:38:b9:
    bb:47:aa:7c:0d:63:32:b9:87
exponent1:
    00:ed:ab:ee:2d:de:7f:72:51:b3:03:dd:b9:e9:05:
    [...]

    7a:53:f0:d3:6b:fb:03:f4:74:db:20:65:8e:56:00:
    f3:0c:e9:c7:67:d1:40:40:31
exponent2:
    3e:49:a0:ba:63:f3:51:1a:1f:42:e5:3f:5a:b2:cc:
    [...]

    7a:3c:45:da:c7:50:5e:0b:48:6d:c3:45:85:50:7d:
    51:23:34:fc:4c:3c:0e:5d
coefficient:
    57:87:04:b5:1a:02:d8:75:30:87:09:2a:fa:95:4b:
    [...]

    9a:87:24:6c:c5:2c:a8:81:de:d6:91:4f:b5:5f:87:
    f7:00:d2:46:db:80:4c:ef


From this we can see the order of the different INTEGERs and their absolute offsets and lengths in the key file:

modulus ~ offset 7 ~ length 257
publicExponent ~ offset 268 ~ length 3
privateExponent ~ offset 273 ~ length 257
prime1 ~ offset 534 ~ length 129
prime2 ~ offset 666 ~ length 129
exponent1 ~ offset 798 ~ length 129
exponent2 ~ offset 930 ~ length 128
coefficient ~ offset 1061 ~ length 128


Extraction of the INTEGERs from the redacted key file can be done by bruteforcing
all the offsets and looking for valid ASN1 objects of length up to the maximum
length we are looking for. This length can be computed as 257 + the header
length of an ASN1 encoded INTEGER. It gives something like 257 + 4 = 261.

$ for i in $(seq 1 2000); do echo -n "Absolute offset: $i -> "; openssl asn1parse -in redacted_6175ab865421ca2c83b7c77d7ee521f3 -offset $i -length 261 2>/dev/null; done | grep -a INTEGER
Absolute offset: 268 ->     0:d=0  hl=2 l=   3 prim: INTEGER           :010001
Absolute offset: 273 ->     0:d=0  hl=4 l= 256 prim: INTEGER           :305B823A4E4F4DEDFDCD3B0055D9FF949466BB68BE58701A781F91D7B29046E947B2DE99DF4B62A77D96058F811A8F3731476A1F354852803938D57B1B75929B1556D2C5EB0DE6326EA93CDA8E267D916E9F9CFD855A0181F4FFD743B24A85BF378BFBBCDFAB13CEA12A5B7EF49BF04B050B89A31B97006369C45AE9029291E30F789B3FD3DAB4CD3B3B88B74890B357EEC0F007535B2558C57604ADE36522C39CFE22BABA439407478059D630747D752DF521F88F44A0FED288D98E254840A259B46D451BB8E160F2594685EC68FF6CEF2DBB563134F44DEB0E6D467E8EBF95516D51EFA7B10BBB0F20A4A6CD9C52599D67063DC8C07A0A48589CF5EC5A3281
   90:d=0  hl=2 l=  61 cons: INTEGER
Absolute offset: 533 ->     0:d=0  hl=3 l= 129 prim: INTEGER           :E4DDBA96C1CBC4F41204EE6FC16E14830438AEEE4BBD21AF5CE88DFD25A12F2A9A26994EEFA0E6BED04AC2E29BF639B4C8F975AD886F3115EC5E384CC68C1FD7D7DB63CC63F6346152809C71D226223D7D6990CAE64DFC16F174FA1A6EE46B25AFAFFCF3936A61D3F2C69D6CEE994FEFF8F2F0A70638420110D303D075AB16D3
Absolute offset: 615 ->     0:d=0  hl=2 l=  61 cons: INTEGER
Absolute offset: 665 ->     0:d=0  hl=3 l= 129 prim: INTEGER           :DEE55998947BFDB75C7E349BC76A1673A8C41B62929C242C0E3D0C808738972518F8639304B3340D6A88510CC524E37963A42D0638F605572AA7B93EDA07DC29457118FA9A990062F05D0025D5467D3EDF8DB448CF12ED4AB67967BE70C2A5617B3085D0E151357D63B1ECA4B53746FCBE586CDC8A4405CFAF719F3F011318DB
Absolute offset: 797 ->     0:d=0  hl=3 l= 128 prim: INTEGER           :061AB3E3597FE9DCE8AE20FDF216D18D3D0B95FEDD1E4A4BB71AACCED7B618DFF604998A357201358DB0B0CA0286EABB1BB12BA659413DF9EBB807A0649B502E1D9FC865A734E5E8C29E938DA5A146C0851BCFB4D9B7B2C599E318D8A3A48C07114C8C5EA2CBEF980B9DA88D433FEB95E6F9F3D9409D378577C16914A24ED1E9
Absolute offset: 928 ->     0:d=0  hl=3 l= 128 prim: INTEGER           :7C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C53E82ECF9659A276FE5EDB494353FD4AEDCF16D80C1C2FFC71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C7154EABFA80A11B71C71C71C71C71C71C71C71C71C71C71C71C71C4E0A6C3981108E695D4559880BFF22C86B1A6F7B2BC342A24E0FB4F1


Some INTEGERs we got contain chunk of "C71"'s. These are the unusable redacted parts.

Looking at the offsets and length we can retrieve all we need to reconstruct a valid key:

p (prime1 at offset 533 ~ 534): 0xE4DDBA96C1CBC4F41204EE6FC16E14830438AEEE4BBD21AF5CE88DFD25A12F2A9A26994EEFA0E6BED04AC2E29BF639B4C8F975AD886F3115EC5E384CC68C1FD7D7DB63CC63F6346152809C71D226223D7D6990CAE64DFC16F174FA1A6EE46B25AFAFFCF3936A61D3F2C69D6CEE994FEFF8F2F0A70638420110D303D075AB16D3

q (prime2 at offset 665 ~ 666): 0xDEE55998947BFDB75C7E349BC76A1673A8C41B62929C242C0E3D0C808738972518F8639304B3340D6A88510CC524E37963A42D0638F605572AA7B93EDA07DC29457118FA9A990062F05D0025D5467D3EDF8DB448CF12ED4AB67967BE70C2A5617B3085D0E151357D63B1ECA4B53746FCBE586CDC8A4405CFAF719F3F011318DB


Rebuilding the private key only requires p and q.

$ rsatool/rsatool.py -p 0xE4DDBA96C1CBC4F41204EE6FC16E14830438AEEE4BBD21AF5CE88DFD25A12F2A9A26994EEFA0E6BED04AC2E29BF639B4C8F975AD886F3115EC5E384CC68C1FD7D7DB63CC63F6346152809C71D226223D7D6990CAE64DFC16F174FA1A6EE46B25AFAFFCF3936A61D3F2C69D6CEE994FEFF8F2F0A70638420110D303D075AB16D3 -q 0xDEE55998947BFDB75C7E349BC76A1673A8C41B62929C242C0E3D0C808738972518F8639304B3340D6A88510CC524E37963A42D0638F605572AA7B93EDA07DC29457118FA9A990062F05D0025D5467D3EDF8DB448CF12ED4AB67967BE70C2A5617B3085D0E151357D63B1ECA4B53746FCBE586CDC8A4405CFAF719F3F011318DB -o unredacted.pem
Using (p, q) to initialise RSA instance

n =
c7455240232e4c309b7afda495ccd5ff4a9cd78e945d76c6713955e12a5da435cdf967bd011d643b
3d417797075f8def866a8cb9f02745acbe78c4920b15dc36365f6c1dd71c9b900bc702a2f21c00e6
711446857236b5c31106e4c1d3ee5bd7c785342aadb6a7d176df7edcb7ce1d78dfe992857e1a3473
0756186ca4c200dec2a97f33b36c789fd7bb5866fbd68e83d823eae64c9e2d740f2f09d0383b39d5
1aaeb190858e8a3b6ad9cbab8d935aa1bd01d1cbba238af4df8455d7d789c71ee6091f711e766f63
3a0420f530adb70495066070a07073fcb01d21cc2fd5648d9f5475d769697d3e325868315ab8e50e
73500f4c2d0b8548ce38e01338294e81


e = 65537 (0x10001)

d =
305b823a4e4f4dedfdcd3b0055d9ff949466bb68be58701a781f91d7b29046e947b2de99df4b62a7
7d96058f811a8f3731476a1f354852803938d57b1b75929b1556d2c5eb0de6326ea93cda8e267d91
6e9f9cfd855a0181f4ffd743b24a85bf378bfbbcdfab13cea12a5b7ef49bf04b050b89a31b970063
69c45ae9029291e30f789b3fd3dab4cd3b3b88b74890b357eec0f007535b2558c57604ade36522c3
9cfe22baba439407478059d630747d752df521f88f44a0fed288d98e254840a259b46d451bb8e160
f2594685ec68ff6cef2dbb563134f44deb0e6d467e8ebf95516d51efa7b10bbb0f20a4a6cd9c5259
9d67063dc8c07a0a48589cf5ec5a3281

p =
e4ddba96c1cbc4f41204ee6fc16e14830438aeee4bbd21af5ce88dfd25a12f2a9a26994eefa0e6be
d04ac2e29bf639b4c8f975ad886f3115ec5e384cc68c1fd7d7db63cc63f6346152809c71d226223d
7d6990cae64dfc16f174fa1a6ee46b25afaffcf3936a61d3f2c69d6cee994feff8f2f0a706384201
10d303d075ab16d3

q =
dee55998947bfdb75c7e349bc76a1673a8c41b62929c242c0e3d0c808738972518f8639304b3340d
6a88510cc524e37963a42d0638f605572aa7b93eda07dc29457118fa9a990062f05d0025d5467d3e
df8db448cf12ed4ab67967be70c2a5617b3085d0e151357d63b1eca4b53746fcbe586cdc8a4405cf
af719f3f011318db

Saving PEM as unredacted.pem

 


The reconstructed key can then be used to connect to the server:


$ ssh -i unredacted.pem berlin@cthulhu.fluxfingers.net -p 1504

Welcome to Ubuntu 14.04.5 LTS (GNU/Linux 3.13.0-65-generic x86_64)
[...]
Last login: Fri Oct 21 08:12:34 2016 from 218.146.74.187
Congratz! The flag is:
flag{thought_ssh_privkeys_are_secure?}
Connection to cthulhu.fluxfingers.net closed.


And voilĂ .

Friday 21 October 2016

Hack.lu CTF 2016 "Old-Tshirt Contest" write-up

I'm a member of CTF team woyouyizhixiaomaol .
Here is our submission for the "Old-Tshirt Contest" challenge held during Hack.lu CTF 2016 by FluxFingers.

Challenge description:
Hey, to get points for this challenge send us a picture of you wearing your old hacklu t-shirts and a sign with your team name to <masked email>. The older the shirts are the more points do you get. You only get points for one t-shirt per year. The points per t-shirt calculate as:
    2017 - Year of the shirt
The more different t-shirts you have the more points you get.

Digging through my wardrobe, I found 12 t-shirts ranging from 2005 till 2016.


We received 78 points for this entry, we also got a special mention during the CTF prize ceremony :).