[OLPC Security] Extending theft-deterrence to support delegation.

[C. Scott Ananian]

This is a proposal to extend the current activation/theft-deterrence
formats and protocols to support delegation. Connectivity to our
deployments is not good enough in practice to support mandatory
connections to antitheft.laptop.org in order to support passive or
active kill functionality. Daily activation and active-kill authority
needs to be delegated to schoolservers (or even to a teacher's XO)
in order to be practical. Further, the mechanism must work even if
no online connection can ever be made by the XO or XS to OLPC's
upstream servers.

Further discussion:
http://lists.laptop.org/pipermail/security/2008-June/000436.html

Activation delegation
---------------------
The first step is to introduce delegation into the activation lease
format. The idea here is that OLPC will generate a 'delegate'
activation lease, which says that, until the expiration time of the
delegate lease, a specified keypair will be able to activate the
machine. For example:

OLPC signs: "delegate activation until 2009-01-1 to keyid ABCDEF"
schoolserver w/ keyid ABCDEF daily signs: "activate machine until tomorrow"

The durations of each of these leases can be varied to trade off trust
in the schoolserver and the "market window" a thief has to sell the
machine before the activation expires. For example, in places with
less risk of theft the school server might generate weekly or monthly
leases for the machines in the classroom, or it might generate longer
leases before weekends, vacations, etc. If theft of a schoolserver is
a concern, the top-level delegation to the schoolserver might be
monthly; if the schoolserver is adequately protected by its own
passwords the delegation might be yearly or "infinite".

The same basic mechanism can work with an arbitrary chain of
delegations. Each signature in the chain takes ~2s to check, and
adds that amount of time to every boot. Excessive chain length
should thus be avoided, but a three-level hierarchy such as:

OLPC signs: "delegate activation 'forever' to Uruguay Min. Ed."
Uruguay Min. Ed. signs: "delegate activation for the year to school#XXXX"
School daily #XXXX signs: "activate until tomorrow"

might be reasonable for some deployments. In particular, this
structure would allow the country to manage the assignment of laptops
to school servers without the involvement of OLPC's activation service.

Technical implementation:
-------------------------
The existing activation lease and developer key formats are defined by:
http://wiki.laptop.org/go/Firmware_Key_and_Signature_Formats
We add a new disposition type, 'D', to the activation lease and
developer key formats. The 'D' character should be immediately
followed by a space and then a 64-byte keyid in both the activation
lease and developer key formats. We also change the version identifier
to '02' for leases and keys with this disposition. A complete
delegated lease looks like:

act02: SHF12345678 D aa<60>aa 20090101T000000Z sig01: sha256 bb<60>bb 7<510>7
key01: 88<474>aa<60>aa
act01: SHF12345678 K 20081201T000000Z sig01: sha256 aa<60>aa 9<510>9

I have used the notation <N> to indicate that N characters were elided
from a field in this example. The bb<60>bb keyid corresponds to the
public key held by OLPC. The aa<60>aa keyid in this example is the
public key held by the schoolserver.

The signed data for act02/dev02 includes '<disposition>:<keyid>' where
the act01/dev01 formats have the substring '<disposition>' in the
signed data.

Note that the existing signature and key formats are newline
terminated. Since I am trying to make the smallest possible changes
to the existing formats, the result is effectively a three-line lease.
I would encourage these lines to be kept together to allow efficient
checking and easier separation of leases from a concatenated file, but
in order to give ourselves future flexibility there shouldn't be any
required ordering of the three lines.

Absent firmware changes, OFW will ignore discard all three of the
lines of this activation lease (the first two because the format is
new, and the third because the keyid is not known to OFW) and invoke
the activation code in the initial ramdisk. This activation code can
correctly parse the lease and proceed with the boot process.

Firmware support would be needed to support the equivalent delegation
mechanism for developer keys. This functionality is less critical;
OLPC should be routinely generating developer keys for all laptops
manufactured, and since developer keys do not expire the delegation
mechanism is not as useful. It could be argued that adding delegation
to developer keys is needless complexity and should be omitted.

Theft-deterrence protocol delegation
------------------------------------
The theft-deterrence protocol
http://wiki.laptop.org/go/Theft_Deterrence_Protocol
already provides a delegation mechanism. However, the mechanism was
designed to include a request of the 'top-level' antitheft protocol at
every query to confirm the delegation. The mechanism for delegating
blacklists management to one server, updates to another, and lease
renewal to a third is adequate but clumsy, requiring chaining the
delegations between the multiple servers.

The simplest workable extension to the delegation mechanism is to add
an "expiration time" field to the delegate response. This allows
future requests to bypass the top-level OLPC service until the
expiration time is reached.

Avoiding the first-boot ping of the top-level service is accomplished
by specifying that a special file named '/security/delegate.json' will
be interpreted to contain an initial response from the top-level
server. It must be signed by the top-level server. The nonce in this
request should be the sha256 hash of the string "<SN>:<UUID>" for the
machine. The /security/delegate.json file should be deleted after it
is processed.

Delegating the theft-deterrence protocol confers authority to
designate a given laptop 'stolen' or not. A local blacklist can be
maintained on the schoolserver in cases where connectivity is
inadequate to support distribution of a central blacklist.

Secure reflash delegation
-------------------------
Uruguay has expressed concern about the ability to bypass their
security system by, for example, installing Peru's build on their
machines using the secure reflash mechanism. I believe the
fundamental issue here is solved by standardizing on this core
security functionality across all deployments, so that Peru's build
does not grant permissions denied by Uruguay's build. But the
critical issue of protecting the root user on the machine remains:
if Uruguay locks down root to prevent clock-resetting attacks, but
Peru does not, then reflash can be used to gain root. Whatever
protections are enforced by reflash must also be enforced by
olpc-update.

One proposal is to specify that a special file 'lock.key' in the
/security directory on NAND be used to specify that, in addition to
the usual fs.zip signatures, a valid signature by the key specified by
lock.key is required in order to perform reflash or olpc-update. As
long as only root is able to write/erase /security/lock.key, the
desired protection can be accomplished.

Alternatives
------------
The mechanism described here extends the act01 and dev01 formats. An
alternative would be to extend the sig01 format to support
arbitrarily-chained signatures. The expiration time and possibly
serial-number binding would have to be moved into the signature format
in that case, but this alternative might allow OLPC to uniformly
delegate all the signed objects in the security system. It is not
clear whether this is a workable mechanism in practice for things like
kernel signatures, but it might suffice to allow a schoolserver to
proxy for the upstream antitheft.laptop.org service. In fact, the
delegation mechanism for the theft-deterrence protocol could be
effectively replaced by simply directing the query first to the
schoolserver (perhaps via DNS redirection by the schoolserver), and
only querying upstream if the schoolserver is unable to provide an
acceptably-signed response using its delegated authority. [I may
attempt to explore this alternative in a future email.]

A different alternative is to simply change the trusted keypairs in
the firmware, os, ramdisk, secure reflash, and theft-deterrence/update
code, effectively creating multiple separate domains of authority for
each major deployment. This doesn't solve the necessity of delegating
daily activation authority to a school server, unless either all
school servers share a key pair, or else the build is customized for
each school.

A more limited version of this alternative is to simply allow for
customization of the secure-reflash keypair in firmware for each
deployment. This accomplishes the aims of secure reflash delegation
with minimal collateral damage.

-----------

Comments requested. Is there a way to accomplish our aims with less
work or more generality? Are there security implications I'm not
thinking of? Does this pass the Mitch Bradley sniff test?
--scott

[C. Scott Ananian]

As promised, here's an alternative which only touches the sig01
signature format. I think I prefer this; let me know if you agree.
--scott

------------------------------------
This is an alternate version of the previous proposal, which
concentrates its changes on one part of the security system: the sig01
signature format. By introducing a delegation/chaining mechanism into
signatures, all parts of our security system which involve signatures
can be delegated.

Format details
--------------

We propose a 'sig02' signature format, as follows:

sig02: hashname_1 key-or-keyid_1 expiration_1 data_1 hashname_2 ...\n
3 2 2 6 1 N/64 1 16 1 M 1 ... 1

The "hashname key expiration data" section is repeated as many
times as there are signatures in the chain. We will call each
repetition an 'sg' below. So the contents of a sig02 are:

* The literal string "sig"
* The two digit version number ("02")
* A colon
* A space
At least one sg, consisting of:
* A six character name for the hash function used by this signature
o "sha256" indicates that this is an RSASSA-PSS signature
using SHA256 as the hash and MGF1-SHA256 as the mask function.
o "rmd160" indicates that this is an RSASSA-PKCS1-v1_5 signature
using RIPEMD-160 as the hash function.
* A space
* At least 64 characters of key data in the key01 format. The
characters must be a suffix of the full key data; if more than
64 characters are present they are assumed to be the full key.
o 64 characters is sufficient to include the exponent and
the least significant bytes of the modulus
o it is recommended that only keyid_1 be abbreviated.
* A space
* An ISO 8601 UTC expiration time in basic format (no dashes or
colons) and no fractional seconds. (eg: "20070816T173500Z").
After this time, the sg must no longer be considered valid.
o The string "00000000T000000Z" indicates that the given
sg never expires.
* The signature data as a hexadecimal-encoded string. The encoded data
is the octet string given by section 8.1.1/8.2.1 of RSA PKCS #1,
version 2.1. The data to be signed is described below.
* A space (if this sg confers a delegation) or a newline
(terminating the signature chain).

The sig02 line validates a byte string called the 'certified
data'. For the final sg in the line, the 'data' field is a
signature of the certified data using the keypair specified in the
sg. For all other sgs, the 'data' field is a signature of the string:
<next keyid>:<serial number>:<expiration time>
where key_1 is used to sign a string containing key_2, key_2 signs a
string containing key_3, etc. Each delegation is bound to a specific
laptop serial number (which should be the same if the signature is to
be meaningful).

A sig02 with delegation is formed by concatenating the signature
of specific certified data onto a prefix of sgs which confer
authority. A sig02 without delegation is identical to the sig01
format, except for the additional expiration time field.

Validating a file containing sig01 and sig02 signatures starts by
scanning the file for sig01 and sig02 signatures with an initial
'keyid' matching a trusted keypair. For a sig02, we then validate
each sg in turn until we reach the final sg, which should validate
against the certified data.

Uses
----
Since the act01 lease format and dev01 key format incorporate a
signature, they can be delegated by simply using the sig02 signature
format instead of sig01.

Kernels, ramdisks, and secure-reflash signatures can be delegated in
the same way, but these signatures will are bound to a specific
serial number. This will probably make this mechanism less useful.

The theft-deterrence protocol can be delegated by simply redirecting
the requests from antitheft.laptop.org to the school server, possibly
via DNS redirection. The school server will include a delegated
signature in its response, which gives it authority to answer for a
specific delegated laptop. If the school server is not authoritative
for a given laptop, it can relay the request to an upstream service if
it has connectivity.

No special initialization is necessary to inform the laptop that its
theft-deterrence responses will be delegated.

As before, current OFW releases ought to ignore 'sig02' signatures,
which will punt activation to the initial ramdisk which can be updated
to parse & accept them. In the future, OFW can parse the sig02 format
itself, which will allow its use for developer keys, kernels,
ramdisks, and secure reflash (if these uses are valuable in practice).

[Jameson &quot;Chema&quot; Quinn]

I will analyze this further, later. However, I see one minor issue with this
proposal right away: there is no way for a key to delegate some but not all
of its authority. Thus, at every level, separate keys must be used for
separate purposes - activation, kernel, ramdisk, and secure-reflash - or all
of these permissions will be synonymous. This is totally feasible; however,
this does limit the extensible usability of this format.

I suggest that the <serial number> part of the chained signed data be
replaced by an application-specific <application>:<authorization details>
field. For example, for activation, this could be
act01:<serial number>
3 2 1 ?

This data would be global across a signature (no provision for passing
subsets of authorazation, a la spki), and would need a plaintext home in the
sig02 format.

This allows for future definitions of, for example, a kernel signature
format here, which would not have to be tied to serial number. It would also
allow for a local school server to have a single key used for signing
distinct authorizations with distinct expiration times, which seems simpler
to me (especially as you imagine the number of distinct authorization types
growing in the future).

Jameson

Post by C. Scott Ananian
As promised, here's an alternative which only touches the sig01
signature format. I think I prefer this; let me know if you agree.
--scott
------------------------------------
This is an alternate version of the previous proposal, which
concentrates its changes on one part of the security system: the sig01
signature format. By introducing a delegation/chaining mechanism into
signatures, all parts of our security system which involve signatures
can be delegated.
Format details
--------------
sig02: hashname_1 key-or-keyid_1 expiration_1 data_1 hashname_2 ...\n
3 2 2 6 1 N/64 1 16 1 M 1 ... 1
The "hashname key expiration data" section is repeated as many
times as there are signatures in the chain. We will call each
* The literal string "sig"
* The two digit version number ("02")
* A colon
* A space
* A six character name for the hash function used by this signature
o "sha256" indicates that this is an RSASSA-PSS signature
using SHA256 as the hash and MGF1-SHA256 as the mask function.
o "rmd160" indicates that this is an RSASSA-PKCS1-v1_5 signature
using RIPEMD-160 as the hash function.
* A space
* At least 64 characters of key data in the key01 format. The
characters must be a suffix of the full key data; if more than
64 characters are present they are assumed to be the full key.
o 64 characters is sufficient to include the exponent and
the least significant bytes of the modulus
o it is recommended that only keyid_1 be abbreviated.
* A space
* An ISO 8601 UTC expiration time in basic format (no dashes or
colons) and no fractional seconds. (eg: "20070816T173500Z").
After this time, the sg must no longer be considered valid.
o The string "00000000T000000Z" indicates that the given
sg never expires.
* The signature data as a hexadecimal-encoded string. The encoded data
is the octet string given by section 8.1.1/8.2.1 of RSA PKCS #1,
version 2.1. The data to be signed is described below.
* A space (if this sg confers a delegation) or a newline
(terminating the signature chain).
The sig02 line validates a byte string called the 'certified
data'. For the final sg in the line, the 'data' field is a
signature of the certified data using the keypair specified in the
<next keyid>:<serial number>:<expiration time>
where key_1 is used to sign a string containing key_2, key_2 signs a
string containing key_3, etc. Each delegation is bound to a specific
laptop serial number (which should be the same if the signature is to
be meaningful).
A sig02 with delegation is formed by concatenating the signature
of specific certified data onto a prefix of sgs which confer
authority. A sig02 without delegation is identical to the sig01
format, except for the additional expiration time field.
Validating a file containing sig01 and sig02 signatures starts by
scanning the file for sig01 and sig02 signatures with an initial
'keyid' matching a trusted keypair. For a sig02, we then validate
each sg in turn until we reach the final sg, which should validate
against the certified data.
Uses
----
Since the act01 lease format and dev01 key format incorporate a
signature, they can be delegated by simply using the sig02 signature
format instead of sig01.
Kernels, ramdisks, and secure-reflash signatures can be delegated in
the same way, but these signatures will are bound to a specific
serial number. This will probably make this mechanism less useful.
The theft-deterrence protocol can be delegated by simply redirecting
the requests from antitheft.laptop.org to the school server, possibly
via DNS redirection. The school server will include a delegated
signature in its response, which gives it authority to answer for a
specific delegated laptop. If the school server is not authoritative
for a given laptop, it can relay the request to an upstream service if
it has connectivity.
No special initialization is necessary to inform the laptop that its
theft-deterrence responses will be delegated.
As before, current OFW releases ought to ignore 'sig02' signatures,
which will punt activation to the initial ramdisk which can be updated
to parse & accept them. In the future, OFW can parse the sig02 format
itself, which will allow its use for developer keys, kernels,
ramdisks, and secure reflash (if these uses are valuable in practice).
--
( http://cscott.net/ )
_______________________________________________
Security mailing list
Security at lists.laptop.org
http://lists.laptop.org/listinfo/security

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.laptop.org/pipermail/security/attachments/20080612/f0228482/attachment-0001.htm

[C. Scott Ananian]

On Thu, Jun 12, 2008 at 4:32 PM, Jameson Chema Quinn

Post by Jameson &quot;Chema&quot; Quinn
I will analyze this further, later. However, I see one minor issue with this
proposal right away: there is no way for a key to delegate some but not all
of its authority. Thus, at every level, separate keys must be used for
separate purposes - activation, kernel, ramdisk, and secure-reflash - or all
of these permissions will be synonymous. This is totally feasible; however,
this does limit the extensible usability of this format.

For better or worse, we already have separate keys for all these
purposes. The current proposal continues with the 'one key per
function' idea.

Post by Jameson &quot;Chema&quot; Quinn
I suggest that the <serial number> part of the chained signed data be
replaced by an application-specific <application>:<authorization details>
field. For example, for activation, this could be
act01:<serial number>
3 2 1 ?

This is reasonable, but parsing an arbitrary-length field is tricky.
We tried adding a 'disposition' field to the act01 and dev01 formats
to future-proof it, but as you can see in the end we failed to
anticipate the exact direction of expansion which would be needed. In
the end, I'd prefer adding a new 'dev02' or 'act02' format if needed
to provide application-specific features, rather than add a field to
sig02 whose use is yet-unknown. Arguments to the contrary are
requested.

In actual fact, the delegations that would be useful for
kernel/ramdisk/secure reflash would be over a (quite large, and daily
changing) set of laptops. Ideas to address that are welcome, but I
suspect they won't fall under the desired 'minimal modifcation to
existing format' goals.
--scott

[Michael Stone]

I'm vaguely inclined toward the sig02 proposal. I think I need a more
complete writeup in order to offer an official opinion (e.g. with more
detailed examples of usage and a discussion of the effect on the act01
format, if any). It's sad that we have no good way to specifying groups
of serial numbers or delegation to an online S/N authority. Can we do
any better there?

Michael

[C. Scott Ananian]

Post by Michael Stone
It's sad that we have no good way to specifying groups
of serial numbers or delegation to an online S/N authority. Can we do
any better there?

I agree (this is the thrust of my response to Chema as well), but I
feel that it is likely out of scope for this release. Again, I don't
feel like we can rely on an online authority for this release, and the
offline mechanisms seem too clumsy to work well.

As a strawman: instead of a serial number in the sig02 format, we use
an md5 hash. This hash must be the exact hash of a separate file
listing serial numbers, one per line. Now we just have to maintain
these files, handle the cases where we add a laptop to the file and
now have to maintain multiple copies, name them, find them on USB
keys, etc, etc.

I'd prefer to first tackle the problem I've got a good solution for,
and defer the "arbitrary sets of serial numbers" case until we can't
do without it.
--scott

[Morgan Collett]

Post by C. Scott Ananian

Post by Michael Stone
It's sad that we have no good way to specifying groups
of serial numbers or delegation to an online S/N authority. Can we do
any better there?

I agree (this is the thrust of my response to Chema as well), but I
feel that it is likely out of scope for this release. Again, I don't
feel like we can rely on an online authority for this release, and the
offline mechanisms seem too clumsy to work well.
As a strawman: instead of a serial number in the sig02 format, we use
an md5 hash. This hash must be the exact hash of a separate file
listing serial numbers, one per line. Now we just have to maintain
these files, handle the cases where we add a laptop to the file and
now have to maintain multiple copies, name them, find them on USB
keys, etc, etc.

By md5, you meant sha-256, right? :)

Post by C. Scott Ananian
I'd prefer to first tackle the problem I've got a good solution for,
and defer the "arbitrary sets of serial numbers" case until we can't
do without it.

Morgan

[C. Scott Ananian]

On Fri, Jun 13, 2008 at 5:46 AM, Morgan Collett

Post by Morgan Collett
By md5, you meant sha-256, right? :)

