密码学

日常记录一些密码学知识

密码学

gid:1phan r3kapij

古典加密

单表替换加密

介绍

一种映射

p –> C

明文都在密文空间找到映射

破解

密钥空间过小时:爆破

给的样本足够长时:http://quipqiup.com

凯撒密码

明文字母表 右移 N 位

密钥为 偏移位数

最多26位

攻击方式:直接爆破

凯撒加密变种

凯撒密码空间可以从26 变成 整个ASCII 范围

攻击方式:

1.直接爆破

2.分析每位间的瀚明距离

密文,从头到尾距离,来缩小密钥空间

Atbash Cipher

A -> Z 对应

B -> Y 对应

以此类推

CTF 解题思路,查出加密方式,搜github脚本,抢一血

棋盘加密
仿射加密

E(x) = a*x + b mod 26

gcd(a,26) == 1

D(c) = a^(-1)*c - b

将字母转换为数字,通过数学运算进行加密

例:

解密:

逆元:

A* b = 1 mod 26

A,b互为逆元

2 * 3 mod 5 = 1

2 ^-1 = 3

使用拓展欧几里得算法,算出逆元

E(x) = a*x + b mod 26

密文 - 7 * 3d的逆元

E(x) - 7 * 3的逆元

拓展欧几里得算法

辗转相除法

由gcd(6,8) == 2得

a 6 + b 8 = 2

a x + b y = gcd(x,y) = 1

只有当两个数字互素的时候

才有逆元

拓展欧几里得算法就是计算 a 和 b的算法

扩展欧几里得算法就是辗转相除法扩展了两个向量

算逆元

pycrypto,

1
from crypto.util.number import inv

E(x) = a*x + b mod 26

x = (y - b) a 的 逆元 mod 26

(逆元)

欧拉函数

fi(p) = (p - 1) p是素数

对仿射密码攻击

爆破 fi(26) = fi(2) fi(13) = 12 26 = 312

已知算法求解(例WCTF某题)

对于单表替换,用字频分析来做

对于仿射加密,直接用仿射加密的脚本来爆破

多表替换加密

把明文 映射到很多个密文空间

怎么样多表有意义?

Vigenero

横是明文

竖着是密钥

攻击vigenere

卡西斯基实验

一定间隔的相同字符串,被加密成相同密文

密钥重复,泄露密钥长度

弗里德曼实验:

凯撒加密改变所有字母的概率平方和

思路:

利用卡西斯基实验,列出因子表,根据表,利用弗里德曼实验算密钥平方和和字母平方和

如果是纯粹vigenere,直接google 搜索攻击网站

思路来应用变种

例题:
Seccon2017

vigenere3d

特性:用两个密钥加密和用一个密钥加密结果是一样的

如果两次应用的密钥长度不一致,

Playfair

将明文中的每两个字母拆出来,构建

构建5 * 5 矩阵 把重复删掉

攻击:

顺序相仿的两个字母会泄露信息

AB BA

做题直接搜脚本

置换

古典密码以逆向题来出现

用C语言编写,用作逆向题目

CTF题中,以.py形式给出的,一般为公钥算法和非对称算法

置换加密,明文中出线的顺序给打乱

栅栏加密

密钥是分组数量

攻击:爆破

Hill 希尔密码

一个可逆的的矩阵

解密:算下密钥矩阵的幂

块密码,加密单位为 CAT ,三个字母一块

明文中的一个字母被改变,密文中的所有字母都会被改变

攻击办法:

k = c * p的幂

培根加密

一句话,加粗与不加粗相间,可以当作隐写似的培根

加粗代表A 不加粗是B

BrainFuck加密

控制台

JSFuck

js的一种书写形式,控制台即可

舞动的小人

google 以图搜图

猪圈密码

百度搜即可

变种:

圣堂武士

夏多

。。。。。

以图搜图,搜变种

算法求逆

1.识别它

2.攻破它(在前人的肩膀上)搜脚本

怎么识别

http://t.cn/ReRqy17

基础密码可看

base64编码

把三个加密的字符,转换为四个加密的字符

做隐写,

flag有可能在base位数里面

base32 把长度为8的字节,映射到

base16

其他算法

算法求解

高级密码学

流加密

OTP – 完善保密性
明文和密钥一样长
绝对安全
明文和密钥(随机比特流)异或在一起,生成随机比特流
I = -ln(p)
把信息量和概率联系在一起,信息论

信息不会凭空产生也不会凭空消失

  • 安全
  • 密钥过长
  • 密钥足够短
  • 不是信息论安全
    OPT VS Pseudorandom generator 伪随机生成器

伪随机数生成器
glibc rand

1
2
3
4
seeding_stage()
for (i = 344;i<MAX ; i++){
r[i]
}

