L4ugh

LLL Attack on Common Private Exponent RSA, Bit-flipping Attack on AES CBC via user-controlled iv

To solve this challenge we need to obtain both d_evil and d_good. There is a mathematical correlation between d_evil and d_good which can be used to obtain d. This d value is needed to enter the AES section and obtain the flag.

1st Step: Obtaining d_evil

We got this output from the program

option: {"option": "1"}
Ns=[63177871485525088951181443705081041461634543859522117456351661402080497656013624345546070712850495609948764684183439400179805537891875164625989052253083230659226521596768360072707440507270327177188344955333689656692052942117636523598888566332378334484989635662511781875819463942251573589312702111067666695137, 68417337722533900652500729977779356663072309260168978032066078964139516598349612942585273964747232440917208024070944878746826859130026151601011616528313228935586842217368126736111151916711142015199565420639331316508069640571601570035232358801113829472768752560859144386001410351637727931231353571569134609613, 168215881121069104898729985793627403151351981328884254464192670823030720417667002544672696986252246417961681145401431457093773120629615493457032091565389427445918129884222127717793599651891523817691046412371891919053448963038240278703665244310516285574823513905266879981762459903701984822492196244463862082391]
es=[12582085533392574037164768248411138060403343393202613693550614803000172294230368141692552003822419391035797084039299201901512976645994807330716118571915746013990494151810672823831168856260922412164054599692289888776400447431070962333675221317644750501553797025822331524893012554824564175094394720928485195797, 52991328407753481067902974746673138076572011687788467203911629995517206407307922740860404612421208610353519701472906794085957060352155035124317720744806171291972518225378971560363131225736966114292306895861938499450530895659529573837086398127260636837343320713697820328407358447537105167261121423215194249369, 12716000118173422228503985827797768395368925658432766439952368872498203791862354466845685008653376234224733294978052658757583825714636644392177238952806721471327627920018233106907442613769777864456001744370303817106405311946809104397220107151351200204233662456907101573711002774913538347184439597239543099945]

