### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Advanced Applied Cryptography ECE 746

Mason

GPA 3.94

### View Full Document

## 22

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

This 124 page Class Notes was uploaded by Antonina Wuckert on Monday September 28, 2015. The Class Notes belongs to ECE 746 at George Mason University taught by Staff in Fall. Since its upload, it has received 22 views. For similar materials see /class/215029/ece-746-george-mason-university in ELECTRICAL AND COMPUTER ENGINEERING at George Mason University.

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

## Reviews for Advanced Applied Cryptography

### 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/28/15

ECE 746 Lecture 11 Random Number Generators Need for random bits in cryptography 1 Secret keys in symmetrickey cryptosystems User private keys in public key cryptosystems starting point of the incremental search for primes p and q in RSA private key x in DSA private key x in Dif eHellman System parameters in public key schemes 39 p q h in DSA p g in Dif eHellman Message private keys in randomized public key schemes k in DSA and ElGamal Need for random bits in cryptography 2 Initialization vectors IV in CBC CFB OFB CTR Block padding in encryption Parameters in security protocols challenges nonces What is a Random Number Generator Working de nition om Bruce Schneier The Output 1 Looks random passes statistical tests 2 Is unpredictable 3 Cannot be reproduced Kinds of RNGs Cryptographically Secure Pseudo Cannot be Random Number RBPYOduced Generator CSPRNG pseudo Random Unpredictable Number Generator PRNG Unpredictable Looks Looks Looks Random Random Random Entropy Entropy of a random variable X uncertainty about the outcome before an observation of X measure of the amount of information provided by an observation of X average number of bits required to encode X Entropy or Uncertainty of X Possible values of X X1 X2 X3 XN Corresponding probabilities p1 p2 p3 pN N HX Z pi10g2 i1 1 HardwareBased Random Bit Generators Underlying Physical Phenomena 1 Thermal noise from a semiconductor diode or resistor 2 The frequency instability of a free running oscillator 3 Time elapsed between emissions of particles during radioactive decay 4 Difference in charge between two neighboring metalinsulator semiconductor capacitors 5 Sound from a microphone or video input from a camera 6 Air turbulence within a sealed disk drive which causes random uctuations in disk drive sector read latency times Block diagram of the Intel RNG Voha e Contvolled Oscmator nghr Speed Osmllator Johnson Thema Nowse Source Reswstor DualOscillator Principle of Operation emal Nowse ngl39rf39f Le cy osmHalo Data to correcla39 quot HardwareBased Random Bit Generators Pros Cons Harder to integrate with E icienc y software 1mplementat10ns Good statistical properties EXpens1ve Subject to observation Subject to manipulation temperature May require deskewing removing biases removing correlations Sources of randomness in SoftwareBased Random Bit Generators system Unique Variable amp External Unguessable Random Cn gura on les Contents of screen Cursor position Druf con gurallon Date and time with time EnVerUment smngs High resolution clock Keystroke timing samples Microphone input Last key pressed with microphone Log le blocks connected Memory statistics Mouse click timing Network statistics Mouse movement Process statistics Video input Program counter for other Less processes and threads M0113 entropy entropy SoftwareBased Random Bit Generators Pros Cons Inexpensive Slow Poor statistical properties Easy to mtegrate w1th SO ware Subject to observation eg using trojan horses Subject to manipulation e g restart 0f the system Require multiple sources and a complex mixing anction SoftwareBased Random Bit Generators Rule of thumb For every BYTE of data collected at random there is one BIT of entropy Strong Random Bit Generator Random 1 Bit Generator eudorandom 39t Generator Next state Oneway Output genertiti function n 1 BSAFE 3x Random Bit Generator Pseudorandom Random State U 1 Bit Generator Bit Generator function Initialization 1 s00 0 State update function Next st Hsi1i Xj state Output function Hash i y function Output generizti n 11 ll 3 Next state function Sji Sji1Ci mod 2L CH 77 1 1 L bits Jp A Qw eP Design Goals Output indistinguishable from true random sequence Knowledge of some outputs does not help predict future or past outputs Make good use of entropy in the seeding material Guaranteed long cycle length Sufficiently large internal state to avoid exhaustive search Good performance Simple algorithm Design Objectives 1 Allow re seeding state update interspersed with output generation Generated bytes depend on all preceeding seed bytes State depends on the order of the seeding bytes passed to update function State update and output generation run in constant time to avoid timing attacks Use at most one underlying hash function Avoid the use of encryption functions to simplify export complience Generated sequence does not depend on the order in which groups of bytes are requested State does not depend on how seed bytes are passed to the update function N U A ONKJ 00 Resistance to Attacks 1 1 Exhaustive Seeding Search 2 Exhaustive State Search 128 bit state 3 1038 different states 1 bilion computers X 1 bilion statessecond X 3107 secondsyear X 1013 years 3 Malicious software attack eg reading internal state by a Virus 4 Forward tracking Possible until next reseeding Resistance to Attacks 2 5 Back tracking Possible back to last reseeding 6 Controlling seed bytes 7 Cycle shortening 8 Timing attacks ANSI X917 Random Bit Generator For DES keys and Vs Pseudorandom Ranoom Bit Generator Bu state S Generator Datetime D Initialization S1 seed 1 EKD Output function xi EKsi ea 1 Next state function 1 xi EKgtlti e I 64 bits FIPS 186 Random Bit Generator For message private keys k Pseudorandom Random Bit Generator Bit Generator Initialization 1Ski mod 2quot s1 seed t efcdab89 98badcfe 10325476 C3d2e1f0 67452301 Output function ki Gt s Next state function 1 SH1 1siki mod 2393 outpm ki 160 bits FIPS 1401 statistical tests 1 Input 20000 consecutive bits of output from the generator 1 Monobit Test A Count the number of 1 s in the 20000 bit stream Denote this number by n1 B The test is passed if 9654 lt 111 lt 10346 Choosing the acceptable boundries 1 The signi cance level of the test or Probability that the test will fail even for a sequence produced by a truly random bit generator Recommended values of or 0001 0o S on S 00100 Choosing the acceptable boundries 2 Type I Error Test rejects sequences that were in fact produced by a random bit generator Likely to occur for large values of the significance level g Type 11 Error Test accepts sequences even if they were not produced by a random bit generator Likely to occur for small values of the significance level g FIPS 1401 statistical tests 2 2 Poker test A Divide the 20000 bit streams into 5000 contiguous 4bit segments Count the number of occurences of each of the 16 possible 4bit values Denote the number of occurances of particular value i by ni 0 S i S 15 B Evaluate 5000 C The test is passed if 103 lt X lt 574 15 X i Z n 5000 10 FIPS 1401 statistical tests 3 3 Runs test A Run maximal sequence of consecutive l s or 0 s which is a part of a sample string Blockrun ofl s Gaprun ofO s Example 0110l11110100d1 block Of gap of length 4 length 3 B The test is passed if the number of occurances of blocks and gaps of respective lengths are each within the following interval 1 23152685 2 11141386 Leng fh 3 527 723 Required of run 4 240384 immal 5 103 209 6 103 209 FIPS 1401 statistical tests 4 4 Long run test A A long run is de ned to be a run of length 34 or more of either zeros or ones B The test is passed if there are NO long runs Other basic statistical tests Autocorelation test sampleStang OlOlOlllOlOlOllllOlOlOOOlOlOOlO samplemmg gtOlOlOlllOlOlOllllOlOlOOOlOlOOlO shiftedbyd Disagreements lOllllOllOlOOOlOlOllllOOOO ndl AdZsi sid i0 nd 4 X 2Ad 2 nd Xshould have The test is passed if normal d1str1but1on X l lt 196 N0 1 Maurer s Universal Statistical Test Basic principle It should not be possible to significantly compress without loss of information the output sequence of a random bit generator Features detects a wide array of statistical defects requires a much longer sample sequence compared to basic tests that detect individual defects 1 7 2 Q initial Lbit blocks 0111 0101 1101 0101 0110 1001 0001 0101 0011 01001001 4 9 K remaining L bit blocks Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 QK 1QK 001001110101110101000110100010011010 0111 0100 Maurer s Universal Statistical Test Q 2102L 2 3 4 5 6 7 8 9 Q1 5135 6915 3 K 2 10002L 7 5 13 4 6 8 8 10 7 4 TH last occurance of the block corresponding to integer j initialized using rst Q blocks of the sample sequence Ai number of positions since the last occurance of block bi A1 i Tiba de ned for Q1 Si S QK eg AQ5 Q5 Q 16 Maurer s Universal Statistical Test A Evaluate QK 1 Xu i 2 1g 2 A1 iQ1 B Accept if t1 lt Xu lt t2 t1 LL VG u uL given in tables t2 LL Y6 039 5L K Q given in tables 7 number of standard deviations Xu is allowed to deviate from the mean eg for a rejection rate 0001 7 330 Maurer s Universal Statistical Test Tables of means and variances L 11 a L 11 73911 1 07326495 0690 9 81764248 3311 2 15374383 1338 10 01723243 3356 3 24016068 1901 11 10170032 3384 4 33112247 2358 12 11168765 3401 5 42534266 2705 13 12168070 3410 6 52177052 2954 14 13167693 3416 7 61962507 3125 15 14167488 3419 8 71836656 3238 16 15167379 3421 Table 53 Mean 11 and variance 0392 2779 smlisffc Xu for PEI7110M sequences wit7 paranelm s L Km Q gt The variance of39Xu is 72 CLK2 oiZK wm39e CLK a 07 7 08L 16128L IquotVLf01K 3 2L NIST RNG Test Suite NIST Special Publication SP 80090 httpcsrcnistgovmg The Frequency Monobit Test Frequency Test Within a Block The Runs Test Test for the LongestRunofOnes in a Block The Binary Matrix Rank Test The Discrete Fourier Transform Spectral Test The Nonoverlapping Template Matching Test The Overlapping Template Matching Test 9 Maurer39s quotUniversal Statisticalquot Test 10 The LempelZiv Compression Test 11 The Linear Complexity Test 12 The Serial Test 13 The Approximate Entropy Test l4The Cumulative Sums Cusums Test 15 The Random Excursions Test and 16 The Random Excursions Variant Test 1 2 3 4 5 6 7 8 Diehard Battery of Statistical Tests by Prof George Marsaglia Florida State University httpwwwstatfsuedupubdiehard First published in 1995 on a CD ROM of random numbers Tests Birthday Spacings Overlapping Permutations Ranks of matrices Monkey Tests Count the Parking Lot Test Minimum Distance Test Random Spheres Test The Squeeze Test 100verlapping Sums Test 11Runs Test 12The Craps Test WSF P39 RENNE 0 CryptX Queensland University of Technology Information Security Institute httpwwwisi quteduauresourcescrythtestsphp 1 Stream Cipher Tests These tests are applied to the binary bit stream prior to mixing with plaintext 2 Key Generator Tests These tests are applied to the key generator blocks 3 Block Cipher Tests These tests are applied to output blocks from 7 highlypatterned data or 7 the bitwise addition of plaintext and ciphertext blocks or 7 the user39s own block data 4 Block Cipher Properties TRNG Market Survey by Mike Dugan ECE 746 Spring 2005 0 Establish Evaluation Criteria for Comparing TRNGs 0 Conduct a Market Survey for Commercially Available TRNG Implementations Evaluate Products Identify Entropy Sources How Would a System Designer Choose a TRNG and What Product Would They Select Evaluation Criteria 1 Statistical Veri cation Testing NIST SP 80022 DIEHARD CryptX FIPS 1402 2 Rated Speed Mbps 3 M Dependant on Form Factor Evaluation Criteria cont Form Factor Embedded or StandAlone Price 903994 Amount of SelfTest Veri cation Power Requirements Operating Temperature Entropy Source Not Considered in The Evaluation Because This is Transparent to the End User Market Survey Dnbedded Stand alone SafeNet39s SafeXcel IP TRNG EIP75a Protege R200 USE SafeNet39s SafeXcel IP TRNG EIP75b Protege R210 USE Protegeo R300 SMT Protege R230 USE In neon TPM Used on Intel P4 ME ComSciIe J1000KU USE IQ Quantique Quantis OEM ZrandomU SE ID Quantique Quantis PCI 1 or 4 chip ID Quantique Quantis USE Orion Products RS232 HG324 made by quotrandomcomquot RS232 Araneus Alea I USE 20 Evaluation Shortcomings Product Offerings Leaning Toward Total Cryptographic Module NIST CMVP FIPS 1402 Information Manufacturers Provide Very Little Detailed Final Evaluation Did Not Include Size or Operating Temperature Due to Lack of Information Without Any Details Fewer Products Than Expected Manufacturers Only Listed Ability to SelfTest Evaluation Results Power Requirements Were Very Similar and Therefore Not Included Embedded Verification Speed Mime Sell Test Price IE IQ Quantique Quantis OEM NIST amp DH 40 Yes 39399 SafeXcel IP TRNGEIP75b FlPS 1402 1320 Yes 7 SafeXcel IP TRNGEIP75a FlPS 1402 822 Yes 7 Protegeo K300 SMT 7 0 05 Yes 7 In neon TPM Used on Intel P4 MB No info No info 7 7 SLand alone Verification Speed Mime Sell Test Price IE ID Quantique Quantis PCI4 NIST amp DH 16 Yes 240573 ID Quantique Quantis PCIl NIST amp DH 40 Yes 1223 58 ID Quantique Quantis USB NIST ampDH No info YES 12400 I H3324 made by quotmndomcomquot NIST amp DH 12 7 32088 Amneus Alea I USE NIST ampDH 01 7 20490 Zrandom USB DH amp Poker 0 04 7 71400 Protege R230 USB CryptX 2 04 Yes 1279 50 Protege R210 USB CryptX 0 39 Yes 53500 Protege R200 USB CryptX 08 Yes 34500 ComScire J1000KU USB JS Coron 10 7 89500 Orion Products RS232 256 bit runtest 00076 7 65073 21 ECE 746 Secure Telecommunication Systems Course web page httpece omn quotWW 3636 inrie ht m ECE web page gt Courses gt Course web pages ECE 746 Sequence of the ECE cryptographyrelated courses Secure Telecommunication Systems 1 ECE 46 Cryptography and Computer Network Security ECE 64 every Fall every Spring1 Computer Arithmetic ECE 645 every Spring ECE 746 Part of Ms in CpE Network and ComputerNetworks electzve Certi cate in Information Systems Security Ms in EE Communicatio s Computer Engineering PhD in IT PhD in ECE Certi cate in Communications and Networking ystem Security requzred 5014752 NETWORK AND SYSTEM SECURITY Concentration advisor Kris Ga 1 ECE 542 Computer Network Architectures and Protocols SC Chang et al 2 ECE 646 Cryptography and Computer Network Security K Gaj lab project ClC VHDL or analytical 3 ECE 746 Secure Telecommunication Systems K Gaj lab project ClC VHDL or analytical 4 INFS 766 Internet Security Protocols R Sandhu Kris Gaj Research and teaching interesm I cryptography I network security I computer a1ithmetic I VLSI design and testing Contact Science amp Technology 11 room 223 kgajgrnuedu kgajOlyahoocom 703 993 1575 Of ce hours Monday 600700 PM Tuesday 730830 PM and by appointment ECE 746 Lecture Project Labmatory Homework 0 0 20 40 A 10 A Midterm exam I Spect catzun 7 5 in class Results 7 12 20 Oral presentatzun 7 10 Midterm exam 2 Written 72pm 7 8 takehome 10 REVIEW 7 5 projects A depth breadth Lecture viewgraphs chalk amp blackboard handouts of viewgraphs please extend with your notes books 2 required optional available on reserve in the Johnson Center articles Cryptobytes RSA Data Security Conf CHES CRYPTO etc web sites Crypto Resources standards FAQs surveys Homework reading assignments analytical problems theoretical problems may require basics of number theory or probability theory problems from the main textbook short programs literature surveys Midterm exams multiple choice test short problems practice exams available on the web midterm exam review sessions optional Tentative dates Exam 1 March 22 or 29 Exam 2 Saturday May 7 takehome Lecture topics 1 ALGORITHMS 1 Contest for the new Advanced Encryption Standar 2 Rijndael 7 ABS 3 Galois Field arithmetic 4 Stream ciphers 5 Review of public key cryptography 6 Elliptic curve cryptosystems Lecture topics 2 IMPLEMENTATION S 7 Smart cards and PCMCIA cards 8 Attacks against implementations 9 Security requiremenm for cryptographic modules FIPS 140 Lecture topics 3 KEY MANAGEMENT 10 Key generation and management Secret sharing 11 Public Key Infrastructure Lecture topics 4 SECURE INTERNET PROTOCOLS 12 Secure Internet Secure electronic mail Secure WWW Secure virtual private networks 13 Security in Wireless Networks Additional topics 4 Covered if the time permits TECHNOLOGIES OF THE FUTURE l Zeroknowledge identi cation schemes 2 Biometrics 3 Quantum Cryptography and Quantum Computing 4 DNA Computing Laboratory I 34 labs I done at home or in the ECE labs so ware downloaded from the Web I based on detailed instructions I grading based on Written repons Tentative list of laboratory topics 1 Properties and comparative analysis of publickey ciphers and digital signature schemes 2 Secure electronic mail 3 Libraries of operations on large integers and elements ofthe Galois eld Typical course dif culty This course dif culty Project 1 I depth originality I based on additional literature I you can start in the point where former students ended I based on something you know and are interested in I teams of 13 students I so ware hardware analytical I may involve experiments I over 15 project topics suggested by the instructor I you may propose your own topic Project 2 I about four weeks to choose a topic and write the speci cation I regular meetings with the instructor 3 and progress reports I draft version of viewgraphs and a nal report due Monday May 9 I discussion of dra reports and viewgraphs I short oral presentations Monday May 16 I final written reports due Monday May 16 I publication of reports and viewgraphs on the web Final Project Report Initial submission Paper for review I quot15 r r 11 pt rent Tim es New Roman or equivalent Title page Title authors abstract Figures included in the text Final submission Cameraiready copy IEEE form at published on the web Project Report Reviews Detailed evaluation form published on the web Reviews evaluated by the instructor based on justi cation of evaluation scores mistakes found and those overlooked constructive suggestions fairness Project Types Software Hardware program in a highlevel behavioral mode language c CH Jaw i HDL or assembler VHDL Verilog apped into FPGA or ASIC veri ed using timing simulation Analytical literature survey compamtive analysis ofcompeting algorithms protocols or imp1emen ations HVJPORTAN T RULE MS CpE Students specializing in Network and System Security Nl39UST choose implementation oriented projects ie Software Software Project topics Software Educational software for a cryptographic laboratory KRYPTOS OPEN SOURCE PROJECT httpwwwkryptosprojectorg Prerequisites CC Idea Develop extensions to the existing GMU educational software for teaching cryptography KRYPTOS Examples of tasks provide a choice of an underlying library currently only Crypto faster libraries available but more dif cult to integrate statistical tests for randomness of input output and intermediate results Comparative Analysis of Software Multiprecision Arithmetic Libraries for Public Key Cryptography High GMPNTLLiDIA CLN bu D 1 9 OpenSSL E MIRACL O quotifquoter PIOLOGIE Ash raf AbuSharekh LOW Cr toPP MS Thesis April 2004 LOW JPThgh Primitives Schemes Support Statistical Tests for Randomness Multiple tests for randomness available Public domain implementations of selected tests exists NIST Statistical Test Suit DIEHARD by Prof Marsaglia No clear consensus which tests should be used for testing true and pseudorandom number generators NIST standard in the initial stage of development CAMERA v10 by Mike Lyons Instructor in the BS IT and MS TCOM programs Design philosophy Enable experiential learning by creating an interactive environment learn by doing Make it visual images reinforce concepts co or and movement are attractive especially to young students User experience if Based on a graphical user interface GUI windows draggable icons mousedriven lookandfeel is native to the platform The user creates models by connecting icons representing processes When the model is run the processes are executed and data is passed between them according to the user s design The user controls execution and can examine and change data 10 Project topics Software Generating large primes for cryptographic applications Prerequisites CC or Java Assumptions AKS and FrobeniusGrantham algorithms previoussemester implementations in C and Java ine icient better mathematical analysis required better choice of library functions needed timing measurements for various prime sizes comparative analysis Projects Software Timing attacks against public key cryptosystems Timing cryptanalysis of RSA and ECCs implemented using publicdomain libraries of operations on large integers Initial implementation developed by Kevin Magee as a part of ECE 746 amp scholarly paper Hardware ll rrojeu loplLb Hardware Implementation of a selected publicrkey eg ECC RSA NTRU using FPGA devices Prerequisites VHIDL or Verilog FPGA or semicustom ASIC design Assumptions design in ahardvmre description language at the RTL level 39 39 39 39 spee minimumama yenfication using awilable tools logic synthesis to the gatestandard cell level static timing analysis and timing simulation possible experimental testing using the SLAACIV or Wild Star II FPGA boards Project topics Hardware Critical analysis of the existing implementations of AES Prerequisites basic understanding ofhardvmre and FPGA and ASIC design technologies There exists easily over 20 ditferent academic and commercial implementations ofAES in hardware Limited number of distinctly different architectures d implementation tricks Analyze and compare existing implementations and detennine which factors in uence most the performance o given implementation and how they can be fairly compared ainst each other Kinds of Random Number Generators c I nun se Cannnthg 139le ugnp z y cure Pseudu Ramlom Number REPYndncad GenentnrCSPRNG Pseudu Randum Number Generator PRNG Analysis of existing implementations of True Random Number Generators internal vs external hardwired v soft source of randomness principle for extracting randomness speed interface to user logic production test runtime test selftest validationcertificate reproducibility resistance to attacks Analysis of countermeasures against sideachannel attacks based on power analysis 16 rounds of DES JW WVWMW MAMm wamt mwhatumam WM x Wmm Wmmllgvkmmm JWW M MVMFW WVMI MW WWF WWKJ IWMIWLAJM DPA 7 Differential Power Analysis The most successfulpractical attack against implementations of crypt ography Existing countermeasures offer Hardware Software Cryptographic libraries for recon gurable computers What is a reconfigurable computer Reconfigurable processor system Microprocessor system V0 Interface H Interface V0 Recon gurable Computers from SRC Computers Inc and Star Bridge Systems Inc Reconfigurable Processor MAP Interface Card SNAP SRC Servers SRC Programming HDL HLL VHDL C uP system SRC FPGA system E E Library Application Developer Programmer Q v IDEAZ Modulo Multiplier Four Clock Delay m um D a Ile KEV S heets Library Starbridge Programming Object Project topics Hybrid SoftwareHardware Factoring of large numbers using recon gurable computer Prerequisites programming in C number theory basic understanding of hardware knowledge of VHDL helpful Assumptions analysis of available literature high level design speci cation of basic components design of basic components and the entire system functional veri cation timing analysis Project topics Hybrid SoftwareHardware Encryption and authentication of the FPGA bitstream Prerequisites programming in C basic understanding of hardware knowledge of VHDL helpful 15 Secure Remote Upgrade DesignerNendor should be able to remotely modify the con guration without revealing intellectual property such as unique architecture or proprietaryclassified algorithm Need for encryption and authentication of con guration Possible Attacks 1 eavesdropping configuration during an upgrade modifying con guration during an upgrade Possible Attacks 2 impersonating the designervendor in order to disrupt the operation of the device denial of service A A I A AL 1 I Protecting an FPGA bitstream EPROM 1 D SAELE FPGA 1 Cun guratlun Area ROLLEACK Regula r blts lream Decryption and authentication of the bitstream Encryption protects intellectual property protects classi ed algorithms Authentication prevents against progranming user lo ic with unauthorized corrupted or random bitstream prevents against reading out cryptographic keys by reprogramming user logic rollback mechanism required in case of an authentication failur Analytical Group protocols for secure adihoc wireless networks I work on new original security protocols for the group communication in adhoc networks I initial results available in the form of a conference paper I requires good knowledge of math I possible work under the supervision of a visiting Professor from Australia at GMU in March and April Projects Analytical Survey of Cryptographic Chips and IP cores Survey of commercially available integrated circuim implementing cryptographic algorithms Survey of commercially available FPGA IP cores implementing cryptographic algorithms Partial list of encryption chipmakers Broadcom AEP Systems HiFn Corrent Cavium Motorola SafeNet Layer N Networks Intel NetContjnuum NetOctave Philips Semiconductors Selected ASIC Security Chips BHOADGOMI Chip name Encryptio HMAC Data rate Public key Other 1 algorithms Mbps algorithms algorithms Broadcom DESCBC SHAl 500 DH Onchip RNG BCM5823 3DES MD5 RSA CBC AESCBC AESCTR Broadcom 3DES SHAl 4800 none Inline IPsec BCM5841 CBC MD5 processing AESCBC Onchip SA database AESCTR RNG Selected ASIC Security Chips Chip name Encryptio HMAC Data rate Public key Other 11 algorithms Mbps algorithms Nitrox Lite a39g m SHA l 1000 DH Inline IPsec CN1010 3DES MD5 RSA processing AES RSA 7K 1024 ARC4 RSA39ssec 0n chi RNG NITROX II DES SHAl 10000 DH Inline Psec CN2560 3DES MD5 RSA PFOCCSSing AES RSA 40K 1024 ARC4 RSA39ssec On chip RNG 2M SA39s with 512 MB DRAM Adapts to quothankquot Innll Families of Cavium chips Nitrox Lite Nitrox Nitrox l9 ECE 746 Lecture 4 Mathematical background Groups rings and elds Evariste Galois 18111832 Evariste Galois 18111832 Studied the problem of nding algebraic solutions for the general equations of the degree 2 5 eg fX a5X5 a4X4 a3X3 a2X2 a1X a0 0 Answered definitely the question Which speci c equations of a given degree have algebraic solutions On the way he developed group theory one of the most important branches of modern mathematics Evariste Galois 18111832 1829 Galois submits his results for the rst time to the French Academy of Sciences Reviewer 1 AugustinLuis Cauchy forgot or lost the communication 1830 Galois submits the revised version of his manuscript hoping to enter the competition for the Grand Prize in mathematics Reviewer 2 Joseph Fourier 7 died shortly after receiving the manuscript 1831 Third submission to the French Academy of Sciences Reviewer 3 SimeonDenis Poisson 7 did not understand the manuscript and rejected it Evariste Galois 181 11832 May 1832 Galois provoked into a duel The night before the duel he writes a letter to his friend containing the summary of his discoveries The letter ends with a plea Eventually there will be I hope some people who will nd it pro table to deczpher this mess May 30 1832 Galois is grievously wounded in the duel and dies in the hospital the following day 1843 Galois manuscript rediscovered by Joseph LiouVille 1846 Galois manuscript published for the first time in a mathematical journal c at r a Wrgz w xii5amp5 quot3954 w 39 5 y or r flew a a 4 39 3939 1 41 W 39v A 0 fur iJ gray jiffy Definition of a Group 2162 Definition A quotI m7 vs V mnsi s oin sci G ith 2 binni upcmliou nn 6 saris ing the following 11m Mmms ii lhc iiimin upcrutiun is minim 391 Inn is a i i b m a bi w for nil in b c g G iii Iherc is an Cleman e G called the Mum391 cL lm llh such that a 4x i H a a For oil a E Iiiii I or each a e G there exists an cicmam a 1 e G mailed ilm mi39ul39i u nrn xuch hm a 17L aquot i group G is LYIVL IVILIH orr mmuuluIrcl if funhcrmmc iv 11 1 Mn Humming G are that muliplimtivc group notation has been used For the group operation lime l iid m h in itiliiw group he idcmily cicr i0 i gionp operation is uddii lien ii group is i mcni is dunmcd b3 KL and the inverse ofa is denmcd 7quot 39 amt the symbol gt9 wiil 0 omitted and the grou mich 39 funii uniess othch Minn ii simpl be dcnmcd byjuxmposiliun r 2163 Definition A gi39mIpG is iilluifiGi is nitc nicninnncrnrcicnicnisinanniicgmnpis an M in iiLinn Group Example 1 Z set of integers addition is an abelian group i is associative eg 5713 5713 ii Identity element 0 a0 0a a iii Inverse ofa a eg 7 7 0 iv is commutative eg 5 8 8 5 Group Example 2 Z set of integers multiplication is NOT a group i is associative eg 5 7 13 5 7 13 ii Identity element 1 a 1 1 a 7 a iii No inverse of a for any a 6 1 or 1 eg there is no integer x such that 5 39x 1 iv is commutative eg 5 8 8 5 Group Example 3 Zn 0 1 2 m nl mod n addition modulo n is an abelian nite group of order n i mod n is associative eg 57 mod 16 13 mod 16 57 13 mod 16 mod 16 ii Identity element 0 0a mod n a0 mod n a iii Inverse ofa 0 for 610 eg 7 167 na otherwise 7 9 mod 16 0 iv mod n is commutative eg 5 8 mod 16 8 5 mod 16 Group Example 4 Zn0 1 2 nl mod n multiplication modulo n is NOT a group ifn is composite i mod n is associative eg 57 mod 16 4 mod 16 5 7 4 mod 16 mod 16 11 Identity element 1 a 391 mod n 1 a mod n a iii There is no inverse of a for any a eg there is no XE ZnO that is not relatively prime with n SUCh that 2 Xm0d 16 1 iv mod n is commutative eg 5 8 mod 16 8 5 mod 16 Group Example 5a Znquot a as 1 2 n1 and a is relatively prime with n mod n multiplication modulo n is an abelian finite group of order pn Forn15 zn1 2 4 7 8 11 13 14 p158 1 mod n is associative eg 4 7 mod 15 2 mod 16 4 7 2 mod 15 mod 16 11 Identity element 1 a 391 mod n 1 a mod n a eg 28 mod 15 1 111 There 1s an 1nverse for every 4 4 mod 15 1 element of the group 7 13 mod 15 1 1111mod15 1 iv mod n is commutative eg 5 8 mod 15 8 5 mod 15 Group Example 5b Z1 1 2 p1 Wherep is prime mod p multiplication modulo p is an abelian finite group of order p1 Forp 11 z 1 2 3 4 5 6 7 8 9 10 p1111110 i mod n is associative eg 4 7 mod 11 2 mod 11 4 7 2 mod 11 mod 11 ii Identity element 1 a 391m0d p 1 a mod p a eg 26 modll 1 111 There is an inverse for every 3 4 mod 11 1 element of the group 5 9 mod 11 1 7 8 mod 11 1 iv mod n is commutative eg 5 8 mod 11 8 5 mod 11 Cyclic Group on A nonrcmpl subset H uru group G is u iuugmup nfG ii H i iisuiiu group N inspect lo the operation MG 1111 i u subgroupofG uuuH G ihcn H is called u 1mchsubgroupi G 2167 Definition 39 1 15 G ilmrc quotifilii i 1 1 I 6 Such 1111 Clement a is culicd agunw39urm ofG 6 a i i 1 2168 Fact 11 s i u Di39ou mi 11 g G then me sci uruii puum um mum u miiu subgroup of G milcd the subgroup gm um I a uuu dcnolcd 13 a Lci G be a Uroup and a E G he ul dui ofa is de ned 10 bc the cast DONKEVC pr 39iLiCLi that such an intcg 39ists lisuch a t docs not exist 11 to he 30 Ini then thc urdci39ofa is d 2170 Fact Lct G be of the su upud In a e G mun clement ui uiiuuiucrt i39iicu m1 lhi size group generated b a is equal lo 2171 Fact p i in 1 iGi llcncc m g G 11 order ofa divides iGi 2172 Fact chiysubgroupofu v m39dor 71 than for each posi ci oquisalso iiG is u clicgroupof no divisor d ofn G columns cxactl um subgroup ofnrdci d Cyclic Group Example 6 Z 1 2 pl Wherep is prime mod p multiplication modulo p is a cyclic group with pp1 generators Forp11ZP1 23 4 56 7 8 9 10 There are p10 4 generators In particular 21m0d11 2 25m0d11 9 22m0d11 4 27m0d11 7 23m0d11 8 28m0d11 3 24m0d11 5 29m0d11 6 25m0d1110 210m0d111 2 is a generator primitive element of Z1 1 Cyclic Group Example 6 continued 31 mod 11 3 32 mod 11 9 33 mod 11 5 34 mod 11 4 35 mod 11 1 3 is NOT a generator of of Z 1 lt3gt 3 9 5 4 1 is a cyclic subgroup of Z 1 generated by 3 3 is an element of Z1 1 of order 5 lt3gt size of the subgroup generated by 3 order of 3 5 Size of the subgroup 5 10 size of of the group Test for a generator of a cyclic group Size 0fthe cyclic group ZNquot 10 25 Test for a2 2102 mod 11 25 mod 11 10 1 2105mod1122m0d11 4 721 Result 2 is a generator onHquot Test for a3 3102 mod 11 35 mod 11 243 mod 11 1 3105m0d1132m0d11 971 Result 3 is NOT a generator onHquot Subgroups of a Cyclic Group 2173 Fact Let G in a group H urn ordcrofu g G ist lhcnthc m39dcrofak St w 1 ii lfGisu 39 vaomdcm amld nJhcn Ghnscxacll we clcmcnlsofm39dcr d m 11m39ticnlur G has mm generators lb ofm39dcr l8 lhc group 5 011 and their gum D s 2174 Example onsidcrthcmulliplicmi upZ fn l39 isc 1 a 3 in andugcncmmrisa 2 l39hcmhgmn c llslc tl m l uhlu 27 Table 27 m mmrmru u Z1 Definition of a Ring 2175 Definition Ail1Q R ml 7r x 7 Consists ofu set R 39ilh iwo hinul39 opcrmimrs arbitrarin dc noiml i iiikikiiliollid 39 gtlt muiiipliculiunion Rt nilisijriug the lkviluuing momm i iR 1 is an ibcliun m39oun ili idcmin icnmcd H quot 391 he imcrmion X is 39 39 ocmtwc iSa gtlt bx c a X bi x z furall ubc E R iiii Ilmrc is a Inuitiplicmivc idcmiq icnoicd i with i U such hail X a a x1 12 for all a e R m lhc operation X is llAli IWH39U over l39hai is a gtlt rb c a gtlt b a X c and 17 c X a ib X N c x foruil abc e R 39lhc ring is u mmmuurivuring ifa x l b x a for all ab E R Ring Example 7 Z set of integers addition multiplication is a commutative ring i Z is an abelian group with identity element 0 ii is associative eg 5 7 13 5 7 13 iii has an identity element 1 a 1 1 a 7 11 iv is distributive over 6g 5 713575 13and 5713513713 is commutative eg 5 8 8 5 V Ring Example 8 Zn0 1 2 n l mod In addition modulo n mod n multiplication modulo 1 is a commutative ring i Zn is an abelian group with identity element 0 ii is associative eg 57 mod 16 4 mod 16 5 7 4 mod 16 mod 16 iii has an identity element 1 a 39 1 mod n 1 a mod n a iv is distributive over eg 5 7 4 mod16 mod16 5 7mod 16 5 4 mod 16 v is commutative eg 5 39 8m0d16 8 395 mOd 16 Definition of a Field 2181 Definition A 39 39 iniiici2ii I w Ir Ir39 i39w iivc im ci scs 717 mm 2182 Definition 10 L liumuwmiiu o rkl is 1 ifi i 1 IS ncvcrcquul to 1 forum in 2 i ihumisc iiic cimmcicrisiic ni iiic uid is the icusi posiiiw gcr m such that 7 l i Ci iiialsO 2185 Fact lithe characteristic m viii uid is with ihcn m is a prime numbcr 2186 Definition A siilisci F viii eld E is El iiv ei ifE ifF is iiscii zi licld Willi i39ChliCL l m the pci39aiions ofE lfl 118 is Kim CRSL E is SaidinbcunL 39 l7lil1 n izOfF Field Example 9 Z set of integers addition multiplication is NOT a field No inverse of a for any a 1 or 1 eg there is no integer x such that 5 39 x 1 Example 10 Zn0 1 2 n1 mod In addition modulo n mod n multiplication modulo n is NOT a eld ifn is composite No inverse of a if a is not relatively prime with n eg there is no xe Zn such that 2 39x 1 mod 16 Field Example 11 Zp0 1 2 pl modp addition modulo p mod p multiplication modulo p is a eld if and only ifp is prime i ZP mod p mod p is a commutative ring ii There is multiplicative inverse for all numbers from ZPO egg 26 mod111 gt 2391mod116 34 mod111 gt 31mod114 59 mod111 gt 51mod119 78 mod111a 7391mod118 Field Example 12 ZP0 1 2 p l mod p addition modulop mod p multiplication modulo p is a eld of characteristic p 111 1 modp0 p times Sets of polynomials 2187 Definition If is a cmnnmmiiw ring ihcn upuiimmziul in dis indclcrminamz m39cl39lik ring R is 1m mmssimi ui iiic form flaw anr 0421 ai1 an WIICi39C such a E R and n 2 U The clcmcni a1 is culled lhc wur umm ofz in fi z39 l39hc largest integer m or which am o is called the LUgl39L L of fix dL nOlUd iiiig fir am is milieu lhc Iciidiiig mimic of I if i 3 uii iii mmiiim iaziiiiiiiiiuii and an 011icnfizi has dcgl39cc 0 fall the coef cients Offiz m o mi imiiiiii iiiiii iis dcmcc For mulhumalic 39 11 fi m39i is called the U I L aim in be 700 lhc polynomial x is siiiii m be mam iiiis leading Cucf llcnl is quiai m 1 2188 Definition If is a COmmliiEiliVE ring ihc iiiiiiiiiiiiiiiiiiiiig Rm is Ihc ring Formed by the 5 Mail polyiomiais iii hr ilidClCi milmlD z Ming coef cients from R N two upcm inns arc thc standard publiumlsil addiiimi and multiplication with semi mm uiiiiimctic performed in thc i39ing R Sets of polynomials ZX polynomials with coefficients in Z eg fX 4 X3 254 X2 45 X 7 ZnX polynomials with coef cients in Zn eg for n15 fX3X314X24x7 Z2X polynomials with coef cients in Z2 eg fXlX3OX2lxlX3 xl Polynomial rings ZX polynomial addition polynomial multiplication ZnX polynomial addition polynomial multiplication Z2X polynomial addition polynomial multiplication For Z2X i Z2X is an abelian group with identity element 0 ii is associative 6 thxtl 39 X1 39thlX2X1 39X1 39 X21 iii has an identity element 1 fX 1 mod n 1 fX mod n fX iv is distributive over ega thxtl 39 Xt1XZ1 X2X 1 X1 X2X 1 X 1 Division of Polynomials 2190 Definition Lct fm eFz be a polynomial ofilcgrcc mlcast l lhcn ffm issaidmbc I r39utlm39Ivu 111w F if it cannot in wrincn as the product oftwo polynomials in Fm each ofposiliw c 2191 Definition 1mm ugmlhm m mlpmmius Kym11x g FM with my o 39 39 k39 quot1L1W39 V quot quot e F m such mm My qz391h1m 71111uhcrmlrgr xlt1lnghm Morcmcr W and rm 1er unique 11w polynomial gm is called thc Worm 1mg 1139 39 39 quot 39 39 39 um hm and the quotient is smnctimcs denoted 9111 on hm 1 cf De nition 28 Finite sets of polynomials Z2 xfx polynomials with coef cients in Z2 of degree less than ndeg fx eg for fX X3 X 1 g7XX2Xl g3XXl g6X X2 X 1401 X g5X XZ 1 g1X 1 g4X X2 goX 0 Zpxfx polynomials with coef cients in Zp of degree less than ndeg fx eg for fX X3 X 1 and p3 X 0 g0 Total 3quot polynomials gM1X 2X2 2X 2 91 IZXI17XPOIHIZX 117X39X 117XP0w IX ZXSX I17XPOUIIXXZX XSX 117X P0m1zx1xgx uoyeaudmnul BIIIIOIIKWJ X ZX XIVX P0m1zx1xgx uomppe BIIIIOIIKWCI X pom uopeoqdmnul Emma10d XH 190111 110111191912 Immou lod XJXdz X pom uopeoqdmnul Emma10d XH 190111 110111191912 Immou lod XJXZz s uu eywou lod rzmm nilmum v 22mm yum771 v T 1 T 4 W WWW gt1 IUIJHJLHj 931 g m g 111 1pm 10 21mer yxw wmzmmnnLHnnu176qu NIH711p m I I L W w 72w 1 1 mahmumuJWWWmu g39y alqel rrv n Chi H m n L8 45 x1 x AX M MN m Cm LL Wu ltI39Z 85H m mm Mr 39 LU MT iriuiiimmmm Finite fields 39 lhr Ul39iL F 2208 Definition A 39 39 oi F is the number ofclcmcms in F 2209 Fact distance umzmuumcvx 17 17mm hallx it Il39Finx llilcllcillillcllFCUIHIiIlp vlclllclllhtill nulllcDrilllclhlnd nuguru 2 l 1m 1mm r y mm 11 um mm ilt denoted l1 nutm mmutinm 1y GFlpm Informali speaking um uids are Winnpm irmq are mumum the s ale though the rcprcwmulimi nl39ihcir llultl clcnwlm mu he dullrum mc that if is 1 I lime 2 is a eld and hung cvci Iiuld ol39urdcl p is isomorphic to ZP l Mic olhumisu slam lllc nite eld 117 ill hunccihrlh he iLlcllli Cd ili Z Z iicld ul39 Finite fields fx is an irreducible polynomial of degree In Fq GF2 quot Z2XfX polynomial addition mod fX polynomial multiplication mod fX where q 2m Fq GFpm ZPXfX polynomial addition mod fX polynomial multipllcatlon mod fX where q pm All non zero elements have multiplicative inverses eg for fx x3 x l and p2 xl x2 x mod x3 xl l gt xl391 mod fx x2x Primitive Element 2212 Definition H l 39r 39 39 quot liiiiuimi griml Lilli lluiiiilcd h l 2213 Fact IF i311CClicgl ullpUfurdcl39qi l Han aquot a lniiill u a 1R ll IL39UIL39H ur gmul llml group 11 l culled u lll illll llw 2214 De nition l gclwl39lllui unhu c Fq Primitive Polynomial 2228 Definition An irreducible polynomml fix 6 Z ofdcgrcc m is called a H39illilh39 i in i V in FFquot Zpzl39fxl39l 2229 Fact 39llic lrl39cdlicihlcpolymlnia flml e Z I llfdcgl39ccm isaprimitivepolynomlul if and mily iffl ml divides zl 7 1 for l pm 7 l and iii no smaller pusiiivc iin Number of primitive polynomials over Z2 of degree m m p2m1m fx 2 1 X2X1 3 2 X3X1 X3X21 4 2 X4X1 X4X31 5 6 X5X21 etc k m k m k m w 7L7H J 71 MU KN J 3 u u MM 3 w mm 7 m H 7 7 31 x x 20 27 2 w W 7 04gt m MM HM h Table 48 I immrupowmUIUIA uvcr Z2 w uni1m i g m g 220 unavpuncm 10 vgn unur mIkl n u gt quot1 as 1 a mumm Himz Um m QueIm39umI m punurwmu I x I 19 i x1 mull 1quot 1 1 uclnr nulminn 11 11111 1 1 gr 11111111 1 1 111110 1 L 11111101 1 11 11111111 1 zlx 1111111 a rim1 11110 T t zl 111111 a l 1 111111 4 z x 11111111 111 z9x1 111111 11 z r z 11101 12 z rz11 11111 11 rur 1 111111 11 z1 111111 Table 29 Ivu m m 0 11117111110 at 1 1 1 1 Test for a primitive polynomial Test for fx x4xl fx irreducible Size ofthe cyclic group Fqquot ql Zml 1535 x155 mod x4x1 x3 1 KW3 mod x4xl x2x 1 Result x is a generator of FqZ2xfx Test for fx x4x2l fx is reducible x4x21 x2x 1 x2x1 Result Z2xfx mod fx is not a group Computing Multiplicative Inverse 2 1 Extended Euclid s Algorithm for computing z a 1 mod n 9i ri xi r Ii quot1 r2 n 9920 ri q1Lraj r1 a x11 qo r0 x0 ri1quotir1quot1i ri q r x 1 1 1 xi1 xiil quotIi xi 1 qH r 1 xt1 I modn r0 x n Note If rt1 1 the inverse does not exist 21 ECE 746 Lecture 2 cont Rijndael Encryption Round Keym Add Round Key Round Keyi Shift Row Add Round Key Round KeyNr Decryption 1 Round Keyi Inv Shift Row Inv Byte Sub Nr l times Round Key0 Properties of component transformations 1 Shi Row Inv Byte Sub Inv Shift Row Inv Shi Row Inv Byte Sub Properties of component transformations 2 KRound Keyi IRX Add Round Key XK IM Inv Mix Column E 38 5 IMXKIMXIMK gtlt 1M Inv Mix Column IMKlnv Round Keyi W100 Add Round Key IMXIMK I Decryption 2 Round KeyNr Inv Mix Column Inv Round Keyi Nr l times Round Key0 Decryption 3 Round KeyO Add Round Key Inv Byte Sub Inv Byte Sub Inv Shift Row Add Round Key Round KeyNr Decryption 4 Round KeyO Add Round Key Round Keyi Inv Byte Sub Inv Shift Row Add Round Key Round KeyNr Lecture 9 SideChannel Attacks Timing Cryptanalysis Power Analysis Fault Analysis Cache Attacks Traditional Cryptographic Assumptions input Cryptograpllic output transformation Encryption Decryption Signing etc Secret key K Actual Information Available Leaked information Timing Power consumption Electromagnetic radiation Ll input Cryptograpllic output transformation Encryption Decryption Signing etc Secret key K Timing Cryptanalysis Timing Cryptanalysis Inventor Paul Kocher 22 years at the time of the attack discovery biology student at Stanford Time November 1995 November 29 1995 presentation of the basic concept at the university seminar December 11 1995 article in New York Times January 1996 presentation at the RSA Data Security Conference RSA announces introducing countermeasures against this attack to their libraries 1000 Netscape bugs bounty awarded to Kocher Timing Cryptanalysis Requirements 1 Capability to measure the time of transformation dependent on the unknown private or secret key for a sequence afdz erent input data messages or ciphertexts 2 Capability to measure the time of partial operations of the transformation e g a single iteration of the RSA exponentiation far the same sequence of input data With the adaptively chosen values of the key bits Time necessary to reconstruct keys Single minutes Time linearly proportional to the key length Timing cryptanalysis Possible seen arias 0 server signing messages originated in the local network before sending them to Internet 0 absentminded CEO 0 hacked card reader Cryptographic transformations particularly vulnerable to timing cryptanalysis Easiest to attack 1 RSA signature generation Without using Chinese Remainder Theorem 2 BSA signature generation 3 Computing public keys in the DiffieHellman key exchange 4 Signature generation in Elliptic Curve Cryptosystems More dif cult to attack 1 RSA signature generation With Chinese Remainder Theorem Times of signing messages M1 MP t 1 TSGNM1 TSGNM2 l TSGNM3 1 TSGMMP ime RSA Signature Generation d n Operation SGNM S Md modN 81 omputations performed in the first iteration for i for i 0 to Ll For di0 ifd1 P P P modN s SP modN For r1 pppmodN S SPmodN P P P mod N Analysis of correlations between the time of the first iteration T1 and he time of the entire transform39ti0n TSGN 1 time TSGNM1 T1ltledoogt T1ltledo1gt I TSGNM2 T1Mzdo0 TSGNM3 Range times except the first one time TSGNM TSGNM 39Ti deZO TSGNM39T1MidU1 TsGNM2 TscNOVIz quotT1M2idu0 TscNOVIz quotT1M2idu1 TSGNM3 Distribution of the execution times of all iterations except the first one For do0 Standard deviation Standard deviation For do1 Distribution of the execution times of the entire transformation Standard deviation Test for bit do Assuming correct guessing of do and thus the time of the first iteration Standard deviation of the execution times of remaining iterations decreases Assuming incorrect guessing of do and thus the time of the first instruction Standard deviation of the presumed execution time of the remaining iterations increases Analysis of correlations between execution times of the second iteration T2 and all but the first iteration TSGN T1 time m T2M1d10 TSGNM1T1M1 T2M1 id11 i TSGNltM2gtT1ltM2gt T2M2d10 Midi GNM339T1M3 T2M3d10 T2M3d11 average times Timing Cryptanalysis Countermeasures Equalizing the time of all operations independently of the values of operands Problems Increase in the average time of all transformations Difficulties in writing software and designing hardware Timing Cryptanalysis Countermeasures Masking Method I Choose random X different for each message P K oeher SGNM MXd mod N X 1d mod N mod N Nd mod N X X ld mod N modN Md mod N X 1 d modN ma be com uted in advance y P Only m additional multiplications Timing Cryptanalysis Countermeasures Method II R Rive Choose random Y SGNM MY 1 d mod N Y modN Nd mod N Y4ed mod N Y modN Md mod N Y 1 mod N maybe computed in advance Only m additional multiplications Timing Cryptanalysis Summary Requirements regarding the capabilities necessary to unt the attack not met for many applications eg emai Simple countermeasure that increases the time of transformations to a very small extant lt1 Problems With modi cation of applications already deployed in particular hardware implementations Power Analysis Power Cryptanalysis Attack that enables to recover a key stored in a cryptographic device based on the measurement of power consumption during cryptographic operations Inventors Paul Kocher Joshua Iaffe iBenjamin Jun Cryptography Research Time first developments beginning of 1997 first publication June 1998 Power Cryptanalysis The most vulnerable devices smart cards cryptographic tokens Requirements access to the device eg a smart card Time necessary to recover the key seconds for simple power analysis several hours for differential power analysis Equipment basic measurement equipment ammeter oscilloscope Power cryptanalysis 0 can be performed during the regular operation of a smart card J assuming that the opponent modified a reader 0 does not require an unauthorized access to the card 0 does not require the knowledge of the plaintext Power cryptanalysis Basic variants Simple Powertrulyin SPA Obsmatim and analysis ofpower Consumption during a single transaction Dyferentia Power Armlyler DPA measurements tztistieal analysis of mu tipl ased on the imilarpnnciples as timing cryptanalysis HighOrder Dyferentia Power Analysis Complai statistical analysis ofmultiple measuranents Expenmenta equipment L Dem 1m mamronng the urrzm consumpuan m 1 mp menavmxummwuammve mmsmumm mam WWW1ame Warm Ilivznm Simple Power Analysis SPA DWerent im39b39uctionx have Merent power conmmption pm ternx multiplication I addition XOR storing data to a register storing register to memory Simple Power Analysis Measurements by Paul Kocher Permutation IP 16 rounds of DES i Pamutation Iquot 1W We mmtwwwwmemmwwwwhww wotWWWWWWMMMWMwwwwttnth WM WW magnified view of the second and third round Simple Power Analysis f a sequence qfinm39uctionx depends on the key bm 39 39 39 un My Example Generation of the RSA signature 81 for iL1 downto 0 rivate ke bit p y S S2 modN a 1 S S M modN Simple Power Analysis Example Generation of the RSA signature multiplication squaring QE Power consumption during the signamre generation SPA attack on RSA Test key value 0F 00 F0 00 FF 0 l l fllllllll FD 0000 0000 FF 0000 0000 00 3 00 i 1 ll 91 0F oooooooo on W9M 9 l f Joye abs y y w u M Warsaw May 2007 Simple Power Analysis Countermeasures Sequence of instructions independent of the key bits with the exception of instructions having the same power pattern Avoid conditional branches if switch etc Ability to prevent analysis depends strongly on the operations used by the cipher and on the processor instruction set Differential Power Analysis DPA Power consumption depends not only on the m of the executed instructions but also on values of operands Examples storing data to the register or memory Storing 1 has a larger power consumption than storing 0 variable shifts and rotations Power consumption depends on the number of positions by which we shift or rotate logical and arithmetic operations Strong dependence of the power consumption on values of operands 11 lnformauon leakage chsumptian of a chip depends on rd Ania Leakage models mumme tuht MM tidLi L I Him 7 u w vdm rm a i t4lt9y anevmumlw amlwl rimmaawaa nlaumicNWWWlaxxlw Wmt Iliva Information leakage M t M ci iquotiif y r 0 yr hi ii ii ii lii w iii A i i LHIIIW i i lt Vi er gt anevmumlw amlwl rimmaawaa nlaumicNWWWlaxxlw Wmt Iliva Differential Power Analysis I phase Target Speci catiun Pharc Find an intermediate bit a such that a fK D where K one or multibit fragment orthe internal key unlmu t pnnent D fragment of data 22 ciphertext or plaintext latan tn the n uncut f funcu39on which may be deduced from the description ofthe cryptoalgorithm latan tn the uppunent Example Last round of DES Instruction I Km opponent of the result of F a K D K fragment ofthe Kl known Ciphertext D to the opponent unknown to the known to the opponent Km unknown to the opponent Differential Power Analysis Phase I Target Speci cation Phase Bit a appears as an input to the instruction I for which an average power consumption P 1a depends strongly on the value of a D Wm P1a1 E 1 Average power consumption by the instruction I for different values of the input bit a Phase II Data collection phase Measuring power consumption for N different data blocks Dx ie N different plaintexm and the corresponding ciphertexts PICK 111 HOW 113 PICK 112 HOW 11m PKK D Phase I Data analysis phase Assume a certain value of the key fragment K and add MmNZ power consumptions corresponding to the same value of a PKsz 1100 PICKr DB0 PICKn Dm0 PMKv 1190 PMKZ 1211 13009 1231 P1009 DMH P1009 1211 Correct value of the key fragment K KK Z PMKquot 129 mew Kquot 1190 2 13mm 1 Kquot 1291 T1KK m DI N2 Incorrect value of the key fragment K K K39 2 PARK 11 K39 10 Z P MK 11 K 11 TKK39m0 T K63 Currect value at the key fragment K currespnnds m 39 Tm Differential Power Analysis a r P Round 1 Round2 W rh W MWJMWWWL a bit no 5 of the plaintext Number of measurements N1000 P Round 1 Round2 A ack does not require the knowledge of the position e instruc onlin u39me Instructions arreuea by bit uwill show up automatically on an quot quotI I ofthe key fragmentK Differential Power Analysis Exanyle 0f the mack Panlay39 Rohmgi IBM 1999 Implementation of the AES candidate 39I Wo sh 0 d 1287bit key recovered based on about 50 encryptjuns of independent data blocks Differential Power Analysis for Key Sche ulin Biham Shamir 1999 By observing power conmngption during enciyptions of multiple blocks qulaintext it isposn39ble t0 detemline the exact location qfinm um39ons belonging to key scheduling All encryption performed using the same key key scheduling Data 1 Data 2 3 P 7 Data 3 W M 3 3 3 Differential Power Analysis for Key Scheduling The last phase of each period of computing an internal key corresponds to storing the key in memory m Storing 6 bytes of an internal key to memory Differential Power Analysis for Key Scheduling Analysis of power consumption during storing the internal keys to memory enables to determine the Hamming weight the number of ones for all bytes of the internal keys Hamming weight ESE number of ones in abyte 5 4 3 4 3 3 Example Key scheduling in DES 16 internal keys X 48 bis 96 bytes 96 guessed Hamming weighs Each byte of an internal key contains a subset of 8 out of 56 bis of the external key x1x xl1xux28x31x36x45 X4x12x15 xmx21x33x39X51 X5X1 ail9X33X45x48 XSU X55 2 Unique solution Differential Power Analysis Proposed countermeasures Goal Elimination or signi cant reduction of the correlation between operand values and power consumption I Desynchronization Random change of the power consumption in time by random injection of dummy instructions Problem Dummy instructions may be recognized using simple power analysis and removed from the waveforms Differential Power Analysis Proposed countermeasures 11 Noise generator Noise generator added to the card to randomize the regular power consumption Problem Correlations can be still exploited using a larger number of measurements Noise can be ltered out Differential Power Analysis Proposed countermeasures Ill Filter at the power input physical shielding Problem Limited accuracy of the lter Possibility of deactivation in case of the access to the car Differential Power Analysis Proposed countermeasures IV Software balancing Problem Signi cant reduction of spee d Correlations still present for more complex arithmetic operation Differential Power Analysis Proposed countermeasures V Hardware balancing All instructions executed by the processor has the same power consumption for all operand values Problem Very costly and hard to design Differential Power Cryptanalysis Countermeasures Lack of effective countermeasures in existing cards We have not yet encountered a card that couldn t be broken Paul K ocher 1998 Protection methods developed and licensed by Cryptography Research currently introduced to several types of cards Shamir s countermeasure ij 49 9 SZ S3 1C2 C1 S4 Microcontroller GND Shamir s countermeasure 4 c1 4X V133 c1 VDD SI DD SI C1 VDE SI C1 VDD SI C1 MC H C1 MC H C1 MCH C1 M C1 MC C1 2 2 2 2 2 V At C2 V AV C2 DD 53 DD 53 MC 02 MC 02 4 4 upply from cz upply from cz supply from c1 upply from c1 supply from 39 c2 c1 amp cz 20 Shamir s countermeasure C1 voltage 6V 5V C2 voltage supply supply from supply from c1 c1 amp cz rom cz Shamir s countermeasure C1 voltage 6V 5V C2 voltage supply supply from supply from c1 c1 amp cz rom cz Shamir s countermeasure Microcontroller GND 21 Implementation of capacitors Value 4H HF Minimum Dimensions 2 X 2 X 04 mm Possible Implementations External components located under the card contacts next to the 39 Embedded in the card material by using alternate layers of plastic and aluminium Workshop Quo vadis cryptology Warsaw Poland 2003 Josh Jaffe Cryptography Research Inc I have analyzed about 100 dz erent smart cards and I have not found a single one resistant against the Differential Power Analysis Fault Analysis 22 Differential Fault Analysis Inventors D Boneh R DeMillo R Lipton Bellcore Time 1997 Extension to classical cryptosystems E Biham A Shamir Differential Fault Analysis Assumptions Transient localized fault during the operation of the cryptographic device A caused by noise B enforced by the attacker Generation of the RSA signature using Chinese Remainder Theorem M mod N S M 1 mod N Sp SmodpMde modp Sq Smodq quq modq s SpRq sq RP modN RqqP391 mod N Rpwqu mod N 23 Differential Fault Analysis Attacker generates Correct signature S S SpRq Sq RP mod N Signature S obtained as a result of a transient fault in one of the branches of computations s SpRq s RP modN Where Sq Sq quq mod q Attacker computes s S Rp sq sq pq39l modNSq sq p 1391Sq Sq modN p 1391Sq Sq kpq Attackers discovers factorization of N Improvement by A Lenstra Sufficient knowledge of A one incorrect signature S with an error in one branch of the computations and B signed message M pgcd1VIS modNN 24 Proof of the Lenstra s improvement 1 s SpRq 5 RP modN S e modN Spe mod NRqe mod N Sq e mod NRPe mod N mod N MpRq Mq Rp mod N RququodN lgeERpmodN because because qP391gt 9 mod p qP391 mod p 1 pq391gte mod p p i391 modp 0 qP391gt 9 mod q qP391 mod q 0 pq391gte mod q p i391 mod q 1 Proof of the Lenstra s improvement 2 M s e modN lIpRqMq RpmodN MpR Mq Rp modN gcd M S e modN N p Differential Fault Analysis Countermeasures Checking the correctness of the result before it leaves the device Problem Additional computations Random padding Problem Current standards 25 Summary 1 Completely new class of attacks using information leaking from the cryptographic devices Attacks efficient against both classical cryptosystems and public key u r All attacks practical very fast and inexpensive Summary 2 Most dangerous attack Differential Power Analysis DPA Practical implementations few practical countermeasures Less dangerous Timing cryptanalysis Differential Fault Analysis Known efficient countermeasures Need to modify devices developed before invention of the attack Cache Attacks 26 Cache timing attack 1 Inventor Prof Daniel J Bernstein University of Illinois at Chicago When rst document published at the webpage of Prof Bernstein No 4 improved and extended publication Apr 14 2005 Cache timing attack 2 Ciphers vulnerable to this attack AES Triple DES majority of other ciphers Implementations vulnerable to this attack Software implementations using lookup tables to perform internal operations of the cipher such as S boxes Include both the reference and optimized implementations of ABS presented in this lecture Cache timing attack 3 Microprocessors found vulnerable to this attack Intel Pentium III thlon Intel Pentium M IBM Power PC Sun UltraSparc and many others Cryptographic libraries vulnerable to this attack OpenSSL and many others 27 Cache timing attack 4 Practical result Recovery of the full 128bit AES key Time of the attack according to Bernstein Time necessary to process 22532 million 800byte packets 22532 million 600byte packets and 227 128 million 400byte packets several hours l Final computations several minutes Cache timing attack 5 Practical result Recovery of the full 128bit AES key Time of the attack according to my student R Several days Time necessary to process 2238 million 800byte packets 2224 million 600byte packets and 221 2 million 400byte packets several days Final computations m 2 minutes Cache timing attack 5 Scenarios server encrypting data leaving k internal intruder virus measuring time of cryptographic transformations 28 Cache Attacks Pure software No special privileges No interaction with the cryptographic code some variants Very efficient eg full AES key extraction from Linux encrypted partition in 65 milliseconds Compromise otherwise wellsecured systems eg see NIST AES process Commoditize sidechannel attacks easily deployed software breaks many common systems er Why cache analysis CPU core cache Main memory Annual 600 79 speed untll lecently increase Typical 03ns 50150ns gt timing gap latency Address Leakage The cache is a shared resource cache state affects and is affected by all processes leading to crosstalk between processes The cached data is subject to memory protection But the metadata leaks information about memory access patterns which addresses are being accessed Tvmv M M 29 Cache timing attack 6 Major idea Lookup table As a result of properties of cache time necessary to access a speci c position in the table depends on the address of this positio addr2 Different access times Cache timing attack 7 Maj or idea Lookup table Addrl fragment of known message fragment of a round key Addr2 fragment of known message fragment of a round key Access time depends on a fragment of a round key Round function encryption KeyAdditionak 0132 ROUNDS ordina y ounds 7 z lt ROUND zH o r ableRound netiona k L t round is special there is no MixColumn Sub titutionasBC tRowaoBC K AdditionakRDUNDSBC message block key 30 Key scheuuung NIF4 erZehwmds Rmmrl key sdec nn WW mew mew L Tableelookup implementation lndlz m m m laakeuplahleswnh mpms equal m meg Cache liming attack 3 Maj nr idea Addressused dunng gm lmg Luuk39up tableT Add knuwn mexmge byte 6 1mm key byte Address used dunn attackm Addr knuwn mexxage39 byte 6 unlmawn key byte Fmdmessage byte and message39 byte that 9v summed anis Cache timing attack 8 Basic problems with creating a constanttime implementation Cache is signi cantly faster than main RAM Cache Level 1 is faster than Cache Level 2 Possible countermeasure Assure that the entire look up table is in Level 1 Cache Cache timing attack 8 Problems with known countermeasures Reading from two different locations in RAM may change the same cell of Cache Interrupts may change the contents of cache Writing to RAM including stack may change the contents of cache Cache timing attack 9 Conclusions New and very ef cient attack against implementations of ABS and other ciphers So far no ef cient countermeasures Recommendation Limit the amount of ciphertext obtained using the same key 32 Conclusions Cache state attacks are cheap easy to exploit hard to detect applicable to many deployed systems expensive to avoid Must be considered when designing choosing implementing and evaluating cryptographic algorithms memevmsemmbv anhvmer w nuamscwmmmm WWW Mavznm Acoustic Cryptanalysis Acoustic cryptanalysis Adz Shamquot Eran Tramer Rump Session EuracoptZUUA Hardware and soltware necessary to mount an attack microphone ampli er software for the spectral analysis of sound ECE 746 Lecture 11 Secret Sharing Zero Knowledge Secret Sharing Simple Shared Control Schemes Dual control Secret Shares S random S1 S2 S S1 mod m ISSISml Unanimous consent control Secret Shares S random SI 82 S3 SH 1 S Si S ml St SS1 82 St1modm Secret Sharing t 11 threshold schemes tltn Secret Shares Rule 3 3132 sn Any t or more shares are sufficient to compute S Any t l or less shares do not reveal any information about S Shamir s tn Threshold Scheme Secret S Computation of shares by the trusted party T l T chooses a prime p gt maXS n and defines a0S 2 T selects t l random independent coefficients a1a2a11 OSaiSpl defining the random polynomial fXaOa1 xa2X2 aT1 X 3 T computes Sifimodp lSiSn 4 T distributes pairs i Si to I1 users Shamir s tn Threshold Scheme Recovering the secret Shares of t users provide t distinct points of the polynomial Xi yi ni Sm Coefficients of polynomial f including a0S can be computed using Lagrange interpolation t fx Z Yi H X 39 Xj Xi 39 X1971 i1 ls j s t j i t s f0 Z yi ci where ci H Xi X1 Xiquot i1 lsj S tj i Shamir s tn Threshold Scheme Example Shares S1 8 S3 10 S5 11 Parameters t3 n5 p17 X11 3718 X23 3210 X35 3731 1 c1 3 31 1 5 51 1 mod 17 4 c2 1 13391 5 53 1 mod 17 3 c3 1 15391 3 35 1 mod 17 11 S841031111mod1713 Properties of the Shamir s Threshold Scheme 1 Perfect Given the knowledge of t1 or fewer shares all values of the shared secret S remain equally probable 2 Ideal The size of the share is the same as the size of the secret 3 Extendable to new users New shares can be computed and distributed without affecting shares of existing users 4 Varying levels of control possible Providing a single user with multiple shares gives more control to that individual 5 No unproven assumptions Security does not depend on any unproven assumptions regarding the dif culty of number theoretic problems ZeroKnowledge Identi cation Protocols Strange Cave Strange Cave A Thief Ali Baba Strange Cave Ali Baba 0 Strange Cave Ali Baba N O Thie Strange Cave li Baba Thief Strange Cave A Thief Ali Baba Strange Cave Ali Baba O Strange Cave Thief Ali Baba l 0 A Strange Cave Ali Baba f Thief Strange Cave Secret of the Strange Cave Excavated Strange Cave ick Ali Commitment TV Crew Excavated Strange Cave Mick Ali 0 Ch allenge Crew Ali Come out on the right Excavated Strange Cave Mick Ali E Crew Response Excavated Strange Cave Secret ick Ali Crew Response Basic FiatShamir ZeroKnowledge Scheme Private key of A Public key of A Secret S P S2 mod N commitment Z X2 mod N random X q challenge q 6 01 response Y XSq mod N B verifies whether Y2 E Z Pq mod N The exchange is repeated t times gt probability of error 12 Attack against the basic FiatShamir scheme A assumes that B will choose A assumes that B will choose q0 q1 random X random X ZX2modN Z X2PmodN q0 q1 YXmodN Y XPmodN Y25X2modNE Y 2EX2P2modNE EZquodN EZ quodN Generalized FiatShamir Scheme Private key of A Public key of A Secrets S1 S2 Sm P1 P2 Pm Pi Si2 mod N Z X2 mod N random X 11 12 quota qm qi e 03 1 Y X H qu139 mod N J B veri es whether YZEZ39H ijjmodN J The exchange is repeated t times gt probability of error 12 m Attack against the generalized FiatShamir scheme A assumes that B will choose q q l q 2 q m random X Z X2 H Pin mod N J ql qz quotqm Y X H ij j mod N J Y ZEXZPZmOdNE EZ Hij j modN J Signature based on the FiatShamir Scheme Signing Private key of A Secrets S1 S2 Sm random X Z X2 mod N 11 12 qm hM Z V gt SGNM q1 12 quot393 q a qi e 01 y x n sjqj mod N 3 J ECE 746 Lecture 6 Stream Ciphers Block vs stream ciphers M1M2Mn m1m2mn K lgt BIOCk K lgt Stream ci her p c1pher C1C2Cn 1czcn CiZfKMi Ci 2 fKmi mm 2 m2 m1 Every block of cipheitext Every block of ciphertext is a function of only one is a function of the current and corresponding block of plaintext all proceeding blocks of plaintext General model of a synchronous stream cipher i Encryption u Decryption Fiam39exl m Cinhertexl c Kcy A g I ficrkjgt nextstate function 2 monki keystream function Pi hizi quotI output function General model of a selfsynchronizing stream cipher Encryption H Decryption Sender i 39tialization key vector seed Pseudorandom Ke Generator Typical stream cipher Receiver k 1nitializati on ey vector seed Pseudorandom Ke Generator C Length CD w or In plaintext ciphertext ciphertext plaintext Linear Feedback Shift Register LFSR L CD gt onnection polynomial CD 1chc2D2cLDL Example of LFSR Slage Siege Stage 3 Z 1 output D D D 4 1DD4gt Stage 0 17 Length Connection polynomial CD Initial state sL1 sL2 sl so LSFR recursion sj clsj1 B 02sz B B cL1sJL1 B cszL foerL LFSR State Sequence output D D Di D t Dt D D Du t Dg D D DU U U L L U S L L L U l U U L l H l L L L 2 L U U L LU U L L L 1 U L U U LL L 0 L L lt1 U U L U L2 U L U L V U U U L L3 L 0 L U L U H U L4 L L U L 7 L L H U L5 H L L U Features of Linear Feedback Shift Registers efficient in hardware large periods good statistical properties analysis using algebraic techniques Singular vs Nonsingular LFSR Nonsingular LSFR Singular LSFR cLl cLO periodic ultimately periodic Period of LFSR Period of the Linear Feedback Shift Register lt L CD gt A If CD is irreducible Period of LFSR is the least positive integer N such that CD 1 DN N 2L 1 B If CD is primitive N 2L 1 LFSR maximumlength LFSR output msequence Golomb s randomness postulates 1 Necessary but not suf cient conditions for aperiodic pseudorandom sequence to look random In the cycle sNsi si SHNJ R1 of1 sof0 s l R2 total of runs 2m total of runs until 2m 2 ofruns of size in 2 R3 The autocorrelation function Ct has two values 1 if F0 cm i ION iflStSNl Golomb s randomness postulates 2 De nitions N periodic sequence Sequence ss0 s1 s2 for which Si 2 SiN Run A string of consecutive 0 s or consecutive 1 s which are neither proceeded nor succeeded by the same symbol Pseudonoise sequence pn sequence A binary sequence that satisfies Golomb s randomness postulates Autocorrelation Function Example d3 lt A37 D38 011001000111101 011 A D 1 001000111101011 7 CG N 15 d4 47 D48 A 011001000111101 110 A D m0 111010110 C4 4 Linear complexity Ls the length of the shortest LSFR that generates s Special cases s 000000 00 Ls 0 No LSFR exists Ls gt0 Properties of linear complexity For any sequence sn s0 s1 s2 sn1 l OSLsnSn 2 Ms 0 iff S 0000 000 n times 3 Ms n iff S 0000001 nl times 4 Ls 0 t s Ls Lt Linear complexity profile For any binaiy sequence s s0 s1 s2 sn1 linear complexity pro le of sn is the sequence L1L2L3 L n where Li Lsi Ls0 s1 s2 SH Linear complexity pro le LLtsNJ Properties of linear complexity pro le 1 jgti gt Lj 2 Li 2 LN1gt LN is possible only ifN 2 2 LN N1 N1 339IfLN1gtLN LN139 T T 39LN i INHN1IN BerlekampMassey Algorithm Sequence of length 2 2L generated by an unknown LF SR of length L 0110110110101010011010111010010101 Length 22L Unique LFSR ltL CDgt S L BerlekampMassey Algorithm 630 Algorithm Be ekamprMassey a1gonthm N l I abinar smuunccs 155153 5710flcngIhn 01 I Pl Il1cIlncarcomplcxhyLLS 015710 L15 5 n H LHL 71 BgmH NH lziiuImmn CD 1i1c N lt m dc Ihc 11 1ming mumm m Haw LIxul39upum v d detsm f 1 mm mml 2 J 2 22 11 d 1 thc n 10 he follvwing39 T 90117 CDltCD BD Dquot quot lfL g N2l1ICHLHN17 L mHN BLDltTD 23 NHN 1 3 Rmuran

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "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!"

#### "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."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.