20XX年密码编码学与网络安全培训教材 文档预览

密码编码学与网络安全电子工业出版社

2006-2007第3章对称算法DES3.1分组密码算法原理3.2

DES算法3.3

DES强度3.4差分分析和线性分析3.5分组密码设计原理3.A

DES

in

/etc/passwd3.B

DES

in

OpenSSL↓↓↓↓↓↓↓密码技术发展

1918，William

F.

Friedman，The

Index

ofCoincidence

and

Its

Applications

in

Cryptography

1949，Claude

Shannon，The

CommunicationTheory

of

Secrecy

Systems1967，David

Kahn，The

Codebreakers1970s，NBS/NIST，DES

（90s,

AES）

1976，Diffie,

Hellman，New

Directory

inCryptography

1984，C.H.

Bennett，Quantum

Cryptography:Public

Key

Distribution

and

Coin

Tossing1985，N.

Koblitz，Elliptic

Curve

Cryptosystem2000，AES3.1分组密码算法原理分组密码算法Block

Cipher明文被分为固定长度的块(即分组)，对每个分组用相同的算法和密钥加解密分组一般为n＝64比特，或更长(Padding)密文分组和明文分组同样长对某个密钥可以构造一个明密文对照表Codebook

(Substitution

Table)所以分组的长得至少64比特才好密钥空间2^k<<可逆映射个数(2^n)!序列密码算法(流密码算法)流密码算法Stream

Cipher每次可以加密一个比特适合比如远程终端输入等应用流密码可用伪随机数发生器实现密钥做为随机数种子，产生密钥流

keystream(不重复,或极大周期)XOR

(plaintext，key-stream

)One-time

Pad比较基本区别粒度8字节分组vs.1比特或1字节各自适应不同的应用数据格式Padding对相同的明文分组，总是输出相同的密文分组；而流密码却输出不同的密文比特流密码一般快很多分组密码多些，是主流分组密码也可以用作流模式安全性对比Block

Cipher

Principles0000

11100001

01000010

11010011

00010100

00100101

11110110

10110111

10001000

00111001

10101010

01101011

11001100

01011101

10011110

00001111

01110000

11100001

00110010

01000011

10000100

00010101

11000110

10100111

11111000

01111001

11011010

10011011

01101100

10111101

00101110

0000乘积密码：重复使用代替和置换，实现混乱和扩散。Feistel(DES)加密框架明文分组的长n＝2w –分左右两半L0

R0密钥K产生子钥：K→k1，k2，…，kr –r是轮数，比如16轮⊕是异或函数XOR–

p⊕x⊕x

=

p函数F是散列混乱函数–可以是手工精心构造的查表函数Feistel网络•Feistel解密•Feistel

–

‘for’

Loop加密计算序列L0＝左半

L1＝R0R0＝右半

R1＝L0⊕F(k1,R0)L2＝R1R2＝L1⊕F(k2,R1)L3＝R3R3＝L2⊕F(k3,R2)…Ri＝Li-1⊕F(ki,Ri-1)Li＝Ri-1…Ln＝Rn-1Rn＝Ln-1⊕F(kn,Rn-1)密文即（Ln，Rn）解密计算2轮解密举例

假设n＝2轮，C

＝（L2，R2）加密明文＝半＋半＝L0+R0L1＝R0

R1＝L0⊕F(k1,R0)L

＝R

R

＝L

⊕F(k

,R

)2 1

2

1

2

1解密密文＝半＋半＝L2＋R2R1＝L2L1＝R2⊕F(k2,R1)R0＝L1L0＝R1⊕F(k1,R0)明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L0Feistel伪代码明文m长度n＝2t，记为m0m1，每个长度为t密钥k产生r个子密钥k1,k2

,...,krm：0,

1i,

i+1

<-

kir,

r+1

<-

kr加密Efor

i=2

to

r+1

domi＝mi-2

XOR

f(mi-1,ki-1)得密文（mr，mr+1）解密Dfor

i=r

to

1

domi-1＝mi+1

XOR

f(mi,

ki)或for

i=r-1

to

0

domi＝mi+2

XOR

f(mi+1,

ki+1)＝mi

XOR

f(mi+1,

ki+1)

XOR

f(mi+1,

ki+1)＝mi唯一的非线性结构就是F可以重复使用两个变量即可Feistel参数特性分组大小密钥大小循环次数一般仅几轮是不够的，得十几轮才好，如16轮子钥产生算法越复杂越好轮函数Round关键其他考虑速度（尤其是软件实现的速度）便于分析（使用简洁的结构）Feistel类算法举例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel结构的AES、IDEA*绝大数分组密码属于或类似Feistel结构多轮每轮有XOR（或能恢复的操作）轮函数3.2

DESData

Encryption

Standard1971

IBM

Horst

Feistel—Lucifer→DES，key由128bit→56bit1973

NBS，77

NIST

