signup

6 minutes to read

We are given the Python source code to encrypt the flag (app.py):

from Crypto.Util.number import getPrime, getRandomRange, isPrime, inverse, long_to_bytes, bytes_to_long  
from hashlib import sha512
from random import SystemRandom
from FLAG import flag

L = 2048
N = 256

def repeating_xor_key(message, key):

    repeation = 1 + (len(message) // len(key))
    key = key * repeation
    key = key[:len(message)]
    
    msg = bytes([c ^ k for c, k in zip(message, key)])
    return msg

def domain_params_generation():

    q = getPrime(N)

    print(f"[+] q condition is satisfied : {N} bit")
    print(q)

    p = 0
    while not (isPrime(p) and len(bin(p)[2:]) == L):
        factor = getRandomRange(2**(L-N-1), 2**(L-N))
        p = factor*q + 1
        
    print(f"[+] p condition is satisfied : {L} bit")
    print(p)

    g = 1
    while g == 1:
        h = getRandomRange(2, p-2)
        g = pow(h, factor, p)

    print(f"[+] g condition is satisfied ")
    print(g)

    
    return(p, q, g)


def key_generation(p, q, g):

    x = getRandomRange(1, q-1)
    y = pow(g, x, p)

    # print(f"[+] private key : {x}")
    print(f"[+] public key  : {y}")

    return(x, y)


def sign(message, private_key, parameters):

    p, q, g = parameters
    k = getRandomRange(1, q-1)

    r = 0
    while r == 0:
        r = pow(g, k, p) % q

    s = 0
    while s == 0:
        Hm = int(sha512(message.encode('utf-8')).hexdigest(), 16)
        s = (inverse(k, q) * (Hm + private_key*r)) % q

    return (r, s)


def verify(message, signature, public_key, parameters):

    p, q, g = parameters
    r, s = signature

    if 0 < r < q and 0 < s < q:
        
        w = inverse(s, q)
        Hm = int(sha512(message.encode('utf-8')).hexdigest(), 16)
        u1 = (Hm * w) % q
        u2 = (r * w) % q
        v = ( (pow(g, u1, p) * pow(public_key, u2, p)) % p ) % q

        if v == r:
            print(f"[+] Valid signature")
            return True
        else:
            print("[!] Invalid signature")
            return False


parameters = domain_params_generation()
p, q, g = parameters

keys = key_generation(p, q, g)
x, y = keys

print()
print("=============================================================================================")
print("===================================== Let's signup ==========================================")
print("=============================================================================================")
print()

with open('./messages', 'r') as o:

    messages = o.readlines()

    for message in messages:
        
        message = message.rstrip()
        print("********************************************************************************")
        print(f"message : {message}")
        signature = sign(message, x, parameters)
        r, s = signature
        print(f"signature: {signature}")

        # verify(message, signature, y, parameters)

    o.close()


key = long_to_bytes(x)
ctf = repeating_xor_key(flag, key)
print()
print("[+] Cipher Text Flag (CTF) : ")
print(hex(bytes_to_long(ctf))[2:])

Moreover, we have the output of the script (output.txt):

[+] q condition is satisfied : 256 bit
82349764091980216703243528787846721157571379253101971061732427939554681522787
[+] p condition is satisfied : 2048 bit
22597614376179368541927291014351181151227386315855982530475290304066480549601872481125000412312232411854471891135859606462198144416258790805203892259557432117585853522644532244043882866950543772453962473369978828348563267281282352402870551728874298860312184560283971631533453430210347478794479982659822354364676170461394200151617927348650724770337556315374296708920869883704844016422867256502854967833552352244354161923370938186895496059235837548125257119775236437293842236838420824347387394024112360489719718482356279060719080630335848636921250967340335457343005624222097640480295331833551512059471129216303573167509
[+] g condition is satisfied
1522212929726315022276463307120954560926577974082882818811797965963142559037271005677110576098054722157527674127902562772533441779935566082403254092732974888203331702770403906546118095393659134079664766399608052006354212408035095060235607110586791971501473747663375215625574865706205289870455822949113508277054039439561937834562865074493156250996591912564352116714825726533396169890605271470775008065174813981767038809048518345994705536020788635479039463106099323099699225053825245500316037480436011003338091199884975066597695902083102085310246580054607257558459623691521498166469718547232285924180800892984387501802
[+] public key  : 10301551349126329107088362265646928131049491442403482867496980836175873288506342576259707854365987702240527285572213439531723683002024146579359208402373918640506155640001430423630072829735081526301031527635977510509965942632354962864260004282149309957641462890526767244115715946314304320419688533957853639652278917522214541525010449214567907170562229712395613781822381944931215562795920884762599015541122869232934183665333423423899053585371134224417264749221110182731383922695086302701203378645475314119934887765168566160180674997559835947912322992312116118206408320274722250233256553213251576546136974127152356743543  

=============================================================================================
===================================== Let's signup ==========================================
=============================================================================================

********************************************************************************
message : AUSSMKJVUNUPKBQ9X10U15409YQT79I6XNF7U0K5YI1568Q42L
signature: (56550035924113170505830328735387144247082155512866957659656089559388264283806, 81360207435150401587545818478565496253332501404776627654827674339875574853292)
********************************************************************************
message : TXNJSIVFXYVZL7SO393MU20XJAK9TN75M0VV29RYI1TMORLJB3
signature: (59454243776673042612495706274074683779593162173045377254234644102590461254174, 69901126149177379418089041430016833757460549835486806478242279543570064790515)
********************************************************************************
...
********************************************************************************
message : 4L0A5NHNMJAS3GJT0AWR1EPAL3R6YTMYAFIWK8SEIBFKUWH98V
signature: (23656285267672134853079913256893925874990475097287627360940184092061316722900, 60259462838850060842954111630590641393950384980094248092524544563470754722439)
********************************************************************************
message : VRE2H23VMQ2ORK8WNRTLBEASQF3GY9VK05CEYQ74KGO44B8QJK
signature: (4221419519268981734259482267401150235000986484722820856700522542664903741971, 39042686015475285979469968400043348530602713981922607759813976003431964156934)

[+] Cipher Text Flag (CTF) :
caaa08c4332e5701a9105ab701cc830b9ddbe18f6612c999f82a344bdc597819fba00f81772e4001bc584cff06d287089d8085a3123bdca5e7706612d7641f66a2b6228a67336c60975719ef04e1b55edad4e6850126ee92bc25692bd15e274db3b214973f224001af5f46bb40d2930cd69bae

We have some parameters for a Digital Signature Algorithm (DSA) implementation, a long list of messages and signatures and finally the encrypted flag. The flag is encrypted using XOR and the DSA private key $x$.

DSA implementation

The code for the DSA is correct (more information here):

It generates prime numbers $p$ and $q$ (such that $p = mq + 1$ for some integer $m$)
Then public values $g$ and $y$
And private values $k$ and $x$

In order to sign messages, it uses SHA512 as hash function and computes:

$$ r = g^k \mod{q} $$

$$ s = \left(\mathrm{SHA512}{(m)} + x \cdot r\right) \cdot k^{-1} \mod{q} $$

And the output is the pair $(r, s)$.

Helper functions

First of all, we can use this Python script to parse the contents of output.txt:

def get_number(pattern: str, res: str) -> int:
    return int(re.findall(pattern, res)[0])


def main():
    with open('output.txt') as o:
        res = o.read()

    q = get_number(r'\[\+\] q condition is satisfied : 256 bit\n(\d+)', res)
    p = get_number(r'\[\+\] p condition is satisfied : 2048 bit\n(\d+)', res)  
    g = get_number(r'\[\+\] g condition is satisfied \n(\d+)', res)
    y = get_number(r'\[\+\] public key  : (\d+)', res)

    m_i = re.findall(r'message : (.+)', res)
    signatures = re.findall(r'signature: \((\d+?), (\d+?)\)', res)
    signatures = list(map(lambda s: list(map(int, s)), signatures))

    r_i = list(map(lambda rs: rs[0], signatures))
    s_i = list(map(lambda rs: rs[1], signatures))

    ctf = re.findall(r'\[\+\] Cipher Text Flag \(CTF\) : \n(.+)', res)[0]
    ctf = bytes.fromhex(ctf)

The security flaw

DSA can be compromised when the nonce values are not chosen randomly or they are used more than once. This time we have a total of 100 messages and signatures. However, if we list the number of distint values of $r_i$, we have 99 (we are very lucky, since $k$ nonces are taken from getRandomRange):

    print(f'{len(r_i) = }, {len(set(r_i)) = }')  
    same_k = (-1, -1)

$ python3 solve.py
len(r_i) = 100, flen(set(r_i)) = 99

Since $r_i = g^{k_i} \mod{q}$, if $r_i = r_j$, then $k_i = k_j$, because $2 \leqslant k_i < q$. So, there is one pair that reuses the same nonce $k$. Let’s find it:

    same_k = (-1, -1)

    for i, r in enumerate(r_i):
        if r in r_i[i + 1:]:
            same_k = (i, r_i.index(r, i + 1))  
            break

    print(f'{same_k = }')

$ python3 solve.py
len(r_i) = 100, len(set(r_i)) = 99  
same_k = (29, 74)

So, we have message $m_{29}$ with signature $(r, s_{29})$ and message $m_{74}$ with signature $(r, s_{74})$, where $r = g^k \mod{q}$.

Therefore, we have

$$ \begin{cases} s_{29} = \left(\mathrm{SHA512}{(m_{29})} + x \cdot r\right) \cdot k^{-1} \mod{q} \\ s_{74} = \left(\mathrm{SHA512}{(m_{74})} + x \cdot r\right) \cdot k^{-1} \mod{q} \end{cases} $$

If we substract both equations, we get

$$ s_{29} - s_{74} = \left(\mathrm{SHA512}{(m_{29})} - \mathrm{SHA512}{(m_{74})}\right) \cdot k^{-1} \mod{q} $$

So we can find $k^{-1}$ as follows

$$ k^{-1} = (s_{29} - s_{74}) \cdot \left(\mathrm{SHA512}{(m_{29})} - \mathrm{SHA512}{(m_{74})}\right)^{-1} \mod{q} $$

Then $k = \left(k^{-1}\right)^{-1} \mod{q}$. And once we have $k$, we are able to find $x$:

$$ x = \left(s_{29} \cdot k - \mathrm{SHA512}{(m_{74})}\right) \cdot r^{-1} \mod{q} $$

Python implementation

Let’s program the above equations in Python:

    m29, r, s29 = m_i[same_k[0]], r_i[same_k[0]], s_i[same_k[0]]  
    m74, r, s74 = m_i[same_k[1]], r_i[same_k[1]], s_i[same_k[1]]

    k_inv = (s29 - s74) * pow(h(m29) - h(m74), -1, q) % q
    k = pow(k_inv, -1, q)
    x = (s29 * k - h(m29)) * pow(r, -1, q) % q

    print(f'{x = }')

    key = long_to_bytes(x)
    flag = repeating_xor_key(ctf, key)

    print()
    print(flag.decode())

Flag

If we run the script, we will find the flag:

$ python3 solve.py
len(r_i) = 100, len(set(r_i)) = 99
same_k = (29, 74)
You did a shared and known job, here is the flag :  
HTB{Sh4r3d_K_1s_n0t_A_g00d_S1gninG_Id3a}
best wishes good luck!!

The full script can be found in here: solve.py.