1 /* fides.cc - Light-weight, decentralised trust and authorisation management
2 Copyright (C) 2008-2009 Guus Sliepen <guus@tinc-vpn.org>
4 Fides is free software; you can redistribute it and/or modify
5 it under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 2.1 of
7 the License, or (at your option) any later version.
9 Fides is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU Lesser General Public License for more details.
14 You should have received a copy of the GNU Lesser General Public
15 License along with this program; if not, see <http://www.gnu.org/licenses/>.
21 #include <sys/types.h>
30 #define FIDES_DEBUG false
33 #define debug if(FIDES_DEBUG)
38 /// Saves a certificate to a file.
40 /// @param cert Certificate to save.
41 /// @param filename File to save the certificate to.
42 void fides::certificate_save(const certificate *cert, const std::string &filename) const {
43 ofstream file(filename.c_str());
44 file << cert->to_string() << '\n';
47 /// Loads a certificate from a file.
49 /// @param filename File to save the certificate to.
50 /// @return The certificate.
51 certificate *fides::certificate_load(const std::string &filename) {
52 ifstream file(filename.c_str());
55 return certificate_from_string(data);
58 /// Loads a certificate from a string.
60 /// @param data String containing the certificate in textual form.
61 /// @return The certificate.
62 certificate *fides::certificate_from_string(const std::string &data) {
64 e = data.find(' ', 0);
66 throw exception("Invalid certificate");
67 string fingerprint = hexdecode(data.substr(0, e));
68 const publickey *signer = find_key(fingerprint);
70 throw exception("Unknown public key");
72 e = data.find('.', b);
74 throw exception("Invalid certificate");
75 struct timeval timestamp;
76 timestamp.tv_sec = atol(data.c_str() + b);
78 timestamp.tv_usec = atol(data.c_str() + b);
79 e = data.find(' ', b);
81 throw exception("Invalid certificate");
83 e = data.find(' ', b);
85 throw exception("Invalid certificate");
86 string signature = b64decode(data.substr(b, e - b));
88 string statement = data.substr(b);
90 return new certificate(signer, timestamp, statement, signature);
95 /// \brief Interaction with a Fides database.
97 /// A fides object manages a database of public keys and certificates.
98 /// New certificates can be created, certificates can be imported and exported,
99 /// and queries can be done on the database.
102 /// Creates a new handle on a Fides database.
104 /// Will load the private key, known public keys and certificates.
105 /// After that it will calculate the trust value of all keys.
107 /// @param dir Directory where Fides stores the keys and certificates.
108 /// If no directory is specified, the following environment variables
109 /// are used, in the given order:
113 fides::fides(const std::string &dir): homedir(dir) {
114 debug cerr << "Fides initialising\n";
116 // Set homedir to provided directory, or $FIDES_HOME, or $HOME/.fides, or as a last resort $PWD/.fides
118 homedir = getenv("FIDES_HOME") ?: "";
119 if(homedir.empty()) {
121 homedir = getenv("HOME") ?: getcwd(cwd, sizeof cwd);
122 homedir += "/.fides";
125 // Derived directories
127 certdir = homedir + "certs/";
128 keydir = homedir + "keys/";
129 obsoletedir = homedir + ".obsolete_certs/";
131 // Ensure the homedir and its subdirectories exist
132 mkdir(homedir.c_str(), 0700);
133 mkdir(certdir.c_str(), 0700);
134 mkdir(keydir.c_str(), 0700);
135 mkdir(obsoletedir.c_str(), 0700);
138 mykey.load_private(homedir + "priv");
140 } catch(fides::exception &e) {
141 cerr << "Fides generating keypair\n";
143 mykey.save_private(homedir + "priv");
144 mykey.save(keydir + hexencode(mykey.fingerprint()));
147 vector<string> files = dirlist(keydir);
148 for(size_t i = 0; i < files.size(); ++i) {
149 debug cerr << "Loading key " << files[i] << '\n';
151 publickey *key = new publickey();
152 key->load(keydir + files[i]);
153 keys[hexdecode(files[i])] = key;
156 keys[mykey.fingerprint()] = &mykey;
158 files = dirlist(certdir);
159 for(size_t i = 0; i < files.size(); ++i) {
160 debug cerr << "Loading certificate " << files[i] << '\n';
161 certificate *cert = certificate_load(certdir + files[i]);
162 if(false && !cert->validate()) {
163 cerr << "Bad certificate in database: " << cert->to_string() << '\n';
166 certs[hexdecode(files[i])] = cert;
169 // TODO: save and load this value
177 debug cerr << "Fides exitting\n";
178 for(map<string, certificate *>::const_iterator i = certs.begin(); i != certs.end(); ++i)
180 for(map<string, publickey *>::const_iterator i = keys.begin(); i != keys.end(); ++i)
181 if(i->second != &mykey)
185 /// Checks the validaty of all certificates.
187 /// @return True if all known certificates are valid, false otherwise.
188 bool fides::fsck() const {
191 for(map<string, certificate *>::const_iterator i = certs.begin(); i != certs.end(); ++i) {
192 if(!i->second->validate()) {
193 cerr << "Validation of certificate failed: " << i->second->to_string() << '\n';
198 cerr << errors << " errors in " << certs.size() << " certificates\n";
202 /// Returns the base directory used by Fides.
204 /// @return The home directory.
205 string fides::get_homedir() const {
209 /// Tests whether this is the first time Fides has run and has generated new keys.
211 /// @return True if this is the first time, false otherwise.
212 bool fides::is_firstrun() const {
216 /// Find the public key corresponding to a given fingerprint.
218 /// @param fingerprint String containing a fingerprint.
219 /// @return Pointer to the public key corresponding to the fingerprint, or NULL if it was not found.
220 publickey *fides::find_key(const std::string &fingerprint) const {
221 map<string, publickey *>::const_iterator i;
222 i = keys.find(fingerprint);
229 /// Find all certificates from a give public key and that match a regular expression.
231 /// @param signer Public key to match certificates to.
232 /// @param regex Regular expression to match the statement of each certificate to.
233 /// @return A vector of certificates that match the criteria.
234 vector<const certificate *> fides::find_certificates(const publickey *signer, const std::string ®ex) const {
235 vector<const certificate *> found;
236 map<string, certificate *>::const_iterator i;
237 regexp regexp(regex);
238 for(i = certs.begin(); i != certs.end(); ++i) {
240 cerr << "No certificate for " << hexencode(i->first) << '\n';
243 if(i->second->signer == signer)
244 if(regexp.match(i->second->statement))
245 found.push_back(i->second);
250 /// Find all certificates that match a regular expression.
252 /// @param regex Regular expression to match the statement of each certificate to.
253 /// @return A vector of certificates that match the criteria.
254 vector<const certificate *> fides::find_certificates(const std::string ®ex) const {
255 vector<const certificate *> found;
256 map<string, certificate *>::const_iterator i;
257 regexp regexp(regex);
258 for(i = certs.begin(); i != certs.end(); ++i)
259 if(regexp.match(i->second->statement))
260 found.push_back(i->second);
264 /// Find all certificates from a give public key.
266 /// @param signer Public key to match certificates to.
267 /// @return A vector of certificates that match the criteria.
268 vector<const certificate *> fides::find_certificates(const publickey *signer) const {
269 vector<const certificate *> found;
270 map<string, certificate *>::const_iterator i;
271 for(i = certs.begin(); i != certs.end(); ++i)
272 if(i->second->signer == signer)
273 found.push_back(i->second);
277 /// Import public keys and certificates from a stream.
279 /// @param in Stream to read from.
280 void fides::import_all(std::istream &in) {
284 while(getline(in, line)) {
288 if(is_pem || !line.compare(0, 11, "-----BEGIN ")) {
290 if(!line.compare(0, 9, "-----END ")) {
291 publickey *key = new publickey();
292 key->from_string(pem);
293 debug cerr << "Imported key " << hexencode(key->fingerprint()) << '\n';
302 certificate *cert = certificate_from_string(line);
303 debug cerr << "Importing certificate " << hexencode(cert->fingerprint()) << '\n';
308 /// Export all public keys and certificates to a stream.
310 /// @param out Stream to write to.
311 void fides::export_all(std::ostream &out) const {
312 for(map<string, publickey *>::const_iterator i = keys.begin(); i != keys.end(); ++i)
313 out << i->second->to_string();
314 for(map<string, certificate *>::const_iterator i = certs.begin(); i != certs.end(); ++i)
315 out << i->second->to_string() << '\n';
318 /// Trust a public key.
320 /// This creates a certificate that says that we trust the given public key.
321 /// If a key is trusted, then authorisation certificates from that key are taken into account
322 /// when calling functions such as fides::is_allowed().
324 /// @param key Public key to trust.
325 void fides::trust(const publickey *key) {
326 string full = "t+ " + hexencode(key->fingerprint());
330 /// Distrust a public key.
332 /// This creates a certificate that says that we distrust the given public key.
333 /// If a key is distrusted, then authorisation certificates from that key are not taken into account
334 /// when calling functions such as fides::is_allowed().
336 /// @param key Public key to trust.
337 void fides::distrust(const publickey *key) {
338 string full = "t- " + hexencode(key->fingerprint());
342 /// Don't care about a public key.
344 /// This creates a certificate that says that we neither trust nor distrust the given public key.
345 /// This key and certificates created by it are then treated as if we have never trusted nor distrusted this key.
347 /// @param key Public key to trust.
348 void fides::dctrust(const publickey *key) {
349 string full = "t0 " + hexencode(key->fingerprint());
353 /// Recalculate the trust value of all known public keys.
354 void fides::update_trust() {
355 // clear trust on all keys
356 for(map<string, publickey *>::const_iterator i = keys.begin(); i != keys.end(); ++i)
357 i->second->trust = 0;
359 // Start by checking all trust certificates from ourself.
360 // If another key is positively or negatively trusted, update its trust score
361 // and add it to the the list of new keys to check.
362 // Then add our own key to the list of already checked keys.
363 // Then check all the trust certificates of those on the tocheck list, etc.
364 // Already checked keys are never updated anymore (TODO: is that smart?)
365 // Certificates of keys with a zero or negative trust score are not processed.
367 set<publickey *> checked;
368 set<publickey *> tocheck;
369 set<publickey *> newkeys;
370 set<publickey *>::iterator i;
373 tocheck.insert(&mykey);
375 while(tocheck.size()) {
377 checked.insert(tocheck.begin(), tocheck.end());
380 // loop over all keys whose certificates need to be checked
382 for(i = tocheck.begin(); i != tocheck.end(); ++i) {
383 debug cerr << "Trust for key " << hexencode((*i)->fingerprint()) << " set to " << (*i)->trust << '\n';
385 // except if this key is not trusted
390 // find all non-zero trust certificates of this key
392 vector<const certificate *> matches = find_certificates(*i, "^t[+-] ");
394 // update trust value of those keys
396 for(size_t j = 0; j < matches.size(); j++) {
397 publickey *other = find_key(hexdecode(matches[j]->statement.substr(3)));
400 cerr << "Trust certificate for unknown key: " << matches[j]->to_string() << '\n';
404 // except for keys we already checked
406 if(checked.find(other) != checked.end()) {
407 debug cerr << "Skipping trust certificate for already checked key: " << matches[j]->to_string() << '\n';
413 if(matches[j]->statement[1] == '+')
418 newkeys.insert(other);
426 /// Merges a public key into the database.
428 /// @param key The public key to merge.
429 void fides::merge(publickey *key) {
430 if(keys.find(key->fingerprint()) != keys.end()) {
431 debug cerr << "Key already known\n";
435 keys[key->fingerprint()] = key;
436 key->save(keydir + hexencode(key->fingerprint()));
439 /// Merges a certificate into the database.
441 /// The database is searched to find if there are certificates from the same signer
442 /// with similar statements.
443 /// If the given certificate is similar to another one in our database,
444 /// then the certificate with the newer timestamp wins and will be allowed in the database,
445 /// the older certificate will be removed.
447 /// @param cert The certificate to merge.
448 void fides::merge(certificate *cert) {
449 // TODO: check if cert is already in database
450 // TODO: check if cert obsoletes other certs
452 // If we already know this certificate, drop it.
453 if(certs.find(cert->fingerprint()) != certs.end()) {
454 debug cerr << "Certificate already known\n";
458 // If the certificate does not validate, drop it.
459 if(!cert->validate()) {
460 // TODO: this should not happen, be wary of DoS attacks
461 cerr << "Trying to merge invalid certificate: " << cert->to_string() << '\n';
465 // TODO: move these regexps to the class?
466 regexp authexp("^a[+0-] ");
467 regexp trustexp("^t[+0-] ");
468 vector<const certificate *> others;
470 // Is this an authorisation cert?
471 if(authexp.match(cert->statement)) {
472 // Find certs identical except for the +/-/0
473 // TODO: escape statement in regexp
474 others = find_certificates(cert->signer, string("^a[+0-] ") + cert->statement.substr(3) + '$');
476 if(timercmp(&others[0]->timestamp, &cert->timestamp, >)) {
477 debug cerr << "Certificate is overruled by a newer certificate\n";
480 if(timercmp(&others[0]->timestamp, &cert->timestamp, ==)) {
481 // TODO: this should not happen, be wary of DoS attacks
482 debug cerr << "Certificate has same timestamp as another timestamp!\n";
485 debug cerr << "Certificate overrules an older certificate!\n";
486 // save new cert first
487 certificate_save(cert, certdir + hexencode(cert->fingerprint()));
488 certs[cert->fingerprint()] = cert;
491 rename((certdir + hexencode(others[0]->fingerprint())).c_str(), (obsoletedir + hexencode(others[0]->fingerprint())).c_str());
492 certs.erase(others[0]->fingerprint());
498 // Is this a trust cert?
499 // TODO: it's just the same as above!
500 if(trustexp.match(cert->statement)) {
501 // Find certs identical except for the +/-/0
502 // TODO: escape statement in regexp
503 others = find_certificates(cert->signer, string("^t[+0-] ") + cert->statement.substr(3) + '$');
505 if(timercmp(&others[0]->timestamp, &cert->timestamp, >)) {
506 debug cerr << "Certificate is overruled by a newer certificate\n";
509 if(timercmp(&others[0]->timestamp, &cert->timestamp, ==)) {
510 // TODO: this should not happen, be wary of DoS attacks
511 debug cerr << "Certificate has same timestamp as another timestamp!\n";
514 debug cerr << "Certificate overrules an older certificate!\n";
516 rename((certdir + hexencode(others[0]->fingerprint())).c_str(), (obsoletedir + hexencode(others[0]->fingerprint())).c_str());
517 certs.erase(others[0]->fingerprint());
519 certs[cert->fingerprint()] = cert;
520 certificate_save(cert, certdir + hexencode(cert->fingerprint()));
525 // Did somebody sign the exact same statement twice?
526 // Could happen if there is a different, conflicting statement between this new and the corresponding old one.
527 others = find_certificates(cert->signer, string("^") + cert->statement + '$');
529 if(timercmp(&others[0]->timestamp, &cert->timestamp, >)) {
530 debug cerr << "Certificate is overruled by a newer certificate\n";
533 if(timercmp(&others[0]->timestamp, &cert->timestamp, ==)) {
534 // TODO: this should not happen, be wary of DoS attacks
535 debug cerr << "Certificate has same timestamp as another timestamp!\n";
538 debug cerr << "Certificate overrules an older certificate!\n";
540 rename((certdir + hexencode(others[0]->fingerprint())).c_str(), (obsoletedir + hexencode(others[0]->fingerprint())).c_str());
541 certs.erase(others[0]->fingerprint());
543 certs[cert->fingerprint()] = cert;
544 certificate_save(cert, certdir + hexencode(cert->fingerprint()));
548 debug cerr << "Certificate is new\n";
549 certs[cert->fingerprint()] = cert;
550 certificate_save(cert, certdir + hexencode(cert->fingerprint()));
553 /// Calculates whether a statement is allowed or denied.
555 /// @param statement The statement to calculate the authorisation values for.
556 /// @param self Will be set to 1 if we allow the statement,
557 /// 0 if we neither allowed nor denied it,
558 /// or -1 if we denied it.
559 /// @param trusted Will be positive if the majority of the trusted public keys
560 /// gave a positive authorisation, 0 if there is a tie,
561 /// or negative if the majority gave a negative authorisation.
562 /// @param all Same as trusted but for all public keys.
563 void fides::auth_stats(const std::string &statement, int &self, int &trusted, int &all) const {
564 self = trusted = all = 0;
565 vector<const certificate *> matches = find_certificates(string("^a[+0-] ") + statement + '$');
566 for(size_t i = 0; i < matches.size(); ++i) {
567 char code = matches[i]->statement[1];
573 if(matches[i]->signer == &mykey)
575 if(matches[i]->signer->trust > 0)
581 /// Tests whether the given public key is trusted.
583 /// @param key The public key to test.
584 /// @return True if the key is explicitly trusted, false otherwise.
585 bool fides::is_trusted(const publickey *key) const {
586 return key->trust > 0;
589 /// Tests whether the given public key is distrusted.
591 /// @param key The public key to test.
592 /// @return True if the key is explicitly distrusted, false otherwise.
593 bool fides::is_distrusted(const publickey *key) const {
594 return key->trust < 0;
597 /// Tests whether the given statement is allowed.
599 /// @param statement The statement to test.
600 /// @param key The public key to test.
601 /// @return True if the statement is allowed for the given key, false otherwise.
602 bool fides::is_allowed(const std::string &statement, const publickey *key) const {
603 int self, trusted, all;
606 auth_stats(hexencode(key->fingerprint()) + " " + statement, self, trusted, all);
608 auth_stats(statement, self, trusted, all);
618 /// Tests whether the given statement is denied.
620 /// @param statement The statement to test.
621 /// @param key The public key to test.
622 /// @return True if the statement is denied for the given key, false otherwise.
623 bool fides::is_denied(const std::string &statement, const publickey *key) const {
624 int self, trusted, all;
627 auth_stats(hexencode(key->fingerprint()) + " " + statement, self, trusted, all);
629 auth_stats(statement, self, trusted, all);
639 /// Creates a certificate for the given statement.
641 /// @param statement The statement to create a certificate for.
642 void fides::sign(const std::string &statement) {
643 // Try to set "latest" to now, but ensure monoticity
645 gettimeofday(&now, 0);
646 if(timercmp(&latest, &now, >=)) {
648 if(latest.tv_usec >= 1000000) {
650 latest.tv_usec -= 1000000;
656 // Create a new certificate and merge it with our database
657 merge(new certificate(&mykey, latest, statement));
660 void fides::allow(const std::string &statement, const publickey *key) {
663 full += hexencode(key->fingerprint()) + ' ';
668 void fides::dontcare(const std::string &statement, const publickey *key) {
671 full += hexencode(key->fingerprint()) + ' ';
676 void fides::deny(const std::string &statement, const publickey *key) {
679 full += hexencode(key->fingerprint()) + ' ';