SOA Security and HSPD-12: Cryptographic Foundations

Cryptographic Foundations for Understanding HSPD-12 and FIPS 201 Compliance Requirements
Post Overview
• Brief Overview of FIPS 201
• Cryptographic Foundations and Standards for FIPS 201

Additional Publications in Support of FIPS 201
– NIST Interagency Report 7337 Personal Identity Verification Demonstration Summary
• Report summarizes the demonstration of commercially available products that support FIPS 201 and the accompanying special publications
– NIST 800-06 PIV Card to Reader Interoperability Guidelines
• Provides interoperability requirements for PIV card readers in the areas of
– Performance
– Communications
• Covers two types of card readers:
– Contact card readers
– Contactless card readers
• Covers both access use cases:
– Physical access
– Logical access.
• Requirements are for PIV readers designed to read end-point cards.

Cryptographic Foundations and Standards for FIPS 201
• Review of Cryptographic Objects in FIPS 201
• Cryptographic Foundations
• FIPS 201 Cryptographic Requirements
• FIPS 201 Certificate Status Information Requirements

Cryptographic Mechanisms Specified in FIPS 201
Asymmetric PIV authentication key
Card authentication key
Asymmetric digital signature key for signing documents and messages
Asymmetric key management key, supporting key establishment or key transport

Cryptographically Protected Objects in FIPS 201, SP 800-73 and SP 800-76
Authentication Information Stored on the PIV Card
The following objects on the PIV card are required to be digitally signed by FIPS 201 and SP 800-73:
– The CHUID
– Biometric information
– The SP 800-73 Security Object
– X.509 Public Key certificates

Public Key Cryptographic Algorithms For Digital Signatures
• Rivest-Shamir-Adelman (RSA)
• Elliptic Curve Cryptography Digital Signature Algorithm (ECC DSA)
Cryptographic Components used with RSA Public Key Encryption
• The following components must be used with RSA in order to be secure:
– A hashing algorithm
– A padding scheme

Rivest-Shamir-Adelman (RSA) Public Key Encryption Algorithm
• An algorithm invented in 1978 based on the difficulty of factoring large integers, which can be used for encryption and digital signatures
• The algorithm is based on a public key which comprises a number N which is the product of two large primes (referred to as the modulus) and another number which is relatively prime
• The algorithm produces a private key, which is the multiplicative inverse of the relatively prime number which is included in the public key which is extremely difficult to calculate
• It is widely believed that the private key is as difficult to as it is to factor the integer N, but it has not been proven to be as difficult

Secure Hash Algorithms (SHA) for RSA
• Because the RSA algorithm requires the use of a hash algorithm, a secure hash algorithm must be used along with RSA
• The SHA family is a set of related cryptographic hash functions that were designed by the National Security Agency
• SHA has two major subsets:
– SHA-1
• Published in 1995
• Was considered to be the successor to the widely used MD5 function
• Vulnerable to known attacks
– SHA-2 (including SHA-224, SHA-256, SHA-384 and SHA-512)
• No attacks have yet been reported
• Because they are similar to SHA-1 researchers are working on more secure hashing standards to use in the event that SHA-2 is compromised

Purpose of Padding Schemes in RSA
• RSA must be combined with a padding scheme for the following reasons:
– To increase message size in order to address the following problems that can occur in short messages:
• Values m=0 and m=1 produce ciphertexts equal to 0 or 1 because of the properties of exponentiation
• Ciphertexts can be easily decrypted by taking the eth root of the ciphertext if using low encryption exponents and small values of m
– To provide a non-deterministic mapping from plaintext to ciphertext in order to defend against chosen plaintext attacks, which deterministic encryption algorithms such as RSA are vulnerable to

Specific Padding Schemes Used for RSA
• Public Key Cryptographic Standard (PKCS) #1 v 1.5
• Padding based on the Probabilistic Signature Scheme (PSS)

