New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Special Topics in Computer Science and Engineering

by: Americo Huel

Special Topics in Computer Science and Engineering CSE 5095

Marketplace > University of Connecticut > Engineering Computer Science > CSE 5095 > Special Topics in Computer Science and Engineering
Americo Huel
GPA 3.73

Zhijie Shi

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Zhijie Shi
Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 87 page Class Notes was uploaded by Americo Huel on Thursday September 17, 2015. The Class Notes belongs to CSE 5095 at University of Connecticut taught by Zhijie Shi in Fall. Since its upload, it has received 37 views. For similar materials see /class/205924/cse-5095-university-of-connecticut in Engineering Computer Science at University of Connecticut.


Reviews for Special Topics in Computer Science and Engineering


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/17/15
Instruction Set Architecture 1 WUNN Z Jerry Shi Assistant Professor of Computer Science and Engineering University of Connecticut Shdes adapted fromR Baiasubramomanc56810Unwer5it ofUtan Baden andTuHsenCSEZAO UCSD Many figures are provide by Eisevier Instruction Set Architecture ISA ISA provides the level of abstmction for both the hardware and so ware Interface between the so ware that runs on a computer and the hardware that exec 39 Application Operating l System COIIllJll61 Instruction Set Architecture Micro code Do system interface Machine Organization Instruction Set Architecture ISA Functional de nition of operations modes and storage locations supported by hardware Precise description of the ways to invoke and access them No guarantees regarding 7 How operations are implemented 7 Which operations are fast which are slow and when 7 Which operations take more power In early days In 19505 each new model had entirely different instruction set 7 Programmed at machine code or assembly level IBM introduced FORTRAN in 1957 7 Much easier to write programs 7 Code wasn tmuch slower 7 Possible to use a new machine without reprogramming 7 Algol PLI and other highlevel languages followed Computer makers weren t so happy 7 Needed to write new compilers and 05 s for each new model Written in assembly code Portable compilers didn t exist IBM360 architecture the first ISA used for multiple models huge success 7 6 models introduced in 1964 7 Evolved to 370 virtual addressing and 390 32bit address ISA for different segments 0 Instruction sets for all three segments are very similar 0 Desktops 7 Equal emphasis for integer and oating point 7 Little regard for code size and power 0 Servers 7 High performance high throughput 7 Many do not need floatingpoint 0 Embedded 7 Emphasis on low cost and power 7 code size is important 7 Floatingpoint may be optional 0 Desktops and embedded also care about multimedia applications 7 Special media extension instructions Where are instructions stored V011 Neumann Architecture inst amp storage Harvard Architecture Crafting an ISA Designing an ISA is both an art and a science What makes a good ISA 7 Completeness 7 Orthogonality 7 Regularity and simplicity 7 Compactness 7 Ease of programming 7 Ease of implementation High performance implementation Recently lowpower lowcost highavailability etc 7 Compatibility x86 IA32 generations 8086 80286 80386 80486 Pentium Pentium II Pentium III Pentium 4 Key ISA decisions Operations destination apemnd H 7 opermion 7 ow many 7 What kinds r yXTb o Operands HOW blg source operands 7 How many 7 Locations 7 How to specify Instruction format 7 How many formats 7 Instruction length Operand locations Three types of computers 7 Stack 7 Accumulator 7 Registers Two types of register machines 7 Registermemory Most operands can be either in registers or in memory 7 Loadstore Most operations deal with registers only Explicit load and store instructions move data between registers and In em ory How many operands Stack 0 address add tos 6 tos next Accumulator 1 address add A ace 6 acc MEMA Registermemory 2 addresses add Ra B Ra Ra B 3 addresses add Ra Rb C Ra Ra C LoadStore 3 addresses add Ra Rb Rc Ra Rb Rc load Ra Rb Ra eMEMRb store Ra Rb MEMRb Ra Operand locations for four ISA classes a Slack n Accumulator c Registermemory a RegisterregisterHeadstare Processor Ev ltII MW 2003 Elsevier Science USA All rights reserved Example CAB Stack Accumulator Reg regmem Reg loadstore Push A Load A Load R1 A Load R1 A Push B Add B Add R3 R1 B Load R2 B Add Store C Store R3 C Add R3 R1 R2 Pop C Store R3 C Registers fast exploit locality reduced memory traf c easier to reorder Addressing mode Register add R1 R2 R3 Immediate add R1 R2 3 Displacement load R1 16R2 Register indirect load R1 R3 Indexed load R1 R2R3 Auto increment load R1 R2 Auto decrement load R1 R2 Directabsolute load R1 256 Memory indirect load R1 R2 0 Scaled load R1 R2R3 Addressing mode 2 instruction Immediate 3 Load R116R2 Indexed Directabsolute Memory indirect Load R1 R2 RegsR1 6 MemMemRegsR2 More addressing modes 9 low instruction counts more complexity CISC like Most comm on modes immediate and displacement Displacement and immediate values often require fewer than 8 bits but also often require 16 bits Frequency of the addressing mode Memory indirect Scaled Register indirect 43 Immediate 39 Displacement 39 55 40 0 10 20 30 40 50 60 Frequency of the addressing mode 2003 Elsevier Science USA All rights reserved Number of bits of displacement 40 35 Inieger average 80 25 Percentage of displacement 20quot Floatingpaint average 1 5 1 0 1 2 3 4 5 6 7 B 9 10 11 12 13 14 15 Number of bits of displacement C 2003 Elsevier Science USA All rights reserved Number of bits needed for immediate 40 l Floatingpoint average Percentage of I immediates 20 1 5 Integer average 10 M iVA h 5 4 J W 0 a 0 1 2 3 4 5 6 7 B 9 10 11 12 13 14 15 Number 01 bits needed for immediate 2003 Elsewer Science USA All Hng reserved Little and big endian Consider a 64bit quantity composed of bytes 70 MSBLSB B7 B6 B5 B4 B3 B2 B1 B0 Littleendian format MemA B0 MEMA 1 Bl MEMA2 B2 Advantage easier to organize bytes halfwords words double words etc into registers Alpha X86 Bigendian format MemA B7 MEMA 1 B6 MEMA2 B5 Advantage values are stored in the order they are printed out the sign is available early Motorola Bigendian R1 0x01020304 After R1 is stored into memory OXAAOO OXAAOO 01 OXAAOl 02 OXAAOZ 03 OXAA03 04 Bigendian may be in registers too Bit 0 is the leftmost bit MSB Littleendian R1 0x01020304 After R1 is stored into memory OXAAOO OXAAOO 04 OXAAOl 03 OXAAOZ 02 OXAA03 01 How many registers VAX 7 16 registers 7 R15 is program counter PC Loading R15 is a jump instruction 7 Fine print some restrictions apply x86 7 8 general purpose registers 7 Plus oating point and special purpose registers 7 Plus some special purpose ones PowerPC has 8 fourbit condition registers a count register to hold loop index and others re gi sters Most RISC s have 32 int and 32 oating point registers IA64 has 128 integer 128 oating point and 64 predicate Operands in an instruction Type Advantages Disadvantages Examples RegisterRegister ps 0 mem Simple fixedlength simple c degeneration easy pipelining andparallelism extraction High instruction count 39 e Alpha MIP S ARM P owerPC SP ARC RegisterMemory 2 ops 1 mem Can access data Without doing a load small code size One ofthe operands is destroyed instruction latency is variable Intel 80x86 otorola MemoryMemory 2 ops 2 mem or 3 ops 3 mems Most compact code size doesn twaste registers Variation in instruction length hard to decode accesses v instruction latency VAX What operations Arithmetic 7 Add subtract multiply divide Logic 7 And or shift rotate etc Load store Control ow 7 Unconditional branch 7 Conditional branch 7 Function callreturn Floating point operations Permutation Operations types Operator Type Examples ArithmeticLogical Add sub and or mul div Data transfer Loadsstores Flow control Branch jump call return System OS call virtual memory management cache Floating point FP add sub mul div Decimal Decimal add sub mult decimal to character conversions String Move compare search Graphics Compressiondecompression vertexpixel ops Types of branches Conditional branch beq R1 R2 label Unconditional branch jump label 0 Procedure call call funl Procedure return return I Floatingpoint average Callreturn I Integer average Conditional branch 50 75 1 00 Frequency of branch instructions 0 25 Branch distance Percentage at distance Floatingpoint average a 9 10 Bits DI branch displacement 2003 Elsswev Science USA All rights veserved Branch instruction decisions How is the destination of a branch speci ed How is the condition of the branch speci ed What should be done at function callsreturns What about interrupt Specifying the target address Absolute address PCRelative target address PC distance 7 Needs fewer bits to encode 7 Independent of howwhere the compiled code is linked 7 The displacement needs 48 bits typically Registerindirect jumps the address is not known at compile time and has to be computed at runtime 7 Procedure returns 7 Case statements 7 Virtual functions 7 Function pointers 7 Dynamically shared libraries Specifying branch conditions Condition codes 7 Processor status bits are set as a sideeffect sub R1 R2 R3 bz foo Condition register cmp R1 R2 R3 39 or cmpgt bgt Rl label Compare and branch bgt R1 R2 label Specifying branch condition 2 Name Examples HOW condmon ls Advantages Disadvantages tested 80X86 s ti CC39 xtr tt condition ARM TeSts Spedal bits set conii innilfset Instrudtsigns 2311be P PC cede CC ower by ALU Ops for free reordered SPARC Condition Alpha Comparison sets Register MIPS register and this is Simple Register pressure tested Compare PARISC Comparison is part One instruction Com 18X 1 sums and branch VAX of the branch instead of two p p p Frequency of comparison types Not equal Equal Greater than or equal 0 Greater than 0 Less than or equal Less than 35 0 1 0 30 40 50 Frequency of comparison types in branches 20 2003 Elsevier Science USA All rights reserved Floatingpoint average I Integer average 16 Function callretum 0 Need to maintain a stack of return addresses In memory or in hardware Can save all registers together or this can be done selectively Who is responsible for saving registers Caller saving Global register has to be made available to other procedures Only saves values that it cares about Callee saving Saves only as many registers as it needs Some registers can be overwritten A combination of both is typically employed Common operations 80x86 instruction Integer average total executed Load 22 Conditional branch 20 Compare 16 Store 1 2 Add 8 And 6 Sub 5 Move re gisterre gister 4 CallReturn 2 Instruction set encoding Instruction bits are precious resources Operations are easy to encode ef ciently 7 The key issues are the number of operands and their addressing modes Few addressing modes 7 Low complexity in decoding and pipelining but greater code size Fixed instruction lengths 7 Low complexity in decoding but greater code size Instruction lengths Operation and Address Address Address Address no of operands specifier 1 field 1 specifier field a Variable eg VAX Intel 80x86 Operation Address Address Address field 1 field 2 field 3 b Fixed eg Alpha AFlM MIPS PowerPC SPARC SuperH Operation Address Address specifier field Operation Address Address Address specifier 1 specifier 2 field Operation Address Address Address specifier field 1 field 2 0 Hybrid eg IBM 36070 MIPS16 Thumb Tl TM5320C54X 2003 Esevier Science USA A rights reserved Example instruction layout for MIPS ltype instruction 5 5 16 Opcode rs Immediate Encodes Loads and stores of bytes half words words double words All immediates rt rs op immediate Conditional branch instructions rs is register rd unused Jump register jump and link register rd 0 rs destination immediate O Rtype instruction 6 5 5 5 5 6 Opcode rd shamt funct l S f39t Registerregister ALU operations rd rs funct rt Function encodes the data path operation Add Sub Readwrite special registers and moves Jtype instruction 6 26 Opcode Offset added to PC Jump and jump and link Trap and return from exception Compiler Regularity Compiler is primary customer of ISA Register allocation is a huge contribute to performance Compiler writer s job made easier when ISA has Primitives not solutions Simple tradeoffs Compiler wants Simplicity over power Compiler optimization Dependencies Language dependent machine independent Somewhat language dependent largely machine independent Small language dependencies machine dependencies slight eg register countstypes Highly machine dependent language independent intermediate representation High eVel opti zations Glo al 0 mizer Front end per language Code generator Function Transform language to common intermediate form For example loop transformations and procedure inlining also called procedure integration Including global and local optimizations register allocation Detailed instruction selection and machinedependent optimizations may Include or be followed by assembler 2003 Elsevier Science USA All rights reserved Effect of compiler optimization Branchescalls I Floatingpoint ALU ops El Loadsslows lucas level 3 lucas level 2 El Imege ALU 0P5 lucas level 1 21 Program compiler lucas level 0 100 optimization level mct levela 76 mcl level 2 76 met level 1 34 mcf level 0 100 0 20 40 60 80 100 Percentage of unoptimized instructions executed 2003 Elsevier Science USA All rights reserved Register allocation issues Graph coloring determine when variables are live and avoid allocating the same register to variables that are live simultaneously Stack local variables 7 Easy to allocate registers for Global data area statically declared objects 7 Most of them are arrays or other aggregate data structure 7 May be accessed from multiple places aliasing 7 Dif cult to allocate to registers Heap dynamically created objects accessed with pointers 7 Dif cult to allocate to registers 20 RISC vs CISC Complex Instruction Set Computer Hardware is faster 9 implement everything in hardware 7 Rich instruction set 7 Complex decoding 7 Complex analysis to identify dependences Reduced Instruction Set Computer Focus on the most frequently used operations 7 Easy to extract parallelism 7 Simpler hardware easy to achieve higher clock speeds Reduced instruction set computer RISC Relatively few instructions Instructions have the same length Relatively few instruction formats Instructions can be executed in one cycle 7 Except for a few instructions like MUL 7 Good for pipeline design Relatively few addressing mode Operands are stored in registers 7 except for LOAD STORE instructions A large number of registers 21 Popular processors Intel 7 lA32 ClSC 7 lA64 RISC Many features borrowed from HP PARISC processors 7 XScale RISC was ARM s StrongARMZ AMD 7 Athlon RISC Uses technologies in DEC Alpha 21064 Converts X86 instructions into xedlength MicroOPs 7 Hammer Athlon with 64bit extension Freescale and IBM 7 PowerPC RISC PowerPC PowerMac ARM Advanced RISC Machines Ltd 7 RISC processor core 0 SPARC 7 RISC processors designed by Sun TI and Fujitsu RISC vs CICS 22 Dealing with code size in RISC Some hybrid versions allow for 16 and 32bit instructions 40 reduction in code size useful for embedded apps Compress instructions in memory 7 More hardware complexity Reducing the register le size can also reduce the instruction length 7 However applications need more registers SPEC89 benchmarks Perlarmance rato MIPSNAX Instructions executed val m CPI ratio dz g 4 42 61gt 139 6 so 0 065a gob SPECBQ benchmarks Q Q Q 0 2003 E sewer Science USA A rights reserved 23 Key points Modern ISA s typically sacri ce power and exibility for regularity and simplicity 7 Trade off code density for instruction level parallelism Instruction bits are very limited 7 Particularly in a xedlength instruction format Registers are critical to performance 7 IA64 has 128 registers Displacement addressing mode handles the majority of memory reference needs A little bit more about the history In the 1960s stack architectures were considered a good match for highlevel languages In the 1970s ISAs were enriched to make the compiler sjob easier 7 CISC 7 Software costs were a concern In the 1980s there was a push for simpler architectures 7 high clock speed and high parallelism 7 RISC In the 1990s multimedia extensions ApplicationSpecific Instruction Set Processor 7 Choose only the instructions critical to the performance of target applications Save die area Reduce power consumption 24 Case study PowerPC instruction set architecture Integer instructions Load and Store instructions Flow control instructions Trap instructions Processor control instructions Memory synchronization instructions Memory control instructions System linkage instructions Simpli ed PowerPC block diagram Instruction Unit MMU LoadStore Unit L SU GPR File I ALU o Registers in a 32bit PowerPC core Generalpurpose registers 7 32 registers R0 to R31 Condition registers 7 CRO to CR7 each 4 bits LT GT EQ and SO XER register 7 Summary over owSO Over owOV and Carry CA Link register LR Count register CTR Other registers 7 Floatingpoint registers time base facilitycon guration memory management exception handling etc Generalpurpose registers GPR R0 through R31 are in generalpurpose register le 7 R0 is not always 0 7 R0 is considered 0 in some instructions addi R1 no 10 You can use any GPR but follow calling conventions if your codes will be linked with other codes 26 Condition register CR 0 A 32bit register used for testing and branching Grouped into eight 4bit fields 0 Can be accessed with instructions such as crand and cror CRO 7 CR7 cnu cm i 042 Figure 41 cm ORA mi 19 an Condition Register CR 23 2A Table 4 3 Bit Settings for CHO Field of CR Descriptian Example setting CRO Table 43 Bit Settings for CRO Fieid of CH cmpw R1 R2 R1 10 R2 5 CRO 010x R1 gt R2 Description cmp 0 1 R1 R2 5 10 10 10 100x 001x R1 lt R2 R1 How can you check lt gt and R2 27 Integer instructions Arithmetic instructions add 121122123 R1R2R3 Compare instructions cmp cr30R1 R2 result will be CR3 cmpw cr3 R1 R2 Mnemonics Logical instructions or 121122123 R1R2R3 Rotate and shift instructions rlwnm R1R2R303l R1 R2 ltltlt R3 rotlw R1 R2 R3 Mnemonics Load and store instructions Three addressing modes for Load and Store Register indirect addressing 1 R1 R2 R1 R2 Register indirect with immediate index addressing lwz R1 4R2 R1 R2 4 F EA R2 4 P R is always 0 in lwz 0 Register indirect with index addressing lwz R1 R2 R3 R1R2R3 EA R2 R3 28 Load and store instructions 2 Use three addressing modes to load and store 7 byte 8bit half word16bit word 32bit The base register may be updated Branch and ow control instructions Branch instructions 7 bx b ba bl bla Absolute address or relative address Save the next instruction address in LR Branch conditional instructions 7 bcx bc bca bcl bcla Branch conditional to link register 7 bclr can be used as return Branch conditional to count register 29 Count register CTR I A 32bit register that holds a loop count Can be decremented by using proper BO elds in conditional branch instructions 7 Bit 2 in the B0 eld Table 87 Bo Operand Encodings nesmpnon Example 100p using CTR main P set the count register P repeated instructions again P CTR CTR 1 P go to again if CTR 0 exit P CTR 10 do while CTR bdnz is listed in Table F 4 PEpage F 7 30 Call functions using link register LR or R1 R2 R3 bl foo call foo add R1 R1 R2 blr return branch to the link register Nested function calls foo 31 Calling convention Linux R0 scratch registers R1 stack pointer R2 system reserved R3 7 R10 parameter and result passing 7 R3 and R4 are also return values R11 7 R12 scratch registers R13 global pointer to the small data area R14 7 R31 global integer registers 7 R31 may be used as environment pointers Integer exception register Summary over owSO Over owOV and Carry CA Affected by instructions such as addo and addco CA is set and used by addc adde and other instructions o 1 2 a Fwem1 so 1 UV 1 DA 1 R at es 1 ouuujuuuuuujmu 1 ww1 1 i 24 25 31 Fwe1d1 r BENT 1 Reset1 0000700007000070000 1 WW1 WW Figure 421XER Register 32 mfspr and mtspr instructions Move from specialpurpose registers to GPR Move to specialpurpose registers from GPR Ninemonics mfxer R1 mfspr R1 1 mflr R1 mfspr R1 8 mfctr R1 mfspr R1 9 mtxer R1 mtspr 1 R1 mtlr R1 mtspr 8 R1 mtctr R1 mtspr 9 R1 Case study MiniMIPS w m D uc4 nx Wig 4 Blucdliun MemMY upmzmwnrds Lor Lot 777 8 m 4 rru Conrot n oating palm um TMU Copmr 0 Chapter m Fmp amp memory u n n Registers and data r WNW Wu a w m H 1 m n W Wm A typical MIPS instruction and execution steps HIthcvd anguagc slalcmcmz Asscmhw language HISLrHcUon Machinelanguageinstruction 000000 10010 1000 1 u an 1n n ALlHypE Regisler nguster Register Unuser Addninn mmumon H3 17 24 opturle Regisxer ch sw nilrumon We Dana Cache We LJLhE not used P C 524 nstruction Register Operanun mm Register femh readout readstore wmeback 34 Three instruction formats op rs n rd sh fn 15 10 15 I0 5 U 51m l a m r hil I a In a bus r hils l Upran Scum snurrn Ivewnannn shm lu39mle ngnvvr 1 vgimr 1 n ghu39r mmum I39Vlvminn DJ rs rt 0 Drilluln sl l H I 11 10 I5 quot l I n my I hm 5 hm 1mm OpiumJ SuurLE sslindnun Immeume upEmnd Ur Imo u dam Ur Andre millx u quotum m 2 address H P 2 39 P 5 0 ll lms I 2mm I am Mo Ml mnry wum uldm mm mm lwixlm Ivy 4 R and I types of instructions up rs n rd sh in c 5 20 1o 5 o uiu u o ulw 0 0 uiulx o u o wlu u u olu o 0 u ulw u o u x 0 A t source 0 39nalion Unust add 2 register 2 vegism sub L Sourcr mstmmon regime I 0 rs rl r uperandu 39sel 19 h IUUl0000000lIUUUUOUUUUUUUUlllIUI Smurrs Diwlinmion Immodinke upemml 35 LoadStore instructions rs rt 0 erandoffsel 25 20 15 P 0 wlw on wln x 0 0olnn unloononn x 0 nal se Dala O Tsct relative to base rcgmcr rogislc Memory Note an base and offset Address m mm hm mgisrer The memory Add A 1 of 51 Andi l Cal ing one 01 these Am and me nLher me wise 39 ohm 4 arhilrmy n wumd make period 2 sens m i 1 Ftp H19 addmss 39 A 55 A hdvm he bmeA Am 7 7777777 uement and 1va o sel 5M However 0 may A a 164 base confiws us In a 5mm pomon of ummy spare lui instruction up rs rt operandoffset amp z 5 2 n 1 5 u IIOUWiiIUUUUUITUUUOIUUUUUUUUUUI1110139 lui 15 Hmm Dmlhmliy Immmiimv npmml IUUUUUUUUUOIIW10WIOUUDUUUUUOUUDOOUI Commquot nf 50 Mlcr lhr imlnn inn is chllcd Jump instruction 3 up 23 lump Iargel address U 13911 11 n o 1 1 l x 1 nl me Pr Hfrlrlivc mrgm quB 112 hi1s 0 rs rl rd sI I n 1 P 1 111 I39 111 1 1 I11 11 n n 1 1391 1 1 I 1 11 111111 on on n 1111 on 11 on 11 1 u 11ml A1 11 snune 11mm Unust Unust 39 Hmrmliun ragislcr Conditional branch and comparison instructions 3 1 up rs n cperaudomeu 1 Ilnlo t 1 o 20 15 1 1 1 1 Ulo lln o 0 0 lnlo t 1 0 0 0 Ulo l I I I U N Source Zero Reialive bmnch distaan 111 words 31 op 25 rs 20 rt 1 S operandoffset 0 IO O DI 01x1 D O O III 0101 olo o oomo o D O O I I 1 110139 1qu a Source 1 Source 2 Rrialivchranchdlslancc1n words LL 5 up rs H in 31 25 20 15 M 10 5h 5 0 kluloia u u1010u1 01u101110 0 u 13913 0 uuo101010 d7 A1 U Sounx 1 Sourcc 2 Dcsunauon Unmml 51 instrumon reg1 sm legism 3 1 2 Is 20 n 1 5 operand0mm llUlO 01OIIO UH HI10 010139010 000 0100 010 1 1 1101 51 in Source Desn39nanon Immedialeoperand 37 Addressing mode Atltitrtssiug Inltlrn irin Ulhcr 39II39HWIIIS Invtt vt d pcmntl tmpnm 1 mm in llte marhine ltutttrvriinlrv E Roi iwr Reg Ii c Rog dam Rvgislr39i r Ml mory Mum ltliir Mam t39l illlrllivi ddiir g Lunslaul ut tset Reg Psr urlnrlirrrl Summary of instruction set class instruction Usage Meaning op fn Copy Load upper immediate lul rt 1mm rt e imm0x0000 15 Add add rd rs rt rd e rs rt 0 32 Subtract sub rdrsrt rd e rs7 rt 0 34 Arithmetic Set le 51 rdrsrt rd eif s lt rd then 1 else 0 0 42 Add immediate addi rtrs1mm rs imm 8 Set less than immediate sitr rt rs 1mm rt e ifrs lt imm then lelse 0 10 and rd rs rt rd e rs A rt 0 36 OR or rd rs rt rd e rs v rt 0 37 XOR xor rd rs rt rd e rs e rt 0 33 Logic NOR nor rd rs rt rd e rs v rt 0 39 AND immediate andl rt rs 1mm rt e rs A imm 12 OR immediate orl rtrs1mm rt e rsv imm 13 XOR immediate xorl rtrs1mm rt e rs imm 14 M Loadword 1w rt1mmrs rt ememrsimm 35 my me Store word 5w rt 1mmr5 memrs imm e rt 43 Jump 3 L goto L 2 Jump register 3 r rs goto rs 0 8 Branch on lessthano bitz rsL ifrs lt0then gotoL 1 Control transfer Branch on equal beq rs rt L if rs rt then goto L 4 Branch on not equal brie rs rt L If rs s rt then goto L 5 Ju l L oto L 3 System call syscall See Section76 Table 72 0 12 r eeptfor and tt39 L w L Table 51 38 Summary of MiniMIPS instruction format 31 quotP 25 395 20 n 15 quoti 10 sh 5 fquot o R 6 hils 5 bus 5 mm 3 bus 5 bus 6 bils Opmde Source 1 Source 2 1 Destination Unused Opwde ext I or haw or desl n 1 mm I jla 5 Jump largcl address 24 bus I lnsl I lnslructlon 32 bus I Floating point instructions computation and conversion 0 ex 51 M in 31 P 25 20 IS 10 5 Flo i oo o ilou ooxlo 0 1alo Hoo oltJ oo u oltxor3x xxl Hoarmgpoinr s o Sour e Source Destination add 39 a 1 regwsterl regwster regwster sub t ul div eg op ex 395 id in n 15 20 h lo 5 o FmIonnnuotvxonouuuwooununouinnxxx llonling pmnl kw o Unused 50mm Dmllnauon Tol ormm insmuliun ms 0 rPgNer i l r s 32 wd 1 d 33 1 w 36 Data movement and comparison ft f id f 11 quotP 25 ex 0 1r 5 1o 5 quot 11 ro1 011113900011 gt1 0 010 o ale 1 110 nlo 1 o 10391100111139 Hmtingpoinl 5 o Unused bourcr Domination mov e 6 insmlrliuu d 1 regiexer register 0quot 25 395 211 n 15 quotI 111 sh a iquot u J1 R01000100Xl30071DUIUWUOUIUUUUOIUUOUUDI Hualingelmml mfcl 0 Smlru39 Doslinalluu 11mm 11mer I union mt A 4 mmslvr H EiSiEr ri operandoffset 31 25 20 15 390 1 0 0 0 1lo 1 0 o olo o oro xlo 0 0 0 010 s o o o 1 1 1 O set oatingpoint bcl mstmcrion 0 ex id in 31 p 25 20 15 1o 5 Flo l u o o 1lo o o o x 0 I oia olo 0 0 0 olo o o o ulo o o Floatmgepomr s o ource Source Unused ceq instruction 6 1 registerz registe c1t c1e Floatingpoint instructions lass Instruction Usage Meaning ex in Move sdregisters mov fdfs fd efs 6 Copy Move fm coprocessorl mfcl rtrd r1 era move fpmgtoCPU 0 Move to coprocessor 1 mtcl rd rt rd rt move CPU reg to fp 4 Add sin ledouble add Ed is it fd lt f5 ft 3 0 Subtract smgledouble subf fdfsft fd fs ft at 1 uluplysmgledouble mulf 11 re fd f5 11 v 2 Dwidesmgledouble le fdfsft fdltfs ft 3 3 N mmet c N 1 ldouble neg e 65 change signbit v 7 d ceq f t iffsfilsetfp agtotme 50 Co arelesssd c it f5ft iffslt lsetfp agtotme at 60 Compare less orequal sd c1e f5ft iffs setfp agtotme at 62 Convertimegertosingle cvtsw fdfs fdes pfsfsisinteger 0 32 Convertimegertodouble cvt d w fdfs fded pfszfsisimeger 0 33 Convertsmgleto double cvt d s fdfs f d pf 1 33 C quote 5 Convert double tosingle cvt s a fdfs fded p slevenfs 1 32 Convertsingle to in ger cvt w s fdfs demos 0 36 Convert double to integer cvt wd Ed is fd ein fs even fs 1 36 Load word coprocessor 1 lwcl ft1mmrs ft e memrs imm rs Memory access Storewordcoproeessorl swcl ft1mmr5 memr51mm em rs Branch coprocessor ltrue belt L 1mequot gotoL 8 C Sf Branch coprocessorlfalse bclf L falSequotgotoL 8 is sd for singledouble is 01 fol singledouble 40 DSP Instruction Set Architecture Case Study TMS320C67 13 What is DSP n A digital signal processor DSP is an integrated circuit designed or ighspee a a manipulations for example audio video and Analog Compute QuiilllllllllllllW Q quot Digital Computer ash A quot 7 7 V a 7 sumquot W in mm DSP of Analog Signals analog to digital converter analog world ahalog reconstruction t dlgltilll world filter 0 ana 09 converter Characteristics of DSP Applications El Computationally demanding multiply multiplyaccumulate El Stringent realtime requirement El Streaming data El High data bandwidth El Predictable program flow A Typical DSP System gm lt2 lt2gt 7 iv Computational Architectures von Neuman Machine A STORED PROGRAM INPUT 2157 A ADDRESS AND D UTPUT umr D DATA DATA Harvard Architecture A A STORED 357 NPUTI STORED PROGRAM UNIT OUTPUT DATA gt H D Modern DSPS El Texas Instruments l TMS320C6X DSP famin El Freescale l MSCSlXX multi core DSP famin El Analog Devices SHARC Blackfin C67X DSP Roadrnap Perfnrmance 15 39 JDHDMFLDPS alldhevon C6713 DSK Overview El 225 MHz TMS320C6713 floating point DSP El AIC23 stereo codec I 892 KHz sample rates El Memory I 16 MB dynamic RAM I 512 KB nonvolatile FLASH memory El General purpose 10 I 4 LEDS I 4 DIP switches El USB interface to host PC C6713 DSK Physical Layout microphone imainpu Iineumpui hen pnune ampm lnput 5mm SI moi stereo Functional Block Diagram Host Port Int Emb dded JT G Ext JTAG J e A m m 3 0123 C6713 DSP Features I HighestPerformance FloatingPoint Digital Signal Processor DSP Eig t 32Bit InstructionsCycle 3264BitData Word Advanced Very Long Instruction Word VLIW TM8320C67X DSP Core Eight Independent Functional Units T 5Fixe rant 2 FuurALUs Fluatmgrand Fixedrant n Twu Muinpirers Dating and a Fixedrant LoadStore Architecture With 32 32Bit GeneralPurpose Registers L1LZ Memory Architecture AKByte LIP Program Cache DirectMapped AKByte LID Data Cache 2Way yum M TotalMVRtr PM mm mm ddmni L2 Mapped RAM Enhanced DirectMemoryAccess EDMA Controller 16 Independent Channels Two Multichannel Buffered Serial Ports SacialPeriphemlInterfaceSP1 HighSpeed TDM Interface Ac97 Interface U U DU C6713 Block Diagram um A C6713 Data Path u 2 Data Paths n LVUW L1 L2 a 8Functwona um Foatmgrpomt 407m IntegerALU EwtCounungNormahzauon 2Hoaung pomtAnmEnenc E39 S UW 5152 2 Hoaung PomtAuxmarv I m El Cmtlrdd d t HA LA p5 n epen en Up t0832rb t1nstmcnons a M1 ME I grammg El Regwsters y 2m umpher Integerz oatmgrpcmt 32327bwtregwsterstotd a DrUmtD1 D2 39 Crosspams xy gt0 327bxtaddsubtractAddrCa cu atwons mm mm gtM am mg Sn1555 ram M7 m lmwa s Function Unit amp C sumll SL 52 Advanced VLIW VelociTI Example 1 E in Example 2 Example 3 Fetch Packet fetches 8 instructionscycle Pac et executes 1 to 8 instructionscycle Fetch packets can contain multiple execute packets Parallelism determined at compileassembl ume CPU Execute a CPU Examples 1 8 parallel instructions 2 8 serial instructions 3 Mixed Serialparallel Groups Reduces Code size Numbe of program Fetches on Power Consumptl mos imxm Pipeline Fetch Decode Execute PSPWPR DP DC E1 E2 E3 E4 E5l nOperate in Lock Step 1 Decode n Fetch I DP Instruction Dispatch I PG Program Address Generate I DC Instruction Decode I PS Program Address Send a Execute I PW Program Access Ready Wait I E1 E5 Execute 1 through Execute 5 I PR Program Fetch Packet Receive I E6 E10 Double Precision Only Execute Packet 4 Execute Pac et WNW Delay Slots Delay Slots number of extra cycles until result is I written to register file I available for use by a subsequent instructions I Multicycle NOP instruction can fill delay slots while miniml ing code size impact Most Integer No Delay 4 SinglePrecision 3 Delay Slots Loads 4Deay Slots Branches V 5 Delay Slots Branch Target mmm Addressing Modes 1 Indirect addressing l R Register R contains the address of memory location l R d Postincreamented with modi cation I R d Preincreamented with modi cation I R d Preincreamented Without modi cation I Circular addressng I Address is bounded to a range I Controlled by AlVlR register AMR Register 31 26 25 21 20 16 Resewed BK1 3K0 RO RWO RWD 15 1413 1211 109 87 65 43 21 0 D7 MODE ES MODE 35 MODE B4 MODE A7 MODE A6 MODE A5 MODE A4 MODE RWD RlWO RW O RWD RlWD RWO RNVO RW O Legend R Readable by the MVC lnstructlon W Writeable by the MVC mstruction n value after reset Example AMR 0004 0001 h LDW Dl A4 9 Al Before LDW 1 cycle after LDW 5 cycles after LDW 10 m m m m TEXAS INsrnuers Cross Path Constrains i There can be at most two instructions per cycle using crosspaths Vain ADD Ale AlBlAO MPY M2X A2BZB3 Invalid ADD le AlBlAO MPY Mlx A2B2A3 Load Store Constrains El Address register must be on the same side as the D unit Valid Invalid LDW 131 Al A2 LDW D1 A1A2 l LDW 132 B182 LDW D2 A3 B2 El A load store using one register file in parallel with another load store must use a different register file mim Invalid LDW Dl A0Bl LDW Dl A0Al STW 132 AlBE ll STW DZ A2B2 LDW 131 AOB1 J LDW D2 B2Al Assembly Code Format A specific address or memory location Label Instruction Unit Operands comments instruction Load Store Instructions LDH D2 B2 B7 loadB2 7gt B7 incr B2 LDH Dl A2 A7 loadA2 7gt A7 incr A2 LDDW Dl A10l AlA0 load two 327bit words to register pair STW D1 A1 A48 store AlegtA4 offset 8 Branch Instructions El Branch using a displacement Unit can be 51 or 52 B 51 LOOP ADD Ll Al SUB D1 A5 A0 A2 A6 A3 LOOP A6 El Branch using a register I Only on 52 B 52 B10 Integer Instructions n Arithmetic instructions ADD Ll A3 A7 A7 a Move instructions MVKL 51 x A4 MVKH 51 x A4 MVKLH 81 X A4 move 1 Comparison instructions CMPEQ CMPGT CMPLT A3 A7 7gtA7 move 16LSB5 of X 7gt A4 move 16MSB5 of X 7gt A4 Xltltl6 7gt A4 CLR Clear 21 Bit Field El Syntax CLR unit scm csta cstb dst or CLR unit scm srcl dst L cstb J csza 5 52 lexlxlxlxlxlxlxhlolquotIDIOI1I10I1Ixlexlxlxlexlxlxlxlxlxlxlxlxl I32925272635242372212015varIBImnmnlo9a755132tu dst xxxxxxxxOOODOOODDx xxxxxxxxxxxx 313029232726252423222120v9vamxslaumuum9a7554az u nzw FNSWUMEN I S EXT Extract and Sign Extend a Bit Field El Syntax EXT unit scm csta cstb dst or EXT unit 5rc2 srcl dst lt cstb Eta 1 313029282726252423222126191517V5151A1312111D 9 a 7 6 a 4 a 210 Then shw s right by 23 to produce an 29 23 2726 25 24 23 22212019181716 5 M d 3 11111111111111111111111EEEEl 31 1 1312111DSB7654 0 Tim mmwsm Floating Point Instructions n Arithmetic instructions ADDSP ADDDP SUBSPm 1 Conversion instructions DPINT DPSP m Multiplication Instructions Integer MPY MPYH MPYHL MPYHLU MPYHSLU MPYHU MPYHULS MPYHUS MPYLH MPYLHU quot 39 MPYLH MPYLHU MPYLSHU MPYSU MPYU MPYUS Floating point MPYDP MPYSP MPYSPDP MPYSPZDP 22 multiplication instructions in total Example Dot Product C float dotpfloat a int i float sum for i 0 i lt 200 l sum ai bi39 return sum float b LOOP i All Assembly MVK s1 200 Al ZERO Ll A7 LDW Dl A4 A2 LDW Dl A8 A3 NOB 4 MPYSP Ml A2 A3 A6 NOB 3 ADDSP Ll A6 A7 A7 SUB 81 Al 1 Al B 52 LOOP NOB 5 Double Word Loading N m w 0 LOOP LDDW L U U S I m a m m ADDSP ADDSP 39 bra NOP ADDSP NO 81 100 Al Ll A7 L2 B7 Dl A4 A3A2 D2 B4 B3B2 81 Al 1 Al 2 82 LOOP Mlx A2 B2 A6 MZX A3 B3 B6 Ll A6 A7 A7 L2 B6 B7 B7 nch occurs here 3 Ll A7 B7 A4 3 Optimization with Software Pipeline B E 83 Schedule Table of Dot Product After Software Pipelining far Flnating Point Implementation Lao Cycle quot9 Unis 1 2 a A 5 s 7 a 9 in D1 LDDW LDDW LDDW LDDW LDDW LDDW LDDW n2 LDDW LDDW LDDW LDDW L D M1 MFVSF M2 MPVSF LI L2 si SUB SUB SUB SUB 52 B B B B lns irumunsmthe rs iiteratmn m quotGnu ms Assembly Code for Loop Kernel rcycles 104m loop kernel LDDW m A4vAzA2 32441 data in A2 an A3 55 1 l l H 54 53 32131 d n E2 and 53 l sl A1 1A1 ydecrement court H 52 00 branch to LOOP H A2BZA5 rlower 3 39 roduct into A6 H AEoE5 7upper 3 bit product into as H A6A7A7 7accum in A7 ll 13513757 accum in E7 The loop kemel can be done in one cycle Example Fast Fourier Transform Discrete FFT CooleyTukey algorithm radix2 DIT case Ll 7m m 71 in m 39 Xk Zyimoxgme N HZwunm e Na 5 Mr m A MA amk m quot399 N m wzmc M 12quot e M EA 67Aok if 1c lt M EH clt gt0H if k 2 M DFT Butter y Diagram N8 Wk sankN 1 M0 gtlt2v w w nap v7 X I quotaquot M xtz E X xm m gtltgtltgtltgtltL Lfgtltw XXV m w x5 If gtlt3 Wquot W m Butter y Diagram Input x X V j 2 Output w r m X A XX Outoforder m w d A d WXXXX M xm M r a 5 m X w M w r m r 7 xm n1 1 gt04 Max 2 m XX A X m m XX X m w a m 7 KW W11 4 m a w 7 Km Implementation in C vom DSPFispicfftrZJZut float x float w short n short n2 1e 1a 1 j k m float rtemp itemp c 5 Number ofstages forkn k gt 1 k gtgt 1 s XZml 7 s X2m7 rtemp itemp rtemp itemp 1a n2 1e ltlt 1 Stage k Cell N 2 N 2 N 2 H subgroup Zk39l subgroups in total Avmlemmmbw Addelemm Abgmp AAAAAA Am 5 mm AAA Am 5 mm AAA Dpru Xixptg await Implementation In Aw A Ainz Am Az 3AA A A A Am Amp m Lmear Assembly Dimp MV A Aicnt lune 100p ant Code 3AA AEAz A A A2 PEA Am up A MD AA Ann ajgu 8 a AAA w pt Aw Am Amp m m Am AAAAA Am AAAA m AAAAA m We m Aw Am AAAA m Aw m We pt Amp l l A xian l l 53dan lm 163d 5 met We pm me We m load gtltZm1 gtltZm A 1 MV A71 an mm A m A A A FA MPYSP Arxzm E s a pq mm AixzmpA n Aipz MPYSP AgtltZmp1 512 Ap3 Am A FA A pz A A sum A33 A334 new Am Aw AiszApnAiszA AAAA HZAAHMZAA SW A szA A new A m mmmmmmp my 532m Agnew Ax21as XZlBXZLBrtEmp suasp a szapma 1temp a mep15 xzm1 zAanrxtemp my aszap1aAcemp aszap1xzAA1 Zla1tampmp ST A W A AA mm AAA 3m A leas E xs 3m rxzmps rxs 3m synapsnixsw A mm A A A A M Am Amp m Aimm A may 7 Ach 3AA A A A A A AAA We Amp m A711 a 0100p branch outer loop 20 Scheduling Table 12 13 12 0 3 4 a 6 7 10 11 14 15 16 19 20 1111 LDDW LDDW Load 57w 57w gtlt21agtlt21a1 Dz LDDW 57w 57w 1M1 WYSF uz IMFYSF WYSF 1L1 ADDSF ADDSF SUBSF Lz sum sum ADDSF 51 p p 52 gtlt2mgtlt21a The End 21 ABC ofComputer Security L CON N Z Jerry Shi Department of Computer Science and Engineering University of Connecticut CSE5095 Qaecial Topics in Computer Engineering What is security Con dentiality Integiity Nonrepudiation Authentication Availability Access control Trust PIivacy 7 Anonymity What are these people doing Cryptographer cryptography 7 Design security systems Cryptanalyst cryptanalysis 7 Break security systems Cryptologist cryptology 7 Do both Classes of cryptographic algorithms Symmetrickey algorithms 7 Use the same key for encryption and decryption 7 Block ciphers 7 Stream ciphers Publickey algorithms 7 A pair of keys one private and one public Hash algorithms 7 Message digest Based on primitives we build cryptosystems Based on cryptosystems we build protocols Con dentiality Symmetrickey ciphers 7 Use same key for encryption and decryption 0 Sometimes two keys are not identical but trivially related 0 Block ciphers 7 Divide the message into blocks 0 Stream ciphers 7 Can do encryptiondecryption bit by bit Kerckhoffs39 assumption The system must be practically if not mathematically indecipherable 0 It must not be required to be secret and it must be able to fall into the hands of the enemy without inconvenience 0 Its key must be communicable and retainable without the help of written notes and changeable or modifiable at the will of the correspondents It must be applicable to telegraphic correspondence 0 It must be portable and its usage and function must not require the concourse of several people 0 Finally it is necessary given the circumstances that command its application that the system be easy to use requiring neither mental strain nor the knowledge of a long series of rules to observe Block ciphers Provides con dentiality 7 When used properly Building block in many protocols 7 Even in authentication protocols Kerberos Used as pseudo random number generator 7 Used to construct stream ciphers Faster than publickey algorithms Can be Viewed as a simple substitution cipher 7 2 Substitutions for nbit blocks Block ciphers for con dentiality Plaintext C iphertext to C iphertext Key eg DES AES RC6 MARS Serpent Twofish Kasumi RC5 IDEA etc Breaking a cipher Plaintext C iphertext C iphertext Bruteforce 2quot trials for 11bit key Cryptanalysis CipherteXtonly attack Knownplaintext attack Chosenplaintext attack AdaptiVchosenplaintext attack Chosenciphertext attack Chosenkey attack Rubberhose cryptanalysis 7 Purchasekey cryptanalysis Breaking cipher Total break 7 The key can be recovered Global deduction 7 Another algorithm can generate plaintext without knowing the key Instance deduction 7 A specific plaintext can be retrieved without knowing the key Information deduction 7 Attacks can know some information about the plaintext and key Unconditionally secure 7 Bruteforce attacks Computationally secure Earlier ciphers Polyalphabetic cipher Substitution based ciphers Caesar cipher 7 Each letter in the plaintext is replaced by a letter at some xed number of positions down the alphabet Enx X 11 mod 26 Breaking Caesar cipher 0 Try all possible shift amounts 0 Frequency attacks 7 Pattern U12 5533 333 q shade Letter ipher igenere c V 0 A serials of Caesar cipher speci ed by a repeated keyword EN ABlt39DEF AABLDEFBHI BSCthGHI JKLMuovunsruvwxvz JKLMncPunsruvwxvz JKLMNOI UIISVUVWXVZA P K mod 26 C Example P ATTACKATDAWN K LEMONLEMONLE C LXFOPVEFRNHR IKLMNovopsTuvu em N NXYZABEDEF KLMNDFURSTUVWXV n E 5 n a I Tabula Recta ZZABK Breaking Vigenere cipher Dif culty nd the length of the keyword 7 Once the length is found frequency analysis can be applied Method 7 Kasiski examination Charles Babbage and Friedrich Kasiski 7 Friedman test William F Friedman Index of Coincidence Kasiski examination 1 Find the repeated groups and nd the distance between them 2 Factor out each of these numbers 3 Identify the ones with high probabilities Friedman test Pl Two randomly chosen letters from the language are the same 7 0067 for monocase English Pa Two randomly chosen letters from the alphabet are the same 7 126 00385 for English P0 Observed coincidence rate For atext ofN letters 7 n1n171 nzquot n2 7 l n26n267 1 NN 7 l26 Estimated length P1 7 Pa P0 7 Pa The accuracy can be improved with the index of coincidence Improving Vigen re cipher 0 Running key cipher 7 Use a book as a very long keystream 0 Both parties agree on where to start 7 Security 0 The entropy of the key is low 7 Use a better book almanacs or trade books 0 Key space is too small 0 Autokey 7 Attach the plaintext to the keyword 7 Weakness the relationship between the key and the plaintext The Enigma machine Some other simple ciphers ROTl 3 7 Caesar cipher with a shift amount 13 XOR cipher 7 Each byte in plainteXt is XORed with a key byte Beaufort cipher 7 Use plainteXt and key to locate a letter in a table and the row number is the cipherteXt One time pad Vernam s patent US patent 1310719 7 Combining two codes with XOR Although the term XOR is not used in the patent OTP XOR plaintext with random key bits The key is 7 Secret 7 Truly random 7 As long as the plainteXt 7 Used only once Perfect security 7 Problem Techniques in symmetric key ciphers Claude E Shannon quotCommunication Theory of Secrecy Systemsquot Bell System Technical Journal vol284 page 656 715 1949 Confusion obscure the relationship between the plainteXtkey and the ciphertext 7 Sbox nonlinear substitution Diffusion dissipate the redundancy of plaintext by spreading it out over the ciphertext 7 Permutation Substitution Permutation Network SPN ciphers Composed of a number of stages involving substitution and permutation plamtext Sample SPN p I Lunsz PM 111 HII39iIHH i nrlwll 4 hum 1 1 J J Mimi Hi I J i P x I 34 5 I lll HH HHII J x 1 i 1 quot39 i1 J V 4 iphmA v C v Feistel ciphers Round function in a Feistel cipher 7 Does fneed to be invertible i1 LiRi1 R1 Li1 fRi1 Ki Iterative structure of block ciphers Plaintext Number of rounds Operations in a round Ciphertext Commonly used block cipher DES Data Encryption Standard 7 3DES AES Advanced Encryption Standard RC4 RC5 RC6 7 Fast IDEA And more Electronic Codebook ECB mode F awmexi P aimexi IIID x mm Cipher mack ther mm prher Key 7 Encryptron Key 7 Encryption Key 7 Encrypmn ML LLH UJ cmnmm cipnenexx Ciphenext E ectmnic Codebcok ECB mode encryption thenext C pherzext Ciphenexl 11 Tr r V i Emu cxpner Black mm mm Cipher Key 7 Detryplion Key 7 Decryptxun Key 7 Detryphnn LLLUZLLEI LILLle ling P ainlext P amtext Plaintext Electronic Codebook ECB mode decryption Cipher block chaining CBC mode Plamtexl mamm F amtext I z w w I mmauzauon Vector uvx I mack mm mm C Dher mock Ember Key anuyptmn Kev Encryptvon Kev Entryptmn x r w w w 1 x w 1 Iphertext prherlext C pherlext Upher Block Chaimnq CBC mode encrypt on nmmanan Vetmr HV Gunmen C phenexr Cipherrext mm clpm Black Cipher monk cums Key 7 Detryp nn Kay 7 Bethyuan Key 77 Derryplmn v v v L Pramex Flarnlexx P alntext Cipher Block Chainan CBC mode decryption Cipher Feedback CFB mode lnmalizatlon Vector va x x v 39 v mock C pher mock C pher Black ClphEr Key 7 EMryplmn Key 7 Encryptlon Kev 7 Enzryptiun memzext P amtext H LM71 H H 7 Plntext 139 m v 7 Hum HLH HH H Ciphenexl thenext prhenaxt Cipher Feedback CFB mode encryption lmt a izatmn Veztnr uv III 771 i l amzkc her ElotkCIpher BYnekC r Encryptlnn Key 7 Encrypliun Key Encrypllnll 7C Imx quot47W n 7D C phenext C phertext p enext g iuALu V T ALi L MJJ memen F s ntex Plaw ntext Cipher Feedback CFB mode decrypmn Output Feedback OFB mode minaHzauon VezlorHW x w w x w meek Cipher Key 7 Encrypnon u mock cmher Elutk Cipher Key 7 Encryption Encrypnon P a t xt Marncen m 7 g m w v Key 4 Fla ext DILEELLI 7 u 7 w w w w w w prhertext xt Output Feedback OFB mode encryption lnmallza nn Vector WY CDIEE 39 Block Cipher mack Cypher Shack ther KEy7 Encryption Key 7 Encryp an Key 7 Enerny n C phenext J C phertext Ciphenext m7 m 7 W m 7 w v v HHMM HM P alntext 1 P amtext Output Feedback OFB mode decryption Counter mode Nunte Counter Nance Counter Nome Counler cssmss ooooouoo sancias noououm cssbcras ououoau nm nqun rm 1713 W n v friH Key 7 Eluzk Clpher Key 7 arm Cipher Key 7 Elnzk Clpher Encrypan Encryptinn Enuynhnn P amtext P amtext merncexc rm mw r m dm r n Illll r r r crpnenexr Ciphenext Clpnenexl Counter cm mode encryption Nome Coumer Nance Cwnler Name Coumer zssbzfzs nuuuuauu zsabzfas mmmmm 59mm ununuuuz m mr 7quot em Cipher u n Key Blnzk iphar Key Harm mpner Key Encryptlan Encryyklnn nuyp n Crphenext e crpnenex Ciphenexl r mnmn n 39r n umme n 4 11 39 L r 39 r mm P amtext wemxm Counter 1Cl39R mode decryption Example Plaintext Encrypted with ECB mode Encrypted with other modes Chaining block ciphers Ciphers S1 S2 S3 S1 and S2 commute if S1 X S2 S2 X S1 7 Many ciphers do not commute Always associative S1 X S2 X S3 S1 X S2 X S3 Idempotent ciphers S X S S Ekl Ek2P Ek3P If a cipher is not idempotent iteration may increase security 3DES Ekl Dk2Ek3P Attacks on block ciphers Differential cryptanalysis Biham and Shamir 90 7 Relationship between difference of plainteXt and difference of cipherteXt Linear cryptanalysis Matsui 93 7 Uses linear relation of certain bits in plainteXt and cipherteXt Sidechannel attacks 7 Timing power radiation acoustic fault etc Differential cryptanalysis X1 Y1 X2 Y2 AXX1 X2 0P 0P 21 22 AZZl ZZ Characteristic AXAY gtAZ Desired in I Cipher Design I Attack Hamming weight ofAZ AZ Large Small Probability for given AX AY AZ Small Large A simple characteristic 0 6 gt AZ 6 W 1 and only bit I is 1 No difference in the rst operand Onebit difference in the second operand Attackers wants Hamming weight of AZ to be small 8 bit Data Dependent Rotation DDR Z X ltltlt Y X HHEIHH Data Y Control 394 U 1 U u z unannnau mwt DDR 0 egtAZ EAZn2for1gnbits 0 AZ 0 forotherbits X1 X2 10101110 10101110 Y1 Y2 nunlnana mullaann quot v v 39 IDDRI IDDRI 21 22 10111010 01110101 AZ11001111 AZ6 Differential propelties Operation 0 2 A ex 9 gtA DDR EQAD n2 When t lt1gn EOAD n2 when t lt1gn A 0 otherwise A 1 otherwise GRP For any I For any I EOAD 4 EOAD M4 OMFLIP AOor2 A10r3 CROSS GRP 0 80 gtAZ 714 for all bits X1 X2 10101110 10101110 Y1 Y2 10110010l 10110011l V7 V7 I GRP I I GRP I 21 22 01101101 01111010 AZ00010111 AZ4 20 GRP has the best differential properties Operation 0 2 A ea 9 9A DDR EQAD n2 When t lt lgn EOAD n2 When t lt lgn A 0 otherwise A 1 otherwise GRP For any t For any t EA 714 EA 714 OMFLIP w 0 or 2 w 1 or 3 CROSS Avalanche effect If an input is changed slightly the output changes signi cantly 21 Linear cryptanalysis notation F A word used to select bits from another word X I F Parity of bits in X specified by bits in F eg 0110110101111 Approximation X 017 Y Z approximation TX Ty Fz OiFx YFyZFz p probability of the above equation bias lp 7 12 l Desired in I Cipher Design I Attack Bias lp 7 lZl I Small Large Result DDR has better linear properties than GRP 22 Crypto hash functions Transform an input message of an arbitrary length to a value of a xedlength which called a hash value or a message digest HM 7 x Three properties 7 Preimage resistant Given x difficult to find M such as X Hll 7 Second preimage resistant Given Ml difficult to find M2 such as HMl HM2 7 Collision resistant Difficult to find two messages M1 and M2 such as HMl HM2 Generic attacks on hash functions Assume a hash value of 71 bits Onewayness 2 1 Second preimage resistance 2 1 Collision resistance 12 X 2 2 7 Birthday attacks Implementation of birthday attack 7 Store all previous results and search for the new hash 7 Cycle nding algorithm eg Floyd s algorithm HHX HX 23 MerkleDamgiird construction Message with padding A Initial Value F Compression Function Some properties are the same as block ciphers eg avalanche effect Can be constructed from block ciphers Hash based on block ciphers DaviesMeyer Emii1iil1 i MatyasMeyerOseas Hi EgHii71mi mi MiyaguchiPreneel EgHiirlmi mi Hpi MDC2 by IBM 7 Two MatyasMeyerOseas in parallel to double the hash length go is different Outputs of compression functions are mixed AB CD 9AD CB MDC4 7 Each iteration contains two sequential executions of MDCZ 24 Commonly used hash functions MD5 SHA family 7 SHA0 SHA1 and SHA2 Whirlpool Tiger RIPEMD128160256320 7 Improved version of RIPEMD The story of Alice and her boss Eurocypt 05 Caesar writes letter of recommendation Email from Alice Please digitally sign the attached letter Caesar Views the le signs it and sends signature to Alice Alice wants to forge Caesar s signature but she 7 Has xed target 7 Knows how to generate random collision Solution 25 Helping Alice 0 Use advanced document language Porstscript 0 Find random strings R1 and R2 and concatenate to some preamble X1 preamble put R1 X2 preamble put R2 MDSX1 MD5X2 Appending a string S to both X1 and X2 MD5X1H s M3509 H s Y1 preamble put R1 put R2 if then T1 else T2 Y2 preamble put R2 put R2 if then T1 else T2 httpth infnrmatik mi m quot14 im L quotP J quotIn h nlli inn Hash Tree Merkle Tree 0 Check the integrity of a subset of blocks Easy to update hash if one block is updated 7 Protect cache 26


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.