TRYHACKME BREAKING RSA

Introduction

Welcome to my write-up for the Breaking RSA room on TryHackMe! While many penetration testing labs focus on exploiting software flaws or misconfigurations, this room shows us how cryptography and mathematics are principle of the job.

What is RSA?

RSA is a asymmetric algorithm which The security of this algorithm lies in the fact that multiplying two very large prime numbers is easy, but factoring this enormous product back into its prime factors (integer factorization) is extremely difficult for current computers.

How RSA Works?

1- We choose two distinct primes (p and q) and multiple them (n = p . q).

2- We calculate number of relatively primes with n by using Euler Function φ(n) = (p-1) . (q-1).

3- We choose an integer such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. This integer (e) will be source of our public key.

4- We determine another integer d, by using d ≡ e^(-1) (mod φ(n)) which means e . d ≡ 1 (mod φ(n)). By using Bezout Theorem on e and φ(n) , e . d + φ(n) . y = 1 ≡ e . d (mod φ(n)) we can see an integer such as d always exist no matter which integer we chose e before. We can find the d with Euler Theorem, a^(φ(n)) ≡ 1 (mod n). We can rewrite the expression for our problem such that e^(φ(φ(n)) ≡ 1 (mod φ(n)) and also e . e^(φ(φ(n) — 1) ≡ 1 (modφ(n)). And we can choose d = e^(φ(φ(n) — 1). d is source of our private key.

5- We generate public key as (n , e) and private key as (n , d).

6- We represent the message to be sent with M (M < n) and ciphertext with C. We encrypt the message with C ≡ M^e (mod n) expression.

7- If we want decrypt the ciphertext we use d . e ≡ 1 (mod φ(n)) information and we apply on the encrpyt expression such that C^d ≡ M^ed (mod n). We can see M^ed ≡ M (mod n) with Chinese Remainder Theorem. So we simply see the decryption expression is C^d ≡ M (mod n).

Questions

Q1: How many services are running on the box?

basic nmap scan result of target

Answer: 2

Q2: What is the name of the hidden directory on the web server? (without leading ‘/’)

We can use “gobuster”.

• -u: We use for write target’s adress.
• -w: We use for select wordlist.

Answer: development

Q3: What is the length of the discovered RSA key? (in bits)

We visit the adress we found (http://10.112.136.158/development/).

We click on “id_rsa.pub” and download the key.

cat id_rsa.pub
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDrZh8oe8Q8j6kt26IZ906kZ7XyJ3sFCVczs1Gqe8w7ZgU+XGL2vpSD100andPQMwDi3wMX98EvEUbTtcoM4p863C3h23iUOpmZ3Mw8z51b9DEXjPLunPnwAYxhIxdP7czKlfgUCe2n49QHuTqtGE/Gs+avjPcPrZc3VrGAuhFM4P+e4CCbd9NzMtBXrO5HoSV6PEw7NSR7sWDcAQ47cd287U8h9hIf9Paj6hXJ8oters0CkgfbuG99SVVykoVkMfiRXIpu+Ir8Fu1103Nt/cv5nJX5h/KpdQ8iXVopmQNFzNFJjU2De9lohLlUZpM81fP1cDwwGF3X52FzgZ7Y67Je56Rz/fc8JMhqqR+N5P5IyBcSJlfyCSGTfDf+DNiioRGcPFIwH+8cIv9XUe9QFKo9tVI8ElE6U80sXxUYvSg5CPcggKJy68DET2TSxO/AGczxBjSft/BHQ+vwcbGtEnWgvZqyZ49usMAfgz0t6qFp4g1hKFCutdMMvPoHb1xGw9b1FhbLEw6j9s7lMrobaRu5eRiAcIrJtv+5hqX6r6loOXpd0Ip1hH/Ykle2fFfiUfNWCcFfre2AIQ1px9pL0tg8x1NHd55edAdNY3mbk3I66nthA5a0FrKrnEgDXLVLJKPEUMwY8JhAOizdOCpb2swPwvpzO32OjjNus7tKSRe87w==

As we can see we succesfully download the file. For observe anatomy of the key we can use ssh-keygen.

Answer: 4096

Q4: What are the last 10 digits of n? (where ’n’ is the modulus for the public-private key pair)

We don’t have any leaking information so best attack strategy is Fermat’s factorization attack. First, we need find n. We can write a simple python code.

from Crypto.PublicKey import RSA

key = RSA.import_key(open("id_rsa.pub").read())

print("\n:")
print(key.n)

You must install Crypto libary if you didn’t install

Answer: 1225222383

Q5: What is the numerical difference between p and q?

Now, we found n so we can find p and q with Fermat’s factorization attack. We can use the code given by THM.

#!/usr/bin/python3
# gmpy2 is a C-coded Python extension module that supports
# multiple-precision arithmetic.
# pip install gmpy2
from gmpy2 import isqrt
from math import lcm

def factorize(n):
    # since even nos. are always divisible by 2, one of the factors will
    # always be 2
    if (n & 1) == 0:
        return (n/2, 2)

    # isqrt returns the integer square root of n
    a = isqrt(n)

    # if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
    if a * a == n:
        return a, a

    while True:
        a = a + 1
        bsq = a * a - n
        b = isqrt(bsq)
        if b * b == bsq:
            break

    return a + b, a - b

print(factorize(960343778775549488806716229688022562692463185460664314559819511657255292180827209174624059690060629715513180527734160798185034958883650709727032190772084959116259664047922715427522089353727952666824433207585440395813418471678775572995422248008108462980790558476993362919639516120538362516927622315187274971734081435230079153205750751020642956757117030852053008146976560531583447003355135460359928857010196241497604249151374353653491684214813678136396641706949128453526566651123162138806898116027920918258136713427376775618725136451984896300788465604914741872970173868541940675400325006679662030787570986695243903017923121105483935334289783830664260722704673471688470355268898058414366742781725580377180144541978809005281731232604162936015554289274471523038666760994260315829982230640668811250447030003462317740603204577123985618718687833015332554488836087898084147236609893032121172292368637672349405254772581742883431648376052937332995630141793928654990078967475194724151821689117026010445305375748604757116271353498403318409547515058838447618537811182917198454172161072247021099572638700461507432831248944781465511414308770376182766366160748136532693805002316728842876519091399408672222673058844554058431161474308624683491225222383)) // n

We found both p and q.

p = 30989413979221186440875537962143588279079180657276785773483163084840787431751925008409382782024837335054414229548213487269055726656919580388980384353939415484564294377142773553463724248812140196477077493185374579859773369113593661078143295090153526634169495633688691753691720088511452131593712380121967802013042678209312444897975134224456911144218687330712554564836016616829044029963400114373142702236623994027926718855592051277298418373056707389464234977873660836337340136755093657804153998347162906059312569124331219753644648657722107663012261197728061352359157767204739644300066112274629356310784052940617408518123
q = 30989413979221186440875537962143588279079180657276785773483163084840787431751925008409382782024837335054414229548213487269055726656919580388980384353939415484564294377142773553463724248812140196477077493185374579859773369113593661078143295090153526634169495633688691753691720088511452131593712380121967802013042678209312444897975134224456911144218687330712554564836016616829044029963400114373142702236623994027926718855592051277298418373056707389464234977873660836337340136755093657804153998347162906059312569124331219753644648657722107663012261197728061352359157767204739644300066112274629356310784052940617408516621

Simply we substract primes from each other.

Answer: 1502

Q6: What is the flag?

We generate private key file with Euler and Euclid algorithm which i mention “How RSA Works” part.

from Crypto.PublicKey import RSA

p = 30989413979221186440875537962143588279079180657276785773483163084840787431751925008409382782024837335054414229548213487269055726656919580388980384353939415484564294377142773553463724248812140196477077493185374579859773369113593661078143295090153526634169495633688691753691720088511452131593712380121967802013042678209312444897975134224456911144218687330712554564836016616829044029963400114373142702236623994027926718855592051277298418373056707389464234977873660836337340136755093657804153998347162906059312569124331219753644648657722107663012261197728061352359157767204739644300066112274629356310784052940617408518123
q = 30989413979221186440875537962143588279079180657276785773483163084840787431751925008409382782024837335054414229548213487269055726656919580388980384353939415484564294377142773553463724248812140196477077493185374579859773369113593661078143295090153526634169495633688691753691720088511452131593712380121967802013042678209312444897975134224456911144218687330712554564836016616829044029963400114373142702236623994027926718855592051277298418373056707389464234977873660836337340136755093657804153998347162906059312569124331219753644648657722107663012261197728061352359157767204739644300066112274629356310784052940617408516621

e = 65537 

print("calculating...")

n = p * q

phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

key = RSA.construct((n, e, d, p, q))

with open("private_key.pem", "wb") as f:
    f.write(key.export_key("PEM"))

print("private_key.pem succesfully created.")

Finally we are ready connect target sistem via ssh and capture the flag.