[gentoo-portage-dev] [0/4] proto-GLEPS for Tree-signing

[gentoo-portage-dev] [0/4] proto-GLEPS for Tree-signing

[Robin H. Johnson]

[-- Attachment #1: Type: text/plain, Size: 1070 bytes --]

Hi folks, it's that time again, time for the proto-gleps on
tree-signing. Barring two minor TODO items, I have completed all of the
series dealing with distribution issues and Manifest2.

The developer issues and gnupg management issues remain, but they don't
block the Manifest2 and distribution parts, so I'm not including them
here at this time.

I have included the changes that genone made in message-id
20071201110545.d2d9c163.genone@gentoo.org to all of the dev-portage@
alias.

I'm going to put each GLEP into a separate email under this thread.

XX - this email
00-proposal-overview  
01-distribution-process-security
02-developer-process-security - NOT INCLUDED
03-gnupg-policies-and-handling - NOT INCLUDED
04-manifest2-hashes  
05-manifest2-clarifications

If you want to view the files in CVS:
http://sources.gentoo.org/viewcvs.py/gentoo/users/robbat2/tree-signing-gleps/

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

[-- Attachment #2: Type: application/pgp-signature, Size: 329 bytes --]

[gentoo-portage-dev] [1/4] proto-GLEPS for Tree-signing

[Robin H. Johnson]

[-- Attachment #1.1: Type: text/plain, Size: 172 bytes --]

Attached.

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

[-- Attachment #1.2: 00-proposal-overview --]
[-- Type: text/plain, Size: 14568 bytes --]

GLEP: xx
Title: Security of distribution of Gentoo software - Overview
Version: $Revision: 1.8 $
Last-Modified: $Date: 2008/07/01 07:03:50 $
Author: Robin Hugh Johnson <robbat2@gentoo.org>
Status: Draft
Type: Informational
Content-Type: text/x-rst
Created: November 2005
Updated: May 2006, October 2006, Novemeber 2007, June 2008
Post-History: ...

Abstract
========
This is the first in a series of 4 GLEPs. It aims to define the actors
and problems in the Gentoo software distribution process, with a strong
emphasis on security. The concepts thus developed, will then be used in
the following GLEPs to describe a comprehensive security solution for
this distribution process that prevents trivial attacks and increases
the difficulty on more complex attacks. 

Motivation
==========
Since at mid-2002 (see endnote: "History of tree-signing in Gentoo"),
many discussions have taken place on the gentoo-dev mailing list and in
many other places to design and implement a security strategy for the
distribution of files by the Gentoo project.

Usually the goal of such proposals was and is to be able to securely
identify the data provided by Gentoo and prevent third parties (like a
compromised mirror) from delivering harmful data (be it as modified
ebuilds, executable shell code or any other form) to the users of the
Gentoo MetaDistribution.

These strategies can neither prevent a malicious or compromised upstream
from injecting "bad" programs, nor can they stop a rogue developer from
committing malicious ebuilds. What they can do is to reduce the attack
vectors so that for example a compromised mirror will be detected and no
tainted data will be executed on user's systems.

Gentoo's software distribution system as it presently stands, contains a
number of security shortcomings. The last discussion on the gentoo-dev
mailing list [http://thread.gmane.org/gmane.linux.gentoo.devel/38363]
contains a good overview of most of the issues. Summarized here:
1. Unverifiable executable code distributed:
   The most obvious instance are eclasses, but there are many other bits
   of the tree that are not signed at all right now. Modifying that data
   is trivial.
2. Shortcomings of existing Manifest verification
   A lack and enforcement of policies, combined with suboptimal support
   in portage, makes it trivial to modify or replace the existing
   Manifests. 
3. Vulnerability of existing infrastructure to attacks.
   The previous two items make it possible for a skilled attacker to
   design an attack and then execute it against specific portions of
   existing infrastructure (eg: Compromise a country-local rsync mirror,
   and totally replace a package and it's Manifest).

Specification
=============
Security is not something that can be considered in isolation. It is
both an ongoing holistic process and lessons learnt by examining
previous shortcomings.

System Elements
---------------
There are a few entities to be considered:
- Upstream. The people who provide the program(s) or data we wish to
  distribute.
- Gentoo Developers. The people that package and test the things
  provided by Upstream.
- Gentoo Infrastructure. The people and hardware that allow the revision
  control of metadata and distribution of the data and metadata provided
  by Developers and Upstream.
- Gentoo Mirrors. Hardware provided by external contributors that is not
  or only marginally controlled by Gentoo Infrastructure. Needed to
  achieve the scalability and performance needed for the substantial
  Gentoo user base.
- Gentoo Users. The people that use the Gentoo MetaDistribution.

The data described here is usually programs and data files provided by
upstream; as this is a rather large amount of data it is usually
distributed over http or ftp from Gentoo Mirrors. This data is usually
labeled as "distfiles". Metadata is all information describing how to
manipulate that data - it is usually called "The Tree" or "The Portage
Tree", consists of many ebuilds, eclasses and supporting files and is
usually distributed over rsync. The central rsync servers are controlled
by Gentoo Infrastructure, but many third-party rsync mirrors exist that
help to reduce the load on those central servers. These extra mirrors
are not maintained by Gentoo Infrastructure.

Attacks may be conducted against any of these entities. Obviously
direct attacks against Upstream and Users are outside of the scope of
this series of GLEPs as they are not in any way controlled or
controllable by Gentoo - however attacks using Gentoo as a conduit (such
as adding a payload at a mirror) must be considered.

Processes
---------
There are two major processes in the distribution of Gentoo, where
security needs to be implemented:
1. Developer commits to version control systems controlled by
   Infrastructure.
2. Tree and distfile distribution from Infrastructure to Users, via the
   mirrors (this includes both HTTP and rsync distribution).

Both processes need their security improved. In [GLEPxx+2] we will discuss
how to improve the security of the first process. The relatively
speaking simpler process of file distribution will be described in
[GLEPxx+1]. Since it can be implemented without having to change the
workflow and behaviour of developers we hope to get it done in a
reasonably short timeframe.

Attacks against Processes
-------------------------
Attacks against the process #1 may be as complex as a malicious or
compromised developer (stolen SSH keys, rooted systems), or as simple as
a patch from a user that does a little more than it claims, and is not
adequately reviewed.

Attacks against the process #2 may be as simple as a single rooted
mirror, distributing a modified tree to the users of that mirror - or
some alteration of upstream sources. These attacks have a low cost and
are very hard to discover unless all distributed data is transparently
signed.

A simple example of such an attack and a partial solution for eclasses
is presented in [ http://thread.gmane.org/gmane.linux.gentoo.devel/24677
]. It shows quite well that any non-Gentoo controlled rsync mirror can
modify executable code; as much of this code is per default run as root
a malicious mirror could compromise hundreds of systems per day - if
cloaked well enough, such an attack could run for weeks before being
noticed. As there are no effective safeguards right now users are left
with the choice of either syncing from the sometimes slow or even
unresponsive Gentoo-controlled rsync mirrors or risk being compromised
by syncing from one of the community-provided mirrors. We will show that
protection against this class of attacks is very easy to implement with
little added cost. 

Security for Processes
------------------------
Protection for process #1 can never be complete (without major
modifications to our development process), as a malicious developer is
fully authorized to provide materials for distribution. Partial
protection can be gained by Portage and Infrastructure changes, but the
real improvements needed are developer education and continued
vigilance. This is further discussed in [GLEPxx+2].

This security is still limited in scope - protection against compromised
developers is very expensive, and even complex systems like peer review
/ multiple signatures can be broken by colluding developers. There are many
issues, be it social or technical, that increase the cost of such
measures a lot while only providing marginal security gains. Any
implementation proposal must be carefully analysed to find the best
security to developer hassle ratio.

Protection for process #2 is a different matter entirely. While it also
cannot be complete (as the User may be attacked directly), we can ensure
that Gentoo infrastructure and the mirrors are not a weak point. This
objective is actually much closer than it seems already - most of the
work has been completed for other things!. This is further discussed in
[GLEPxx+1]. As this process has the most to gain in security, and the
most immediate impact, it should be implemented before or at the same
time as any changes to process #1.

Requirements pertaining to and management of keys (OpenPGP or otherwise)
is an issue that affects both processes, and is broken out into a
separate GLEP due to the technical complexity of the subject.
This deals with everything including: types of keys to use; usage
guidelines; procedures for managing signatures and trust for keys,
including cases of lost (destroyed) and stolen (or otherwise turned
malicious) keys.

Backwards Compatibility
=======================
As an informational GLEP, this document has no direct impact on
backwards compatibility. However the related in-depth documents may
delve further into any issues of backwards compatibility.

Endnote: History of tree-signing in Gentoo
==========================================
This is a brief review of every previous tree-signing discussion, the
stuff before 2003-04-03 was very hard to come by, so I apologize if I've
missed a discussion (I would like to hear about it). I think there was
a very early private discussion with drobbins in 2001, as it's vaguely
referenced, but I can't find it anywhere.

2002-06-06, gentoo-dev mailing list, users first ask about signing of
ebuilds:
[ http://thread.gmane.org/gmane.linux.gentoo.devel/1950 ]

2003-01-13, gentoo-dev mailing list, "Re: Verifying portage is from
Gentoo" - Paul de Vrieze (pauldv):
[ http://thread.gmane.org/gmane.linux.gentoo.devel/6619/focus=6619 ]

2003-04, GWN articles announcing tree signing:
[ http://www.gentoo.org/news/en/gwn/20030407-newsletter.xml#doc_chap1_sect3 ]
[ http://www.gentoo.org/news/en/gwn/20030421-newsletter.xml#doc_chap1_sect2 ]

2003-04, gentoo-security mailing list, "The state of ebuild signing
in portage" - Joshua Brindle (method), the first suggestion of signed Manifests,
but also an unusual key-trust model:
[ http://marc.theaimsgroup.com/?l=gentoo-security&m=105073449619892&w=2 ]

2003-04, gentoo-core mailing list, "New Digests and Signing -- Attempted Explanation"

2003-06, gentoo-core mailing list, "A quick guide to GPG and key
signing." - This overview was one of the first to help developers see
how to use their devs, and was mainly intended for keysigning meetups.

2003-08-09, gentoo-core mailing list, "Ebuild signing" - status query,
with an not very positive response, delayed by Nick Jones (carpaski)
getting rooted and a safe cleanup taking a long time to affect.

2003-12-02, gentoo-core mailing list, "Report: rsync1.it.gentoo.org compromised"

2003-12-03, gentoo-core mailing list, "Signing of ebuilds"

2003-12-07, gentoo-core mailing list, "gpg signing of Manifests", thread
includes the first GnuPG signing prototype code, by Robin H. Johnson
(robbat2). Andrew Cowie (rac) also produces a proof-of-concept around
this time.

2004-03-23, gentoo-dev mailing list, "2004.1 will not include a secure
portage" - Kurt Lieber (klieber). Signing is nowhere near ready for
2004.1 release, and it is realized that it there is insufficient traction
and the problem is very large. Many arguments about the checking and
verification side. First warning signs that MD5 might be broken in the
near future.
[ http://thread.gmane.org/gmane.linux.gentoo.devel/16876 ]

2004-03-25, gentoo-dev mailing list, "Redux: 2004.1 will not include a
secure portage" - Robin H. Johnson (robbat2). Yet another proposal,
summarizing the points of the previous thread and this time trying to
track the various weaknesses.
http://marc.theaimsgroup.com/?l=gentoo-dev&m=108017986400698&w=2

2004-05-31, Gentoo managers meeting, portage team reports that
FEATURES=sign is now available, but large questions still exist over
verification policies and procedures, as well as handing of keys.
[ http://www.gentoo.org/proj/en/devrel/manager-meetings/logs/2004/20040531.txt ]

2005-01-17, gentoo-core mailing list, "Global objective for 2005 :
portage signing". Thierry Carrez (koon) suggests that more go into
tree-signing work. Problems at the time later in the thread show that
the upstream gpg-agent is not ready, amongst other minor implementation
issues.

2005-02-20, gentoo-dev mailing list, "post-LWE 2005" - Brian Harring
(ferringb). A discussion on the ongoing lack of signing, and that
eclasses and profiles need to be signed as well, but this seems to be
hanging on GLEP33 in the meantime.
[ http://thread.gmane.org/gmane.linux.gentoo.devel/25556/focus=25596 ] 

2005-03-08, gentoo-core mailing list, "gpg manifest signing stats".
Informal statistics show that 26% of packages in the tree include a
signed Manifest. Questions are raised regarding key types, and key
policies.

2005-11-16, gentoo-core mailing list, "Gentoo key signing practices and
official Gentoo keyring". A discussion of key handling and other
outstanding issues, also mentioning partial Manifests, as well as a
comparision between the signing procedures used in Slackware, Debian and
RPM-based distros.

2005-11-19, gentoo-portage-dev mailing list, "Manifest signing" - Robin
H. Johnson (robbat2) follows up the previous -core posting, discussion
implementation issues.
[ http://thread.gmane.org/gmane.linux.gentoo.portage.devel/1401 ]

2006-05-18, gentoo-dev mailing list, "Signing everything, for fun and for
profit" - Patrick Lauer (bonsaikitten). Later brings up that Manifest2 is needed for
getting everything right.
[ http://thread.gmane.org/gmane.linux.gentoo.devel/38363 ]

2006-05-19, gentoo-dev mailing list, "Re: Signing everything, for fun and for
profit" - Robin H. Johnson (robbat2). An introduction into some of the
OpenPGP standard, with a focus on how it affects file signing, key
signing, management of keys, and revocation.
[ http://thread.gmane.org/gmane.linux.gentoo.devel/38363/focus=38371 ]

Thanks
======
I'd like to thank Patrick Lauer (bonsaikitten) for prodding me
to keep working on the tree-signing project, as well helping with
spelling, grammar, research (esp. tracking down every possible
vulnerability that has been mentioned in past discussions, and
integrating them in this overview).

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:

[-- Attachment #2: Type: application/pgp-signature, Size: 329 bytes --]

[gentoo-portage-dev] [2/4] proto-GLEPS for Tree-signing

[Robin H. Johnson]

[-- Attachment #1.1: Type: text/plain, Size: 172 bytes --]

Attached.

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

[-- Attachment #1.2: 01-distribution-process-security --]
[-- Type: text/plain, Size: 9534 bytes --]

GLEP: xx+1
Title: Security of distribution of Gentoo software - Infrastructure to User distribution - MetaManifest
Version: $Revision: 1.13 $
Last-Modified: $Date: 2008/07/01 07:09:56 $
Author: Robin Hugh Johnson <robbat2@gentoo.org>, 
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Requires: GLEP44, GLEPxx+5
Created: October 2006
Updated: November 2007, June 2008
Post-History: ...

========
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.

=============
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.
2.1. 'ALL' will contain every file in the tree.
2.2. 'COVERED' will contain every file that is mentioned in an existing
     Manifest2.

3. Traverse the tree, depth-first.
3.1. At the top level only, ignore the distfiles and packages
     directories.
3.2. If the directory contains a Manifest file add it to the ALL set and
     don't descend any further, otherwise add all files to the ALL set
3.3. 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 [GLEPxx+5]), and place them
     into the COVERED set.

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

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. The MetaManifest must ultimately be GnuPG-signed.
7.1. For the initial implementation, the same key as used for snapshot
     tarball signing is sufficient.
7.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, 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 [GLEPxx+5].

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.1. Abort if the signature check fails.

2. For a verification of the tree following an rsync:
2.1. Build a set 'ALL' of every file covered by the rsync. (exclude
     distfiles/, packages/, local/)
2.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'.
2.3. Construct the set 'UNCOVERED' by set-difference between the ALL and
     COVERED sets.
2.4. For each file in the UNCOVERED set, assign a Manifest2 filetype.
2.5. If the filetype for any file in the UNCOVERED set requires a halt
     on error, abort and display a suitable error.
2.6. Completed verification

3. If checking at the installation of a package:
3.1. M2-verify the entry in MetaManifest for the Manifest
3.2. M2-verify all relevant metadata/ contents if metadata/ is being
     used in any way (optionally done before dependancy checking).
3.3. M2-verifying the contents of the Manifest. 
3.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.

=======================
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 entries that they are not
certain how to handle.

======
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
TODO:
- Ned Ludd (solar) - Security concept review

=========
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:

[-- Attachment #2: Type: application/pgp-signature, Size: 329 bytes --]

[gentoo-portage-dev] [3/4] proto-GLEPS for Tree-signing

[Robin H. Johnson]

[-- Attachment #1.1: Type: text/plain, Size: 172 bytes --]

Attached.

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

[-- Attachment #1.2: 04-manifest2-hashes --]
[-- Type: text/plain, Size: 8108 bytes --]

GLEP: xx+4
Title: Manifest2 hash policies and security implications
Version: $Revision: 1.10 $
Last-Modified: $Date: 2008/07/01 07:18:43 $
Author: Robin Hugh Johnson <robbat2@gentoo.org>, 
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Requires: GLEP44
Created: October 2006
Updated: November 2007, June 2008
Post-History: ...
Updates: GLEP44

Abstract
========
While Manifest2 format allows multiple hashes, the question of which
checksums should be present, why, and the security implications of such
have never been resolved. This GLEP covers all of these issues, and
makes recommendations as to how to handle checksums both now, and in
future.

Motivation
==========
This GLEP is being written as part of the work on signing the Portage
tree, but is only tangentially related to the actual signing of
Manifests. Checksums present one possible weak point in the overall
security of the tree - and a comprehensive security plan is needed.

Specification
=============
The bad news
------------
First of all, I'd like to cover the bad news in checksum security.
A much discussed point, as been the simple question: What is the
security of multiple independent checksums on the same data?
The most common position (and indeed the one previously held by myself),
is that multiple checksums would be an increase in security, but we
could not provably quantify the amount of security this added.
The really bad news, is that this position is completely and utterly
wrong. Many of you will be aghast at this. There is extremely little
added security in multiple checksums [J04]. For any set of checksums,
the actual strength lies in that of the strongest checksum.

How fast can MD5 be broken?
---------------------------
For a general collision, not a pre-image attack, since the original
announcement by Wang et al [W04], the time required to break MD5 has
been massively reduced. Originally at 1 hour on a near-supercomputer
(IBM P690) and estimated at 64 hours with a Pentium-3 1.7Ghz. This has
gone down to less than in two years, to 17 seconds [K06a]!

08/2004 - 1 hour, IBM pSeries 690 (32x 1.7Ghz POWER4+) = 54.4 GHz-Hours
03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours
11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours
03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours
04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours

If we accept a factor of 800x as a sample of how much faster a checksum
may be broken over the course of 2 years (MD5 using the above data is
>2000x), then existing checksums do not stand a significant chance of
survival in the future. We should thus accept that whatever checksums we
are using today, will be broken in the near future, and plan as best as
possible. (A brief review [H04] of the present SHA1 attacks indicates an
improvement of ~600x in the same timespan).

And for those that claim implementation of these procedures is not yet
feasible, see [K06b] for an application that can produce two
self-extracting .exe files, with identical MD5s, and whatever payload
you want.

The good news
-------------
Of the checksums presently used by Manifest2, one stands close to being
completely broken: SHA1. The SHA2 series has suffered some attacks, but
still remains reasonably solid [G07],[K08]. No attacks against RIPEMD160
have been published, however it is constructed in the same manner as
MD5, SHA1 and SHA2, so is also vulnerable to the new methods of
cryptanalysis [H04].

To reduce the potential for future problems and any single checksum
break leading to a rapid decrease in security, we should incorporate the
strongest hash available from each family of checksums, and be prepared
to retire old checksums actively, unless there is a overriding reason to
keep a specific checksum.

What should be done
-------------------
Portage should always try to verify all supported hashes that are
available in a Manifest2, starting with the strongest ones as maintained
by a preference list. Over time, the weaker checksums should be removed
from Manifest2 files, once all old Portage installations have had
sufficient time to upgrade. We should be prepared to add stronger
checksums wherever possible, and to remove those that have been
defeated.

An unsupported hash is not considered to be a failure unless no
supported hashes are available.

Checksum depreciation
~~~~~~~~~~~~~~~~~~~~~
For the current Portage, SHA1 should be gradually removed, as presents
no advantages over SHA256. Beyond one specific problem (see the next
paragraph), we should add SHA512 (SHA2, 512 bit size), the Whirlpool
checksum (standardized checksum, with no known weaknesses). In future,
as stream-based checksums are developed (in response to the development
by NIST [AHS]), they should be considered and used.

There is one temporary stumbling block at hand - the existing Portage
infrastructure does not support SHA384/512 or Whirlpool, thus hampering
their immediate acceptance. SHA512 is available in Python 2.5, while
SHA1 is already available in Python 2.4. After Python2.5 is established
in a Gentoo media release, that would be a suitable time to remove SHA1
from Manifest2 files.

Backwards Compatibility
=======================
Old versions of Portage may support and expect only specific checksums.
This is accounted for in the checksum depreciation discussion.

References
==========

[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions",
  (Advanced Hash Standard). http://csrc.nist.gov/pki/HashWorkshop/

[BOBO06] Boneh, D. and Boyen, X. (2006). "On the Impossibility of
  Efficiently Combining Collision Resistant Hash Functions"; Proceedings
  of CRYPTO 2006, Dwork, C. (Ed.); Lecture Notes in Computer Science
  4117, pp. 570-583. Available online from:
  http://crypto.stanford.edu/~dabo/abstracts/hashing.html

[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective
  Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive,
  Report 2004/204. Available online from:
  http://eprint.iacr.org/2004/207.pdf

[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash Functions
  - Application to Cascaded Constructions;" Proceedings of CRYPTO 2004,
  Franklin, M. (Ed); Lecture Notes in Computer Science 3152, pp. 
  306-316. Available online from:
  http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf

[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions
  Within a Minute". Cryptology ePrint Archive, Report 2006/105.
  Available online from: http://eprint.iacr.org/2006/105.pdf

[K06b] Klima, V. (2006). "Note and links to high-speed MD5 collision
  proof of concept tools". Available online from:
  http://cryptography.hyperlink.cz/2006/trick.txt

[K08] Klima, V. (2008). "On Collisions of Hash Functions Turbo SHA-2".
  Cryptology ePrint Archive, Report 2008/003. Available online from:
  http://eprint.iacr.org/2008/003.pdf

[G07] Gligoroski, D. and Knapskog, S.J. (2007). "Turbo SHA-2".
  Cryptology ePrint Archive, Report 2007/403. Available online from:
  http://eprint.iacr.org/2007/403.pdf

[W04] Wang, X. et al: "Collisions for Hash Functions MD4, MD5,
  HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint
  Archive, Report 2004/199, first version (August 16, 2004), second
  version (August 17, 2004). Available online from:
  http://eprint.iacr.org/2004/199.pdf

Thanks to
=========
I'd like to thank the following folks, in no specific order:
- Ciaran McCreesh (ciaranm) - for pointing out the Joux (2004) paper,
  and also being stubborn enough in not accepting a partial solution.
- Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring
  (ferringb): for being knowledgeable about the Portage Manifest2
  codebase.

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:

[-- Attachment #2: Type: application/pgp-signature, Size: 329 bytes --]

[gentoo-portage-dev] [4/4] proto-GLEPS for Tree-signing

[Robin H. Johnson]

[-- Attachment #1.1: Type: text/plain, Size: 172 bytes --]

Attached.

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

[-- Attachment #1.2: 05-manifest2-clarifications --]
[-- Type: text/plain, Size: 7728 bytes --]

GLEP: xx+5
Title: Manifest2 filetypes
Version: $Revision: 1.15 $
Last-Modified: $Date: 2008/07/01 08:52:34 $
Author: Robin Hugh Johnson <robbat2@gentoo.org> 
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Requires: GLEP44
Created: November 2007
Updated: June 2008
Post-History: ...
Updates: GLEP44

Abstract
========
Clarification of the Manifest2 [GLEP44] specification, including new types to
help in the tree-signing specification.

Motivation
==========
[GLEP44] was not entirely clear on the usage of filetype specifiers.
This document serves to provide some of the internal logic used by
Portage at the point of writing, as well as adding new types to cover
the rest of the tree, for the purposes of tree-signing coverage.

Specification
=============
General
-------
For any given directory with a Manifest file, every file located in that
directory, or a sub-directory must be listed in that Manifest file,
unless stated otherwise in the following sections. The Manifest file
must not contain an entry for itself.

Excluded files
--------------
When generating or validating a Manifest, or commiting to a version
control system, the package manager should endeavour to ignore files
created by a version control system, backup files from text editors. A
non-exhaustive list is suggested here: .cvs/, .svn/, .git/, .hg/, .#*,
*.rej, *.orig, *.bak, *~.

Additionally, for a transitional Manifest1->Manifest2 system, old-style
digest files located in a 'files/' directory, may be excluded from
Manifest2 generation, or included with a type of MISC.


Existing filetypes:
-------------------
AUX
~~~
- The AUX type is used for all items under the 'files' subdirectory. 
- They should be verified relative to $FILESDIR. 
- The string 'files/' is left out of the Manifest line. 
- The absence of a file mentioned by AUX must be treated as an error. 
- The AUX type is intended to denote potentially executable content
  (either directly or indirectly), that must be treated an error if
  modified or absent.

EBUILD
~~~~~~
- The EBUILD type is used solely for files ending in .ebuild, or other
  suffixes as defined by the EAPI.
- The files are located in the same directory as the Manifest file. 
- The modification or absence of a file mentioned by EBUILD must be
  treated as an error.

DIST
~~~~
- The DIST type is used for distfiles
- They may be found directly via the $DISTDIR setting of the package
  manager. 
- During simple verification of a Manifest, a missing DIST file should
  not be consider as a validation error (it is however a failure to
  fetch or unpack).

MISC
~~~~
- The MISC type covers all remaining files in a directory. 
- MISC is intended to mark all content that was not used in
  some way that directly affected execution of the package manager. 
- This includes metadata.xml and ChangeLog entries, and any other purely
  informational content.
- MISC entries where the file is missing may optionally be ignored as by
  non-strict package managers.
- It should be possible to install a package while all MISC entries have
  been deleted from the tree.


New filetypes:
--------------
_INFO (new, abstract)
~~~~~~~~~~~~~~~~~~~~~~~~~
- This is the functionality of the old AUX, but does not include the
  implicit 'files/' prefix in the path, and is verified relative to the
  working directory instead of $FILESDIR.
- The modification or absence of a file listed as a _INFO-derived type 
  is not an error unless the package manager is attempting to be strict.

_CRIT (new, abstract)
~~~~~~~~~~~~~~~~~~~~~~~~~
- _CRIT is based off the _INFO type.
- The modification or absence of a file listed as a _CRIT-derived type 
  must be treated as an error.

EBUILD
~~~~~~
- Now derived from _CRIT.
- Otherwise unchanged.

DIST
~~~~
- Now derived from _CRIT.
- Otherwise unchanged.

MISC
~~~~
- Now derived from _INFO.
- Otherwise unchanged.

MANIFEST (new)
~~~~~~~~~~~~~~
- The MANIFEST type is explicitly to cover all nested Manifest files.
- During validation, this serves as an indicator that the package
  manager may need to check subtree Manifest file. 
- A missing MANIFEST file may be treated as a minor (eg excluding an
  entire category) or critical validation failure.
- The failure should be considered as critical only if files that would
  be directly covered by this Manifest are missing. Deletion of a
  category-level Manifest while preserving the packages is forbidden.
  Deletion of an entire category is not.

ECLASS (new)
~~~~~~~~~~~~
- uses _CRIT.
- This type shall be used for all eclasses only.
- TODO: What about patches etc under eclasses/? Probably EXEC?

DATA (new)
~~~~~~~~~~
- uses _CRIT.
- The DATA type shall be used for all files that directly affect the
  package manager, such as metadata/cache/* and profiles/.

EXEC (new)
~~~~~~~~~
- uses _CRIT.
- If the file gets sourced, executed, or causes a change (patches) in
  how something is sourced or execututed, it belongs in the EXEC
  filetype.
- This filetype should be used for the scripts directories of a
  repository for important files.

UNKNOWN (new)
~~~~~~~~~~~~~
- uses __FOO.
- All other files that are not covered by another type should be
  considered as 'UNKNOWN'.

On Bloat
--------
If repeated use of a common path prefix is considered a bloat problem, a
Manifest file should be added inside the common directory, however this
should not be done blindly, as bloat by inodes is more significant for
the majority of use cases. 

Chosing a filetype
------------------
1. matches Manifest 
    => MANIFEST, stop.
2. matches *.ebuild 
    => EBUILD, stop.
3. matches *.eclass 
    => ECLASS, stop.
4. listed in SRC_URI 
    => DIST, stop.
5. matches files/* 
    => AUX, continue [see note].
6. matches {*.sh,*.bashrc,*.patch,...} 
    => EXEC, stop.
7. matches {metadata/cache/*,profiles/,package.*,use.mask*,...} 
    => DATA, stop.
8. matches {ChangeLog,metadata.xml,*.desc,...} 
    => MISC, stop.
9. not matched by any other rule 
    => UNKNOWN, stop.

The logic behind 5, 6, 7 is ensuring that every item that by it's
presence or absense may be dangerous should always be treated strictly.
(Consider epatch given a directory of patches ${FILESDIR}/${PV}/, where
it blindly includes them, or alternatively, the package.mask file or a
profile being altered/missing).

Note: The AUX entries should only be generated if we are generating a
compatible Manifest that supports older versions of Portage. They should
be generated along with the new type.

Backwards Compatibility
=======================
For generation of existing package Manifests, the AUX entries must
continue to be present for the standard Portage deprecation cycle.
The new entries may be included already in all Manifest files, as they
will be ignored by older Portage versions. Over time, ECLASS, DATA,
EXEC, UNKNOWN may replace the existing AUX type.

The adoption of this proposal does also affect [GLEPxx+1] as part of
this GLEP series, however this GLEP was an offset of the research in
that GLEP.

Thanks to
=========
I'd like to thank the following people for input on this GLEP.
- Marius Mauch (genone) & Zac Medico (zmedico): Portage Manifest2

References
==========
[GLEP44] Mauch, M. (2005) GLEP44 - Manifest2 format.
  http://www.gentoo.org/proj/en/glep/glep-0044.html	

Copyright
=========
Copyright (c) 2007 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:

[-- Attachment #2: Type: application/pgp-signature, Size: 329 bytes --]

Re: [gentoo-portage-dev] [2/4] proto-GLEPS for Tree-signing

[Mike Auty]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sorry,
	I lost my notes from when I last looked these over several months ago,
and only just found them again.  I haven't copied this to gleps@g.o, so
let me know if I should do that.  I just had a quick couple of things I
was thinking about, and one of them I figured out during my re-read, so
it's only really the following...

In this Glep (xx+1), in the section discussing the procedure for
creating a MetaManifest file, in step 3.3, does that include
verification of the manifest's signature if it has one?  It would seem
odd to ignore the signature if it's wrong (I'm not sure about the case
if a signature isn't present).  I also don't know how this would then be
handled (a complete abort, or ignoring the latest changeset to that
ebuild?).
	If the signature check happened here, it could also allow for
enforcable revocation of developer certificates (once they're revoked,
any signed manifests will have the ebuild changes ignored).  That may be
a lot of work and may take too long, but if not (and depending on our
users' trust needs), it might allow them just to check the
MetaManifest's signature, and not that of the individual packages.  Does
that seems sensible?

	I've probably missed a key issue somewhere along the way, in which
case, sorry, and do feel free to chide me liberally...  5:)
	Mike  5:)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)

iEYEARECAAYFAkiPdNAACgkQu7rWomwgFXoJ9gCeLZOvpGAyr+EzI/d8EKWrnqnf
CVoAoI63EiYvB4+1cBSURIlRxaH0xy4o
=yZH7
-----END PGP SIGNATURE-----

Re: [gentoo-portage-dev] [2/4] proto-GLEPS for Tree-signing

[Marius Mauch]

On Tue, 29 Jul 2008 20:51:45 +0100
Mike Auty <ikelos@gentoo.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Sorry,
> 	I lost my notes from when I last looked these over several
> months ago, and only just found them again.  I haven't copied this to
> gleps@g.o, so let me know if I should do that.  I just had a quick
> couple of things I was thinking about, and one of them I figured out
> during my re-read, so it's only really the following...
> 
> In this Glep (xx+1), in the section discussing the procedure for
> creating a MetaManifest file, in step 3.3, does that include
> verification of the manifest's signature if it has one?  It would seem
> odd to ignore the signature if it's wrong (I'm not sure about the case
> if a signature isn't present).  I also don't know how this would then
> be handled (a complete abort, or ignoring the latest changeset to that
> ebuild?).

I don't think that verification at this stage would be a good idea. The
only sane way to respond to a failed check would be to either exclude
the whole package from the sync (keeping the state from the last run),
leading to various problems (what if it's a critical bugfix/security
bump, or breaks a the deptree of many packages?), or not record the
Manifest in the Metamanifest, which hasn't any benefits over reyling on
the client doing the verification.

Marius

Re: [gentoo-portage-dev] [2/4] proto-GLEPS for Tree-signing

[Robin H. Johnson]

[-- Attachment #1: Type: text/plain, Size: 1739 bytes --]

On Tue, Jul 29, 2008 at 08:51:45PM +0100, Mike Auty wrote:
> In this Glep (xx+1), in the section discussing the procedure for
> creating a MetaManifest file, in step 3.3, does that include
> verification of the manifest's signature if it has one?  It would seem
> odd to ignore the signature if it's wrong (I'm not sure about the case
> if a signature isn't present).  I also don't know how this would then be
> handled (a complete abort, or ignoring the latest changeset to that
> ebuild?).
It doesn't care whatsoever about signatures inside Manifests.
That's because there's no difference between a Manifest that isn't
signed by a developer, and a Manifest that is developer-signed but any
master signature on the developer has been revoked.
It's also totally impossible to just block a changeset at the moment
like that, even if we had Git.

> 	If the signature check happened here, it could also allow for
> enforcable revocation of developer certificates (once they're revoked,
> any signed manifests will have the ebuild changes ignored).  That may be
> a lot of work and may take too long, but if not (and depending on our
> users' trust needs), it might allow them just to check the
> MetaManifest's signature, and not that of the individual packages.  Does
> that seems sensible?
They don't need to check the signatures of the individual packages
unless they are really paranoid anyway. You've missed one of the key
points of MetaManifest:
It defends ONLY the path from the Gentoo infrastructure to the users.

P.S, you don't need to CC me.

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

[-- Attachment #2: Type: application/pgp-signature, Size: 329 bytes --]