PKCS (Public Key Cryptography Standards) #1 v1.5
• Specified in the Network Working Group RFC 2313, Mar. 1998
• The original PKCS #1 standard was subject to chosen and adaptive ciphertext attacks
• PKCS #1 was modified to specify a plaintext-aware padding scheme, meaning that an adversary cannot produce a valid ciphertext without actually knowing the underlying plaintext, which defends against chosen ciphertext attacks
• However, because PKCS #1 v1.5 contains ad hoc constructions, it has not until now been proven secure against adaptive ciphertext attacks according to RSA Laboratories, the holder of the patent for the RSA public key encryption algorithm
• Used by most current implementations of RSA, but not recommended for new applications, for which an Optimal Asymmetric Encryption Padding (OAEP) scheme is recommended

Probabilistic Signature Scheme (PSS)
• A provably secure way of creating signatures with RSA
• Uses hashing in a sophisticated way to tie the security of the signature scheme to the security of RSA
• This is based on the notion that a digital signature scheme is provably secure if its security can be tied closely to that of an underlying cryptographic primitive, in this case RSA
• Developed by Mihir Bellare and Phillip Rogaway in 1996

Cryptographic Components Required For using Elliptic Curve Based Public Key Encryption
• An algorithm based on the difficulty of the discrete logarithm problem for elliptic curve groups
• A hashing algorithm

Elliptic Curve Digital Signature Algorithm (ECDSA)
• A variant of the Digital Signature Algorithm (DSA) that operates on elliptic curve groups
• The discrete logarithm problem is expressed by the problem of solving the following equation where a and c are known:
• ab=c
• An elliptic curve is a plane curve defined by an equation of the form:
• y2=x3 + ax + b
• The solutions to this equation form a finite abelian group
• Elliptic curve cryptography is based on the difficulty of solving the discrete logarithm problem on an elliptic curve group, which is believed to be more difficult than the corresponding problem in the underlying finite field
• It therefore provides smaller key sizes for the same security level, with execution time and signature size exactly the same
• While no proof of the difficulty of ECC has been published as of 2006, it is recommended by the National Security Agency in its Suite B set of recommended algorithms for communication of data with classification levels up to TOP SECRET

Hash Algorithms for ECDSA
• Because Elliptic Curve Digital Signature Algorithm uses a hash function, hash algorithms are required just as they are in RSA
• SHA-224 and SHA-256 are examples of hash algorithms that can be used with ECDSA

Key Management Key Algorithms
The following algorithms are used for key management key management:
• Rivest-Shamir-Adelman (RSA)
• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Cryptography Menezes-Qu-Vanstone (ECC MQV)

Diffie-Hellman Key Exchange (foundation for ECDH)
• A cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.
• Because the parties involved are not known to each other it is known as an anonymous or non-authenticated key agreement protocol.
• It provides the basis for a variety of authenticated protocols and is used to provide perfect forward secrecy in Transport Layer Security (TLS)’s ephemeral modes.
• First published by Whitfield Diffie and Martin Hellman in 1976, although it was developed earlier by Malcolm J. Williamson of the British signals intelligence agency GCHQ, but was at that time classified.

How Diffie-Hellman Key Exchange Works
• An example:
• A and B agree to use a prime number p=23 and base g=5.
• A chooses a secret integer a=6, then sends B the value (g2 mod p) = 56 mod 23 = 8
• B chooses a secret integer b=15 and sends A the value (gb mod p) = 515 mod 23 = 19
• A computes the value (gb mod p)2 mod p = 196 mod 23 = 2, the shared secret
• B computes value (g2 mod p)b mod p = 815 mod 23 = 2, the shared secret
Both A and B have computed the same value because g2b and gb2 are equal. However computing the shared secret given g, p and g2 mod p cannot be done with the best known algorithms if p is a prime of 300 or more digits, and a and b are at least 100 digits long. This is known as the discrete logarithm problem.

