# S_H

Challenge starts with redacted

`SSH`

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-----

First and last line is crusial to discover what format key is exported here there is:

-----BEGIN RSA PRIVATE KEY-----

That means this is using

`DER Distinguished Encoding Rules`

But it can be also-----BEGIN OPENSSH PRIVATE KEY-----

which mean key is exported in slightly differetnt format this challengese use first option. But for OPENSSH format description is here https://dnaeon.github.io/openssh-private-key-binary-format/

and looks like that

// AUTH_MAGIC is a hard-coded, null-terminated string,

// set to "openssh-key-v1".

byte[n] AUTH_MAGIC

// ciphername determines the cipher name (if any),

// or is set to "none", when no encryption is used.

string ciphername

// kdfname determines the KDF function name, which is

// either "bcrypt" or "none"

string kdfname

// kdfoptions field.

// This one is actually a buffer with size determined by the

// uint32 value, which preceeds it.

// If no encryption was used to protect the private key,

// it's contents will be the [0x00 0x00 0x00 0x00] bytes (empty string).

// You should read the embedded buffer, only if it's size is

// different than 0.

uint32 (size of buffer)

string salt

uint32 rounds

// Number of keys embedded within the blob.

// This value is always set to 1, at least in the

// current implementation of the private key format.

uint32 number-of-keys

// Public key section.

// This one is a buffer, in which the public key is embedded.

// Size of the buffer is determined by the uint32 value,

// which preceeds it.

// The public components below are for RSA public keys.

uint32 (size of buffer)

string keytype ("ssh-rsa")

mpint e (RSA public exponent)

mpint n (RSA modulus)

// Encrypted section

// This one is a again a buffer with size

// specified by the uint32 value, which preceeds it.

// The fields below are for RSA private keys.

uint32 (size of buffer)

uint32 check-int

uint32 check-int (must match with previous check-int value)

string keytype ("ssh-rsa")

mpint n (RSA modulus)

mpint e (RSA public exponent)

mpint d (RSA private exponent)

mpint iqmp (RSA Inverse of Q Mod P, a.k.a iqmp)

mpint p (RSA prime 1)

mpint q (RSA prime 2)

string comment (Comment associated with the key)

byte[n] padding (Padding according to the rules above)

But that is out of the scope of this challenge. This use use DER and this is

**type-length-value**encoding.Each

**type**is defined as follows:type (hex) | Description |
---|---|

02 | Integer |

03 | Bit String |

04 | Octet String |

05 | NULL |

06 | Object Identifier |

0C | UTF8String |

10 (or 30)* | Sequence and Sequence of |

11 (or 31)* | Set and Set of |

13 | PrintableString |

16 | IA5String |

17 | UTCTime |

18 | GeneralizedTime |

Two types with * are always encoded as 0x30 or 0x31, because 6th bit is used to indicate wheter a field is Constructed or Primitive, these two tags are always Constructed so thier encoding has bit 6 set to 1.

Example:

type | length | value |
---|---|---|

02 | 03 | 110011 |

This can be read as

**INT**that is 3byte long and its value is 0b110011But

**length**can be saved in more deliberete way: if first octet after**type**have 8th bit set to 1 then it shows that**length**is written in**long form**so if next byte after**type**starts with 0x8X it means that it uses long form of length encoding and value of X**describe length in bytes**Example:

type | length | value |
---|---|---|

02 | 82 01 01 | 00 D8 7A ...[snipped]... |

So here it is type

**INT**with long form of length- 0x82 0x80 confirm long from and 2 says that length is encoded on 2 byte so 0x0101 is full length

X.690

Wikipedia

Source

Key can be decoded from

`base64`

and saved as raw bytes. This allows for decoding it by hand. To do that first and last line need to be deleted as `-----BEGIN RSA PRIVATE KEY-----`

isn't valid base64.Decoded and save key looks like this:

Most of the key is missing but compare it with

**dummy generated key**This article says that 0x0282 is header where the most important values are`p`

,`q`

,`dp`

,`dq`

,`N`

, Seraching through

**dummy key**there are 7 hitsRunning it on obfuscated key it results only in 3 hits, but offsets are simillar.

RSAPrivateKey ::= SEQUENCE {

version Version,

modulus INTEGER, -- n

publicExponent INTEGER, -- e

privateExponent INTEGER, -- d

prime1 INTEGER, -- p

prime2 INTEGER, -- q

exponent1 INTEGER, -- d mod (p-1)

exponent2 INTEGER, -- d mod (q-1)

coefficient INTEGER, -- (inverse of q) mod p

otherPrimeInfos OtherPrimeInfos OPTIONAL

}

By keeping in mind this

**private key format**and applying it to**dummy key**also assuming that`e`

is small so it isn't using long lenght encoding and `coefficient`

can be quite big so it is using it. Data should be as follow:`coefficient`

at offset 829`dq`

at offset 724`dp`

at offset 61F`q`

