VNCTF 2023 Crypto 赛道的所有题解,包含了特殊 Sbox 下 AES 的差分分析、DLPwAI 等问题,题目质量很好,记录一下。
crypto-sign-in-1
源码
源码存档于:source link
分析
求ecc上的dlp,我们可以选择 来确定 ecc 曲线的 中的 值,由于 q 不太大,随机选择 ,多试几次,每次分解 ecc 的阶 ,如果其所有素因子不大于 ,即光滑阶的情况下,就可以快速求解 ECDLP 问题。这题和 2022 ASISCTF 中 Desired Curve 考点类似。
EXP
Sage EXP
1 | from pwn import * |
crypto-sign-in-2
源码
源码存档于:source link
分析
sbox 放 sage 简单分析一下:
1 | # sage 9.5 |
发现,给定差分输入,其对应的差分输入是固定的,也就是该sbox对差分而言可逆。因此,在AES的框架内,使用该sbox,则 、、、 都是差分可逆的,可以直接写逆,根据已知明文 noise 恢复 flag:算noise密文和flag密文的差分,恢复出noise和flag的明文差分,然后和noise异或就得到flag的明文。
实际上,AES 的所有操作中只有 是包含非线性运算的,而这题的 Sbox 是线性的,那么 AES 整个过程就是线性的,而线性的密码非常脆弱,参考 Hill Cipher 的例子,因此 Sbox 在对称加密体制中非常重要, Sbox 不能是线性或者仿射的,也不能拥有可分析(高概率)的差分特征。
回到题目本身,noise是32字节,利用恢复的差分输入就可以恢复前面32字节,然后利用 cbc 模式的trick推算出不同位置的输入差分(明文与前一个密文或者 IV 异或,而前一个密文是已知的),这样就可以恢复出任意分组的字节。具体地:EXP中用到了noise第二个分组和flag其他分组的差分来恢复所有明文。
EXP
Python EXP
1 | import numpy as np |
crypto-sign-in-3
源码
源码存档于:source link
分析
整个函数过程给出了四组方程:
根据提示,我们知道 secret 不超过 392 比特,即 x0 是小根,消元,得到 x0 的方程求coppersmith小根即可。
EXP
Sage EXP
1 | from Crypto.Util.number import bytes_to_long,getPrime |
crypto-sign-in-4
源码
源码存档于:source link
分析
该类问题 的一个算法
具体细节推导参考论文:
- https://eprint.iacr.org/2008/300.pdf
- https://www.jstage.jst.go.jp/article/imt/6/4/6_4_1175/_pdf/-char/en
实现上述类似两次bsgs的算法即可,显然 时时间复杂度最小,大概 时间复杂度。
EXP
Sage EXP
1 | from tqdm import tqdm |