チーム TokyoWesterns で参加。最終 3 位。わたしは diysig 以外の暗号問題を解いた。

ROR (Crypto 260pts)

問題のコードでは、

$N=2^{k_1}3^{k_2}7^{k_3} (k_1, k_2, k_3 は123以上の456以下の未知の整数)$ , $eは271828以上314159以下の未知の整数$ として、 $i = 0, \cdots, mのビット数 - 1$ に対して $\mathrm{ROR}(m,i)^e \bmod n$ を出力している。

$N$ は偶数であることから、 $\mathrm{ROR}(m,i)^e \bmod n \bmod 2 = \mathrm{ROR}(m,i) \bmod 2$ となる。したがって、下位 1bit を順に見ていくと元もメッセージ m が求まる。

irb(main):001:0> [File.read('chall.txt').lines.map{|a|a.to_i%2}.join.reverse.to_i(2).to_s(16)].pack('H*')
=> "zer0pts{0h_1t_l34ks_th3_l34st_s1gn1f1c4nt_b1t}"

nibelung (Crypto 525pts)

コードを読むと、結局のところfglg.pyのFiniteGeneralLinearGroupは各要素が_GF_(p)上にあるような_n_ × _n_行列を表している。

暗号化、復号は未知の鍵となる行列 $U$ とし、メッセージ $F$ をとすると、暗号化: $U F U^{-1}$ 復号: $U^{-1} F U$ となっている。

サーバーでは最初にフラグの暗号化結果を出力し、その後行列の各要素が 0 から 255 までの数である任意の行列に対して暗号化・復号操作を何度でも行うことが出来る。

暗号化操作を見ると、入力 $F$ に対して線形性がある。したがって一つの要素を 1 とし、それ以外の要素を 0 とした 36 種類の行列に対して暗号化を行い、それとフラグの暗号結果の間で線形方程式を解くことによって、フラグを求めることができる。

require 'ctf'
def read(s)
    r = []
    6.times do |i|
        r << s.gets.scan(/\d+/).map{|a|a.to_i}
    end
    r
end
TCPSocket.open(*ARGV) do |s|
    # s.echo = true
    s.expect('Encrypted Flag:')
    s.gets
    flag = read(s)
    
    s.expect(/p = /)
    p = s.gets.to_i
    puts "p = %d" % p
    puts "flag = %s" % flag.inspect
    encs = []
    36.times do |i|
        s.puts('1')
        e = "\0" * 36
        e[i] = "\1"
        s.puts [e].pack('m').split.join
        s.expect('Encrypted:')
        s.gets
        encs << read(s)
    end
    puts "enc = %s" % encs.inspect
    s.puts "3"
end

from out import *

flag = [v for v in sum(flag, [])]
enc = [[v for v in sum(e, [])] for e in enc]
m = Matrix(GF(p), len(flag))
for i in range(len(flag)):
    for j in range(len(flag)):
        m[i, j] = enc[i][j]

print ''.join(list(map(chr, list(m.solve_left(vector(GF(p), flag))))))

$ ruby get_params.rb 13.231.224.102 3002 > out.py
$ sage solve.sage
zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}

dirty laundary (Crypto 636pts)

PRNG は線形であるため、逆や次を容易に求めることができる。各 share について RPNG を 3 回利用しているので順に $r_1, r_2, r_3$ とする。

まず、単純な秘密分散の形にするために、各 share について次のような計算を行う。

$g,n$ を元に $r_2$ を求める。
$r_2$ を元に、 $r_1, r_3$ を求める。
$r_3$ を元に Paillier 暗号を解読し、 $r_1$ と合わせて、f(x)を求める。

これによって秘密分散を解けばよい状態になったが、 $p$ が未知であるため単純に解くことは出来ない。 $f(x) = (k_0 + k_1x+k_2x^2) \bmod(p)$ としたとき、mod_を削除して、 $f(x) = k_0 + k_1x + k_2x^2 - g(x)p (g(x)は0 \leq f(x) < pになるように選択された非負整数)$ と表せる。 $g(x)$ を固定することで、4_変数の線形方程式と見なすことができる。 $f(x)$ の式より、 $t_x$ は $0 \leq g(x) < x^2+x+1$ を満たす。この問題ではxは最大でも_4_であるため、 $g(x)$ の全探索が出来る。

from Crypto.Util.number import long_to_bytes
class PRNG256(object):
    def __init__(self, seed):
        self.mask = (1 << 256) - 1
        self.seed = seed & self.mask

    def _pick(self):
        b = ((self.seed>>0)^^(self.seed>>2)^^(self.seed>>5)^^(self.seed>>10)^^1)&1
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b
    
    def inverse(self):
        b = self.seed >> 255 & 1
        self.seed = self.seed<<1
        b = b ^^ 1
        b  = b ^^ ((self.seed>>2)^^(self.seed>>5)^^(self.seed>>10)) & 1
        self.seed &= self.mask
        self.seed = self.seed | b
        
    def rand(self):
        x = 0
        for i in range(256):
            x = (x << 1) | self._pick()
            s = self.seed
            
            self._pick()
            self.inverse()
            assert s == self.seed
        return x
    
