# YauzaCTF 21 - Crypto Challenges

## Shadows

The challenge is composed of two files:

import json

from Crypto.Util.number import bytes_to_long, getPrime
from storage import flag


def mul(x):
    m = 1
    for i in x:
        m *= i
    return m


if __name__ == '__main__':
    flag = bytes_to_long(flag.encode())

    count = 25
    threshold = 11
    psize = 24

    primes = list(sorted(getPrime(psize) for _ in range(count)))

    pmin = mul(primes[-threshold + 1:])
    pmax = mul(primes[:threshold])

    assert pmin < flag < pmax

    shadows = [flag % x for x in primes]

    with open('secrets.json', 'wt') as out_file:
        out_file.write(json.dumps({
            'shadows': shadows[1:threshold],
            'primes': primes[:threshold],
            'threshold': threshold
        }))

and

{"shadows": [7832917, 8395798, 4599919, 154544, 3430534, 4694683, 123690, 5911445, 7380167, 10597668], "primes": [8412883, 8889941, 9251479, 9471269, 9503671, 9723401, 10092149, 10389901, 10551241, 10665527, 11099951], "threshold": 11}

It is a Chinese Remainder problem, but one remainder is missing. However, the prime numbers are very small (24 bits). We solve this challenge by bruteforcing the missing remainder.

from sympy.ntheory.modular import crt
import binascii


shadow = [    0,     7832917, 8395798, 4599919, 154544, 3430534, 4694683, 123690, 5911445, 7380167, 10597668]
primes = [8412883, 8889941, 9251479, 9471269, 9503671, 9723401, 10092149, 10389901, 10551241, 10665527, 11099951]
threshold = 11

n=0
while n < 0xffffffff:
	shadow[0]=n
	ct=hex(crt(primes,shadow)[0])[2:]
	if len(ct) % 2 ==1:
		ct="0"+ct
	pt=binascii.unhexlify(ct)
	if pt.lower().startswith(b"yau"):
		print(n,pt)
	n+=1

# 7717390 b'YauzaCTF{k33p_1t_1n_7h3_sh4d0w5}'

and the flag is **YauzaCTF{k33p_1t_1n_7h3_sh4d0w5}**.

## Knapsack

The Knapsack challenge is only composed of :

flag= [12777998288638, 10593582832873, 7834439533378, 10486500991495, 14714582460036, 7568907598905, 12800035735033, 14724457772647, 11910445040159, 11202963622894, 10291238568620, 15103559399914, 13156142631772, 16988824411176]
ba = [2948549611747, 2043155587142, 361533419625, 1001380428657, 2438250374319, 1059738568330, 115120002311, 198226659880, 2343897184958, 2592576935132, 2327834076450, 237536244289, 309228208827, 3327276767693, 462372704541, 2176574227058]

Please find here a description of the cryptosystem (https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem). In short, a superincreasing sequence (item i is bigger than the sum of all previous item) is used to create a linear combinaison with the bits of the plaintext (big endian). In our case, we solve this problem by using the LLL algorithm which recovers the individual bits of the plaintext.

# python3 -m pip install olll
# https://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/

import olll

flag= [12777998288638, 10593582832873, 7834439533378, 10486500991495, 14714582460036, 7568907598905, 12800035735033, 14724457772647, 11910445040159, 11202963622894, 10291238568620, 15103559399914, 13156142631772, 16988824411176]
ba = [2948549611747, 2043155587142, 361533419625, 1001380428657, 2438250374319, 1059738568330, 115120002311, 198226659880, 2343897184958, 2592576935132, 2327834076450, 237536244289, 309228208827, 3327276767693, 462372704541, 2176574227058]

