X-CTF is a capture the flag competition in Singapore organized by NUS Greyhats. The online qualifiers took place over the weekend of 9 - 10 April 2016. Halfway through the competition, we realize that the challenges were solved pretty quickly by the participants, and thus I wrote some new challenges. The following two challenges were by me.

Fact0r!z3

Category: Crypto
Description Can you decrypt this?
Encrypted.zip.

Solution

This is a simple challenge, I made this as a prequel to the next challenge. The solution is to factorize the modulus value of the RSA public key, allowing you to calculate the decryption key.

After downloading the file, uncompress the archive file.

1
2
3
→ tar zxvf 4b5978caa2cef859f97d0443ada4db40
x 8987609732e4da707a5d7563bd619f53
x flag.enc

It’s quite obvious that we’re suppose to decrypt flag.enc in order to obtain the flag.

Using OpenSSL, we can obtain the content of the public key.

1
2
3
4
5
6
7
8
9
10
11
12
→ openssl rsa -text -pubin -in 8987609732e4da707a5d7563bd619f53
Modulus (447 bit):
    48:e8:f0:19:5d:8c:7b:0a:f1:4b:7f:ae:1b:d9:f8:
    e4:08:77:44:8e:66:44:e9:f5:83:cd:76:57:d2:36:
    5c:7f:83:51:99:08:e1:1f:6e:41:35:bb:f7:6a:76:
    b9:80:cc:d1:e6:99:43:dd:39:f5:3d
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MFMwDQYJKoZIhvcNAQEBBQADQgAwPwI4SOjwGV2MewrxS3+uG9n45Ah3RI5mROn1
g812V9I2XH+DUZkI4R9uQTW792p2uYDM0eaZQ9059T0CAwEAAQ==
-----END PUBLIC KEY-----

Using some python kungfu, we can obtain the Integer value of the Modulus to give : 207006830488235668671955689390815624796833363161842587562758966652474780634716637447867252305688653008916026906416134119860202636965181

Throw this into factordb.com, and we can see that this modulus value is easily factorized.

1
2
p = 3133337  
q = 66065932419090467661779020064172996647610315507665657272983712461339070975996720891454462863614304177595970974847625429329881413

Using RSAtool.py, we can reconstruct the private key file, allowing us to decrypt flag.enc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
→ python ~/CTF/tools/rsatool.py -p 3133337 -q 66065932419090467661779020064172996647610315507665657272983712461339070975996720891454462863614304177595970974847625429329881413 -e 65537 -o key.pem
Using (p, q) to initialise RSA instance

n =
48e8f0195d8c7b0af14b7fae1bd9f8e40877448e6644e9f583cd7657d2365c7f83519908e11f6e41
35bbf76a76b980ccd1e69943dd39f53d

e = 65537 (0x10001)

d =
d94d65c2a8045044cdf2ffaeb5ad759f5bf0b8584bb61f3bd878aa47267f99994b86491e0a427c57
2f77adc1ad492131dc6db513b3b221

p = 3133337 (0x2fcf99)

q =
18663ff92c4c79e1a244f109ad859cecfb34d162303f3f6e525e411dfa723a7a18af3732239f058b
2e524d819a28c3d4e9c4d83a945

Saving PEM as key.pem

→ openssl rsautl -decrypt -inkey key.pem -in flag.enc
XCTF{S33MZ_L!K3_Y0U_fact0r!zed_!T}

And we got the flag for the first part! XCTF{S33MZ_L!K3_Y0U_fact0r!zed_!T}

Fact0r!z3_aga!n

Category: Crypto
Description Can you decrypt it this time? A litle bird told me that if the d value is small, it would be possible.
Encrypted.zip.

This is the sequel to the previous challenge and as the sequel, it is considered more difficult. Likewise like the previous challenge, the objective of this challenge is to factorize the modulus value of the public key in order to reconstruct the private key.

There’s an additional hint provided here as well. A litle bird told me that if the d value is small, it would be possible.
This was hinting that the d value is small, and that certain RSA attack would work as the d value is smaller. In this case Wiener’s attack was possible as \(d<\frac{1}{3}n^\frac{1}{4}\).

