Subject: [saag] Blockchained log format

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 11 Sep 2017 09:01:51 -0400

​I now have the Mesh at a point where we can use it for real applications.
While working on writing application protocols, I noticed that a large
number of applications have at their center a structure which is
essentially just a sequence of entries that are 'mostly' append only.

For example, a contacts file is a sequence of contacts, a bookmarks file a
sequence of bookmarks, etc. etc. Even a mail spool or comments to a blog
post, they all fit the same format.

​It seems to me that it would be rather useful to have a cryptographic file
format that supported this type of interaction with confidentiality and
integrity protections plus the ability to do incremental updates, to merge
updates from two different logs that have got out of sync and the ability
to read the file in forward and reverse directions - the most interesting
information is usually at the end.

I am looking at using at a JSON style encoding with some binary extensions
as follows.

The file consists of a header and a list of entries.

The header contains a Jose structure with the cryptographic keying material
for the rest of the file. This is the place where the public keys are
specified, key exchange set up, etc.

The list of entries consists of a sequence of frames. Each frame has the
structure:

<Length> <data> <R-Length>

The Length format follows the usual self describing approach and can be 1,
2, 4 or 8 bytes in length. The R-Length is the length in reverse order and
MUST be exactly the same as the Length value or the file is declared
corrupt. The R-Length value allows the log to be read in reverse order.
Thus if we have a mail spool with 1 million entries, we can just read the
last 200 by starting at the end and working back.

This approach means that the size of the frame has to be known when it is
written out. It is not possible to stream inside a frame but a stream may
be represented as a sequence of frames.

Within the frame itself, there is a structure

<Header> <Encrypted-Payload>

Each payload is encrypted under a new session key and IV.

The header contains the following as authenticated data:
* time added (used in synchronization)
* digest value of <Encrypted-Payload>
* optional blockchain value

Since we want to verify the data before unwrapping it or exposing it to
infrastructure that has the keys, the authentication has to be on the
outside and must therefore be on the encrypted data.

The payload may be signed or MAC-ed

The inclusion of an optional blockchain value allows a sequence of entries
to be authenticated using a single signature verification. It will also
make attempting to merge two sequences that have got out of sync a headache
for the person writing the code. I suspect use of these features will be
disjoint, pick one or the other.

The simplest chaining mode would be for each entry to chain to the last
digest value. A more efficient structure would be to use a Merkle tree.

Ideas? Comments?

---

From: Nick Johnson <[email-masked]>
Date: Mon, 11 Sep 2017 13:30:15 +0000

Have you considered CBOR as an alternative to inventing your own binary
encoding?

-Nick Johnson

On Mon, Sep 11, 2017 at 2:02 PM Phillip Hallam-Baker <[email-masked]>
wrote:

> ​It seems to me that it would be rather useful to have a cryptographic
> file format that supported this type of interaction with confidentiality
> and integrity protections plus the ability to do incremental updates, to
> merge updates from two different logs that have got out of sync and the
> ability to read the file in forward and reverse directions - the most
> interesting information is usually at the end.
>
>
> The header contains a Jose structure with the cryptographic keying
> material for the rest of the file. This is the place where the public keys
> are specified, key exchange set up, etc.
>
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 11 Sep 2017 13:16:39 -0400

> Have you considered CBOR as an alternative to inventing your own binary
​​Yes and rejected. JSON is the future. CBOR is intentionally different it
has a different data model. The people designing it were told that this
would be a problem but their response was 'we are doing an independent
submission, we do not have to consider your ideas or requirements'. ​

But regardless of the history, this is a new requirement and rather
different to those considered by CBOR or JSON-B. There is no way to address
the 'read from the end' requirement except by either introducing new coding
elements or using some form of escaping scheme (see JSON text sequences).

​
On Mon, Sep 11, 2017 at 9:29 AM, Alan DeKok <[email-masked]>
 wrote:

