Subject: [Anima] Pinning of raw public keys in Constrained Vouchers

From: Michael Richardson <[email-masked]>
Date: Sun, 26 May 2019 22:50:43 -0400

I've been trying to improve the text to better explain pinning of registrar keys
(rather than certificates), in order to resolve
   https://github.com/anima-wg/constrained-voucher/issues/18

and also to remove as many bytes on the wire required to do constrained
enrollment, the question came up.  The registrar identity crosses
the wire three times!

1) the registrar sends it's identity (whether raw public key or
   certificate) during the DTLS or EDHOC handshake,

2) the pledge sends the registrar's identity in the voucher-request (signed),

3) then the MASA sends the registrar's identity in the voucher (signed).

Couldn't we send a hash of identity in (2) and (3), and to do this we need a
new element in the constrained voucher.  This I've given the mouthful name
of:  proximity-registrar-sha256-of-subject-public-key-info
and: pinned-sha256-of-subject-public-key-info
(knowing that the YANG->SID process will turn this into a small integer).

A sha256 hash is 32-bytes in size.
A 256-bit ECDSA key is about 32-bytes in size.
An equivalent 2048-bit RSA key is 256 bytes in size.
So the hash only wins if we use bigger ECDSA keys, or if we use RSA.
(okay, so there are a few bytes for the subject-public-key-info (SPKI) wrapping,
which also provides algorithm agility)

We could truncate the hash if we felt this was still secure enough
We could add the length of the thing (the RPK) being hashed if that would
help with pre-image attacks, but that's mostly already there in the SPKI
encoding, but I suppose an attacker might find a way to prepad with nonsense
DER.

Please help me decide if this is a useful thing to do.
If it's useful, is it useful enough to drop the pinned-domain-subject-key-info?

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Jim Schaad <[email-masked]>
Date: Sun, 26 May 2019 20:54:13 -0700

> -----Original Message-----
> From: Michael Richardson <[email-masked]>
> Sent: Sunday, May 26, 2019 7:51 PM
> To: [email-masked]
> Cc: Esko Dijk <[email-masked]>; Jim Schaad
> <[email-masked]>; Göran Selander <[email-masked]>
> Subject: Pinning of raw public keys in Constrained Vouchers
> 
> 
> I've been trying to improve the text to better explain pinning of
registrar
> keys (rather than certificates), in order to resolve
> enrollment, the question came up.  The registrar identity crosses the wire
> three times!
> 

Fixing on a single hash function would probably be frowned upon by the IESG.
The lack of algorithm flexibility would be an issue.

> (okay, so there are a few bytes for the subject-public-key-info (SPKI)
> wrapping, which also provides algorithm agility)
> 
> We could truncate the hash if we felt this was still secure enough We
could
> add the length of the thing (the RPK) being hashed if that would help with
> pre-image attacks, but that's mostly already there in the SPKI encoding,
but I
> suppose an attacker might find a way to prepad with nonsense DER.

As I remember things:

* Adding the random value would make the collision resistance attack simpler
for the registrar.  It has some random bytes that do not have to have any
structure to create two different public keys with the same hash value.
* Adding the random value might make a second pre-image attack more
difficult, but I doubt it.  You have more bytes as input, but that is
generally not the biggest issue for finding a second pre-image collision.
* You don't care about pre-image resistance if you are making the input
public.

Generally, one would want to person doing the signing to add the random
bytes to make the collision resistance attack harder.  However, as one would
need to transport the random bytes this would not make things better.

I cannot speak to the level of security that is required for your solution.
However, strength is directly related to the size of the hash value.  

Jim

---

From: Michael Richardson <[email-masked]>
Date: Mon, 27 May 2019 10:30:16 -0400

>> (knowing that the YANG->SID process will turn this into a small integer).

    jim> Fixing on a single hash function would probably be frowned upon by the IESG.
    jim> The lack of algorithm flexibility would be an issue.