LFSR(线性反馈移位寄存器)
CTF应用,给密钥流,问密钥流下一个比特是什么

只有描述为本元多项式的LFSR,才为

Shrinking Generator

利用侧信道分析
拆成两个LFSR的问题

SNOW3G
手机SIM卡,加密3G信号的算法

流密码一般用于手机流量加密

ps:多项式,根据多项式画出LFSR流程图

LFSR已知明文明文攻击

根据公式画流程图

101001100010 解题

LFSR是有可能反推回去,所以需要一个非线性函数

ZUC

块加密

将明文块用key加密成密文块,解密为逆过程

混淆与扩散

迭代分组密码

大部分的密码都是迭代分组密码

是DES和AES算法的核心结构

轮函数构造

des加密。

1
2
Li + 1 = Ri
Ri + 1 = Li

des加密

轮函数 + 子密钥生成器

des弱密钥:使用密钥key,对明文加密,加密后的结果还是明文本身

des的密钥有56位,看起来64位,在第8N位,设置校验位

DES的s盒,接收6个bit的输入,提供4个bit的输出

s盒是不可逆的,一个输入,对应多个输出

出题方向:

Feistel challenge

给Feistel网络写解密函数

没有用key再执行依次,Feistel 网络里面

用了key,将key放在Feistel网络里面

3DES加密

$$
C = Ek3(Dk2(Ek1(P)))
$$

$$
P = Dk1(Ek2(Dk3(C)))
$$

2DES 生日悖论

中间相遇攻击
P – K1 –> M –k2 –> C
$$
C = Ek2(Ek1(P))
$$

AES

AES是可逆的,典型的块加密,
AES-> S盒->循环移位->列混淆->addRoundKey
前九轮
最后一轮不包括列混淆运算

AES只需要在逆向的时候,能识别出来就可以,DES要多关注一些

分组密码加密模式

ECB

ECB是一种没有加密模式的加密模式,明文用密钥做出加密,分析出密文

加密模式存在的意义

ECB不能隐藏明文中的隐藏信息,图像盒大规模的数据中,不能应用ECB

CBC(PCBC)

和ECB的区别,引入和前项密文做异或的操作,第一个引用初始向量和明文做异或
要求:

  • IV不可预测
  • 必须是完整的
  • 两步错误传播特性
  • 明文统计特性的隐写
  • 并行解密
    针对CBC的攻击
    字节翻转攻击,对密文进行篡改,通过影响上一段的密文,影响下一段的明文,成自己想要的样子
    C1 xor M = P2
    C1 xor M xor P2 xor P’ = P’

Cookie 生成
最初采用md5 用户名,后来
1.MAC
2.加密

向服务器,请求 用户名 ,服务器返回des cbc加密后的用户名,当作cookie

块[IV][C1][C2]

想要把P1由Wang改为admin,提交[iv xor P1 xor S] [c2]
wang555
占两个块
P1:wang P2:555

思路:舍掉C2 将IV xor P1 xor ‘admin’ 异或在一起

升级版:
要求明文有一定格式,占用复数个块,不仅在于用户名,还在于位置
Location=XXXX&name=wang5;要求密文解出明文满足格式
总长度大于两个块
Location=xxx占用一个块,明文占用一个块

攻击方法:
CBC反转攻击存在问题,两步错误传输,修改之前密文,可以控制下一个块,当前块修改为乱码
其中Location的地址可以是乱码,因为服务器只校对格式,所以location可以为乱码,可以通过修改乱码对应的块的对应下一个块

写成三个块的格式
p1 location=xxx
p2 xxxxxxxx
p3 ;name=wang5;
可以篡改p2对应的密文块,可以修改下一块对应的明文

可以直接篡改c2,p2会是乱码,P3会成为理想的格式

分析网站数据结构,如果考虑CBC攻击,考虑是否能被压缩成一个块,就能直接修改IV
如果不能压缩成一个块,则查看可以是乱码的位置。

Padding Oracle Attack

Padding Oracle 查询器,应答器

询问密文解密后的明文,通过服务器返回的信息对错,来实现一次攻击

如果最后一个块没有实际一个块长度,采用补齐的方式,其中一种方式为PKCS#5,一个块差5个字节够一个快,补五个0x05,差两个补两个0x02,如果正好补8个0x08

当服务器解密P3时按照后面0x0N 对应取出N个块,当被C3篡改时,例0x03 0x02 时,服务器会告诉Padding不对,此时可以进行Padding Oracle Attack ,刚开始并不知道正确与否,修改p2最后一个字节,P3变成乱码,P3修改后!=P3,还能通过Padding的校验,当最后一个块被改成0x01的时候,可以实现,最多要穷举1个字节的空间,也就是256次,就可以知道,被修改后P3最后一个字节是01,把b初试字节拿出来 b xor i i取值 00-ff,当padding时,说明,
B xor i xor P3 = 01 可以求出 P3的最后一个字节,可以爆破第二个字节,把要爆破第二个字节,首先把最后一个块的最后一个字节为02,只需要修改i,i = i’ b xor P3 L = 02

