Wiener (Crypto 300)

Task

It's gold rush time! The New York Herald just reported about the Californian gold rush. We know a sheriff there is hiring guys to help him fill his own pockets. We know he already has a deadful amount of gold in his secret vault. However, it is protected by a secret only he knows.
When new deputies apply for the job, they get their own secret, but that only provies entry to a vault of all deputy sheriffs. No idiot would store their stuff in this vault.
But maybe we can find a way to gain access to the sheriff's vault? Have a go at it:

nc wildwildweb.fluxfingers.net 1426
You might also need this [see attachment].

Solution

When connects to wildwildweb.fluxfingers.net:1426 one gets acquainted with command interface to acquire credentials (login name, ssh private key, ssh public key) for the address wildwildweb.fluxfingers.net:1427 and to view public keys of other persons having access to that address. The main purpose of the task is to login with credentials corresponding to sheriff.

Taking a look at service source code provided one can notice, that RSA keys are generated in a bit unusual way:

def create_parameters(size=2048):
    p = get_prime(size // 2)
    q = get_prime(size // 2)
    N = p * q
    phi_N = (p - 1) * (q - 1)
    while True:
        d = prng.getrandbits(size // 5)
        e = int(gmpy.invert(d, phi_N))
        if (e * d) % phi_N == 1:
            break

    assert test_key(N, e, d)
    return N, e, d, p, q 

Instead of generating modulus N, picking standard public exponent e and calculating private exponent as (e^(-1)) mod phi(N), they pick rather small random private exponent d and find corresponding e. The d picked is proportional to N^0.2.

With the key generation set up this way RSA cryptosytem becomes weak to Wiener's attack (see http://en.wikipedia.org/wiki/Wiener%27s_attack). As anyone can see, Wiener's attack is applicable with d < (N^0.25)/3, so that's our case. To perform the attack we are to be able to make continued fractions from ordinary ones, calculate convergents of fractions and solve quadratic equations in rational field. A quick glance at Sage package hasn't given an impression to help us in this: its method "continued_fraction" seems to be working, but we don't want to make division before finding continued fraction values not to loose preciseness. Therefore let's write some code ourselves.

First, method to make continued fraction -- it's tested to give the same result as "continued_fraction" method of sage does:

def makeNextFraction(fraction):
    (a,b) = fraction
    res=b/a
    a1=b%a
    b1=a
    return res, (a1,b1)

def makeContinuedFraction(fraction):
    (a,b) = fraction
    v=[]
    v.append(0)
    while not a == 1:
        r, fraction = makeNextFraction(fraction)
        (a,b) = fraction
        v.append(r)
    v.append(b)
    return v

Next, method for finding convergents -- the same as sage's "continued_fraction(e).convergents()":

def makeIndexedConvergent(sequence, index):
    (a,b)=(1,sequence[index])
    while index>0:
        index-=1
        (a,b)=(b,sequence[index]*b+a)
    return (b,a)

def makeConvergents(sequence):
    r=[]
    for i in xrange(0,len(sequence)):
        r.append(makeIndexedConvergent(sequence,i))
    return r

To solve quadratic equations we will use sympy package:

from sympy.solvers import solve
from sympy import Symbol

def solveQuadratic(a,b,c):
    x = Symbol('x')
    return solve(a*x**2 + b*x + c, x)

To try different convergents let's use this code:

def wienerAttack(N,e):
    conv=makeConvergents(makeContinuedFraction((e,N)))
    for frac in conv:
        (k,d)=frac
        if k == 0:
            continue
        phiN=((e*d)-1)/k
        roots=solveQuadratic(1, -(N-phiN+1), N)
        if len(roots) == 2:
            p,q=roots[0]%N,roots[1]%N
            if(p*q==N):
            	return p, q

Now we can stick this all together and save as wienner_attack.py [see attached].

The reminder we do manually.

1. Save sheriff's ssh-rsa public key to sheriff.pub.
2. Convert ssh-rsa to pem with ssh-keygen:

   $ ssh-keygen -f sheriff.pub -e -m pem > sheriffpub.pem

3. Get e and N from PEM using openssl:

   $ openssl asn1parse -in sheriffpub.pem -i
       0:d=0  hl=4 l= 520 cons: SEQUENCE          
       4:d=1  hl=4 l= 256 prim:  INTEGER           :02AEB637F6152AFD4FB3A2DD165AEC9D5B45E70D2B82E78A353F7A1751859D196F56CB6D11700195F1069A73D9E5710950B814229AB4C5549383C2C87E0CD97F904748A1302400DC76B42591DA17DABAF946AAAF1640F1327AF16BE45B8830603947A9C3309CA4D6CC9F1A2BCFDACF285FBC2F730E515AE1D93591CCD98F5C4674EC4A5859264700F700A4F4DCF7C3C35BBC579F6EBF80DA33C6C11F68655092BBE670D5225B8E571D596FE426DB59A6A05AAF77B3917448B2CFBCB3BD647B46772B13133FC68FFABCB3752372B949A3704B8596DF4A44F085393EE2BF80F8F393719ED94AB348852F6A5E0C493EFA32DA5BF601063A033BEAF73BA47D8205DB
     264:d=1  hl=4 l= 256 prim:  INTEGER           :0285F8D4FE29CE11605EDF221868937C1B70AE376E34D67F9BB78C29A2D79CA46A60EA02A70FDB40E805B5D854255968B2B1F043963DCD61714CE4FC5C70ECC4D756AD1685D661DB39D15A801D1C382ED97A048F0F85D909C811691D3FFE262EB70CCD1FA7DBA1AA79139F21C14B3DFE95340491CFF3A5A6AE9604329578DB9F5BCC192E16AA62F687A8038E60C01518F8CCAA0BEFE569DADAE8E49310A7A3C3BDDCF637FC82E5340BEF4105B533B6A531895650B2EFA337D94C7A76447767B5129A04BCF3CD95BB60F6BFD1A12658530124AD8C6FD71652B8E0EB482FCC475043B410DFC4FE5FBC6BDA08CA61244284A4AB5B311BC669DF0C753526A79C1A57

4. Restore factorization of N using Wiener's attack:

   $ python wiener_attack.py -e 0x0285F8D4FE29CE11605EDF221868937C1B70AE376E34D67F9BB78C29A2D79CA46A60EA02A70FDB40E805B5D854255968B2B1F043963DCD61714CE4FC5C70ECC4D756AD1685D661DB39D15A801D1C382ED97A048F0F85D909C811691D3FFE262EB70CCD1FA7DBA1AA79139F21C14B3DFE95340491CFF3A5A6AE9604329578DB9F5BCC192E16AA62F687A8038E60C01518F8CCAA0BEFE569DADAE8E49310A7A3C3BDDCF637FC82E5340BEF4105B533B6A531895650B2EFA337D94C7A76447767B5129A04BCF3CD95BB60F6BFD1A12658530124AD8C6FD71652B8E0EB482FCC475043B410DFC4FE5FBC6BDA08CA61244284A4AB5B311BC669DF0C753526A79C1A57 -n 0x02AEB637F6152AFD4FB3A2DD165AEC9D5B45E70D2B82E78A353F7A1751859D196F56CB6D11700195F1069A73D9E5710950B814229AB4C5549383C2C87E0CD97F904748A1302400DC76B42591DA17DABAF946AAAF1640F1327AF16BE45B8830603947A9C3309CA4D6CC9F1A2BCFDACF285FBC2F730E515AE1D93591CCD98F5C4674EC4A5859264700F700A4F4DCF7C3C35BBC579F6EBF80DA33C6C11F68655092BBE670D5225B8E571D596FE426DB59A6A05AAF77B3917448B2CFBCB3BD647B46772B13133FC68FFABCB3752372B949A3704B8596DF4A44F085393EE2BF80F8F393719ED94AB348852F6A5E0C493EFA32DA5BF601063A033BEAF73BA47D8205DB
   -p 12001304129015480165432875074437607933493850611499879464845243350215176144760883615322622081442653872645865326992384034722586201972392183010813439352778246403016897976571514715418700569567613729681273931557848857971070286176848136118602099586101089743239644367344468295964691411425416652519752140536869089101
   -q 28216117316929874067495888027767527011360661622486842768414059951572932145196930641365509243766454218518793508840136548374994021850853203018205749779390383366761851772055038753940967432004901699256177783249460134792699230632136386268348434203012426963129659057781488950062703849444443906614331812260961682887
   -e 318540665379393469901456665807211509077755719995811520039095212139429238053864597311950397094944291616119321660193803737677538864969915331331528398734504661147661499115125056479426948683504604460936703005724827506058051215012025774714463561829608252938657297504427643593752676857551877096958959488289759878259498255905255543409142370769036479607835226542428818361327569095305960454592450213005148130508649794732855515489990191085723757628463901282599712670814223322126866814011761400443596552984309315434653984387419451894484613987942298157348306834118923950284809853541881602043240244910348705406353947587203832407

5. Use rsatool.py (https://github.com/ius/rsatool/blob/master/rsatool.py) to generate sheriff's private key:

   $ python rsatool.py -o sheriffpriv.pem -p 12001304129015480165432875074437607933493850611499879464845243350215176144760883615322622081442653872645865326992384034722586201972392183010813439352778246403016897976571514715418700569567613729681273931557848857971070286176848136118602099586101089743239644367344468295964691411425416652519752140536869089101 -q 28216117316929874067495888027767527011360661622486842768414059951572932145196930641365509243766454218518793508840136548374994021850853203018205749779390383366761851772055038753940967432004901699256177783249460134792699230632136386268348434203012426963129659057781488950062703849444443906614331812260961682887 -e 318540665379393469901456665807211509077755719995811520039095212139429238053864597311950397094944291616119321660193803737677538864969915331331528398734504661147661499115125056479426948683504604460936703005724827506058051215012025774714463561829608252938657297504427643593752676857551877096958959488289759878259498255905255543409142370769036479607835226542428818361327569095305960454592450213005148130508649794732855515489990191085723757628463901282599712670814223322126866814011761400443596552984309315434653984387419451894484613987942298157348306834118923950284809853541881602043240244910348705406353947587203832407 &>0

6. Login with sheriff's credentials and get the flag:

   $ chmod 0600 sheriffpriv.pem
   $ ssh sheriff@wildwildweb.fluxfingers.net -p 1427 -i sheriffpriv.pem
   Woah look how much gold that old croaker has: flag{TONS_OF_GOLD_SUCH_WOW_MUCH_GLOW}