dsa

Dsa (Crypto, 333p)

###ENG PL

We are given following python code - it is supposed to sign messages:

#!/usr/bin/python

from hashlib import *
from Crypto.Util.number import *
from gmpy import *
import os

def param_gen():
    q = getPrime(1024)
    while True:
        t = 2*getRandomRange(1, 2**256)
        p = t*q + 1
        if is_prime(p):
            break
    while True:
        h = getRandomRange(1, p-1)
        g = pow(h, (p-1)/q, p)
        if g != 1:
            break
    return (p, q, g)

def key_gen(params):
    p, q, g = params
    x = getRandomRange(1, q)
    y = pow(g, x, p)
    pubkey, privkey = y, x
    return pubkey, privkey

def sign(msg, privkey, params):
    p, q, g = params
    while True:
        k = getRandomRange(1, 1024) * pow(pubkey, privkey, p) % q
        r = pow(g, k, p) % q
        s = invert(k, q) * ( int(sha512(msg).hexdigest(), 16) + privkey * r) % q
        if r*s != 0 :
            break
    return (int(r), int(s))

def verify(msg, signature, pubkey, params):
    p, q, g = params
    r, s = signature
    if (0 < r < q) and  (0 < s < q) :
        w = invert(s, q)
        u1 = (int(sha512(msg).hexdigest(), 16) * w) % q
        u2 = (r * w) % q
        v = ((pow(g, u1, p) * pow(pubkey, u2, p)) % p) % q
        if v == r:
            return True
    return False

params = param_gen()
p, q, g = params
print params
pubkey, privkey = key_gen(params)

for i in range(0, 40):
    msg = 'ASIS{' + os.urandom(16).encode('hex') + '}'
    signature = sign(msg, privkey, params)
    r, s = signature
    print str((msg, r, s))

This challenge asks us to recover private key (x) given only a handful (around 40) signatures, public key, and public parameters given (attached to this solution in github).

After a while, we find a vulnerability in this challenge -

k = getRandomRange(1, 1024) * pow(pubkey, privkey, p) % q

This is obviously insecure, as only 1024 ks can possibly be generated. If only we could recover k, this challenge would be trivial - given k we can calculate privkey from linear equation:

s = invert(k, q) * ( int(sha512(msg).hexdigest(), 16) + privkey * r) % q
<=>
s * k - int(sha512(msg).hexdigest(), 16) * invert(r, q) % q = privkey

But we don't know k... yet.

After another while, we noticed that if we could find two messages encrypted with the same k, challenge would be easy again. We could solve system of linear equations:

s = invert(k, q) * ( int(sha512(msg0).hexdigest(), 16) + privkey * r) % q
s = invert(k, q) * ( int(sha512(msg1).hexdigest(), 16) + privkey * r) % q

...where k and privkey are unknowns. But again, this wasn't the case in this challenge.