c xor i xor p3 S = 0x02
可以知道p3最后一个字节,穷举了256 2次
在一个des的块中,8
256 次,就能恢复出一个DES的块

解密完倒数第一个块中,要解密倒数第二个块的明文,把原来倒数第二个块,变成倒数第一个块,将原来倒数第一个块割裂掉,

通过修改原来倒数第三个字符串的最后一个值,修改倒数第二个块的最后一位为0x01

依次类推,构成 Padding Oracle Attack

只要服务器告诉padding,就可以构成解密密文

服务器做用户校验,用
用到 padding attack的地方
cbc(key||name),拿到加密key,就可以对任意用户名加密,就可以任意用户登陆

基础,服务器告诉对不对
进阶,服务器返回rgb流量包,500 里面夹杂着 200,可能为oracle padding attack
如果padding 不对返回 500 ,正确返回 200的包

分析大的流量包,百度搜搜,python 处理 wireshark流量包

其他考察,侧信道攻击结合,

有可能防止padding 攻击,对返回的包沉默掉,不返回结果,但是有可能去解密最后一个块,解密成功在解密前一个块,如果没有设置cbc并行解密,如果密文足够长,在padding 错误,立马停止运算,正确可能会计算1s,通过返回时间,来判断padding包正确与否

PCBC

和CBC大部分一样,但是加密时,把明文和密文都异或进来,是一种尝试防止CBC翻转攻击策略,缺陷速度特别慢,每一个块解密,明文和密文相互依赖,无法并行加解密

块加密,尝试变成流加密

CFB

叫做伪流加密

CFB也可以被翻转攻击,思路一样,可以并行解密,不需要padding,相当于明文异或密钥流

OFB

问题,存在循环,有不可忽视的概率被加密回来的。
有预先预测的可能,容易泄露信息

优点:可以预先计算 key
缺点:不能加解密并行

CTR

加密模式之间的比较

总结
以上都不能在生产中应用,如果有,作者暗示有漏洞
生产中应用
GCM 和 CCM
这两种加了完整性校验的

避免padding 攻击

密文偷取,第二个快不够长,才够凑齐第二个快,可以不许padding,从第一个块去tail,补齐,第二个够一个块,把割喉的head放在后面,
先解密倒数第二个快,补齐后再解密,Tail的前半部分,使用

CBC

密文偷取,和ECB密文偷取一致,将最后一个不够长的块用0填充,

解密反过来,先解密倒数第二快,时前面的明文块,和后面的密文块,把红色密文块,补齐到后一部分,解密就ok,看最后一个块差多少满一个块,从前面截出来,红色,ok

密文偷取是防止padding攻击的方案,并不是一种攻击方式

迭代分组密码

公钥算法(RSA)

公钥算法有两个密钥,一个加密,一个解密

加密分为,对称加密和非对称加密(公钥算法)

对数,
y = log x

在y = logx mod p 情况下,算离散对数是困难的

安全性来源,

大数分解:
已知
p*q = N

知道N,分解出 p 和 q

最多只需要尝试根号n 次

RSA

根据一定条件选择大质数 p 和 q ,计算 N = p * q
根据欧拉函数,fi(N) = fi(p ) * fi()

加密过程 ENC&DEC

C = pow(M,e,N)
M = pow(C,d,N)

a fi(n) 次方 = 1 mod N

RSA 中 N的长度小于512bit 个人pc就能攻破,N的长度大于2048长度,被认为是安全的,现在各种证书是4096bit

快速幂算法

1
2
3
4
5
6
7
8
def fastExp(m,d,N):
ret = 1
while d > 0:
if d & 1:
ret = ret * m % N
d = d //2
m = pow (m,2,N)
return ret

中国剩余定理加速法,加速RSA解密的过程

中国剩余定理

简单理解于解题的一种算法,CTF中遇到,利用库去解密,或者使维基百科,一行一行摘成python

RSA侧信道攻击(功率分析)

快速幂算法情况下

中国剩余定理情况下

CTF 中的RSA

  • pem 格式 证书

根据 opssl 来恢复

  • pcap流量包 广播攻击,发了很多流量,里面有密文 用 python 中的 scapy
  • nc 交互
  • 直接贴出N = ****; e = ******

RSA算法使用中较容易犯的错误,出题思路

  • 过小的N
  • 过小的d
  • 过小的e
  • 重复使用 p , q
  • 不恰当的p q 特征,差的绝对值太小,或者差的绝对值太大
  • 广播同一段明文的不同密文
  • 不同的e 共用n(共模攻击)
  • 提供 padding Oracle

