ImageVerifierCode 换一换
格式:PPT , 页数:54 ,大小:555.50KB ,
资源ID:376701      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-376701.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(Introduction to Practical Cryptography.ppt)为本站会员(周芸)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

Introduction to Practical Cryptography.ppt

1、1,Introduction to Practical Cryptography,Lectures 3/4 Stream Ciphers,2,Agenda,Properties Building Blocks Competitions Examples,3,Uses,Encryption of streaming data Random bit generation,4,Stream Ciphers,Stream cipher outputs keystream, KS KS produced by a function, F, that is initialized with a key,

2、k C = Ek(P) = P KS P = C KS k can be used only once C1 = Ek1(P1); C2 = Ek2(P2) C1 C2 = P1 KS1 P2 KS2 = P1 P2 if KS1 = KS2 Will know when P1 and P2 have identical bits If know part of P1 (if packet headers, format information), then can obtain part of P2 Period how long is KS before it starts repeati

3、ng? repeating is equivalent to reusing a key,5,Stream Ciphers,Speed Initialization Keystream generation Resources memory, power, cpu Hardware, software suitability,6,Stream Ciphers,Synchronous stream cipher Sender and receiver must be in-synch Lost bit garbles all subsequent bits unless synch up Fli

4、pped bit garbles only one bit Can precompute key stream Example: RC4, block cipher in OFB mode Self-synchronizing stream ciphers Use n previous ciphertext bits to compute keystream Lost bit: synch up after n bits Flipped bit : next n bits garbled Cant precompute keystream Example: Block cipher in ci

5、phertext feedback (CFB) mode,7,Stream Ciphers General Concept,State UpdatesFSR based (SOBER, LILI)Array Permutations (RC4),key,state (data),output function,pi (ci),ci (pi),ksi,next state function,synchronous,8,Stream Ciphers General Concept,key,state (data),output function,pi (ci),ci,ksi,next state

6、function,subset of cis,error propagation block cipher in CFB mode,self synchronizing,9,Keystream Properties,Period Period of 232 repeats after 8.5 minutes when encrypting 1MB/sec Random appearance: Runs of 1s or 0s: with length 1, with length 2, 1/8 have length 3 Test little or no compression Dissip

7、ates statistics of plaintext Complexity: Low ability to define a bit as a linear expression (or algebraic expression) of bits period bits away No discernable relation to key (seed/initial state) bits,10,Agenda,Properties Building Blocks Competitions Examples,11,Stream Ciphers - Approaches,Feedback S

