-
-
第十二题 尊严之战 Nep WP
-
发表于: 2022-6-8 09:57
-
程序逻辑简单，IDA直接能看出来并把前面计算的正向逻辑写出来（不过x64dbg调试会出问题，不知道这是有意还是无意）
其中mt19937代码来自https://github.com/clibs/mt19937ar
考虑爆破随机数seed
过了4h无解，程序上也基本没有干扰的地方，猜测这是个密码学问题，把已知数据提出来（2组1024byte+2组32byte）
摘了一下算法发现是一个如下的模型：
A,B为已知32*32矩阵,ans1,ans2为已知32长向量
l=[randint(0,126)]*16+[0]*16
r1=[0]*16+[randint(0,126)]*16
r2=[0]*16+[randint(0,126)]*16
err1=[randint(0,1)]*32
err2=[randint(0,1)]*32
A*l+A*r1+29*err1=ans1 mod 127
B*l+B*r2+29*err2=ans2 mod 127
求l
是个很明显的LWE问题。能想到用格规约，但是个人并不怎么会，所以硬着头皮分析数值间的关系。
我们知道格上有一种对向量的类似GCD的算法，叫做LLL，其效果是可以迭代出一些格中的较短行向量。通过这一特性我们可以构造一些结构，通过增广向量的维数构造关系，将一些在原向量空间中的长向量与增广空间中的短向量进行绑定，通过这种方式迭代长向量就可以记录一些得到短向量的操作留痕，而这种操作留痕往往就是我们需要求解的数量。
一般理想状态中，这种绑定最好是两个空间互不干扰的，也就意味着增广部分带来的向量长度相比于原向量的长度，应当忽略不计。这时迭代出的短向量的结果变化忠实记录了迭代过程，没有造成任何影响。但事实上，由于数据有界，而迭代所需的独立条件条数又总是多于实际迭代时原向量的维数，所以必然会造成多解。我们不能放任其发生，便要通过两个空间之间的干扰来进行约束，这就要我们增广出的部分虽然是小量，但并不是可忽略的，应有一定的权重。
基础知识与手法了解完，我们开始具体分析应如何构造。
首先，我们未知的有两种，一种为每个元素为【0，126】，另一种为0或1，很明显这两组造成的边界影响情况不同，所以其所在的空间圈层也不同，也就意味着，我们需要有两个不同的空间分别记录这两组不同的量。
空间划分完，我们先来看最刚性的条件：运算结果相等。
这个式子中的约束条件有有限域%127，模元M=127，注意到每一维都执行该操作，且相互独立，所以这一项应形成一个127倍的单位矩阵，由于求模的过程减少了多少个模元我们从未关注，也不必关心，所以其不需要在增广空间中留痕，自然也不需要绑定短向量。
此外就是矩阵乘，注意到矩阵乘右侧的向量，每一位都代表了对矩阵的一列的选择，数值代表了共加入了多少次，所以我们可以将矩阵转置，分别增广在空间中一个独立的小单位，这时，当某行被约减时，这个单位对应位置的小单位数量即表达了为达成这个效果，对应的原行被增加了多少次。方便起见，我们在增广空间中放置对应的一个单位矩阵。
接下来是err的处理，理论上有两种手法：
对比手法，发现第一组方案有硬伤，第二组方案有理解问题，所以先选择第二组方案。
得到草图
扣一些细节：注意到AB共用的向量l只有前16位是有值的（后16位随机数被当做了r1和r2），也就是AT与BT的高16行对应转置后对应的行向量约减过程其实是相同的，所以我们可以将AT和BT进一步拆分为上半部分ATU与BTU，和下半部分ATD和BTD，优化维数后得到新格。
接下来我们需要考虑三个空间之间的约束关系，以及部分未定参数的的选择。
前文我们提到了空间之间的约束理论，知道优先级更高的约束条件应赋予更高的权重，以减小空间间的影响。所以原空间相比而言应提供较高的权重。那么问题来了，剩下两个空间之间的关系应怎么处理？
我们知道，err的条件其实更严苛，因为他只允许有0或1两种选择，更多的选择都是不合法的；而lr对应的数据是可以充满这个有限域的。也就意味着，err所在的空间应是不受lr所在空间影响的。那么lr所在空间的数据应相比于err所在空间为小量。这里我们取$$L=M^2$$为放大倍数，保证在较大维度中的数据每单位的异动带来的数量变化都远超后边的小量整体在所有范围内的变化。
于是得到
在第三层中，注意到格中得到的结果绝对值越小越好，所以我们知道，0肯定是比1优先级更低的，这并不利于我们得到的结果符合客观。为了使二者地位均等，我们需要一种把二者映射为相反数使得其绝对值相同，$$f(x)=1-2*x$$这个映射较好，所以我们再稍作改动
这时由于lr对应的维度过小，且经历了有限域映射，结果会自然而然分布为最小剩余系，所以我们不再单独做相同的处理。
另一方面，我们要保证最后一行被使用且仅被使用一次，所以就要让其留痕平方不超过结果向量的主要影响的分维度的一个单位变化，在这里我们选取t=sqrt(L)，新开辟一列记录结果（这也是L至少为127^2的一个原因）。在结果中找最后一列为t或-t的结果就是合法解待选。
迭代后寻找最后一列绝对值为t，第三部分绝对值均为一个L的值即为合法解。这时第二部分的值即为负的lr对应值，特殊的，第二部分前16位即为输入负值%127后的结果。
原则上输入求模了127，所以要恢复后再过一遍哈希判断哪个是唯一解。
可以看到，第一组符合题意，由于经历了预处理，这时得到的第二部分即为flag值，处理后得到的flag数值为
(112, 50, 36, 13, 94, 90, 29, 14, 2, 28, 4, 101, 109, 43, 124, 76)
经过哈希之后得到
flag：7032240d5e5a1d0e021c04656d2b7c4c
（其实就是直接转化，不用再枚举hash，但提交没有kctf【……】，导致晚出了一小时orz。）
希望本篇的思路可以提供区分于整体提升明可夫斯基界的格构造方案，但以上也是笔者本人的小小尝试记录，如有错误/值得改进之处，还请各位批评指正。
#include<stdio.h>#include<string.h>#include<stdlib.h>#include "mt19937ar.h"int genNumber() {
unsigned long r = genrand_int32();
return r % 127;
}int ANS1[32]={0x37, 0x5A, 0x53, 0x4B, 0x03, 0x3C, 0x25, 0x4F, 0x38, 0x05, 0x16, 0x64, 0x59, 0x17, 0x1F, 0x0F,
0x44, 0x0B, 0x48, 0x1C, 0x27, 0x4A, 0x23, 0x63, 0x66, 0x79, 0x2A, 0x21, 0x44, 0x43, 0x65, 0x32};
int K1 = 0;
int ANS2[32]={0x5B, 0x6B, 0x75, 0x5A, 0x48, 0x6A, 0x6A, 0x23, 0x2C, 0x57, 0x14, 0x6B, 0x6B, 0x35, 0x0E, 0x64,
0x65, 0x1A, 0x23, 0x39, 0x73, 0x34, 0x02, 0x3E, 0x19, 0x06, 0x21, 0x46, 0x1C, 0x4B, 0x00, 0x61};
int K2 = 0;
int main() {
init_genrand(0x0000000091941ABB); // K1 K2
int FLAG[16]={0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF};
int s0[1024]={0};
for (int i = 0; i < 1024; i++) { //32
int a = genNumber();
s0[i]=a;
//printf("%.2x \n", a);
}
int s1[32]={0};
for (int i = 0; i < 16; i++) {
s1[i]=FLAG[i];
}
for (int i = 16; i < 32; i++) { //16
int a = genNumber();
s1[i]=a;
//printf("%.2x \n", a);
}
int s2[32]={0};
for (int i = 0; i < 32; i++) { //32 & 1
int a = genNumber() & 1;
s2[i] = a*29;
//printf("%.2x \n", a);
}
//Start Calc
int sA[32]={0};
for(int i=0;i<32;i++){
int s = 0;
for(int j=0;j<32;j++){
int temp = s1[j] * s0[32*i+j];
s+= temp%0x7f;
}
sA[i]=s;
}
for(int i=0;i<32;i++){
sA[i] = (sA[i] + s2[i]) % 0x7f;
printf("%.2x ", sA[i]);
}
puts("");
}#include<stdio.h>#include<string.h>#include<stdlib.h>#include "mt19937ar.h"int genNumber() {
unsigned long r = genrand_int32();
return r % 127;
}int ANS1[32]={0x37, 0x5A, 0x53, 0x4B, 0x03, 0x3C, 0x25, 0x4F, 0x38, 0x05, 0x16, 0x64, 0x59, 0x17, 0x1F, 0x0F,
0x44, 0x0B, 0x48, 0x1C, 0x27, 0x4A, 0x23, 0x63, 0x66, 0x79, 0x2A, 0x21, 0x44, 0x43, 0x65, 0x32};
int K1 = 0;
int ANS2[32]={0x5B, 0x6B, 0x75, 0x5A, 0x48, 0x6A, 0x6A, 0x23, 0x2C, 0x57, 0x14, 0x6B, 0x6B, 0x35, 0x0E, 0x64,
0x65, 0x1A, 0x23, 0x39, 0x73, 0x34, 0x02, 0x3E, 0x19, 0x06, 0x21, 0x46, 0x1C, 0x4B, 0x00, 0x61};
int K2 = 0;
int main() {
init_genrand(0x0000000091941ABB); // K1 K2
int FLAG[16]={0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF};
int s0[1024]={0};
for (int i = 0; i < 1024; i++) { //32
int a = genNumber();
s0[i]=a;
//printf("%.2x \n", a);
}
int s1[32]={0};
for (int i = 0; i < 16; i++) {
s1[i]=FLAG[i];
}
for (int i = 16; i < 32; i++) { //16
int a = genNumber();
s1[i]=a;
//printf("%.2x \n", a);
}
int s2[32]={0};
for (int i = 0; i < 32; i++) { //32 & 1
int a = genNumber() & 1;
s2[i] = a*29;
//printf("%.2x \n", a);
}
//Start Calc
int sA[32]={0};
for(int i=0;i<32;i++){
int s = 0;
for(int j=0;j<32;j++){
int temp = s1[j] * s0[32*i+j];
s+= temp%0x7f;
}
sA[i]=s;
}
for(int i=0;i<32;i++){
sA[i] = (sA[i] + s2[i]) % 0x7f;
printf("%.2x ", sA[i]);
}
puts("");
}[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
