# 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
2d0b8548ce38e01338294e81020301000102820100305b823a4e4f4dedfdcd3b0055d9ff949466bb68be58701a781f91d7b29046e947b2de99df4b62a77d9605
8f811a8f3731476a1f354852803938d57b1b75929b1556d2c5eb0de6326ea93cda8e267d916e9f9cfd855a0181f4ffd743b24a85bf378bfbbcdfab13cea12a5b
d630747d752df521f88f44a0fed288d98e254840a259b46d451bb8e160f2594685ec68ff6cef2dbb563134f44deb0e6d467e8ebf95516d51efa7b10bbb0f20a4
a6cd9c52599d67063dc8c07a0a48589cf5ec5a328102818100e4ddba96c1cbc4f41204ee6fc16e14830438aeee4bbd21af5ce88dfd25a12f2a9a26994eefa0e6
d3f2c69d6cee994feff8f2f0a70638420110d303d075ab16d302818100dee55998947bfdb75c7e349bc76a1673a8c41b62929c242c0e3d0c808738972518f863
9304b3340d6a88510cc524e37963a42d0638f605572aa7b93eda07dc29457118fa9a990062f05d0025d5467d3edf8db448cf12ed4ab67967be70c2a5617b3085
d0e151357d63b1eca4b53746fcbe586cdc8a4405cfaf719f3f011318db028180061ab3e3597fe9dce8ae20fdf216d18d3d0b95fedd1e4a4bb71aacced7b618df
f604998a357201358db0b0ca0286eabb1bb12ba659413df9ebb807a0649b502e1d9fc865a734e5e8c29e938da5a146c0851bcfb4d9b7b2c599e318d8a3a48c07
114c8c5ea2cbef980b9da88d433feb95e6f9f3d9409d378577c16914a24ed1e90281807c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c53e82ecf
9659a276fe5edb494353fd4aedcf16d80c1c2ffc71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c7154eabfa80a11b71c71c71c71c71c71c71c71c7
1c71c71c71c71c4e0a6c3981108e695d4559880bff22c86b1a6f7b2bc342a24e0fb4f1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c
71c71c71c71c71c71c78854452a27d358a79163d47aec71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c77be212bf27


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