### Create a StudySoup account

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

Already have a StudySoup account? Login here

# CryptographyComp Netwk Sec ECE 646

Mason

GPA 3.94

### View Full Document

## 35

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

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

## Reviews for CryptographyComp Netwk Sec

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

Lecture 12 Security Protocols Cryptographic Standards Companies Developing Cryptographic Hardware Secure Communication Systems e g DMS Security protocols eg SMIME SSL IPSec Security mechanisms eg digital signatures Algorithms eg DES AES RSA component Non cryptographic component communications administration OS security database security etc Cryptograph39 100 Cost of cryptography in the layer model of the Internet Cost of adding SMIME SET cryptography Application layer http ftp email SSL Transport layer tcp udp Internet protocol layer IPsec ip Network access layer ethernet atm Physical layer SlVIIME Secure Electronic Email protocol developed by RSA Data Security Inc in cooperation with consortium of several big companies in 1995 work on the corresponding Internet standard started by IETF 1997 enables secure communication between email programs from various companies multiple products using SMIME e g Netscape Communicator Microsoft Outlook Entrust and many others Cryptographic algorithms Triple DES RC240 AES DH RSA DSS SHAl MD5 Competition PGP SSL Secure WWW ecure ockets Layer protocol developed by Netscape in 1994 SSLv 30 in use since 1996 SSLv20 withdrawn since 1996 work on the equivalent Internet standard IETF TLS Iransport Layer ecurity TLS 10 SSL 31 the most widely deployed security protocol Secure browsers e g MS Explorer Mozilla Firefox Secure servers e g Microsoft Server Apache HTTP Server Multiple libraries eg OpenSSL open source Competition almost none in the past SHTTP PCT SSL Secure WWW ltgt browser server WWW 1 Parameter negotiation 2 Server authentication 3 Client authentication only on request 4 Key Exchange 5 Con dential and authenticated message exchange Cryptographic algorithms Con dentiality none RC4 40 RC240 DES40 RC4 128 RC2128 DES IDEA Triple DES AES Digital signatures RSA DSS Hash functions SHAl MD5 Key agreement RSA DH Fortezza SSL Encryption Algorithms Block cipher Stream cipher Algorithm Key size Algorithm Key size IDEA 128 RC44O 40 RC24O 40 RC4128 128 DES40 40 DES 56 3DES 168 Fortezza 80 AES 128 192 356 IPsec Virtual Private Networks VPN Loca etwor Security 3977 S e curity gateway Remote user local networks may belong to the same or diiTerent organizations security gateways may come from diiTerent vendors IPsec Virtual Private Networks VPN VPN Economic alternative to networks based on leased lines Cost reductiun up to 70 development by IETF Internet Engineering Task Force started in 1994 rst IPSec version RFC 182529 published in 1995 IPsec required in IPv6 optional w IPv4 S WAN Secure Wide Area Network interoperability test for products developed by various vendors 1995 Algorithms con dentiality DES Triple DES AES RC5 IDEA CAST Blow sh Triple IDEA authentication HMACMD596 HMACSHA196 key agreement IKE Competition SSL PPTP Microsoft Followup Course ISA 656 Network Security Cryptographic standards Secretkey cryptography standards Federal Banking International standards standards standards NIST ANSI ISO FIPS 46 1 DES X392 DES ISO 10116 Mom FIPS 462 DES Imam of an n bit FIPS 81 Modes of X3106 DES modes 39pher operation of operation ISOIEC 18033 3 FIPS 463 Triple X952 Modes of operation AES Camellla SEED ofTriple DES TDEA MISTYI CAST 128 MUGI FIPS 197 AES SNOW NIST FIPS National Institute of Standards and Technology Federal Information Processing Standards American Federal Standards Required in the government institutions Original algorithms developed in cooperation with the National Security Agency NSA and algorithms developed in the open research adapted and approved by NIST PublicKey Cryptography Standards unof cial industry standards industry standards RSA Labs IEEE PKCS P1363 PKCS international bank standards standards I ISO ANSI ISO ANSI X9 federal standards NIST FIPS PKCS PublicKey Cryptography Standards Informal Industry Standards developed by RSA Laboratories in cooperation with Apple Digital Lotus Microsoft MIT Northern Telecom Novell Sun First except PGP formal specification of RSA and formats of messages IEEE P1363 Working group of IEEE including representatives of major cryptographic companies and university centers from USA Canada and other countries Part of the Microprocessors Standards Committee Modern open style Quarterly meetings multiple teleconferences discussion list very informative web page with the draft versions of standards IEEE P1363 Combined standard including the majority of modern public key cryptography Several algorithms for implementation of the same function Tool for constructing other more specific standards Specific applications or implementations may determine a profile subset of the standard ANSI X9 American National Standards Institute Work in the subcommittee X9F developing standards for financial institutions Standards for the wholesale e g interbank and retail transactions np bank machines smart card readers ANSI represents USA in ISO ISO International Organization for Standardization International standards Common standards with IEC International Electrotechnical Commission ISOIEC JTCl SC 27 Joint Technical Committee 1 Subcommitte 27 Full members 21 Australia Belgium Brazil Canada China Denmark Finland France Germany Italy Japan Korea Holland Norway Poland Russia Spain Sweden Switzerland UK USA ISO International Organization for Standardization Long and laborious process of the standard development Study period NP New Proposal Minimum WD Working Draft 3 years CD Committee Draft DIS Draft International Standard IS International Standard Review of the standard after 5 years ratification corrections or revocation Publickey Cryptography Standards unof cial industry standards indu stry standards RSA Labs lip IEEE PKCS PKCS P13 63 international bank standards standards ISO ANSI ISO ANSI X9 federal standards NIST FIPS 1991 1992 1993 1994 1995 1996 199719981999 PKCS 711PKCS 13 5 PKCS 1 10 PKCS e e 9 PKCS 1 v20 IEEE P1363a 5 mi ANSI K930 DSA X96iEC iSA 6 X9s1 R A R W ISO 9796 10118 12 117703 DH a Mquot I 101183 14888D SA NIST FIP FIPS 180 1 93996 4NR 5 180SHA e e SHAl v U FIPS 1 sou a I IFS 186 1DSAampRSA RSA with OAEP IEEE P1363 discrete logarithm elliptic curve discrete logarithm RSA amp R W with ISO14888 or ISO 9796 DSA NR with ISO 9796 with ISO 9796 DH1 DH2 and MQV EC DHl EC DHZ and EC MQV RSA with OAEP IEEE P136321 discrete logarithm new scheme elliptic curve discrete logarithm new scheme RSA amp RW with ISO14888 or ISO 9796 DSA NR with ISO9796 with ISO 9796 new scheme DH1 DH2 amp MQV ECDH 1 ECDH2 amp ECMQV ANSI X9 Standards 39 discrete elliptic curve factorizatlo logarithm discrete logarithm signatur X942 DH1 DH2 MQV Industry standards discrete elliptic curVe fact0r1zat10 logarithm discrete logarithm PKC S l PKCS 1 RSA PKCS 13 new scheme PKCS 13 PKCS 1 Slgna quotr RSA i R W ECDSA key PKCS 2 PKCS 13 agreement DH ECDH1 2 ECMQV NIST FIPS 39 discrete elliptic curve factorizatlo logarithm discrete logarithm FIPS 1862 FIPS 1862 FIPS 1862 RSA DSA EC DSA key agreement International standards ISO r discrete elliptic curve logarithm discrete logarithm ISO 14888 2 ISO 148883 ISO 14888 3 ISO 9796 2 Iso 9796 3 ISO 9796 3 ISO 11770 3 ISO 11770 3 Notes for users of cryptographic products 1 Agreement with a standard does not guarantee the security of a cryptographic product Security secure algorithms guaranteed by standards proper choice of parameters secure implementation proper use Notes for users of cryptographic products 2 Agreement with the same standard does not guarantee the compatibility of two cryptographic products I compatibility the same algorithm guaranteed by standards the same protocol the same subset of algorithms the same range of parameters Major Companies Developing Cryptographic Hardware RSA Expo Floorplan Security Processors erine CA Los Gatos CA 915ng NETWORKS Mountain Vlew CA Security Processors Applications SSL IPSec WLAN 50 MbpslO Gbps encryption speed 1 K to 40 K sessionssec IO Options PCIe PCIPCIX HT Programmable multiprotocol support in a single design Complete singlechip security solution for both symmetric and asymmetric security processing with dynamic adaptability Selected Processors 1 a Chip name Encryption HMAC Data rate Public key other algorithms algorithms Mbps algorithms Broadcom DESCBC SHA1 500 DH Onchip RNG BCM5823 3DESCBC MD5 RSA AESCBC AESCTR Broadcom 3DESCBC SHA1 4800 none lnline lPsec processing BCM5841 AESCBC MD5 Onchip SA database AESCTR RN G Selected Processors 2 mmmsmmmm Chip name Encryption C Data rate Public key other al gorithms algorithms Mbps algorithms HiFn 7956 DESCBC SHA1 632 DH lPsec header and trailer 3DEsch Mp5 RSA processing IKE support AESCTR RN G AR HiFn 8350 DESC SHA1 4000 DH lnline lPsec processing HIPP III 3DESCBC MD5 RSA Onchip ase ESCBC AESXCBC IKE processing AESCTR RC4 Selected Processors 3 mm 9139911 NETWORKS Chip name Encryption HMAC Data rate Public key Other algorithms algorithms Mhps algorithms CN1010 3DES SHA1 1000 DH lPsec header and trailer AES MD5 RSA processing IK support RC4 Onchip SA database CN1340 3DES SHA1 3200 DH lnline lPsec processing AES M05 RSA Onchip SA database RC4 IKE processing RNG RSA results reported in the industry using ASICs Number of the RSA 1024 bit signatures per second SafeNet SafeXcel 1842 2100 Cavium CN1340 Nitrox 42000 Network Processors with Cryptographic Accelerators Netronome Pittsburgh PA Network Processors with Cryptographic Accelerators HighPerformance Solution for Applications from MultiGbps to 10 Gbps and Beyond Chip name Encryption HMAC Data rate Public key Other algorithms algorithms Mbps algorithms Intel DESCBC SHA 1 10000 none Network processor XP2850 3DESCBC with fryinttog aph c acce era or an o AESCBC flowthrough processing 20 Smart Card Chips San Jose CA Tokyo Japan Neubiberg Bavaria Germany South Korea GENEVA Switzerland Eindhoven The Netherlands Smart Cards Gemplus Axalto formerly Schlumberger Tacoma WA Giesecke amp Devrient Munich Germany Israel Irvine CA 21 Hardware Accelerators for Password Recovery Waukesha WI Crypto Device Makers UK Cambridge UK 22 Crypto Cores Cambridge England Newport Beach CA Mississauga Ontario Canada Amphion IP cores 1 m N G CONE AES Encryption rtexII FPGA ASIC TSMC 180nm ASIC Size Slices Data rate Nbps Size gates Data rate Mbps FPGA Compact 403 4 BRAM 350 148K 581 Standard 696 4 BRAM 250 341 182K 426 581 170 Fast 573 10 BRAM 1323 27K 2327 176 Ultra fast 2181 100 10880 203K 25600 235 BRAM AES Decryption Compact 549 4 BRAM 290 164K 581 200 Standard 746 4 BRAM 290 426 192K 426 581 136 Fast 778 10 BRAM 1064 34K 2327 219 Ultra fast 3998 100 9344 283K 25600 BRAM Simplex AES Encryption I Decryption Compact 799 6 BRAM 290 25K 581 200 standard 1256 18 BRAM 930 493K 2327 250 Amphion IP cores 2 AMGg EDN C can DES I 3DES Encryption I Decryption Virtexll FPGA ASIC TSMC 180nm Size Slices Data rate Mbps Size gates Data rate Mbps ASIC FPGA Ultra compact 527 128 79K 266 208 Compact 803 240 118K 533 222 Fast 1367 430 218K 1067 L48 Ultra fast 4305 1941 567K 4267 220 SHA1 amp SHA2 cores SHA1 854 626 17K 1264 2m SHA256 1122 420 26K 1575 375 SHA 256 2403 390 52K 1307 33 5 I384 I 512 626 2098 335 Hellon Techn nlnmes cores AES Encryption or Decryption rtexll FPGA ASIC TSMC 180nm ASIC Size Slices Data rate Size gates Data rate Nbps FPGA Mbps Tiny lt 25 lt 30 120 Standard 392 LUT 223 lt 11K gt 500 2 24 3 BRAM 39 Fast 899 LUT 1699 lt 31 K gt 2000 mg 10 BRAM Pipelined 7 gt 10000 gt 25000 250 DES amp 3DES DES 888 LUT 640 lt 6K gt 1250 195 3DES 230 gt 460 200 SHA1 573 874 20K gt 1000 114 MD5 613 1 744 16K 1140 153 BRAM SHA256 849 1 685 lt 22K 1575 230 BRAM FPGA RSA Cores from Helion Technology Medium rate applications TARCET TYPICAL PERFORMANCE R A operations Altera PPCA stratix ll 1 35 Altera PPCA stratix ill 2 49 Xilinx PPCA 18 Spartan 1 5 Xilinx PPCA rtex 4 11 32 Xilinx PPCA rtex 5 1 38 AREA 225 ALuT 1 WK RAM 61 N512 RAMs 2123ALUT5 2 NBK RAMs 55 MLAEs 152s slices 1 ElockRAM 152s slices 1 ElockRAM 555 slices 1 ElockRAM Low rate applications TARGET Altera PPCA Cyclone lll 6 Altera PPCA stratix ill 2 Xilinx PPCA Spartan 1 5 Xilinx PPCA Virtex 4 11 Xilinx PPCA Virtex 5 1 TYPICAL PERFORMANCE SA operations operation 1024bit RSA signature AREA sac LEs 4 NBK RAMs 415ALuTs 4 NBK RAMs 212 slices 1 ElockRAMs 212 slices 1 ElockRAMs 155 slices 1 ElockRAM Assessment Labs Santa Clara CA Fairfax VA McLean VA San Luis Obispo CA San Diego CA 25 ECE 646 Lecture 9 Modes of operation of secretkey block ciphers Block vs stream ciphers M1M2MN m1mzmN Q Q 1s1 IV K lgt BIOCk K lgt Stream ciOISi mi ci her IS NS 18 m p Clpher 11 1 1 C1C2CN c1czcN CiszaVD 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 Typical stream cipher Sender Receiver k initialization k initialization vector vector Pseudorandom Pseudorandom Key Key Generator Generator ki keystream ki Lkeystream 39 w mi Ci Ci Ini plaintext ciphertext ciphertext plaintext Standard modes of operation of block ciphers Block ciphers ECB mode Stream ciphers Counter mode OFB mode CFB mode CBC mode ECB Electronic CodeBook mode Electronic CodeBook Mode ECB M1 M2 M3 MNl MN C1 C2 C3 CN l CN C1 EKMi for i1 N Counter Mode Counter Mode CTR Encryption IV IV1 IV2 IVN 1 IVN ci mi 43 ki k1 EKIVi1 for i1N Counter Mode CTR Decryption IV2 IVN IVN 1 IV1 m1 ci 69 ki ki EKIVi1 for i1N Counter Mode CTR IV IV 1 I 1 L 1 L IN IN K gt E K gt E OUT OUT 1 L 1 L IS1 IV Ci EKGSi 9 mi ISM 1si1 Jbit Counter Mode CTR IV IV1 IV2 IVN 1 IVN ki EIVi11j for i1N Jbit Counter Mode CTR IV IV i OFB Output FeedBack Mode Output Feedback Mode OFB Encryption ci mi 43 ki ki EKki1 for i1N and k0 IV Output Feedback Mode OFB Decryption m1 ci 69 ki ki EKki1 for i1N and k0 IV Output Feedback Mode OFB Ci EKUSi 9 mi ISM EKUSi J bit Output Feedback Mode OFB V 1V shift 1 shi 1 CFB Cipher FeedBack Mode Cipher Feedback Mode CFB Encryption ci mi 43 ki ki EKci1 for i1N and c0 IV Cipher Feedback Mode CFB Decryption ci mi 43 ki ki EKci1 for i1N and c0 IV Cipher Feedback Mode CFB K IS1 IV OUT 1 L ci EKISi 43 mi ISM Ci Jbit Cipher Feedback Mode CFB IV IV shift 1 j bits Lj bits j 11 CBC Cipher Block Chaining Mode Cipher Block Chaining Mode CBC Encryption m3 mN l mN E3 LN ci EKmi 69 cH for i1N c0IV Cl 32 12 Cipher Block Chaining Mode CBC Decryption cN m1 DKci 69 ci1 for i1N c0IV Comparison among various modes 13 Block Cipher Modes of Operation Basic Features 1 ECB CTR OFB CFB CBC Security weak strong strong strong strong B35 speed SECB mSECB m lL39SECB jL39SECB msECB Capability for parallel Encryptlon Encryptlon None Decryption Decryption processing and and only only and pipelining decryption decryption Cipher Encryption Encryption Encryption Encryption Encryption operations and only only only and decryptlon decryption PreProceSSing No Yes Yes No No Random RW W No R only R only access Block Cipher Modes of Operation Basic Features 2 ECB CTR OFB CFB CBC Security against the exhaustive key search attack Minimum num ber of l plaintext 2 plaintext 2 plaintext 1 plaintext l plaintext the message block blocks blocks blocks blocks and ciphertext 1 Ciphel teXt 2 Ciphertext 2 ciphertext 2 ciphertext 2 ciphertext blocks block blocks blocks blocks blocks needed for FL for jL Error propagation in the decrypted message Modi cation 0fjbits L bits bits bits LJ bltS Lt bltS Current and Current and Current and Current and Deletlon Of l blts all subsequent all subsequent all uh ennent L bus 311 SUbsequem Integrity No No No No No 14 New modes of operation Operating Modes Contest 4 Old Modes CBC CFB OFB ECB April 2001 10 New Candidates from Egypt Estonia Norway Sweden Thailand USA Counter mode Summer 2001 5 Standard Modes 2002 New Standard Modes 15 Modes submitted to the contest 1 Full name Authors Institution A A Belal Alexandria ZDEM 2D Enmypuon MOde M A Abdel University Gawad Egypt ABC Accumulated Block L Knudsen U OfBergen Chaining NOI39W y H Lipmaa Finland CTR C Gunter M 0 de P Rogaway Estonia USA D Wagner Thailand IACBC Integrity Aware CBC C Jutla IBM USA IAPM Integrlty Aware C Ju a IBM USA Parallalizable Mode Modes submitted to the contest 2 Full name Authors Institution IGE Infinite Garble V D Gligor VDG Inc Extension P Donescu USA KFB Key Feedback Mode J Hastad NADA M Naslund Ericsson Sweden UCSD USA OCB Offset Codebook P Rogaway Thailand PCFB Propagating Cipher H Hellstr m Streamsec Feedback swede XCBC eXtended CBC V D Gligor VDG Inc Encryption P Donescu USA 16 Evaluation Criteria for Modes of Operation Security Functionality Efficiency Evaluation criteria 1 Security resistance to attacks proof of security random properties of the ciphertext Efficiency number of calls of the block cipher capability for parallel processing memoryarea requirements initialization time capability for preprocessing l7 Evaluation criteria 2 Functionality security services confidentiality integrity authentication exibility variable lengths of blocks and keys different amount of precomputations requirements on the length of the message vulnerability to implementation errors requirements on the amount of keys initialization vectors random numbers etc error propagation and the capability for resynchronization patent restrictions Modes of operation Current standard CBC mN i mN Problems No parallel processing of blocks from the same packet No speedup by preprocessing No integrity or authentication 18 ECE 646 Lecture 9 RSA Genesis operation amp security Public Key Asymmetric Cryptosystems Public key of Bob KB Private key of Bob kB f g g Encryption V Decryption Alice Bob Trapdoor oneway function Whit eld Dif e and Martin Hellman New directions in cryptography 1976 PUBLIC KEY X fX Y f391Y PRIVATE KEY Professional NSA vs amateur academic approach to designing ciphers Know how to break Russian 1 Know nothing about ciphers cryptology Use only wellestablished 2 Think ofrevolu onary proven methods ideas 3 Hire 50000 mathematicians 3 Go for skiing 4 Cooperate with an industry 4 Publish in Scienti c giant American Keep as muCh as P0551131e 5 Offer a 100 award for Secret breaking the cipher Cipherlext 9585 9513 7545 2205 1477 1409 2225 4355 8829 0575 9991 1245 7431 9874 5951 2093 0815 2982 2514 5708 3559 3147 5522 8839 8952 8013 3919 9055 1829 9451 5781 5145 Public key 114381625757 88886766923577997614 661201021829672124236256256184293 570693524573389783059712356395870 505 8989075147599290026879543541 e 9007 Award 5100 Challenge published in Scienti c American 129 decimal digits RSA as a trapdoor oneway function PUBLIC KEY CfM Me modN C PRIVATE KEY N pQ P Q large pn39me numbers e d E 1 mod P1Q1 RSA keys PUBLIC KEY PRIVATE KEY N 7 ILP e E3 Q N P Q P Q large prime numbers e d E 1 mod Pl Ql Why does RSA work 1 7 M CdmodN ME modNcl modN M decrypted original message message e d 1 mod P1Q1 e d E 1 mod N Euler s totith function Euler s totient phi function 1 qN 7 number ofintegers in the range from 1 to N71 that are relatively prime with N Special cases 1 P is prime P Pl Relatively primewith P 1 23 P1 2 NPQ PQareprime MN P1Q1 Relatively prime with N 1 2 3 PQl 7 P 2P 3P 21 7 Q 2Q 3Q P1Qgt Euler s totient phi function 2 Special cases 3 N P2 P is prime N P 39Pl Relatively pn me with N 1 2 3 PZl 7 P 2P 3P P1P In general If N Plel p222 p323 Ptet MN 1391 Pr ltP1gt ll Euler s Theorem Lennard Euler 170771783 V a Pa D E 1 mod N a gcda N 1 Euler s Theorem Justification 1 For N10 For arbitrary N R1379 Rltxxz X Ngt Let 213 Let us choosearbitmrya such that gcdaN1 s 3391m d 10 s ax modN axzmodN 33mod1037mod10 H m N 39m0d10 90 39177 reaxranged set R Euler s Theorem Justification 2 For N10 For arbitrary N R S R S xx2 x3 x4 2 1W 1W aX1 maex ax4modN 1391 x r l39l 21 x mow 11 1 1W 1W xl39xl 39x3 39x4 aAxrxzxzxAmodN H X 21W H x modN Fl ll 1 modN MD 2 1 modN Why does RSA work 2 CdrnodN ME rnodNcl modN 7 d 7 edzlmodwCN 7M5 modNi d1kwN MHk Pm modN M MWW rnodN M MWDmOle modN M 1k modNM Rivest estimation 1977 The best known algorithm for factoring a 129digit number requires 40 000 trilion years 40 1015 ears assuming the use ofa supercomputer being able to perform 1 multiplication of129 decimal digit numbers in In Esu39niaiea age omie universe 100 bln years 10quot years Lehmer Sieve Bicycle chain sieve D H Lehmer 1928 g V 217 lr39l I Computer Museum Mountain View CA Machine Congruences E O Carissan 1919 Supercomputer Cray G AV 1 an neaEAncNlNc Computer Museum Mountain View CA Early records in factoring large numbers equire computational power in MIPSyears 1974 0001 1984 01 1991 7 1992 75 1993 120 398 830 How to factor for free A Lenstra ampM Manasse I989 Using the spare time of computers otherwise unused Program and results sent by e mail later using Practical implementations of attacks Factorization RSA Year N r dillgg igs Method 1994 430 129 QS 5000 MIPSyears 1996 433 130 GNFS 750 MIPSyears 1998 467 140 GNFS 2000 MIPSyears 1999 467 140 GNFS 8000 MIPSyear Breaking RSA 129 How 1600 computers Cray C90 through 16 MHz PC 0 I S 0mg 0 03 camputaliunalpnwer of the Internet Results or cryptanalysis he magic word are squeamish usszfrage An amrd of 100 donated to Free So ware Foundation August 1993 1 April 1994 8 months D Atkins M Gmff A K Lenstra P Leyland 600 volunteers from the entire World Elements affecting the progress in factoring large numbers I computational power 19771993 increase ofabout 1500 times I computer networks Internet better algorithm General purpose Time uf zctmmg depends only an the Size qu GNFS General Number Field Sieve os Quadratic Sieve Continued Fraction Method hzsmncal Factoring methods Special purpose TZWLE uf zctmmg ZS much shorter sz mfactms qu are ufthe special form ECM Elliptic Curve Method Pollard s pl method Cyclotomic polynomial method SN39FS Special Number Field Sieve Running time of factoring algorithms Lam c exp CU1391n q 391n 1quot 1 For 10 Algorithm polynomial m as a function oftnenumbec qu39 C 1quot 1 D ofbits ofq For 11 Algorithm exponential L41 c expltltcult1gtgtlt1n q 0st OM For 0ltalt1 as a function oftnenumbec ofbits ofq fn 01 iffor any positive constant cgt0 there exist a constant n gt0 such thato S nlt cfona11 n 2nn General purpose factoring methods Expected running time QS N39FS Liilz11wltlt1 alt1gtgtanmmgtgtan tum LNl3192exp192 111 1an 1n Ink7 QS mm NFS mm e ieient e ia39ent 100D 1 130D 0 U 0 U Nin decimal digits D First RSA Challenge RSAVIEIEI RSArl 1U RSArlZU RSAVIKEI RSAVHEI RSAVISEI Rsarmu RSA200 May 2005 RSA717EI RSAVIBEI RSAVIBEI RSAVZEIEI RSAerU Largest number factored to date RsAAsn RsAA n RSAJWEI RSAAXU RSAABU RsAesun Second RSA Challange Lentgh of N Length of N a in bits in decimal digits factorization Number of his vs number of decimal digits 10mm 2mm digim log10 2 bim as 030 bim 256 bits 77D 384 bits 116 D 512 bits 154 D 768 bits 231 D 1024 bits 308 D 2048 bits 616 D Factoring 512 bit number 512 bits 155 decimal digits old standard for key sizes in RSA 1 7March 22 August 1999 Group of Herman te Riele Centre for Mathematics and Computer Science CW1 Amsterdam First stage 2 months 168 Workstations SGI and Sun 175400 MHz 120 Pentian PC 300450 MHZ 64 MB RAM 4 stations DigitalCompaq 500 MHz Second stage Cray C916 10 days 23 GB RAM Factoring RSA576 512 bits 155 decimal digits When Announced December 3 2003 Who J Franke and T Kleinjung Balm Univmnw Max leklnxu39mtefurmthm cs in Balm ExperbnemlMuthenm39cxInm39mte in Essen P Montgomery and H to Riele 7 C F Bahr D Leclair P Leyland and R Wackerbarth man FedemlAgenLy rInfmm un Tetlmulagy Security BIS Factoring RSA200 When 200 decimal digits 664 bits Dec 2003 May 2005 Who CWI Netherlands 8mm Umvzrslty Effort Technulugy Secnnzy 8139 First stage About 1 year on various machines equivalent to 55 years on Opteron 22 GHz CPU Second stage 3 months on a cluster of 80 22 GHz Opterons connected via a Gigabit network Factoring RSA640 640 bits 193 decimal digits When June 2005 Nov 2005 7 Whu39 CWI Netherlands 8mm Unzvmry Max Planck Instztutz fm Mathemancs m 8mm Expenmzmal Mathematzcs Instztute m Essen German FederalAgzmyfm Infmmatmn Effort Technulugy Secnnzy 31 First stage 3 months on 80 Opteron 22 GHz CPUs Second stage 15 months on a cluster of 80 22 GHz Opterons connected via a Gigabit network For the most recent records see Factorization Announcements at TWINKLE The Weizmann INstitute Key Locating Engine Adi Shamir Eurocrypt May 1999 CHES August 1999 Electrooptical device capable to speediup the rst phase of factorization from 100 to 1000 times If ever built it would increase the size of the key that can be broken from 100 to 200 bim Cost of the device assuming that the prototype was earlier built 7 5000 Recommended key sizes for RSA Old standard Individual users 1 New standard 768 him Individual users 231 decimal digits 1024 him Orgammuons slim mini 308 decim a1 digits Organimlions long mini 616 decimal digits Keylengths in public key cryptosystems that provide the same level of security as AES and other secretkey ciphers Arjen K Lenstra En39c R Verheul Selecting Cryptographic Key Sizes Journal of Crwtology Arj en K Lenstra Unbelievable Security Matching AES Security Using Public Key Systems ASIACRYPT 2001 RSA vs DES Resistance to attack Number of operations in the best known attack NDE S 150 NDES DES 5127bit RSA 564m key of security as selected The same cost AEer28 AEer92 AEer56 Practical progress in factorization March 2002 Financial Cryptography Conference Nicko van Someren CTO nCipher Inc announced that his company developed software capable of breaking 512bit RSA key Within 6 weeks using computers available in a single of ce Bernstein s Machine 1 Fall 2001 Daniel Bernstein professor of mathematics U 39 ersity of Illinois in Chicago submits a gmnt application to NSF and publishes fragments of this application as an anicle on the Web D Bernstein Circuits for Integer Factorization A Proposal httpcryptopapershtmlnfscircuit Bernstein s Machine 2 March 2002 I Bernstein s article discovered durin Financial Cryptogrqvhy Conference I Informal panel devoted to analysis of consequences of the Bernstein s discovery Nicko Van Someren nCipher estimates that machine costing 1 bilion is able to break 1024 bit RSA Within several minuts Bernstein s Machine 3 March 2002 alarming voices on emailing discussion lists calling for revocation of all currently used 1024bit keys sensational articles in newspapers about Bernstein s discovery Bernstein s Machine 4 April 2002 Response of the RSA Security Inc Error in the estimation presented at the conference according to formulas from the Bernstein s article machine costing 1 billion is able to break 247bit RSA Within 10 billion x several minuts tens ofyears According to estimations of Lenstra i Verheul machine breaking 1024bit RSA Within one day Would cost 160 billion in 2002 Bernstein s Machine 5 Carl Pomerance Bell Labs fresh and fascinating idea Arjen Lenstra Citibank amp U Eindhoven Ihave no idea What is this all fuss abou Bruce Schneier Counterpane enormous improvements claimed are more a result of rede ning ef ciency than anything else Bernstein s Machine 6 RSA keylength that can be broken using Bernstein s niachine RSA keylengths that can be broken using classical computers 3 2 7 7 1 7 7 39 1 bln1 day s 1000 bln1 day in nity nmnumlinnnl Lime da memory 3 Estimation of RSA Security Inc regarding the number and memory ofPCs necessary to break RSA 1024 Attack time 1 year Single machine PC 500 MHz 170 GB RAM Number of machines 342000000 TWIRL February 2003 Adi Shamir ampEran Tromer Weizmann Institute ofScience Hardware implementation of the sieving phase of Number Field Sieve NFS Assumed technology CMOS 013 pm clock 1 GHz 30 cm semiconductor Wafers at the cost of 5000 each TWIRL A Shamir E Tromer Crypto 2003 Tentative estimations no experimental data 5127bit RSA lt 10 minutes 1024b RSA lt 1 year 10 million Estimated recurring costs with current technology US Xyear by Eran Tromer May 2005 768bit 1024bit But NRE chip size chip transport networks ECE 646 Lecture 10 RSA Genesis operation amp security Public Key Asymmetric Cryptosystems Public key of Bob KB Private key of Bob kB g g Encryption V Decryption Alice Bob Trapdoor oneway function Whit eld Dif e and Martin Hellman New directions in cryptography 1976 PUBLIC KEY X fX Y f391Y PRIVATE KEY Professional NSA vs amateur academic approach to designing ciphers 1 Know hoW to break Russian 1 Know nothing about ciphers cryptology 2 Use only Wellestablished 2 Think of revo1mionary proven methods ideas yd Hire 50000 mathematicians 3 Go for skim 4 Cooperate with an industry 4 Publish in Scienti c glam American 5 Keep as quot1011 as 130551171e 5 Offer a 100 award for Secret breaking the cipher Challenge published in Scientific American Cipherth 9686 9613 7546 2206 14771409 2225 4355 8829 0575 9991 1245 74319874 69512093 0816 2982 2514 5708 3569 3147 6622 8839 8962 8013 3919 9055 1829 945157815145 Public key N 114381625757 88886766923577997614 661201021829672124236256256184293 570693524573389783059712356395870 5058989075147599290026879543541 e 9007 129 decimal digim Award 100 RSA as a trap door one way function PUBLIC KEY M CfMMemodN c PRIVATE KEY N p Q p Q large prime numbers ed 21 mod P1Q1 RSA keys PUBLIC KEY PRIVATE KEY N 7 ILP e E2 Q N P Q P Q large prime numbers e d E 1 mod Pl Ql Why does RSA work 1 7 M CdmodN ME modNdmodN M decrypted original message message e d 1 mod P1Q1 e d E 1 mod N Euler s totith function Euler s totient phi function 1 pN 7 number ofintegers in the range from 1 to N71 that are relatively prime with N Special cases 1 P is prime P Pl Relatively primewith P 1 23 P1 2 NPQ PQareprime NP1 Q1 Relatively prime with N 1 2 3 PQl 7 P 2P 3P 21 7 Q 2Q 3Q P1Qgt Euler s totient phi function 2 Special cases 3 N P2 P is prime N P 39Pl Relatively pn me with N 1 2 3 PZl 7 P 2P 3P P1P In general If N Plel p222 p323 Ptet MN 1391 Pr ltP1gt ll Euler s Theorem Lennard Euler 170771783 V am 2 1 mod N a gcda N 1 Euler s Theorem Justification 1 For N10 For arbitrary N R1379 Rltxxz WWW Let 213 Let us choosearbitmrya such that gcdaN1 s 3391m d 10 s ax modN axzmodN 33mod1037mod10 H m N 39m0d10 90 39177 reaxranged set R Euler s Theorem Justification 2 For N10 For arbitrary N R S R S xx2 x3 x4 2 1W 1W aX1 maex ax4modN 1391 x r l39l 21 x mow 11 1 1W 1W xl39xl 39x3 39x4 aAxrxzxzxAmodN H X 21W H x modN Fl ll 1 modN MD 2 1 modN Why does RSA work 2 CdrnodN ME rnodNcl modN 7 d 7 edzlmodwCN 7M5 modNi d1kwN MHk Pm modN M MWW rnodN M MWDmOle modN M 1k modNM Rivest estimation 1977 The best known algorithm for factoring a 129digit number requires 40 000 trilion years 40 1015 ears assuming the use ofa supercomputer being able to perform 1 multiplication of129 decimal digit numbers in In Esu39niaiea age omie universe 100 bln years 10quot years Early records in factoring large numbers equire computational power in MIPSyears 1974 0001 1984 01 1991 7 1992 75 1993 120 398 830 How to factor for free A Lenstra ampM Manasse I989 Using the spare time of computers otherwise unused Program and results sent by e mail later using Practical implementations of attacks Factorization RSA Year N r dillgg igs Method 1994 430 129 QS 5000 MIPSyears 1996 433 130 GNFS 750 MIPSyears 1998 467 140 GNFS 2000 MIPSyears 1999 467 140 GNFS 8000 MIPSyear When Who D Atkins M Gmff A K Lenstra P Leyland 600 volunteers from the entire World HoW39 1600 computers 0mg 0 03 currqmtaliunalpnwer of the Internet Results at cryptanalysis Breaking RSA 129 August 1993 1 April 1994 8 months Cray C90 through 16 MHz PC 0 I 5 he magic word are squeamish usszfrage An amrd of100 is donated to Free So ware Foundation Elements affecting the progress in factoring large numbers I computational power 19771993 increase ofabout 1500 times I computer networks Internet I better algorithm Factoring methods General purpose Special purpose TZWLE Uf zctmmg ZS much Shmter th mfartm qu are ofch special form Time af zctmmg depends only an the Size qu GNFs General Number ECM Elliptic Curve Method Field Sieve os Quadratic Sieve Pollard s pl method c It 39 1 39al th d ContinuedFraLtionMethod y m p yquot m me hzstmzcal SN39FS Special Number Field Sieve Running time of factoring algorithms le cl exp CU1 1n Q 391n 1n 1 For 0 Algorithm polynomial m as a function oftnenumbec qu39 C 1quot 1 D ofbits ofq For 11 Algorithm exponential L41 c expltltcult1gtgtlt1n q 0st OM For 0 lt ot lt 1 39 as a function oftnenumbec ofbits ofq fn 01 iffor any positive constant cgt0 there exist a constant n gt0 such thato S nlt cfona11 n 2nn General purpose factoring methods Expected running time QS N39FS Hill21 EW1 01 in N In in NJ LNl3192exp192 om lan 1n inmw QS mm NFS mm e ieient e ia39ent 100D 1 130D 0 U 0 U Nin decimal digits D RSA Challenge Rsneiuu Smallest unfactored number RSArl 1U RSArlZU RSAVIKEI RSA HU RSA150 RSAVISEI RSArl U RSAVWU Unused awards accumulate at arate RSAVIBU ofl750 qua1ter RSAASU RSAA U RSAJWU RSAABU RSAJWU RSAVSUU Factoring 512 bit number 512 bits 155 decimal digits old standard for key sizes in RSA 1 7March 22 August 1999 Group of Herman te Riele Centre for Mathematics and Computer Science CW1 Amsterdam First stage 2 months 168 Workstations SGI and Sun 175400 MHz 120 Pentium PC 300450 MHZ 64 MB RAM 4 stations DigitalCompaq 500 MHz Second stage Cray C916 10 days 23 GB RAM TWINKLE The Weizmann INstitute Key Locating Engine Adi Shamir Eurocrypt May 1999 CHES August 1999 Electrooptical device capable to speediup the rst phase of factorization from 100 to 1000 times If ever built it would increase the size of the key that can be broken from 100 to 200 bim Cost of the device assuming that the prototype was earlier built 7 5000 Recommended key sizes for RSA Old standard Individual users 1 New standard 768 him Individual users 231 decimal digits 1024 him Organlmuons short term 308 decim a1 digits Organimlions long term 616 decimal digits Keylengths in public key cryptosystems that provide the same level of security as AES and other secretkey ciphers Arjen K Lenstra En39c R Verheul Selecting Cryptographic Key Sizes Journal of Crwtology Arj en K Lenstra Unbelievable Security Matching AES Security Using Public Key Systems ASIACRYPT 2001 RSA vs DES Resistance to attack Number of operations in the best known attack NDE S 150 NDES DES 5127bit RSA 564m key of security as selected The same cost AEer28 AEer92 AEer56 Practical progress in factorization March 2002 Financial Cryptography Conference Nicko van Someren CTO nCipher Inc announced that his company developed software capable of breaking 512bit RSA key Within 6 weeks using computers available in a single of ce Bernstein s Machine 1 Fall 2001 Daniel Bernstein professor of mathematics U 39 ersity of Illinois in Chicago submits a gmnt application to NSF and publishes fragments of this application as an anicle on the Web D Bernstein Circuim for Integer Factorization A Proposal httpcryptopapers htmlnfscircuit Bernstein s Machine 2 March 2002 I Bernstein s article discovered durin Financial Cryptogrqvhy Conference I Informal panel devoted to analysis of consequences of the Bernstein s discovery Nicko Van Someren nCipher estimates that machine costing 1 bilion is able to break 1024 bit RSA Within several minuts Bernstein s Machine 3 March 2002 alarming voices on emailing discussion lists calling for revocation of all currently used 1024bit keys sensational articles in newspapers about Bernstein s discovery Bernstein s Machine 4 April 2002 Response of the RSA Security Inc Error in the estimation presented at the conference according to formulas from the Bernstein s article machine costing 1 billion is able to break 247bit RSA Within 10 billion x several minuts tens ofyears According to estimations of Lenstra i Verheul machine breaking 1024bit RSA Within one day Would cost 160 billion in 2002 Bernstein s Machine 5 Carl Pomerance Bell Labs fresh and fascinating idea Arjen Lenstra Citibank amp U Eindhoven Ihave no idea What is this all fuss about Bruce Schneier Counterpane en rmous improvements claimed are more a result of rede ning ef ciency than anything else Bernstein s Machine 6 RSA keylength that can be broken using Bernstein s machine RSA keylengths that can be broken using classical computers 3 2 7 7 1 7 7 39 Slbln day 1000 bln1 day infinity nmnumlinnnl Lime oa 1 memory 1 RSA Challange Lentgh of N Length of N Award for in bits in decimal digits factorization 193 ECE 646 Lecture 12 Key management Using the same key for multiple messages M1 M2 M3 M4 M5 time EK Using Session Keys amp Key Encryption Keys K1 K2 K3 if if if i tlme ii i a IEKEKK1 EKEKK2 EKEKK3 M1 M2 M3 M4 M5 time Key Distribution Center KDC KBimC Kcm IDil C Simple key establishment protocol based on KDC KAil C KBilGC KCJGC IDil C let me talk Bob KBKDC A1iceaa 23 KAKDC BOb KAB Alice Bob KAVKDC KBVIQC Key establishment protocol based on KDC IAil C KBimC 1 let me talk with Bob 2 KAKDC BO KAB tiCketBob 3 ticketB0b KBKDC Alice K AB B Bob IArKDC KBrIGC Alice Key agreement Alice Bob A 5 private key B s private key A s public key B s public key V Secret derivation Key derivation Key derivation Key of A and B Key OfA and B Dif eHellman key agreement scheme Alice Bob 0t q global pubhc elements X yA0t Amodq yBotXBmodq XA Key derivation Key derivation l 1 Key K AB Key K AB Maninthemiddle attack Alice Bob A 5 private key B s private key A s public key B s public key Charlie Secret C s public C s public derivation key key I Key of A and C Key OfB and C Secret derivation Does public key cryptography have an Achilles heel Alice Bob Bob send me your public key Alice Bob s public key Bob message encrypted using Bob s public key Charlie Does public key cryptography have an Achilles heel Alice Bob Bob send me your public key Alice Bob spublirkey Bob Charlie s public key message encrypted using BoberpubHrkey Charlie s public key Charlie Does public key cryptography have an Achilles heel Alice Bob send me your public key Alice Bob spublirkey Bob Charlie s public key message encrypted message reencrypted using Charlies s 115mg BOb S public key Charlie PUbliC key Directory of public keys 1 On line 1 A L Alice Alice s public key Bob Bob s public key Charlie Charlie s public key Dave Dave s public key Eve Eve s public key Bob Bob s public key Alice message encrypted using Bob s public key Bob Charlie Directory of public keys 2 On line 1 A L Alice Alice s public key Bob Bob s public key Charlie Charlie s public key Dave Dave s public key Eve Eve s public key Alice message encrypted using WWuHirkey BOb Charlie s public key Charlie Directory of public keys 3 On line 1 A 1 Alice Alice s public key Bob Bob s public key Charlie Charlie s public key Dave Dave s public key Eve Eve s public key Alice BOb message encrypted message reencrypted using Charlie s using Bob s public key Charlie public key PGP Flow of trust Manual exchange of public keys Las Vegas Edinburgh Bob ltgt David David ltgt Betty Bob David Betty Washington New York London David send me Betty s public key Betty s public key signed by David message encrypted using Betty s public key Certification Authority Proof of identity Certlflcatlon Authority Public key of Bob Certi cate Public key of Certi cation Authority Certificate User s distinguished name User s public key User s Credentials Serial number Issuer name Expiration date CA s signature Distinguished Name DN according to X500 Example Common name CN Kris Gaj Country name C US State or province name ST VA Locality name L Fairfax Organization name O George Mason University Organizational unit name OU ECE Other elds permitted Street address SA DescriptiOIl D Post of ce bOX PO BOX T61Ph0ne number TN Postal code PC Ser1al number SN Title T Nonrepudiation only Alice Bob M SGNAM CertCAA KUQ Alice s private key KR A CA s public key KUCA Notation KUX public key of X SGNXM signature of X KRX private key of X for the message M CertYX KUX ceIti cate issued by Y for the user X Confidentiality only CA s public key KUCA On line 1 A L CertCAA KUA CertCAB KUB Cert C KU CertCAB KUB Ce 11 D KUE KABM3 KUBKAB Alice Bob Bob s private key KRB Confidentiality and Nonrepudiation Alice s private key KR A CA s public key KUCA On line 1 A L CenCAA KUA CertCAB KUB Cert C KU C It B KU CA C e CA a B CertCADKUD SGNAM CertCAA KUA KABM KUBKAB Alice Bob Bob s private key KRB CA s public key KUCA Public Key Infrastructure M SGNAM C6rtGMUA1 KUA ce FairfaxGMUa KUGMU CertVAFairfaX KUF CeITUSVA KUVA airfax Certificate Revocation Lists CRLs Issue time Issuer CA s name Serial numbers of revoked certi cates CA s signature Certi cate is valid if it has a valid signature of CA did not expire is not listed in the CA s most recent CRL Symmetric Key Generation with System Information An ECE 646 Semester Project Fall 2001 Paul Kohlbrenner ECE646 Project Final Report 7 Paul Kohlbrener Page 1 of 13 10 Introduction In my project speci cation I proposed to construct a system that generates a key by combining bits from a user and a user selectable set of other sources I accomplished this task The Skey system will encrypt a le using a pass phrase supplied by the user The pass phrase is combined with a random number to increase its entropy The random number is hidden using secret sharing and the shares are encrypted with data unique to the user s system Finally the encrypted shares are stored in the le header of the encrypted le Decryption begins much like the encryption process a pass phrase is obtained from the user and the unique system data is read The encrypted shares of the secret random number are decrypted and the random number generated when the le was encrypted is combined with the user s pass phrase to form the nal le decryption key 20 The Skey system 21 Major subsystems The Skey system has three major subsystems Each of these subsystems provides support to the driver program The subsystems are 0 The arbitrary length integer math package 0 The AES encryption package 0 The secret sharing package 22 The Math Module Contained in the les SkeyMathh and SkeyMathc the math module implements the functionality needed for the secret sharing module Integers can be any length Each integer must be separately allocated using functions from SkeyMath The maximum length of the integer is set at allocation time Functions supported are Addition Subtraction Multiplication Division with reminder Modular Multiplication Modular EXponentiation Random number generation Random prime number generation Assignment Comparison Initialization with 64 bit C integer Printing of numbers in he and decimal ECE646 Project Final Report 7 Paul Kohlbrener Page 2 of 13 Integers are represented as a pointer to a struct containing a pointer to an array of bytes a sign a length and a ag indicating wither the number was allocated from the heap or the local stack The Most Signi cant Byte MSB is located at the highest numbered array location This conforms to LittleEndian notation The Division algorithm used is the classical algorithm from the Handbook oprplz39ed Cryptography Algorithm 1420 I implemented the speedups suggested in Note 1423 The Modular Multiplication operation just multiplies the two operands into a larger temporary variable and performs a division by the modulus before returning the result I looked at using Montgomery multiplication but Note 1439 appears to recommend against this The Modular EXponentiation uses a simple righttoleft binary exponentiation algorithm The Random Number Generator will generate a random number the length of the return container passed to it The generator must be initialized by calling InitRandomNumberGenerator The pointer returned by this initialization call is then passed by the application to the generator each time a random number is requested The initialization routine uses four sources of random bits to initialize the system The 64bit return value from QueryPerformanceCounter This call returns the current value of the highresolution performance counter The 64bit return value from GetSystemTimeAsFileTime This call returns the current system time in 100ns increments The 32bit return value from GetCursorPos This call returns the current position of the mouse The 32bit return value from GetCurrentProcessId This call returns the current process ID ECE646 Project Final Report 7 Paul Kohlbrener Page 3 of 13 The two 64bit quantities are appended and set as the Input in the state struct The CursorPos is modeXp ed by the process id using a modulus the length of the desired return container This quantity is set as the Key in the state struct A random number is then requested using this constructed state The random number generator works by rst doing an AES encrypt of the Input value in the state using the Key value as a key The resulting quantity is then modeXp ed by the 64bit quantity obtained from a call to GetSystemTimeAsFileTime Finally the old Input value is moved to be the next Key value the result of the modeXp is set as the new Input value and the modeXp is returned as the random integer If the size of the requested random number is larger then 128 bits the process iterates until enough bits are generated I have not had time to assess the goodness of the random numbers produced by this process The prime number generator starts by calling the random number generator to get a random number This random number has its leastsigni cant bit set to make it odd and optionally it can have it s mostsigni cant byte set to 0X01 the secret sharing algorithm likes numbers like this The number is then passed to IsPrime where it is determined if the number is prime The routine iterates adding two each time until IsPrime returns true Is prime does a few trial divisions the rst 10 primes and then calls MillerRabin for 10 rounds Obviously using more then 10 primes could make this faster The math module contains a callable test suite Each major operation returns a coverage variable that indicates which functional blocks within the operation were exercised Note that this is not a true path coverage as not all unique paths through the routine are identi ed The test suite calls each of the operations with a number of test variables and records the combined test coverage achieved The test suite uses number that are less then 8 bytes long so that results can be compared to the same operation done with 64bit integers in C 23 The AES Module ECE646 Project Final Report 7 Paul Kohlbrener Page 4 of 13 The AES module is a very straightforward implementation of AES written from scratch from the draft standard and the original AES proposal It implements all three key sizes 128 192 256 bits and all three block sizes 128 192 256 Calling InitializeAES initializes the implementation The return value from the initialization is an Encryption Parameter pointer This pointer contains the block and key sizes passed to the initializer This allows several different parts of the Skey system to run encryptions using different block and key sizes each obtains it s own Encryption Parameter pointer To setup a key one calls SetupKey with a valid Encryption Parameter block The key schedule is created and stored in the Encryption Parameter block replacing any previous key schedule Finally the routine Cipher is called to encrypt a block Calling TestAES does testing of the AES module In TestAES the test vectors from the draft standard are passed to the encryption and the results are compared to the results from the draft standard Only the 128bit block size is checked with all three key sizes I implemented an extensive debug output scheme that exactly matched the internal state output from the draft standard This proved to be extremely useful during debugging as I could just file compare the output with a copy of the output from the draft standard I never had time to tune this AES implementation There are several unnecessary block moves and a number of other small things that could be done to increase the speed of the encryption I also did not have time to compare the speed of the encryption for files to other implementations 24 The Secret Sharing Module The Secret Sharing module is an implementation of Shimir s Threshold Scheme as documented in the Handbook of Applied Cryptography Mechanism 1271 As written this module will always create four shares but it can support a t value from 1 to 4 The size of the secret is fixed at 128 bits As suggested in Mechanism 1271 the interpolation formula constants are precomputed Considerable work needs to be done to make this module more configurable There is no automatic testing of this module There are a number of internal debug statements that can be turned on by using the debug control on the Skey command line ECE646 Project Final Report 7 Paul Kohlbrener Page 5 of 13 30 System Design Rania lrtcgm Hmh m 7ii7iii iiiii a Inth l Eurn h gt ms 1 111 Beak mv Kn mum 139 I Pl AF i I quot V gt quot Junstrum 1rllhnm1im Cup file Figure 1 The flow diagram for Skey encryption The diagram in Figure l illistrates the ow of the program during encryption The diagram above implies that the shares are directly encrypted by the AES using the environmental information as the key This is not quite correct What currently happens is the IV is encrypted using the environmental info as the key and the result of the encryption is used as a keystream to encrypt the share The Skey system works entirely from the DOS command line The help text is as follows ECE646 Project Final Report 7 Paul Kohlbrener Page 6 of 13 Skey Encryption System a ECE646 project Usage Skey ltkeysgt ltencryption parametersgt ltinput filegt ltoutput file Where ltkeysgt one or more of the following p ltguoted pass phrasegt use as part of key sltAuxKeysgt Use ltAuXKeysgt for Secret Sharing bit mask 0 15 range tltTvaluegt Number of shares required to decrypt ltencryption parametersgt zero or more of the following e Encrypt default d Decrypt kltNkgt Use ltNkgt for key size 32 bit words bltNbgt Use ltNbgt for block size 32 bit words X Enter test mode do timings etc gltngt Debug level default is 0 Notes 1 The default output file is the input filename with the string quotskeyquot appended The 7b block size option has never been tested I have left in a few debug statements so the share processing can be observed It is also possible to use the is ag to null out some environmental info on decryption for testing purposes this wouldn t normally make sense ECE646 Project Final Report 7 Paul Kohlbrener Page 7 of 13 Sum knitm qubal 55mm Sharing Uguullu V tment Elnaes lmm ki E1 Hulk 39A M E 3 o T p I h 1 r r I i w Emwhd A JLv 39 wmmnmm v39 Inlhnmllm Lhnp HHLc Figure 2 The flow diagram for Skey decryption The decryption ow is a bit similar to the encryption ow In fact much of the decryption logic uses the same routines as the encryption ow Obviously using CTR mode was a good choice from this perspective 40 Example Runs I have reproduced several runs of the Skey system below In general the text below is unedited I note that of ceial is misspelled but here and there I have deleted some lines from the dir output for example Commands Ityped are in bold First off we see the le skeytesttxt exists and is 182 bytes long C pxkprivategmuECE646Proj ectworkgtdir skeytest Directory of C pxkprivategmuECE646Proj ectwork 12152001 12303 182 Skeytesttxt l Fi1es 182 bytes 0 Dirs 7707590656 bytes free CpXkprivategmuECE646Proj ectworkgtty39pe skeytesttxt This is a test file for the skey program This is only a test In the event of a real emergency you would be notified ECE646 Project Final Report 7 Paul Kohlbrener Page 8 of 13 where to turn in your area for news and offical information Next we encrypt skeytesttXt using a threshold of 3 t3 and using all four environmental inputs s15 The is ag takes a bit mask of4 bits lwse info 0use random number CpxkprivategmuECE646Projectworkgtskeydriver t3 515 p quotthis is my test keyquot e skeytesttxt The program runs without any problems and we now have a new le called skeytesttXtskey CpxkprivategmuECE646Projectworkgtdir skeytest Directory of CpxkprivategmuECE646Projectwork 12152001 1230a 182 Skeytesttxt 12152001 1237a 1216 skeytesttxtSkey 2 Files 1398 bytes 0 Dirs 7707586560 bytes free Most of the header is empty its fixed at 1024 bytes Here are some he dumps of the first 280 bytes You can see some offsets in the first few bytes and then the encrypted shares and P and the IV etc 0000000 000000 01000000 01000000 00000000 b6000000 N 0000016 000010 80000000 28000000 00040000 OOfofff 0000032 000020 0000048 000030 0000064 000040 0000080 000050 0000096 000060 0000112 000070 0000128 000080 28000000 10000000 38000000 00000000 8 0000144 000090 38000000 10000000 48000000 40000000 8 H 0000160 0000a0 88000000 20000000 4e7554d2 2bb65f3f NuT 0000176 0000b0 0820dd25 e43484bb Cd8cf5b7 3ccddc9b 4 lt 0000192 000000 C5aa4151 9ad500d7 5f8661be 53e39ca4 0000208 0000d0 8fe65d7f 155101f9 2a5bf5ff 9b7cefaa 0000224 0000e0 994119e0 9df0d1c9 b6767523 060d66a1 0000240 0000f0 0dc41841 7e52d9cf 430550da fd8d13e4 0000256 000100 05df7490 2bd118d8 db26d50e ef0ab9dd tamp 0000272 000110 ec460eae 2da44546 01000000 00000000 F EF 0000288 000120 ECE646 Project Final Report 7 Paul Kohlbrener Page 9 of 13 The hex dump ofthe last 180 or so bytes follows 0001008 0003f0 0001024 000400 d8ab88f8 68c723c7 1725d58c 07c624d9 h 0001040 000410 2c7de72d fa5b3ef0 413f7225 e962cb3a gtArb 0001056 000420 2f9df23e dcd7c626 ac9309c3 e2e8f942 gtamp B 0001072 000430 ac0b563c d4b41779 63e652b9 593b4383 VltycRYC 0001088 000440 27b53742 90ca9e25 ef98fbfd c2996472 7B dr 0001104 000450 5ec64922 2125459e 70f13271 7b4f9b25 AIquotEp2q0 0001120 000460 d584eea5 b9dfeaa8 68fb0e1b fa7c12a2 hH 0001136 000470 be28d9a1 4af9a86a 5c9cbb2a fde7b498 Jj 0001152 000480 fb5fb488 f4248604 586669dd 69add4d7 Xfii 0001168 000490 0e5c52e4 e8ad72b7 bd356be2 0a046aab Rr5kj 0001184 0004a0 7c3600a7 9cd3e98c 64189385 a4446f13 l6 dDo 0001200 0004b0 e6262cfc 6ec9102f 790515d7 f4fbe5d5 ampny Next Itry a decryption The 7s15 parameter allows all 4 environmental info pieces to be passed through Remember we encrypted with a threshold of 3 CpxkprivategmuECE646Projectworkgtskeydriver 515 p quotthis is my test keyquot d skeytesttxtskey No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and 0 Found the secret with shares 0 1 and 2 As expected the secret was found with shares 0 l and 2 and the le was decrypted to skeytesttxtskeydcpt CpxkprivategmuECE646Projectworkgtdir skeytest Directory of CpXkprivategmuECE646Projectwork 12152001 1230a 182 Skeytesttxt 12152001 1237a 1216 skeytesttxtSkey 12152001 1239a 182 skeytesttXtskeydcpt 3 Fi1es 1580 bytes 0 Dirs 7707500544 bytes free ECE646 Project Final Report 7 Paul Kohlbrener Page 10 of 13 CpXkprivategmuECE646Projectworkgttype skeytesttxtskeydcpt This is a test file for the skey program This is only a test In the event of a real emergency you would be notified where to turn in your area for news and offical information Now delete the decrypted le and try a decryption with the is parameter at 14 thus environmental source 0 will return a random integer CpXkprivategmuECE646Projectworkgtde1 skeytesttxtskeydcpt CpxkprivategmuECE646Projectworkgtskeydriver sl4 p quotthis is my test keyquot d skeytesttxtskey No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 0 l and 2 No secret found with shares 0 2 and 3 Found the secret with shares 1 2 and 3 As expected the share logic had to use 1 2 and 3 before it could recover the secret Now try simulating two environmental sources failing CpXkprivategmuECE646Projectworkgtde1 skeytesttxtskeydcpt CpxkprivategmuECE646Projectworkgtskeydriver 512 p quotthis is my test keyquot d skeytesttxtskey No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 2 and O No secret found with shares 0 l and 2 No secret found with shares 0 2 and 3 No secret found with shares 1 2 and 3 No secret found with all 4 shares Decrypt failure Could not find share key ECE646 Project Final Report 7 Paul Kohlbrener Page 11 of 13 As expected the secret could not be recovered as only shares 2 and 3 were correct Finally try supplying all the correct environmental sources but mess up the passphrase CpxkprivategmuECE646Projectworkgtskeydriver 515 p quotthis is my test keyxquot d skeytesttxts ey No secret found with shares 2 and 0 No secret found with shares 2 and 0 No secret found with shares 2 and 0 No secret found with shares 2 and 0 No secret found with shares 2 and 0 No secret found with shares 2 and 0 Found the secret with shares 0 1 and 2 CpxkprivategmuECE646Projectworkgtdir skeytest Directory of CpxkprivategmuECE646Projectwork 12152001 1230a 182 SkeytesttXt 12152001 1237a 1216 skeytesttxtSkey 12152001 1241a 182 skeytesttXtskeydcpt 3 Files 1580 bytes 0 Dirs 7707500544 bytes free It appears as if the decrypt worked but when we type the le all we see is junk CpXkprivategmuECE646Projectworkgttype skeytesttxtskeydcpt AITUI u ampvi39uUrlt DKSf93 row 65belt2 H 5 a RTFM6 81 yf MuqOO CpxkprivategmuECE646Projectworkgt ECE646 Project Final Report 7 Paul Kohlbrener Page 12 of 13 ECE 646 Lecture 4 Key management Pretty Good Privacy Using the same key for multiple messages time Using Session Keys amp Key Encryption Keys time time Key Distribution Center KDC KEKD C KDVKDC Simple key establishment protocol based on KDC 1 let me talk with Bob 2b KEVKDCC Alice KAE 2a KAVKDCC BOblb KAE Alice KAVKDC KEVKDC Key establishment protocol based on KDC 1 let me talk with Bob 2 KAKDc Bob KAE ticketEab 3 ticketEab KEVKDCC Alice KAE Alice KAVKDC KEVKDC Key agreement Alice Bob A s private key B s private key B s public key A s public key Key oanndB Key OanndB Dif e Hellman key agreement scheme Alice Bob 0L q global public elements XA XB Key deIivation Key deIivation i Key KAB Key KAB Man in the middle attack Alice Bob A s private key B s private key A s public key B s public key Charlie Secret C s public C s public derivation key key denm i Key ofA and C Key OfB and C Does public key cryptography have an Achilles heel Alice Bob send rne your public key Alice Bob s public key Bob message encrypted using Bob s public key Charlie Does public key cryptography have an Achilles heel Alice Bob send rne your public key Alice Wblivkey Bob Charlie s public key message encrypted using Charlie s public key Charlie Does public key cryptography have an Achilles heel Alice Bob send rne your public key Alice WBob Charlie s public key message encrypted m ssage reencryptecl using Charlies s Bob s using public key Charl e public key Directory of public keys 1 e dambase Alice Alice s public key Bob Bob s public key Charlie Charlie s public key Dave Dave s public key Eve Eve s public key Bob Bob s public key Alice message encrypted using Bob s public key Bob Charlie Directory of public keys 2 e dambase Alice Alice s public key Bob Bob s public ke Charlie Charlie s public key 13 va Dave Dave s public key Charlie s Pub 39 Key Eve Eve s public key Alice messageencryptedusinngb rpnb vkey Bob Charlie s public key Charlie Directory of public keys 3 Onrline dambase Alice Alice s public key Bob Bob s public ke Charlie Charlie s public key B bv Dave Dave s public key charlne s pub Key Eve Eve s public key Alice 30b message encrypted message reencrypted using Charlie s Bob s public key using Charlie public key PGP Flow of trust Manual exchange oipublic keys Las Vegas Edinburgh Bob ltgt David David ltgt Betty B euy Washington New York London David sendme Betty s public key Betty s public key signed by David message encrypted using Betty s public key Certification Authority Proof identity Ceru cauon Authority Public key ofBob Certi cate Public key oi Certi cation Authority Certificate User s distinguished name User s public key Users Credenuals Serial number Issuer name Expiration date Distinguished Name DN according to X500 Example Common name CN Kris Gaj Country name C US State or province name ST VA Locality name L Fairfax Organization name 0 George Mason University Organizational unit name OU ECE Other fields permitted Street address SA Description D Post of ce box PO BOX Telephone number TN Postal code PC Serial number SN Title I The exact X509 Certi cate Format Version Signature identifier Issuer Name Period of validity Subject Name Vi hinn 3 Subject39s public info Extensions an x500 ernnmic Stallings 2003 Nonrepudiation only Alice Bob M SGNAM CertCAA KUQ Alice s private key KR A CA s public key KUCA Notation KUX public key of X SGNXM signature of X KRX private key of X for the message M CertYX KUX certi cate issued by Y for the user X Confidentiality only Onrline database CertCAAKUA r AOLKUE Cer CKU Census KUE mam KUS KmMKUEKm CA s public key KUCA Bob s prime key KRE Confidentiality and Nonrepudiation 9 database Genome KUu cencAm KUE SGNAM Certekoe KUk Kmam KUEKAE Alice s prime key KRA Bob s prime ke KRE CA s public key KUCA CA s public key KUCA Public Key Infrastructure M SGNAOVI Genamm KUA CeanGMU KUcmu en Fairfa Kn en rv Kn VeriSign PublicKey Certificate Classes Coxl39lrmulhm of ldculll or cunt llplnled by l39rolusllon Us lllllriur1h Mimic 0 IVth In m u crmllmlinn iiilliul il um Numm Stallings 2003 Certificate Revocation Lists CRLs Issue time Issuer CA s name Serial numbers of revoked certi cates CA s signature Certi cate is valid if it has a valid signature of CA did not expire is not listed in the CA s most recent CRL The exact X509 CRL Format Signature identifier Issuer Name This Update Date Next Update Date Re oked certificate Revoked certificate in Certi cate lhHirzlliuil List Stal S 200 3 Advantages of Certification Authorities over Key Distribution Centers I CA does not need to be oniline I CA is relatively easy to implement I CA crash no new users in the network but all old users operate normally I certi cates are not security sensitive they can be stored in a public database and transmitted over a public ne I compromised CA cannot decrypt messages without rst impersonating one of the users only active attacks can be mounted using CAs private key Authenticated key agreement B s ephemeral pnvaze key 8 s ephemeral publlc key 7 A s ephemeral pnvaze key A s ephemeral pm key Secret den39vation A Key den39vation key key Pretty Good Privacy PGP Email Security 0 email is one of the most widely used and regarded network services currently message contents are not secure may be inspected either in transit or by suitably privileged users on destination system Pretty Good Privacy PGP widely used de facto secure email developed by Phil Zimmerrnann selected best available crypto algs to use integrated into a single program available on Windows Unix Macintosh and other systems originally free now have commercial versions available also PGP Authentication Only Source A 4 Dcstiualiou 3 hml HUM KU u 39om pare a Amhcnliculion mil Notation M message H hash function EP public key encryption concatenation Z compression using ZIP algorithm KRa private key of user A KUa public key of user A 11 N on repudiation Alice Bob Message Signature Message sigiature I Hash value 1 Alice s private key Alice s public key PGP Con dentiality Only Notation M essage z compression using 211 algorithm EC DC 7 classical secretkey encryption decryption EP DP 7 public k y encryption decryption H concatenation Ks session key KRb rprivate key ofuserB KUb 7 public key ofuser B Hybrid Systems Sender s Side 2 Alice session key randum Publlc key er Session key e crypted using Bob s public key essage encrypted using session key Hybrid Systems Receiver s Side 2 Bob 2 session key random Secret key cipher Public key cipher Bob s private key Sessiogl key Message encrypted encryp e us1ng k Bebjs 10me key using sess10n CY PGP Con dentiality and Authentication KUh EmmiRI Compare c39imlidcmin1l Lllld authentication Notation M message H hash function Z compression using ZIP algorithm EP DP public key encryption decryption concatenation EC DC classical secretkey encryption decryption KS session key KRa KRb private key of user A B KUa KUb public key of user A B Transmission and Reception of PGP Messages nllH I l Irnm rudn 34 39 y quot x 114 m up Hgnuun39c hum X ml slgliulul39c cum In is 39 e E517IAH H mm mm at to mm M X l l39 Stallings 2003 13 PGP Operation Compression 0 by default PGP compresses message after signing but before encrypting so can store uncompressed message amp signature for later veri cation amp because compression is non deterministic 0 uses ZIP compression algorithm Major idea behind ZIP compression the brown fox jumped over the brown foxy jumping frog T 13 1 s l u L2 the brown fox jumped over 133le Y himii frog Stallings 2003 Radix64 Conversion 4 4 characters 32 bits Stallings 2003 14 Radix64 Encoding 6bit value Character 6bit value character 6bit value character 6bit value ch 39 encoding encoding encoding e 0 A 16 Q 32 g 48 u I B 17 R 33 It 49 2 C 18 S 31 I 50 3 D 19 T 33 51 z 4 E 20 U 36 k 52 0 S F 21 V 37 I 53 I 6 G 2 W 18 m 54 2 7 II 3 X 39 It 55 3 8 I 21 40 o 56 1 9 J 23 Z 41 I 37 3 U K 26 a 42 q 38 6 I L 27 17 43 I 59 7 12 M 28 L 4 1 s 60 8 3 N 29 d 45 I 61 9 11 0 30 e 46 U 62 3 P i f 47 t 63 39 pad Stallings 2003 General Format of PGP Message Content pitltlic ke K t Ket twinaping Srssiun lil39 I 1390 lnllclll V I Semott kc In l i mestmnp Kc ll of sender s ke my l iiettnnte Message LXttzt Me ntgw t Emquot Operation It It R04 111I 11KS V Stallings 2003 Summary of PGP functions t in D55 or RSA with Function Algorithms l39setl Descriptith A hash code ot39n message I39L lCCI using i squot s39s 39w DIEIIflI signature USS511A or RSASIIA I II In PILL LI A I LIICII1LI the gtL39IILICI s l39ILtlL he and itteIttded 1tIt the message s tge is Clk l39H Cd usint or 3015 ilh a onvttme se W39ASLIZS io Message enet39 ption C T or IDEA 39I lite It39iple D125 I it39ll 71 to III III I LII39m I RSA HlIl the t CCIpILIIIS public Itet and RSA I V tntluded wttIt the message 2 39 messt 2e mft 13 om itquotss I to storne ompt39ession LIP A 1a I C I L W I 3 m tmnsmtsston using Z P To IT itIe transparency for email i i anheutionsnn I39tCl itetl messauema he Itmml C ltlp dlthllll RudnoI cottterston I I 1 I I I eomet ted to an i t 1 string Ll51l1gt ttt11 61 eom et39sion Segmentation 7 I39o ueeonnnodztte maximum message ZL limitations PGP performs segmentation and t39ettssetnlx Stallings 2003 15 Private Key Ring Primle Key Ring Stallings 2003 Public Key Ring Public Key Ring I icld used 10 index table Stallings 2003 PGP Message Generation Without compression or radix64 conversion l uhlic kc ring puplnuc I rimlc kc 1mg uncr mud prn nlc kc Kc ll nlpm er plcd Ignulurc mcsmlgt Stallings 2003 n lt 16 PGP Message Reception without compression or radix64 conversion pass phi asc Public kc ling l rii ulc kc ring mar pied pm inc kg KR session kc K cncr 710d message si unumre message Comparc Stallings 2003 PGP Flow of trust Manual exchange of public keys Las Vegas Edinburgh Bob ltgt David David ltgt Betty Bob David Betty Washington New York London David send me Betty s public key Betty s public key signed by David message enc1ypted using Betty s public key PGP Trust Model You 7 unluumu siunulor gt x issiglmlln I 5 I O kc 3 u Ilul39 i inqu by you In sign km 0 kcy s ouuLI39 is purl uusiul h ylu in sign Ii39S 9 kLyideLnuIIcgilinmtcb you stallingsD 2003 ECE 646 Lecture 14 Cryptographic standards Secretkey cryptography standards Federal Banking International standards standards standards NIST ANSI ISO FIPS 46 1 DES X392 DES FIPS 462 DES ISO 8732 Modes of operatlon FIPS 81 Modes of X3106 DES modes of operation 9 644 operation clpher X952 Modes of operation ISO 10116 Modes of FIPS 463 Triple of Triple DES Operation DES of an n bit FIPS 197 AES cipher NIST FIPS National Institute of Standards and Technology Federal Information Processing Standards American Federal Standards Required in the government institutions Original algorithms developed in cooperation with the National Security Agency NSA PublicKey Cryptography Standards unof cial d t 1ndustry m us ry standards standards RSA Labs IEEE PKCS P1363 PKCS international bank standards standards 1 ISO ANSI ISO ANSI X9 federal standards NIST FIPS PKCS PublicKey Cryptography Standards Informal Industry Standards developed by RSA Laboratories in cooperation with Apple Digital Lotus Microsoft MIT Northern Telecom Novell Sun First except PGP formal specification of RSA and formats of messages IEEE P1363 Working group of IEEE including representatives of major cryptographic companies and university centers from USA Canada and other countries Part of the Microprocessors Standards Committee Modern open style Quarterly meetings multiple teleconferences discussion list very informative web page with the draft versions of standards IEEE P1363 Combined standard including the majority of modern public key cryptography Several algorithms for implementation of the same function Tool for constructing other more specific standards Specific applications or implementations may determine a profile subset of the standard ANSI X9 American National Standards Institute Work in the subcommittee X9F developing standards for financial institutions Standards for the wholesale e g interbank and retail transactions np bank machines smart card readers ANSI represents USA in ISO ISO International Organization for Standardization International standards Common standards with IEC International Electrotechnical Commission ISOIEC JTCl SC 27 Joint Technical Committee 1 Subcommitte 27 Full members 21 Australia Belgium Brazil Canada China Denmark Finland France Germany Italy Japan Korea Holland Norway Poland Russia Spain Sweden Switzerland UK USA ISO International Organization for Standardization Long and laborious process of the standard development Study period NP New Proposal Minimum WD Working Draft 3 years CD Committee Draft DIS Draft International Standard IS International Standard Review of the standard after 5 years ratification corrections or revocation Publickey Cryptography Standards unof cial industry standards indu stry standards RSA Labs q IEEE PKCS PKCS P1363 international bank standards standards ISO ANSI ISO ANSI X9 federal standards NIST FIPS PKCS 1991 1992 1993 1994 1995 1996 199719981999 PKCS 1 10 PKCS 711PKcS 13 5 i IEEE ANSI PKCS 1 V20 P1363121 Pms K930 X96i EC g SA DSA ISO 9796 10118 12 U U U 39 X91 R A R W 11770 3 a3 NIST FIP a 180 SHA 0118 FIPS 180 1 9 SHAl 331488803 SA 939 96 4NR FIPS 1 U 50DS a I IPS 186 1DSAampRSA IEEE P1363 discrete factorizatlon logarithm RSA with OAEP elliptic curve discrete logarithm RSA amp R W DS A EC DSA w1th ISO 14888 NR with ISO 9796 I EC NR or ISO 9796 r w1th ISO 9796 EC DHZ and EC MQV elliptic curve discrete logarithm new scheme new scheme 333 Egg DSA ECDSA W 130399796 NR WithISO9796 EC NR or with ISO 9796 key h DHI 3833 t new SC eme DH2 amp M V agreemen Q amp EOMQV ANSI X9 Standards 39 discrete elliptic curve fadomatlo logarithm discrete logarithm Industry standards PKCS discrete elliptic curve logarithm discrete logarithm PKCS 1 PKCS 13 RSA new scheme PKCS 13 PKCS 1 RSA i R W ECDSA key PKCS 2 PKCS 13 agreement DH ECDH1 2 ECMQV NIST FIPS is loganthm elliptic curve discrete logarithm FIPS 1861 FIPS 186 FIPS 1862 RSA DSA EC DSA key agreement International standards ISO disc logarithm elliptic curve discrete logarithm ISO 9796 1 ISO 14888 3 ISO 14888 3 ISO 97962 ISO 9796 4 ISO 9796 4 k ey ISO 11770 3 ISO 11770 3 agreement PKCS IEEE P1363 ANSI X9 NIST FIPS ISO Secure key sizes discrete elliptic curve discrete Z 1024 512 S L31024 Padding schemes signatures signatures with with message appendix recovery PKCS 12221 PKCS 1 IEEE P1363 OAEP ISO 14888 ISO 9796 ANSI X9 OAEP ISO 14888 ISO 9796 NIST FIPS ISO ISO 14888 ISO 9796 Hash functions based on dedicated modular CipheI S arithmetic PKCS SHA l IEEE P1363 RIPEMD 160 SHA l ANSI X9 RIPEMD 160 SHA l SHA 256 NIST FIPS SHA 384 SHA 512 ISO SHA l MDC2 MASH 1 RIPEMD IZS 160 MASH 2 Notes for users of cryptographic products 1 Agreement with a standard does not guarantee the security of a cryptographic product Security secure algorithms guaranteed by standards 0 proper choice of parameters secure implementation proper use ECE 646 Lecture 8 Modes of operation of secretkey block ciphers Block vs stream ciphers M1M2 MN m1mz mN Q Q IS IV 1 K lgt BIOCk K gt Stream 010131 m1 ci her 18 NS 18 m p Clpher 11 1 1 C1 C2 CN c1 c2 cN CiszaVD Ci fKm1 mi1 m2 m1 Every block of cipherteXt Every block of cipherteXt is a function of the current and is a function of only one all proceeding blocks of plaintext corresponding block of plaintext Typical stream cipher Sender Receiver initialization k initialization vector 6 vector Pseudorandom Pseudorandom Key Key Generator Generator k1 keystream ki Lkeystream 4 tw mi Ci Ci mi plainteXt cipherteXt cipherteXt plainteXt Standard modes of operation of block ciphers Block ciphers Stream ciphers ECB mode Counter mode OFB mode CFB mode CBC mode ECB Electronic CodeBook mode Electronic CodeBook Mode ECB M1 M2 M3 MNl MN C1 C2 C3 CNl CN Ci EKMi for i1 N Counter Mode Counter Mode CTR Encryption IV1 IV2 IVN 1 IVN ci mi 69 ki ki EKIVi1 for i1N Counter Mode CTR Decryption IV1 IV2 IVN 1 IVN k1 EKIVi1 for i1N Counter Mode CTR IV IV 6 1 L 1 L IN K a E K a E OUT OUT 1 L 1 L gt Is1 IV mi ci EKaSi 9 mi ISi1ISi1 Jbit Counter Mode CTR IV IV1 IV2 IVN 1 IVN ci 1111 69 ki k1 EIVi11j for i1N Jbit Counter Mode CTR IV IV OFB Output FeedBack Mode Output Feedback Mode OFB Encryption ci 1111 69 ki ki EKki1 for i1N and k0 IV Output Feedback Mode OFB Decryption 1ni c1 43 ki ki EKki1 for i1N and k0 IV Output Feedback Mode OFB IS1 IV Ci EKISi 9 mi ISM EKUSi Jbit Output Feedback Mode OFB IV shift 7 L bits CFB Cipher FeedBack Mode Cipher Feedback Mode CFB Encryption mi 69 ki k EKci1 for i1N and c0 IV Cipher Feedback Mode CFB Decryption ci mi 69 ki ki EKci1 for i1N and c0 IV Cipher Feedback Mode CFB K 4p IS1 IV OUT 1 L ci EKISi 9 mi ISM Ci 4 Jbit Cipher Feedback Mode CFB IV IV 4 l 11 CBC Cipher Block Chaining Mode Cipher Block Chaining Mode CBC Encryption m3 mNl mN ciEKmi ci1 for i1N cOIV 12 Cipher Block Chaining Mode CBC Decryption 111i DKci 69 ci1 for i1N cOIV Comparison among various modes 13 Block Cipher Modes of Operation Basic Features 1 ECB CTR OFB CFB CBC Security weak strong strong strong strong B35 speed SECB mSECB lL39SECB mjL39SECB mSECB Capability for parallel Encrypnon Encryptlon None Decryption Decryption processing an and only only and pipelining de cryption decryption Cipher Encryption Encryption Encryption Encryption Encryption operations and on y on y only and decryption decryption Prepmcessmg No Yes Yes No No Random RW RW No R only R only access Block Cipher Modes of Operation Basic Features 2 ECB CTR OFB CFB CBC Security against the exhaustive key search attack Minimum number of l plaintext 2 plaintext 2 plaintext l plaintext l plaintext the message block blocks blocks blocks blocks and ciphertext 1 ciphcrtht 2 ciphcrtext 2 ciphertext 2 ciphertext 2 ciphertext blocks block blocks blocks blocks blocks needed for FL for jL Error propagation in the decrypted message Modi cation 0fjbits L bits bits bits LJ bltS Lt J bltS Current and Current and Current and C Deletlon Of l blts all subsequent all subsequent all subsequent L bus all SUbseqUem Integrity No No No No No 14 New modes of operation Operating Modes Contest 4 Old Modes CBC CFB OFB ECB April 2001 10 New Candidates from Egypt Estonia Norway Sweden Thailand USA Counter mode Summer 2001 5 Standard Modes 2002 New Standard Modes 15 Modes submitted to the contest 1 Full name Authors Institution A A Belal Alexandria 39DEM 2D EncryptIOH MOde M A Abdel University Gawad Egypt ABC Accumulated Block L Knudsen U of Bergen Chaining Norway H Lipmaa Finland CTR C Gunter M 0 d e P Rogaway Estonia USA D Wagner Thailand IACBC Integrity Aware CBC C Jutla IBM USA IAPM Integrity Aware C Ju a IBM USA Parallalizable Mode Modes submitted to the contest 2 Full name Authors Institution IGE Infinite Garble V D Gligor VDG Inc Extension P Donescu USA KFB Key Feedback Mode J Hastad NADA M Naslund Ericsson Sweden UCSD USA OCB Offset Codebook P Rogaway Thailand PCFB Propagating Cipher H Hellstr m StreamSec Feedback Sweden XCBC eXtended CBC v D Gligor VDG Inc5 Encryption P Donescu USA l6 Evaluation Criteria for Modes of Operation Security Efficiency Functionality Evaluation criteria 1 Security resistance to attacks proof of security random properties of the ciphertext Ef ciency number of calls of the block cipher capability for parallel processing memoryarea requirements initialization time capability for preprocessing l7 Evaluation criteria 2 Functionality security services confidentiality integrity authentication exibility variable lengths of blocks and keys different amount of precomputations requirements on the length of the message vulnerability to implementation errors requirements on the amount of keys initialization vectors random numbers etc error propagation and the capability for resynchronization patent restrictions Modes of operation Current standard CBC 5 r r T r 4 Problems No parallel processing of blocks from the same packet No speedup by preprocessing No integrity or authentication 18 ECE 646 Lecture 11a Hash functions new attacks Hash function algorithms Based on Based on block ciphers modular arithmetic Customized g e de a dicated IIIIlllllllllllllllllllllll MD2 R t 1988 MDC2 MASH1 1m MDC4 19881996 R t 1990 IBM Braehtl Meyer Schilling I988 tVeS MD5 RIPEMD 128 Rives 1990 NSAgt 1992 European RACE Integrity 1 Primitives Evaluation Project 1992 NSA 1995 RIPEMD 160 SHA256 SHA384 SHA S 12 NSA 2000 Security of dedicated hash functions partially broken L broken H Dobbertin 1995 one hour on PC 20 free bytes at the staIt of the message weakness JMBSH discovered RIEEMDIZS Pa ially broken 1995 NSA reduced round 1998 France vers10n broken collls1ons for the Dobbertm 1995 compress1on functlon Dobbertin 1996 7 10 hours on PC g A 7WIIIIIIIIIIIIIIIIIIIIIIIIIII a SHA256 SHA384 SHA512 a What was discovered in 20042005 broken 4 Wang Feng Lai Yu Crypto 2004 manually Without using a computer 5 attack with broken 240 operations Wang Feng broken S 0 Crypto 2004 RIP 128 L31 Yu Wang Feng Lai Yu 1 Crypto 2004 C to 2004 attack Wlth m anully Without 1rth On a PC 269 Operations using a computer Wang M RIPEMD160 Yu Feb 2005 SHA256 SHA384 SHA512 269 operations Schneier 2005 In hardware Machine similar to the one used to break DES Cost 5000070000 Time 3 years 3 months or Cost 25M 38M Czas 56 hours In software Computer network similar to distributednet used to break DES 33l252 computers Cost 0 Czas 38 years Recommendations of NIST 1 NIST Brief Comments on Recent Clyptanalytic Attacks on SHAI Feb 2005 The new attack is applicable primarily to the use of hash functions in digital signatures In many cases applications of digital signatures introduce additional context information which may make attacks impracticle Other applications of hash functions such as Message Authentication Codes MACS are not threatened by the new attacks ECE 646 Lecture 2 Basic Concepts of Cryptology CRYPTOLOGY CRYPTOGRAPHY CRYPTANALYSIS from Greek cryptos hidden secret logos Word aphos W111ng Basic Vocabulary encryption dec yp m enciphermem deCiPhermem ciphertext message cryptogram message plaintext encrypted plaintext dear message message clear message M C M Sender Receiver Cryptnsyslem Cipher massage mm cmwm w m ciphth De nitinn nfz cryptnsyslan cipher m quottwinmm m mmmns mmmemm szx VM EM Dxmxmnm Subsunm39nn Cith 39 quot CZi ii Wm H n u m u u an mm B H mm H H 111 x u T1 Nlmhuu zyx 2m z 4 m Kerckhoff s principle The security of a cipher MUST NOT depend on anything that cannot be easily changed Auguste Kerckhoff 1883 Unpublished vs published algorithm Unpublished algorithm Published algorithm 1 The only reliable way of assessing cipher security Prevents backdoors hidden by designers Large number of implementations low cost high performance 4 No need for antireverse engineering protection Software implementations Domestic and international w 1 Cryptanalysis must include recovering the algorithm 2 2 Smaller number of users 3 smaller motivation to break 3 Unavailable for other countries om Fundamental Tenet 0f Cryptography If lots of smart people have failed to solve a problem then it probably will not be solved anytime soon Security of unpublished ciphers 39 39 quot 39 cheme builtin MS Word MS Excel MS Money WordPerfect ProWrite DataPerfect Lotus 123 Symphony QuattroPro Paradox Semantec s Qamp IPKZip etc Time 12minutes for old Versions ofprograms up to several days fornew Versions of some programs a F r m Companies Access Data mk So mre y lzs Breaking ciphers used in GSM 1999 1 GSM world39s most widely used mobile telephone system I 51 market share of all cellular phones both analog and digital I over 215 million subscribers in America Europe Asia Africa and Austmlia I In the US GSM employed in the quotDigital PCSquot networks of Paci c Bell Bell South Omnipoint etc Two voice encryption algorithms 51 and A52 encrypt voice between the cell phone and the base station Breaking ciphers used in GSM 2 Both voice encryption algorithms I never published I i ed and analyzed by the secretive quotSAGEquot group part of ETSI 7 European Telecommunications Standard Institute I A51 believed to be based on the modi ed French naval cipher Both algorithms reverseengineered by quotMarc Briceno with the Smartcard Developer Association published by the Berkeley group 51 inMay 1999 A52 in August 1999 making ciphmused in GSM 3 mama mm ASZ A Numbxufapmmrsmth snack 2 ASI My 1999 lawn Gal Numhexaprnmns mm man 24quot Lessthanlxuumunasmg z mmmzmamm andlvm 79 GE 1m asks Based an m Analyss afthz ASH mitth am m mm mmms afthz canvzxsaonn Atmck nn Mil39zre classics Da many mm c mu mm mm rm minan rubl nunAckhmuh menyuumm meresreqnired mm tm lzy39s ciphu39s FUNCHONAUT I easykzymsmhnonn m smmres dlgx Software or hardware SO FTWARE HARDWARE low cost Em 33910 access control exibility to keys new cryptaalganthms 39 tamper resistance protection agamstnew attacks Viruses mtemat attacks security or data during transmission A Basic hardware implementations of cryptography VLSI chip ASIC FPGA smart card 39 PCMCIA card cryptographic card standalone cryptographic device Cryptographic chips and boards Why are cryptographic chips needed hardware accelerators for web servers SSL Secure Socket Layer 7 cryptographic protoco1 used by majority of today s web servers to protect credit card numbers for online transactions such as buying abook on the arnazoncorn Why are cryptographic chips needed hardware accelerators for Virtual Private Networks VPNs IPSec Secure Internet Protocol 7 cryptographic protoco1 used to support VPNs rrtua1 Private Networks ie secure Communi cationbetween remote Local Area Networks LANs using Internet IPSec optional in P ver 4 requiredin emerging P ver 5 Acce1erau39on can be provided using secure gateways secure clientPCMCIA cards Virtual Private Network Remote Z i HPSt H Ht E C t h39 d 39 t xyp ograp 1c en pom s Host Host secun39ty gateways may come from different vendors ECE 646 Lecture 3 Types of Cryptosystems Implementation of Security Services Types of Cryptosystems 1 Block vs stream ciphers Cryptosystem Cipher message cryptographic key ciphe ext Block vs stream ciphers MM2M 1 ck B10 cipher n mlvav vmn memory K Ci Stream cipher ChCzCn one cn cifKMi Ci fKUT v mm quot 2 m1 EALcL EALcL is afunction ofonly one is afunction ofthe current and c c Typical stream cipher Sender Receiver initialization initialization key vectorseed key vectorseed Pseudomndom Pseudorandom m m plaintext ciphertext ciphertext plaintext Types of Cryptosystems 2 Secretkey vs publickey ciphers Secretkey Symmetric Cryptosystems key of Alice and Bob 7 KAB key of Alice and Bob 7 KAB inf 3 c Encryption Decryp on Alice Key Distribution Problem Digital Signature Problem Both sides have and are able to generate a signature There is a possibility of the I receiver falsifying the message I sender denying that heshe sent the message Public Key Asymmetric Cryptosystems Public key of Bob KB Private key of Bob kB I 1 O Encryption V Decryption Alice Bob Classi cation of cryptosystems Terminology secretkey public key symmetric asymmetric symmetrickey classical conventional Oneway function X fX Y f 1Y EXAMPLE f YfX AX mod P Where P and A are constants P is a large prime A is an integer smaller than P Number of bits of P Average number of multiplications necessary to compute f f 391 1000 1500 1030 Trap door one way function Whit eld Dif e and Manin Hellman New directiom in cryptogrqvhy 1976 PUBLIC KEY x fX Y WY PRIVATE KEY Key Distribution Alice 30b message message Bows Bob s Bob s public priwte public key key key cipherlexl ciphenext message Bob s public Intruder key cipherlext Digital Signature Alice 30b signature signature Alice s Alice s Alice s private public public key key message message signature signature Intruder Alice s 1 ng Alice s public public key key message message Implementation of Security Services N on repudiation Alice Bob Message Signature Messng Signature I Hash value 1 Alice s private key Alice s public key Hash function arbitme length message hash function hash value fixed length Hash functions Basic requirements 1 Public description NO key 2 Compression arbitrary length input gt xed length output 3 Ease of computation Hash functions Security requirements It is computationally infeasible Given Mm m and hm To Find m i m such that Mm Mm m i m such that Mm Mm N on repudiation Alice Message Signature Alice s private key Message Signature I Hash value 1 Hash value 2 I Alice s public key N on repudiation Alice Bob Message Signature Message Siglzture Alice s private key Alice s public key Authentication Alice Bob Message MAC Message MAC cret key of Alice and Bub MAC Message Autentication Codes keyed hash functions arbitrary length message secret key K xed len th MAC functions Basic requirements 1 Public description SECRET key parameter 2 Compression arbitrary length input gt xed length output 3 Ease of computation MAC functions Security requirements Given zero or more pairs In MACrn i1k it is computationally impossible to nd any new pair m MACm such that m i InI i 1k CBCMAC Cipher Block Chaining MAC Message MAC Relations among security services N 0n repudiati0n Alice Bob Message Signature Message Sigizture I Hash value 1 Alice s private key Alice s public key Authentication Alice Bob Message MAC Message MAC Secret key at Alice and Bub Hybrid Systems Features required from today s ciphers FUNCTIONALITY I easy key distribution I di als39 natures Features of secret key ciphers FUNCTIONALITY I easy key distribution I digital signatures Features of public key ciphers PERFORMANCE FUNCTIONALITY I easy key distributio I digital signatures Average Decryption Speed for implementation based on the same technology software hardware Triple DES deciphering speed S 100 s 1000 RSA1024 deciphering speed Basic operations of secret key ciphers Sbox Software Hardware C ROM Seb ox n x m g nrbit address WORD S 1ltltn n 0x23 0x34 0x56 2 words ASM mibit output S DW 23H 34H 56H direct logic Sub s m on x y x y x ym Basic operations of secret key ciphers Pbox Software Hardware Psbox nxn C x x2 x m amp 7 sequence of instructions ltltlamp yl Y2 y y y n ASM sequence of Permutation insmmons order ofwires Basic Operations of the Public Key Cryptosystem RSA Encrypu39on public key Exponent ciphertm plaintm mod public key mudulus krblts krblts krblts D ecrypu39on pr m key ExpunEnt plaintm ciphemxt In 01 private key mndulus krblts krblts krblts Hybrid Systems session key Alice mmiam serratrlcq Bob s public key 3quotquot 395 Prim key Session key ncrypted crypted using essage e e k Bob s public key using session ey Hybrid Systems Sender s Side 2 Alice session key randum Secret key cipher Session key encrypted using Bob s public key Mess e encrypted using session key Hybrid Systems Receiver s Side 2 Bob session key randum Secret key cipher Session key encrypted using Bob s public key Message encrypted using session key Evaluating the security of secretkey ciphers Classi cation of attacks 1 Ciph ertextonly attack Given ciphertext Lankedfar plaimext or key Example Frequency analysis of letters in the ciphertext effective only for most simple historical ciphers Classi cation of attacks 2 Known plaintext attack Given ciphertext guessed fragment of the plaintext Lankedfar remaining plaimext or key Example exhaustive key search successive bruteforce attack eys Classi cation of attacks 3 Chosen plaintect attack Given Capability to encipher 39 arily chosen fragment of the plaintext Lankedfar key Example D erential cryptanalysix ECE 646 Lecture 9 RSA Genesis operation amp security Public Key Asymmetric Cryptosystems Public key of Bob KB Private key of Bob kB I Network Encryption Decryption Alice Bob Trapdoor oneway function Whit eld Dif e and Martin Hellman New directions in cryptography 1976 PUBLIC KEY X fX Y F f391Y PRIVATE KEY w Know how to break Russian Hire 50000 mathematicians Coopemte with an industry Keep as much as possible Professional NSA vs amateur academic approach to designing ciphers 1 Know nothing about ciphers cryptology Use only wellestablished 2 Think of revo1mionary proven methods ideas 3 Go for skiing 4 Publish in Scienti c American 5 Offer a 100 award for breaking the cipher giant secret Challenge published in Scientific American Cipherth 9686 9613 7546 220614771409 2225 4355 8829 0575 9991 1245 74319874 69512093 0816 2982 2514 5708 3569 3147 6622 8839 8962 8013 3919 90551829 945157815145 Public key N 114381625757 88886766923577997614 6612010218296721242362562561 570693524573389783059712356395870 5058989075147599290026879543541 e 9007 129 decimal digits Award100 977 RSA as a trap door one way function PUBLIC KEY C fM Me modN PRIVATE KEY N 1 Q p Q large prime numbers e d 21 mod P1Q1 RSA keys PUBLIC KEY PRIVATE KEY eaN dPQ 96 N P Q P Q large prime numbers e d El mod PlQl Why does RSA work 1 7 M Cquot1 mod N ME modNquot1 mod N M original message decrypted message d E 1 mod P1Q391 ii ed El m0dpN a Euler s totient function Euler s totient phi function 1 MN 7 number ofintegers in the range from 1 to N71 that are relatively prime wit Special cases 1 P is prime P Pl Relatively prime with P 1 2 3 P1 2 NPQ PQareprirne NP1 Q1 Relatively prime with N 1 2 3 PQl 7 P 2P 3P Q1P Q 2Q 3Q P1Q Euler s totient phi function 2 Special cases 3 N P2 P is prime N P P1 Relatively pn me with N 1 2 3 PH 7 P 2P 3P P1P In general IfNPlelP2amp2P323 Ptet MN 1391 Pf Ia1 11 Euler s Theorem Lennard Euler 170771783 V am 2 1 mod N a gcda N 1 Euler s Theorem Justification 1 For N10 For arbitrary N R1379 Rxxzme Let 213 Let us choosearbicmya such that gcdaN1 S 3391m d1 v saxmodN x2modN 33m0d 10 37mod 10 H modN 39 mod 10 W00 3917 reaxranged setR Euler s Theorem Justification 2 For N10 For arbitrary N RS RS xx2 x3 x4 2 1W 000 WMa39X2ax3ax4modN H x l39i ax modN 11 i 000 1W erzx 7 aAxrxzxzxAmodN H x elmH x modN 11 11 a4 1 modN aW 1 modN Why does RSA work 2 M Cquot1 mod N ME mod Nquot1 mod N mod gtN 1klttgtN Mkam modNM M PNkmodN MEdmodN e39d ed M M PN mod Nk modN M 1k modNM Rivest estimation 1977 The best known algorithm for factoring a 129digit number requires 40 000 trilion years 40 1015 years assuming the use ofa supercomputer being able to perform 1 multiplication of 129 decimal digit numbers in 1 ns Riven s assumptmn translate a the delay afa Smglz Uglc gate 210 Estimated age omie universe 100 bln years 10 years Early records in factoring large numbers Number of Number Required Years decimal computational of bits iglts ower in MIPSyears 1974 45 149 0001 1984 71 235 01 1991 100 332 7 1992 110 365 75 1993 120 398 830 How to factor for free A Lenstra ampM Manasse 1989 Using the spare time of computers otherwise unused Program and results sent by e mail later using WWW Practical implementations of attacks Factorization RSA Number Year 3 696111in Memod ES 221322 1994 430 129 Q3 5000 MIPSyears 1996 433 130 GNFS 750 MIPSyears 1998 467 140 GNFS 2000 MIPSyears 1999 467 140 GNFS 8000 MIPSyear Breaking RSA 129 August 1993 1 April 1994 8 months When Who D Atkins M Graff A K Lenstm P Leylan 600 volunteers from the entire World How 1600 computers from ciay C90 through 16 MHz PC o fax machines 0mg 0 03 camputaliunalpnwer of the Internet Resulm ofcryplanalysis he mang words are squeamsh usszfrage An amrd of100 is donated to Free Softvwre Foundation Elements affecting the progress in factoring large numbers I computational power 9771993 increase ofabout 1500 times I computer networks Internet 0 better algo hm Factoring methods General purpose Special purpose Time uf zctmmg ZS much shorter szm zctms qu are ufthz spew fmm Time uf zctmmg depends only no the Size qu GNFs Genem Number ECM Elliptic Curve Method Field Sieve Pollard s pl method QS Quadratic Steve C l t 39 1 39al th d Continued Fraction Method y quot 1 yquot quot me hzsmncal SN39FS Special Number Field Sieve Running time of factoring algorithms L406 cl exp CU1391n Q 391n 1quot 1 For 00 AlgonLhmpnlynumizl M as a function othe number Lam c 1quot qr ofbits ofq For a1 AlgonLhm exponential L41 c expltltcult1gtgtlt1n q 0M 0M For 0ltalt1 as a function ofthenumbec ofbits ofq fn 01 iffor any positive constant cgt0 there exist a constant nngt0 such that 0 S n lt c for all n 2 nn General purpose factoring methods Expected running time Q8 N39FS LnllZ1EXP1 01 InkJ in mm LnilK1922p192 51 InkJV lnlnNJM QS mm NFS mm e ia39alt e ia39alt 100D 0D 130D Nin decimal digits D RSA Challenge RSAsl nu Smallest unfactored number RSArl 1U RSArl ZEI RSArl 3U RSAVHEI RSAquot 150 RSArl 5U RSArl 6U RSA39WU Unused awards accumulate at a rate RSArl 8B of 1 750 qua er RSAA 5U RSAA 6U RSAJWU RSAA 8U RSAA 9U RSAVS ID Factoring 5 12 bit number 512 bits 155 decimal digits old standard for key sizes in RSA 1 7March 22 Augmf 1999 Group of Herman te Riele Centre for Mathematics and Computer Science CW1 Amsterdam First stage 2 months 168 Workstations SGI and Sun 175400 MHz 120 Pentium PC 300450 MHZ 64 MB RAM 4 stations DigitalCompaq 500 MHz Second stage Cray C916 10 days 23 GB RAM TWINKLE The Weizmann INstitute Key Locating Engine Adi Shamir Eurocrypt May 1999 CHES August 1999 Electrooptl39cal device capable to speedaup the rst phase of factorization from 100 to 1000 times If ever builtitwould increase the size of the key that can be broken from 100 to 200 bits Cost of the device assuming that the prototype was earlier built a 5000 Recommended key sizes for RSA Old standard Individual users 1 New standard 768 bits Individm l 59 231 decimal digits 1024 bits 0 LI 1 ll rgamza 039 s or m 308 decimal digits Organizations long term 2048 hits 616 decimal digits Keylengths in public key cryptosystems that provide the same level of security as AES and other secretkey ciphers Arjen K Lenstra En39c R Verheul Selecting Cryptographic Key Sizes Journal of Cryptology AI39en K Lenstra Unbelievable Security Matching AES Security Using Public Key Systems ASIACRYPT 2001 RSA vs DES Resistance to attack Number of operations in the best known attack NDE S 150 NDES DES 5127bit RSA 564m key Keylengths in RSA providing the same level of security as selected secretkey u The same cost DES AE87128 AEs7192 AE87256 2 kevs 3 kevs Keylengths in RSA providing the same level Practical progress in factorization March 2002 Financial Cryptography Conference Nicko van Someren CTO nCipher Inc announced that his company developed software capable of breaking 512bit RSA key Within 6 weeks using computers available in a single of ce Bernstein s Machine 1 Fall 2001 Daniel Bernstein professor of mathematics at University of Illinois in Chicago submits a grant application to NSF and publishes fragments of this application as an article on the Web D Bernstein Circuits for Integer Factorization A Proposal httpcryptopapers htmlnfscircuit Bernstein s Machine 2 March 2002 I Bernstein s article discovered during Financial Cryptogrqvhy Conference I Informal panel devoted to analysis of consequences of tlie Bernstein s discovery Nicko Van Someren nCipher estimates that machine costing 1 bilion is able to break 1024 bit RSA Within several minuts Bernstein s Machine 3 March 2002 alarming voices on emailing discussion lists calling for revocation of all currently used 1024bit keys sensational articles in newspapers about Bernstein s discovery Bernstein s Machine 4 April 2002 Response of the RSA Security Inc Error in the estimation presented at the conference according to formulas from the Bernstein s article machine costing 1 billion is able to break 10247bit RSA Within 10 billion x several minuts tens of years According to estimations of Lenstm i Verheul machine reaking 1024bit RSA Within one day Would cost 160 billion in 2002 Bernstein s Machine 5 Carl Pomerance Bell Labs fresh and fascinating idea Arjen Lenstra Citibank amp U Eindhoven I have no idea What is this all fuss about Bruce Schneier Counterpane enormous improvements claimed are more a result ofrede ning ef ciency than anything else Bernstein s Machine 6 RSA keylength that can be broken using Bernstein s machine RSA key lengths that can be broken using classical computers 7 7 1 7 7 39slblnnoay 1000bln1day a in nity a time days memory 3 RSA Challange Lentgh of N Length of N Award for in bim in decimal digits factorization 193 ECE 646 Lecture 3 Types of Crypt0systems Implementation of Security Services Types of Crypt0systems 1 Block vs stream ciphers Cryptosystem Cipher message 71 bits cryptographic key k bits i m bits ciphertext Block vs stream ciphers M1M2Mn m1m2mn ll I Internal state IS I Block K K gt Cipher gt Stream cipher C1C2Cn clczcn CFfKGVL Ci fKmi Isi ISiHZgKltmi 131 Every block of ciphertext Every b109k 0f ClpheneXt is a function of the current block 15 a mcuon 0f only one of plaintext and the current internal state corresponding block of plaintext of the cipher Typical stream cipher Sender Receiver k initialization k initialization ey vector seed ey vector seed Pseudorandom Pseudorandom 39I I Key I I Key Generator I I Generator I I I I ki keystream ki Lkeystream r I I J w mi Ci Ci mi plainteXt cipherteXt cipherteXt plainteXt Types of Cryptosystems 2 Secretkey vs publickey ciphers Secretkey Symmetric Cryptosystems key of Alice and Bob K AB key OfAlice and Bob KAB Encryption Decryption Alice Bob Key Distribution Problem 5000 500000 Digital Signature Problem Both corresponding sides have the same information and are able to generate a signature There is a possibility of the 0 receiver falsifying the message sender denying that heshe sent the message Public Key Asymmetric Cryptosystems Public key of Bob KB Private key of Bob kB Encryption Decryption Alice Bob Classi cation of cryptosystems Terminology secretkey public key symmetric asymmetric symmetric key classical conventional Oneway function X fX Y f391Y EXAMPLE f YfX AX mod P where P and A are constants P is a large prime A is an integer smaller than F Number of bits of P Average number of multiplications necessary to compute f f 1 1000 1500 l 1030 Trapdoor oneway function Whitfield Diffie and Martin Hellman New directions in cryptography 1976 PUBLIC KEY X fX Y f391Y PRIVATE KEY Key Distribution Alice Bob message message Bob s Bob s Bob s public PriVate public key key key Ciphenem ciphertext message Bob s public Intruder key ciphertext Digital Signature Alice Bob signature signature Alice s Alice s Alice s private public public key key key message message signature signature Intruder Alice s Judge Alice s public public key key message message Implementation of Security Services Non39replldiation 521mm MW Hash funcu39nn l HaShvaluzl Alice s privzm kgy Signaling Hashval mz I rimpkg Cipher Bob Am Public key H3511 function armer laugh 1711511 value xed length Hash functions Basic requirements 1 Public description NO key 2 Compression arbitrary length input gt fixed length output 3 Ease of computation Hash functions Security requirements It is computationally infeasible Given To Find hm m h th t m and hm m m suc a hm hm m 7393 m such that h171 hm Nonrepudiation Memga Alice s pmm key Bob sigmmxe Nonrepudiation Mzge S39gpaulm Memga Alice s pmm key Alice 5 public key Authentication MAC 7 Message Autentica on Codes keyed hash functions arbnrary lmgth message seem key K xed lauth MAC functions Basic requirements 1 Public description SECRET key parameter 2 Compression arbitrary length input gt fixed length output 3 Ease of computation MAC functions Security requirements Given zero or more pairs mi MACmi i lk it is computationally impossible to nd any new pair m MACm such that m qtmi i1k CBCMAC Cipher Block chaining MAC Message MAC Relations among security services NONVREPUDIATION AUTHENTICATION mTEGRTTY Nonrepudiation Bob S39gpaulm Memga Signature Hash fm nn I Hashvaluz 1 yes rltgt7 m Hashvaluz 2 I 17min key cipher Alice s privzm key Alice 5 public key Authentication Secret key anlice and Bah Hybrid Systems Features required from today s ciphers PERFORMANCE FUNCTIONALITY easy key distribution digital signatures Features of secretkey ciphers FUNCTIONALITY easy key distribution digital signatures Features of publickey ciphers PERFORMANCE FUNCTIONALITY easy key distribution digital signatures Average Decryption Speed for implementations based on the same technology software hardware AES deciphering speed RSA1024 deciphering speed z 100 z 1000 Basic operations of secret key ciphers Sbox S box n x m n rquot Substitution Software Hardware C ROM n bit address WORD S1ltltn 0x23 0x34 0x56 2n words ASM m bit output S DW 23H 34H 56H direct logic Basic operations of secret key ciphers PboX P box n x n g quot n Permutation Software Hardware C X1 szs anxn sequence of instructions ltlt I amp YI yZ Y3 Yn1 Yr ASM sequence of instructions ROL OR AND order of wires Basic Operations of the Public Key Cryptosystem RSA Encryption II public key exponent ciphertext I I Plaintext I mod I public key modulus k bits k bits k bits Decryption private key exponent plaintext I I Ciphel teXt I mod Iprivate key modulus k bits k bits k bits Alice Hybrid Systems session key random secretkey Bob s public key Bob s private key Session key encrypted using Bob s public key Message encrypted using session key Hybrid Systems Sender s Side 2 Alice session key random Public key cipher message Secret key cipher Session key encrypted using Bob s public key Message encrypted using session key Hybrid Systems Receiver s Side 2 Bob session key random Secret key cipher Public key cipher B Obas private key 365503 key Message encrypted encryp e mug using session key Bob s public key Evaluating the security of secretkey ciphers Classi cation of attacks 1 Ciphertext only attack Given ciphertext Looked for plaintext or key Example Frequency analysis of letters in the ciphertext effective only for most simple historical ciphers Classification of attacks 2 Known plaintext attack Given ciphertext guessed fragment of the plaintext Looked for remaining plaintext or key Example successive exhaustive key search bruteforce attack keys ECE 646 Lecture 8 SecretKey Ciphers IDEA RC5 IDEA X Lai J Massey E TH 199091 128bit key billion machines each checking billion keys per second still would require 10 trillion years to check all keys used in PGP Pretty Good Privacy the most popular public domain program for secure email constructed to provide an absolute resistance against differential cryptanalysis IDEA Three basic operations X X YX K YXKmod216 YXKmod2161 where 0 represents 216 Corresponding inverse operations Y X Y K X Y K mod 216 X Y Kl mod 2161 Halfround of IDEA Transformation Forward transformation Xd Xa Xb Xc Ka w KC Kd Ya Yb Yo Yd Inverse transformation Yd Ya Yb Yo Kal Kb Kd39l Xa Xb Xc Xd Halfround of IDEA Subencryption Forward transformation X Xb Xc Xd WinXaBXb VinXcBXd MANGLER Ke FUNCTION Kf Wont Vout Ya Xa GD Wont Yd Xd GD Vout Yb Xb D Wont Yc Xe D Vout Halfround of IDEA Subencryption Inverse transformation Yb Yc Yd WinXa Xb VinXc Xd MANGLER Ke FUNCTION Kf Wont Vout j 3 X21 Ya D Wont Xd Yd D Vout Yb Yb GD Wont Xe Yc GD Vout

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