So extending to other hash functions is just a question of amending the YANG.
There aren't hundreds of hash functions, and SID values should provide space
for at least 30 code points here.   Perhaps explaining how the algorithms can
be agile in the Security Considerations.

    >> suppose an attacker might find a way to prepad with nonsense DER.

    jim> As I remember things:

    jim> * Adding the random value would make the collision resistance attack simpler
    jim> for the registrar.  It has some random bytes that do not have to have any
    jim> structure to create two different public keys with the same hash
    jim> value.

Sorry, do you mean, simpler for an attack on the registrar?

I'm saying that the subject-public-key-info starts with an
AlgorithmIdentifier, which is a sequence.  An attacker could add additional
items to the sequence in order to make a second pre-image attack (usually
that requires additional bytes, changing the length of the item).
This depends upon the victim verifier ignoring the extra bytes somehow; a
Postel Principle parser might do that, and if I were building a pull-parser
for this, I might do that.

In practice, most constrained implementations avoid DER parsing by accepting
a known sequence of bytes for the subject-public-key-info and use memcmp().
I.e. they are extremely conservative in what they accept, to the point of
violating the specification one could argue.

    jim> * Adding the random value might make a second pre-image attack more
    jim> difficult, but I doubt it.  You have more bytes as input, but that is
    jim> generally not the biggest issue for finding a second pre-image
    jim> collision.

    jim> * You don't care about pre-image resistance if you are making the input
    jim> public.

What do you mean by the part about public?
Yes, in DTLS 1.2, the certificates are visible, and an active attacker can
see them.

    jim> I cannot speak to the level of security that is required for your solution.
    jim> However, strength is directly related to the size of the hash value.

We make certificates by doing sha256 hashes of the subject-public-key-info
and other names, and having the CA sign that.  I think that it makes no sense
to truncate the hash going into a 256-bit sized signature, since ECDSA signs
256-bit values.   I am not sure how to evaluate the strengh required here.
It's a CBOR value, so it has a length, and I suppose we could define a way to
truncate the value in a standard direction, and then decide later.

I think that a non-truncated hash ought to be as strong as sending the key
itself, and having two code paths is not a win here.

---

From: Jim Schaad <[email-masked]>
Date: Mon, 27 May 2019 11:12:25 -0700

> Sent: Monday, May 27, 2019 7:30 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; 'Esko Dijk' <[email-masked]>; =?iso-8859-
> 1?Q?'G=F6ran_Selander'?= <[email-masked]>
> Subject: Re: Pinning of raw public keys in Constrained Vouchers
> 
> 
>     >> new element in the constrained voucher.  This I've given the
mouthful
> name
>     jim> Fixing on a single hash function would probably be frowned upon
by
> the IESG.
We
>     >> could
>     >> add the length of the thing (the RPK) being hashed if that would
help
> with
>     jim> * Adding the random value would make the collision resistance
attack
> simpler
>     jim> for the registrar.  It has some random bytes that do not have to
have
> any

No, I mean a simpler attack by the registrar.  

> I'm saying that the subject-public-key-info starts with an
AlgorithmIdentifier,
> which is a sequence.  An attacker could add additional items to the
sequence
> in order to make a second pre-image attack (usually that requires
additional
> bytes, changing the length of the item).
> Postel Principle parser might do that, and if I were building a
pull-parser for
> this, I might do that.

Given that this is a DER encoded item, there is no way for a victim to
ignore the extra bytes inside of the SPKI structure.   If it does then then
it is completely incorrectly doing the parsing.  You would not even be able
to have trailing bytes that might or might not be part of the SPKI object.
Even if you did BER indefinite length encoding, you would not be able to
ignore the extra bytes, but you would have bytes to play with as you can
have different encodings that represent the same output value.  

