[Cryptography-dev] Thoughts on opaque key material.

[Alex Stapleton]

Individually I don't think these issues are much of a problem but their 
combination does sound like it needs addressing.

1) This mostly seems like a documentation issue. If we expose these values 
anywhere in our API we must document them, even if we hide them inside some 
backend specific API. Perhaps we can give these values lower priority in 
the docs and guide people towards the operations somehow?

2) There are 2 problems here. First are HSMs which provide only opaque 
handles to work on keys. Yet they also often provide APIs for loading 
existing keys into them. We still need to expose the individual key 
parameters to write keys to them. If we only support generating keys inside 
the HSM then we can avoid this to some extent, I suspect we will always 
need access to *public* key material though.

The 2nd problem is APIs like CC which only provide DER encoded keys to the 
user. This makes implementation annoying for sure. Fortunately we currently 
have one mandatory backend that is fully capable of translating those DER 
keys, OpenSSL. There is not yet any good reason not to use it for this 
purpose. If we do make OpenSSL optional then working with raw DER for key 
structures isn't impossible and we seem to have some more in depth X.509 
plans in progress anyway.

3) The problem is not that CRT is optional. The problem is that not 
everyone uses PKCS#1. OpenPGP uses a different formulation of CRT, OpenSSH 
regenerates CRT values on demand in places etc. Now certainly some backends 
might not care about the CRT values we store. They are rare but maybe we 
should still accommodate them? It seems like we should actually identify 
them first. Currently all backends on our to do list have a strong 
preference for the use of CRT.

4) Having investigated this issue in some depth we certainly have a small 
timing side channel on conversion in the OpenSSL backend. I'm not confident 
this is actually a serious danger though. IIRC the side channel leaks a 
small amount of information about the sum of the number of 1 bits in each 
part of the key, on Python 2.7.

The main slowness is in the constant reallocation of the internal key 
structures. Abandoning our current API seems like a rather severe 
optimisation to me. Until the opaque key idea came up our leading solution 
to this problem was caching the backend internal representation on the key 
objects. I don't think there's anything blocking us from implementing that?

So it seems like there's still a lot of different problems mixed up here.

1) Our documentation has too much emphasis on key material. We can fix this 
by writing better docs.

2) Implicit key conversion may be a security issue and is "slow". We can 
fix this within the current API.

3) Insistence on PKCS#1 for RSA. We have taken some steps to make this 
easier for users. I expect we will find application specific corner cases 
regardless of representation here. IMO this is best solved at the protocol 
library and documentation level.

4) Opaque backends. We can use OpenSSL to translate the key for them or 
just get down to adding more in depth ASN1 support in general.

5) We don't have a good plan for HSMs. We should definitely address this 
directly. I think they will inherently require their own interfaces though. 
I would support splitting our current interfaces into *Material and 
*Operations in anticipation of an HSM backend. We could do this easily 
today without huge API impacts but multi backend should continue to require 
a *Material key.

I do have concerns that multi backend will turn into a complexity tar pit 
but so far it hasn't been too horrible.



On 22 April 2014 00:15:34 David Reid <dreid at dreid.org> wrote:

> I apologize for how disorganized these thoughts are, the problems are more
> fully formed than
> the solutions and I ended up spending much more time than desired writing
> this email, so I just sort of cut myself off at 4pm.  Hopefully we can
> figure out some of these answers on the mailing list.
>
> --
>
> Currently RSA key material is represented as an object having a series of
> properties that correspond to the various mathematical components of an
> RSA key.
>
> The initial reasoning for this is that it would make the internal
> representation of a key backend independent and allow for moving key
> material from one backend to another (for example, loading the key from one
> backend and performing encryption with another backend).
>
> However, as an initial proponent of this argument I feel comfortable saying
> that I was completely wrong.  It has variety of negative effects,
>
> 1) The mathematical components have terrible names that we MUST expose to
>    users.  In RSA n, p, q, e, and d.  In ECDSA x and y.
>
>    Even when these components have well known multisyllable names their
> value
>    as descriptors is somewhat limited, "public exponent" is a much better
> name
>    than "e" but still requires knowledge of the mathematical foundations of
>    RSA to be of any value to anyone.  (You can argue that the
>    hazmat/primitives layers are the place for exposing this kind of detail
> to
>    users and that if you don't understand the RSA mathematically you
> shouldn't
>    be using them, however we've never felt any need to point out that AES
>    S-boxes can be described by a system of 23 quadratic equations in 80
> terms.)
>
> 2) Not all backend representations of keys expose the individual components.
>
>    Even given a single backend such as openssl there is no guarantee that
>    two internal structures will contain all the necessary data.  This is
>    most notable with keys stored in a HSMs or SmartCards where it is a
> feature
>    that you can not extract the RSA private key from the system.
>
>    However this is also evident in backends like CommonCrypto which don't
> have
>    a public API for getting or setting the values of the various key
>    components.  To actually use an RSA key from OpenSSL on CommonCrypto you
>    MUST convert it to some intermediate representation that both understand
>    (likely PKCS#8).
>
> 3) Optional optimizations get exposed to users as required interface.
>
>    Similarly, our exposure of the Chinese remainder theorem intermediate
>    calculations on the RSAPrivateKey interface complicates the usage of RSA
>    key material on multiple backends instead of simplifies it.  Not all
>    serialization formats or backends support storing/loading the CRT values
>    potentially requiring us to perform duplicate calculations of these
> values
>    for exposing them on the nonopaque interface.
>
> 4) Using the generic key components makes frequent operations (like
> obtaining
>    a new signing/verify context) more expensive.
>
>    These backend specific operations now require potentially costly (or even
>    dangerous) conversions between the generic and backend
>    specific representations.
>
>
> Given these issues I think we must seriously consider switching away from
> these backend independent representations as our primary interface to key
> materials.  Preferring instead opaque backend specific implementations.
>
> For example, instead of a concrete RSAPrivateKey instance which can be
> instantiated with the underlying components, I imagine all key generation
> and
> loading being mediated by backends and resulting in objects that provide
> much
> more narrow interfaces organized around what you can do with a key (instead
> of
> what a key intrinsically is).  For example, when generating an RSA key on
> the
> openssl backend you would get back an object which provides a basic
> interface
> indicating that it is an RSA key, that has some basic attributes for key
> size, and accessing the public key object, then methods for obtaining
> backend
> specific contexts for performing signing/verification and
> encryption/decryption operations.
>
> In addition to those basic operations the object may provide any number of
> backend specific serialization methods, potentially including "serializing"
> the
> key to something similar to the current interface (which we can think of as
> a
> bag of bignums).
>
> In this way we can facilitate converting between backend specific key
> representations through a process of serialization/deserialization (in many
> cases through a formal specification such as PKCS#8).
>
> -David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/cryptography-dev/attachments/20140422/2145b9f7/attachment.html>