type
status
date
summary
password
category
slug
icon
CTF中的LFSR类题目
题型：给出反馈函数和输出序列，反推出初始状态
2018 CISCN 线上赛 oldstreamgame
题目
题解
0xffffffff -->32位的常数 $0b11111111111111111111111111111111$ 按位与运算（同1才为1）与$0xffffffff$做按与运算，结果为原数低32位，
R（flag）是32位的初始状态output = (R << 1) & 0xffffffff 把R左移一位后低32位（即抹去R的最高位）i=(R&mask)&0xffffffff#把传入的R和mask做按位与运算，运算结果取低32位，将该值赋给i变量。
i&1的作用是从低到高取出每一位
lastbit^=(i&1)说明Lastbit是i从低位异或到高位的结结果，如果i中有奇数个1，结果1；偶数个1，结果为0。output^=lastbit将output变量的最后一位设置成lastbit变量的值。整体流程:
每轮产生8个lastbit,lastbit取决于r按位与上mask后结果中1的个数，因为按位与性质，都为1时才为1,mask已知,
只需考虑mask中是1的位置（从右边数
每次产生lastbit后，R值更新为output(=R去掉最高位第32位是lastbit的值)
每轮产生一个结果，即8个lastbit异或的结果
WP
2018 强网杯 线上赛 streamgame1
题目
题解
方法一
和第一题一样
方法二
因为flag不是很长（19bit)，所以可以爆破
WP
2018 强网杯 线上赛 streamgame2
题目
题解
同1，2，len(flag)==27
WP
2019 0CTF/TCTF 线上赛 zer0lfsr
题目
题解
方法一：Fast Correlation Attacks
Fast Correlation Attacks（快速相关攻击）
Correlation Attacks（相关攻击）
利用单个LFSR的输出序列和combine之后的LFSR的输出序列之间具有的一定的相关性这一特点，来还原LFSR的初始状态
两种重要的快速相关攻击的手法:Algorithm A和Algorithm B
使用该攻击的满足条件：单个LFSR的输出序列和combine之后的LFSR的输出序列之间的相关性大于0.53\
例子：
x1 | x2 | x3 | combine(x1,x2,x3) |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
当x1=0时，会对应四个result（即
combine(x1,x2,x3)）值，其中3个result值为0，一个为1，即x1和result相同的概率为0.75。同理，x2和x3也满足这一规律，这样一来我们就找到了一个很关键的要素，那就是单个x的值和combine之后的值相同的概率有0.75。Meier-Staffelbach模型
两种重要的快速相关攻击的手法:Algorithm A和Algorithm B，都默认建立在该模型之下。
两种算法的比较：
1.算法A:
优点：错误率接近0.75时攻击效果显著。
缺点：当抽头数量较多时，该攻击将逐渐退化为穷举攻击。
2.算法B:
优点：错误率接近0.5时攻击效果显著。
缺点：该攻击需要进行大量的双精度计算，计算量较大
脚本：
方法二：z3约束求解
z3约约束求解的核心是列方程和解方程，如果能解，z3就会给你一组解（注意：如果方程有多组解，z3只会给你其中的一组解，所以这组解虽然满足题意但未必是正确答案，这个时候我们可以尝试能否继续为方程添加约束条件，进一步限制解的范围，从而获得我们预期的一组解）
Solver添加方程的时候，只添加了200个方程，按理来讲，我们应该有
len(outputs)个方程，为什么只添加200个呢？实际上在这里200并不是一个精确数字，而是一个大概的数字，意思是当添加够200个方程的时候，得到的解就已经固定了，即我们需要的那组解，我们把它改到300，得到的还是这组解，所以就不用继续添加没有必要的方程了。那么既然我们说反正都一样，我直接给他添加len(outputs)个方程，不是更省事吗，也不用去关它多少个方程之后解就固定了，其实大家可以动手去试一下，这样虽然理论上是一样的，但是实际操作的时候计算机反而解不出来，原因就是约束的方程过多了，计算机反而解不出来了，因此我们需要手动测试一下，找到一个合适的数值，来使得我们的脚本既能求出我们希望的一组解，又能让计算机正常跑出来。wp
解出init1,init2,init3
2018 强网杯 线上赛 streamgame3
题目
Fast Correlation Attacks（快速相关攻击）