> 
> In practice, most constrained implementations avoid DER parsing by
> accepting a known sequence of bytes for the subject-public-key-info and
use
> memcmp().

 I don't know that I would say that this is a violation of the spec.  You
are saying does this match what I expect to see and since it is DER a memcmp
is a fine way to do this.  The issue here would be that you need to make
sure that you have correctly identified the border of the SPKI in the
containing object.  That is, you cannot put in extra bytes in the
surrounding object and do the memcmp based on the size in memory rather than
the size in the PDU.

> Yes, in DTLS 1.2, the certificates are visible, and an active attacker can
see
> them.

Yes that is what I mean.  There is no issue about the attacker getting the
hashed bytes from the hash structure.  There are some cases where the
content is not available to the attacker and doing an inversion is what is
desired.  An example of this is creating key values from passwords.

> truncate the value in a standard direction, and then decide later.

The first sentence has me slightly worried.  Is the CA computing the hash or
is the hash being provided to the CA?  

> itself, and having two code paths is not a win here.

One attack is a birthday attack.  This is O(2^(n/2)) in terms of inputs to
be evaluated.  That is if you compute 2^(n/2) hash values you have a 50/50
chance of finding a collision.  This means that it takes 2^128 attempts for
a 256-bit hash value, but only 2^64 for a 128-bit hash value, even if you
truncate as SHA-256 value to 128 bits rather than using a 128-bit hash
function (such as AES-CBC).   The idea that 64-bit authentication values are
fine is the current thinking in the CoRE and ACE groups as that is the size
of authentication value that is being used for encryption of items.  Part of
this is based on the assumption that these values are only of interest for
short term and not historically.  TLS on the other hand is worried about
long term (i.e. recorded for later use) and thus has gone with longer
authentication values as a general rule.  In COSE we are saying that a
truncated hash is fine for identifying certificates, but that is operating
as a filter rather than an identifier.

Jim

---

From: Michael Richardson <[email-masked]>
Date: Wed, 29 May 2019 11:37:11 -0400

Jim Schaad <[email-masked]> wrote:
    jim> As I remember things:
    jim> * Adding the random value would make the collision resistance attack
    jim> simpler for the registrar.  It has some random bytes that do not
    jim> have to have any structure to create two different public keys with
    jim> the same hash value.

    > No, I mean a simpler attack by the registrar.

Yes, I'd call it the malicious registrar.

The attack would take an existing (nonceless) voucher that pinned the device
to a specific registrar, and then try to create a registrar with a keypair
that hashes the same.  This would be used for offline registrars.
If we pin the public key then this can not happen.

    > have different encodings that represent the same output value.

Are we are agreeing, but using different terms?
So yes, an attacker could resort to non-DER encoding (BER encoding) to give it
bytes to play with. That would be non-DER though.
My reading of the ASN.1 is that one could include arbitrary additional parameters
in the algorithm SEQUENCE, (correctly DER encoded) and use those bytes to do
the pre-image attack... except that it would fail because constrained devices
are using memcmp().

    >> use memcmp().

    jim> I don't know that I would say that this is a violation of the spec.  You
    jim> are saying does this match what I expect to see and since it is DER a memcmp
    jim> is a fine way to do this.

well, because it locks the list of parameters to be 0.

AlgorithmIdentifier  ::=  SEQUENCE  {
        algorithm               OBJECT IDENTIFIER,
        parameters              ANY DEFINED BY algorithm OPTIONAL  }

Perhaps we have never extended any, but the extension point is right here.

    >> and other names, and having the CA sign that.  I think that it makes no
    >> sense to truncate the hash going into a 256-bit sized signature, since
    >. ECDSA signs 256-bit values.   I am not sure how to evaluate the strengh required here.

    > is the hash being provided to the CA?

I think that in traditional CA processing, we provide the public key (in a
CSR) to the CA, and it computes the hash.   My point here is that if we were
concerned (as I concern myself above) with pre-image attacks against sha256
under signature, then we should be concerned about certificates, period :-)