def bit_reverse(x):
    ret = 0
    for i in range(256):
        ret |= (x >> i & 1) << (255 - i)
    return ret

pubkey = [[1341233826702376842498119940039016826282055747303464974435594326637538907180149241566365225911074218597539880291426265503244204409536388336349105099303221252199164187921036400118788488925884552440483653638244202969641876448593915624469362160298646189903056069767976491733960779483023305191435635289734365528710722401088230332490023131911734288011232016872906051832164035804891447455672110954242647111735228814935698789659541198379357658233047482430645842400366769, 26674131724614738833784434076708623929346303545393320399944409878863187402150503055207795853307211144249179748395076848334742855586049336411971031238044174387954252693537728148985955948048292029557791508049506146642880016520533230306989498523300220064692662847160710441255197572391506435448482713046019266895261344521636514739951705743608587218033949609867770113753539973249063631220635085754002655371345431327359674264770777710263422098079037291585196293197114766337658570276078577504309446984989309950901135119579313915133962619448102748], [1411836429669183892966134560305538366838547135114531535251720851922638607907850507674940852917802242615202155607148892358461384679202044548831141295353829571829695255020484687938869019916289932148352179781631904110271902114010910086393396910500275240681423526254331492385949217178047157696773667958133033180038804263460584550022281663780195927924119675790311322672399731902027722031296853164002026620552741589967849779933976523556743919696732887883645621044361611, 54901986783642835051699889113428335659585153809842942356885004842920465421336706391742814742564346205356241657334450930082155461145433648171896778260206136182255774717095790534292114459150791413586339545764791219429615253607065582132297246948860985575596282841990693455389149847062253133706015420405086059551754437445312366999921584484205222674268615179520174172834649126131935196501454388399695961162329114143523185659562031324488650262065740579199795214468943489727171700351304387397461071307646615194578618714043441377328663670751933627], [1827670639023479057974423662769264575893916686880865506873460556631343496594640149665454545389837639322275346518374263849034235979447405363606817187890637783196194162726024155794431981524906947485134171466324929779048499566048313669091401079263506127226379009753084566863868890271238236467261185095363669354791741608878314575987029663948818461252180763032199904220494918133642971421746749038691538192915859604276912102975568194119467980419612286906176868952703619, 141955627685405861596265155634043580262274251775483613944451161608579951914157317215316282492132012795129761525653914539354069858559035449093879514616280531615371142125208924414389214738475566668885506757054698120214732427844927492109681218414883961942239601431792698791724207705264637074459890882510377535948407156226101316457666689930453121343643609559536469767469803312169661110669941502466830780526471703979445391121676012137033701185329849968518454602730837677935298633914797575550202371889703865031673251813095889426000075905120210715], [1402052496936016320097183149388969226815975944499402219852856803114088852450193317864886134127265736138410526536722880486066577543930136034727844243512981614084924117627899623040044660188020312540158405739267327536264551679882312483493710047604544613918162585552941665913115010517121759370648692761286982491236666306877105976920137441035714264352280173247224313429635552985171274872512067599818448065403462190853902179488909659352339753894521914217223448955215971, 86436796561750399172835178406595458158200152808363576725949152209752050457844658406574932376510960241857243310231191629391788175840467781934160642603459961684570827889722817126673212897198457329009359718685889481495826330541120466944045405490044949949259866864077324005529448874478602844692164951174440203087657096219194318354305991767616656455848089449159017933275879827733328877162500978230626795632715808168172022720272496925901610663582044355831900584113960342572153829531696471382379336709069115911649499884361699625754418888357105356], [1342704677106999319938700388688741153377785166648218447242877900112547844266669406514804811924511017558918915960330401218483170328967889513789896923310776509048521832125539811902549091395153161067069971385687776610710438852173147435486069694433486331195576027716222479219032032167578074212853391036064686760331515843088926026790746958731708142341497399752153088465594599246790180097507576747721603670126927119225609501504821203851575717696464442894256866979152071, 151778423244836361358618726678490961359665141861531434745037765026759553125937345447572403824004985824284188179016742237419300096576909738404031925822083587101759301624897645367726786635718018753092807084873240915940763159043557284908261185169254084475196021977237239622460403373815939034200532293365581548664725892312716054043939540402460543140481578956351181169010805594314620139932866466533726652277935117332880706565744981667712583109377942817662191762058437395347618376144282145949244368040832594427185427142218601311894439404196869044]]
shares = [[1, 597508787369395694379078055274758557631538862739941784216641187447047696613646680523204534254585433553841883904815873020522119769161150848487658944289025139852884425534715254212765760070437058597554314741974198161950731308938774064571532399460855957695621714795771549456243813779399463109411846725520743344118554521413815793297768851076100135443002760221642947948812785225122631701884241216019284262219988306790748365483241216049579680655534490056279281295122379176443966669667315043992274193717298501474638381448820981658485993472350525815696097401765948865514729845467484551526100202532018343011967560856014086051860031235536215643818290727062383335942089683311730283931932548912461126311217820002459492022071267001562804194559301166310110244724819006466684456151803974731484616982434451280906366032894303395363863415992620820995729046300233942195095878917887892047030748729267329243516360791348477702146680442138382721731], [2, 1456602020473336436595302182756958090511415476510657696986700623481719785551149148046222482541285365312188959543693509514194665154201380523065476755444520574235515226702501340621170242202481024616882142010693536315240074931107987736512086290237614373546387137118763177589626855206838418103751404170044959913691735814429141324338320985853997370723970242452295801714270370307506226450063833723978620621565509156414542500828358085837989711050634637181122088180962097398190523961973415973551114076986713383243786853784427170667899647985426058777600468130304251574650780445218699779580427275505399994170596637813422179447545139427789051628741760457519163521253124217051884027796849542531386743511788474207049545545002209680929220223136064442178057025754413867781284144371821327271523387818972046823739716532656252490038504917848103009173556160906958786293914926056507083575731302212603218169279706378356509037364037831069878231086], [3, 1595390928798835569336924563570335102923880736692143989367168050283822219400199743337809496383236309872055902908859973435410009867512480962418933647220942557496021772016027755153856780432756247783750165029188435931829475752098685139218491512524939261083097196175538068246302620283880442794354650203913256502298415299185414984420565985768541932846631373242689036582178180151029187744659165675733768586790929935335022733816827888717408760672442814312920814112098749134708381258920239270611481275188904733904484814532961896311957117153388398557892281039130937627251977203045005113457955326984992365109238884156875118258875576742912093629961904108637328565523791833431848861487780279931219592300441525537266970002720517825091950356133381996157142667046040400474609347986971206237389511449743320732065481903260813584781835955382208803634275373602785992176618584713593998708722680023507255977968510697362982348044089009664597010849], [4, 1011012847725577745336080393532189501492336190558468303901251128666948418862933107036802327706950463653743889588322849131239222018844807849320331335500253801822404870042943180018988070672118930708294758392176800835465940314497189212667345256623160148381248676718065742459754530766291525548914975338009832256832712589706835806517309607232698495103676951407256990497727674074485975124944372384103938197756270712242538878327377737064117888518506218677244903776303353809628478075251845418928422454505051034628606854452823018144040158582352384256981850775768889499743760124313790601039804655287368427678715298719610014768027055861100647302291703640051847379108339724116217620803865940790490720181318014407063347236752588796661376810081172579531972899972207972694482013181432385593628852052754597961311854114120889315842451116669964549895840227042765846799089720825799247881359370434521814841837587026380076995924399761319705723220], [5, 585069911394639305069783453652980853778745872799905806085352980735658699442233349825102728267563130252863283620016490723644364840781783036228871276919495247201207769697803633760636387168623971368425694237096294184568991213677440659398241600565247753979592046970818227704368395870777535026523567976874952173624307944192305292867662966386645876919788206043645183603762002422420998136405555517112532618282483706131862387809257609229574812285296154253501278056085465591743515177435365781927790199047842732048344042345351145298190659111295473008507446985055866290274758068271147032318530780490684852153963206087326840116434394159695925404604438964668680275485416592324577630006500633520246499405212932824588562414909326852417065336364436077691987208909857190371325101826958691831214195954288881703669647778463778679987622877010187433236808312183932607053247793338457198918138891876330549197934696966944916096701567755521275990739]]

