Re: Subject Key Attestation Evidence "light" - Invention Disclosure

Russ Housley <housley@vigilsec.com> Fri, 19 September 2008 15:12 UTC

Return-Path: <owner-ietf-smime@mail.imc.org>
X-Original-To: ietfarch-smime-archive@core3.amsl.com
Delivered-To: ietfarch-smime-archive@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 5F4E13A69A7 for <ietfarch-smime-archive@core3.amsl.com>; Fri, 19 Sep 2008 08:12:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -101.414
X-Spam-Level:
X-Spam-Status: No, score=-101.414 tagged_above=-999 required=5 tests=[AWL=-0.818, BAYES_00=-2.599, J_CHICKENPOX_26=0.6, J_CHICKENPOX_46=0.6, MSGID_FROM_MTA_HEADER=0.803, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id QzC5io0tn8aY for <ietfarch-smime-archive@core3.amsl.com>; Fri, 19 Sep 2008 08:12:11 -0700 (PDT)
Received: from balder-227.proper.com (properopus-pt.tunnel.tserv3.fmt2.ipv6.he.net [IPv6:2001:470:1f04:392::2]) by core3.amsl.com (Postfix) with ESMTP id 176B53A67EF for <smime-archive@ietf.org>; Fri, 19 Sep 2008 08:12:10 -0700 (PDT)
Received: from balder-227.proper.com (localhost [127.0.0.1]) by balder-227.proper.com (8.14.2/8.14.2) with ESMTP id m8JEsSqh059599 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Fri, 19 Sep 2008 07:54:28 -0700 (MST) (envelope-from owner-ietf-smime@mail.imc.org)
Received: (from majordom@localhost) by balder-227.proper.com (8.14.2/8.13.5/Submit) id m8JEsSwX059597; Fri, 19 Sep 2008 07:54:28 -0700 (MST) (envelope-from owner-ietf-smime@mail.imc.org)
X-Authentication-Warning: balder-227.proper.com: majordom set sender to owner-ietf-smime@mail.imc.org using -f
Received: from woodstock.binhost.com (woodstock.binhost.com [8.8.40.152]) by balder-227.proper.com (8.14.2/8.14.2) with SMTP id m8JEsGoC059569 for <ietf-smime@imc.org>; Fri, 19 Sep 2008 07:54:27 -0700 (MST) (envelope-from housley@vigilsec.com)
Message-Id: <200809191454.m8JEsGoC059569@balder-227.proper.com>
Received: (qmail 26073 invoked by uid 0); 19 Sep 2008 14:51:48 -0000
Received: from unknown (HELO THINKPADR52.vigilsec.com) (96.255.143.50) by woodstock.binhost.com with SMTP; 19 Sep 2008 14:51:48 -0000
X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9
Date: Fri, 19 Sep 2008 10:25:03 -0400
To: Anders Rundgren <anders.rundgren@telia.com>, ietf-smime@imc.org
From: Russ Housley <housley@vigilsec.com>
Subject: Re: Subject Key Attestation Evidence "light" - Invention Disclosure
In-Reply-To: <00e101c91a2b$e2481320$82c5a8c0@arport2v>
References: <00e101c91a2b$e2481320$82c5a8c0@arport2v>
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"; format="flowed"
Content-Transfer-Encoding: 8bit
Sender: owner-ietf-smime@mail.imc.org
Precedence: bulk
List-Archive: <http://www.imc.org/ietf-smime/mail-archive/>
List-ID: <ietf-smime.imc.org>
List-Unsubscribe: <mailto:ietf-smime-request@imc.org?body=unsubscribe>

Please file a formal IPR statement on the IETF web site, especially 
if you believe that this invention is related to any RFC or 
Internet-Draft.  The URL for IPR statements is: 
https://datatracker.ietf.org/ipr/about/

Thanks,
   Russ

At 03:46 AM 9/19/2008, Anders Rundgren wrote:

>The following may be prior art, or be common knowledge. It may
>even be a bad idea.  However, the publishing was only done
>in order to thwart possible future IPR claims.  If the principle
>is already patented, I would appreciate more information
>if possible.  The concept described is primarily intended for usage
>with mobile phones having embedded crypto hardware which should
>be the majority within 5-10 years from now, since crypto hardware is
>close to a requirement for making secure operating systems.
>In case you find the mail version hard to read, there is a PDF with
>the same content available:
>http://webpki.org/papers/keygen2/SubjectKeyAttestationEvidence-light__InventionDisclosure.pdf
>
>The decribed scheme is an intrinsic part of the KeyGen2 universal
>key-provisioning protocol:
>http://webpki.org/papers/keygen2/keygen2-key-attestation-1.pdf
>
>SKAE "light" - Invention Disclosure
>------------------------------------
>
>Background
>=========
>
>In some cryptographic systems, asymmetric key-pairs may be
>internally generated in Security Elements (SEs), like Smart Cards.
>For on-line (remote) provisioning of keys to SEs, there is a whish
>by CAs to be able to securely verify that the public key part
>they receive for inclusion in a certificate, indeed was (together
>with its private counterpart), generated inside of a "genuine" SE.
>
>To support this requirement the TrustedComputingGroup's (TCG's)
>Trusted Platform Module (TPM) V1.2 specification features a
>mechanism known as Subject Key Attestation Evidence (SKAE).
>
>Prerequisite: The SE contains an embedded private key and a
>matching public key certificate identifying the SE in some way that
>makes sense for CAs.  The private key is used for signing evidence
>attestations regarding generated key-pairs.
>
>Problem: If the embedded private key of the SE is also to be usable
>for other cryptographic operations, a "hacked" software environment
>could exploit this by creating unprotected key-pairs externally and
>still be able providing CAs with genuine-looking attestation
>evidences.  TCG's solution to this problem is based on the use
>of dedicated key attest keys, specific X.509 certificate extensions,
>and potentially also relying on multiple CA roots.  Although
>working, this scheme appears unnecessary complex for supporting
>a single-purpose key.
>
>Solution
>======
>
>The following steps describe how a simpler form of SKAE,
>purely based on cryptography, could be implemented in an SE.
>
>First you need to restrict the SE key-certifying private key from being
>able to perform unformatted ("blank") RSA decryption
>operations through direct API calls to the SE.
>
>You MAY still allow the key-certifying key creating standard
>PKCS #1 signatures which are useful for many purposes including
>authentication and message integrity.  Encryption operations using
>the public key MAY also be supported.
>
>To support SKAE, the proposal is to create a unique variant of PKCS #1
>signatures that must only be generated during key-generation.
>Such a signature MAY also be created if the SE is explicitly invoked with
>a previously generated public key, unless that would lead
>to key-reuse vulnerabilities.
>
>A unique variant of PKCS #1 could in its simplest form be implemented
>through the use of a non-standard padding pattern.  The hash
>algorithms to use would still be the existing SHA-1 etc.  A verifier
>should then be able to securely distinguish between standard
>signatures and SKAE signatures.  A nonce option would also be
>suitable for inclusion in the signature packet.   On the next pages,
>there is a sample program in Java implementing the proposed
>SKAE scheme.
>
>Although this scheme only describes PKCS #1 (RSA) keys, the
>principles are presumable applicable to other asymmetric key types as
>well including ECDSA.
>
>One might consider the proposed solution as a standards-defying
>"kludge", but the fact is that all current SKAE schemes rely on very
>specific generation and validation code.
>
>The primary target for this invention are mobile phones which are
>likely to be fitted with secure hardware fairly soon, since this
>is more or less a requirement for other purposes as well, most
>notably for Operating System integrity protection.
>
>Side Effect: PoP Becomes Redundant
>==========================
>
>It seems that a properly designed SKAE scheme makes
>Proof of Possession (PoP) signatures like in CRMF (RFC 4211)
>redundant which is an advantage because combining PoP
>signatures with PIN-code provisioning introduces fairly
>awkward state-handling in SEs since the generated private
>key typically must be used before it is fully provisioned.
>
>Anders Rundgren, WebPKI.org, September 15, 2008
>
>Author's address:
>Storbolsäng 50
>740 10 Almunge
>Sweden
>
>Email: anders.rundgren@telia.com
>
>---------------------------------------------------------------------
>
>
>import javax.crypto.Cipher;
>
>import java.security.GeneralSecurityException;
>import java.security.MessageDigest;
>import java.security.PublicKey;
>import java.security.PrivateKey;
>import java.security.KeyPair;
>import java.security.KeyPairGenerator;
>
>import java.security.interfaces.RSAKey;
>
>/**
>  * SKAE (Subject Key Attestation Evidence).  The following J2SE 
> compatible code is meant illustrate
>  * the use of SKAE signatures.
>  */
>public class skae
>   {
>     static final String SHA_1            = "SHA-1";
>
>     static final String UNFORMATTED_RSA  = "RSA/ECB/NoPadding";
>
>     static final byte[] PS_END_SEQUENCE  = new byte[] {(byte)0x00, 
> (byte)'S',  (byte)'K',  (byte)'A',  (byte)'E'};
>
>     static final byte[] DIGEST_INFO_SHA1 = new byte[] {(byte)0x30, 
> (byte)0x21, (byte)0x30, (byte)0x09, (byte)0x06,
>                                                        (byte)0x05, 
> (byte)0x2b, (byte)0x0e, (byte)0x03, (byte)0x02,
>                                                        (byte)0x1a, 
> (byte)0x05, (byte)0x00, (byte)0x04, (byte)0x14};
>
>
>     /**
>      * Create an SKAE package for signing or verification
>      * @param rsa_key The certifying (attesting) private or public key.
>      * @param certified_public_key The certified (attested) key.
>      * @param optional_nonce An optional "nonce" element.
>      * @return The SKAE package.
>      */
>     public static byte[] createSKAEPackage (RSAKey rsa_key,
>                                             PublicKey certified_public_key,
>                                             byte[] optional_nonce)
>     throws GeneralSecurityException
>       {
> 
>////////////////////////////////////////////////////////////////////////////////////////
>         // To make it feasible securely distinguishing standard 
> RSASSA-PKCS1.5 signatures     //
>         // from SKAE signatures the latter are packaged in a 
> different way which should       //
>         // create errors if processed by a crypto library that does 
> not support SKAE.         //
>         // The following shows the packaging differences in 
> detail.                           //
>         // 
>                            //
>         // EMSA-PKCS1-v1_5: EM = 0x00 || 0x01 || PS || 0x00 || 
> T                              //
>         // 
>                            //
>         // EM-PKCS1-SKAE:   EM = 0x00 || 0x01 || PS || 0x00 || 'S' 
> || 'K' || 'A' || 'E' || T  //
> 
>////////////////////////////////////////////////////////////////////////////////////////
>         byte[] modulus = rsa_key.getModulus ().toByteArray ();
>         int k = modulus.length;
>         if (modulus[0] == 0) k--;
>         byte[] encoded_message = new byte [k];
>         encoded_message[0] = (byte)0;
>         encoded_message[1] = (byte)1;
>         MessageDigest md = MessageDigest.getInstance (SHA_1);
>         if (optional_nonce != null)
>           {
>             md.update (optional_nonce);
>           }
>         byte[] hash = md.digest (certified_public_key.getEncoded ());
>         int i = k - 2 - PS_END_SEQUENCE.length - hash.length - 
> DIGEST_INFO_SHA1.length;
>         int j = 2;
>         while (i-- > 0)
>           {
>             encoded_message[j++] = (byte)0xff;
>           }
>         i = 0;
>         while (i < PS_END_SEQUENCE.length)
>           {
>             encoded_message[j++] = PS_END_SEQUENCE[i++];
>           }
>         System.arraycopy (DIGEST_INFO_SHA1, 0, encoded_message, j, 
> DIGEST_INFO_SHA1.length);
>         System.arraycopy (hash, 0, encoded_message, j + 
> DIGEST_INFO_SHA1.length, hash.length);
>         return encoded_message;
>       }
>
>
>
>    /**
>      * Verify an SKAE signature
>      * @param skae_signature The signature to be verified.
>      * @param certifying_public_key The certifying (attesting) public key.
>      * @param certified_public_key The certified (attested) key.
>      * @param optional_nonce An optional "nonce" element.
>      * @throws GeneralSecurityException if the signature is invalid 
> or indata is incorrect.
>      */
>     public static void verifySKAESignature (byte[] skae_signature,
>                                             PublicKey certifying_public_key,
>                                             PublicKey certified_public_key,
>                                             byte[] optional_nonce)
>     throws GeneralSecurityException
>       {
>         Cipher cipher = Cipher.getInstance (UNFORMATTED_RSA);
>         cipher.init (Cipher.ENCRYPT_MODE, certifying_public_key);
>         byte[] received_signature_package = cipher.doFinal (skae_signature);
>         byte[] reference_signature_package = createSKAEPackage 
> ((RSAKey)certifying_public_key,
> 
>certified_public_key,
> 
>optional_nonce);
>         if (reference_signature_package.length != 
> received_signature_package.length)
>           {
>             throw new GeneralSecurityException ("Signature package 
> length error");
>           }
>         for (int i = 0; i < received_signature_package.length ; i++)
>           {
>             if (received_signature_package[i] != 
> reference_signature_package[i])
>               {
>                 // A more comprehensive diagnostic would be preferable...
>                 throw new GeneralSecurityException ("Signature 
> package content error");
>               }
>           }
>       }
>
>
>     public static class GeneratedKey
>       {
>         PublicKey certified_public_key;
>         PublicKey certifying_public_key;
>         byte[] skae_signature;
>       }
>
>
>     public static class SecurityElement
>       {
>         PublicKey certifying_public_key;
>
>         private PrivateKey certifying_private_key;
>
>         public SecurityElement () throws GeneralSecurityException
>           {
>             /////////////////////////////////////////////////////////////////
>             // Key-certifying keys are typically created once during       //
>             // device manufacturing. The public key part is also most      //
>             // likely distributed in an X.509 certificate issued by a CA   //
>             // setup specifically for certifying crypto hardware.          //
>             // That is, the following lines are just for showing the       //
>             // cryptography, without any infrastructural considerations.   //
>             /////////////////////////////////////////////////////////////////
>             KeyPairGenerator certifier = 
> KeyPairGenerator.getInstance ("RSA");
>             certifier.initialize (2048);
>             KeyPair certifying_key_pair = certifier.generateKeyPair ();
>             certifying_public_key = certifying_key_pair.getPublic ();
>             certifying_private_key = certifying_key_pair.getPrivate ();
>           }
>
>
>         /**
>          * Create a certified key-pair.
>          * @param size The size of the RSA key.
>          * @param optional_nonce An optional "nonce" element.
>          * @return A container with a generated public key and 
> attesting signature.
>          */
>         public GeneratedKey generateCertifiedKeyPair (int size, 
> byte[] optional_nonce)
>         throws GeneralSecurityException
>           {
>             /////////////////////////////////////////////////////////////////
>             // Generate a new key-pair in the Security Element.  The       //
>             // private key is presumably stored securely in hardware and   //
>             // never leave its container, unless "sealed" by the latter.   //
>             /////////////////////////////////////////////////////////////////
>             KeyPairGenerator kpg = KeyPairGenerator.getInstance ("RSA");
>             kpg.initialize (size);
>             KeyPair new_key_pair = kpg.generateKeyPair ();
>
>             /////////////////////////////////////////////////////////////////
>             // Now let the Security Element attest that the new key-pair   //
>             // actually was created inside of the Security Element.        //
>             //                                                             //
>             // NOTE 1: The Security Element MUST NOT expose an API that    //
>             // allows unformatted RSA decryptions like used below to be    //
>             // performed with the key-certifying key, otherwise "malware"  //
>             // could easily create fake attestations for any externally    //
>             // supplied key-pair!                                          //
>             //                                                             //
>             // NOTE 2: Due to the fact that SKAE signatures are only to    //
>             // be created for generated keys, the key-certifying key MAY   //
>             // also be used for creating ordinary PKCS1.5 signatures for   //
>             // things like authentications and securing message integrity  //
>             /////////////////////////////////////////////////////////////////
>             GeneratedKey gk = new GeneratedKey ();
>             gk.certified_public_key = new_key_pair.getPublic ();
>             Cipher cipher = Cipher.getInstance (UNFORMATTED_RSA);
>             cipher.init (Cipher.DECRYPT_MODE, certifying_private_key);
>             gk.skae_signature = cipher.doFinal (createSKAEPackage 
> ((RSAKey)certifying_private_key,
> 
>gk.certified_public_key,
> 
>optional_nonce));
>             gk.certifying_public_key = certifying_public_key;
>             return gk;
>           }
>       }
>
>
>     public static void main (String[] args) throws Exception
>       {
>
>         /////////////////////////////////////////////////////////////////
>         //                                                             //
>         //                     CLIENT Operations                       //
>         //                                                             //
>         // It is assumed that the critical operations are performed    //
>         // inside of the Security Element, otherwise attestations      //
>         // would not be more trustworthy than the environment where    //
>         // the Security Element is actually running in!                //
>         /////////////////////////////////////////////////////////////////
>         SecurityElement se = new SecurityElement ();
>
>         /////////////////////////////////////////////////////////////////
>         // Generate a new key-pair in the Security Element.  The       //
>         // private key is presumably stored securely in hardware and   //
>         // never leave its container, unless "sealed" by the latter.   //
>         /////////////////////////////////////////////////////////////////
>         byte[] nonce = null; // Didn't use a nonce in the sample run
>         GeneratedKey gk = se.generateCertifiedKeyPair (1024, nonce);
>
>         /////////////////////////////////////////////////////////////////
>         //                                                             //
>         //                     VERIFIER Operations                     //
>         //                                                             //
>         // The certifying public key is supposed to be transferred to  //
>         // the verifier by some kind of protocol, together with the    //
>         // SKAE-signature, certified public key, and the optional      //
>         // nonce.  A nonce (if used) would preferably be created by    //
>         // the verifier during an earlier (not shown) protocol phase.  //
>         /////////////////////////////////////////////////////////////////
>         verifySKAESignature (gk.skae_signature,
>                              gk.certifying_public_key,
>                              gk.certified_public_key,
>                              nonce);
>
>         System.out.println ("The SKAE signature appears to be valid!");
>       }
>
>   }