en/glep/glep-0058.txt

GLEP: 58
Title: Security of distribution of Gentoo software - Infrastructure to User distribution - MetaManifest
Version: $Revision: 1.4 $
Last-Modified: $Date: 2008/10/28 07:45:27 $
Author: Robin Hugh Johnson <robbat2@gentoo.org>, 
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Requires: 44, 60
Created: October 2006
Updated: November 2007, June 2008, July 2008, October 2008, January 2010
Post-History: Decemeber 2009

========
Abstract
========
MetaManifest provides a means of verifiable distribution from Gentoo
Infrastructure to a user system, while data is conveyed over completely
untrusted networks and system, by extending the Manifest2 specification,
and adding a top-level Manifest file, with support for other nested
Manifests.

==========
Motivation
==========
As part of a comprehensive security plan, we need a way to prove that
something originating from Gentoo as an organization (read Gentoo-owned
hardware, run by infrastructure), has not been tampered with. This
allows the usage of third-party rsync mirrors, without worrying that
they have modified something critical (e.g. eclasses, which are still
unsigned).

Securing the untrusted distribution is one of the easier tasks in the
security plan - in short, all that is required is having a hash of every
item in the tree, and signing that hash to prove it came from Gentoo.

Ironically we have a hashed and signed distribution (it's just not used
by most users, due to it's drawbacks): Our tree snapshot tarballs have
hashes and signatures.

So now we want to add the same verification to our material that is
distributed by rsync. We already provide hashes of subsets of the tree -
our Manifests protect individual packages. However metadata, eclasses
and profiles are not protected at this time. The directories of
packages and distfiles are NOT covered by this, as they are not
distributed by rsync.

This portion of the tree-signing work provides only the following
guarantee: A user can prove that the tree from the Gentoo infrastructure
has not been tampered with since leaving the Gentoo infrastructure.
No other guarantees, either implicit or explicit are made.

Additionally, distributing a set of the most recent MetaManifests from a
trusted source allows validation of trees that come from community
mirrors, and allows detection of all cases of malicious mirrors (either
by deliberate delay, replay [C08a, C08b] or alteration).

=============
Specification
=============
For lack of a better name, the following solution should be known as the
MetaManifest. Those responsible for the name have already been sacked.

MetaManifest basically contains hashes of every file in the tree, either
directly or indirectly. The direct case applies to ANY file that does
not appear in an existing Manifest file (e.g. eclasses, Manifest files
themselves). The indirect case is covered by the CONTENTS of existing
Manifest files. If the Manifest itself is correct, we know that by
tracking the hash of the Manifest, we can be assured that the contents
are protected.

In the following, the MetaManifest file is a file named 'Manifest',
located at the root of a repository.

---------------------------------------------
Procedure for creating the MetaManifest file:
---------------------------------------------
1. Start at the root of the Gentoo Portage tree (gentoo-x86, although
   this procedure applies to overlays as well).

2. Initialize two unordered sets: COVERED, ALL.

   1. 'ALL' will contain every file in the tree.
   2. 'COVERED' will contain every file that is mentioned in an existing
      Manifest2.

3. Traverse the tree, depth-first.

   1. At the top level only, ignore the following directories: distfiles,
      packages, local
   2. If a directory contains a Manifest file, extract all relevant local
      files from it (presently: AUX, MISC, EBUILD; but should follow the
      evolution of Manifest2 entry types per [#GLEP60]), and place them
      into the COVERED set.
   3. Recursively add every file in the directory to the ALL set,
      pursusant to the exclusion list as mentioned in [#GLEP60].

4. Produce a new set, UNCOVERED, as the set-difference (ALL)-(COVERED).
   This is every item that is not covered by another Manifest, or part
   of an exclusion list.

5. If an existing MetaManifest file is present, remove it.

6. For each file in UNCOVERED, assign a Manifest2 type, produce the
   hashes, and add with the filetype to the MetaManifest file.

7. For unique identification of the MetaManifest, a header line should
   be included, using the exact contents of the metadata/timestamp.x
   file, so that a MetaManifest may be tied back to a tree as 
   distributed by the rsync mirror system. The string of
   'metadata/timestamp.x' should be included to identify this revision
   of MetaManifest generation. Eg:
   "Timestamp: metadata/timestamp.x: 1215722461 Thu Jul 10 20:41:01 2008 UTC"
   The package manager MUST not use the identifying string as a filename.

8. The MetaManifest must ultimately be GnuPG-signed.

   1. For the initial implementation, the same key as used for snapshot
      tarball signing is sufficient.
   2. For the future, the key used for fully automated signing by infra
      should not be on the same keyring as developer keys. See [#GLEPxx+3
      for further notes].

The above does not conflict the proposal contained in GLEP33, which
restructure eclasses to include subdirectories and Manifest files, as
the Manifest rules above still provide indirect verification for all
files after the GLEP33 restructuring if it comes to pass.

If other Manifests are added (such as per-category, per first-level
directory, or protecting versioned eclases), the size of the
MetaManifest will be greatly reduced, and this specification was written
with such a possible future addition in mind.

MetaManifest generation will take place as part of the existing process
by infrastructure that takes the contents of CVS and prepares it for
distribution via rsync, which includes generating metadata. In-tree
Manifest files are not checked at this point, as they are assumed to be
correct.

--------------------------------------------------------
Verification of one or more items from the MetaManifest:
--------------------------------------------------------
There are two times that this may happen: firstly, immediately after the
rsync has completed - this has the advantage that the kernel file cache
is hot, and checking the entire tree can be accomplished quickly.
Secondly, the MetaManifest should be checked during installation of a
package.

----------------------------------------------------
Procedure for verifying an item in the MetaManifest:
----------------------------------------------------
In the following, I've used term 'M2-verify' to note following the hash
verification procedures as defined by the Manifest2 format - which
compromise checking the file length, and that the hashes match. Which
filetypes may be ignored on missing is discussed in [#GLEP60].

1. Check the GnuPG signature on the MetaManifest against the keyring of
   automated Gentoo keys. See [#GLEPxx+3] for full details regarding
   verification of GnuPG signatures. 
   1. Abort if the signature check fails.

2. Check the Timestamp header. If it is significently out of date
   compared to the local clock or a trusted source, halt or require
   manual intervention from the user.

3. For a verification of the tree following an rsync:

   1. Build a set 'ALL' of every file covered by the rsync. (exclude
      distfiles/, packages/, local/)
   2. M2-verify every entry in the MetaManifest, descending into inferior
      Manifests as needed. Place the relative path of every checked item
      into a set 'COVERED'.
   3. Construct the set 'UNCOVERED' by set-difference between the ALL and
      COVERED sets.
   4. For each file in the UNCOVERED set, assign a Manifest2 filetype.
   5. If the filetype for any file in the UNCOVERED set requires a halt
      on error, abort and display a suitable error.
   6. Completed verification

4. If checking at the installation of a package:

   1. M2-verify the entry in MetaManifest for the Manifest
   2. M2-verify all relevant metadata/ contents if metadata/ is being
      used in any way (optionally done before dependancy checking).
   3. M2-verifying the contents of the Manifest. 
   4. Perform M2-verification of all eclasses and profiles used (both
      directly and indirectly) by the ebuild.

Notes:
======
1. For initial implementations, it is acceptable to check EVERY item in
   the eclass and profiles directory, rather than tracking the exact
   files used by every eclass (see note #2). Later implementations
   should strive to only verify individual eclasses and profiles as
   needed.
2. Tracking of exact files is of specific significance to the libtool
   eclass, as it stores patches under eclass/ELT-patches, and as such
   that would not be picked up by any tracing of the inherit function.
   This may be alleviated by a later eclass and ebuild variable that
   explicitly declares what files from the tree are used by a package.

====================
Implementation Notes
====================
For this portion of the tree-signing work, no actions are required of
the individual Gentoo developers. They will continue to develop and
commit as they do presently, and the MetaManifest is added by
Infrastructure during the tree generation process, and distributed to
users.

--------------------------------------------
MetaManifest and the new Manifest2 filetypes
--------------------------------------------
While [#GLEP60] describes the addition of new filetypes, these are NOT
needed for implementation of the MetaManifest proposal. Without the new
filetypes, all entries in the MetaManifest would be of type 'MISC'.

----------------------------------------------------
Timestamps & Additional distribution of MetaManifest
----------------------------------------------------
As discussed by [C08a,C08b], malicious third-party mirrors may use the
principles of exclusion and replay to deny an update to clients, while
at the same time recording the identity of clients to attack.

This should be guarded against by including a timestamp in the header of
the MetaManifest, as well as distributing the latest MetaManifests by a
trusted channel.

On all rsync mirrors directly maintained by the Gentoo infrastructure,
and not on community mirrors, there should be a new module
'gentoo-portage-metamanifests'. Within this module, all MetaManifests
for a recent time frame (eg one week) should be kept, named as
"MetaManifest.$TS", where $TS is the timestamp from inside the file.
The most recent MetaManifest should always be symlinked as
MetaManifest.current. The possibility of serving the recent
MetaManifests via HTTPS should also be explored to mitigate MitM
attacks.

The package manager should obtain MetaManifest.current and use it to
decide is the tree is too out of date per operation #2 of the
verification process. The decision about freshness should be a
user-configuration setting, with the ability to override.

--------------------------------
MetaManifest size considerations
--------------------------------
With only two levels of Manifests (per-package and top-level), every
rsync will cause a lot of traffic transfering the modified top-level
MetaManifest. To reduce this, first-level directory Manifests are
strongly recommended. Alternatively, if the distribution method
efficently handles small patch-like changes in an existing file,
using an uncompressed MetaManifest may be acceptable (this would
primarily be distributed version control systems). Other suggestions
in reducing this traffic are welcomed.

=======================
Backwards Compatibility
=======================
- There are no backwards compatibility issues, as old versions of
  Portage do not look for a Manifest file at the top level of the tree.
- Manifest2-aware versions of Portage ignore all entries that they are
  not certain how to handle. Enabling headers and PGP signing to be
  conducted easily.

======
Thanks
======
I'd like to thank the following people for input on this GLEP.

- Patrick Lauer (patrick): Prodding me to get all of the tree-signing
  work finished, and helping to edit.
- Ciaran McCreesh (ciaranm): Paludis Manifest2
- Brian Harring (ferringb): pkgcore Manifest2
- Marius Mauch (genone) & Zac Medico (zmedico): Portage Manifest2
- Ned Ludd (solar) - Security concept review

==========
References
==========

[C08a] Cappos, J et al. (2008). "Package Management Security".
    University of Arizona Technical Report TR08-02. Available online
    from: ftp://ftp.cs.arizona.edu/reports/2008/TR08-02.pdf
[C08b] Cappos, J et al. (2008). "Attacks on Package Managers"
    Available online at:
    http://www.cs.arizona.edu/people/justin/packagemanagersecurity/

=========
Copyright
=========
Copyright (c) 2006 by Robin Hugh Johnson. This material may be
distributed only subject to the terms and conditions set forth in the
Open Publication License, v1.0.

vim: tw=72 ts=2 expandtab:
1	GLEP: 58
2	Title: Security of distribution of Gentoo software - Infrastructure to User distribution - MetaManifest
3	Version: $Revision: 1.4 $
4	Last-Modified: $Date: 2008/10/28 07:45:27 $
5	Author: Robin Hugh Johnson <robbat2@gentoo.org>,
6	Status: Draft
7	Type: Standards Track
8	Content-Type: text/x-rst
9	Requires: 44, 60
10	Created: October 2006
11	Updated: November 2007, June 2008, July 2008, October 2008, January 2010
12	Post-History: Decemeber 2009
13
14	========
15	Abstract
16	========
17	MetaManifest provides a means of verifiable distribution from Gentoo
18	Infrastructure to a user system, while data is conveyed over completely
19	untrusted networks and system, by extending the Manifest2 specification,
20	and adding a top-level Manifest file, with support for other nested
21	Manifests.
22
23	==========
24	Motivation
25	==========
26	As part of a comprehensive security plan, we need a way to prove that
27	something originating from Gentoo as an organization (read Gentoo-owned
28	hardware, run by infrastructure), has not been tampered with. This
29	allows the usage of third-party rsync mirrors, without worrying that
30	they have modified something critical (e.g. eclasses, which are still
31	unsigned).
32
33	Securing the untrusted distribution is one of the easier tasks in the
34	security plan - in short, all that is required is having a hash of every
35	item in the tree, and signing that hash to prove it came from Gentoo.
36
37	Ironically we have a hashed and signed distribution (it's just not used
38	by most users, due to it's drawbacks): Our tree snapshot tarballs have
39	hashes and signatures.
40
41	So now we want to add the same verification to our material that is
42	distributed by rsync. We already provide hashes of subsets of the tree -
43	our Manifests protect individual packages. However metadata, eclasses
44	and profiles are not protected at this time. The directories of
45	packages and distfiles are NOT covered by this, as they are not
46	distributed by rsync.
47
48	This portion of the tree-signing work provides only the following
49	guarantee: A user can prove that the tree from the Gentoo infrastructure
50	has not been tampered with since leaving the Gentoo infrastructure.
51	No other guarantees, either implicit or explicit are made.
52
53	Additionally, distributing a set of the most recent MetaManifests from a
54	trusted source allows validation of trees that come from community
55	mirrors, and allows detection of all cases of malicious mirrors (either
56	by deliberate delay, replay [C08a, C08b] or alteration).
57
58	=============
59	Specification
60	=============
61	For lack of a better name, the following solution should be known as the
62	MetaManifest. Those responsible for the name have already been sacked.
63
64	MetaManifest basically contains hashes of every file in the tree, either
65	directly or indirectly. The direct case applies to ANY file that does
66	not appear in an existing Manifest file (e.g. eclasses, Manifest files
67	themselves). The indirect case is covered by the CONTENTS of existing
68	Manifest files. If the Manifest itself is correct, we know that by
69	tracking the hash of the Manifest, we can be assured that the contents
70	are protected.
71
72	In the following, the MetaManifest file is a file named 'Manifest',
73	located at the root of a repository.
74
75	---------------------------------------------
76	Procedure for creating the MetaManifest file:
77	---------------------------------------------
78	1. Start at the root of the Gentoo Portage tree (gentoo-x86, although
79	this procedure applies to overlays as well).
80
81	2. Initialize two unordered sets: COVERED, ALL.
82
83	1. 'ALL' will contain every file in the tree.
84	2. 'COVERED' will contain every file that is mentioned in an existing
85	Manifest2.
86
87	3. Traverse the tree, depth-first.
88
89	1. At the top level only, ignore the following directories: distfiles,
90	packages, local
91	2. If a directory contains a Manifest file, extract all relevant local
92	files from it (presently: AUX, MISC, EBUILD; but should follow the
93	evolution of Manifest2 entry types per [#GLEP60]), and place them
94	into the COVERED set.
95	3. Recursively add every file in the directory to the ALL set,
96	pursusant to the exclusion list as mentioned in [#GLEP60].
97
98	4. Produce a new set, UNCOVERED, as the set-difference (ALL)-(COVERED).
99	This is every item that is not covered by another Manifest, or part
100	of an exclusion list.
101
102	5. If an existing MetaManifest file is present, remove it.
103
104	6. For each file in UNCOVERED, assign a Manifest2 type, produce the
105	hashes, and add with the filetype to the MetaManifest file.
106
107	7. For unique identification of the MetaManifest, a header line should
108	be included, using the exact contents of the metadata/timestamp.x
109	file, so that a MetaManifest may be tied back to a tree as
110	distributed by the rsync mirror system. The string of
111	'metadata/timestamp.x' should be included to identify this revision
112	of MetaManifest generation. Eg:
113	"Timestamp: metadata/timestamp.x: 1215722461 Thu Jul 10 20:41:01 2008 UTC"
114	The package manager MUST not use the identifying string as a filename.
115
116	8. The MetaManifest must ultimately be GnuPG-signed.
117
118	1. For the initial implementation, the same key as used for snapshot
119	tarball signing is sufficient.
120	2. For the future, the key used for fully automated signing by infra
121	should not be on the same keyring as developer keys. See [#GLEPxx+3
122	for further notes].
123
124	The above does not conflict the proposal contained in GLEP33, which
125	restructure eclasses to include subdirectories and Manifest files, as
126	the Manifest rules above still provide indirect verification for all
127	files after the GLEP33 restructuring if it comes to pass.
128
129	If other Manifests are added (such as per-category, per first-level
130	directory, or protecting versioned eclases), the size of the
131	MetaManifest will be greatly reduced, and this specification was written
132	with such a possible future addition in mind.
133
134	MetaManifest generation will take place as part of the existing process
135	by infrastructure that takes the contents of CVS and prepares it for
136	distribution via rsync, which includes generating metadata. In-tree
137	Manifest files are not checked at this point, as they are assumed to be
138	correct.
139
140	--------------------------------------------------------
141	Verification of one or more items from the MetaManifest:
142	--------------------------------------------------------
143	There are two times that this may happen: firstly, immediately after the
144	rsync has completed - this has the advantage that the kernel file cache
145	is hot, and checking the entire tree can be accomplished quickly.
146	Secondly, the MetaManifest should be checked during installation of a
147	package.
148
149	----------------------------------------------------
150	Procedure for verifying an item in the MetaManifest:
151	----------------------------------------------------
152	In the following, I've used term 'M2-verify' to note following the hash
153	verification procedures as defined by the Manifest2 format - which
154	compromise checking the file length, and that the hashes match. Which
155	filetypes may be ignored on missing is discussed in [#GLEP60].
156
157	1. Check the GnuPG signature on the MetaManifest against the keyring of
158	automated Gentoo keys. See [#GLEPxx+3] for full details regarding
159	verification of GnuPG signatures.
160	1. Abort if the signature check fails.
161
162	2. Check the Timestamp header. If it is significently out of date
163	compared to the local clock or a trusted source, halt or require
164	manual intervention from the user.
165
166	3. For a verification of the tree following an rsync:
167
168	1. Build a set 'ALL' of every file covered by the rsync. (exclude
169	distfiles/, packages/, local/)
170	2. M2-verify every entry in the MetaManifest, descending into inferior
171	Manifests as needed. Place the relative path of every checked item
172	into a set 'COVERED'.
173	3. Construct the set 'UNCOVERED' by set-difference between the ALL and
174	COVERED sets.
175	4. For each file in the UNCOVERED set, assign a Manifest2 filetype.
176	5. If the filetype for any file in the UNCOVERED set requires a halt
177	on error, abort and display a suitable error.
178	6. Completed verification
179
180	4. If checking at the installation of a package:
181
182	1. M2-verify the entry in MetaManifest for the Manifest
183	2. M2-verify all relevant metadata/ contents if metadata/ is being
184	used in any way (optionally done before dependancy checking).
185	3. M2-verifying the contents of the Manifest.
186	4. Perform M2-verification of all eclasses and profiles used (both
187	directly and indirectly) by the ebuild.
188
189	Notes:
190	======
191	1. For initial implementations, it is acceptable to check EVERY item in
192	the eclass and profiles directory, rather than tracking the exact
193	files used by every eclass (see note #2). Later implementations
194	should strive to only verify individual eclasses and profiles as
195	needed.
196	2. Tracking of exact files is of specific significance to the libtool
197	eclass, as it stores patches under eclass/ELT-patches, and as such
198	that would not be picked up by any tracing of the inherit function.
199	This may be alleviated by a later eclass and ebuild variable that
200	explicitly declares what files from the tree are used by a package.
201
202	====================
203	Implementation Notes
204	====================
205	For this portion of the tree-signing work, no actions are required of
206	the individual Gentoo developers. They will continue to develop and
207	commit as they do presently, and the MetaManifest is added by
208	Infrastructure during the tree generation process, and distributed to
209	users.
210
211	--------------------------------------------
212	MetaManifest and the new Manifest2 filetypes
213	--------------------------------------------
214	While [#GLEP60] describes the addition of new filetypes, these are NOT
215	needed for implementation of the MetaManifest proposal. Without the new
216	filetypes, all entries in the MetaManifest would be of type 'MISC'.
217
218	----------------------------------------------------
219	Timestamps & Additional distribution of MetaManifest
220	----------------------------------------------------
221	As discussed by [C08a,C08b], malicious third-party mirrors may use the
222	principles of exclusion and replay to deny an update to clients, while
223	at the same time recording the identity of clients to attack.
224
225	This should be guarded against by including a timestamp in the header of
226	the MetaManifest, as well as distributing the latest MetaManifests by a
227	trusted channel.
228
229	On all rsync mirrors directly maintained by the Gentoo infrastructure,
230	and not on community mirrors, there should be a new module
231	'gentoo-portage-metamanifests'. Within this module, all MetaManifests
232	for a recent time frame (eg one week) should be kept, named as
233	"MetaManifest.$TS", where $TS is the timestamp from inside the file.
234	The most recent MetaManifest should always be symlinked as
235	MetaManifest.current. The possibility of serving the recent
236	MetaManifests via HTTPS should also be explored to mitigate MitM
237	attacks.
238
239	The package manager should obtain MetaManifest.current and use it to
240	decide is the tree is too out of date per operation #2 of the
241	verification process. The decision about freshness should be a
242	user-configuration setting, with the ability to override.
243
244	--------------------------------
245	MetaManifest size considerations
246	--------------------------------
247	With only two levels of Manifests (per-package and top-level), every
248	rsync will cause a lot of traffic transfering the modified top-level
249	MetaManifest. To reduce this, first-level directory Manifests are
250	strongly recommended. Alternatively, if the distribution method
251	efficently handles small patch-like changes in an existing file,
252	using an uncompressed MetaManifest may be acceptable (this would
253	primarily be distributed version control systems). Other suggestions
254	in reducing this traffic are welcomed.
255
256	=======================
257	Backwards Compatibility
258	=======================
259	- There are no backwards compatibility issues, as old versions of
260	Portage do not look for a Manifest file at the top level of the tree.
261	- Manifest2-aware versions of Portage ignore all entries that they are
262	not certain how to handle. Enabling headers and PGP signing to be
263	conducted easily.
264
265	======
266	Thanks
267	======
268	I'd like to thank the following people for input on this GLEP.
269
270	- Patrick Lauer (patrick): Prodding me to get all of the tree-signing
271	work finished, and helping to edit.
272	- Ciaran McCreesh (ciaranm): Paludis Manifest2
273	- Brian Harring (ferringb): pkgcore Manifest2
274	- Marius Mauch (genone) & Zac Medico (zmedico): Portage Manifest2
275	- Ned Ludd (solar) - Security concept review
276
277	==========
278	References
279	==========
280
281	[C08a] Cappos, J et al. (2008). "Package Management Security".
282	University of Arizona Technical Report TR08-02. Available online
283	from: ftp://ftp.cs.arizona.edu/reports/2008/TR08-02.pdf
284	[C08b] Cappos, J et al. (2008). "Attacks on Package Managers"
285	Available online at:
286	http://www.cs.arizona.edu/people/justin/packagemanagersecurity/
287
288	=========
289	Copyright
290	=========
291	Copyright (c) 2006 by Robin Hugh Johnson. This material may be
292	distributed only subject to the terms and conditions set forth in the
293	Open Publication License, v1.0.
294
295	vim: tw=72 ts=2 expandtab: