Hack You Too CTF - Crypto 400 - Uncle Rivest

Description
Uncle Rivest challenges you to a battle and proposes you to steal flag from his secure infrastructure.

We have access to the python source code of the service. We can easily identify it as RSA cryptosystem from the name of the challenge and source code. Below is the important part of code

            cmd = raw_input('[0] Get auth key\n[1] Login\n[2] Exit\n').strip()
            if cmd == '0':
                login = raw_input('Enter your login:\n').strip()
                if re.search('[^a-zA-Z0-9]', login):
                    print 'Bad login'
                    continue
                if login == self.admin:
                    print 'Not for admins!'
                elif len(login) < self.max_login_len:
                    m = self.str_to_hash(login)
                    auth_key = self.binpow(m, self.d, self.n)
                    print 'Your auth key:\n%s' % base64.b64encode(str(auth_key))
                else:
                    print 'Error'
            elif cmd == '1':
                login = raw_input('Login:\n').strip()
                auth_key = raw_input('Auth key:\n').strip()
                try:
                    auth_key = int(base64.b64decode(auth_key))
                except:
                    print 'Error'
                    continue
                c = self.str_to_hash(login)
                if c == self.binpow(auth_key, self.e, self.n):
                    if login == self.admin:
                        flag = open('flag.txt','r').readline().strip()
                        print 'You win!\nFlag is: %s' % flag
                    else:
                        print 'Welcome, %s! You are not admin' % login
                else:
                    print 'Wrong auth key!'
            elif cmd == '2':
                sys.exit(0)

Summary of service:
[*] The service calculates the hash value of login name
[*] Then signs on the hash value as hash(m)^d mod n. This is sent back as authorization key
[*] The service doesn't sign when the login name is 'admin357'
[*] We will get flag if we could forge the signature of 'admin357' and validate ourself as admin

The public exponent e and modulo n value are given. Private exponent d is unknown.

e = 65537
n = 24007134668077839318704239757833363695524302813772795891485519226984107072647247568832064425929097558895623559893945502194926707312564453230806425423424997149843823227221596369795583261387779649714834167992749218150200223683296423069590080742550774828141844004559612066990484264910946488068587829100994639319674561758961812687482393281457478086918858906261630888892035335571465704005412337006332665433676386472229329420439767309647448615375682557274786037161968945400623209502352428011196477777002370787813952767888262642821196216644015950350716009261032012403125915949137853338061422774091806367454086620172463286011

After some googling I came across this paper How Not to Design RSA Signature Schemes. It gave good summary of attacks on RSA system. Page 8 describes The Desmedt and Odlyzko Attack against RSA Signatures that use Hash Function. This is what the attack says

[*] It applies to signatures when messages to sign are relatively small
[*] Factor the message we wish to forge into small primes
[*] Obtain signatures for these small primes [ Sig(m1) and Sig(m2) ]
[*] Produce the signature by multiplying the factors signature [ Sig('admin357') = Sig(m1)) * Sig(m2) mod n ]

This method looked much feasible and relevant for this particular challenge. We do the above steps to get the flag. Using the hash function defined in source code, we find the hash value of 'admin357' as 240021000768277

sage: factor(240021000768277)
2879449 * 83356573

Now we should find the two messages whose hash values are 2879449 and 83356573. For this, write a bruteforcer

#!/usr/bin/env python
# Brute.py

from multiprocessing import Process
import string

charset = map(chr,range(ord('a'),ord('z')+1)+range(ord('A'),ord('Z')+1)+range(ord('0'),ord('9')+1))
p = len(charset)+1
sec_option = string.ascii_letters + string.digits

def find_login(start, end):
    for i in sec_option[start:end]:
       for j in sec_option:
           for k in sec_option:
               for l in sec_option:
                   for m in sec_option:
                       s = i + j + k + l + m
                       res = 0
                       p_pow = 1
                       for ch in s:
                           res = res + (charset.index(ch) + 1) * p_pow
                           p_pow = p_pow * p
                       if res == 83356573:
                           print s
threads = 10
size = len(sec_option)/threads

for i in range(threads):
    if i == threads - 1:
        pro = Process(target=find_login, args=(end, len(sec_option)))
    else:
        start = i*size
        end = (i+1)*size
        pro = Process(target=find_login, args=(start, end))
    pro.start()

hash(HDFk)  == 2879449
hash(m4vre) == 83356573

Now find the signatures of these two messages:

