[Cryptography] Transactional software updates

[Phillip Hallam-Baker]

(Also posted to SUIT which is a proposed IETF WG on the topic, I
thought it might be of interest here).


I don't know about you, but I am fed up of the time it takes for
software updates on my desktop. First the update has to be downloaded
and then it has to be installed. Why can't this be instantaneous?

What I would like is to download the software update and then tell the
O/S to simply overlay the update on top of the file system as an
atomic operation. So installing a software update takes a millisecond,
no more.

Rolling back a software update is just a matter of telling the O/S to
stop applying the overlay.

It seems to me that this sort of capability would be very useful at
the device level as well. Even more so as the chief concern in any
software update scheme is that you end up bricking a device. Building
the ability to roll updates forwards and backwards is powerful.

I would also like this to be integrated into software signing and in
an intelligent fashion so that the signature encompasses both the code
and the data and it is possible to validate components independently.


There is of course going to be a cost and it is the need for storage.
The traditional file system organization is a response to highly
constrained storage. I have not yet fully considered space
optimizations because I have been thinking about the constrained
device but I think my approach could be modified for a fairly
constrained device. My approach is not going to be appropriate for
your PIC controllers but it is definitely feasible at the Arduino
level and above.

My approach is based on a Merkle Tree based container format. This may
sound intimidating but it shouldn't be. I designed, documented and
implemented the scheme in under a week:

https://tools.ietf.org/html/draft-hallambaker-jbcd-container-00

or in HTML with diagrams at

http://prismproof.org/Documents/draft-hallambaker-jbcd-container.html


The draft describes a container format that consists of a sequence of
variable length chunks that has the property that the sequence can be
traversed with equal efficiency in the forward and reverse directions.
This can optionally be indexed via a binary tree to allow random
access to any frame in log(n) time. Chain and (Merkle) tree digests
may be constructed which may be signed.

Each frame consists of a header and an optional payload. The payload
may be encrypted and/or signed using JOSE. The only fixed requirement
for the header encoding is that frame 0 has to have a header encoded
in JSON (for interop). The code supports use of JSON, JSON-B, JSON-C
and ASN.1 for header encoding, the container uses JSON-B frame
encoding because it has to support the read in either direction
property.

The original concept here was to provide an append only container
format that could be used as the basis for synchronizing Mesh portal
logs between nodes and also as an encryption format for end-to-end
encrypted Web sites. Static content is straightforward, but people
expect to be able to support applications like Web forums. The idea
was to see if we could support a Web forum run on a cloud server that
does not have the ability to read any of the content (yes).

The authentication scope is intentionally limited to the payloads, and
the signature parameters. The headers are not authenticated which
allows them to be mutable. A device may store the whole update as a
single file or break it apart into attachments. The latter approach
making garbage collection of unused attachments possible without a
separate sweep/collect cycle.


I am not sure that the encryption capability is needed for software
update but it might turn out to be useful allowing devices to be
shipped with code for a wide range of applications and only enabling
the specific modules required. I do not like devices to have more code
than is necessary for their purpose. Authentication is obviously
necessary.

The way I would see this applied to software update is that the
device/desktop would download and verify the incremental updates as a
background task (when bandwidth permits). It would then request user
permission to apply the update (if required) and set a flag internally
telling the loader to use the new version in place of the old. Any
processes that needed to be restarted would be restarted.

This could be used to effect updates across multiple devices at the
same time. It could also allow support for features such as testing
the configuration and performing an automatic rollback if the test
failed.


Besides providing a more secure process, this provides a better user experience.

The code required to support the container format is comparable to
that required to implement a SHA-2 or the like. implementation in a
TPM or such would be entirely feasible.