# BSides Ahmedabad CTF 2021 Writeup - SSSS.RNG, floorsa, Roda

## SSSS.RNG

$p$を512bitの素数、$a,b,x$を$p$未満のランダムな数とする。

以下すべて$\mathbb{Z}/p\mathbb{Z}$上の演算として、

$$
\begin{aligned}
g_1&=ax+b\\
g_2&=ag_1+b\\
g_3&=ag_2+b\\
g_4&=ag_3+b\\
g_5&=ag_4+b\\
g_6&=ag_5+b
\end{aligned}
$$

とする。

$$f(X):=g_1+g_2X+g_3X^2+g_4X^3+g_5X^4+g_6X^5$$

と定義して、$f(1),f(2),f(3),f(4),f(m),p$ が与えられるので$m$を復元する。

### 解法

線形合同法で生成される数値は $x$ と $b$ に関して1次の多項式となるので、$f(X)$ は $a$ に関する多項式 $l(X), k(X)$ を用いて

$$f(X)=l(X)x+k(X)b$$

と書ける。これと $f(1),f(2),f(3),f(4)$ を用いると $x,b$ を消去できるので $a$ に関する一変数高次合同式が得られる。この式の根を求めると $a$ が得られ、残りも解ける。

p = 2908561168050746475465170048583677924550221390147321314856251074876765877416890922338619139786060615096740196376171212325702080653039392939240436429222829
vs = [(1, 1651293975450381579706844999808202297670211173037061827272908790114230592434748044848097133563469251678879059156225205298834971071359017469397331605782920), (2, 49656064002974834481096383104316375265711545391722811288216446968986145936494966876404160910407919885451814058823146922107458035910700220495010462147112), (3, 1481214561214496310917942246038921499126047497749957535731608952096552856013930232284898279007009260107597472601959627310496773682697020898442717240484400), (4, 1950790377868548708758723604473108315857898618124646291056275632619091046294238343215502355242288776617394025418770078552886012721353626716473759644786481)]
fm = 708078355843841364722603057137729966137248436075776171805731561888875332687774464375592593202164126123800524500062359645261336234459019198930345744751457

PR.<a> = PolynomialRing(GF(p))

# f(X) := l(X) * x + k(X) * b
def l(y):
    factor = a
    ret = 0
    for i in range(6):
        ret += factor
        factor *= a * y
    return ret
def k(y):
    factor = 0
    ret = 0
    for i in range(6):
        factor += a ** i
        ret += factor * y ** i
    return ret


f1, f2, f3, f4 = vs[0][1], vs[1][1], vs[2][1], vs[3][1]
k1, k2, k3, k4 = k(1), k(2), k(3), k(4)
l1, l2, l3, l4 = l(1), l(2), l(3), l(4)

d = (l2 * f1 - l1 * f2) * (l4 * k3 - l3 * k4) - (l4 * f3 - l3 * f4) * (l2 * k1 - l1 * k2)
roots = d.roots()
raw_a = roots[0][0]
raw_l1, raw_l2 = l1(raw_a), l2(raw_a)
raw_k1, raw_k2 = k1(raw_a), k2(raw_a)
raw_b = (raw_l2 * f1 - raw_l1 * f2) / (raw_l2 * raw_k1 - raw_l1 * raw_k2)
raw_x = (f1 - raw_k1 * raw_b) / raw_l1

PR2.<m> = PolynomialRing(GF(p))

def g(i):
    ret = raw_x
    for j in range(i):
        ret = raw_a * ret + raw_b
    return ret