I think that we can also intelligently advise pledge to carefully check
the DER encoding is minimal, and using memcmp() works very well here.
Stupider implementation wins here :-)

    > as a filter rather than an identifier.

I have not paid enough attention to the HMAC algorithms in COSE... just
reading rfc8152.  Truncated to 64-bits.  Hmm.  We wouldn't have a keyed-hash,
just a hash, which makes it more vulnerable to off-line dictionary attacks I
think.
But, I think you are perhaps referring to the kid usage?

In online uses of the voucher, it has a limited time when it is useful,
and in the online usage, there is also a freshness nonce.  So it seems that
we could truncate the hash efficiently.  It would be inappropriate to
generate off-line nonceless (constrained) vouchers with this method,
but I think that is something we can write down intelligently.

--
]               Never tell me the odds!                 | ipv6 mesh networks [
]   Michael Richardson, Sandelman Software Works        |    IoT architect   [
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: Jim Schaad <[email-masked]>
Date: Wed, 29 May 2019 09:30:29 -0700

> Sent: Wednesday, May 29, 2019 8:37 AM
> Cc: [email-masked]; 'Esko Dijk' <[email-masked]>;
'=?iso-8859-
> 1?Q?'G=F6ran_Selander'?=' <[email-masked]>
attack
> to a specific registrar, and then try to create a registrar with a keypair
that
> hashes the same.  This would be used for offline registrars.
> So yes, an attacker could resort to non-DER encoding (BER encoding) to
give
> it bytes to play with. That would be non-DER though.
> My reading of the ASN.1 is that one could include arbitrary additional
> parameters in the algorithm SEQUENCE, (correctly DER encoded) and use
> those bytes to do the pre-image attack... except that it would fail
because
> constrained devices are using memcmp().

No - there are constraints on what can occur in the ANY field (1988 syntax)
that are defined by the OID of the algorithm.  Thus while the structure
allows for arbitrary additional parameters, they are restricted by the
algorithm to a single (usually absent or NULL) value.

>     jim> are saying does this match what I expect to see and since it is
DER a
> memcmp

This is the syntax that I normally use:

AlgorithmIdentifier{ALGORITHM-TYPE, ALGORITHM-TYPE:AlgorithmSet} ::=
        SEQUENCE {
            algorithm   ALGORITHM-TYPE.&id({AlgorithmSet}),
            parameters  ALGORITHM-TYPE.
                   &Params({AlgorithmSet}{@algorithm}) OPTIONAL
        }

Which shows that the extension point is restricted and not completely open.
Use the DER sequence requires that this be checked correctly.

> 
>     >> We make certificates by doing sha256 hashes of the
subject-public-key-
> info
>     >. ECDSA signs 256-bit values.   I am not sure how to evaluate the
strengh
> required here.
>     >> It's a CBOR value, so it has a length, and I suppose we could
define a
> way to
>     > The first sentence has me slightly worried.  Is the CA computing the
hash
> or
the DER
> encoding is minimal, and using memcmp() works very well here.
>     >> I think that a non-truncated hash ought to be as strong as sending
the
> key
>     > function (such as AES-CBC).   The idea that 64-bit authentication
values
> are
> reading rfc8152.  Truncated to 64-bits.  Hmm.  We wouldn't have a keyed-
> hash, just a hash, which makes it more vulnerable to off-line dictionary
> attacks I think.

Look at the hash draft not the RFC -
https://datatracker.ietf.org/doc/draft-ietf-cose-hash-algs/
> In online uses of the voucher, it has a limited time when it is useful,
and in
> the online usage, there is also a freshness nonce.  So it seems that we
could
> truncate the hash efficiently.  It would be inappropriate to generate
off-line
> nonceless (constrained) vouchers with this method, but I think that is
> something we can write down intelligently.

I would want to read the result, but I think this would be correct.

Jim