Elliptic Curve Diffie-Hellman (ECDH)
• A key agreement protocol that allows two parties to establish a shared secret key over an insecure channel
• The key can be used to encrypt subsequent communications using a symmetric key cipher
• A variant of the Diffie-Hellman protocol using elliptic curve cryptography, which is based on a more complex version of the discrete logarithm problem allowing shorter key sizes for the same degree of security based on known algorithms
• Secure because nothing is disclosed other than the public keys, and extraction of the private key of one of the parties requires solution of the Elliptic Curve Discrete Logarithm Problem.

Elliptic Curve Cryptography Menezes-Qu-Vanstone (ECC MQV)
• An authentication protocol for key agreement (based on the Diffie-Hellman scheme) which was initially proposed in 1995
• Possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication
• Provides protection against an active attacker
• Has been shown by Hugo Krawczyk in June 2005 to be vulnerable to attacks in the Canetti-Krawczyk model of key exchange, which was acknowledged by Alfred Menezes in a proposed patch of ECC MQV called HMQV-1 in Nov. 2005
• Specified by the National Security Agency as part of the Suite B set of cryptographic standards for securing US Federal government communications up to the TOP SECRET classification

Algorithms for Card Management Keys
• Triple DEA
• Advanced Encryption Standard (AES)
DEA
• DEA is the Data Encryption Algorithm, also known as the Data Encryption Standard (DES)

Triple DEA
• Triple DEA is a block cipher formed from the DES cipher by using it three times
– Three steps are needed to prevent meet-in-the-middle attacks that are effective against double DES encryption
• Triple DEA requires keys that are 32 characters long and is ANSI standard for PIN management
– 2TDEA is Two Key Triple DEA
• A variant of 3TDEA that uses the same key as the first and third key, but is vulnerable to chosen-plaintext or known-plaintext attacks, giving it an effective security of 80 bits
– 3TDEA is Three Key Triple DEA
• Has a key length of 168 bits comprised of three 56-bit keys, with an effective security of 112 bits.

Advanced Encryption Standard (AES)
• AES, which is also known as Rijndael, is the Advanced Encryption Standard which is viewed as the natural successor to Triple DEA
– AES is around six times faster than TDEA
– AES provides a larger block size, potentially longer keys
– There are as of 2006 no known cryptanalytic attacks on AES, however there have been successful side channel attacks
– The following variants are used in FIPS 201, using the key sizes included in the variant name:
• AES-128
• AES-192
• AES-256

Advanced Encryption Standard (AES) Cipher
• AES operates on a 4x4 array of bytes, referred to as the state
• For encryption, each round of AES (except for the last round) is performed in four phases:
– 1: Each byte of the state is combined with the round key, each round key is derived from the cipher using a key schedule
– 2: Each byte is replaced with another using a lookup table, resulting in a non-linear substitution
– 3: Each row of the state is shifted cyclically a certain number of steps
– 4: The four bytes of each column are combined using a linear transformation
– The last round performs the first rounding step instead of the column combination

FIPS 201 Cryptographic Guidelines
• FIPS 201 Signature Algorithm and Key Size Requirements for PIV Information
• FIPS 201 Public Key Object Identifiers for PIV Key Types
• FIPS 201 Standards for Key Management
• FIPS 201 Hash Algorithm Standards for Message Digests in the NIST 800-73 Security Objects
• FIPS 201 Card Management Keys
• FIPS 201 Certificate Status Information
• Note: Guidelines listed in red are the ones that expire in 2010 due to the security level not being viewed as adequate beyond that date

FIPS 201 Signature Algorithm and Key Size Requirements for PIV Information
• Through 12/31/2010 the following are supported:
– RSA (1024, 2048 or 3072 bits), SHA-1 or SHA-256 hash algorithms, PKCS #1 v1.5 padding scheme
– RSA (1024, 2048 or 3072 bits), SHA-256 hash algorithm, PSS padding scheme
– ECDSA (Recommended Curves, 224-283 bits), SHA-1, SHA-224 or SHA-256 hash algorithms