8、hift Register (FSR) based useful in hardware Block cipher CTR, CFB, OFB modes Components similar to those found in block ciphers,12,Feedback Shift Register,bn-1,bn-2,b1,b0,b0,F(bn-1,b0),new bn-1,Linear F: bn-1 = ibi for i 0,1i=0,n-1Nonlinear F,Tap Sequence: bits used in F,Feedback with Carry Shift (

9、FCSR)F: s = (ibi + c) for i 0,1i=0,n-1bn-1 = s mod 2c = s/2 mod log2 (# tap bits),State: bi values,bits, same concept with bytes, words,13,Period LFSR of n bits: Maximum 2n 1 FCSR: depends on initial state Non-linear FSR: depends on function, initial state Inefficient in Software Small # of bits in

10、tap sequence, easier to break. Large # of bits in tap sequence, slow. Security Berlekamp-Massey Algorithm: 2n output bits needed to reproduce the LFSR in O(n2) time. Non-linear FSR: avoid linear approximations,Feedback Shift Registers,14,Variations Utilizing LFSR,Combination generator Output bit = n

11、onlinear function on output of multiple LFSRs. May clock each LFSR differently Various combinations of AND,OR,Thresholds,LSFR1,LSFR2,LSFRn,. . .,nonlinear function,keystream,15,Variations Utilizing LFSR,Clock controlled generator Move to next state only on some clock cycles. Move to next state on ev

12、ery cycle but only output bit on some clock cycles. 2nd LFSR may control clock. Clock control that affects output is also called stuttering,16,Clock Control Examples,Stop and Go: 2 LFSRs LFSR1s output clocks LFSR2 Alternating Stop and Go: 3 LFSRs output of LFSR1 indicates whether to clock LFSR2 or L

13、FSR3 output is of LFSRs 2 and 3 Bilateral Stop and Go: 2 LFSRs output = of both outputs clock LSRFs depending on their output values Self-Decimated Generators: control their own clock some function of their state bits controls clock,17,Clock Control Examples,Shrinking Generator: 2 LFSRs always clock

14、 if LFSR1 outputs 1, use LFSR2s output, else no output on that cycle called “shrinking” because fewer output bits than clock ticks Self Shrinking Generator: similar to shrinking generator but use 2 different bits from 1 LSFR instead of 2 LFSRs Cascade: output of 1st level (may be single or combinati

15、on of generators) controls clock of next level usually not secure due to some relationship between 1st level output and final output.,18,Agenda,Properties Building Blocks Competitions Examples,19,NESSIE Stream Cipher Submissions,None recommended BMGL too slow, small internal state time/memory tradeo

16、ff attack Leviathan - distinguishing attack LILI-128 attack O(271) SNOW distinguishing attack SOBER-t16 distinguishing attack SOBER-t32 distinguishing attack Both Sober algorithms thought to be subject to side channel analysis,20,ECRYPTs eStream Contest,Just ended (3rd round of evaluations finished,

17、 winners selected) 4 for software, 4 for hardware In third round of evaluations 16 candidates 3+ years from time of call for proposals to final report originally November 2004 to January 2008 Just endedECRYPT: European Network of Excellence for Cryptology,21,eStream Overview,Categories key length of

18、 128 bits and an IV length of 64 and/or 128 bits key length of 80 bits and an IV length of 32 and/or 64 bits Separate software and hardware categories within each Evaluation Security Free of licensing requirements Performance, range of environments Committee is only collecting submissions. Evaluatio

19、ns are done by the general cryptographic community.,22,eStream Evaluation,Security Criteria Any key-recovery attack should be at least as difficult as exhaustive search. Distinguishing attacks Interest to the cryptographic community Relative importance of high complexity distinguishing attacks is an

20、 issue for wider discussion Clarity of design Implementation Criteria Software and hardware efficiency Execution code and memory sizes Performance Flexibility of use,23,eSTREAM Phase 3 Candidates,http:/www.ecrypt.eu.org/stream/phase3list.html key lengths: 128 bits for SW and 80 bits for HW,24,eSTREA

21、M Winners,http:/www.ecrypt.eu.org/stream/ key lengths: 128 bits for SW and 80 bits for HW,25,Agenda,Properties Building Blocks Competitions Examples,26,Stream Cipher Examples,Lists http:/en.wikipedia.org/wiki/Stream_cipher http:/www.ecrypt.eu.org/stream/RC4A5/1A5/3LILISoberTriviumLex,27,RC4,S-Box Cr

22、eation input key; if (key 256 bytes) repeat key until 256 bytes; for (i=0; i 256; +i) Si = i; / initialize S-BoxKi = ith key byte; j = 0; for (i = 0; i 256; +i) j = (j + Si + Ki) mod 256;swap(Si,Sj); ,Keystream Generator i = 0; j = 0; loop i = (i+1) mod 256; j = (j+Si) mod 256; Swap(Si,Sj); t = (Si

23、+ Sj) mod 256; ks_byte = St; ,2 S-Box entries form index into S-Box Output S-Box entry (byte),S-Box: key dependent permutation of 0 to 255. (lookup table),28,RC4 Cryptanalysis,Initial keystream byte highly correlated with first few key bytes Recommendations to discard first 256 or 512 output bytes D

24、istinguish from random: O(230.6) bytes needed Attempts to backtrack to initial state from keystream,Keystream Generator i = 0; j = 0; loop i = (i+1) mod 256; j = (j+Si) mod 256; Swap(Si,Sj); t = (Si + Sj) mod 256; ks_byte = St; ,29,A5/1,Used in Global System for Mobil Communications (GSM) Example of

25、 a cipher manufacturers tried to keep secret, it was leaked and also reversed engineered within 5 years A5/2 weaker cipher used in some countries due to export rules GSM phone conversations are sent as sequences of frames. One 228 bit frame is sent every 4.6 milliseconds: 114 bits for the communicat

26、ion in each direction. A5/1 produces 228 bits to XOR with the frame Initialized using a 64-bit key combined with a publicly-known 22-bit frame number. In some GSM implementations, 10 key bits are fixed at zero - effective key length is 54 bits. A5/1 is based around a combination of three LFSRs with

27、irregular clocking.,30,A5/1,Image from Wikipedia,31,A5/1 LSRFs,19 bits x19 + x5 + x2 + x + 1 clock bit 8 tapped bits: 13, 16, 17, 18 22 bits x22 + x + 1 clock bit 10 tapped bits 20, 21 23 bits x23 + x15 + x2 + x + 1 clock bit 10 tapped bits 7, 20, 21, 22Least significant bit numbered 0 Tapped bits o

28、f each LSRF are XORed to create value of next 0 bit. Output bits of the three LSRFs are XORed to form the keystream bit,32,A5/1,Each cycle, look at the three clock bits. The majority value, cm, is determined. In each LSRF, if the clock bit matches cm, the registers are clocked. In each cycle, 2 or 3

29、 LSRFs will be clocked.,33,A5/1 Initialization,Registers set to all 0s Incorporate the key and frame number: For 64 cycles, the key is mixed in by XORing the ith key bit with the least significant bit of each register For 22 cycles, the 22 bit frame value is mixed in same as with key value Normal cl

30、ocking used 100 cycles are run using the majority clocking, the output is discarded End result is the initial state,34,A5/1,Three short LSFRs Not many tap bits to guess,35,A5/3 Core,BLCNT is a 64 bit counter KM = 0x555.555 (128 bit key modifier) CK = key bits,CBC XORed with counter and key A counter

31、 previous output,defined on next slide,36,A5/3 GSM,Kc = key,http:/ forkeystream.,c,s1,s2,sk,s1,s2,sn,clocking function,integer output,Irregular: clocked c times,Regularly clocked,b,non-linear function,Family of keystream generators,38,SOBER - Original,LFSR S17 = 141 S15 175 S0 LFSR: 17 bytes, 128 bi

32、t key,Nonlinear transformation Vn = (S0 + S2 + S5 + S12) (S12 S13),Stutter Control,Output function (sc) 00: No output 01: Vn 01101001 10: Vn 11: Vn 10010110,output byte,sc,Vn,Clock Control,Vn,sc = next 2 bits of byte need byte: clock, take Vn Clock Control (sc) 00: 1 clock01: clock, output, clock10:

33、 2 clocks11: 1 clock,Sis,39,Sober t8,16,32,8,16,32 = byte size of key,40,Sober-t,LSFR for Sober-tw w = 8,16,32,Max period: 213w-1,41,Non-linear Function,LFSR output input to non-linear function fw, output added to subset of LSFRs bits, XORed with key-dependent value, this result then added to subset

34、 of LSRF bits,42,Trivium,Christophe De Canniere and Bart Preneel hardware oriented synchronous stream cipher Trivium generates up to 264 bits of key stream from an 80-bit secret key and an 80-bit initial value (IV). Internal state is 288 bits,43,Trivium,IV and key used to initialize the state Iterat

35、e state extract values of 15 specific state bits and use them to update 3 bits of the state and to compute 1 bit of the key stream zi. state bits then rotated and process repeats,44,Trivium Key Stream Generation,for i = 1 to N do t1 s66 s93 t2 s162 s177 t3 s243 s288 zi t1 t2 t3 t1 t1 s91 s92 s171 t2

36、 t2 s175 s176 s264 t3 t3 s286 s287 s69 (s1; s2; : : : ; s93) (t3; s1; : : : ; s92) (s94; s95; : : : ; s177) (t1; s94; : : : ; s176) (s178; s279; : : : ; s288) (t2; s178; : : : ; s287) end for,45,Trivium Initialization,load 80-bit key and 80-bit IV into 288-bit initial state set all remaining bits to

37、 0, except for s286, s287, and s288, which are set to 1 state is rotated over 4 full cycles of the for look, but no bits are output (for i = 1 to 4288),46,Trivium,state bit is not used for at least 64 iterations after it has been modified up to 64 iterations can be computed at once, provided that 3

38、AND gates and 11 XOR gates in the original scheme are duplicated a corresponding number of times,47,Estimated Gate Counts 1-bit to 64-bit hardware implementations,48,Software,Stream generation: 12 cycles/byte Key setup: 55 cycles IV setup: 2050 cycles on Intel XeonTM CPU 1.5 GHz,49,Trivium Security,

39、Linear correlations between key stream bits and internal state bits are easy to find because zi is simply defined to be equal to s66s93 s162 s177 s243 s288. But, as opposed to LFSR based ciphers, Triviums state evolves in a nonlinear way not clear how an attacker should combine these equations in or

40、der to efficiently recover the state Estimate: follow linear trails through the cipher and approximate the outputs of all encountered AND gates by 0. However, the positions of the taps in Trivium have been chosen in such a way that any trail of this specific type is forced to approximate at least 72

41、 AND gate outputs If assume that the correlation of linear combination is completely explained by a specific trail considered, then it would have a correlation coefficient of 2-72 Detecting such a correlation would require at least 2144 bits of key stream Other more complicated types of linear trail

42、s with larger correlations might exist, estimate that no correlations will exceed 2-40,50,Lex,Alex Biryukov Leak EXtraction Software category Uses AES reuse if application has AES implementation,51,Lex,Initialize: Key AES: 128-bit key, K, run through standard AES key-schedule State: 128-bit IV is en

43、crypted by AESS = AESK(IV ) Generate key stream Repeatedly encrypt (starting with S) Rekey every 500 AES applications,52,Lex,takes 4 bytes from each round of AES (see next slide),53,Lex,54,Lex,order of bytes not relevant for security relevant for fast software implementation allows extraction of a 32-bit value from two 32-bit rows in four steps (t0&0xFF00FF) 8) (t2&0xFF00FF),t0 = 1st row, t2 = 3rd row in 4x4 matrix,

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1