2024-11-09

Purple Pill CTF 2024 - Legend[crypto]

Purple Pill CTF 2024 writeup for the challenge legend (crypto)

Difficulty : Easy (imo)

Team : Phreaks 2600

Description :

FR : Nous fournissons notre chiffrement pour le système de points secrets de MegaCorp, nous pensons que tout est sécurisé, pouvez-vous essayer ?

EN : We provide our encryption for MegaCorp’s secret points system, we think everything is secure, can you check?

Author : Yogosha

TL;DR

The flag is converted to binary
For bit = ‘1’: $ a^{e} \equiv n \mod p $ is stored
For bit = ‘0’: $ -n \mod p $ is stored
Using legendre symbol, we can recover if it was a 1 or 0 and recover the flag

Introduction

We are provided a simple custom encryption algorithm using modular arithmetic and powers. We also got the output of the encryption.

player.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b"PPC2024{REDACTED}"


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) # chaque caractère to binaire
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p) 
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext

print(encrypt_flag(FLAG))

'''
    [828385226842191, 884750330806283, 388570376230914, 205778797108144, 638369485764265, 69553132238148, 914460818501558, 13379099491480, 413346006831117, 741990430872996, 404039335154972, 337032981465603, 813973495213166, 849525080960656, 469174126189644, 454412813601180, 224421703708509, 312511174463140, 361563200570126, 847258418044783, 162086149759169, 381850173544007, 197363232503970, 845828471250686, 106660093241302, 947502641559183, 315391286945203, 450457288568455, 892168892661339, 948435665125264, 239805296072908, 544476170770024, 819902082919125, 539069227549429, 540656081002047, 331630242769344, 664716916353105, 244752846739769, 819038499760649, 78470407305005, 317015896320788, 772740995468290, 558472131576413, 563751162082506, 66131311572166, 495470153223431, 453455959350407, 812416491005115, 212301471971528, 1001728315460707, 360182719076079, 403131883381677, 212096731053902, 315118136060712, 38703242475581, 904284254966929, 123025326268469, 53773098486664, 651530957443841, 73799825375654, 990445098510197, 872146702664040, 533382695643271, 683138683037949, 221226605405410, 20318989875754, 153638102855200, 553781554977906, 962377297451780, 509279211769760, 591168720293735, 916600918386333, 675052877320757, 611448601932642, 861298336449398, 675758433888843, 567236338543871, 194562492980741, 753962336111480, 942900772057946, 527383061956393, 886878317000835, 738951041753626, 44079826078335, 705912019707333, 613504834174280, 426753983673881, 158254296021228, 925240206539261, 445845549405730, 333581201702230, 278659615053609, 71593005652192, 439519132324054, 84664430167409, 619229613229618, 696678989147946, 501941148845726, 125793184976446, 310783557359522, 900188720208438, 81956682753876, 822734158955703, 749169043596199, 847258212995182, 429799246097054, 922539937592645, 892180612498511, 201050027693215, 605295024001706, 340116423010122, 864152875089762, 875246480087219, 846788671570737, 156127780686744, 426857113953329, 813647847792868, 750885942922158, 483654113690232, 705769576241822, 704037794995886, 595670251761290, 460047193028596, 60267611451148, 729026604258752, 955862092867721, 649013949112319, 99731746970076, 962655632565009, 862315496302689, 894631209776222, 60616076696180, 61636549669898, 132275476007143, 397062636321012, 391042343948712, 652407418227371, 41784745558361, 440160938480014, 887339419649672, 231158422246203, 744801114788651, 803151388477335, 966379522368877, 857392667751251, 677775640693699, 420221354559703, 897414273163298, 110416417065392, 192000016421537, 252036767375257, 731057157140649, 8925182150751, 189898494578180, 184286771933789, 794384054994436, 399657459187255, 842625003035788, 950266212513231, 338194429031718, 722742388283523, 925408068530869, 24646943304551, 73238636644961, 616930400333127, 187081361951157, 248019083721065, 251157441712705, 804702148212411, 505525909601862, 34414520827564, 477455633131130, 426992447741910, 709019745087039, 258854132367952, 842927628930359, 131285629402068, 510974599417228, 789632741612521, 885251829020685, 435708837785478, 428099314696031, 186546641692708, 821278660764656, 962423218529295, 628355072214389, 367582360674662, 770035005833105, 133988077113241, 938708027986090, 147527088740717, 363893058407270, 915715055205114, 428717951140847, 302121462874300, 193699709418485, 375961454982136, 809826176809785, 89863346252234, 71706561241191, 974009468772679, 473200886829824, 221557310112488, 342897908810582, 217512190895301, 796785920906820, 40469251248088, 426078253285341, 16222086473744, 646482470054426, 692824995159910, 587814176266800, 427387397818853, 921630362114332, 649035217466289, 218051970393608, 470302751708131, 880281936801962, 350096517731954, 241359150225626, 836193267072137, 107539075393329, 138104764093741, 674632839526888, 804696787629961, 640805046781299, 963470988829567, 50821721702212, 643969147535178, 631762494747104, 60176507269066, 733015588136338, 78624201754536, 15708594773324, 403448455423321, 508551344914849, 750688474426581, 795481489053587, 853152575969425, 917476993113167, 83807873375891, 964300249453063, 266711214861811, 1000361881119009, 232177426323349, 97716719767841, 665413222785511, 234108433674735, 68687047057345, 625433668759702, 873128553138350, 942502721284303, 165886284006184, 299851912084940, 273163860732884, 918910288014889]
'''

