Uwusignatures CTF Challenge Solution

Challenge Overview

Challenge Name: Uwusignatures Category: Crypto Points: 261 Author: elijah5399

Description:

As an uwu girl, I decided to make this digital signature scheme to share my signatures with everyone!

I'll only show you half of my signature though, because I'm shy...

Surely, no one would steal from a cutie like myself... right?

Connection: nc challs.nusgreyhats.org 33301

Initial Analysis

The challenge provides a Python file uwusignatures.py implementing a custom digital signature scheme. Let's examine the key components:

Code Analysis

class Uwu:
    def __init__(self, keylen):
        self.p = getPrime(keylen)
        self.g = getRandomRange(1, self.p)
        self.x = getRandomRange(2, self.p)  # private key
        self.y = pow(self.g, self.x, self.p)  # public key
        self.k = getRandomRange(1, self.p)
        while GCD(self.k, self.p - 1) != 1:
            self.k = getRandomRange(1, self.p)
        print(f"{self.p :} {self.g :} {self.y :}")
        print(f"k: {self.k}")  # 🚨 CRITICAL VULNERABILITY!

Key Observations:

1. This is a variant of ElGamal digital signatures

2. CRITICAL FLAW: The server prints the nonce k value!

3. The same k is reused for all signatures (not regenerated per signature)

4. To get the flag, we need to forge a signature for "gib flag pls uwu"

Signature Scheme Details

Signing: s = ((h - x * r) * k^(-1)) mod (p-1) Verification: g^h ≡ y^r * r^s (mod p) Where:

• h = SHA256(message)

• r = g^k mod p

• x = private key

• k = nonce (leaked!)

The Vulnerability: K-Reuse Attack

When the same nonce k is reused across multiple signatures, it creates a catastrophic vulnerability:

1. Same r value: Since r = g^k mod p, reusing k means r is identical for all signatures

2. Private key recovery: With two signatures using the same k, we can algebraically recover the private key x

Exploitation Strategy

Step 1: Gather Information

Connect to the server and collect:

• Public parameters: p, g, y

• The leaked nonce: k

• Two signatures for different messages

nc challs.nusgreyhats.org 33301

Server Response:

Welcome to my super uwu secure digital signature scheme!
p = 28581604583782202143265111259124764526558825270793277405217394025745721954242254650965121482666635832686847474953440562605929002515608632964837704031786219117086986365555362911719993384506358582903300968928565193358567967799661175969775606231196220739601603275247187365872493703245095030170642525169857628874828723382454145699792436618477569467807268534404279857152331863245576074611134202405776998737108819578147772994298861844565336899724017862013870691248091221349545431949433843727531476934363372637337251401879263333278436051314996981429686780914130059682966220700794805365732309015888301565442824558714505349489
g = 13848683002866283304209230121718892686269072577134567400452720860245681493741003987303504800213923101669655981090103435680450277015337930888533692866570802369537467886393333681165721258219015658594810630182725352119309472177339329735747203066180815430324751872948679966917249314441187467096565697027183234785608229694988037776123692371541682254030402082934059532466644987165296295825826226378671369828451384797539559636704831402164768674918167354495036431879392891664896354939497263573261920042749726303930408770608926284688360604485321985811528949325116958202049524152355055092646825544117981593937928138981075791223
y = 20620169414902502338561831043406834260669101419380957375831823709489932725977581086850101378562777184663305809842090976763335619439956329768332032585950846586128220779762547145229109343686448381511459326285055126052695966813631202649358091081019604722000850119692422587396721259380786519957209785366924157968306737114724340278377608428009589963314349733766724993357830529725442599594445808471075513963148631428872496358353831004734925663817818703201066713221688729827656326815768023582497197173724446141598150808611330560778011886157386166278670237679175086231949521056132411275362078398718795815943470282645224905094
k: 4378031792006870256693045691209051164960988969025829825114846073833994185874539390707268303609688979239078737994155476188447496452455468267915199597825087188244546679257572153774462208881950968258828157789999407319488829138213142408315712593063525712267189620037760486656749699518895440553202291352655671196912061703817108922077335853601805172639293529253815481660739980616407018577925423407050396812598034367384127990699382151869423433592672208876788106391055466824446030188868505296175820029016572299301915661367806433440549210008514916434938928457069975985280022388868960383859028408943033402336677527171992082595

Step 2: Obtain Known Signatures

Request signatures for two different messages:

# Message 1
{"m": 123}
# Response: s1 = 23838810343301920651199855403738533075669127243241581832260507739861908376432660810729411684162925085875999308387624191042729204056846442735425178382059835387510274927702225838598803861139822388686585693807811689773927870039425486836041691046772329959964553085685452383946495857597640443798158514729231448385624894266551590000834025287115178659464093773267188885476938114971610159256437861800918775540646007440489259455011992824064027289155379958227279102393436021561510509359628056861623928013854067045704383991867682459244759009895348825096582933270608574940647895786833274899468859842999207095286566827263306607389

# Message 2  
{"m": 456}
# Response: s2 = 28360411703274409235364904101035918833158994677565402586787423202924288819877593049790719717633928779973618481431553628399167407272985931193312758063166875933167739272573429490552005807764105944661193640929020751464393592423653878125662081288481061162771378775400590880896808285267122572121780363268371459516358018196542205223830367020924644288141387041252216534005370718969934165312795253299827988547950751354276199823892769338600092450259308001059597630657632560145526065991943396768248849401440724037420338562058837975202553263435383927133297147258151388521932151203329935203733506100854105909132007693117738599043

Step 3: Recover Private Key

With the leaked k and known signatures, we can recover the private key x:

from Crypto.Util.number import *
import hashlib

# Server parameters
p = 28581604583782202143265111259124764526558825270793277405217394025745721954242254650965121482666635832686847474953440562605929002515608632964837704031786219117086986365555362911719993384506358582903300968928565193358567967799661175969775606231196220739601603275247187365872493703245095030170642525169857628874828723382454145699792436618477569467807268534404279857152331863245576074611134202405776998737108819578147772994298861844565336899724017862013870691248091221349545431949433843727531476934363372637337251401879263333278436051314996981429686780914130059682966220700794805365732309015888301565442824558714505349489
g = 13848683002866283304209230121718892686269072577134567400452720860245681493741003987303504800213923101669655981090103435680450277015337930888533692866570802369537467886393333681165721258219015658594810630182725352119309472177339329735747203066180815430324751872948679966917249314441187467096565697027183234785608229694988037776123692371541682254030402082934059532466644987165296295825826226378671369828451384797539559636704831402164768674918167354495036431879392891664896354939497263573261920042749726303930408770608926284688360604485321985811528949325116958202049524152355055092646825544117981593937928138981075791223
y = 20620169414902502338561831043406834260669101419380957375831823709489932725977581086850101378562777184663305809842090976763335619439956329768332032585950846586128220779762547145229109343686448381511459326285055126052695966813631202649358091081019604722000850119692422587396721259380786519957209785366924157968306737114724340278377608428009589963314349733766724993357830529725442599594445808471075513963148631428872496358353831004734925663817818703201066713221688729827656326815768023582497197173724446141598150808611330560778011886157386166278670237679175086231949521056132411275362078398718795815943470282645224905094
k = 4378031792006870256693045691209051164960988969025829825114846073833994185874539390707268303609688979239078737994155476188447496452455468267915199597825087188244546679257572153774462208881950968258828157789999407319488829138213142408315712593063525712267189620037760486656749699518895440553202291352655671196912061703817108922077335853601805172639293529253815481660739980616407018577925423407050396812598034367384127990699382151869423433592672208876788106391055466824446030188868505296175820029016572299301915661367806433440549210008514916434938928457069975985280022388868960383859028408943033402336677527171992082595

# Known signatures
m1, s1 = 123, 23838810343301920651199855403738533075669127243241581832260507739861908376432660810729411684162925085875999308387624191042729204056846442735425178382059835387510274927702225838598803861139822388686585693807811689773927870039425486836041691046772329959964553085685452383946495857597640443798158514729231448385624894266551590000834025287115178659464093773267188885476938114971610159256437861800918775540646007440489259455011992824064027289155379958227279102393436021561510509359628056861623928013854067045704383991867682459244759009895348825096582933270608574940647895786833274899468859842999207095286566827263306607389

# Calculate r and hash
r = pow(g, k, p)
def hash_m(m):
    sha = hashlib.sha256()
    sha.update(long_to_bytes(m))
    return bytes_to_long(sha.digest())

h1 = hash_m(m1)

# Recover private key x
# Since GCD(r, p-1) = 1 in this case, we can directly invert r
x = ((h1 - s1 * k) * pow(r, -1, p-1)) % (p-1)

Step 4: Forge Target Signature

Now we can forge a signature for the target message:

# Target message
target_msg = bytes_to_long(b"gib flag pls uwu")
h_target = hash_m(target_msg)

# Forge signature
s_target = ((h_target - x * r) * pow(k, -1, p-1)) % (p-1)

# Verify our forged signature
def verify_signature(m, r, s):
    h = hash_m(m)
    lhs = pow(g, h, p)
    rhs = (pow(y, r, p) * pow(r, s, p)) % p
    return lhs == rhs

print(f"Signature verification: {verify_signature(target_msg, r, s_target)}")
# Output: True ✅

Step 5: Submit and Get Flag

Submit the forged signature:

{
  "m": 137457664979133345092444721504268416885,
  "r": 27705931485116418224621449487391072526860100540050399693307990203460680459828553263274088376514832048851321498318256595918064281644626554908004073462528866428742545798551092821132502292156020335628144976944494540262181952896725203942043453217739426882695841928469150760751996001249499160218181301695056131924497666938146481232527939976609433224719911634330650675041017384389020720071211278305737374659529203063748439620320606937581641575361683761134450635663507478270602360366008948007134200059007079880263541821727495791501426712965964048114432966289537884690939472913933704414600851982464515831750560784038339323329,
  "s": 3543207270597413962505716531415114132702704596191944661388003774954873338098139925111296392184454136317632828016556975939555280062159887394254315487526931503835042187137742368311623145625866829766860101886078078984840736219946310485393489414826792986906492433895987309583910457710582884476607479763417049436296095883327367506177002685301362176116236256353590655991857985486594723491019327224146044798457822902498064857117764678755493714581719044483324058041922758141837238283034734729432543522092801081882116239603156573687007663234700890490163542581548168411381128535228379535239916453897728055539474657252133721240
}

Server Response:

Very cutesy, very mindful, very demure!
grey{h_h_H_h0wd_y0u_Do_tH4T_OMO}

Flag

grey{h_h_H_h0wd_y0u_Do_tH4T_OMO}

Key Takeaways

1. Never reuse nonces in cryptographic schemes - it's catastrophic for security

2. Never leak private values like nonces, even "accidentally"

3. K-reuse attacks are a classic vulnerability in signature schemes (DSA, ECDSA, etc.)

4. Proper implementation should generate a fresh, random nonce for each signature

5. Defense in depth - even if nonces were properly generated, leaking them would still be fatal

This challenge demonstrates why cryptographic implementations must be extremely careful about nonce generation and keeping secrets truly secret!