> On Sep 11, 2017, at 9:01 AM, Phillip Hallam-Baker <[email-masked]>
> wrote:
> >
> > ​I now have the Mesh at a point where we can use it for real
> applications. While working on writing application protocols, I noticed
> that a large number of applications have at their center a structure which
> is essentially just a sequence of entries that are 'mostly' append only.
>
>   My $0.02 is that such a system isn't that useful in isolation.  i.e. For
> an isolated system, it's not that hard to create the data && signatures
> post-facto.
>
>   The real value would be in adding cross-linking between the chains.
> e.g. if you have logging on multiple machines, they can periodically
> exchange hashes / states, which are incorporated into each others logs.
> This "cross-links" the logs, and ties the whole system together.  Which
> creates a "web of signatures", instead of a "web of trust".  The benefit is
> that you don't even need to trust the other systems.
>

​That is exactly how I intend to tie data elements together in the Mesh.
However I wasn't going to mention it here because my main reason for using
the signed Merkle tree is efficiency rather than non-repudiation.

​The use case I am considering here is limited to 'Alice's iPhone
authenticates the changes it has made to Alice's contacts to Alice's
desktop.' Yes, we could enroll that in a master log to prevent an insertion
attack but this attack isn't going to be possible unless Alice is already
hosed.

The idea of the Mesh is that there is some portion of Alice's profile that
is available persistently and published through an untrusted cloud called
the cryptomesh. And in that situation we definitely want to cross link the
logs held by the independent portals in some fashion.

I have not yet fully worked out how to do that but this is my current
scheme.​

There are three types of chained digest data:

1) The last link in the chain or the apex of a tree. This is a digest value

2) A digest value signed by a trusted party at some known point in time.
This is a trust Apex.
3) A set of digest values that allow a chain to be established and verified
to one or more entries. This is a digest chain.

A digest chain is useless on its own because you don't know if it is
trusted. To do that you have to specify some means of validation. So there
will be some form of description of this process which may be simple (one
trusted signer) or complex (multiple signers, quorums) or very complex
(proof of work, multiple sources, yadda yadda). But whatever the
description it must be machine readable to be useful and thus we must at
some point have something we can take a fingerprint of.

So let the UDF fingerprint of the description be:

MA72Y-WXNYF-Z4DWJ-VZBT4-TUYR6-36PIX

For routing etc. purposes, we need a domain name, so let us make a strong
name out of it:

example.com.mm--ma72y-wxnyf-z4dwj-vzbt4-tuyr6-36pix

And now we can present the digest value mdmlr-ydtlr-2gqch-li3o6-lo6is-hrx3y
as a uri:

tbs:example.com.mm--ma72y-wxnyf-z4dwj-vzbt4-tuyr6-36pix:value:mdmlr-ydtlr-2gqch-li3o6-lo6is-hrx3y

So we can use the structure I already described to present cross links to
arbitrary external chains and the means of resolution just by incorporating
them into the authenticated data.

This is not something I would normally do for a personal system but it
might be something you would use as a matter of course in a file system if
you were tracking patent application data, forensics, etc.

To make a system like this practical, you would need to have an analog of
NTP for 'current block' and likely need to distribute it down to the system
level. Which is the reason I was not bringing it up. The problem when you
mention time is that there is always someone who insists that 'synchronized
time is absolutely useless unless it is to the femptosecond level. Which is
nonsense of course. There are multiple uses for time and unless you are
doing something like logging NASDAQ transactions, chances are that you do
not need trusted time resolution that is anywhere close to the resolution
you would prefer for synchronization.

I would like all the clocks in my house to be synchronized to better than a
second and preferably better than 100ms. When I am designing a system, I am
not going to rely on the systems being synchronized to the hour.

There are layers to trust:

1) Transparent untrusted source. (Blockchain, days)
2) Accountable trusted source. (Signed NTP, minutes)
3) Unaccountable trusted source . (NTP, seconds)