过小的N

过小的N容易被直接分解

onilne DB:http://factordb.com

本地:RSATool,yafu

RSATool 支持 RSA本地分解

yafu 支持windows

过小的e

pwn(m,e) < N(e == 3)

Cipher Text = pwn(m,e) + K * N (e == 3)

m ^e = m ^e + K * n

如果e,太小,就进行运算,

广播攻击

C1 = pow(m,e,N1)

C2 = pwn(m,e,N2)

c = pow(m,e,N3)

如果

M^e < N 1 N 2 N 3

可以用中国剩余定理进行攻击

过小的d

rsa-wiener-attk

https://giuhub.com/pablocelayes/rsa-wiener-attack

如何识别d非常小

先生成 不大的 e 计算 e的逆 = d

如果遇到了题目,rsa加密的密钥,和 e 差不多长,或者特别长,可以采用这种方法

重复使用PQ

N1 = p1 * q1

N2 = p1 * q2

gcd(N1,N2) = p1

不恰当的pq特征

如果p,q相差特别小,或者p,q差别太大的时候,Fermat方法& Pollard rho 方法

使用Yafu

共模攻击

使用拓展欧几里得算法

e1 r1 + e2 r3 = 1

拓展欧几里得算法,可以用pycrypt 中的算法

Padding Oracle

在 SSL v1.5版本

弱化版本,要求明文的,1023位是 1 如果不是则返回错误

攻击:

高级加密

循环域

基于离散对数的困难问题

DDH

CDH

DHKE

关于 order

pow(3,2,5),pow(4,2,5) v.s pow(2,4,5)

ElGameal Enc

安全性假设:DDH,CDH
群是一种代数结构,由两部分组成,第一部分是一个集合,第二部分,是集合的一种运算
群可以简单的理解为,一个运算和一个集合的总和
群的阶
循环群,
(2,2 *2,2*3,2*4)
这种方式生成一个群,称为循环群
最大的指数,为群的阶

域是有两种运算的空间

g:形成源

x([1,q-1])

ElGamal Enc

Cipher text:
(c1,c2)

运算都在群中

ElGameal Signature 签名算法

椭圆曲线

ECC
椭圆曲线上的加法,形成了群

椭圆曲线上的点,是群的集合,椭圆曲线上的加法是群的运算

椭圆曲线的加法的计算公式

test

椭圆曲线上的群

群上运算必须满足的特征

  • 闭合性

  • 结合性

  • 单位元

  • 逆元

    某些条件下,椭圆曲线的点可以构成一个循环群

    2P是P+P

    NP 是 N个P相加

曲线上有多少个点

在计算中曲线上的点是有限的

为什么使用椭圆曲线

性能上的优势?

  • 来源于密钥长度(更短的密钥)

椭圆曲线上的离散对数

椭圆曲线上的离散对数问题

怎么算aP?

RSA中提到的快速幂

椭圆曲线上的DHKE

首先,双方公开协商好用的曲线、模数,与基点P

不同代数结构中的困难问题

双线性对中

e(g^a,h^b) == e(g,h)^(a*b)

CDH?DDH?

签名算法

DSA(在实数域上的算法)

Hash(SHA-2 in DSS)

(L,H) = (1024,160),(2018)

ECDSA(在椭圆曲线上的算法)

ElGamal Signature

RSA签名

  • 签名

    s = pow(p,d,n)

  • 验证

    s = pow (p,e,n)(可能敲错了)

HMAC(HASH函数)

不安全的HMAC V.S 安全的HMAC

拙劣的HMAC 可以被HASH拓展攻击,CBC翻转字符串的题

CBC-MAC

利用CBC机制

Attack:

  • 加解密共用一个key(拿着密文进行签名,会把明文和密文对应的最后一个块发给攻击者)
  • 允许用户选择iv

HASH函数MD结构

MD结构运算

SHA 与 MAC

密钥分发

迪菲赫尔曼密钥交换(一种密钥交换的办法)

N 个同时凑齐,才可以解密

构建秘密分割协议:

构建N元一次方程组

从N个人中选K个,只有K个人凑齐就可以复现出明文

利用门限方案

树形权限分割

k 私钥(DES或AES),利用门限方案,分割成两部分

属性加密(CPABE)

MPC(多方安全计算)

国外CTF题中出现的

OT

Yao’s protocol

OT:

A 有两个消息,B想要一个消息,但不想让A知道他想要哪条消息,并且B只能得到不多于一条的消息

-------------本文结束感谢您的阅读-------------
如有疑问或需要技术讨论,请发邮件到 zlem0n@foxmail.com