Following the same steps as the previous challenge, we first obtain the modulus and e values of the public key.

1
2
n = 1358016654793718168576890372704045370292566693250198337571997713911873446535830350906288566272075747587625218927182158794773627266352290009114996887264885273166024519614459408235461543052969897056498639245852139107189600240612291331078593266375574088348938551792344519865321083218447570464200135681789040698448141245180753009200026942273771102971607691513134494634442001453402739091058614558399864407649009999241938404547068622618622996222788477239323058919028619017187860542797806083989245206963757505047738707660921123080733896257510371124808120528550409099172252647694465039601292947708319054049548469524371745309
e = 413646193299856964297595873583269391991677525082759838946971228433489444661147754904876781963643387300426778756247641221869815165656651791063782778832692165650632062745207006311718667769564624561939249776482558452967527416265195742164181060801895639268069202268063010541397525052398620760929202045239384126147631668142034495992456907185667803259903606787633599324685858845766860959168442908303044304319398713375708066833636555483932272992603871307617206789452044701736784287470883649969255328595694298117591936909898261849426261801035861462685108401288571621011309064307726074190651265291411002869221079175064335651

Googling around leads to a python script for the Wiener’s attack on a popular CTF team’s blog BalalaikaCr3w.

Running the script with the n and e value quickly provides us with the corresponding p and q values needed to reconstruct the private key.

1
2
3
4
→ python ~/CTF/tools/wiener_attack.py -n 1358016654793718168576890372704045370292566693250198337571997713911873446535830350906288566272075747587625218927182158794773627266352290009114996887264885273166024519614459408235461543052969897056498639245852139107189600240612291331078593266375574088348938551792344519865321083218447570464200135681789040698448141245180753009200026942273771102971607691513134494634442001453402739091058614558399864407649009999241938404547068622618622996222788477239323058919028619017187860542797806083989245206963757505047738707660921123080733896257510371124808120528550409099172252647694465039601292947708319054049548469524371745309 -e 413646193299856964297595873583269391991677525082759838946971228433489444661147754904876781963643387300426778756247641221869815165656651791063782778832692165650632062745207006311718667769564624561939249776482558452967527416265195742164181060801895639268069202268063010541397525052398620760929202045239384126147631668142034495992456907185667803259903606787633599324685858845766860959168442908303044304319398713375708066833636555483932272992603871307617206789452044701736784287470883649969255328595694298117591936909898261849426261801035861462685108401288571621011309064307726074190651265291411002869221079175064335651
-p 9137680666764853583548316438998008915285472636091785739594127466571221684684134296951534109078917008184054665081257177231154376919717493617815741914917972113486254132700066127081792088268751347553413815661030111443066402165891910883462831658451778251528180641983181467545471181983140196700930933918047320399
-q 148617215277946085196952504917545900921947201835121992590926549203285830240287840326685954338945019561925743147029298144273188382321071868867244770321808853004675177550018714209360479392000010200481086783373136532647862377216579620653192958581411929955913661912527040227235183587391150737375290030745978811091
-e 413646193299856964297595873583269391991677525082759838946971228433489444661147754904876781963643387300426778756247641221869815165656651791063782778832692165650632062745207006311718667769564624561939249776482558452967527416265195742164181060801895639268069202268063010541397525052398620760929202045239384126147631668142034495992456907185667803259903606787633599324685858845766860959168442908303044304319398713375708066833636555483932272992603871307617206789452044701736784287470883649969255328595694298117591936909898261849426261801035861462685108401288571621011309064307726074190651265291411002869221079175064335651

The following parts are done similar to the previous challenge.

1
2
→ openssl rsautl -decrypt -inkey key.pem -in flag.enc
XCTF{I_LIKE_SAUSAG3S_D0_Y0U}

And we got the flag for the second part! XCTF{I_LIKE_SAUSAG3S_D0_Y0U}

Hope you enjoyed the challenge, I’ll be writing the write up for b0verfl0w soon.