# qchecker (misc, 14 teams solved) ###### tags: `SECCON CTF 2021` ## Overview ![](https://i.imgur.com/Dq0HHzG.png) ```ruby= eval$uate=%w(a=%(eval$uate=%w(#{$uate})*"");Bftjarzs=b=->a{a.split(?+).map{|b|b.to_i(36)}};c=b["awyiv4fjfkuu2pkv+awyiv4f v ut 71 6g 3j +a x c e5e4pxrogszr3+5i0o mfd5dm9xf9q7+axce5 e4khrz21ypr+5htqqi 9iasvmjri7+axcc76i 03zrn7gu7+cbt4 m8 xybr3cb27+1ge6 s n jex10w3si9+1k8vdb4 fzcys2yo0"];d,e,f, g,h,i=b["0+0+zeexa xq012eg+k2htkr1ola j6+3cbp5mnkzll t3 +2qpvamo605t7j " ] ;(j=eval(?A<<82<<7 1<<86)[0])&&d==0&& (e+=1;k=2**64;l=-> (a,b){(a-j.ord)*25 6.pow(b-2,b)%b }; f=l[f,k+13];g= l [ g, k+ 37];h=l[h,k+51];i= l[i,k+81];j==?}&&( d=e==32&&f+g+h +i ==0?2:1);a.sub ! (/"0.*?"/,'"0'+[d ,e ,f,g,h,i].map{|x|x .to_s(36)}*?+<<34) );srand(f);k=b["7a cw+jsjm+46d84" ]; l=d==2?7:6;m=[ ? #*(l*20)<<10]*11* "" ;l.times{|a|b=d==0 &&e!=0?rand(4):0;9 .times{|e|9.times{ |f|(c[k[d]/10* *a %10]>>(e*9+f)& 1 )!=0&&(g=f;h=e;b. ti mes{g,h=h,8-g};t=( h*l+l+a)*20+h+g*2+ 2;m[t]=m[t+1]=""<< 32)}}};a.sub!( /B .*?=/,"B=");n= m . co un t( ?# )- a.length;a.sub ! ("B=","B#{(1..n).map{(rand(26)+97).chr}*""}=");o=0;m.length.times{|b|m[b]==?#&&o<a.length&&(m[b]=a[o];o+=1)};puts(m))*"" ``` This is [Quine](https://en.wikipedia.org/wiki/Quine_(computing)) written in Ruby. Without arguments, qchecker.rb outputs itself. ``` $ ruby qchecker.rb > tmp.rb $ diff qchecker.rb tmp.rb $ $ ruby qchecker.rb | ruby | rby | ruby > tmp.rb $ diff qchecker.rb tmp.rb $ ``` By giving arguments, each character randomly spins and finally shows `WRONG` (if arguments are not the correct flag). ``` $ ruby qchecker.rb S eval$uate=%w(a=%(eval$uate=%w(#{$uate})*"");Bwgbo=b=->a{a.split(?+).map{|b|b.to_i(36)}};c=b["awyiv4fjfkuu2pkv+awyiv4fvut 7 16 g3 j+axce5e4pxrog sz r3 +5 i 0 omfd5dm9xf9q7+axce 5e4khr z21ypr +5 htqqi9iasvmjri 7+axcc76i03zrn7gu7 +c bt4m8xybr3cb27 +1ge6snjex10w3si9+ 1 k 8vdb4fzcys2yo0"];d ,e,f,g ,h,i=b [" 00+1+39ubf223f 9ukl+1nr1yq4jmt2uc +2 i94g0cg8tzr9+3 pyrp2i6zsa4o"];(j= e v al(?A<<82<<71<<86) [0])&& d==0&& (e +=1;k=2**64;l= ->(a,b){(a-j.ord)* 25 6.pow(b-2,b)%b };f=l[f,k+13];g=l[ g , k+ 37];h= l[h,k+ 51 ];i=l[i,k+81]; j==?}&&(d=e==32&&f +g +h+i==0?2:1);a .sub!(/"0.*?"/,'"0 ' +[d,e,f,g,h,i].ma p{ |x|x.t o_s(36 )} *?+<<34));sran d(f);k=b["7acw+jsj m+ 46d84"];l=d==2 ?7:6;m=[?#*(l*20)< < 10]*11*"";l.times {| a|b=d= =0&&e! =0 ?rand(4):0;9.t imes{|e|9.times{|f |( c[k[d]/10**a%1 0]>>(e*9+f)&1)!=0& & (g=f;h=e;b.times{ g, h=h,8- g};t=( h* l+l+a)*20+h+g* 2+2;m[t]=m[t+1]="" << 32)}}};a.sub!( /B.*?=/,"B=");n=m. c o un t(?#)- a.leng th ;a .s ub ! ("B=","B#{(1..n).map{(rand(26)+97).chr}*""}=");o=0;m.length.times{|b|m[b]==?#&&o<a.length&&(m[b]=a[o];o+=1)};puts(m))*"" ``` ``` $ ruby qchecker.rb S | ruby - E eval$uate=%w(a=%(eval$uate=%w(#{$uate})*"");Biudihhz=b=->a{a.split(?+).map{|b|b.to_i(36)}};c=b["awyiv4fjfkuu2pkv+awyiv4f v ut716g 3j +axce5 e4pxro gs zr 3+ 5i 0 o mfd5dm 9xf9q7 +a xce5e4 khrz21 yp r+5htqqi9iasvm jr i7+axcc76i03zr n7 gu7+cbt4m8xybr 3c b27+1ge6snjex10w3 s i9+1k8 vdb4fz cy s2yo0" ];d,e, f, g,h,i=b["00+2+ zh x2zkipay9t+34g nm 6zxe6vmb+cowor 1r 18pu+3m9rkvnbbvy7 c "];(j= eval(? A< <82<<7 1<<86) [0 ])&&d==0&&(e+= 1; k=2**64;l=->(a ,b ){(a-j.ord)*25 6. pow(b-2,b)%b};f=l [ f,k+13 ];g=l[ g, k+37]; h=l[h, k+ 51];i=l[i,k+81 ]; j==?}&&(d=e==3 2& &f+g+h+i==0?2: 1) ;a.sub!(/"0.*?"/, ' "0'+[d ,e,f,g ,h ,i].ma p{|x|x .t o_s(36)}*?+<<3 4) );srand(f);k=b [" 7acw+jsjm+46d8 4" ];l=d==2?7:6;m=[? # *(l*20 )<<10] *1 1*"";l .times {| a|b=d==0&&e!=0 ?r and(4):0;9.tim es {|e|9.times{|f |( c[k[d]/10**a%10]> > (e*9+f )&1)!= 0& &(g=f; h=e;b. ti mes{g,h=h,8-g} ;t =(h*l+l+a)*20+ h+ g*2+2;m[t]=m[t +1 ]=""<<32)}}};a.su b !(/B.* ?= /, "B=");n=m.coun t( ?#)-a.length;a .s ub ! ("B=","B#{(1..n).map{(rand(26)+97).chr}*""}=");o=0;m.length.times{|b|m[b]==?#&&o<a.length&&(m[b]=a[o];o+=1)};puts(m))*"" ``` ``` $ ruby qchecker.rb | \ > ruby - S | \ > ruby - E | \ > ruby - C | \ > ruby - C | \ > ruby - O | \ > ruby - N | \ > ruby - } eval$uate=%w(a=%(eval$uate=%w(#{$uate})*"");Bznsfhsqlrgcghiaegtbnuluptkqabxjbjfoyccwvwy=b=->a{a.split(?+).map{|b|b.to_i( 3 6)}};c =b["aw yi v4 fj fk uu2pkv+awyiv4fvut716g 3 j+axce 5e4pxr og szr3+5i0omfd5d m9 xf9q7+axce5e4k hr z21ypr+5htqqi9 ia svmjri7+axcc76i03zrn7gu7+cbt4m8xybr3c b 27+1ge 6snjex 10 w3si9+1k8vdb4f zc ys2yo0"];d,e,f ,g ,h,i=b["01+7+2 xx pr6klrgdhm+3k56y97gn2udi+2vlsu8rxnir5 t+1 qk vn lt r7xz h4"];(j=eval(? A< <82<<71<<86)[0 ]) &&d==0&&(e+=1; k= 2**64;l=->(a,b){(a-j.ord)*256.pow(b-2 ,b) %b }; f= l[f, k+ 13];g=l[g,k+37 ]; h=l[h,k+51];i= l[ i,k+81]; j==?}&&(d=e==32&&f+g+ h+i == 0? 2: 1);a .sub!(/" 0.*?"/,' "0'+[d,e,f,g,h ,i ].map{|x|x.to_ s( 36)}*?+<<34)); srand(f);k=b["7acw+js jm+46 d84"]; l=d==2 ?7:6;m=[?# *(l*20 )<<10]*11*"";l .t imes{|a|b=d==0 && e!=0?rand(4):0 ;9.times{|e|9.times{| f|(c[ k[d]/1 0**a%1 0]>>(e*9+f)& 1)!= 0&&(g=f;h=e;b. ti mes{g,h=h,8-g} ;t =(h*l+l+a)*20+ h+ g*2+ 2;m[ t]=m[ t+1]= ""<<32 )}}};a .sub!(/B.*?=/, "B =" );n=m.count(?# )- a. leng th;a .sub! ("B=","B#{(1..n).map{(rand(26)+97).chr}*""}=");o=0;m.length.times{|b|m[b]==?#&&o<a.length&&(m[b]=a[o];o+=1)};puts(m))*"" ``` ## Reversing part The outermost structure of this script is `eval$uate=%w(...)*""`. An idiom `%(abc def xyz)*""` becomes a string `"abcdefxyz"`. So, by erasing all spaces and inserting appropriate spaces and line breaks, we get the following formatted script: ```ruby= eval$uate=%w( a = %(eval$uate=%w(#{$uate})*""); Bftjarzs = b = -> a { a.split(?+).map{|b| b.to_i(36) } }; c = b["awyiv4fjfkuu2pkv+awyiv4fvut716g3j+axce5e4pxrogszr3+5i0omfd5dm9xf9q7+axce5e4khrz21ypr+5htqqi9iasvmjri7+axcc76i03zrn7gu7+cbt4m8xybr3cb27+1ge6snjex10w3si9+1k8vdb4fzcys2yo0"]; d, e, f, g, h, i = b["0+0+zeexaxq012eg+k2htkr1olaj6+3cbp5mnkzllt3+2qpvamo605t7j"]; (j = eval(?A<<82<<71<<86)[0]) && d==0 && ( e += 1; k = 2**64; l = ->(a,b){ (a-j.ord) * 256.pow(b-2, b) % b }; f = l[f, k+13]; g = l[g, k+37]; h = l[h, k+51]; i = l[i, k+81]; j==?} && ( d = e==32 && f+g+h+i==0 ? 2 : 1 ); a.sub!( /"0.*?"/, '"0' + [d, e, f, g, h, i].map{|x|x.to_s(36)}*?+ << 34 ) ); srand(f); k = b["7acw+jsjm+46d84"]; l = d==2 ? 7 : 6; m = [?#*(l*20)<<10]*11*""; l.times{|a| b = d==0 && e!=0 ? rand(4) : 0; 9.times{|e| 9.times{|f| (c[k[d]/10**a%10]>>(e*9+f)&1)!=0 && ( g = f; h = e; b.times{ g, h = h, 8-g }; t = (h*l+l+a)*20+h+g*2+2; m[t] = m[t+1] = ""<<32 ) } } }; a.sub!(/B.*?=/, "B="); n = m.count(?#)-a.length; a.sub!("B=", "B#{(1..n).map{(rand(26)+97).chr}*""}="); o = 0; m.length.times{|b| m[b]==?# && o<a.length && ( m[b] = a[o]; o += 1 ) }; puts(m) )*"" ``` Several Ruby's features are used for compacting and obfuscating the script. |Code|Description| |----|----| |`$uate`|`$` makes a global variable. The main purpose here is to separate from `eval`. i.e. `eval$uate=...` is `eval($uate=...)`.| |`%(abc())`|`"abc()"`. A string which can include parentheses as long as they are balanced.| |`%w(abc xyz ())`|`["abc", "xyz", "()"]`. An array of strings. |`b=->(a){a+1}; b[1]`|A lambda and calling the lambda.| |`"zeexaxq012eg".to_i(36)`|`4659461645708163688`. Ruby can decode base-36 numbers.| |`?x`, `??`|`"x"`, `"?"`. Single-character string literals.| |`str<<n`|`str += n.chr`.| The second half of the code format the code itself to ASCII Art. So, we don't need to read it to get the flag. The main part can be rewritten as follows: ```ruby= char = ARGV[0]; if (char) { if (state == 0) { len += 1; k = 2**64; l = lambda{|a, b| (a-char.ord) * 256.pow(b-2, b) % b }; f = l.call(f, k+13); g = l.call(g, k+37); h = l.call(h, k+51); i = l.call(i, k+81); if (char=="}") { if (len==32 && f+g+h+i==0) state = 2 else state = 1 } # Write-back state, flag_len, f, g, h and i to the code ``` With guessing or analysing the second part, we can find that `state=0` means `"SECCON"` (accepting the input), `state=1` means `"WRONG"` and `state=2` means `"CORRECT"`. Finally, let us rewrite the entire code without Quine. ```ruby= flag = "SECCON{bad}" F = [ 0x40a9bbae0cfdfa68, 0x24a8b18187759492, 0xdbc9aa8c316224a7, 0xb45237d9e59cfb1f, ] M = [ 0x1000000000000000d, 0x10000000000000025, 0x10000000000000033, 0x10000000000000051, ] flag.each_char{|char| 4.times{|i| F[i] = (F[i]-char.ord) * 256.pow(M[i]-2, M[i]) % M[i] } } if flag.length==32 && F.sum==0 then puts "CORRECT" else puts "WRONG" end ``` ## Crypto part All numbers in `M` are primes. For a prime $m$, the power $256^{m-2}$ in mod $m$ is a multiplicative inverse of $256$ since $256^{m-2} \times 256 \equiv 1 \mod m$ from [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem). We can see that the above code interprets the flag as a little-endian integer and checks if it equals to the specific value in four modulos. The flag (as an integer) must satisfy the following conditions. $$ \begin{align} \mathrm{flag} & \equiv \mathrm{0x40a9bbae0cfdfa68} \mod \mathrm{0x1000000000000000d}, \\ \mathrm{flag} & \equiv \mathrm{0x24a8b18187759492} \mod \mathrm{0x10000000000000025}, \\ \mathrm{flag} & \equiv \mathrm{0xdbc9aa8c316224a7} \mod \mathrm{0x10000000000000033}\ \mathrm{and} \\ \mathrm{flag} & \equiv \mathrm{0xb45237d9e59cfb1f} \mod \mathrm{0x10000000000000051}. \end{align} $$ From [Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) (CRT), we can get the flag in mod $m' = M[0]\times M[1]\times M[2]\times M[3]$. This is the actual flag since $\mathrm{flag} < m'$. [SageMath](https://www.sagemath.org/) has an implementation of CRT. ```sage= F = [ 0x40a9bbae0cfdfa68, 0x24a8b18187759492, 0xdbc9aa8c316224a7, 0xb45237d9e59cfb1f, ] M = [ 0x1000000000000000d, 0x10000000000000025, 0x10000000000000033, 0x10000000000000051, ] print(int(crt(F, M)).to_bytes(32, "little").decode()) ``` ``` $ sage solve.sage SECCON{L3t5_wr1t3_y0ur_Qu1n3!!!} ``` `SECCON{L3t5_wr1t3_y0ur_Qu1n3!!!}`