A good challenge about SSP(Subset Sum Problem,a kind of knapsack) in Ant x D^3 CTF 2022 .
# ChanllengeInitial：
v = ( R 0 , R 1 , R 2 , . . . , R n − 1 ) s = ( 2 R 0 + 1 , 2 R 1 + 1 , 2 R 2 + 1 , . . . , 2 R n − 1 + 1 ) R i ∈ ( 0 , N ) , n = 100 v = (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 v = ( R 0 , R 1 , R 2 , . . . , R n − 1 ) s = ( 2 R 0 + 1 , 2 R 1 + 1 , 2 R 2 + 1 , . . . , 2 R n − 1 + 1 ) R i ∈ ( 0 , N ) , n = 1 0 0
p ∈ ( Σ ( s _ ) , 2 ⋅ Σ ( s _ ) ) ( p s : p r i m e ) e ∈ ( p / / 2 , p − 1 ) a = [ GF ( p ) ( e ⋅ s 0 ) , GF ( p ) ( e ⋅ s 1 ) , . . . , GF ( p ) ( e ⋅ s n − 1 ) ] P K = a , S K = ( 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)\\ p ∈ ( Σ ( s _ ) , 2 ⋅ Σ ( s _ ) ) ( p s : p r i m e ) e ∈ ( p / / 2 , p − 1 ) a = [ GF ( p ) ( e ⋅ s 0 ) , GF ( p ) ( e ⋅ s 1 ) , . . . , GF ( p ) ( e ⋅ s n − 1 ) ] P K = a , S K = ( s , e , p )
encrypt：
m → array(bin ( x ) ) . rjust(8k,0) m \rightarrow \text{array(bin}(x)).\text{rjust(8k,0)} m → array(bin ( x ) ) . rjust(8k,0)
r = ( R 0 , R 1 , . . . , R n − 2 ) , R i ∈ [ 0 , 1 ] r n = ( m − Σ ( r ) ) m o d 2 r = r + ( r n ) c = ( a 0 ⋅ r 0 + a 1 ⋅ r 1 + a 2 ⋅ r 2 + . . . + + a n − 1 ⋅ r n − 1 ) 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}) r = ( R 0 , R 1 , . . . , R n − 2 ) , R i ∈ [ 0 , 1 ] r n = ( m − Σ ( r ) ) m o d 2 r = r + ( r n ) c = ( a 0 ⋅ r 0 + a 1 ⋅ r 1 + a 2 ⋅ r 2 + . . . + + a n − 1 ⋅ r n − 1 )
decrypt：
m i = ( e − 1 c i m o d p ) m o d 2 m_i = (e^{-1}c_i\mod p)\mod 2 m i = ( e − 1 c i m o d p ) m o d 2
# Analysis发现该题是一个 Knapsack [1] 问题，但不能用普通的的背包出来。
Q1 : Why can't use regularly method of knapsack to attack it?
A1 :
如果直接在 encrypt 上面进行背包的话，会发现他没法背包出来。方案设计者表明了该方案针对于常规攻击是相对安全的。
为了避免弱密钥，推荐 e ∈ [ P / / 2 , P − 1 ] e\in[P//2,P-1] e ∈ [ P / / 2 , P − 1 ]
为了抵抗低密度的攻击，选择 n > log 2 N + log 2 n + 1 n>\log_2{N}+\log_2{n}+1 n > log 2 N + log 2 n + 1
这道题目是 Yasuyuki Murakami 等人的设计 knapsack 公钥密码系统 [3] ，有一篇 paper:《Equivalent key attack against a public-key cryptosystem based on subset sum problem》[2] 讲解针对该题的攻击内容的。
其中说明如果想要恢复 子集和问题 (Subset Sum Problem) 的等价密钥 s 1 , s 2 , . . . , s n , P , e s_1,s_2,...,s_n,P,e s 1 , s 2 , . . . , s n , P , e
a i = e s i m o d P , i ∈ [ 1 , n ] a_i=es_i\mod P,i \in[1,n] a i = e s i m o d P , i ∈ [ 1 , n ]
P 是一个素数（或者用 gcd (P,e) = 1），且满足 P > Σ i = 1 n s i P>\Sigma^n_{i=1}s_i P > Σ i = 1 n s i
s 1 , s 2 , . . . , s n s_1,s_2,...,s_n s 1 , s 2 , . . . , s n
可知 a i ≡ e ⋅ s i m o d P ⇒ a i ≡ e ⋅ s i + k i ⋅ P a_i\equiv e\cdot s_i\mod P \Rightarrow a_i\equiv e\cdot s_i+k_i \cdot P a i ≡ e ⋅ s i m o d P ⇒ a i ≡ e ⋅ s i + k i ⋅ P
a = ( a 1 a 2 . . . a n ) , s = ( s 1 s 2 . . . s n ) , k = ( k 1 k 2 . . . k n ) a = e ⋅ s + P ⋅ k \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} a = ⎝ ⎜ ⎜ ⎜ ⎛ a 1 a 2 . . . a n ⎠ ⎟ ⎟ ⎟ ⎞ , s = ⎝ ⎜ ⎜ ⎜ ⎛ s 1 s 2 . . . s n ⎠ ⎟ ⎟ ⎟ ⎞ , k = ⎝ ⎜ ⎜ ⎜ ⎛ k 1 k 2 . . . k n ⎠ ⎟ ⎟ ⎟ ⎞ a = e ⋅ s + P ⋅ k
存在一个 比较短的向量 t 满足
⟨ a , t ⟩ = e ⟨ s , t ⟩ + P ⟨ k , t ⟩ = 0 \lang\bold{a},\bold{t}\rang = e \lang\bold{s},\bold{t}\rang + P \lang\bold{k},\bold{t}\rang = 0 ⟨ a , t ⟩ = e ⟨ s , t ⟩ + P ⟨ k , t ⟩ = 0
如果该向量是足够短的话，需要满足
∣ ∣ ⟨ s , t ⟩ ∣ ∣ < P ⇒ ⟨ s , 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 , t ⟩ ∣ ∣ < P ⇒ ⟨ s , t ⟩ = 0 , ⟨ k , t ⟩ = 0
因此 向量 s 和向量 k 属于 一个 orthogonal lattice 的 子格。接着可以找到满足上述的最后两个条件的等价私钥。(ps: 事实上，P 并不是严格意义需要去满足他是一个素数，只需要与 e 互素即可)
orthogonal lattice（正交格）[4]:
给出一个格 L ⊆ Z m \mathscr{L}\subseteq \mathbb{Z}^m L ⊆ Z m L \mathscr{L} L Q m \mathbb{Q}^m Q m E E E F = E ⊥ F=E^\perp F = E ⊥ L ⊥ = { v ∈ Z m ∣ u ∈ L , ⟨ u , v ⟩ = 0 } \mathscr{L}^\perp=\{\bold{v}\in \mathbb{Z}^m|\bold{u\in \mathscr{L},\lang\bold{u},\bold{v}\rang = 0} \} L ⊥ = { v ∈ Z m ∣ u ∈ L , ⟨ u , v ⟩ = 0 }
引理：对于任意的格L ⊆ Z m \mathscr{L}\subseteq \mathbb{Z}^m L ⊆ Z m r a n k ( L ) + r a n k ( L ⊥ ) = m rank(\mathscr{L})+rank(\mathscr{L}^\perp) = m r a n k ( L ) + r a n k ( L ⊥ ) = m
# Details of Attack定义一个格 L 1 = { t ∈ L ⊥ ( a ) ∣ ⟨ s , t ⟩ = 0 } \mathscr{L}_1=\{t\in \mathscr{L}^\perp(\bold{a})|\lang\bold{s},\bold{t}\rang=0\} L 1 = { t ∈ L ⊥ ( a ) ∣ ⟨ s , t ⟩ = 0 }
Theorem : 定义格 L 1 = { t ∈ L ⊥ ( a ) ∣ ⟨ s , t ⟩ = 0 } \mathscr{L}_1=\{t\in \mathscr{L}^\perp(\bold{a})|\lang\bold{s},\bold{t}\rang=0\} L 1 = { t ∈ L ⊥ ( a ) ∣ ⟨ s , t ⟩ = 0 } ⟨ s , t 0 ⟩ ≠ 0 \lang\bold{s},\bold{t_0}\rang\neq 0 ⟨ s , t 0 ⟩ = 0 t 0 ∈ L ⊥ ( a ) \bold{t_0} \in \mathscr{L}^\perp(\bold{a}) t 0 ∈ L ⊥ ( a ) L ⊥ ( a ) = L ( t 0 ) ⊕ L 1 \mathscr{L}^\perp(\bold{a})=\mathscr{L}(\bold{t_0})\oplus \mathscr{L}_1 L ⊥ ( a ) = L ( t 0 ) ⊕ L 1
使用 Algorithm 1，可以计算 L ⊥ ( a ) \mathscr{L}^\perp (\bold{a}) L ⊥ ( a ) L ( t 1 , t 2 , … , t n − 1 ) \mathscr{L}(\bold{t_1,t_2,\dots,t_{n-1}}) L ( t 1 , t 2 , … , t n − 1 ) t 1 , t 2 , … , t n − 1 \bold{t_1,t_2,\dots,t_{n-1}} t 1 , t 2 , … , t n − 1 ⟨ s , t ⟩ ≠ 0 \lang\bold{s},\bold{t}\rang\neq 0 ⟨ s , t ⟩ = 0
假设每个 s i s_i s i P > n N P>nN P > n N ∣ ∣ s ∣ ∣ < 2 n N ||\bold{s}||<2\sqrt{n}N ∣ ∣ s ∣ ∣ < 2 n N ∣ ∣ t ∣ ∣ < n / 2 ||\bold{t}||<\sqrt{n}/2 ∣ ∣ t ∣ ∣ < n / 2 ∣ ⟨ s , t ⟩ ∣ ≤ ∣ ∣ s ∣ ∣ ⋅ ∣ ∣ t ∣ ∣ ≤ P |\lang\bold{s},\bold{t}\rang|\leq||\bold{s}||\cdot||\bold{t}||\leq P ∣ ⟨ s , t ⟩ ∣ ≤ ∣ ∣ s ∣ ∣ ⋅ ∣ ∣ t ∣ ∣ ≤ P n / 2 ≤ ∣ ∣ t 0 ∣ ∣ \sqrt{n}/2\leq||\bold{t_0}|| n / 2 ≤ ∣ ∣ t 0 ∣ ∣ t 1 , t 2 , … , t n − 1 \bold{t_1,t_2,\dots,t_{n-1}} t 1 , t 2 , … , t n − 1 t n − 1 \bold{t_{n-1}} t n − 1 t 0 \bold{t_0} t 0
再用一次 Algorithm 1，就可以计算得到 L 1 ⊥ \mathscr{L}_1^\perp L 1 ⊥ L ( u 1 , u 2 ) \mathscr{L}(\bold{u_1},\bold{u_2}) L ( u 1 , u 2 ) t n − 1 \bold{t_{n-1}} t n − 1 t 0 \bold{t_0} t 0 ⟨ s , t i ⟩ = 0 , i ∈ [ 1 , n − 2 ] \lang\bold{s},\bold{t_i}\rang=0 ,i\in[1,n-2] ⟨ s , t i ⟩ = 0 , i ∈ [ 1 , n − 2 ] ⟨ a , t ⟩ = e ⟨ s , t ⟩ + P ⟨ k , t ⟩ = 0 \lang\bold{a},\bold{t}\rang = e \lang\bold{s},\bold{t}\rang + P \lang\bold{k},\bold{t}\rang = 0 ⟨ a , t ⟩ = e ⟨ s , t ⟩ + P ⟨ k , t ⟩ = 0 ⟨ k , t i ⟩ = 0 \lang\bold{k},\bold{t_i}\rang=0 ⟨ k , t i ⟩ = 0 { s , k } ∈ L 1 ⊥ \{\bold{s},\bold{k}\} \in \mathscr{L}_1^{\perp} { s , k } ∈ L 1 ⊥
接着去枚举搜寻等价私钥
s = x 1 u 1 + x 2 u 2 k = y 1 u 1 + y 2 u 2 x i , y i ∈ Z , 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 s = x 1 u 1 + x 2 u 2 k = y 1 u 1 + y 2 u 2 x i , y i ∈ Z , i = 1 , 2
在寻找的过程中需要满足 Analysis 中的最后两条，可以以一个比较高的概率去得到一组等价私钥。
Q2 : How to enumerate the xi,yi ?
A1 :
根据官方的 wp，我们可以得知
s = x 1 u 1 + x 2 u 2 k = y 1 u 1 + y 2 u 2 a = z 1 u 1 + z 2 u 2 x i , y i ∈ Z , 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 = x 1 u 1 + x 2 u 2 k = y 1 u 1 + y 2 u 2 a = z 1 u 1 + z 2 u 2 x i , y i ∈ Z , i = 1 , 2
并且根据 s \bold{s} s x 1 , x 2 x_1,x_2 x 1 , x 2 x 1 = 2 k + G F ( 2 ) ( x 1 ) , x 2 = 2 h + G F ( 2 ) ( x 2 ) x_1 = 2k + GF(2)(x_1),x_2 = 2h + GF(2)(x_2) x 1 = 2 k + G F ( 2 ) ( x 1 ) , x 2 = 2 h + G F ( 2 ) ( x 2 ) s \bold{s} s
( e P ) T ⋅ ( x 1 x 2 y 1 y 2 ) = ( z 1 z 2 ) \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) ( e P ) T ⋅ ( x 1 y 1 x 2 y 2 ) = ( z 1 z 2 )
我们可以得知 P > e >> |a| >> zi，接着就可以得知 ∣ x 1 x 2 ∣ − ∣ y 1 y 2 ∣ |\frac{x_1}{x_2}|-|\frac{y_1}{y_2}| ∣ x 2 x 1 ∣ − ∣ y 2 y 1 ∣
那么就可以用连分数的办法得到 y1,y2。
A2 :
也可以直接爆破 x1,y1,x2,y2，但运气不好就可能比较难跑出来吧？
完整的算法过程在 Attach 中描述
# Attach# Algorithm 1. Find out the orthogonal lattice [4]:INPUT - 格 L \mathscr{L} L ( b 1 , b 2 , . . . , b k ) (\bold{b_1},\bold{b_2},...,\bold{b_k}) ( b 1 , b 2 , . . . , b k )
OUTPUT - 格 L ⊥ \mathscr{L}^\perp L ⊥ ( y 1 , y 2 , . . . , y n − k ) (\bold{y_1},\bold{y_2},...,\bold{y_{n-k}}) ( y 1 , y 2 , . . . , y n − k )
挑选一个 g = ⌈ 2 ( n − 1 / 2 ) + ( ( n − k ) ( n − k − 1 ) / 4 ) Π j = 1 k ∣ ∣ b k ∣ ∣ ⌉ g = \lceil 2^{(n-1/2)+((n-k)(n-k-1)/4)}\Pi^{k}_{j=1}||\bold{b_k}|| \rceil g = ⌈ 2 ( n − 1 / 2 ) + ( ( n − k ) ( n − k − 1 ) / 4 ) Π j = 1 k ∣ ∣ b k ∣ ∣ ⌉
生成一个( n + k ) × n (n+k)\times n ( n + k ) × n B \mathscr{B} B
B = ( g × b 1 , 1 g × b 1 , 2 … g × b 1 , n g × b 2 , 1 g × b 2 , 2 … g × b 2 , n ⋮ ⋮ ⋱ ⋮ g × b k , 1 g × b k , 2 … g × b k , n 1 0 … 0 0 1 ⋱ 0 ⋮ ⋮ ⋱ ⋮ 0 0 … 1 ) \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) B = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ g × b 1 , 1 g × b 2 , 1 ⋮ g × b k , 1 1 0 ⋮ 0 g × b 1 , 2 g × b 2 , 2 ⋮ g × b k , 2 0 1 ⋮ 0 … … ⋱ … … ⋱ ⋱ … g × b 1 , n g × b 2 , n ⋮ g × b k , n 0 0 ⋮ 1 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞
对 B \mathscr{B} B ( x 1 , x 2 , … , x n ) (\bold{x_1},\bold{x_2},\dots,\bold{x_n}) ( x 1 , x 2 , … , x n )
输出向量 ( y 1 , y 2 , . . . , y n − k ) (\bold{y_1},\bold{y_2},...,\bold{y_{n-k}}) ( y 1 , y 2 , . . . , y n − k ) y j ∈ Z n , 1 ≤ j ≤ n − k \bold{y_j}\in \mathbb{Z}^n,1\leq j\leq n-k y j ∈ Z n , 1 ≤ j ≤ n − k
# Algorithm 2. Recover the equivalent private key [2]INPUT - 公钥 a \bold{a} a
OUTPUT - 私钥 s , P , e \bold{s},P,e s , P , e
计算 a \bold{a} a L ⊥ ( a ) = L ( t 1 , t 2 , … , t n − 1 ) \mathscr{L}^\perp (\bold{a}) = \mathscr{L}(\bold{t_1,t_2,\dots,t_{n-1}}) L ⊥ ( a ) = L ( t 1 , t 2 , … , t n − 1 )
取 L 1 = L ( t 1 , t 2 , … , t n − 2 ) \mathscr{L}_1 = \mathscr{L}(t_1,t_2,\dots,t_{n-2}) L 1 = L ( t 1 , t 2 , … , t n − 2 ) L 1 ⊥ = L ( u 1 , u 2 ) \mathscr{L}_1^\perp = \mathscr{L}(\bold{u_1},\bold{u_2}) L 1 ⊥ = L ( u 1 , u 2 )
令 s = x 1 u 1 + x 2 u 2 , k = y 1 u 1 + y 2 u 2 : x i , y i ∈ Z , 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. s = x 1 u 1 + x 2 u 2 , k = y 1 u 1 + y 2 u 2 : x i , y i ∈ Z , i = 1 , 2 .
枚举空间∣ x i ∣ , ∣ y i ∣ < N |xi|,|yi|<\sqrt N ∣ x i ∣ , ∣ y i ∣ < N
对每个集合 ∣ x i ∣ , ∣ y i ∣ : i = 1 , 2 |xi| ,|yi|:i=1,2 ∣ x i ∣ , ∣ y i ∣ : i = 1 , 2 a = e s + P k \bold{a} = e\bold{s}+ P\bold{k} a = e s + P k
用下面两条情况筛选 每个序列 s 1 , s 2 , … , s n , P , e s_1,s_2,\dots,s_n,P,e s 1 , s 2 , … , s n , P , e
gcd ( P , e ) = 1 , P > Σ i = 1 n s i \text{gcd}(P,e)=1 ,P>\Sigma_{i=1}^ns_i gcd ( P , e ) = 1 , P > Σ i = 1 n s i s 1 , s 2 , … , s n s_1,s_2,\dots,s_n s 1 , s 2 , … , s n 剩下来的每一组 s , P , e \bold{s},P,e 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