for i in range(len(pubkey)):
    n, g = pubkey[i]
    c = shares[i][1]
    gnoice = int((g - 1) / n)
    pr = PRNG256(bit_reverse(gnoice))
    for j in range(512):
        pr.inverse()
    noise = pr.rand()
    assert(pr.rand() == gnoice)
    r = pr.rand()
    r = pow(r, n, n ** 2)
    c = Mod(c, n ** 2) / r
    assert int((c-1) / gnoice) % n == 0
    m = int((c-1) / gnoice) // n

    shares[i] = (shares[i][0], Mod(m - noise, n))

def solve(idx, vec):
    if idx == 4:
        M = Matrix(ZZ, 4, 4)
        v = vector(ZZ, 4)
        for i in range(4):
            for j in range(3):
                M[i, j] = (i + 1) ** j
            M[i, 3] = -vec[i]
            v[i] = shares[i][1]
        try:
            ret = M.solve_right(v)[0]
            if 0 < ret and ret < 2 ** 512:
                print(long_to_bytes(ret))
                return True
                
        except ValueError:
            pass
    else:
        m = idx + 1
        for i in range(m ** 2 + m + 1 + 1):
            vec[idx] = i
            if solve(idx + 1, vec):
                return True
            
solve(0, [0] * 4)

$ sage solve.sage

zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}

nomeaning blog.

zer0pts CTF Writeup

ROR (Crypto 260pts)

nibelung (Crypto 525pts)

dirty laundary (Crypto 636pts)