Subject: [Mathmesh] UDF Design notes

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 13 Aug 2019 12:49:02 -0400

Discussing:

http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

I try to avoid giving explanations in documents that contain normative text
as this can be a source of ambiguity. So I will try to summarize the design
concerns here.

The original starting point was the need for a 'better PGP fingerprint'. In
particular, I wanted a digest representation that was:

* Reasonably compact in both printed and voiced form.
* Supported use of SHA2
* Could be expressed at varying precision as the application needs demanded
* Could be upgraded to make use of new algorithms if absolutely necessary
* Could be input via a keyboard
* Could be compared for equality
* Could be used to create a fingerprint of any type of data (not just keys)
* Support use in QR codes, DNS labels, etc.

After a while I quickly realized I would also need to ensure that

* UDFs could not be confused with OpenPGP fingerprints
* A UDF of a key could not be confused with a UDF of a document or
executable

This led to the construct described in the document, i.e.

* A binary UDF is an octet stream in which the first octet describes the
digest algorithm used to create it.
* The binary UDF is canonically presented in BASE32

The choice of Base32 comes from the observation that fingerprints are
frequently read out aloud and having to distinguish case makes the process
tedious and error prone. So it cant be Base64 but Base32 gives us five bits
per char instead of four.

The Type Identifiers for SHA-2 and SHA-3 are chosen so as to cause the
first letter of a SHA-2 digest to always be an M (for Merkle-Damgard and to
remind us of the Rivest/MD5 legacy) and tthe first letter of a SHA-3 digest
will always be a K for Keccak.

I have tried various groupings of digits and ended up choosing 4 because it
makes the code least complex.

A UDF content digest is a digest of a typed content sequence. First
the Content Digest Value (CDV) is determined by applying the digest
algorithm to the content data:

CDV = H(<Data>))

Then the Typed Content Digest Value (TCDV) is determined by applying the
digest algorithm to the content type identifier and the CDV:

TCDV = H (<Content-ID> + ‘:’ + CDV)

The reason for this two step process is that while there are tens of
thousands of content types in use, 99% of documents out there are of less
than 50 content types. So if we have a fingerprint of a file and we are not
sure what content type was intended, we can check the 50 most likely
content types as quickly on a 1GB file as on a 1KB file.

Finally, I started seeing that people have Bitcoin addresses of the form
faceb-ookds-lkjh or whatever. Pretty kewl huh, the first letters of my key
tells you who owns it?

Erm no, what people have done there is provide a new attack vector because
most people will only remember the first ten digits of an address at most
and this mnemonic is encouraging people to assume from memory. Anyone who
wants to impersonate the above, just needs to search for a public key whose
first eight digits match and they will probably trick enough people to be
interesting.

So I decided to encourage people not to do this and then thought, what if
they could have a shorter fingerprint that was just as strong.

There is IETF precedent for this as Christian Huitema (ccd) can explain.
There is unfortunately a patent to Microsoft. It is not clear that the MSFT
patent covers my approach however and since they allowed a royalty free
etc. license in the past, they might well in this instance.

Having developed a spec for content digests, I quickly realized that my
code was also generating a number of ASCII outputs that look like UDF
fingerprints but were not content digests. So I decided to assign code
points for the following:

* Nonces (N)
* Encryption keys (E)
* MAC results (A)
* Shamir Secret Share (S)

These are the features I use in the Mesh and so I have a fairly good
understanding of at least a partial set of requirements. But it is not
necessarily a complete list.

The two use cases that I am most tempted to add are representations for
public and private key literals.

PRO: One spec fits all.
CON: Even 25519 keys are long do we read them out over the phone? Perhaps
we should consider Base64?

I have not decided on this yet and I don't have a use case. But I might
when I get to thinking about TLS SNI encryption type things. I currently
have two possible ways forward.

The first is to add a Type indicator PKIX (112 = P)  which would be
followed by a PKIX KeyInfo block. This would be encoded in Base32. This
would look something like this for an Ed25519 key:

PB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4-SAQQ-RY7F-Q7UU-URHU-VCDB-HALY-LNCG

The second would be to do the above in Base64 but use a type indicator that
gives an initial letter in Base64:

x-Z4lAx9fFvhzLO3a9RHGDPgtcwapxVCo_XdlAj1s1CPI

I have no strong vies on this either way.

---

