NIST Cryptographic StandardsStatus Report : NIST Cryptographic Standards Status Report April 4, 2006 Bill Burr Manager, Security Technology Group NIST william.burr@nist.gov


Crypto Standards Toolkit: Crypto Standards Toolkit Standardized, best of breed solutions for Encryption algorithms modes of operation Message authentication Digital signature Hashing Key generation deterministic (pseudorandom) and nondeterministic (hardware) key derivation Key management agreement transport wrapping Random number generation


Acronyms (some are new): Acronyms (some are new) DLC: Discrete Logarithm Cryptography FFC: Finite Field Cryptography Digital Signature Algorithm (DSA), Diffie-Hellman (DH) and MQV* ECC: Elliptic Curve Cryptography ECDSA, ECDH, and ECMQV* Believed secure if it’s hard to find discrete logarithms in FF or EC spaces respectively IFC: Integer Factorization Cryptography RSA is only algorithm in this category we use Reversible: can use for encryption or digital signatures Believed secure if its hard to factor big numbers * MQV: Menenzes, Qu and Vanstone - efficient secure authenticated key agreement protocol that uses DLC


Cryptographic Standards: Cryptographic Standards Security Requirements for Cryptographic Modules FIPS 140-2 Symmetric Key * DES (FIPS 46-3) * TDES (SP-800-67) * AES (FIPS 197) * Block Cipher Modes - SP 800-38A, B, C * HMAC (FIPS 198) Public Key * Dig. Sig. Std. FIPS 186-2& FIPS 186-3 - DSA – bigger keys - RSA (X9.31 and PKCS #1) - ECDSA (X9.62) * Key Establishment Schemes - SP 800-56A (DH & MQV; FFC & ECC Schemes; X9.42 and X9.63) - SP 800-56B (IFC Schemes; X9.44) * Key Management Guideline - General Guidance - Key Management Organization - Application-Specific Guidance Secure Hash * SHA-1, SHA-224, SHA-256. SHA-384, SHA-512 (FIPS 180-2) Random Number Generation * SP 800-90 (X9-82) FFC: Finite Field Crypt. i.e., DSA, DH, MQV IFC: Integer Factorization Crypt., i.e., RSA ECC: Elliptic Curve Cryptography, i.e., ECDSA, ECDH, ECMQV


Theoretical Comparable Strengths: Theoretical Comparable Strengths Note: Approx. strength of hash functions used in HMAC, rand. no. gen. or key derivation is hash size itself Sym. Key: Symmetric key encryption algorithms FFC and IFC: Finite field discrete log and factoring based public key algorithms ECC: Elliptic Curve discrete log based public key algorithms White background: expected to be secure until at least 2030 Yellow background: Phase out use by 2010 Size in bits


NIST Crypto Standards Status: NIST Crypto Standards Status Black Text: FIPS approved or NIST Recommended Blue italic text: Public Review begun Red Italic text: Under development Hashed background: no plans for this strength Black background: Withdrawn


Recent Events: Random Number Generation: Recent Events: Random Number Generation SP 800-90: Deterministic Random Bit Generators Draft for public review Dec. 2005 Hash, HMAC, block cipher and number theoretic (Elliptic Curve) based generators ANSI X9.82: Consists of four parts Part 1: Overview and Basic Principles Part 2: Entropy Sources Part 3: Deterministic (pseudo-random) Random Bit Generators Part 4: Random Bit Generator Constructions Workshop held Summer 2004


Recent Events: Recent Events FIPS 186-3 Digital Signature Standard began Public Review Extend DSA to include 2048-bit & 3072-bit keys ECDSA & RSA also updated RNG: Points to SP 800-90 Assurance: Points to SP 800-89 (also posted for comment) Public Review ends June 12th http://csrc.nist.gov/publications/drafts.html NIST SP 800-56A: Recommendation for Par-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography Posted: March 2006 http://csrc.nist.gov/publications/nistpubs/ Covers FFC and ECC Diffie-Hellman and MQV schemes


The Future – Near Term: The Future – Near Term Post SP 800-38D, GCM for comments Start issuing Pub. Key certificates with at least 2k FFC or 224 bit ECC keys and SHA-256 or SHA-224 by 2008 Stop using 80-bit equivalent crypto by 2010 Don’t rely on 2key TDEA, SHA-1 (for signatures), 160-bit ECDSA, 1024-bit RSA, 1024-bit DSA, 1024-bit DH & MQV key agreement after Dec 31, 2010 Hash Standard workshops and competition Response to cryptanalysis of SHA-1 Define requirements in workshops – next one Aug. 24-25 in Santa Barbara Competition for new Hash Function standard to supplement or supplant SHA-2 hash functions


Future for Public Key Crypto: Future for Public Key Crypto NIST expects to allow continued use of finite field public key cryptography for the foreseeable future Need 2048-bit keys after 2010 NIST encourages movement to Elliptic Curve methods for 128-bit equivalent public key crypto May never see wide use of 3k FFC & IFC PK algorithms ECC patents should be a minor issue long before we need 128-bit equivalent public key crypto in most unclassified applications With bigger keys, ECC is much more efficient NIST encourages adoption of MQV key agreement protocol Many good properties Specified in SP 800-56A


Full MQV Key Agreement Scheme: Full MQV Key Agreement Scheme One way to view Full MQV is as ephemeral-ephemeral Diffie-Hellman with static keys (contained in PKI certificates) included Get nice properties of e-e DH (forward secrecy) with authentication for about 25% more computation The shared secret is computed from the identifiers of A and B (IDA & IDB), the ephemeral key pairs (ePubA, ePrivA, ePubB & ePrivB), and the static key pairs (sPubA, sPrivA, sPubB & sPrivB). ms1 & ms2 are distinct message strings. K is an authentication key derived from the shared secret. Static public keys or certificates may be obtained out of band. A B IDA, ePubA, Cert(sPub)A IDB, ePubB, MACK(ms1, IDB, IDA, ePubB, ePubA), Cert(sPub)B MACK(ms2, IDA, IDB, ePubA, ePubB)


SP 800-56: MQV Key Agreement Scheme: SP 800-56: MQV Key Agreement Scheme Most good security properties with the fewest messages and public key operations of any key agreement scheme Various combinations of static and ephemeral keys 1, 2 & 3 pass protocols MQV primitives for FFC and ECC Nice properties Implicit key authentication Explicit key authentication Forward secrecy Key compromise impersonation resilience Unknown key-share resilience Certicom patents on MQV IETF proposals from Certicom for TLS and IPSEC No security proof in the Canetti-Krawczyk model


Hash Functions – a Hot Topic: Hash Functions – a Hot Topic Hash functions take a variable-length message and reduce it to a shorter fixed message digest Many applications: “Swiss army knives” of cryptography: Digital signatures (with public key algorithms) Random number generation Key update and derivation One way function Message authentication codes (with a secret key) Integrity protection code recognition (lists of the hashes of known good programs or malware) User authentication (with a secret key) Commitment schemes Recent Cryptanalysis changing our understanding of hash functions Prof. Wang’s analysis of MD5, SHA-0 and SHA-1 & others


Merkle-Damgard Hash Functions: Merkle-Damgard Hash Functions Take a long message, break it into blocks (typ. 512 bits) M1, M2, M3…Mk (pad out last block) Let F be a “compression function” that operates on a block and the current h-bit state and “mixes” the block into the state Last output of compression function is the h-bit message digest. M1 h-bit fixed IV h-bit chaining value h-bit message digest … F F Mk … …


Hash Function Properties: Hash Function Properties Preimage resistant Given only a message digest, can’t find any message (or preimage) that generates that digest. Roughly speaking, the hash function must be one-way. Second preimage resistant Given one message, can’t find another message that has the same message digest. An attack that finds a second message with the same message digest is a second pre-image attack. It would be easy to forge new digital signatures from old signatures if the hash function used weren’t second preimage resistant Collision resistant Can’t find any two different messages with the same message digest Collision resistance implies second preimage resistance Collisions, if we could find them, would give signatories a way to repudiate their signatures


Halloween Hash Bash: Halloween Hash Bash Held Oct. 31-Nov 1 2005 at NIST Recommendations: Getting rid of MD5 is highest priority NIST never recommended MD5, but it is widely used OK to continue using SHA-1 a few more years in old apps (really have to) but new apps must use something else (SHA-2) But we don’t want apps to roll their own crypto SHA-2 support doesn’t arrive from Microsoft until Vista Long tail to XP Can’t issue only SHA-2 certificates until clients can do SHA-2


Hash Bash on SHA-2: Hash Bash on SHA-2 A family of algorithms, but only SHA-256 is usually discussed Very little analysis yet - rather complex May be theoretical break within a decade Probably won’t be a practical attack within a decade Not very efficient in hardware Can fix problems with more rounds Need to be more conservative with number of rounds generally (think block cipher) NIST recommends for relatively near term


Hash Bash: General Observations: Hash Bash: General Observations Merkle-Damgard hash as random oracle => trouble ? Algorithm agility is needed Resilience: several hash functions But: algorithm agility “sucks” in hardware So: we should overbuild But: everybody pays all the time for that


Hash Bash: The Future: Hash Bash: The Future Still uncertain about exactly what we want Beyond Merkle-Damgard: block “generic attacks” Maybe we need more specialized functions MACs, Digital Signatures, PRFs, KDF? Better design Higher hamming weights Better compression functions Provable security? Number theoretic or equivalent to breaking something? Improve protocols to rely less on hash function properties


NIST Policy on SHA-1 and SHA-2: NIST Policy on SHA-1 and SHA-2 Federal Users may use SHA-2 family hash functions (SHA-224, SHA-256, SHA-384, & SHA-512) for all hash function applications. For digital signatures, commitment schemes, time-stamping and other apps that require collision resistance, Federal users: Should convert to SHA-2 as soon as practical, but Must stop using SHA-1 for these apps by end of 2010 Federal users are encouraged to use SHA-2 for all new applications; however, they may continue to use SHA-1 after 2010 for: HMAC Key derivation Random number generation


Longer Term: Hash Standard Strategy: Longer Term: Hash Standard Strategy For reasonably long term, not a crash program Still discussing requirements/criteria Hash functions not as mature as block cipher design in late 90s Flesh out requirements & criteria Additional workshop(s) First one after Crypto2006, August 24-25, 2006 in Santa Barbara Competition Probably 2 stages, as with AES Selection How many? How do we improve significantly on SHA-2?


NSA Suite B: NSA Suite B Previously, NIST’s open crypto algorithms used to protect sensitive unclassified data could not be used to protect classified data. That is no longer the case: NIST and NSA have been working to offer a standardized, public set of algorithms that can be used to protect both unclassified and classified information. The result is Suite B, an NSA selected subset of the NIST toolkit for classified applications up through Top Secret http://www.nsa.gov/ia/industry/crypto_suite_b.cfm?MenuID=10.2.7 Specific NSA approval is still required for the implementations and systems that are used to protect classified information Expect more guidance from NSA on acceptable key management Should be consistent with SP 800-57


Suite B: Suite B FIPS 140 Cryptographic Module Validation required for unclassified applications NSA will evaluate products used for classified applications Commercial COMSEC Evaluation Program (CCEP) and User Partnership Agreements (UPA) Not only evaluate a vendor's product, but also provide extensive design guidance on how to make a product suitable for protecting classified information Use of Suite B algorithms is only one step in a larger process


CNSSP #15: CNSSP #15 Committee on National Security Systems Policy No. 15 128-bit AES can be used for up to SECRET 192 & 256 bit AES can be used for up to TOP SECRET Only AES-256 is used in Suite B http://www.cnss.gov/Assets/pdf/cnssp_15_fs.pdf


Suite B – the algorithms: Suite B – the algorithms Encryption Algorithm AES (FIPS 197) AES-128 up to SECRET AES-256 up to TOP SECRET Digital Signature (FIPS 186-3) ECDSA with 256-bit prime modulus up to SECRET ECDSA with 384-bit prime modulus up to TOP SECRET Key Agreement (NIST SP 800-56A) EC Diffie-Hellman or EC MQV with 256-bit prime mod. up to SECRET EC Diffie-Hellman or EC MQV with 384-bit prime modulus up to TOP SECRET Hash Functions (FIPS 180-2) SHA-256 up to SECRET SHA-384 up to TOP SECRET


Encryption Algorithms: Encryption Algorithms


Hash Algorithms (for dig. signatures): Hash Algorithms (for dig. signatures)


Digital Signature: Digital Signature * Prime Modulus curves only


Key Establishment: Key Establishment * Prime Modulus curves only


Why AES 256 with ECC 384 in Suite B?: Why AES 256 with ECC 384 in Suite B? Theoretically AES 256 is equivalent to ECC 512 AES 192 is equivalent to ECC 384 By CNSSP # 15 192 bit AES is enough for Top Secret AES 192 not included in Suite B AES 256 with ECC 384 seems a mismatch But there is very little performance penalty for AES 256 About a 20% difference A lot of people are choosing to use AES 256 There is a significant performance cost going to ECC 512 and ECC 384 is strong enough for Top Secret Make life simple: use ECC 384, which is fast and strong enough, with AES 256 which is strong and fast enough.


Suite B: Bottom Line: Suite B: Bottom Line Some folks need to do both classified and unclassified applications National security apps. need to use ordinary commercial software No fundamental difference between algorithms for SBU & classified NIST & NSA cooperation: cryptography for both SBU and classified NSA approval of implementations required for classified Expect NSA-managed keying material for classified apps. Unclassified users must have CMVP validated crypto modules More choices of algorithms including the ones in Suite B Users typically generate their own keys Nobody looses; some of us gain


NIST Links: NIST Links NIST Computer Security Resources Center http://csrc.nist.gov/ NIST Crypto toolkit http://csrc.nist.gov/CryptoToolkit/ FIPS 201/PIV page http://csrc.nist.gov/piv-project/index.html FIPS page http://csrc.nist.gov/publications/fips/index.html NIST Security Special Publications http://csrc.nist.gov/publications/fips/index.html


Slide33: Questions ?


NIST Information Security Responsibilities: NIST Information Security Responsibilities NIST has been charged under a series of Laws with the responsibility for issuing guidance and standards for security Federal Information Security Management Act of 2002 (FISMA) Federal Information Processing Standards (FIPS) & NIST guidance apply only to the protection of unclassified, sensitive information by Federal agencies But they are widely adopted by others


NIST Cryptographic Standards “Toolkit”: NIST Cryptographic Standards “Toolkit” The Data Encryption Standard, FIPS 46, approved in 1978 began the modern era of open cryptographic standards US Federal government users must use NIST standards and guidance to protect unclassified, sensitive data Nobody else is required (by US law) to use them FIPS 140 Cryptographic Module Validation Program (CMVP) Crypto FIPS & recommendations are often adopted by others SHA-1, AES, DSS & DES became widely used ANSI & ISO standards No US Federal regulation of cryptography by the private sector Limited commercial crypto export controls & no crypto import controls Some laws/regulations may effectively require business crypto use


NIST Crypto Toolkit Philosophy: NIST Crypto Toolkit Philosophy Best of breed standardized algorithms Intended to be secure against analytic attacks Small but comprehensive set of algorithms and methods Promote interoperability It’s hard & expensive to analyze crypto and be sure it’s secure Industry doesn’t want to have to support too many algorithms Transparent Process – AES selection is a model Published standards, nothing is secret Do our best to explain our choices Invite the whole world to review and comment; work with international cryptographic community Do not rule out patented methods but must be freely licensed Patented crypto is very unpopular


Symmetric Key Block Cipher: Symmetric Key Block Cipher Encrypt & Decrypt with the same key Fast workhorse Used for most message and file encryption Used in a variety of “modes of operation” different security and other properties


Modes of Operation Recommendations: Modes of Operation Recommendations SP 800-38 A – Modes of operation for encryption - update of FIPS 81 ECB – Electronic Code Book CBC – Cipher Block Chaining CFB – Cipher Feedback OFB – Output Feedback Counter (not in FIPS 81) SP 800-38 B: CMAC Mode for Authentication SP 800-38 C: Counter with CBC MAC mode (CCM) Used by 802.11i for wireless LANs SP 800-38 D: Galois Counter Mode (GCM) – Working Draft DP 800-38 E: AES Key Wrap – waiting for active runway


CBC Mode: CBC Mode


Counter Mode(a stream cipher mode): Counter Mode (a stream cipher mode)


CCM Mode Overview: CCM Mode Overview Designed for IEEE 802.11 wireless LANs Use CBC-MAC to compute a MIC (Message Integrity Code) on the plaintext header, length of the header, and the payload Use CTR mode to encrypt the payload Counter values 1, 2, 3, … Use CTR mode to encrypt the MIC anywhere else we’d call it a MAC rather than a MIC Counter value 0 Header Payload MIC Authenticated Encrypted


Finding Hash Collisions: Finding Hash Collisions Find two messages with the same digest Birthday “paradox” Given a population of x equally probable values, we need roughly random samples to expect to find a single collision Therefore any attack on a hash with an n-bit message digest that finds a collision in much under 2n/2 operations is said to “break” the collision resistance property of the hash function Collision Resistance: a strong property A hash function that is collision resistant must necessarily be second preimage resistant


Finding Preimages: Finding Preimages Work backward from message digest to find a message that will produce it Expect to have to hash about 2n messages to find an unknown pre-image for any particular selected message digest Any attack that finds a preimage in significantly under 2n operations is a break of the one-way property or preimage resistance of a hash function If we can find second preimages, we can forge a new digital signature from an old signature


SHA-1 Collisions: SHA-1 Collisions Current best estimate ~ 262 to 263 operations to find a collision Attack due to Prof. Xiaoyun Wang Should be 280 262 is still a fair amount of work How much farther will it go? Would be nice to verify this result May be dangerous to do so How important are collisions? Two extreme views: Relatively minor, only matter for rare instances where we have to prove to a 3rd party (e.g. certain PKI apps), or; Canary in the mineshaft, crack in the dyke – a warning of much bigger dangers possibly close at hand