• After 12/31/2010 the following are required:
– RSA (2048 or 3072 bits), SHA-256 hash algorithm, PKCS #1 v 1.5 padding scheme, PSS
– ECDSA (Recommended Curves, 224-283 bits), SHA-1, SHA-224 or SHA-256 hash algorithms

FIPS 201 Public Key Object Identifiers for PIV Key Types
• PIV Authentication Key, Card Authentication Key and Digital Signature Key may use the following asymmetric algorithms:
– RSA
• The Key Management Key may use the following asymmetric algorithms:
– RSA
– ECDH
– ECC MQV

FIPS 201 Hashing Algorithms for Message Digests in the SP 800-73 Security Objects
• Through 12/31/2010, SHA-1, SHA-224 or SHA-256 may be used
• After 12/31/2010, SHA-224 or SHA-256 may be used
• The specific formats for the Algorithm Object Identifiers are specified in SP 800-76

FIPS 201 PIV Card Management Keys
• PIV cards may support card activation by the card management system to support Card personalization Post-issuance card updates
• The algorithm and key-size requirements for Card Management Keys are:
– Through 12/31/2010, 2TDEA, 3TDEA, AES-128, AES-192 and AES-256 may be used
– After 12/31/2010, 3TDEA, AES-128, AES-192 and AES-256 must be used

FIPS 201 Certificate Status Information
• There are two formats for certificate status information used for the FIPS 201 functional component PIV Card Issuance and Management Subsystem
– X.509 Certificate Revocation Lists (CRLs)
– Online Certificate Status Protocol (OCSP) Status reponse messages

Certificate Revocation Lists
A Certificate Revocation is issued by a Certificate Authority (CA) that also issues X.509 Digital Certificates
A Certificate Revocation List is a list of certificate serial numbers representing certificates that have been revoked and should not be trusted, for one of the following reasons:
– Certificate was revoked by the Certificate Authority (CA)
– A temporary hold has been put on the certificate, possibly because the user believes the private key may have been compromised. The certificate can be later reinstated if the integrity of the private key has been re-established.

Online Certificate Status Protocol (OCSP)
– The Online Certificate Status Protocol is used for obtaining the revocation status of X.509 digital certificates
– Messages are encoded in ASN.1 and usually communicated using HTTP
– OCSP has the following advantages over CRLs:
– OCSP can provide more timely information regarding revocation status of a certificate
– OCSP removes the need for clients to retrieve the CRLs themselves, leading to less network traffic and better bandwidth management
– Clients do not need to parse CRLs themselves, saving client-side complexity
– An OCSP responder may implement billing mechanisms to pass the cost of validation transactions to the seller rather than the buyer
– Not subject to the unnecessary public exposure of CRLs (sometimes compared with credit card companies’ bad customer lists)
– Supports trusted chaining of OCSP requests between responders, allowing clients to communicate with a trusted responder to query an alternate responder, saving client-side complexity

Certificate Status Information Digital Signature Requirements
• Certificate status responses are required to be digitally signed to support authentication and integrity using the following standards, using algorithmic identifiers specified in SP 800-78:
– Through 12/31/2010, the following may be used:
• RSA (1024, 2048 or 3072 bits), SHA-1 or SHA-256 hash algorithms, PCKS #1 v1.5 padding scheme
• RSA (1024, 2048 or 3072 bits), SHA-256, PSS padding scheme
• ECDSA (Recommended Curves, 224-283 bits), SHA-224 or SHA-256 hash algorithms

– After 12/31/2010, the following are required:
• RSA (2048 or 3072 bits), SHA-1 or SHA-256 hash algorithms, PKCS #1 v1.5 or PSS padding scheme
• ECDSA (Recommended Curves, 224-283 bits), SHA-224 or SHA-256 hash algorithms