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

SSSS.RNG

$p$を512bitの素数、

$a,b,x$を

$p$未満のランダムな数とする。

以下すべて

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

$$\begin{array}{rl}{g}_1& =ax+b\\ g_2& =a{g}_1+b\\ g_3& =a{g}_2+b\\ g_4& =a{g}_3+b\\ g_5& =a{g}_4+b\\ g_6& =a{g}_5+b\end{array}$$

とする。

$$f(X):=g_1+g_{2}X+g_3{X}^2+g_4{X}^3+g_5{X}^4+g_6{X}^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関数を用いた値

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

が与えられる。

解法

$\mathrm{floor}\mathrm{\_}\mathrm{sum}(n,m,a,b)$ が直線

$((0,\frac{b}{m}),(n,\frac{an+b}{m}))$ 以下の格子点の数に等しいことに留意すると、

$p$ と

$q$ が互いに素のとき、

$$\mathrm{floor}\mathrm{\_}\mathrm{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すれば勝ち。