Hack.lu 2016 - redacted
Part of the private RSA key is deleted. However, we can extract e,d,p,q which is sufficient to reconstruct the private key.
Description
redacted by cornelius (Crypto)
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
Details
Points: 200 (- 24)
Category: crypto
Validations: 80
Solution
I printed the data in hexadecimal instead of base64:
c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71ff4a9cd78e945d76f1c71c71c71c71c71c71c567bd011d643b3c71c71c71c71c71c71c71c7
1c71c71c71c4c4920b1c71c71c71c71c71c71c71c7c702a2f21c00e6711446857236b5c31106e4c1d3ee5bd7c785342aadb6a7d176df7edcb7ce1d78dfe99285
7e1a34730756186ca4c200dec2a97f33b36c789fd7bb5866fbd68e83d823eae64c9e2d740f2f09d0383b39d51aaeb190858e8a3b6ad9cbab8d935aa1bd01d1cb
ba238af4df8455d7d789c71ee6091f711e766f633a0420f530adb70495066070a07073fcb01d21cc2fd5648d9f5475d769697d3e325868315ab8e50e73500f4c
2d0b8548ce38e01338294e81020301000102820100305b823a4e4f4dedfdcd3b0055d9ff949466bb68be58701a781f91d7b29046e947b2de99df4b62a77d9605
8f811a8f3731476a1f354852803938d57b1b75929b1556d2c5eb0de6326ea93cda8e267d916e9f9cfd855a0181f4ffd743b24a85bf378bfbbcdfab13cea12a5b
7ef49bf04b050b89a31b97006369c45ae9029291e30f789b3fd3dab4cd3b3b88b74890b357eec0f007535b2558c57604ade36522c39cfe22baba439407478059
d630747d752df521f88f44a0fed288d98e254840a259b46d451bb8e160f2594685ec68ff6cef2dbb563134f44deb0e6d467e8ebf95516d51efa7b10bbb0f20a4
a6cd9c52599d67063dc8c07a0a48589cf5ec5a328102818100e4ddba96c1cbc4f41204ee6fc16e14830438aeee4bbd21af5ce88dfd25a12f2a9a26994eefa0e6
bed04ac2e29bf639b4c8f975ad886f3115ec5e384cc68c1fd7d7db63cc63f6346152809c71d226223d7d6990cae64dfc16f174fa1a6ee46b25afaffcf3936a61
d3f2c69d6cee994feff8f2f0a70638420110d303d075ab16d302818100dee55998947bfdb75c7e349bc76a1673a8c41b62929c242c0e3d0c808738972518f863
9304b3340d6a88510cc524e37963a42d0638f605572aa7b93eda07dc29457118fa9a990062f05d0025d5467d3edf8db448cf12ed4ab67967be70c2a5617b3085
d0e151357d63b1eca4b53746fcbe586cdc8a4405cfaf719f3f011318db028180061ab3e3597fe9dce8ae20fdf216d18d3d0b95fedd1e4a4bb71aacced7b618df
f604998a357201358db0b0ca0286eabb1bb12ba659413df9ebb807a0649b502e1d9fc865a734e5e8c29e938da5a146c0851bcfb4d9b7b2c599e318d8a3a48c07
114c8c5ea2cbef980b9da88d433feb95e6f9f3d9409d378577c16914a24ed1e90281807c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c53e82ecf
9659a276fe5edb494353fd4aedcf16d80c1c2ffc71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c7154eabfa80a11b71c71c71c71c71c71c71c71c7
1c71c71c71c71c4e0a6c3981108e695d4559880bff22c86b1a6f7b2bc342a24e0fb4f1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c
71c71c71c71c71c71c78854452a27d358a79163d47aec71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c77be212bf27
e83fc2193dba0d564d874637fa897520a6a9df3e843fab3c051256102723ef1dfed17983ad0d
Obviously the first part is redacted but at position 268 we have 0203010001 which in ASN.1 syntax is integer with value 0x10001. It looks like the value of the public exponents. If we read the following values we have the value for \(d\) which is 256 bytes, \(p\) and \(q\). I just verified that \(p\) and \(q\) are prime and \((2^{e})^d \mod(pq) = 2\) and it confirms that we recover the good values. With this values I was able to reconstruct the complete private key with rsatool:
$./rsatool.py -f PEM -o key.pem -e 65537 -d 6104563261232211901521194772680811854115952356747247030146592811299094814755153165787066325928669260750922344230060286999649968847084969439295250422845285341638142598792675507875382650315896288320067800250797503384452262476795034013205325193077047266016902529159659624897161525777921452788530092217498140692732036141650420003603619222184410028202365437353988060387087491346567756718075971009351048575400533778799735927697664983843527374679533694351653533499959961914403648291267279502443878163626057600309559026102277412241533409202419788720201816455769220033330650190588166980366218017275055319698565183207789703809 -p 160715260849342318931136112813341037345926969012288227225240875622403009493539093929333081548188459992247771680452063593583756278915740193557402138743266217376005578973188641800583345510266770139969709567420846366801788060791738229180205729066714584288249507088921482835100030743352147986722422517067206563539 -q 156522822773738162417254450203271175855220146400024771706084276654684994055624152101542626647589634389361232150411812572776336649201321449632016603858688896275125914484326556417817195311471437215701390750315213065194536381852437122083849274951300180499399546807140772435452395099516509211865918104434503784667
Then I was able to connect to the server with the correct key:
$ ssh berlin@cthulhu.fluxfingers.net -p 1504 -i key.pem
Welcome to Ubuntu 14.04.5 LTS (GNU/Linux 3.13.0-65-generic x86_64)
* Documentation: https://help.ubuntu.com/
The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.
Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.
The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.
Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.
Last login: Wed Oct 19 20:37:05 2016 from 87.125.112.251
Congratz! The flag is:
flag{thought_ssh_privkeys_are_secure?}
Connection to cthulhu.fluxfingers.net closed.
Written on October 19, 2016