And finally, when we began to fall into the pit od despair, we noticed that we could create another system of linear equations. Because k = (1..1024) * MAGIC (where MAGIC = pow(publickey, privkey), but it's not important), we can write above equations as:

s = invert(k1 * MAGIC, q) * (int(sha512(msg0).hexdigest(), 16) + privkey * r) % q
s = invert(k2 * MAGIC, q) * (int(sha512(msg1).hexdigest(), 16) + privkey * r) % q

In more mathematical terms, we can solve this system of equations as follows:

s1 = (c1 + priv*r1) / (k1*magic)
s2 = (c2 + priv*r2) / (k2*magic)

1 = (c1 + priv*r1) / (k1*magic*s1)
1 = (c2 + priv*r2) / (k2*magic*s2)

(c1 + priv*r1) / (k1*magic*s1) = (c2 + priv*r2) / (k2*magic*s2)
(c1 + priv*r1) * (k2*magic*s2) = (c2 + priv*r2) * (k1*magic*s1)
c1*k2*magic*s2 + priv*r1*k2*magic*s2 = c2*k1*magic*s1 + priv*r2*k1*magic*s1
c1*k2*s2 + priv*r1*k2*s2 = c2*k1*s1 + priv*r2*k1*s1
priv*r1*k2*s2 - priv*r2*k1*s1 = c2*k1*s1 - c1*k2*s2 
priv*(r1*k2*s2 - r2*k1*s1) = c2*k1*s1 - c1*k2*s2 
priv = (c2*k1*s1 - c1*k2*s2) / (r1*k2*s2 - r2*k1*s1)

Great, we have private key! But we have to bruteforce 1024 possible values of k1 and k2. It's easy enough in python:

from hashlib import *
from Crypto.Util.number import *
from gmpy import *
import os

def hash(msg):
    return int(sha512(msg).hexdigest(), 16)

def solve_for(params, set1, set2):
    p, q, g = params
    msg1, r1, s1 = set1
    msg2, r2, s2 = set2
    c1, c2 = hash(msg1), hash(msg2)
    for k1 in range(1, 1024):
        print k1
        for k2 in range(1, 1024):
            priv = (c2*k1*s1 - c1*k2*s2) * invert(r1*k2*s2 - r2*k1*s1, q) % q
            if pubkey == pow(g, priv, p):
                print priv
            
params = (
19990043472646209601994864878783430356973105946195950979159251182377121897576105462833887676561348770957108482823143337701724893247634876231133001112659622843245186144815694000013210989382541478073551247763586093331215996260234193847013210807939190828438263706901950228866893621933887960930392778176297205331569773161563794018138992335091883899396920586572927792555042350138728812073331L, 91629484598379105033512409529628860433949558415030791938154302542936417405614272511539966765257644706180090102931421315331051281240103609205686784098900471134711603588304765157414857991689054932897002635007537146809343047302801243835776634361209432398032301656027511721047704054332653738042312201931970395721L, 13622145302845273763875935516952425125176393702394844695432724066597834898277677169908234619701079219174550050531086255052810547971127992364106395259623997686454799745423099095097056224348731737512112568608406081844751809559052204755863089238863185755017905098158596830866362329243334855589147537151782745634416243769180780246626300677625340613515232605024658651528787608437872606367959L)
set1 = ('ASIS{f178fcdecf80695744078436c8443d21}', 90237121958952251064976624492762150213417521896687572941345633764310618911601030617031373795520024583293535375710106225552196376797438589929204291257545448726331743603280815369427093966770848920593554708454565838054224752549404158493278464435213107237527453340811242850765181020853492694252650516970176641788L, 45699965566033911695982803604354032305058506238185457115666900773211243249439993822400900118887663777494151014067272471514622506941212402877792085312967213090334714190020080393819021065260516916603206309212756987461405393121419856054170230373811099272880018713486783939408418428725471847346917597357388173871L)
set2 = ('ASIS{13d82a52a86b3f60d1d5d0a9a8fbd38c}', 82549501691566010240713957921730895287132128726058380260123211081436703044836270709304732846086147549660502736557189123678902405383474467404416541210982435469292602012427497998459504126706153698217704534579606635614323510632001857553260216879546038347723055837869594047336385462982125121614977106061534077159L, 14100015776662279808055950447194278668824709578034279558537621662053558677298084425976090376958899238099311275299915689425374231782256233762239739696534102757257328540054634833325260578944419955606514868448883176935887227050496260234118031035188783965371809668020726016057511098782430965590465392354859239207L)
pubkey = 5120206348411789470161536127663499609309512038887109068976130122757582186109731229884381538683899917243667766639035225751229538595906667027298668257572271684995053081914448593696545954848592131805237134557157103971058735552127997038702518466039596176245969237004179261427946425137677159565508198606851760199742107673019486271187331752618149416170682584515782866631954825392784384052948

solve_for(params, set1, set2)

And we finally get our flag: ASIS{1e58445616cd5178632ae15bef51c4a3}

###PL version

to be done?