---
# System prepended metadata

title: 'qchecker (misc, 14 teams solved)'
tags: [SECCON CTF 2021]

---

# 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!!!}`