Enter your login:
HDFk
Your auth key:
MjAyMTc3NTc0ODE4MDk3NjI4NTgxNjkyNjU1NTkyNDU2OTczMzc4MTkyMzYzMjQ0MTI2MzQ0MTY2MTE3MDc4NTU1ODI1MjU2OTQyNTg5ODYzNjE3MjQxMTUxMDg2ODk4OTY5OTQ0NjkyMDQ2MDU5MzIwNjYzNjY3MTc4MTYwMTI0MjQ0NzUzMjYzMDAxMzU2ODYwOTMzMDkyNDAxMzQ3MzgwNzIyODk2NzY1MjU5ODYyMTExODUzMzkxNjM5ODE0MjU1MjU5Njk2ODU2ODgyMTcxNDI4NDAzNzA2OTI4NDEwMTg3NDA3MDczODc2NzE0MDQ4NTg0MzI4MjcyMTk3NTQ1OTE0MDEyNzIzMzc3NDYyNTg0MDQ3OTY3ODc3NzY2NzEwMzU2ODc3NTE4ODg5OTU3MjA0NDAyMTQyNzQ2MjkxODM0MDQ1MzczNzE0MDQzMTc2OTQ5ODYzMDc0ODMxNDgyNTc4MjgwNDAxMDgyMjg2MDMyOTMyNzUyNDAxNzczMDUwMDUyNTEzMDEwNDg0MTgzNjExNjY0NzY3MjYwMjMzOTg0Mzc1OTg1MzQyODI5NTc0NTYyNzQxNDk1MDQ0MTgwNjkwNTI4ODk4Njk4NjAxNzc2Mzg0OTcwMjc3MTE1MzY5NDA0Mjc3OTE0MDk1NDA5MDY5MjYyOTQzNTY0MjA4ODI1Njk0OTY0MjIxNjY5MzIxMjYzMTA5NDAwMzM2MzgyMzgxOTY3MDA2OTc2MTY1MDYyOTI5MDc3NTE1OTU5ODg2NDIzODk2MjgzMDYxNzcwMDkzNTA0ODk0OTgyMzk1OTY5ODU5NjA=
###################################

Enter your login:
m4vre
Your auth key:
OTMyMjgxMTI4NTIyOTY2MDc3Mjg3NDY5MDI0MjkwOTEzNDY2NTEyMzkxNDgzMTEzNjQwNDM1NzUxNTY5NzU2MzA5ODU4ODI4MTY2OTY1OTA0MDM4NTQ4OTQ2MDk0NTA1MTM1ODQ5Mjc2OTQ5OTE5ODI5MzY1MDg2MzIwOTI5MTA5Mzg2NjI5ODU4MjY1MDEyNDAyOTY0OTQwNTk4Njc1NTM3NzY0MTcwODYwODc4MzYxMjk4ODg4MzY1NTc5NzkzNjM5MjM2NTUyNzk1NzA0NzgyNzMxMjEzNTc0Nzk1NDA2MjM5OTExMzYxMDM5MTcwNjk3Njc0NzQ5NjUwMjc5NDk3NzY5NjQ5MTE2ODY0MTQ5NzAyMzI0MTc2NjQzMTE0OTI0MDE0OTYyMzA5NDE2MTI0OTI1MTYxNjgwMjc4NTUwNDYzNDc2MTE5NDUwODEyODIzMjY0MjM1MzY3NjY5NjIwODQxNzUyMjI4ODEwMjM3Mzg5NTc3MjY0NzU1NzM2MjY4MDg1NDI4MzM5ODM4OTAyNjc1MTA0ODgxNzU2OTkwOTU5Njc4MDIxNjQ5MDg5MjA5MjI2ODUyMjU4NjUwNjY0NjAzODY5MTAwNzY1Mjk3NjcyNTM1MDU2Mjc0MDAyMDk4NjY5MDE2NTQ3OTg3OTMyOTU2MTExMjcyOTMxMzg5MjYyODE4ODAzODU3NjIzMzM2NjM5MTMzMjAxMTI3MDI5NDc3OTA1NzI4NDUwODQ5ODY0ODM1MTU1NDk5MDQ2MDAyMTc2NjkzOTQxNTQzMDY2NDM1NzI0NjAyMjgxNzkzNzk1NzcwMw==
###################################