We are in a situation where we have a few public key pairs that were derived from the same private exponent (d_evil). This situation allows us to use Common Private Exponent Attack on RSA. We will be implementing this paper (https://www.ijcsi.org/papers/IJCSI-9-2-1-311-314.pdf) and using LLL to retrieve d_evil.

Solver to obtain d_evil (credit to https://github.com/ctfcompfest/compfest13-final/blob/master/cryptography/private/writeup/solve.py):

d_evil_solver.py

from pwn import *
import gmpy2
import os

Ns=[] #fill with the output for Ns
es=[] #fill with the output for es

def encrypt():
    e=es.pop(0)
    n=Ns.pop(0)
    return [e, n]

public_keys = []
r = 3
i = 0
while i < r:
    public_keys.append(encrypt())
    print(public_keys)
    public_keys = sorted(public_keys, key=lambda x : x[1])
    i += 1

# create the matrix
M = int(gmpy2.iroot(public_keys[-1][1], 2)[0])
matrix = [[0 for j in range(r + 1)] for i in range(r + 1)]
matrix[0][0] = M
for i in range(r):
    matrix[0][i + 1] = public_keys[i][0]
    matrix[i + 1][i + 1] = -public_keys[i][1]

matrix = str(matrix).replace(',', '')
f = open('matrix', 'w')
f.write(matrix)
f.close()

# using fplll (https://github.com/fplll/fplll)
res = os.popen('fplll -a lll matrix').read()
b1 = int(res.split(' ')[0][2:])
os.system('rm matrix')

# getting the d_evil
d = abs(b1) // M
print(d)

From the script above we got d_evil=15178928444351843699309490354280811018710625016309041634424791660221523247493518326239884724658824489

2nd Step: Obtaining d_good

This value is used for the payload on option 2:

In [1]: x=2**333 - 1

In [2]: x
Out[2]: 17498005798264095394980017816940970922825355447145699491406164851279623993595007385788105416184430591

We then got this output from the program:

option: {"option": "2"}
Enter your payload:     17498005798264095394980017816940970922825355447145699491406164851279623993595007385788105416184430591
RAND = [236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547831550342738774045316773280866091695446555852126352261762151935447363669066696571953760841997886810224, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547831978001113528054845433793564342301369403819891212871861733740351443965662510091142231166518463984432, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547834573620656556633444479386223647444145452246465656292651471470587267389462826706178501708679988894040, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547830458367721061450157017808834830853014602341868622253795672294331059172859536863933208752474837334210, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547835863401476210545765230993750990148889920960508669945911446189664075442943544834378273711469603796160, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547830752414266487317045433007344385646731648362492228071917510674569518792152296095476933455779708230618, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547834129533080478819072535935108652813110595833861849865643800296119832747279784391057749343996635720940, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547835056336646694300076691426438853974708824037294539111393818963969884213464482405390522048764250780194, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547831362700797094853489150774772826437443409299735933567134426737128681242448286707292262166570548912028, 236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547835268414443436134619838420217416506307772744338173950848314756256619167466069287906334543879625933212]

Each value in RAND was calculated as follow:

d_good*user_input + getPrime(666//2)

Notice that earlier we keyed in x = 2^333 - 1, as the user_input. Since x is not prime we can conclude that x > getPrime(666//2), which means we can retrieve d_good by dividing and flooring a value from RAND with x. We actually only need 1 value from RAND[], so after taking just the first value, we can obtain d_good as follow:

d_good=236295022344045481022088596152868031855245900838697652659839869299879993102103237926140027016777547831550342738774045316773280866091695446555852126352261762151935447363669066696571953760841997886810224//x

3rd Step: Obtaining d

From source code:

seed = "It's (666) the work of the devil..."
d_evil = d >> (int(seed[6:9])//2)
d_good = d %  pow(2,int(seed[6:9])//2)

Mathematically, we have:

d_good = d % 2**333
d = k * 2**333 + d_good

d_evil = d // 2**333
d = d_evil * 2**333 + reminder

#notice that k = d_evil and reminder = d_good
d = d_evil * 2**333 + d_good

We can obtain the value for d as follow:

In [1]: pow(2,333)*d_evil + d_good
Out[1]: 265600977930704366505391758369563164412146232168800460268090387566150924418088529060040292126172260512385738121219390367812214338171890978746977883577350038164691811235185496713171580031944115211005489

After submitting this d value, we can then move the next section on AES. We got this output from the program:

option: {"option": "3","d": "265600977930704366505391758369563164412146232168800460268090387566150924418088529060040292126172260512385738121219390367812214338171890978746977883577350038164691811235185496713171580031944115211005489"}
1.get your token
2.sign in{"option": "1","user": "amin"}
{'id': 792666, 'isadmin': False, 'username': 'amin'}
f05b78ef2ee3cd0a6302eb7f15bc221e2486a985e318129e987a524a15ffffe03d50988597ad5f659b8d7dd2f0b55a2834ce4784f0ce7894ffecf645af139ad9a34cc0f3f1f4beab6b44fb934f8187a1

Step 4: AES Bit-flipping Attack

Notice that in the source code, we can see that the iv is user-controlled, and isadmin is being checked if it evaluates to True, on top of additional check that the data has to be a dictionary. Our goal is to tamper with the decryption result such that it will give the output of b'{"isadmin":1}\x03\x03\x03', making sure that we satisfy the unpad function. If we were to use b'{"isadmin":True}' which has the length of 16 bytes, we will be met with unpad error, and we do not want to use more than 1 block in this attack.

We discarded the remaining blocks on the ciphertext to avoid format error on the dictionary during decryption when XOR-ed with the new_iv. This is made possible due to the fact the code only checks for isadmin=True. We can achieve this by inputting a modified iv value appended with the ciphertext that has been trimmed, as follow:

In [1]: ct='f05b78ef2ee3cd0a6302eb7f15bc221e2486a985e318129e987a524a15ffffe03d50988597ad5f659b8d7dd2f0b55a2834ce4784f0ce7894ffecf645af139ad9a34cc0f3f1f4beab6b44fb934f8187a1'

In [2]: data={'id': 792666, 'isadmin': False, 'username': 'amin'}

In [3]: pt = json.dumps(data)

In [4]: iv=bytes.fromhex(ct[:32])

In [5]: new_iv=xor(xor(iv, pt[:16].encode()),b'{"isadmin":1}\x03\x03\x03')

In [6]: new_iv.hex()+ct[32:64]
Out[6]: 'f05b78f86dbd80543412e7785e93013f2486a985e318129e987a524a15ffffe0'

After inputting the tampered token, we can obtain the flag.

1.get your token
2.sign in{"option": "2","token": "f05b78f86dbd80543412e7785e93013f2486a985e318129e987a524a15ffffe0"}
Decrypted plaintext: {"isadmin":1}
1. Get Flag
2.Exit
1. Get Flag
2.Exit
{"option": "1"}
0xL4ugh{cryptocats_B3b0_4nd_M1ndfl4y3r}

FLAG: 0xL4ugh{cryptocats_B3b0_4nd_M1ndfl4y3r}

Poison

Mathematical tricks on ECC ElGamal decryption with flipped private key

First of all, notice how my_priv is related to new_priv. For each bits, the value of my_priv - new_priv will be equal to either 2**i (when the i-th bit in my_priv is 1 and then flipped to 0 in new_priv) or -(2**i) (when the i-th bit in my_priv is 0 and then flipped to 1 in new_priv).

We actually can just focus on the mathematical correlations between the given output to find my_priv.

C1 = k*G
dec = M + k*G*my_priv - k*G*new_priv
dec = M + k*G*(my_priv - new_priv)
#the value of M is given, and we know the correlations between my_priv and new_priv

The approach is to check, if dec = M + k*G*2**i then the i-th bit of my_priv is 1, otherwise it is 0.

Notice that the given out.txt is overspecifying, since we do not need to use C2s value.

Below is the solver script in sage obtain the flag:

solver.sage

from Crypto.Util.number import * 
#DEFINITION
K = GF(0xfffffffffffffffffffffffffffffffeffffffffffffffff);a = K(0xfffffffffffffffffffffffffffffffefffffffffffffffc);b = K(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1)
E = EllipticCurve(K, (a, b))
G = E(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012, 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811)

#Fill the value for ms, C1s, decs from out.txt
ms = []
C1s = []
decs = []

my_prev=0
for bit in range(len(decs)):
    dec0,dec1=decs[bit]
    m0,m1=ms[bit]
    c10,c11=C1s[bit]
    if(E(m0,m1)+E(c10,c11)*2^bit == E(dec0,dec1)):
        my_prev=my_prev+2^bit
print(long_to_bytes(my_prev))

FLAG: 0xL4ugh{f4u1ty_3CC_EG_CR4CK3r!!!}

RSA-GCD

Equation manipulation to find common factors of N

We can manipulate the two equations involving p and q such that it has a common factor with n that is greater than 1. That common factor can then be found using GCD.

Even though we do not have the exact value of out1, we can brute force it by iterating downwards from eq1, since we know that eq1 is the smallest prime that is bigger than out1.

(p+5*q)**power1 = out1 mod pq
(2*p-3*q)**power2 = out2 mod pq

p**(power1*power2) + (5*q)**(power1*power2) = out1**power2 mod pq
(2*p)**(power1*power2) + (-3*q)**(power1*power2) = out2**power1 mod pq

#Substracting 2**(power1*power2)*equation1 with equation2:

(10*q)**(power1*power2) - (-3*q)**(power1*power2) = 2**(power1*power2) * out1**power2 -  out2**power1 mod pq

#This last equation shows us that we can have a constant that is divisble by q.
#This constant and n has a common factor of q.

Below is the solver script in python to find q and decrypt the flag.

solver.py

from Crypto.Util.number import *
from math import gcd

#input the values from the outputs in chall2.txt
power1=
power2=
eq1=
out2=
c=
n=


for i in range(100000):
    q = gcd((pow(eq1-i,power2,n)*pow(2,power1*power2,n))%n - pow(out2,power1,n), n)
    if q > 1:
        print(q)
        break

p=n//q
d=pow(eq1, -1, (p-1)*(q-1)) #for Python 3.8+
print(long_to_bytes(pow(c,d,n)))

FLAG: 0xL4ugh{you_know_how_factor_N!}

Thanks for reading! Follow me on Twitter