Transcription
The Cryptographic Year in ReviewBart PreneelISSE 2012, Brussels2012Cryptography securityhttp://www.ecrypt.eu.orgcrypto is only a tiny piece of the securitypuzzleThe Cryptographic Yearin Review– but an important onemost systems break elsewhereProf. Bart PreneelCOSICKU Leuven, BelgiumBart.Preneel(at)esat.kuleuven.be– incorrect requirements or specifications– implementation errors– application level– social engineering (layer 8)24 October 201212AES updateOutline crypto algorithms– symmetric encryption– hash functions– public key crypto– padding attacksRijndael algorithm designed in Belgiumminor theoretical weaknesses in 2010/20112012: no news is good news2255 implementations validated by NIST fast implementation: PKI hacks bitsliced2010 Intel Westmere2011 Intel Sandy Bridge2011 AMD Bulldozer2012 Intel Ivy Bridgecycle per byte7.601.270.641.300.6434Hash functionsGSM/DECTprotect short hash valuerather than long text easy to break tools are available to get traffic and keycollision resistancepreimage resistance2nd preimage resistanceSatellite telephonesThis is an input to a cryptographic hash function. The inputis a very long string, that isreduced by the hash function to astring of fixed length. There areadditional security conditions: itshould be very hard to find aninput hashing to a given value (apreimage) or to find two collidinginputs (a collision). GMR-1 and GMR-2 broken used by Thuraya and militaryintercepting phone conversations is illegal5h1A3FD4128A198FB3CA34593261
The Cryptographic Year in ReviewBart PreneelISSE 2012, Brussels2004 Hash function crisis:the complexity of collision attacksSHA-1log2 complexitybrute force: 4 million PCs or US 100K hardware (1 year)9080706050403020100designed by NIST (NSA) in ‘94[Wang ’05][Mendel ’08][Manuel ’09][Stevens’12][Wang ’04]MD4MD5SHA-0SHA-1Brute force[Sugita ’06][McDonald Most attacksunpublished/withdrawnprediction: collision for SHA-1 in the next 12 months788NIST AHS competition (SHA-3)Alternatives to SHA-1SHA-3: 224, 256, 384, and 512-bit message digests(similar to SHA-2)Call:02/11/07 RIPEMD-160 [BSI/KU Leuven 96]– still unbroken but output length too short forlong term securityDeadline (64): 31/10/08Round 1 (51): 09/12/0880 SHA-2SHA 2 [NIST/NSA 02]60– seems to withstand attacks– some reservationsRound 2 (14): 24/7/096451Final 4/08Q3/09round 1round 29Preliminary Cryptanalysisfinal10Round 2 CandidatesaSlide credit: Christophe De Cannière, KU Leuven11Slide credit: Christophe De Cannière, KU Leuven122
The Cryptographic Year in ReviewBart PreneelISSE 2012, BrusselsSoftware performance - eBash [Bernstein-Lange11]Finalistslogarithmic scalesloweraSlide credit: Christophe De Cannière, KU Leuvenfactor 4 in cycles/byte13Hardware: post-place & route results forKeccakASIC 130nm nal version:SkeinSkein 5x5 array of 64 bits00permutation: 25, 50, 100, 200, 400, 800, (GateEqv) 18 rounds of 5 steps15Slide credit: Patrick Schaumont, Virginia Tech15Performance of hash functions - Bernstein16Public key crypto(cycles/byte) Intel Core 2 Quad Q9550; 4 x 2833MHz (2008)2001“new” factorization record in January 2010: 768 bitsupgrade your RSA-1024 keys should have been done in 2010 still lots of 512-bit keys aroundPublic-Keyy Cryptologyypgyincreased “acceptance” of ECC– example NSA Suite B in USA– Certicom challenge: ECC2K-130: 1 year with 60KEURO (a large effort is underway)– limited commercial deployment outside government(estimated)17183
The Cryptographic Year in ReviewBart PreneelISSE 2012, BrusselsKey lengths for confidentialityQuantum cRSAexponential parallelismECCdays/hours505121003-4 years10-20 years731031024204814620630-50 years1414096282n coupled quantum bits2n degrees of freedom !Shor 1994: perfect forfactoringbut: can a quantum computerbe built?Assumptions: no quantum computers;no breakthroughs; limited budget19If a large quantum computer canbe built.202001: 7-bit quantum computer factors 152007: two new 7-bit quantum computers2012: 21 has been factored yesterdayall schemes based on factoring (such as RSA) willbe insecuresame for discrete log (Zp, ECC)symmetricsye c keyey ssizes:es x2hash sizes: unchanged!alternatives: postquantum crypto– McEliece, NTRU, – so far it seems very hard to match performance of currentsystems while keeping the security level against conventionalattacks2012: 10 to 15 years for a large quantumcomputerQuantum Computing: An IBM PerspectiveSteffen, M.; DiVincenzo, D. P.; Chow, J. M.; Theis, T. N.; Ketchen, M. B.QuantumQuantum physics provides an intriguing basis for achieving computationalpower to address certain categories of mathematical problems that arecompletely intractable with machine computation as we know it today. Wepresent a brief overview of the current theoretical and experimental works inthe emerging field of quantum computing. The implementation of a functioningquantum computer poses tremendous scientific and technological challenges,but current rates of progress suggest that these challenges will besubstantively addressed over the next ten years. We provide a sketch of aquantum computing system based on superconducting circuits, which are thecurrent focus of our research. A realistic vision emerges concerning the formof a future scalable fault-tolerant quantum computer.21Problematic public keys (1/3)[Lenstra-Hughes Crypto 12]11.7 million openly accessiblepublic keys (TLS/PGP)6.4 million distinct RSA modulirest: ElGamal/DSA (50/50) and 1ECDSA1.1%1% off RSA kkeys occur iin 1 1certificate easy to factor: 0.2% of RSA keys 12,000 keys! 40% have valid certs22Problematic public keys (2/3)[Heninger Usenix Sec. 12] low entropy during key generation RSA keys easy to factor, because they form pairslike: n p.q and n’ p’.q so gcd(n,n’) q DSA keys: reuse of randomness during signing orweak key generation12 million openly accessible publickeys (5.8 TLS/6.2 SSH)23 million hosts (12.8/10.2)1%: 512-bit RSA keys embedded systems 55.6%6% of TLS hosts share publickeys 5.2% default manufacturer keys 0.34% have by accident thesame key why ? routers, servermanagement cards,network security devices key generation at firstboot easy to factor: 0.5% of TLS hostsand 0.03% of SSH hosts DSA key recovery: 1.6% of DSAhosts23RSA versus DSARon was wrong, Whit is right or vice versa?244
The Cryptographic Year in ReviewBart PreneelISSE 2012, BrusselsReaction attack (aka padding attack)Problematic public keys (3/3)Eveethical problem: how to report this?what would theplaintext be?details:Lenstra, Hughes, Augier, Bos, Kleinjung, Wachter, “RonRon was wrong,Whit is right” http://print.iacr.org/2012/064.pdf, or with as title“Public keys,” Crypto 2012.Heninger, Durumeric, Wustrow, Halderman, “Mining Your Ps and Qs:Detection of Widespread Weak Keys in Network Devices,” UsenixSecurity ity12/techschedule/technical-sessionsBobAliceMeet me tonight at 20:00at the Grand PlaceMeet me tonight at 20:00at the Grand Place25Reaction attackEve26Reaction attack (attempt 1)Evelet’s modify theciphertextsorry, youmessage ismalformedlfderrorBobAliceBobAlice 27Reaction attack (attempt 2)Eve28Reaction attack (attempt 3)modify ciphertextin a different wayEvesorry, youmessage ismalformedlfdSorry, youmessage ismalformedlfdf t forwardfastfderrorAliceerrorBobAlice 29Bob 305
The Cryptographic Year in ReviewBart PreneelISSE 2012, BrusselsReaction attack (attempt 1001)Reaction attacks: well knownMeet me tonight at 20:00at the Grande PlaceEveGreat! Now I knowthe plaintext[Bleichenbacher 98] PKCS #1v1.5 – 1 million chosenciphertexts (in practice 200,000)[Klima-Pokorny-Rosa 03] 40% Steel-Tsay 12]– reduced to about 10,000 chosen ciphertexts[Manger 01] OAEP PKCS #1v2[M#1 2 – a fewf1000 chosenhciphertextsi h t t[Bellare-Kohno-Namprempre 02]: SSH[Vaudenay 02] SSL, IPsec, WTLS.[Canvel-Hiltgen-Vaudenay-Vuagnoux 03]: SSL/TLSokkokSolution:– don’t send error messages (bad engineering practice)– KEM/DEM schemes and symmetric authenticatedencryptionBobAlice3132“Efficient padding oracle attacks oncryptographic hardware” (PKCS#11 devices)[Bardou 12]Outlinemost attacks take less than 100 milliseconds crypto algorithmsPKCS#1v1.5DevicetokensessionCBC padtokensessionAladdin eTokenProXXXXFeitian ePass 2000OKOKN/AN/AFeitian ePass 3003OKOKN/AN/AGemalto CyberflexXN/AN/AN/ARSA Securid 800XN/AN/AN/AXXN/AN/AOKOKXOKOKN/AN/ASafenet iKey 2032SATA dKeySiemens CardOSX(89 secs)– symmetric encryption– hash functions– public key crypto– padding attacks PKI hacks33342008 Rogue CA Molnar-Osvik-de Weger ’08]the biology analogyrequest user cert; by specialcollision this results in a fakeCA cert (need to predict serialnumber validity period)the car analogycars have brakes so they can go fastimpact: rogue CA thatcan issue certs thatare trusted by allbrowsershidden assumption:you never drivedownhillUser1Self-signedroot keyCA1CA2User2User xRogue CA6 CAs have issued certificates signed with MD5 in 2008:Rapid SSL, Free SSL (free trial certificates offered by RapidSSL), TCTrustCenter AG, RSA Data Security, Verisign.co.jp35366
The Cryptographic Year in ReviewBart PreneelISSE 2012, BrusselsFlame (successor of Stuxnet/Duqu)Malicious certificates discovered in May 2012 by Cert in Iran targeted cyber espionage in Middle Easterncountries vectors: LAN, USB, Bluetooth record audio, screenshots, keyboard activity andnetworktk traffict ffi (including(i l di SkSkype)) kill command to wipe out its traces (used on June8 2012) advanced MD5 collision attack built-in to createfake certificate for Microsoft Enforced LicensingIntermediate PCA (Windows Update) Aug’ 11 Diginotar: target Iranian opposition May ‘12 Flame– June ’12: Microsoft no longer supports RSA keys shorterthan 1024 bits (except if signed before 1/1/2010)– NIST’s deadline is 31/12/2013 Sept.Sept ‘12:12: Adobe problemTLSCeci n’est pas un HSM similar to but independent from rogue CA attack37Hacks38Does Big Data Means Big Hacks? Privacypsychology: humans are very bad atmanaging and evaluating risks in complexsystemseconomics: information security risks areypy systemicywith largeg markettypicallyfailures in part due to negativeexternalities (e.g. software, e-commerce)– Aug ’12: US Federal Trade Commission ordersweb giant to pay 22.5m for violating privacy ofrival Apple's Safari browser users– Politicians and laws talks about cookies, butweb companies have found many other coolways to keep tracking users Javanot so different from other areas: thelarger the scale, the larger the risk (too bigto fail)– Aug’12: Super-critical 0-day exploits 2 bugs Browsers– Sept ’12: new 0-day on Internet Explorer3940SummarySecure Computation PKIbankingcredit cardGoogleeBay AES is not broken but SHA-1 will be soonSHA-3 has been selectedkey generation remains problematicneed to develop post quantum cryptomultiparty computation becomes practical upgrading and fixing remains problematicmulti-party computation“you can trust itbecause you don’t have to”41 old attacks keep coming back and new attacksget better2012 was an exciting year for cryptanalysts427
The Cryptographic Year in ReviewBart PreneelThe endISSE 2012, BrusselsThank you foryour attention8 nov ‘12 ICC Ghent29 30 nov ‘1229-30www.foryoureyesonly.be4-8 March’13 www.secappdev.org4-7 June’13 COSIC coursewww.cosic.be438
token session token session Aladdin eTokenPro XX X X Feitian ePass 2000 OK OK N/A N/A 33 Feitian ePass 2000 Feitian ePass 3003 OK OK N/A N/A Gemalto Cyberflex X N/A N/A N/A RSA Securid 800 X N/A N/A N/A Safenet iKey 2032 XXN/A N/A SATA dKey OK OK OK OK Siemens CardOS X X (89 secs) N/A N/A Outline crypto algorithms - symmetric encryption .