From: Michael Richardson <[email-masked]>
Date: Wed, 14 Aug 2019 19:45:13 -0400

> * Support use in QR codes, DNS labels, etc.

I think that this was a rather ambitious set of requirements :-)

    > per char instead of four.

I agree with your use.
I wonder if we can train people not to need to mention the case as they
compare.  I should look again if you specify upper-case only.

    > will always be a K for Keccak.

This was very cute.

    > they could have a shorter fingerprint that was just as strong.

Interesting observation.

    > we should consider Base64?

No, but being able to scan QR codes with public keys is important.
DPP needs/uses this already.

    > would look something like this for an Ed25519 key:

On the subject of Subject Key Identifier, which you have created a MIME type,
RFC7469, section 2.4 also gets close to this.

    > gives an initial letter in Base64:

I don't think that reading base64 over the phone will ever be a thing.
Validating (visually) that a QR scan worked right will be a thing.
I prefer to keep it all in base32.

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

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 15 Aug 2019 13:09:08 -0400

> I think that this was a rather ambitious set of requirements :-)

Unless the requirements actually conflict, I would much rather make a
decision for a reason even if it is not a very strong one than flip a coin.

I don't have strong feelings on whether we should group the characters in
blocks of 4, 5 or 3/5 or whatever.

> compare.  I should look again if you specify upper-case only.

I am aiming for case insensitive because case is lost in a lot of contexts.
The QR code spec specifies upper case (I think) but the tools almost
invariably convert to lower.

>     > will always be a K for Keccak.

The design constraint was that the fingerprints must not start with a hex
digit so that UDF and PGP fingerprints remain distinct.

> DPP needs/uses this already.

If you want QR codes of the public keys, that would probably mean we should
go for Base32. I would have to actually try it out but I think it turns out
that Base32  maps onto the supported QR code encodings more efficiently
than Base64.

> I prefer to keep it all in base32.

That is certainly my preference. I will add it into the draft once I have
the sync bug I am chasing sorted. Given the existing code, I think I can
probably hammer it out in a few hours because the code I use to take
fingerprints of public keys is already using the PKIX keyinfo format.

Lets break this out into a separate thread. Can you suggest the data flow?
I am assuming here that this is so I can make a secure connection to a
device over WiFi without Internet connectivity so the connection mechanism
described in the doc isn't exactly going to work :).

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 15 Aug 2019 18:23:34 -0400

OK so here is an Ed25519 key (including the algorithm identification OID) :

OAYC-4MAH-AYBS-WZLQ-AUAA-GIYA-AQQE-E7UO-6QMY-7EGD-C63V-TROP-P2W5-HX6E-IDBE-YVJW-B4SY-GM5U-T2LF-7HQ

Presented in a QR code, we can drop the separators:
OAYC4MAHAYBSWZLQAUAAGIYAAQQEE7UO6QMY7EGDC63VTROPP2W5HX6EIDBEYVJWB4SYGM5UT2LF7HQ

The QR code is reasonably compact either way.

I added this to the draft and pushed the new version:
http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

---

From: Michael Richardson <[email-masked]>
Date: Thu, 15 Aug 2019 20:32:28 -0400

Phillip Hallam-Baker <[email-masked]> wrote:
    > Lets break this out into a separate thread. Can you suggest the data
    > flow?  I am assuming here that this is so I can make a secure
    > connection to a device over WiFi without Internet connectivity so the
    > connection mechanism described in the doc isn't exactly going to work
    > :).

DPP is https://www.wi-fi.org/discover-wi-fi/wi-fi-easy-connect and
google can find you a copy of the document if you don't like their form.
It is already defined.

I am extending it in draft-richardson-anima-smarkaklink-01.

I don't think that I (or Wi-Fi Alliance) have the opportunity to change to
UDF at this point.

Where I think it might still be useful is where the goal is not WiFi
onboarding, but rather a proximity authorization.
For instance, getting access to the thermostat or TV in a hotel room. 
You won't get ownership, rather you'll get authorization to do some stuff.

Some devices won't have screens that can display the QR code, and
instead, a QR code will be printed on paper an attached.  Yes, they will
need to be changed regularly, but maybe UDF can help here.

Being able to type the UDF into a computer, and/or read it over the phone
would have some advantages, although I'm hard pressed to come up with a
non-TV-computer-security-plot-theatre situation where that makes sense.

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