_flag=""
for i in range(len(flag)):
	reduced = olll.reduction([
		[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[0]],
		[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[1]],
		[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[2]],
		[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[3]],
		[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[4]],
		[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[5]],
		[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[6]],
		[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -ba[7]],
		[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -ba[8]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -ba[9]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -ba[10]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -ba[11]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -ba[12]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -ba[13]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -ba[14]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -ba[15]],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, flag[i]]],0.75)

	for j in range(len(reduced)):
		if all([x in [0,1] for x in reduced[j]]):
			pt="".join([str(x) for x in reduced[j]])
			_flag+=chr(int("0b"+pt[:8],2))+chr(int("0b"+pt[8:-1],2))
			break
	print(_flag)

and the flag is **YauzaCTF{l34ky_kn4ps4k_d4mn}**. However, as only 16 words are provided, the encryption works on 16 bits and the flag could have been bruteforce two caracteres by two caracteres.

# Signatures

The objective of this challenge was to forge a signature.

from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long, long_to_bytes, size, getRandomNBitInteger
from storage import flag

def byten(x, n):
    return (x >> (n * 8)) & 0xFF

def mask(n):
    return (1 << n) - 1

def rotate(x, n, s):
    return ((x >> (s - n)) | (x << n)) & mask(s)

def scramble(x):
    magic = 0xC3A569C3A569C3A569C3A569C3A569C33C965A3C965A3C965A3C965A3C965A3C
    for i in range(32):
        x = rotate(x, 27, 256) ^ rotate(magic, i, 256)
    return x

def sha2(x):
    hash = SHA256.new()
    hash.update(x)
    return hash.digest()

def gen_pair():
    private = [getRandomNBitInteger(256) for _ in range(16)]
    public = [long_to_bytes(y) for y in private]
    for i in range(16):
        for j in range(255):
            public[i] = sha2(public[i])
    return private, [bytes_to_long(y) for y in public]


def sign(x, key):
    parts = [byten(x, i) for i in range(16)]

    digest = [long_to_bytes(y) for y in key]
    for i in range(16):
        for j in range(parts[i]):
            digest[i] = sha2(digest[i])

    return digest

def verify(x, sign, public):
    parts = [255 - byten(x, i) for i in range(16)]

    digest = list(sign)
    for i in range(16):
        for j in range(parts[i]):
            digest[i] = sha2(digest[i])
        if digest[i] != long_to_bytes(public[i]):
            return False
    return True


def do_signature(x, private):
    signature = sign(scramble(x), private)
    return bytes_to_long(b''.join(signature))