Reading the code, it’s easy to understand that we will have to work with the output to recover the value.

Solving

Reading source code

Source code is quite simple to read.

Two number are defined :

$ a = 288260533169915 $ (which is not prime)
$ p = 1007621497415251 $ (which is prime)

These number will be used to generate the encrypted values.

We got the encrypt_flag() function :

encrypt_flag()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext

Each character of the flag is converted to binary and prepended with zeros (if necessary) to make it to a length of 8 plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) which returns a long string of zeros and ones.

Then for every bit, a random value $ e < p $ is generated and a value n = $ a^{e} \mod p $.

If the bit value is 1, n is stored untouched, else -n % p is stored in ciphertext.

The ciphertext list is returned and that’s it.

Finding the vulnerability

For this one I had the cursed idea to think I could find e which refer to the problem of the discrete logarithm (finding x such as $ g^{x} \equiv y \mod p $ with g,y and p known) but that’s not the point of the challenge.

Another idea I got is to try to find if encrypted ‘1’ values have common propreties and same with ‘0’ bits.

Since n is the result of a power, we can think of quadratic residues

Saying that n is quadrtic means that it exists a k such that $ n \equiv k^{2} \mod p $.

It simply mean that $n$ is the result of a number to the power of 2 modulo p.

So I thought that it should work not only with the power of 2 but any power.

We can now if a number is a quadratic residue using LEGENDre symbol. (more here)

There is a nice module on cryptohack teaching about these.

In shorts, we compute $ n^{\frac{p-1}{2}} \mod p $

if 1 : it is a quadratic residue
if -1 : it is not

We can test it with this code snippet :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


from random import randint

a = 288260533169915
p = 1007621497415251