​With blockchain, the trustworthiness of the data is almost zero at the
moment the block is mined (it can be overwritten) but quickly reaches near
infinite as blocks are added. Within a few days, the cost of a backdating
attack is the cost of breaking the hash. So the source is untrusted because
we don't need to trust 'em.

Signing NTP responses improves trust but introduces a performance issue. We
can't get better resolution in time than the interval between signing.
Unless we have a protocol where a nonce is signed, we only have protection
against roll forward attacks, not roll back.

---

From: Alan DeKok <[email-masked]>
Date: Mon, 11 Sep 2017 13:52:12 -0400

On Sep 11, 2017, at 1:16 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> ​That is exactly how I intend to tie data elements together in the Mesh. However I wasn't going to mention it here because my main reason for using the signed Merkle tree is efficiency rather than non-repudiation.

  I'm not clear what "efficiency" is in this context.

> ​The use case I am considering here is limited to 'Alice's iPhone authenticates the changes it has made to Alice's contacts to Alice's desktop.' Yes, we could enroll that in a master log to prevent an insertion attack but this attack isn't going to be possible unless Alice is already hosed.

  The point is to also find out when an attack occurred.  Maybe you can't trust Alice's clock because she's been attacked.  But if there are periodic cross-links, you can correlate it with other events in the mesh.

  i.e. the cross-correlation is not only non-repudiation, it's a way to ensure ordering of events, i.e. time.

> The idea of the Mesh is that there is some portion of Alice's profile that is available persistently and published through an untrusted cloud called the cryptomesh. And in that situation we definitely want to cross link the logs held by the independent portals in some fashion.

  It's a nice idea to have an untrusted cloud... the question for me is why would people use it?  For bitcoin, the answer is "to sell bitcoins to later entrants".  So there's a financial incentive.

  I'm not sure why I would put *my* data in an untrusted cloud.  Or would this scheme allow for individuals to control their data, in a way people can't do right now with "cloud" systems?

> This is not something I would normally do for a personal system but it might be something you would use as a matter of course in a file system if you were tracking patent application data, forensics, etc.
> 
> To make a system like this practical, you would need to have an analog of NTP for 'current block' and likely need to distribute it down to the system level. Which is the reason I was not bringing it up. The problem when you mention time is that there is always someone who insists that 'synchronized time is absolutely useless unless it is to the femptosecond level. Which is nonsense of course. There are multiple uses for time and unless you are doing something like logging NASDAQ transactions, chances are that you do not need trusted time resolution that is anywhere close to the resolution you would prefer for synchronization.

  Once you cross-correlate events, you can have some global order of events.  You don't need an explicit time stamp for that.  If dependent events have a fixed order, it matters less that independent events don't have a fixed order.

> I would like all the clocks in my house to be synchronized to better than a second and preferably better than 100ms. When I am designing a system, I am not going to rely on the systems being synchronized to the hour.

  I think synchronization is less important than coordination.  If each clock has it's own time (and rate of time passage), you can correct for individual variation by looking at times across multiple clocks.

  i.e. they don't need to have the *same* time, but the time differences between clocks need to be known, and bounded.

  Alan DeKok.

---

From: iang <[email-masked]>
Date: Thu, 14 Sep 2017 16:34:44 +0200

> Ideas? Comments?

First comment - I (also would) do it in binary.  I used to use text 
formats because I could read and confirm the code, but in the end, it 
was easier to be confident of a binary I/O code than text code. And when 
I added encryption, it made the text a bit useless.

Second comment - for better generality, make it two files not one, one 
being indexes and one being the frames in full.  Each index locates its 
frame in the frame file by start / length or end.

This way, you can read the entire index file into memory qiuckly, and 
then only pull in the frames on demand.

I must admit - I never thought about doing the reverse reading. Probably 
because I've always read the whole (index) thing into memory for any and 
all processing.

iang

ps; in my work, both files have the same header, more or less, and the 
header has the encryption keys in it.  A stream cipher is needed, as 
we're picking up at any point in the frame, I use Chacha and poly.