def do_verify(x, signature, public):
    signature = long_to_bytes(signature, 256*16//8)
    signature = [signature[i*32:(i + 1)*32] for i in range(16)]
    return verify(scramble(x), signature, public)


menu = '''\
[1] Sign message
[2] Get flag
[3] Quit'''

if __name__ == '__main__':
    private, public = gen_pair()
    challenge = getRandomNBitInteger(256)
    while True:
        try:
            print(menu)
            opt = input('> ')
            if opt == '1':
                data = int(input('msg: '))
                if size(data) > 256:
                    raise Exception('Message is too long (256 bits max)')
                if data == challenge:
                    raise Exception('Nice try')

                print(do_signature(data, private))
            elif opt == '2':
                print('Enter signature for the message:')
                print(challenge)
                data = int(input('sign: '))
                if size(data) > 256*16:
                    raise Exception('Signature is too long (16 blocks, 256 bits each)')
                if not do_verify(challenge, data, public):
                    raise Exception('Wrong signature')
                print(flag)
            elif opt == '3':
                exit(0)
            else:
                raise Exception('Unknown option')
        except Exception as ex:
            print('Error:', ex)

In short, 16 numbers of 256 bits are generated, and the private part is composed of the application of the sha2 function 255 times to those value.

To sign x, the value is scrambled (but this is not random) and then signed. The signature is composed of the iterative hash (defined by scrambled) to the public value (but not accessible). The hash verification is done by completing the iterative hash up to the 255 iterations and compared to the private the values.

However, the scramble is not random and we wan sign a unlimited number of value. Obviously, we cannot sign directly the challenge value, but we can sign the challenge+1 and challenge-255.

By doing so, and debugging the scramble function, only the 12th hash need to be replace.

from Crypto.Util.number import bytes_to_long, long_to_bytes

def byten(x, n):
    return (x >> (n * 8)) & 0xFF

def mask(n):
    return (1 << n) - 1

def rotate(x, n, s):
    return ((x >> (s - n)) | (x << n)) & mask(s)

def scramble(x):
    magic = 0xC3A569C3A569C3A569C3A569C3A569C33C965A3C965A3C965A3C965A3C965A3C
    for i in range(32):
        x = rotate(x, 27, 256) ^ rotate(magic, i, 256)
    return x

x = 59182351624691910219326985342729375057882681376420056568634437032596443492739

print(x)
print([byten(scramble(x), i) for i in range(16)])
print(x+1)
print([byten(scramble(x+1), i) for i in range(16)])
print(x-256)
print([byten(scramble(x-1*256), i) for i in range(16)])

a = long_to_bytes(465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606408045821517139432326422296790898124715803347883679032272895159791606401948168895861665579691598078624201466057484352669448377992595009347956456578381061031966996879770504071577086367576854726859566213928445636280725461334608970479085247607004316287928015349012652756358025784101700205221024513687939983444389)
b = long_to_bytes(465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032961769471727195650400111929555586754060473465177109923522104142468599388859755052387968837453908619830019404790000556863073934960080603593462952028975781509803947359050823559088118106624830406830160160710195391926501622538682861989)

_a=[]
_b=[]
for i in range(0,len(a),32):
	_a.append(a[i:i+32])
	_b.append(b[i:i+32])

d=[]
for i in range(len(_a)):
	d.append(_a[i])
d[12]=_b[12]
print(bytes_to_long(b"".join(d)))

python3 sig-solv.py 
59182351624691910219326985342729375057882681376420056568634437032596443492739
[161, 210, 230, 135, 69, 64, 83, 211, 48, 58, 15, 135, 38, 158, 158, 211]
59182351624691910219326985342729375057882681376420056568634437032596443492740
[161, 210, 230, 135, 69, 64, 83, 211, 48, 58, 15, 135, 33, 158, 158, 211]
59182351624691910219326985342729375057882681376420056568634437032596443492483
[161, 210, 230, 135, 69, 64, 83, 211, 48, 58, 15, 135, 38, 159, 158, 211]
465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032437002192304770610953619957988753638573108978591540140452603895680396134899330432311679768843766457252834305627950581267665427794796212496983071957108055647096825006898338300514264627818400155841477587794514801721943731302305728933

[1] Sign message
[2] Get flag
[3] Quit
> 2
Enter signature for the message:
59182351624691910219326985342729375057882681376420056568634437032596443492739
[1] Sign message
[2] Get flag
[3] Quit
> 1
msg: 59182351624691910219326985342729375057882681376420056568634437032596443492740
465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606408045821517139432326422296790898124715803347883679032272895159791606401948168895861665579691598078624201466057484352669448377992595009347956456578381061031966996879770504071577086367576854726859566213928445636280725461334608970479085247607004316287928015349012652756358025784101700205221024513687939983444389
[1] Sign message
[2] Get flag
[3] Quit
> 1
msg: 59182351624691910219326985342729375057882681376420056568634437032596443492483
465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032961769471727195650400111929555586754060473465177109923522104142468599388859755052387968837453908619830019404790000556863073934960080603593462952028975781509803947359050823559088118106624830406830160160710195391926501622538682861989
[1] Sign message
[2] Get flag
[3] Quit
> 2
Enter signature for the message:
59182351624691910219326985342729375057882681376420056568634437032596443492739
sign: 465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032437002192304770610953619957988753638573108978591540140452603895680396134899330432311679768843766457252834305627950581267665427794796212496983071957108055647096825006898338300514264627818400155841477587794514801721943731302305728933
YauzaCTF{Crypt0_$1gn3rrrr}
[1] Sign message
[2] Get flag
[3] Quit

**YauzaCTF{Crypt0_$1gn3rrrr}**

That's all Folks, Electro