fm_g = g(1) + g(2) * m + g(3) * m^2 + g(4) * m^3 + g(5) * m^4 + g(6) * m^5
flag = int((fm_g - fm).roots()[0][0])
print(flag.to_bytes((flag.bit_length() + 7) // 8, 'big'))

## floorsa

通常のRSAの $N,c$ に加えて、[floor_sum](https://atcoder.jp/contests/practice2/tasks/practice2_c)関数を用いた値

$$s:=\mathrm{floor\_sum}(q,q,p,0)$$

が与えられる。

### 解法

$\mathrm{floor\_sum}(n,m,a,b)$ が直線 $((0,\frac{b}{m}),(n,\frac{an+b}{m}))$ 以下の格子点の数に等しいことに留意すると、$p$ と $q$ が互いに素のとき、

$$\mathrm{floor\_sum}(q,q,p,0)=\frac{pq-p-q+1}{2}$$

である。

これと $N:=pq$ を用いると $p+q$ が得られるので、解ける。

require 'openssl'

c = 23040235907187792043102377766239160347012425454756214402219399982044253963561544138187423569531882081170834886320190973854626011799820277883217582208960795474430615579336090533683566370889382239077437657567815790536809115842475993748108172855688647606634510990327206587307392015543017884876145469179123535144938693302707229724909443912012098405828416163212773471183275687343852756789315215914149905888864296778004572587778916842514807079884644431138433900314631727531570096879428541834626325720522038566946030094711700613155240677360427005636301342509966941323931780006792225168839057660986447452212763627881844882128
n = 25436172154773316497363731760659809627551021985352168624695689317365040018878195925779734249357382145683534839534348832631746578327288150976696513216052612085728199134879493012682967254530827617417753223998955022174337237825391634619718971640535408277659054217709169558518413217237374290054035438476060534235907848570089739603581573457194953083783917042829987113625590656741008590506988903895998008845547262465276679611851110911540261411521221317990139079888782193797945245078986517794660508171428778191152342783279365287710944280356669999624474416422142006473378042779555537142175392801014489187786764971671239717769
s = 12718086077386658248681865880329904813775510992676084312347844658682520009439097962889867124678691072841767419767174416315873289163644075488348256608026306042864099567439746506341483627265413808708876611999477511087168618912695817309859485820267704138829527108854584779259206608618687145027017719238030267117794390566380531016624830798422997060308480467087130633621890831591995264022449058406630323270130520401030807803477672651197312971884784226103671425190328967548002718406368654056897938481966140031709870266384782295285897095028680666943294657806202686252742158733266700286323555374087306844259404255328911060160
e = 65537

pq = n - (s * 2 - 1)
t2 = pq**2 - 4 * n
t = (1...t2).bsearch {|i| i * i >= t2}
q = (pq + t) / 2
p = n / q
phi = (p - 1) * (q - 1)
d = e.to_bn.mod_inverse(phi)
m = c.pow(d.to_i, n)
print([m.to_s(16)].pack('H*'))

## Roda

### 解法

`isValidFile`関数をごまかす。

const SIGNATURES = {
  'png': new Uint8Array([0x89, 0x50, 0x4e, 0x47, 0x0d, 0x0a, 0x1a, 0x0a]),
  'jpg': new Uint8Array([0xff, 0xd8])
};

function compareUint8Arrays(known, input) {
  if (known.length !== input.length) {
  	return false;
  }

  for (let i = 0; i < known.length; i++) {
    if (known[i] !== input[i]) {
      return false;
    }
  }

  return true;
}

function isValidFile(ext, data) {
  // extension should not have special chars
  if (/[^0-9A-Za-z]/.test(ext)) {
    return false;
  }

  // prevent uploading files other than images
  if (!(ext in SIGNATURES)) {
  	return false;
  }

  const signature = SIGNATURES[ext];
  return compareUint8Arrays(signature, data.slice(0, signature.length));
}

`ext = 'toString'` などとすれば `'toString' in SIGNATURES === true` かつ `SIGNATUERS.toString.length === 0` となるので任意の `data` がチェックを通過する。似たようなロジックでMIMETYPEが `text/html` となるので任意のHTMLをアップロードできることになる。あとは適当にXSSすれば勝ち。