I did say it was a strawman. ;-)
--scott

[Jameson &quot;Chema&quot; Quinn]

A somewhat-less strawman, to see if it sparks anyone's interest. I feel it
is not worth it.

Each link in the signature chain looks like:
hashname_1 key-or-keyid_1 expiration_1 old_gid new_gid
sig(hash(next_keyid:old_gid:new_gid:expiration_time))

confirmation goes something like this (I know you do it in C, but python is
easier for pseudocode):

valid_gids = ["sn-"+serial_number]
for hashname,keyid,expiration,old_gid,new_gid in signature_chain:
if old_gid in valid_gids:
valid_gids = valid_gids[:valid_gids.index(old_gid)]
if new_gid != valid_gids[-1]:
valid_gids += [new_gid]
else:
return invalid
....confirm signature itself....

In other words, at the beginning the valid gid is serial_number; old_gid
truncates the list of valid gids; and new_gid can extend it.

All gids could be restricted to a certain definite length.

Thus the top level signature could as-sign an xo to a certain group, and
lower level signatures could address it either as part of that group or
individually. The full signature chain would still be valid only for a given
serial number, but some links might be valid for whole groups. In theory, an
XO could keep track of its own front part (group assignments) so that it
could accept just the common tail part of a validation. Of course, unless
you could trust the root user to NEVER delete that front part by mistake,
you would have to keep a backup of each individual group assignment chain,
and so you'd lose all the advantages of this system. Also, for short
signature chains, the benefits of group assignment are small, since the
chain MUST start with a serial number and, to provide any theft deterrence,
SHOULD end with a serial number.

So IF we could trust the xos to keep their own signature chains, and IF most
signature chains were at least 3 links long, and IF there was little cost in
adding extra links in the chain just for group assignment, THEN this system
would provide marginal "benefits" in reducing the need for local school
servers to store separate validation signature chains for each of its client
XOs. Meh.

Post by C. Scott Ananian
On Fri, Jun 13, 2008 at 5:46 AM, Morgan Collett

Post by Morgan Collett
By md5, you meant sha-256, right? :)

I did say it was a strawman. ;-)
--scott
--
( http://cscott.net/ )
_______________________________________________
Security mailing list
Security at lists.laptop.org
http://lists.laptop.org/listinfo/security

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.laptop.org/pipermail/security/attachments/20080613/40477d16/attachment.htm