| Network Working Group | M. Campagna |
| Internet-Draft | Certicom Corp. |
| Intended status: Standards Track | October 12, 2012 |
| Expires: April 13, 2013 |
A Cryptographic Suite for Embedded Systems (SuiteE)
draft-campagna-suitee-04
This document describes a cryptographic suite of algorithms ideal for constrained embedded systems. It uses the existing IEEE 802.15.4 standard as a starting point, builds upon existing embedded cryptographic primitives and suggests additional elliptic curve cryptography (ECC) algorithms and curves. The goal is to define a complete suite of algorithms ideal for embedded systems.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http:/⁠/⁠datatracker.ietf.org/⁠drafts/⁠current/⁠.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 13, 2013.
Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http:/⁠/⁠trustee.ietf.org/⁠license-⁠info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
Constrained embedded systems and in particular devices for wireless personal and body area networks (WPAN and BAN respectively), have unique computation, power and bandwidth constraints. These systems are seeing wider deployment in Smart Energy, Home Automation, Personal Home and Health Care, and more broadly the so-called Internet of Things. The environments in which they are being deployed require varying degrees of security.
The Cryptographic Suite for Embedded Systems (SuiteE) aims to optimally meet the wide variety of cryptographic requirements, by providing a compact and complete collection of cryptographic algorithms having minimal code space, computational requirements and bandwidth usage. Additionally the selection of these algorithms are tuned to minimize overall system costs in mass production by selecting easily embeddable algorithms which will further reduce code space, energy usage and increase computational performance. It is expected that this suite of algorithms can be used to provide security solutions in the 6lowpan and CoRE space.
Mass production economics see many benefits of placing fixed routines in hardware. The benefits are in code space, performance, battery life, and overall cost of the device. This is the fundamental reason why most IEEE 802.15.4 devices implement AES in hardware today. Considering the projected scale of the so-called Internet of things (Cisco estimates the smart grid alone to be 100 to 1000 times the size of the Internet today), efficiencies and cost savings realized in embedding more of the lower level operations in hardware transforms into a basic requirement - technology selection should afford benefits to embedding in hardware.
Many of the environments in which these new embedded systems are being deployed have a life expectancy of 20+ years. This requires the selection of key lifecycle management mechanisms at a security level adequate to deliver the desired security services for the lifespan of the system. [NIST57] provides recommendations on general key management and security levels. We summarize the comparable strengths table and recommended minimum sizes:
| Algorithm Lifetime | Security Strength | Symmetric Key Size | Integer Factorization Cryptography Key Size (e.g., RSA) Size | Elliptic Curve Cryptography (ECC) Key Size |
|---|---|---|---|---|
| Through 2010 | 80 bits | 80 | 1024 | 160 |
| Through 2030 | 112 bit | 112 | 2048 | 256 |
| Beyond 2030 | 128 bit | 128 | 3072 | 256 |
| >Beyond 2030 | 192 bit | 192 | 7680 | 384 |
| >>Beyond 2030 | 256 bit | 256 | 15360 | 512 |
[NIST57] does not provide guidance on life span for security strengths for 192 and 256 bit presumably because of the uncertainty in forecasting technology 30+ years out.
Considering the expected life span of many of these systems and best industry practice we target the 128 bit security strengths for SuiteE.
The design goals of SuiteE are:
A complete cryptographic cipher suite should consist of primitives from which the security services of identification and authentication, confidentiality, data integrity and non-repudiation can be provided. We prescribe an encryption scheme with authentication, a deterministic random number generator, a hash function, a key-agreement scheme, a digital signature scheme, and a certificate scheme that achieves a 128-bit security level, and achieves the goals identified above.
The remainder of this document is organized as follows. Section 2 provides an authenticated encryption mode AES-CCM*. Section 3 provides a deterministic random number generator. Section 4 describes a hashing algorithm using the existing AES core in an AES-MMO mode. Section 6 indicates why elliptic curve technology is selected and the specific curve selection sect283k1. Section 7 specifies the use of an elliptic curve signature scheme with partial message recovery. Section 8 provides an implicit certificate scheme. Section 9 describes an elliptic curve based mutual authenticated key agreement scheme.
IEEE 802.15.4 [IEEE-802.15.4-2003] specifies the use of AES-CCM*, a variation of the Counter Mode with Cipher Block Chaining MAC (CBC-MAC) using AES-128. AES-128 is specified in [FIPS-197]. Using [IEEE-802.15.4-2003] as the normative reference we present a description of AES-CCM* here.
In the sections that follow we will assume that the basic block cipher is AES-128 as specified in [FIPS-197]. We will represent AES-128 as a function E taking two 128-bit inputs, a message block M, and key K, with 128-bit output C = E(M, K).
CTR mode or Counter Mode is a block cipher mode for providing confidentiality. It has some specific advantages in that both the encryption and decryption routines only require the block cipher to operate in a forward, or encrypt-only, direction.
Input: a 128-bit symmetric key K, and a plaintext message P of length Plen, and initial counter value CTR
Output: C
The Decryption routine for CTR mode is symmetric.
Input: a 128-bit symmetric key K, and a ciphertext message C of length Clen, and initial counter value CTR
Output: P
Cipher Block Chaining MAC Mode, CBC-MAC mode uses a block cipher to provide data integrity. Unlike CTR mode, that operates on arbitrary length strings CBC-MAC requires message padding to be on a multiple of the block length. The last message block will be padded out using zero bytes.
Input: a 128-bit symmetric key K, a message M of length Mlen
Output: T
Verification is done by identical computation on input K, message M, and purported MAC T' and an additional check where the computed MAC value T is compared to the received MAC value T' and accepted only if T = T'.
CCM mode is an authenticate and encrypt mode for block ciphers defined in [NIST-800-38C]. It is defined on a 128-bit block size block cipher. CCM* modifies this description to allow for modes that require only authentication, as well as variable length authentication tags.
We break this section up into 3 subsections, input transformation, authentication transformation, and encryption transformation. We will assume that the following inputs are provided to the routines.
Input:
Input:
Output: AuthData
Input:
Output: T
Input:
Output: Ciphertext and AuthTag
We break this section up into 2 subsections, decryption and authentication verification. The AES-CCM* Decryption process should both decrypt any encrypted portion of the message, and authenticate the decrypted message. It will return an error code, or plaintext data. We will assume that the following inputs are provided to the routines.
Input:
Input:
Output: U and Plaintext
Input:
Output: Plaintext or INVALID
This section provides a reduced set of options to the CTR_DRBG definition using AES as defined in [NIST-800-90].
We give a basic description of the AES block-cipher-based DRBG in the next few subsections. The description includes an update function, an initialization function, and a generate function. We will leave it up to implementers to consider other optional functions such as reseed.
We define the state of the CTR_DRBG using the following structure.
The update function CTR_Update() modifies the internal state variables V and K of the DRBG structure using provided data.
Input:
Output:
Functionally we write (V, K) = CTR_Update(V, K, data).
The update function CTR_Update() modifies the internal state variables V and K of the DRBG structure using provided data.
Input:
Output:
Functionally we write (counter V, K) = CTR_Init(seed).
NOTE: The CTR_Init() function can be simplified by making the observation that the resulting state is simply an XOR of the seed value with the fixed output values of AES(0^127||1_2, 0^128)||AES(0^126||10_2, 0^128) = 58E2FCCEFA7E3061367F1D57A4E7455A0388DACE60B6A392F328C2B971B2FE78_{16}, or (K||V) = 58E2FCCEFA7E3061367F1D57A4E7455A0388DACE60B6A392F328C2B971B2FE78 XOR seed.
The function CTR_Generate() modifies the internal state variables V and K of the DRBG structure, and generates a random output of the requested length rlen bytes. If the counter has exceeded 2^48 or rlen exceeds 2^16, an ERROR is returned, and the state is not modified.
Input:
Output:
Functionally we write ((counter V, K), (output, RESULT_CODE)) = CTR_Generate(V, K, data).
[ISO-10118-2] specifies hash functions using an n-bit block cipher. The first function from [ISO-10118-2] ("Hash-function one") maps arbitrary length inputs to n-bit outputs. This is the Matyas-Meyer-Oseas (MMO) construction described in [MOV96]. In the first subsection we specify a family of Merkle-Damgard strengthening (or MD-strengthening) functions that aims to account for existing deployments in ZigBee Smart Energy, and provide a gradual MD-strengthening that reduces padding on small messages.
The following subsection details an MMO construction that utilizes two input pre-processing steps. The first is a prefix-free encoding: the bitlength of the message encoded as a 128-bit integer is prepended to the input message. The second is the more common MD-strengthening transform, which essentially appends an encoding of the length and ensures the output is a multiple of the block length.
The hash function defined here is a not a general purpose hash function at the 128-bit security level, as it does not provide collision resistance. Application of this hash function should conform to the usages defined in this specification. The use of this hash function elsewhere requires careful consideration.
The prefix-free encoding step is defined as follows:
Input: message M of bitlength Mlen
Output: M' of bitlength Mlen + 128
This section defines an escalating MD-strengthening padding scheme to account for minimizing additional blocks for small messages, and expanding length encoding for larger messages. Additionally it allows for compliance with existing applications of MMO hashing defined in ZigBee Smart Energy 1.0. For messages less than 2^16 bits we use MD-strengthening-1, for messages of length less than 2^32 bits but greater than 2^16 - 1 bits we use MD-strengthening-2, and for messages of length less than 2^64 bits but greater than 2^32 - 1 bits we use MD-strengthening-3
Input: A message M of bitlength Mlen.
Output: M' = M_1, M_2, ..., M_m a padded message in 128-bit blocks.
Input: A message M of bitlength Mlen.
Output: M' = M_1, M_2, ..., M_m a padded message in 128-bit blocks.
Input: A message M of bitlength Mlen.
Output: M' = M_1, M_2, ..., M_m a padded message in 128-bit blocks.
We describe the basic MMO construction on a message M that has been padded and MD-strengthened to be of length a multiple of the bit length of AES, 128 bits.
Input: A message M of bitlength Mlen.
Output: H = H_m as the hash value.
At this time SuiteE does not recommend a particular key derivation function (KDF) for compliance. That said, some of the SuiteE primitives do require use of a KDF. One possible choice are the pseudorandom function-based constructions of KDFs given in [NIST-800-108] which are suitable, and may be instantiated with AES-CMAC as a pseudo-random function.
We will assume basic familiarity with Elliptic Curve Cryptography (ECC) notation and specifications. Wherever possible we will refer to freely available standards and indicate alignment of these standards with other well known standards. We will assume the notation in the Standards for Efficient Cryptography Group SEC 1, [SEC1]. This specification defines the basic ECC operations as well as the most widely standardized and used techniques. The overall goal of [SEC1] is to provide a free standard that ensures conformance with other standard specifications, and is instructive to implementers on how to develop the necessary routines to build an elliptic curve cryptosystem.
Elliptic curve cryptography is a natural public key technology to select given a goal of providing public key operations at a 128-bit security level on embedded systems. ECC, like RSA and other public key cryptosystems provides security by the use of key pairs: a private key and a public key. Security properties are built upon the assumption that the private key is securely generated and maintained within the confines of a cryptographic boundary. Ideally, this means that private keys should be generated on the device in which the private keys will be used operationally.
RSA key generation at the 128-bit security level requires the generation 1536-bit prime numbers, and performing integer operations on 3072-bit numbers. The inability of embedded systems to generate these keys on devices today, and the future requirements to implement this in hardware makes RSA a poor choice.
ECC key generation at the 128-bit security level requires the generation of a 256-bit random number and scalar point multiplication, which can be done efficiently in embedded systems today.
Elliptic curves over binary fields have a distinct advantage over elliptic curves over prime fields in that they are more efficient and cost effective in hardware. The binary curve sect283k1 as specified in [SEC2] is the most widely standardized and specified binary curve at the 128-bit security level. It is a Koblitz curve, which has an advantage over random curves in performing point multiplication algorithms.
For a basic description of the algorithms the reader is referred to [SEC1]. For a more complete background and optimizations for elliptic curves the reader is referred to [HMV04].
Throughout the following sections on elliptic curve cryptography we will use the following notation
Fq - is a finite field with q elements.
E - an elliptic curve over Fq, given by the equation y^2 + xy = x^3 + ax^2 + b.
E(Fq) - the group of elliptic curve points over Fq.
G - is a base point in E(Fq) of a large prime order.
n - is a large prime, and the order of the subgroup generated by G.
h - is the cofactor, h = #E(Fq)/n.
Further we will assume it is known how to generate elliptic curve key pairs, and will refer the reader to the freely available specification [SEC1]. In general a key pair is generated by taking a random integer d, 1 < d < n, and computing Q = dG, the addition of the point G to itself d times. In general all parties will have some assurances that the elliptic curve domain parameters are valid, and in particular are fixed to the selected sect283k1 curve parameters.
Fq - is a finite field with q = 2^283. Fq = F_2[X]/(f(x)), where f(x) = x^283 + x^12 + x^7 + x^5 + 1.
E - the elliptic curve is defined as E:y^2 + xy = x^3 + b.
G - is a base point in E of a large prime order, presented here in uncompressed octet encoding 04 0503213F 78CA4488 3F1A3B81 62F188E5 53CD265F 23C1567A 16876913 B0C2AC24 58492836 01CCDA38 0F1C9E31 8D90F95D 07E5426F E87E45C0 E8184698 E4596236 4E341161 77DD2259.
n - is a large prime, and the order of the subgroup generated by G, n = 01FFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFE9AE 2ED07577 265DFF7F 94451E06 1E163C61.
h - is the cofactor, #E(Fq)/n, h = 4.
Elliptic Curve Pintsov-Vanstone Signatures (ECPVS) is an elliptic curve variant of Nyberg-Rueppel signatures. ECPVS is standardized in [X9.92.1] and [IEEE1363-A]. It has three distinct advantages over ECDSA when it comes to constrained environments. The first being that it allows for smaller signature sizes by the incorporation of part of the message into a signature field. The second is a simplification of the integer arithmetic. The signing transformation does not require a modular inverse, improving both code size and computational performance. The verification transformation requires no integer arithmetic and so also removes a modular inverse and modular multiplies in the verification transformation. The third is that it is a Schnorr signature scheme which loosens the collision resistance requirement on the underlying hash function [NSW07]. Thus the AES-MMO hash primitive in SuiteE (see Section Section 4)is sufficient for security. A second consequence is a performance increase in the signature verification, where a scalar multiply with a 256-bit integer (ECDSA) is replaced by a 128-bit integer (ECPVS).
We assume all parties possess the domain parameters for the elliptic curve, as chosen in Section 6, and that the public keys of signers are validated as described in [SEC1], Section 3.2.2.
The scheme presented here is a variant of ECPVS as presented in [X9.92.1], it removes the redundancy requirement on the input message by replacing the use of symmetric key encryption with the authenticated encryption functionality of SuiteE, AES-CCM*.
ECPVS uses encoding and decoding routines to process signatures.
The following subsections specify the encoding and decoding operation primitives that shall be used to generate ECPVS signatures and to verify ECPVS signatures.
Input: The input to the encoding operation is:
Steps
Output: r.
We will denote this process as r = EM(M, Z), for encode message.
Input: The input to the decoding operation is:
Steps
Output: ERROR or message value M.
We will denote this process as M = EM^-1(r, Z), for decode message.
This section contains two subsections, signature generation and signature verification.
Input: The input to the signature generation transformation is:
Steps:
Output: (r, s) as the signature with partial message recovery on V.
Input: The input to verification is:
Steps:
Output: Either an ERROR, or a recovered message M and indication of a VALID signature.
In this section we specify the Elliptic Curve Qu-Vanstone implicit certificate scheme (ECQV).
A traditional certificate scheme consists of a certificate issuer with a key pair (d, Q) to produce a triplet binding an identity, I, and a public key, P, using a signature, sig, by invoking the issuer's private key d. We can represent this certificate as (I, P, sig). An implicit certificate binds an identity element with a public key without an explicit signature by creating a pair of elements; an identity, I, and a public key reconstruction value B. We can represent this certificate as (I, B).
Verification of the certificate is implicit in the use of the public key. The public key is bound to the entity identified in the implicit certificate, and the certification process ensures that only this entity may recover the associated secret key. In effect, certificate verification is combined with the cryptographic primitive for which the signed key is being used. This provides two advantages over traditional certificates. The first is a cost savings on memory and bandwidth. Implicit certificates do not require an explicit signature, reducing the size of the cryptographic material to roughly 1/3rd of a traditional certificate. The second is on computation, the public key reconstruction operation is computationally more efficient than a signature verification, and may be combined with other operations.
The next five sections describe an implicit certificate scheme, defined in [SEC4]. As in the previous section the elliptic curve domain parameters and hash functions are assumed. It is also assumed that the CA has established a key pair (dCA, QCA), and all communicating parties have access to the public key QCA.
We will assume that certificate validation routines have been established in regards to verifying certificate validity, key usage and certificate formatting. These checks will be assumed in steps in which certificate parsing takes place where possible error values may be returned.
This section describes the basic operations by which an entity A generates a certificate request. It is assumed that A and CA have an authenticated channel, but the channel may not be private.
Input: none
Steps:
Output: a key pair (kA, RA).
The entity A, requesting the certificate, sends the public key RA along with purported identity of A to the Certificate Authority, and stores (kA, RA) for future use, keeping kA secret.
This section describes the certificate generation process executed by a certificate authority. It is assumed that A and CA have an authenticated channel, but the channel may not be private.
Input: the following items or equivalent
Steps:
Output: Either an implicit certificate CertA, and private key contribution value r, or an ERROR value.
This section describes the certificate reception process by which a certificate requester computes its private key.
Input: the following items or equivalent
Steps:
Output: Either a key pair (dA, QA), or an ERROR value.
This section describes the certificate public key reconstruction operation. This would be done by any entity desiring to authenticate a cryptographic operation with entity A.
Input: the following items or equivalent
Steps:
Output: Either an alleged public key QA, or an ERROR value.
We say the output is "alleged" since the party that extracted it does not at this point know that it belongs to the party identified in CertA. However, the scheme does guarantee that only the identified party possesses the secret key associated to QA.
The elliptic curve MQV, or ECMQV scheme is a key agreement scheme based on ECC. We give a description here, but will refer to [SEC1] as the definitive normative reference. ECMQV can provide a variety of security properties and we refer the reader to [NIST-800-56] to use an instantiation of ECMQV that best satisfies their application security goals. We select ECMQV for SuiteE because of its well studied security properties, wide standardization, existing deployment in the constrained environment space and the computational and bandwidth savings it can provide over competing methods to provide an authenticated key agreement scheme.
As in previous ECC sections we will assume all parties have agreed upon and access to validated elliptic curve parameters, and for the purpose of SuiteE this is the sect283k1 curve as defined in [SEC2].
This section defines the basic operations of the ECMQV primitive. We will assume the two communicating parties A and B have established two key pairs (dA1, QA1) and (dA2, QA2), and (dB1, QB1) and (dB2, QB2) respectively. The description is presented from A's reference point, B would perform the same operations with analogous key pairs. The first of each public key may be a static public key derived from an implicit certificate and used to authenticate the entity.
Input: The following or equivalent
Steps:
Output: Shared secret key K of klength, or an ERROR value.