FIPS-46－NBS/NIST、IBM、NSA1994最后一次延长到1999年－AES取代之参数Feistel体制分组密码分组大小64bit，密钥大小56bit，轮数16轮S-Boxes

*DES•密钥置换选择-1Key

Permuted

Choice

One

(PC-1)57

49

41

33

25

17

9

81

58

50

42

34

26

18

1610

2

59

51

43

35

27

2419

11

3

60

52

44

36

3263

55

47

39

31

23

15

407

62

54

46

38

30

22

4814

6

61

53

45

37

29

5621

13

5

28

20

12

4

647×8K的56比特重新排列，成为C0D01

2

3

4

5

6 7

89

10

11

12

13

14

15

1617

18

19

20

21

22

23

2425

26

27

28

29

30

31

3233

34

35

36

37

38

39

4041

42

43

44

45

46

47

4849

50

51

52

53

54

55

5657

58

59

60

61

62

63

64Keyi

(48bit)C0D0…C15D15PC-214171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入选的：9、18、22等Round

number

1

2

3

4

5

6

7

8

910111213141516Bits

rotated

1

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1每轮从56比特中选取48比特即为Ki，并同时左移初始置换及逆置换Initial

Permutation

（IP/IP-1）5850423426181024084816562464326052443628201243974715552363316254463830221463864614542262306456484032241683754513532161295749413325179136444125220602859514335271911335343115119592761534537292113534242105018582663554739312315733141949175725初始明文按照IP重排；16轮后的密文按照IP-1重排即为最后密文oddeven轮One

Round•扩展置换Expansion

Permutation•32

1

2

3

4

5456789891011121312131415161716171819202120212223242524252627282928293031321R的32bit→48biti两边的是重复选中的6×8轮函数Round

Function•S盒S-Boxes：1/4两边2比特选择行号中间4比特选择列号S-Boxes：5-8从S盒出来后重排：Permutation

FunctionP

8×416 7

20

21

29

12

28

171 15

23

26 5

18

31

102 8

24

14

32

27

3

919

13

30 6

22

11 4

25DESReview一个DES计算实例p=0123456789ABCDEFk=133457799BBCDFF1•……••c=85E813540F0AB405使用OpenSSL库的DES函数明文64bitKey

56bit“plaintxt”8字节

“password”取低7bits×8手工运算vs.void

DES_ecb_encrypt(const_DES_cblock

*input,DES_cblock

*output,DES_key_schedule

*ks,int

enc);密文8B32

97

23

0f

81

3e

da

af3.3

DES安全强度对DES的争议集中在密钥空间太小Key

space从Lucifer的2^128降到DES的2^56DES

Challenge

III,

22

hours

15

minutesS盒S-BoxesS盒的设计准则？陷门？trapdoors

by

NSA(?)

“Form

surprise

to

suspicion”从惊喜(甚至能够抵御很后来才发现的各种攻击)到怀疑(n年前就如此厉害的NSA现在究竟有多厉害)密钥大小Key

Size2^56

≈7×10^161Mkeys/Second

means

1000

yearsSpecial

machine

designedWiener

http://www3.sympatico.ca/wienerfamily/Michael/Cost/time

table

>Recent

newsin

1997

on

Internet

in

a

few

months

(Rocke,96days)in

1998

on

dedicated

h/w

in

a

few

days(DES

II-2

EFF,

56

hrs)in

1999

above

combined

in

22hrs

15

mins“Deep

Crack”

by

EFF穷举(蛮力)攻击Cost/Time表Key

search

machine

unit$

100,000$

1,000,000$10,000,000expected

search

time35

hours3.5

hours21

mins<Efficient

DES

Key

Search>wiener93efficient.pdfA

Brute

Force

Search

of

DES

Keyspace /pubs/des-key-crack/按照NIST的提议，98年以后DES不应继续使用–3DES、AES、RC5、IDEA等“Deep

Crack”

Hardware

CrackerDeveloped

by

theElectronic

Frontier

FoundationCost

US$210,000–

$80,000

design–

$210,000

materials

(chips,

boards,

chassis

etc)VLSI

Chip

Developed

by

AdvancedWireless

Technologies24

search

units

per

chip40

MHz16

cycles

per

encryption2.5

million

keys/sBoard

contains

64

chips6

cabinets

holding

29

boardsDeep

Crack

System90

billion

keys/s37,000

search

unitsc.f.

Distributed

Net’s

34

billion

keys/sControlled

by

PCchecks

possible

all

ASCII

candidate

solutionsfrom

the

search

unitsSolved

RSA’s

DES-III

in

22

hoursJan

18,

1999蛮力攻击对明文内容的要求*问题：如何辨别出来？对给定的某个密文，任何一个密钥都可以解密出一个可能的明文，但是其中应该只有一个是正确的明文。必须事先知道明文的结构，比如已经知道这是文字文本、源程序（图像、声音、压缩的？）如果有两个密钥，解密出来的两个明文都有意义？可能性极小因为密钥空间2^k<<可逆映射个数(2^n)!One

