My friend said that he found a way to use python to make his own SSH keys. He says that he loves being able to set his own value for e. I asked him for an example and he sent me the obfuscated_id_rsa file to keep me from accessing his computer.
We are given a redacted private key:
-----BEGIN RSA PRIVATE KEY-----
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAePgPfju1DWgxJZWKh/qXof
f+N3PjCCPKSpAoIBAQDYetLlj1ZjnEa4lgbf7K9ri+oVhhcIGqaQ867E2Hn4NxHT
GkVBMKqhHmH2Awc/lorAYrcQhl8et6nB1X6qk6w19kLXaMoGM1Ta4jnDBQzJ0A8+
ty8EuMvRdNilHBEUP/lKjcrY4WSgiaeaXFHMBqo8FWhJqlN9DgrPBZ19NhlTvITW
9+CeXJe3gVelCDgptrQnX/YTr2OVq5Jsb/91S1D4Hj72fP/BKzuPA3gVVMJOdW9N
jnDVWcM9MWqwLN+2UYVWRcY8XFFSeiAXN2IDe/U2tUdCPWglgmq7B/otmySf5/Gj
BdauMkI3A95ozOvjgjah/wIeRN/Bo4zKlJ2WE2J9AoIBAQDfqA9NbeHlAJe4x7p7
86q60nNiBVtZZTwdWgXntjZMpliaW1UQyOf2n8XNFoHCN9cS+kbyFEhJAfG365R4
GIyA6hr0ZKjSRPW/5grI6jct+qBjbde6nzrZe91yLlu/6NE61hJ/UDPEsuEGkxpm
fNK6Z4G1Vdb5Kc9xrjQvi1TOnfO4yq3Nd2r2VHaxXkNJKMI1mSDTuHggiEaNKY5k
evHmfNpgxGSUpGVhMqPT9hS/og1xMg3Lbs5YjcGbjZSFUtSLaY0JD3qxqI79Fqgs
f1Fxrzupb9qPkOwNDJjVEAlYmv877X6jXCO/nr7/tth3a9OWVfjBcSkVGE4rfyJC
PgFJAoIBAFbCqDIqgUAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA==
-----END RSA PRIVATE KEY-----
We know that multiple redundant parts of the key are all encoded here, per a recent twitter thread and e.g. https://blog.cryptohack.org/twitter-secrets
We basically just work thru that far better writeup :)
Let's look for integer headers "02 82" in ASN.1
(after base64 | od -tx1 )
0000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
0002360 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 07
0002400 8f 80 f7 e3 bb 50 d6 83 12 59 58 a8 7f a9 7a 1f
0002420 7f e3 77 3e 30 82 3c a4 a9 02 82 01 01 00 d8 7a <== here length 0x0101 = 257 (raw_start=0x242d)
0002440 d2 e5 8f 56 63 9c 46 b8 96 06 df ec af 6b 8b ea
0002460 15 86 17 08 1a a6 90 f3 ae c4 d8 79 f8 37 11 d3
0002500 1a 45 41 30 aa a1 1e 61 f6 03 07 3f 96 8a c0 62
0002520 b7 10 86 5f 1e b7 a9 c1 d5 7e aa 93 ac 35 f6 42
0002540 d7 68 ca 06 33 54 da e2 39 c3 05 0c c9 d0 0f 3e
0002560 b7 2f 04 b8 cb d1 74 d8 a5 1c 11 14 3f f9 4a 8d
0002600 ca d8 e1 64 a0 89 a7 9a 5c 51 cc 06 aa 3c 15 68
0002620 49 aa 53 7d 0e 0a cf 05 9d 7d 36 19 53 bc 84 d6
0002640 f7 e0 9e 5c 97 b7 81 57 a5 08 38 29 b6 b4 27 5f
0002660 f6 13 af 63 95 ab 92 6c 6f ff 75 4b 50 f8 1e 3e
0002700 f6 7c ff c1 2b 3b 8f 03 78 15 54 c2 4e 75 6f 4d
0002720 8e 70 d5 59 c3 3d 31 6a b0 2c df b6 51 85 56 45
0002740 c6 3c 5c 51 52 7a 20 17 37 62 03 7b f5 36 b5 47
0002760 42 3d 68 25 82 6a bb 07 fa 2d 9b 24 9f e7 f1 a3
0003000 05 d6 ae 32 42 37 03 de 68 cc eb e3 82 36 a1 ff
0003020 02 1e 44 df c1 a3 8c ca 94 9d 96 13 62 7d 02 82 <== here length 0101 = 257
0003040 01 01 00 df a8 0f 4d 6d e1 e5 00 97 b8 c7 ba 7b
0003060 f3 aa ba d2 73 62 05 5b 59 65 3c 1d 5a 05 e7 b6
0003100 36 4c a6 58 9a 5b 55 10 c8 e7 f6 9f c5 cd 16 81
0003120 c2 37 d7 12 fa 46 f2 14 48 49 01 f1 b7 eb 94 78
0003140 18 8c 80 ea 1a f4 64 a8 d2 44 f5 bf e6 0a c8 ea
0003160 37 2d fa a0 63 6d d7 ba 9f 3a d9 7b dd 72 2e 5b
0003200 bf e8 d1 3a d6 12 7f 50 33 c4 b2 e1 06 93 1a 66
0003220 7c d2 ba 67 81 b5 55 d6 f9 29 cf 71 ae 34 2f 8b
0003240 54 ce 9d f3 b8 ca ad cd 77 6a f6 54 76 b1 5e 43
0003260 49 28 c2 35 99 20 d3 b8 78 20 88 46 8d 29 8e 64
0003300 7a f1 e6 7c da 60 c4 64 94 a4 65 61 32 a3 d3 f6
0003320 14 bf a2 0d 71 32 0d cb 6e ce 58 8d c1 9b 8d 94
0003340 85 52 d4 8b 69 8d 09 0f 7a b1 a8 8e fd 16 a8 2c
0003360 7f 51 71 af 3b a9 6f da 8f 90 ec 0d 0c 98 d5 10
0003400 09 58 9a ff 3b ed 7e a3 5c 23 bf 9e be ff b6 d8
0003420 77 6b d3 96 55 f8 c1 71 29 15 18 4e 2b 7f 22 42
0003440 3e 01 49 02 82 01 00 56 c2 a8 32 2a 81 40 00 00 <== Here Lenth 01 00 = 256
0003460 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
0004440 00 00 00 00 00 00 00 00 00 00 00
0004453
Get us a template to work off:
$ openssl genrsa -out dummy.pem 4096`
$ openssl rsa -in dummy.pem -inform pem -text | grep -B1 -A2 "^[a-z].*:"
writing RSA key
Private-Key: (4096 bit, 2 primes)
modulus:
00:c5:4c:2b:86:bc:39:a6:f0:2d:ec:d2:02:52:70:
f6:c3:6e:10:4a:d2:a3:41:f7:10:2f:9f:17:40:b1:
--
68:5f:01
publicExponent: 65537 (0x10001)
privateExponent:
05:ec:a3:30:f4:f5:76:8e:67:3e:a1:7c:14:32:d4:
02:15:cb:be:47:6e:c3:64:12:69:1a:54:9b:2a:c6:
--
30:9d
prime1:
00:e6:e8:bf:dd:00:f9:80:9d:41:de:f2:48:8e:f4:
84:60:17:b0:85:9a:e6:14:1c:50:ec:42:85:fe:8e:
--
b7:15
prime2:
00:da:bc:70:37:38:b5:6d:7a:56:e9:01:fb:c8:7c:
01:39:86:48:f3:d6:2b:d7:9d:a7:41:18:0d:45:28:
--
83:3d
exponent1:
00:d0:5b:34:c5:37:1b:eb:f1:fa:7e:32:21:46:dd:
5c:95:58:ca:ef:c3:d5:d8:4f:b4:b5:7b:51:6d:61:
--
0c:01
exponent2:
6d:3a:c2:b2:e0:cf:c0:de:e1:fd:b3:ae:df:3c:05:
84:8b:69:6c:d2:9b:cc:2d:7f:33:43:66:85:0d:ca:
--
65
coefficient:
00:b5:85:21:b4:a7:28:3d:0a:32:5c:cb:ad:e6:f4:
7a:bb:8f:8a:37:32:f7:d5:a6:1f:e6:9c:be:cf:49:
$ cat dummy.pem | grep -v '\-\-\-' | base64 -d | od -tx1
Note that(in dummy): exponent 2 is 256 long
Prime1 is at 0x2063 (after header)
Prime2 is at 0x2468
- prime1 @ 0x2063 -
mlashley@home ~/ctf/snyk_2023/s_h $ cat dummy.pem | grep -v '\---' | base64 -d | od -tx1 | grep "00 e6 e8"
0002060 82 01 01 00 e6 e8 bf dd 00 f9 80 9d 41 de f2 48
- prime2 @ 0x2468 -
mlashley@home ~/ctf/snyk_2023/s_h $ cat dummy.pem | grep -v '\---' | base64 -d | od -tx1 | grep "00 da bc"
0002460 f9 82 b7 15 02 82 01 01 00 da bc 70 37 38 b5 6d
We presumably have
- last 26 bytes of prime1
- all of prime2
- all of exponent1
- first 6-7 bytes of exponent 2.
We don't know e, it is not 65537 or 3 - but we can loop:
from Crypto.Util.number import isPrime
q = 0x00d87ad2e58f56639c46b89606dfecaf6b8bea158617081aa690f3aec4d879f83711d31a454130aaa11e61f603073f968ac062b710865f1eb7a9c1d57eaa93ac35f642d768ca063354dae239c3050cc9d00f3eb72f04b8cbd174d8a51c11143ff94a8dcad8e164a089a79a5c51cc06aa3c156849aa537d0e0acf059d7d361953bc84d6f7e09e5c97b78157a5083829b6b4275ff613af6395ab926c6fff754b50f81e3ef67cffc12b3b8f03781554c24e756f4d8e70d559c33d316ab02cdfb651855645c63c5c51527a20173762037bf536b547423d6825826abb07fa2d9b249fe7f1a305d6ae32423703de68ccebe38236a1ff021e44dfc1a38cca949d9613627d
dp = 0x00dfa80f4d6de1e50097b8c7ba7bf3aabad27362055b59653c1d5a05e7b6364ca6589a5b5510c8e7f69fc5cd1681c237d712fa46f214484901f1b7eb9478188c80ea1af464a8d244f5bfe60ac8ea372dfaa0636dd7ba9f3ad97bdd722e5bbfe8d13ad6127f5033c4b2e106931a667cd2ba6781b555d6f929cf71ae342f8b54ce9df3b8caadcd776af65476b15e434928c2359920d3b8782088468d298e647af1e67cda60c46494a4656132a3d3f614bfa20d71320dcb6ece588dc19b8d948552d48b698d090f7ab1a88efd16a82c7f5171af3ba96fda8f90ec0d0c98d51009589aff3bed7ea35c23bf9ebeffb6d8776bd39655f8c1712915184e2b7f22423e0149
for e in range (3,65537,2):
for kp in range(3, e):
p_mul = dp * e - 1
if p_mul % kp == 0:
p = (p_mul // kp) + 1
if isPrime(p):
print(f"e={e} Possible p: {p}")
We'll get a bunch of hits - but lets assume 257
e=257 Possible p: 31686209390529354241433907795352571491489917615595621321321201588761706744164594592960435777189570873850993450698178650526527668343711713183336134946920259966369686101403002660496913974177718643484139114550519651282259720248918194296172753679890180854173308282138472794672574658704199752778207419128806160632991702532034274668465745841499860296216977325800120273277300699669501432751243687523313445472221114032700313583212605660944200321468627784426897269244974563038525009222035926245152790119097539578334113376327464030858573930361855845071495333920879519107626372093533166962253423425223289203575933767091348087977
We cannot test against the Modulus as we have no parts...
We do some validatons, and write out a key:
#!/usr/bin/python3
from Crypto.Util.number import isPrime
from Crypto.PublicKey import RSA
e=257
p=31686209390529354241433907795352571491489917615595621321321201588761706744164594592960435777189570873850993450698178650526527668343711713183336134946920259966369686101403002660496913974177718643484139114550519651282259720248918194296172753679890180854173308282138472794672574658704199752778207419128806160632991702532034274668465745841499860296216977325800120273277300699669501432751243687523313445472221114032700313583212605660944200321468627784426897269244974563038525009222035926245152790119097539578334113376327464030858573930361855845071495333920879519107626372093533166962253423425223289203575933767091348087977
q=0x00d87ad2e58f56639c46b89606dfecaf6b8bea158617081aa690f3aec4d879f83711d31a454130aaa11e61f603073f968ac062b710865f1eb7a9c1d57eaa93ac35f642d768ca063354dae239c3050cc9d00f3eb72f04b8cbd174d8a51c11143ff94a8dcad8e164a089a79a5c51cc06aa3c156849aa537d0e0acf059d7d361953bc84d6f7e09e5c97b78157a5083829b6b4275ff613af6395ab926c6fff754b50f81e3ef67cffc12b3b8f03781554c24e756f4d8e70d559c33d316ab02cdfb651855645c63c5c51527a20173762037bf536b547423d6825826abb07fa2d9b249fe7f1a305d6ae32423703de68ccebe38236a1ff021e44dfc1a38cca949d9613627d
p_lower_bits = 0x80f7e3bb50d683125958a87fa97a1f7fe3773e30823ca4a9
dp= 0x00dfa80f4d6de1e50097b8c7ba7bf3aabad27362055b59653c1d5a05e7b6364ca6589a5b5510c8e7f69fc5cd1681c237d712fa46f214484901f1b7eb9478188c80ea1af464a8d244f5bfe60ac8ea372dfaa0636dd7ba9f3ad97bdd722e5bbfe8d13ad6127f5033c4b2e106931a667cd2ba6781b555d6f929cf71ae342f8b54ce9df3b8caadcd776af65476b15e434928c2359920d3b8782088468d298e647af1e67cda60c46494a4656132a3d3f614bfa20d71320dcb6ece588dc19b8d948552d48b698d090f7ab1a88efd16a82c7f5171af3ba96fda8f90ec0d0c98d51009589aff3bed7ea35c23bf9ebeffb6d8776bd39655f8c1712915184e2b7f22423e0149
dq_upper_bits = 0x56c2a8322a81
N = p*q
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
# We have found the two prime factors of the modulus
assert isPrime(p) and isPrime(q) and p*q == N
# Our private exponent matches that from dp recovered
assert d % (p-1) == dp
## The top bits of the Modulus match those recovered
#assert hex(N).startswith(hex(N_upper_bits))
# The prime p matches the low bits
assert hex(p).endswith(hex(p_lower_bits)[2:])
# The derived dq matches the recovered upper bits of dq
assert hex(d % (q-1)).startswith(hex(dq_upper_bits))
key = RSA.construct((N,e,d,p,q))
pem = key.export_key('PEM')
print(pem.decode())
Use that key to access the challenge server:
mlashley@home ~/ctf/snyk_2023/s_h $ ssh -p 32323 -i full_key_recovered.pem challenge@challenge.ctf.games cat flag.txt
flag{67128130ce65193ab51d6e18bd44eb87}