for i in range(10):
    e = randint(1, p)
    n = pow(a, e, p)

    print(pow(n, (p-1)//2, p))

Which outputs 10 ‘1’. So, $ a^{e} \mod p$ generates quadratic residues.

We can write $ n^{\frac{p-1}{2}} \equiv 1 \mod p $.

So : $ (-n)^{\frac{p-1}{2}} \equiv -1 \equiv p - 1 \equiv 1007621497415250 \mod p $

We can now recover every bit value by calculating the quadratic residues.

Solve script

solve_legend.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


output = [828385226842191, 884750330806283, 388570376230914, 205778797108144, 638369485764265, 69553132238148, 914460818501558, 13379099491480, 413346006831117, 741990430872996, 404039335154972, 337032981465603, 813973495213166, 849525080960656, 469174126189644, 454412813601180, 224421703708509, 312511174463140, 361563200570126, 847258418044783, 162086149759169, 381850173544007, 197363232503970, 845828471250686, 106660093241302, 947502641559183, 315391286945203, 450457288568455, 892168892661339, 948435665125264, 239805296072908, 544476170770024, 819902082919125, 539069227549429, 540656081002047, 331630242769344, 664716916353105, 244752846739769, 819038499760649, 78470407305005, 317015896320788, 772740995468290, 558472131576413, 563751162082506, 66131311572166, 495470153223431, 453455959350407, 812416491005115, 212301471971528, 1001728315460707, 360182719076079, 403131883381677, 212096731053902, 315118136060712, 38703242475581, 904284254966929, 123025326268469, 53773098486664, 651530957443841, 73799825375654, 990445098510197, 872146702664040, 533382695643271, 683138683037949, 221226605405410, 20318989875754, 153638102855200, 553781554977906, 962377297451780, 509279211769760, 591168720293735, 916600918386333, 675052877320757, 611448601932642, 861298336449398, 675758433888843, 567236338543871, 194562492980741, 753962336111480, 942900772057946, 527383061956393, 886878317000835, 738951041753626, 44079826078335, 705912019707333, 613504834174280, 426753983673881, 158254296021228, 925240206539261, 445845549405730, 333581201702230, 278659615053609, 71593005652192, 439519132324054, 84664430167409, 619229613229618, 696678989147946, 501941148845726, 125793184976446, 310783557359522, 900188720208438, 81956682753876, 822734158955703, 749169043596199, 847258212995182, 429799246097054, 922539937592645, 892180612498511, 201050027693215, 605295024001706, 340116423010122, 864152875089762, 875246480087219, 846788671570737, 156127780686744, 426857113953329, 813647847792868, 750885942922158, 483654113690232, 705769576241822, 704037794995886, 595670251761290, 460047193028596, 60267611451148, 729026604258752, 955862092867721, 649013949112319, 99731746970076, 962655632565009, 862315496302689, 894631209776222, 60616076696180, 61636549669898, 132275476007143, 397062636321012, 391042343948712, 652407418227371, 41784745558361, 440160938480014, 887339419649672, 231158422246203, 744801114788651, 803151388477335, 966379522368877, 857392667751251, 677775640693699, 420221354559703, 897414273163298, 110416417065392, 192000016421537, 252036767375257, 731057157140649, 8925182150751, 189898494578180, 184286771933789, 794384054994436, 399657459187255, 842625003035788, 950266212513231, 338194429031718, 722742388283523, 925408068530869, 24646943304551, 73238636644961, 616930400333127, 187081361951157, 248019083721065, 251157441712705, 804702148212411, 505525909601862, 34414520827564, 477455633131130, 426992447741910, 709019745087039, 258854132367952, 842927628930359, 131285629402068, 510974599417228, 789632741612521, 885251829020685, 435708837785478, 428099314696031, 186546641692708, 821278660764656, 962423218529295, 628355072214389, 367582360674662, 770035005833105, 133988077113241, 938708027986090, 147527088740717, 363893058407270, 915715055205114, 428717951140847, 302121462874300, 193699709418485, 375961454982136, 809826176809785, 89863346252234, 71706561241191, 974009468772679, 473200886829824, 221557310112488, 342897908810582, 217512190895301, 796785920906820, 40469251248088, 426078253285341, 16222086473744, 646482470054426, 692824995159910, 587814176266800, 427387397818853, 921630362114332, 649035217466289, 218051970393608, 470302751708131, 880281936801962, 350096517731954, 241359150225626, 836193267072137, 107539075393329, 138104764093741, 674632839526888, 804696787629961, 640805046781299, 963470988829567, 50821721702212, 643969147535178, 631762494747104, 60176507269066, 733015588136338, 78624201754536, 15708594773324, 403448455423321, 508551344914849, 750688474426581, 795481489053587, 853152575969425, 917476993113167, 83807873375891, 964300249453063, 266711214861811, 1000361881119009, 232177426323349, 97716719767841, 665413222785511, 234108433674735, 68687047057345, 625433668759702, 873128553138350, 942502721284303, 165886284006184, 299851912084940, 273163860732884, 918910288014889]

for v in output :
    if pow(v, (p-1)//2, p) == 1:
        recovered+="1"
    else:
        recovered+="0"

recovered_bits = [recovered[i:i+8] for i in range(0, len(recovered), 8)]
print(''.join([chr(int(c, 2)) for c in recovered_bits]))

FLAG : PPC2024{legendre_symbol?was_it?}

Conclusion

That was a nice way to remind me some basics of modular arithmetic. It was only after solving that I noticed that the name of the challenge was an hint.

clueless