at offset 51A`p`

at offset 415`d`

at offset 211

So applying it to challenge redacted key:

- coefficient is missing
- there are some first bytes of
`dq`

(offset 723) - there is whole
`dp`

(offset 61E) - there is whole prime
`q`

(offset 519)

And all of this allows for recovering private key as according to (page 8)

e*dp = kp*(p-1) + 1

and this allows for

`p`

bruteforcing as `kp < e`

After some maths shananigansp = (e*dp-1)/kp + 1

Appart from

`p`

value some other values needs to be calculated- Private exponent
`d = pow(e, -1, (possible_p-1)*(q-1))`

- Second exponent
`dq = d % (q-1)`

- Modulus
`N = possible_p * q`

Putting it togheter:

from Crypto.Util.number import isPrime

from Crypto.PublicKey import RSA

# RSAPrivateKey ::= SEQUENCE {

# version Version,

# modulus INTEGER, -- n

# publicExponent INTEGER, -- e

# privateExponent INTEGER, -- d

# prime1 INTEGER, -- p

# prime2 INTEGER, -- q

# exponent1 INTEGER, -- d mod (p-1)

# exponent2 INTEGER, -- d mod (q-1)

# coefficient INTEGER, -- (inverse of q) mod p

# otherPrimeInfos OtherPrimeInfos OPTIONAL

# }

#upper bits of dq

dq = 0x56C2A8322A8140

#whole dp

dp=0x00DFA80F4D6DE1E50097B8C7BA7BF3AABAD27362055B59653C1D5A05E7B6364CA6589A5B5510C8E7F69FC5CD1681C237D712FA46F214484901F1B7EB9478188C80EA1AF464A8D244F5BFE60AC8EA372DFAA0636DD7BA9F3AD97BDD722E5BBFE8D13AD6127F5033C4B2E106931A667CD2BA6781B555D6F929CF71AE342F8B54CE9DF3B8CAADCD776AF65476B15E434928C2359920D3B8782088468D298E647AF1E67CDA60C46494A4656132A3D3F614BFA20D71320DCB6ECE588DC19B8D948552D48B698D090F7AB1A88EFD16A82C7F5171AF3BA96FDA8F90EC0D0C98D51009589AFF3BED7EA35C23BF9EBEFFB6D8776BD39655F8C1712915184E2B7F22423E0149

#whole q

q=0x00D87AD2E58F56639C46B89606DFECAF6B8BEA158617081AA690F3AEC4D879F83711D31A454130AAA11E61F603073F968AC062B710865F1EB7A9C1D57EAA93AC35F642D768CA063354DAE239C3050CC9D00F3EB72F04B8CBD174D8A51C11143FF94A8DCAD8E164A089A79A5C51CC06AA3C156849AA537D0E0ACF059D7D361953BC84D6F7E09E5C97B78157A5083829B6B4275FF613AF6395AB926C6FFF754B50F81E3EF67CFFC12B3B8F03781554C24E756F4D8E70D559C33D316AB02CDFB651855645C63C5C51527A20173762037BF536B547423D6825826ABB07FA2D9B249FE7F1A305D6AE32423703DE68CCEBE38236A1FF021E44DFC1A38CCA949D9613627D

#Acording to Recovering cryptographic keys from partial information, by example https://hal.science/hal-03045663/document

# e*dp = kp*(p-1) + 1

# e*dq=1+kq*(q-1) + 1

#kp < e and kq > e

#This allows for bruteforcing `p` value

#with p=(e*dp-1)/kp + 1

public_exponent = 65537

#we need to bruteforce both values `e` and `kp` for finding p

killswitch = False

for e in range(3, public_exponent):

for kp in range(1,e):

possible_p = (e * dp -1)//kp +1

if isPrime(possible_p):

print(f"p candidate {str(possible_p)[:20]}...[snipp]...")

N = possible_p * q

#math is hard there is some error for some primes base is non invertable so i just skip it i hope it work #todd_howard

try:

d = pow(e, -1, (possible_p-1)*(q-1))

except:

continue

possible_dp = d % (possible_p-1)

if possible_dp == dp:

possible_dq = d % (q-1)

if hex(possible_dq).startswith(hex(dq)):

dq = possible_dq

print("It just works - dq match")

print(f"found exact prime: {possible_p}")

print(f"Found e: {e}")

print(f"Found d: {d}")

print(f"Found N: {N}")

p = possible_p

found_e = e

found_d = d

found_N = N

killswitch = True

if killswitch:

break

# so now we know everything to construct RSA key (N,p,q,e,d)

reconstructed_key = RSA.construct((found_N,found_e,found_d,p,q))

pem = reconstructed_key.exportKey("PEM")

print(pem.decode())

There is one assumption done as there is no known

`e`

value I assumed it is no larger than usual `65537`

Output of code above is recovered private SSH key

That allows login to the server

Just a funny cat hacking into nsa

Last modified 4mo ago