sage: HDFk = 20217757481809762858169265559245697337819236324412634416611707855582525694258986361724115108689896994469204605932066366717816012424475326300135686093309240134738072289676525986211185339163981425525969685688217142840370692841018740707387671404858432827219754591401272337746258404796787776671035687751888995720440214274629183404537371404317694986307483148257828040108228603293275240177305005251301048418361166476726023398437598534282957456274149504418069052889869860177638497027711536940427791409540906926294356420882569496422166932126310940033638238196700697616506292907751595988642389628306177009350489498239596985960 
sage: m4vre = 9322811285229660772874690242909134665123914831136404357515697563098588281669659040385489460945051358492769499198293650863209291093866298582650124029649405986755377641708608783612988883655797936392365527957047827312135747954062399113610391706976747496502794977696491168641497023241766431149240149623094161249251616802785504634761194508128232642353676696208417522288102373895772647557362680854283398389026751048817569909596780216490892092268522586506646038691007652976725350562740020986690165479879329561112729313892628188038576233366391332011270294779057284508498648351554990460021766939415430664357246022817937957703
sage: c = HDFk * m4vre
sage: n = 24007134668077839318704239757833363695524302813772795891485519226984107072647247568832064425929097558895623559893945502194926707312564453230806425423424997149843823227221596369795583261387779649714834167992749218150200223683296423069590080742550774828141844004559612066990484264910946488068587829100994639319674561758961812687482393281457478086918858906261630888892035335571465704005412337006332665433676386472229329420439767309647448615375682557274786037161968945400623209502352428011196477777002370787813952767888262642821196216644015950350716009261032012403125915949137853338061422774091806367454086620172463286011
sage: d = c % n
sage: d
13574623912432240044822863812359283234859747054148159494167235793917678319412072444049220920878999004683366385825155698767760556797615066283417123606928385652060060105820138620728285638496912124805566477509535383074533513156122531232065826370773868088087444815382738938881580869082664659745993055583125491761462132535762521732243362070654723892827301858921446245233115836311936507425056946162395221057250160140532999076594373669854001012508803090254776204137540070507399407964736897613474767804984570580214311552244341901130144736560242966070953745838499808795280677707289411139719908808829636035822691459884636879416
sage: import base64
sage: base64.b64encode(str(d))
'MTM1NzQ2MjM5MTI0MzIyNDAwNDQ4MjI4NjM4MTIzNTkyODMyMzQ4NTk3NDcwNTQxNDgxNTk0OTQxNjcyMzU3OTM5MTc2NzgzMTk0MTIwNzI0NDQwNDkyMjA5MjA4Nzg5OTkwMDQ2ODMzNjYzODU4MjUxNTU2OTg3Njc3NjA1NTY3OTc2MTUwNjYyODM0MTcxMjM2MDY5MjgzODU2NTIwNjAwNjAxMDU4MjAxMzg2MjA3MjgyODU2Mzg0OTY5MTIxMjQ4MDU1NjY0Nzc1MDk1MzUzODMwNzQ1MzM1MTMxNTYxMjI1MzEyMzIwNjU4MjYzNzA3NzM4NjgwODgwODc0NDQ4MTUzODI3Mzg5Mzg4ODE1ODA4NjkwODI2NjQ2NTk3NDU5OTMwNTU1ODMxMjU0OTE3NjE0NjIxMzI1MzU3NjI1MjE3MzIyNDMzNjIwNzA2NTQ3MjM4OTI4MjczMDE4NTg5MjE0NDYyNDUyMzMxMTU4MzYzMTE5MzY1MDc0MjUwNTY5NDYxNjIzOTUyMjEwNTcyNTAxNjAxNDA1MzI5OTkwNzY1OTQzNzM2Njk4NTQwMDEwMTI1MDg4MDMwOTAyNTQ3NzYyMDQxMzc1NDAwNzA1MDczOTk0MDc5NjQ3MzY4OTc2MTM0NzQ3Njc4MDQ5ODQ1NzA1ODAyMTQzMTE1NTIyNDQzNDE5MDExMzAxNDQ3MzY1NjAyNDI5NjYwNzA5NTM3NDU4Mzg0OTk4MDg3OTUyODA2Nzc3MDcyODk0MTExMzk3MTk5MDg4MDg4Mjk2MzYwMzU4MjI2OTE0NTk4ODQ2MzY4Nzk0MTY='

Login:
admin357
Auth key:
MTM1NzQ2MjM5MTI0MzIyNDAwNDQ4MjI4NjM4MTIzNTkyODMyMzQ4NTk3NDcwNTQxNDgxNTk0OTQxNjcyMzU3OTM5MTc2NzgzMTk0MTIwNzI0NDQwNDkyMjA5MjA4Nzg5OTkwMDQ2ODMzNjYzODU4MjUxNTU2OTg3Njc3NjA1NTY3OTc2MTUwNjYyODM0MTcxMjM2MDY5MjgzODU2NTIwNjAwNjAxMDU4MjAxMzg2MjA3MjgyODU2Mzg0OTY5MTIxMjQ4MDU1NjY0Nzc1MDk1MzUzODMwNzQ1MzM1MTMxNTYxMjI1MzEyMzIwNjU4MjYzNzA3NzM4NjgwODgwODc0NDQ4MTUzODI3Mzg5Mzg4ODE1ODA4NjkwODI2NjQ2NTk3NDU5OTMwNTU1ODMxMjU0OTE3NjE0NjIxMzI1MzU3NjI1MjE3MzIyNDMzNjIwNzA2NTQ3MjM4OTI4MjczMDE4NTg5MjE0NDYyNDUyMzMxMTU4MzYzMTE5MzY1MDc0MjUwNTY5NDYxNjIzOTUyMjEwNTcyNTAxNjAxNDA1MzI5OTkwNzY1OTQzNzM2Njk4NTQwMDEwMTI1MDg4MDMwOTAyNTQ3NzYyMDQxMzc1NDAwNzA1MDczOTk0MDc5NjQ3MzY4OTc2MTM0NzQ3Njc4MDQ5ODQ1NzA1ODAyMTQzMTE1NTIyNDQzNDE5MDExMzAxNDQ3MzY1NjAyNDI5NjYwNzA5NTM3NDU4Mzg0OTk4MDg3OTUyODA2Nzc3MDcyODk0MTExMzk3MTk5MDg4MDg4Mjk2MzYwMzU4MjI2OTE0NTk4ODQ2MzY4Nzk0MTY=
You win!
Flag is: h0W_did_YoU_hAck_RSA
###################################
[0] Get auth key
[1] Login
[2] Exit

We have successfully forged the signature for 'admin357' and the flag is : h0W_did_YoU_hAck_RSA