A good challenge about SSP(Subset Sum Problem,a kind of knapsack) in Ant x D^3 CTF 2022.

# Chanllenge

Initial:

v=(R0,R1,R2,...,Rn1)s=(2R0+1,2R1+1,2R2+1,...,2Rn1+1)Ri(0,N),n=100v = (R_0,R_1,R_2,...,R_{n-1})\\ s = (2R_0+1,2R_1+1,2R_2+1,...,2R_{n-1}+1)\\ R_i \in (0,N),n = 100

p(Σ(s_),2Σ(s_))(ps:prime)e(p//2,p1)a=[GF(p)(es0),GF(p)(es1),...,GF(p)(esn1)]PK=a,SK=(s,e,p)p \in (\Sigma(s\_),2\cdot \Sigma(s\_))(ps:prime)e \in (p//2 , p-1)\\ a = [\text{GF}(p)(e\cdot s_0),\text{GF}(p)(e\cdot s_1),...,\text{GF}(p)(e\cdot s_{n-1})]\\ PK=a,SK=(s,e,p)\\

encrypt:

marray(bin(x)).rjust(8k,0)m \rightarrow \text{array(bin}(x)).\text{rjust(8k,0)}

r=(R0,R1,...,Rn2),Ri[0,1]rn=(mΣ(r))mod2r=r+(rn)c=(a0r0+a1r1+a2r2+...++an1rn1)r = (R_0,R_1,...,R_{n-2}),R_i\in [0,1]\\ rn = (m-\Sigma(r))\mod 2\\ r = r + (rn)\\ c = (a_0\cdot r_0 + a_1\cdot r_1 + a_2\cdot r_2 + ... + + a_{n-1}\cdot r_{n-1})

decrypt:

mi=(e1cimodp)mod2m_i = (e^{-1}c_i\mod p)\mod 2

# Analysis

发现该题是一个 Knapsack [1] 问题,但不能用普通的的背包出来。

Q1 : Why can't use regularly method of knapsack to attack it?

A1 :

如果直接在 encrypt 上面进行背包的话,会发现他没法背包出来。方案设计者表明了该方案针对于常规攻击是相对安全的。

为了避免弱密钥,推荐 e[P//2,P1]e\in[P//2,P-1]

为了抵抗低密度的攻击,选择 n>log2N+log2n+1n>\log_2{N}+\log_2{n}+1 去满足 d > 1,防止了我们常规攻击背包问题的方式。

这道题目是 Yasuyuki Murakami 等人的设计 knapsack 公钥密码系统 [3] ,有一篇 paper:《Equivalent key attack against a public-key cryptosystem based on subset sum problem》[2] 讲解针对该题的攻击内容的。

其中说明如果想要恢复 子集和问题 (Subset Sum Problem) 的等价密钥 s1,s2,...,sn,P,es_1,s_2,...,s_n,P,e ,需要让 keys 满足以下条件

  1. ai=esimodP,i[1,n]a_i=es_i\mod P,i \in[1,n]

  2. P 是一个素数(或者用 gcd (P,e) = 1),且满足 P>Σi=1nsiP>\Sigma^n_{i=1}s_i

  3. s1,s2,...,sns_1,s_2,...,s_n 是一个正奇数序列

可知 aiesimodPaiesi+kiPa_i\equiv e\cdot s_i\mod P \Rightarrow a_i\equiv e\cdot s_i+k_i \cdot P

a=(a1a2...an),s=(s1s2...sn),k=(k1k2...kn)a=es+Pk\bold{a} = \left( \begin{matrix}a_1 \\a_2\\...\\a_n\end{matrix}\right), \bold{s} = \left( \begin{matrix}s_1 \\s_2\\...\\s_n\end{matrix}\right), \bold{k} = \left( \begin{matrix}k_1 \\k_2\\...\\k_n\end{matrix}\right)\\ \bold{a} = e\cdot \bold{s} + P\cdot \bold{k}

存在一个 比较短的向量 t 满足

a,t=es,t+Pk,t=0\lang\bold{a},\bold{t}\rang = e \lang\bold{s},\bold{t}\rang + P \lang\bold{k},\bold{t}\rang = 0

如果该向量是足够短的话,需要满足

s,t<Ps,t=0,k,t=0||\lang\bold{s},\bold{t}\rang||< P \Rightarrow \lang\bold{s},\bold{t}\rang=0,\lang\bold{k},\bold{t}\rang=0

因此 向量 s 和向量 k 属于 一个 orthogonal lattice 的 子格。接着可以找到满足上述的最后两个条件的等价私钥。(ps: 事实上,P 并不是严格意义需要去满足他是一个素数,只需要与 e 互素即可)

orthogonal lattice(正交格)[4]:

给出一个格 LZm\mathscr{L}\subseteq \mathbb{Z}^m. 格 L\mathscr{L} 的所有基能够张成 Qm\mathbb{Q}^m 的相同子空间 EEF=EF=E^\perp 作为内积的正交向量子空间。我们定义 orthogonal lattice 为 L={vZmuL,u,v=0}\mathscr{L}^\perp=\{\bold{v}\in \mathbb{Z}^m|\bold{u\in \mathscr{L},\lang\bold{u},\bold{v}\rang = 0} \}

引理:对于任意的格LZm\mathscr{L}\subseteq \mathbb{Z}^mrank(L)+rank(L)=mrank(\mathscr{L})+rank(\mathscr{L}^\perp) = m

# Details of Attack

定义一个格 L1={tL(a)s,t=0}\mathscr{L}_1=\{t\in \mathscr{L}^\perp(\bold{a})|\lang\bold{s},\bold{t}\rang=0\}

Theorem : 定义格 L1={tL(a)s,t=0}\mathscr{L}_1=\{t\in \mathscr{L}^\perp(\bold{a})|\lang\bold{s},\bold{t}\rang=0\} ,那么存在一 个s,t00\lang\bold{s},\bold{t_0}\rang\neq 0 的向量 t0L(a)\bold{t_0} \in \mathscr{L}^\perp(\bold{a}) ,满足 L(a)=L(t0)L1\mathscr{L}^\perp(\bold{a})=\mathscr{L}(\bold{t_0})\oplus \mathscr{L}_1

使用 Algorithm 1,可以计算 L(a)\mathscr{L}^\perp (\bold{a}) LLL 以后的格基为 L(t1,t2,,tn1)\mathscr{L}(\bold{t_1,t_2,\dots,t_{n-1}}) ,并且根据他们长度的升序重新排序这 n-1 个向量 t1,t2,,tn1\bold{t_1,t_2,\dots,t_{n-1}} 。根据 Theorem 可知,只有一个向量是满足 s,t0\lang\bold{s},\bold{t}\rang\neq 0 。将第 n-1 个作为该满足条件的向量。

假设每个 sis_i 的分布都很均匀,可以得到 P>nNP>nN ,同时 s<2nN||\bold{s}||<2\sqrt{n}N 。所以当 t<n/2||\bold{t}||<\sqrt{n}/2 时,s,tstP|\lang\bold{s},\bold{t}\rang|\leq||\bold{s}||\cdot||\bold{t}||\leq P 。那么 n/2t0\sqrt{n}/2\leq||\bold{t_0}|| 时,满足 Thorem 的条件。并且 n-1 个向量 t1,t2,,tn1\bold{t_1,t_2,\dots,t_{n-1}} 是按照长度升序排序的,我们可以知道这里的 tn1\bold{t_{n-1}} 就是此处会产生的最长的 t0\bold{t_0}

再用一次 Algorithm 1,就可以计算得到 L1\mathscr{L}_1^\perp 的正交格 L(u1,u2)\mathscr{L}(\bold{u_1},\bold{u_2}) 。根据上面的 Theorem,以及 tn1\bold{t_{n-1}} 就是此处最长的 t0\bold{t_0} ,认为 s,ti=0,i[1,n2]\lang\bold{s},\bold{t_i}\rang=0 ,i\in[1,n-2] 。 基于 a,t=es,t+Pk,t=0\lang\bold{a},\bold{t}\rang = e \lang\bold{s},\bold{t}\rang + P \lang\bold{k},\bold{t}\rang = 0k,ti=0\lang\bold{k},\bold{t_i}\rang=0 。我们就可以得到 {s,k}L1\{\bold{s},\bold{k}\} \in \mathscr{L}_1^{\perp}

接着去枚举搜寻等价私钥

s=x1u1+x2u2k=y1u1+y2u2xi,yiZ,i=1,2\bold{s}=x_1\bold{u_1} + x_2\bold{u_2}\\ \bold{k}=y_1\bold{u_1} + y_2\bold{u_2}\\ x_i,y_i\in \mathbb{Z},i=1,2

在寻找的过程中需要满足 Analysis 中的最后两条,可以以一个比较高的概率去得到一组等价私钥。

Q2 : How to enumerate the xi,yi ?

A1 :

根据官方的 wp,我们可以得知

s=x1u1+x2u2k=y1u1+y2u2a=z1u1+z2u2xi,yiZ,i=1,2\bold{s}=x_1\bold{u_1} + x_2\bold{u_2}\\ \bold{k}=y_1\bold{u_1} + y_2\bold{u_2}\\ \bold{a}=z_1\bold{u_1} + z_2\bold{u_2}\\ x_i,y_i\in \mathbb{Z},i=1,2

并且根据 s\bold{s} 的奇偶性,可以判断出 x1,x2x_1,x_2 的奇偶性,接着随机生成一组 x1=2k+GF(2)(x1),x2=2h+GF(2)(x2)x_1 = 2k + GF(2)(x_1),x_2 = 2h + GF(2)(x_2) ,满足生成的 s\bold{s} 全是正数即可。

(eP)T(x1x2y1y2)=(z1z2)\left( \begin{matrix}e\\P\end{matrix}\right)^T \cdot \left( \begin{matrix}x_1&x_2\\y_1&y_2\end{matrix}\right) = \left( \begin{matrix}z_1&z_2\end{matrix}\right)

我们可以得知 P > e >> |a| >> zi,接着就可以得知 x1x2y1y2|\frac{x_1}{x_2}|-|\frac{y_1}{y_2}| 比较小。

那么就可以用连分数的办法得到 y1,y2。

A2 :

也可以直接爆破 x1,y1,x2,y2,但运气不好就可能比较难跑出来吧?

完整的算法过程在 Attach 中描述

# Attach

# Algorithm 1. Find out the orthogonal lattice [4]:

INPUT- 格 L\mathscr{L} 的一个 格基 (b1,b2,...,bk)(\bold{b_1},\bold{b_2},...,\bold{b_k})

OUTPUT - 格 L\mathscr{L}^\perp 的 格基 (y1,y2,...,ynk)(\bold{y_1},\bold{y_2},...,\bold{y_{n-k}})

  1. 挑选一个 g=2(n1/2)+((nk)(nk1)/4)Πj=1kbkg = \lceil 2^{(n-1/2)+((n-k)(n-k-1)/4)}\Pi^{k}_{j=1}||\bold{b_k}|| \rceil .

  2. 生成一个(n+k)×n(n+k)\times n 完整格 B\mathscr{B}

    B=(g×b1,1g×b1,2g×b1,ng×b2,1g×b2,2g×b2,ng×bk,1g×bk,2g×bk,n100010001)\mathscr{B} = \left( \begin{matrix}g\times b_{1,1}&g\times b_{1,2}&\dots&g\times b_{1,n}\\g\times b_{2,1}&g\times b_{2,2}&\dots&g\times b_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\g\times b_{k,1}&g\times b_{k,2}&\dots&g\times b_{k,n}\\ 1&0&\dots&0\\ 0&1&\ddots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&1 \end{matrix} \right)

  3. B\mathscr{B} LLL 格基规约后张成 基(x1,x2,,xn)(\bold{x_1},\bold{x_2},\dots,\bold{x_n})

  4. 输出向量 (y1,y2,...,ynk)(\bold{y_1},\bold{y_2},...,\bold{y_{n-k}}) ,其中 yjZn,1jnk\bold{y_j}\in \mathbb{Z}^n,1\leq j\leq n-k .

# Algorithm 2. Recover the equivalent private key [2]

INPUT- 公钥 a\bold{a} .

OUTPUT - 私钥 s,P,e\bold{s},P,e

  1. 计算 a\bold{a} 的正交格,定义 L(a)=L(t1,t2,,tn1)\mathscr{L}^\perp (\bold{a}) = \mathscr{L}(\bold{t_1,t_2,\dots,t_{n-1}})

  2. L1=L(t1,t2,,tn2)\mathscr{L}_1 = \mathscr{L}(t_1,t_2,\dots,t_{n-2}) ,计算他的正交格,定义 L1=L(u1,u2)\mathscr{L}_1^\perp = \mathscr{L}(\bold{u_1},\bold{u_2}) .

  3. s=x1u1+x2u2,k=y1u1+y2u2:xi,yiZ,i=1,2.\bold{s} = x_1\bold{u_1} +x_2\bold{u_2},\bold{k} = y_1\bold{u_1} +y_2\bold{u_2}:x_i,y_i\in \mathbb{Z},i=1,2.

    枚举空间xi,yi<N|xi|,|yi|<\sqrt N

  4. 对每个集合 xi,yi:i=1,2|xi| ,|yi|:i=1,2 ,用 a=es+Pk\bold{a} = e\bold{s}+ P\bold{k} 计算 P 和 e

  5. 用下面两条情况筛选 每个序列 s1,s2,,sn,P,es_1,s_2,\dots,s_n,P,e

    1. gcd(P,e)=1,P>Σi=1nsi\text{gcd}(P,e)=1 ,P>\Sigma_{i=1}^ns_i
    2. s1,s2,,sns_1,s_2,\dots,s_n 是正奇数序列
  6. 剩下来的每一组 s,P,e\bold{s},P,e 都是等价私钥

# Reference

[1] : Knapsack Problem : https://en.wikipedia.org/wiki/Knapsack_problem#Subset-sum_problem

[2] : Jiayang Liu, Jingguo Bi:《Equivalent key attack against a public-key cryptosystem based on subset sum problem》

[3] : Murakami, Y., Hamasho, S., Kasahara, M.: 《A public-key cryptosystem based on decision version of subset sum problem》. Information Theory and its Applications (ISITA), Honolulu, HI, USA, 2012, pp. 735–739

[4] : Nguyen, P.Q., Stern, J.: 《Merkle-Hellman revisited: a cryptanalysis of the QuVanstone cryptosystem based on group factorizations》 CRYPTO, Santa Barbara, CA, USA, 1997, pp. 198–212

请我喝[茶]~( ̄▽ ̄)~*

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