OSP Challenge

Have you heard of OTP? This is OSP (One Secret Password).

given an osp.py that contains the following block of code.

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, isPrime
from string import printable, ascii_letters
from secret import FLAG
import os

secret = os.urandom(len(FLAG))

def OSP(plain, secret):
    assert len(plain) == len(secret), 'The length has to be idenntical!'
    ct = []
    p = getPrime(256)
    for f, k in zip(FLAG, secret):
        ct.append((f * p + k))
    return ct, p

ct, p = OSP(FLAG, secret)
print(ct)

And given a text file output.txt that contains the flag encrypted:

5447072546591309544167389173397699795993168970119080464536675615517059887871841
6955492636416595264090666175261678201037431146459748900869908862891014933743799
5614674778794119068603308840271475174331420323045821401907034865225277115190905
7290697100822214312962505509009228957713933852313230775610627362307449388382150
5949879243199738117475148174019025931007923028899303276647753364641711569829134
10307537280472785752809059512737185767802458204994567648277093857055359480126320
7290697100822214312962505509009228957713933852313230775610627362307449388382014
8715316074546095270667822677436319673589070352190528743258680984827295820594564
4357658037273047635333911338718159836794535176095264371629340492413647910297392
4609061385577261921987790839028822904301912205485375777684879366975973751276187
7961106029633452410706184176504330471066939264020194525092064361140318297658489
4106254688968833348680031838407496769287158146705152965573801617851322069318627
8547713842343285746231903010562544295250818999263787805888321735119078593275661
7961106029633452410706184176504330471066939264020194525092064361140318297658510
4106254688968833348680031838407496769287158146705152965573801617851322069318692
4609061385577261921987790839028822904301912205485375777684879366975973751276175
3268243527954785726500433504038619877595901382071448278722005369310235932723134
9637128351661547655065380845242084254449452793287603898795656858222490570849839
7961106029633452410706184176504330471066939264020194525092064361140318297658493
6536487055909571453000867008077239755191802764142896557444010738620471865445985
4022453572867428586462072004970609080118032470241782496888621992997213455659123
4609061385577261921987790839028822904301912205485375777684879366975973751276211
7961106029633452410706184176504330471066939264020194525092064361140318297658707
5363271430489904781949429339960812106824043293655709995851495990662951274212211
7961106029633452410706184176504330471066939264020194525092064361140318297658649
6704089288112380977436786674951015133530054117069637494814369988328689092765262
9553327235560142892847421011805196565280327116824233430110477233368381957190188
4106254688968833348680031838407496769287158146705152965573801617851322069318653
6452685939808166690782907174640352066022677087679526088758831113766363251786487
4273856921171642873115951505281272147625409499631893902944160867559539296637772
2765436831346357153192674503417293742581147323291225466610927620185584250765693
3771050224563214299808192504659946012610655440851671090833083118434887614680427
8547713842343285746231903010562544295250818999263787805888321735119078593275529
4022453572867428586462072004970609080118032470241782496888621992997213455659182
8547713842343285746231903010562544295250818999263787805888321735119078593275562
8547713842343285746231903010562544295250818999263787805888321735119078593275594
8128708261836261935142103843378105849405190616946935462462423610848535524977837
4273856921171642873115951505281272147625409499631893902944160867559539296637945
4525260269475857159769831005591935215132786529022005308999699742121865137616416
4441459153374452397551871172155047525963660852558634840314520117267756523956886
4609061385577261921987790839028822904301912205485375777684879366975973751276006
8463912726241880984013943177125656606081693322800417337203142110264969979616102
10475139512675595277244979179610961146140709557921308585647453106763576707445416

My approach solving the challange

first thing i do is i try to collect as much information as possible from the given code. by looking at output.txt you can see that most of the lines are of length 79. while there are two lines that differs from the rest, they have the length of 80.

the function OSP(plain, secret) takes byte array (b"array") and secret (random bytes with the length equals to the flag’s length) and returns the used prime number and ct

def OSP(plain, secret):
    assert len(plain) == len(secret), 'The length has to be idenntical!'
    ct = []
    p = getPrime(256)
    for f, k in zip(FLAG, secret):
        ct.append((f * p + k))
    return ct, p

by just looking you can identify the most important part in it.

#...
p = getPrime(256)
for f, k in zip(FLAG, secret):
    ct.append((f * p + k))
#...

Trying the OSP() function to see how it works.

FLAG = b'A'
secret = os.urandom(len(FLAG))

ct, p = OSP(FLAG, secret)

f is the ord(‘A’), p is a prime number and k is a random byte and it will result in 56935293674359....900212209796131672 of length 79 now i know where is the 79 chars came from.

i wrote this function to decrypt needing only the prime number. By just doing the opposite of what the encrypt function is doing.

# decrypts and returns ASCII char
def decrypt(ctx, prime) -> int:
    return int((ctx-len(str(ctx)))/prime)

where ctx is f. len(str(ctx)) is k and prime is p from the OSP() function

int(
    (ctx - len(str(ctx) )) / prime
 )

calling this: decrypt(ct[0], p) returns 65 == ord(‘A’) which is our flag!

the method this encryption function get’s its prime number is by p = getPrime(N)

i know the N. so i went on to bruteforce the prime number. and this is my code to do it.

Solution

from Crypto.Util.number import getPrime

# as from the OSP() function
# >> p = getPrime(256)
BIT_LEN = 256

# decrypts and returns ASCII char
def decrypt(ctx, prime) -> int:
    return int((ctx-len(str(ctx)))/prime)

# read output.txt (encrypted data) file
with open("output.txt", 'r') as f:
    out = f.readlines()
    for i in range(len(out)):
        out[i] = out[i].strip()

# I know that the flag starts with ASCWG{
flag_pfx = "ASCWG{"

def solve(prime) -> str:
    flag = ""
    for i in range(len(out)):
        flag += chr(decrypt(int(out[i]), prime))
    return flag

p = getPrime(BIT_LEN)
ret = solve(p)

# Bruteforce prime number
while flag_pfx not in ret:
    p = getPrime(BIT_LEN)
    ret = solve(p)

print(f"prime: {p}")
print(f"flag length: {len(ret)}")
print(f"flag: {ret}")

$ python solve.py
prime: 83614740067651512734468706.....00802220121111201
flag length: 43
flag: ASCWG{Wh47_1f_17's_N07_@_Pr1M3!-f0ffa3657e}