time

pad就是让对手分辨不出哪个更像正确明文S盒特性SizeInput

N

×

output

M8×32，but

DES

6×42^N

→

M

bitsin

contrast

to

DES’s

2^2×2^4→4NonlinearBent

functionS-boxes’

evolutionBlowfish,

but

DES’s

is

man-madeavoid

analyze

in

advanceAvalancheEffect

in

DES(A)P1：00000…0

(64bit)P2：10000…0(相差1bit)K

：0000001

1001011•01001001100010•00111000011000•00111000110010(B)K1：…

(56bit)K2：…(相差1bit)P

：…

(64bit)DES弱密钥DES弱密钥：4(子密钥相同)0101

0101

0101

0101000000000000001F1F

1F1F

E0E0

E0E0eq0000000FFFFFFFE0E0

E0E0

1F1F

1F1FFEFE

FEFE

FEFE

FEFEFFFFFFFFFFFFFF0000000FFFFFFFDES半弱密钥：12（两个子密钥，互为加解密）01FE01FE01FE01FEFE01FE01FE01FE011FE01FE00EF10EF1E01FE01FF10EF10E01E001E001F101F1vsE001E001F101F1011FFE1FFE0EFE0EFEFE1FFE1FFE0EFE0E011F011F010E010E1F011F010E010E01E0FEE0FEF1FEF1FEFEE0FEE0FEF1FEF1DES可能的弱密钥：24（四个子密钥） –…3.4差分分析和线性分析蛮力攻击计时攻击差分分析线性分析–正面分析密码算法的新技术，在很多算法上取得很好的效果差分分析Differential

CryptanalysisBiham,

Shamir

(‘S’)–

1991»

NSA,1974攻击实例–对8轮DES，只需微机几分钟–对16轮DES，复杂度为2^47需这么多的选择明文，使本方法只有理论意义Differential

Cryptanalysis

of

the

Full

16-round

DES线性分析Linear

Cryptanalysis对DES攻击进展需要2^47个已知明文虽比选择明文容易，但仍只具有理论意义Linear

Cryptanalysis/RES/LINANA.HT

MGoogle(“A

Tutorial

on

Linear

and

DifferentialCryptanalysis

”)DES其他DES肯定能破译不单是RSA

challengeDES算法仍值得信赖但是关键场合不要用DES对一般个人用户仍是安全的RSA

challenge反而给了信心DES还是AES，或者其他DES模块仍广泛存在，AES还没有普及如果软件实现，任何一个经过考验的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/Open3.5分组密码的设计原理DES

Design

Criteria设计准则as

reported

by

Coppersmith

in

[COPP94]7

criteria

for

S-boxes

provide

fornon-linearityresistance

to

differential

cryptanalysisgood

confusion3

criteria

for

permutation

P

provide

forincreased

diffusion分组密码设计原理轮数轮函数FS盒雪崩效应密钥使用方法子钥衍生方法雪崩效应轮函数F及S盒的设计strict

avalanche

criterionbit

independence

criterion轮函数F雪崩效应准则独立准则S盒构造方法随机方法随机加测试方法人工构造方法数学构造方法•查阅和学习Google(“Engima兴亡”)Google(“ENIGMA传奇”)DES

Challenge/rsalabs/challenges/des//descracker/D基于互联网的分布式并行破译项目–

/3.A

DES

in

/etc/passwdfile

‘passwd’

formatusername:passwd:UID:GID:full_name:directory:shell{From

Shadow-Password-HOWTO}account:password:UID:GID:GECOS:directory:shell{From

RH8}shadow/etc/passwd/etc/shadowpasswd

--->

*passwd–

username:passwd:last:may:must:warn:expire:disable:reservedsample–

username:Npge08pfz4wuk:503:100:FN:/home/username:/bin/shusername:x:503:100:FN:/home/username:/bin/shusername:Npge08pfz4wuk:9479:0:10000::::1/22/2crypt()函数crypt#define

_XOPEN_SOURCE#include

<unistd.h>char

*crypt(const

char

*key,

const

char

*salt);passwd

space–128-32-’7f’=95个可用字符–

95^nsalt两个字符，每个可从[a-zA-Z0-9./]中选出来，即有

4096种不同取值抵制字典攻击中的预算值crypt()描述从passwd到keypadding形成8字符的组每组产生56bits＝8×7的密钥如果多于1组，则XOR累计重复加密64比特0到25回–中间置换，受salt控制，计有4096种不同的置换输出2＋11字符2字符是明码salt11字符是编码后的DES的64bits输出密文crypt()

Fig•Passwd

Cracker基于字典的口令猜测攻击字典的构造普通字典×用户相关的词语John

the

Ripper

password

cracker/john//20010409/169181.shtmlL0phtCrack/wiki/L0phtCrack更多安全工具/tools2.htmlZip

cracker

sample

Advanced

ZIP

Password

Recoverystatistics:E