www.tinc-vpn.org Git - fides/blob - lib/fides.cc

   1 /* fides.cc - Light-weight, decentralised trust and authorisation management
   2    Copyright (C) 2008-2009  Guus Sliepen <guus@tinc-vpn.org>
   3
   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.
   8
   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.
  13
  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/>.
  16 */
  17
  18 #include <iostream>
  19 #include <fstream>
  20 #include <cstdlib>
  21 #include <sys/types.h>
  22 #include <sys/stat.h>
  23 #include <unistd.h>
  24 #include <dirent.h>
  25 #include <botan/types.h>
  26 #include <botan/botan.h>
  27 #include <botan/ecdsa.h>
  28 #include <botan/look_pk.h>
  29 #include <botan/lookup.h>
  30 #include <botan/filters.h>
  31 #include <botan/sha2_32.h>
  32 #include <list>
  33
  34 #include "fides.h"
  35
  36 #ifndef FIDES_DEBUG
  37 #define FIDES_DEBUG false
  38 #endif
  39
  40 #define debug if(FIDES_DEBUG)
  41
  42 using namespace std;
  43
  44 // Global state
  45
  46 Botan::AutoSeeded_RNG fides::rng;
  47
  48 /// \class fides::publickey
  49 ///
  50 /// \brief Representation of a public key.
  51 ///
  52 /// A public key is the counterpart of a private key that is held by some entity.
  53 /// If we have a public key, we can verify signatures made by the corresponding private key.
  54 /// Thus, we can ascertain if a statement, if it has been properly signed,
  55 /// was indeed made by that entity.
  56
  57 fides::publickey::publickey(): pub(0), trust(0) {
  58 }
  59
  60 fides::publickey::~publickey() {
  61         delete pub;
  62 }
  63
  64 /// Loads a public key from a stream.
  65 //
  66 /// @param in Stream to read from.
  67 void fides::publickey::load(std::istream &in) {
  68         try {
  69                 Botan::DataSource_Stream source(in);
  70                 pub = dynamic_cast<Botan::ECDSA_PublicKey *>(Botan::X509::load_key(source));
  71         } catch(Botan::Exception &e) {
  72                 throw exception(e.what());
  73         }
  74 }
  75
  76 /// Loads a public key from a file.
  77 //
  78 /// @param filename Name of the file to read the key from.
  79 void fides::publickey::load(const std::string &filename) {
  80         ifstream in(filename.c_str());
  81         load(in);
  82 }
  83
  84 /// Saves the public key to a stream.
  85 //
  86 /// @param out Stream to write to.
  87 void fides::publickey::save(std::ostream &out) const {
  88         out << to_string();
  89 }
  90
  91 /// Saves the public key to a file.
  92 //
  93 /// @param filename Name of the file to save the key to.
  94 void fides::publickey::save(const std::string &filename) const {
  95         ofstream out(filename.c_str());
  96         save(out);
  97 }
  98
  99 /// Loads a public key from a string.
 100 //
 101 /// @param in String containing a public key in textual format.
 102 void fides::publickey::from_string(const std::string &in) {
 103         try {
 104                 Botan::DataSource_Memory source(in);
 105                 pub = dynamic_cast<Botan::ECDSA_PublicKey *>(Botan::X509::load_key(source));
 106         } catch(Botan::Exception &e) {
 107                 throw exception(e.what());
 108         }
 109 }
 110
 111 /// Write the public key to a string.
 112 //
 113 /// @return String containing the public key in textual format.
 114 string fides::publickey::to_string() const {
 115         return Botan::X509::PEM_encode(*pub);
 116 }
 117
 118 /// Get the fingerprint of the public key.
 119 //
 120 /// @param bits Number of bits from the fingerprint to return.
 121 ///             The number will be rounded down to the nearest multiple of 8.
 122 /// @return String containing the fingerprint.
 123 string fides::publickey::fingerprint(unsigned int bits) const {
 124         // TODO: find out if there is a standard way to get a hash of an ECDSA public key
 125         Botan::SHA_256 sha256;
 126         Botan::SecureVector<Botan::byte> hash = sha256.process(Botan::X509::PEM_encode(*pub));
 127         return string((const char *)hash.begin(), bits / 8);
 128 }
 129
 130 /// Verify the signature of a statement.
 131 //
 132 /// @param statement The statement. This is the data that has been signed.
 133 /// @param signature The signature of the statement.
 134 /// @return Returns true if the signature is indeed a valid signature, made by this public key, of the statement.
 135 ///         Return false otherwise.
 136 bool fides::publickey::verify(const std::string &statement, const std::string &signature) const {
 137         auto_ptr<Botan::PK_Verifier> verifier(Botan::get_pk_verifier(*pub, "EMSA1(SHA-512)"));
 138         verifier->update((const Botan::byte *)statement.data(), statement.size());
 139         Botan::SecureVector<Botan::byte> sig;
 140         sig.set((const Botan::byte *)signature.data(), signature.size());
 141         return verifier->check_signature(sig);
 142 }
 143
 144 /// \class fides::privatekey
 145 ///
 146 /// \brief Representation of a public/private keypair.
 147 ///
 148 /// With a private key we can create a signature of a statement,
 149 /// so that others who have the corresponding public key
 150 /// can ascertain that the statement was really made by us.
 151
 152 fides::privatekey::privatekey(): priv(0) {
 153 }
 154
 155 fides::privatekey::~privatekey() {
 156         delete priv;
 157         pub = 0;
 158 }
 159
 160 /// Generates a new public/private keypair.
 161 //
 162 /// @param field OID of the field to generate a key in.
 163 void fides::privatekey::generate(const std::string &field) {
 164         Botan::EC_Domain_Params domain = Botan::get_EC_Dom_Pars_by_oid(field);
 165         pub = priv = new Botan::ECDSA_PrivateKey(rng, domain);
 166 }
 167
 168 /// Generates a new public/private keypair.
 169 //
 170 /// This function uses standard NIST fields.
 171 /// @param bits Desired size of the keys.
 172 ///             Allowed values are 112, 128, 160, 192, 224, 256, 384 and 521.
 173 ///             Keys less than 160 bits are considered weak.
 174 ///             Keys greater than 224 bits are considered very strong.
 175 void fides::privatekey::generate(unsigned int bits) {
 176         switch(bits) {
 177                 case 112: return generate("1.3.132.0.6");
 178                 case 128: return generate("1.3.132.0.28");
 179                 case 160: return generate("1.3.132.0.9");
 180                 case 192: return generate("1.3.132.0.31");
 181                 case 224: return generate("1.3.132.0.32");
 182                 case 256: return generate("1.3.132.0.10");
 183                 case 384: return generate("1.3.132.0.34");
 184                 case 521: return generate("1.3.132.0.35");
 185                 default: throw exception("Unsupported number of bits for private key");
 186         }
 187 }
 188
 189 /// Loads a private key from a stream.
 190 //
 191 /// @param in Stream to read from.
 192 void fides::privatekey::load_private(std::istream &in) {
 193         try {
 194                 Botan::DataSource_Stream stream(in);
 195                 pub = priv = dynamic_cast<Botan::ECDSA_PrivateKey *>(Botan::PKCS8::load_key(stream, rng, ""));
 196         } catch(Botan::Exception &e) {
 197                 throw exception(e.what());
 198         }
 199 }
 200
 201 /// Loads a private key from a file.
 202 //
 203 /// @param filename Name of the file to read from.
 204 void fides::privatekey::load_private(const std::string &filename) {
 205         ifstream in(filename.c_str());
 206         load_private(in);
 207 }
 208
 209 /// Saves the private key to a stream.
 210 //
 211 /// @param out Stream to write to.
 212 void fides::privatekey::save_private(std::ostream &out) const {
 213         out << Botan::PKCS8::PEM_encode(*priv);
 214 }
 215
 216 /// Saves the private key to a file.
 217 //
 218 /// @param filename Name of the file to write to.
 219 void fides::privatekey::save_private(const std::string &filename) const {
 220         ofstream out(filename.c_str());
 221         save_private(out);
 222 }
 223
 224 /// Signs a statement with this private key.
 225 //
 226 /// @param statement The statement that is to be signed.
 227 /// @return A string containing the signature.
 228 string fides::privatekey::sign(const std::string &statement) const {
 229         auto_ptr<Botan::PK_Signer> signer(Botan::get_pk_signer(*priv, "EMSA1(SHA-512)"));
 230         Botan::SecureVector<Botan::byte> sig = signer->sign_message((const Botan::byte *)statement.data(), statement.size(), rng);
 231         return string((const char *)sig.begin(), (size_t)sig.size());
 232 }
 233
 234 // Base64 and hex encoding/decoding functions
 235
 236 /// Hexadecimal encode data.
 237 //
 238 /// @param in A string containing raw data.
 239 /// @return A string containing the hexadecimal encoded data.
 240 string fides::hexencode(const std::string &in) {
 241         Botan::Pipe pipe(new Botan::Hex_Encoder);
 242         pipe.process_msg((Botan::byte *)in.data(), in.size());
 243         return pipe.read_all_as_string();
 244 }
 245
 246 /// Decode hexadecimal data.
 247 //
 248 /// @param in A string containing hexadecimal encoded data.
 249 /// @return A string containing the raw data.
 250 string fides::hexdecode(const std::string &in) {
 251         Botan::Pipe pipe(new Botan::Hex_Decoder);
 252         pipe.process_msg((Botan::byte *)in.data(), in.size());
 253         return pipe.read_all_as_string();
 254 }
 255
 256 /// Base-64 encode data.
 257 //
 258 /// @param in A string containing raw data.
 259 /// @return A string containing the base-64 encoded data.
 260 string fides::b64encode(const std::string &in) {
 261         Botan::Pipe pipe(new Botan::Base64_Encoder);
 262         pipe.process_msg((Botan::byte *)in.data(), in.size());
 263         return pipe.read_all_as_string();
 264 }
 265
 266 /// Decode base-64 data.
 267 //
 268 /// @param in A string containing base-64 encoded data.
 269 /// @return A string containing the raw data.
 270 string fides::b64decode(const std::string &in) {
 271         Botan::Pipe pipe(new Botan::Base64_Decoder);
 272         pipe.process_msg((Botan::byte *)in.data(), in.size());
 273         return pipe.read_all_as_string();
 274 }
 275
 276 /// \class fides::certificate
 277 ///
 278 /// \brief Representation of a certificate.
 279
 280 /// Construct a certificate from elements of an already existing certificate.
 281 //
 282 /// @param key        Public key used to sign the certificate.
 283 /// @param timestamp  Timestamp of the certificate.
 284 /// @param statement  Statement of the certificate.
 285 /// @param signature  Signature of the certificate.
 286 fides::certificate::certificate(const publickey *key, struct timeval timestamp, const std::string &statement, const std::string &signature): signer(key), timestamp(timestamp), statement(statement), signature(signature) {}
 287
 288 /// Verifies the signature of the certificate.
 289 //
 290 /// @return True if the signature is valid, false otherwise.
 291 bool fides::certificate::validate() const {
 292         string data = signer->fingerprint(256);
 293         data += string((const char *)&timestamp, sizeof timestamp);
 294         data += statement;
 295         return signer->verify(data, signature);
 296 }
 297
 298 /// Construct a new certificate and sign it with the private key.
 299 //
 300 /// @param key        Private key to sign the certificate with.
 301 /// @param timestamp  Timestamp of the certificate.
 302 /// @param statement  Statement of the certificate.
 303 fides::certificate::certificate(const privatekey *key, struct timeval timestamp, const std::string &statement): signer(key), timestamp(timestamp), statement(statement) {
 304         string data = signer->fingerprint(256);
 305         data += string((const char *)&timestamp, sizeof timestamp);
 306         data += statement;
 307         signature = key->sign(data);
 308 }
 309
 310 /// Get the fingerprint of this certificate.
 311 //
 312 /// @param bits Number of bits from the fingerprint to return.
 313 ///             The number will be rounded down to the nearest multiple of 8.
 314 /// @return String containing the fingerprint.
 315 string fides::certificate::fingerprint(unsigned int bits) const {
 316         return signature.substr(signature.size() - bits / 8);
 317 }
 318
 319 /// Write the certificate to a string.
 320 //
 321 /// @return String containing the certificate in textual format.
 322 string fides::certificate::to_string() const {
 323         string data = fides::hexencode(signer->fingerprint());
 324         data += ' ';
 325         char ts[100];
 326         snprintf(ts, sizeof ts, "%lu.%06lu", timestamp.tv_sec, timestamp.tv_usec);
 327         data += ts;
 328         data += ' ';
 329         data += fides::b64encode(signature);
 330         data += ' ';
 331         data += statement;
 332         return data;
 333 }
 334
 335 // Utility functions
 336
 337 /// Return the names of all the files in a directory.
 338 //
 339 /// @param path Directory to search for files.
 340 /// @return A vector of strings with the name of each file in the directory.
 341 ///         The filename does not contain the leading path.
 342 static vector<string> dirlist(const std::string &path) {
 343         vector<string> files;
 344
 345         DIR *dir = opendir(path.c_str());
 346         if(!dir)
 347                 return files;
 348
 349         struct dirent entry, *result = &entry;
 350
 351         while(result) {
 352                 readdir_r(dir, &entry, &result);
 353                 if(!result)
 354                         break;
 355                 struct stat st;
 356                 if(result->d_type == DT_UNKNOWN) {
 357                         if(stat((path + "/" + result->d_name).c_str(), &st))
 358                                 continue;
 359                         if(S_ISREG(st.st_mode))
 360                                 files.push_back(result->d_name);
 361                 } else if(result->d_type == DT_REG) {
 362                         files.push_back(result->d_name);
 363                 }
 364         }
 365
 366         closedir(dir);
 367
 368         return files;
 369 }
 370
 371 /// Saves a certificate to a file.
 372 //
 373 /// @param cert      Certificate to save.
 374 /// @param filename  File to save the certificate to.
 375 void fides::certificate_save(const certificate *cert, const std::string &filename) const {
 376         ofstream file(filename.c_str());
 377         file << cert->to_string() << '\n';
 378 }
 379
 380 /// Loads a certificate from a file.
 381 //
 382 /// @param filename  File to save the certificate to.
 383 /// @return          The certificate.
 384 fides::certificate *fides::certificate_load(const std::string &filename) {
 385         ifstream file(filename.c_str());
 386         string data;
 387         getline(file, data);
 388         return certificate_from_string(data);
 389 }
 390
 391 /// Loads a certificate from a string.
 392 //
 393 /// @param data  String containing the certificate in textual form.
 394 /// @return      The certificate.
 395 fides::certificate *fides::certificate_from_string(const std::string &data) {
 396         size_t b, e;
 397         e = data.find(' ', 0);
 398         if(e == string::npos)
 399                 throw exception("Invalid certificate");
 400         string fingerprint = hexdecode(data.substr(0, e));
 401         const publickey *signer = find_key(fingerprint);
 402         if(!signer)
 403                 throw exception("Unknown public key");
 404         b = e + 1;
 405         e = data.find('.', b);
 406         if(e == string::npos)
 407                 throw exception("Invalid certificate");
 408         struct timeval timestamp;
 409         timestamp.tv_sec = atol(data.c_str() + b);
 410         b = e + 1;
 411         timestamp.tv_usec = atol(data.c_str() + b);
 412         e = data.find(' ', b);
 413         if(e == string::npos)
 414                 throw exception("Invalid certificate");
 415         b = e + 1;
 416         e = data.find(' ', b);
 417         if(e == string::npos)
 418                 throw exception("Invalid certificate");
 419         string signature = fides::b64decode(data.substr(b, e - b));
 420         b = e + 1;
 421         string statement = data.substr(b);
 422
 423         return new certificate(signer, timestamp, statement, signature);
 424 }
 425
 426 /// \class fides
 427 ///
 428 /// \brief Interaction with a Fides database.
 429 ///
 430 /// A fides object manages a database of public keys and certificates.
 431 /// New certificates can be created, certificates can be imported and exported,
 432 /// and queries can be done on the database.
 433
 434
 435 /// Creates a new handle on a Fides database.
 436 //
 437 /// Will load the private key, known public keys and certificates.
 438 /// After that it will calculate the trust value of all keys.
 439 ///
 440 /// @param dir Directory where Fides stores the keys and certificates.
 441 ///            If no directory is specified, the following environment variables
 442 ///            are used, in the given order:
 443 ///            - \$FIDES_HOME
 444 ///            - \$HOME/.fides
 445 ///            - \$WPD/.fides
 446 fides::fides(const std::string &dir): homedir(dir) {
 447         debug cerr << "Fides initialising\n";
 448
 449         // Set homedir to provided directory, or $FIDES_HOME, or $HOME/.fides, or as a last resort $PWD/.fides
 450         if(homedir.empty())
 451                 homedir = getenv("FIDES_HOME") ?: "";
 452         if(homedir.empty()) {
 453                 char cwd[PATH_MAX];
 454                 homedir = getenv("HOME") ?: getcwd(cwd, sizeof cwd);
 455                 homedir += "/.fides";
 456         }
 457
 458         // Derived directories
 459         homedir += '/';
 460         certdir = homedir + "certs/";
 461         keydir = homedir + "keys/";
 462         obsoletedir = homedir + ".obsolete_certs/";
 463
 464         // Ensure the homedir and its subdirectories exist
 465         mkdir(homedir.c_str(), 0700);
 466         mkdir(certdir.c_str(), 0700);
 467         mkdir(keydir.c_str(), 0700);
 468         mkdir(obsoletedir.c_str(), 0700);
 469
 470         try {
 471                 mykey.load_private(homedir + "priv");
 472                 firstrun = false;
 473         } catch(fides::exception &e) {
 474                 cerr << "Fides generating keypair\n";
 475                 mykey.generate();
 476                 mykey.save_private(homedir + "priv");
 477                 mykey.save(keydir + hexencode(mykey.fingerprint()));
 478                 firstrun = true;
 479         }
 480         vector<string> files = dirlist(keydir);
 481         for(size_t i = 0; i < files.size(); ++i) {
 482                 debug cerr << "Loading key " << files[i] << '\n';
 483
 484                 publickey *key = new publickey();
 485                 key->load(keydir + files[i]);
 486                 keys[hexdecode(files[i])] = key;
 487         }
 488
 489         keys[mykey.fingerprint()] = &mykey;
 490
 491         files = dirlist(certdir);
 492         for(size_t i = 0; i < files.size(); ++i) {
 493                 debug cerr << "Loading certificate " << files[i] << '\n';
 494                 certificate *cert = certificate_load(certdir + files[i]);
 495                 if(false && !cert->validate()) {
 496                         cerr << "Bad certificate in database: " << cert->to_string() << '\n';
 497                         continue;
 498                 }
 499                 certs[hexdecode(files[i])] = cert;
 500         }
 501
 502         // TODO: save and load this value
 503         latest.tv_sec = 0;
 504         latest.tv_usec = 0;
 505
 506         update_trust();
 507 }
 508
 509 fides::~fides() {
 510         debug cerr << "Fides exitting\n";
 511         for(map<string, certificate *>::const_iterator i = certs.begin(); i != certs.end(); ++i)
 512                 delete i->second;
 513         for(map<string, publickey *>::const_iterator i = keys.begin(); i != keys.end(); ++i)
 514                 if(i->second != &mykey)
 515                         delete i->second;
 516 }
 517
 518 /// Checks the validaty of all certificates.
 519 //
 520 /// @return True if all known certificates are valid, false otherwise.
 521 bool fides::fsck() const {
 522         int errors = 0;
 523
 524         for(map<string, certificate *>::const_iterator i = certs.begin(); i != certs.end(); ++i) {
 525                 if(!i->second->validate()) {
 526                         cerr << "Validation of certificate failed: " << i->second->to_string() << '\n';
 527                         errors++;
 528                 }
 529         }
 530
 531         cerr << errors << " errors in " << certs.size() << " certificates\n";
 532         return !errors;
 533 }
 534
 535 /// Returns the base directory used by Fides.
 536 //
 537 /// @return The home directory.
 538 string fides::get_homedir() const {
 539         return homedir;
 540 }
 541
 542 /// Tests whether this is the first time Fides has run and has generated new keys.
 543 //
 544 /// @return True if this is the first time, false otherwise.
 545 bool fides::is_firstrun() const {
 546         return firstrun;
 547 }
 548
 549 /// Find the public key corresponding to a given fingerprint.
 550 //
 551 /// @param fingerprint String containing a fingerprint.
 552 /// @return Pointer to the public key corresponding to the fingerprint, or NULL if it was not found.
 553 fides::publickey *fides::find_key(const std::string &fingerprint) const {
 554         map<string, publickey *>::const_iterator i;
 555         i = keys.find(fingerprint);
 556         if(i != keys.end())
 557                 return i->second;
 558         else
 559                 return 0;
 560 }
 561
 562 /// Find all certificates from a give public key and that match a regular expression.
 563 //
 564 /// @param signer Public key to match certificates to.
 565 /// @param regex  Regular expression to match the statement of each certificate to.
 566 /// @return A vector of certificates that match the criteria.
 567 vector<const fides::certificate *> fides::find_certificates(const publickey *signer, const std::string &regex) const {
 568         vector<const certificate *> found;
 569         map<string, certificate *>::const_iterator i;
 570         regexp regexp(regex);
 571         for(i = certs.begin(); i != certs.end(); ++i) {
 572                 if(!i->second) {
 573                         cerr << "No certificate for " << hexencode(i->first) << '\n';
 574                         continue;
 575                 }
 576                 if(i->second->signer == signer)
 577                         if(regexp.match(i->second->statement))
 578                                 found.push_back(i->second);
 579         }
 580         return found;
 581 }
 582
 583 /// Find all certificates that match a regular expression.
 584 //
 585 /// @param regex  Regular expression to match the statement of each certificate to.
 586 /// @return A vector of certificates that match the criteria.
 587 vector<const fides::certificate *> fides::find_certificates(const std::string &regex) const {
 588         vector<const certificate *> found;
 589         map<string, certificate *>::const_iterator i;
 590         regexp regexp(regex);
 591         for(i = certs.begin(); i != certs.end(); ++i)
 592                 if(regexp.match(i->second->statement))
 593                         found.push_back(i->second);
 594         return found;
 595 }
 596
 597 /// Find all certificates from a give public key.
 598 //
 599 /// @param signer Public key to match certificates to.
 600 /// @return A vector of certificates that match the criteria.
 601 vector<const fides::certificate *> fides::find_certificates(const publickey *signer) const {
 602         vector<const certificate *> found;
 603         map<string, certificate *>::const_iterator i;
 604         for(i = certs.begin(); i != certs.end(); ++i)
 605                 if(i->second->signer == signer)
 606                         found.push_back(i->second);
 607         return found;
 608 }
 609
 610 /// Import public keys and certificates from a stream.
 611 //
 612 /// @param in Stream to read from.
 613 void fides::import_all(std::istream &in) {
 614         string line, pem;
 615         bool is_pem = false;
 616
 617         while(getline(in, line)) {
 618                 if(line.empty())
 619                         continue;
 620
 621                 if(is_pem || !line.compare(0, 11, "-----BEGIN ")) {
 622                         pem += line + '\n';
 623                         if(!line.compare(0, 9, "-----END ")) {
 624                                 fides::publickey *key = new publickey();
 625                                 key->from_string(pem);
 626                                 debug cerr << "Imported key " << hexencode(key->fingerprint()) << '\n';
 627                                 merge(key);
 628                                 is_pem = false;
 629                         } else {
 630                                 is_pem = true;
 631                         }
 632                         continue;
 633                 }
 634
 635                 fides::certificate *cert = certificate_from_string(line);
 636                 debug cerr << "Importing certificate " << hexencode(cert->fingerprint()) << '\n';
 637                 merge(cert);
 638         }
 639 }
 640
 641 /// Export all public keys and certificates to a stream.
 642 //
 643 /// @param out Stream to write to.
 644 void fides::export_all(std::ostream &out) const {
 645         for(map<string, publickey *>::const_iterator i = keys.begin(); i != keys.end(); ++i)
 646                 out << i->second->to_string();
 647         for(map<string, certificate *>::const_iterator i = certs.begin(); i != certs.end(); ++i)
 648                 out << i->second->to_string() << '\n';
 649 }
 650
 651 /// Trust a public key.
 652 //
 653 /// This creates a certificate that says that we trust the given public key.
 654 /// If a key is trusted, then authorisation certificates from that key are taken into account
 655 /// when calling functions such as fides::is_allowed().
 656 ///
 657 /// @param key Public key to trust.
 658 void fides::trust(const publickey *key) {
 659         string full = "t+ " + hexencode(key->fingerprint());
 660         sign(full);
 661 }
 662
 663 /// Distrust a public key.
 664 //
 665 /// This creates a certificate that says that we distrust the given public key.
 666 /// If a key is distrusted, then authorisation certificates from that key are not taken into account
 667 /// when calling functions such as fides::is_allowed().
 668 ///
 669 /// @param key Public key to trust.
 670 void fides::distrust(const publickey *key) {
 671         string full = "t- " + hexencode(key->fingerprint());
 672         sign(full);
 673 }
 674
 675 /// Don't care about a public key.
 676 //
 677 /// This creates a certificate that says that we neither trust nor distrust the given public key.
 678 /// This key and certificates created by it are then treated as if we have never trusted nor distrusted this key.
 679 ///
 680 /// @param key Public key to trust.
 681 void fides::dctrust(const publickey *key) {
 682         string full = "t0 " + hexencode(key->fingerprint());
 683         sign(full);
 684 }
 685
 686 /// Recalculate the trust value of all known public keys.
 687 void fides::update_trust() {
 688         // clear trust on all keys
 689         for(map<string, publickey *>::const_iterator i = keys.begin(); i != keys.end(); ++i)
 690                 i->second->trust = 0;
 691
 692         // Start by checking all trust certificates from ourself.
 693         // If another key is positively or negatively trusted, update its trust score
 694         // and add it to the the list of new keys to check.
 695         // Then add our own key to the list of already checked keys.
 696         // Then check all the trust certificates of those on the tocheck list, etc.
 697         // Already checked keys are never updated anymore (TODO: is that smart?)
 698         // Certificates of keys with a zero or negative trust score are not processed.
 699
 700         set<publickey *> checked;
 701         set<publickey *> tocheck;
 702         set<publickey *> newkeys;
 703         set<publickey *>::iterator i;
 704
 705         mykey.trust = 3;
 706         tocheck.insert(&mykey);
 707
 708         while(tocheck.size()) {
 709                 // add
 710                 checked.insert(tocheck.begin(), tocheck.end());
 711                 newkeys.clear();
 712
 713                 // loop over all keys whose certificates need to be checked
 714
 715                 for(i = tocheck.begin(); i != tocheck.end(); ++i) {
 716                         debug cerr << "Trust for key " << hexencode((*i)->fingerprint()) << " set to " << (*i)->trust << '\n';
 717
 718                         // except if this key is not trusted
 719
 720                         if((*i)->trust <= 0)
 721                                 continue;
 722
 723                         // find all non-zero trust certificates of this key
 724
 725                         vector<const certificate *> matches = find_certificates(*i, "^t[+-] ");
 726
 727                         // update trust value of those keys
 728
 729                         for(size_t j = 0; j < matches.size(); j++) {
 730                                 publickey *other = find_key(hexdecode(matches[j]->statement.substr(3)));
 731
 732                                 if(!other) {
 733                                         cerr << "Trust certificate for unknown key: " << matches[j]->to_string() << '\n';
 734                                         continue;
 735                                 }
 736
 737                                 // except for keys we already checked
 738
 739                                 if(checked.find(other) != checked.end()) {
 740                                         debug cerr << "Skipping trust certificate for already checked key: " << matches[j]->to_string() << '\n';
 741                                         continue;
 742                                 }
 743
 744                                 // update trust
 745
 746                                 if(matches[j]->statement[1] == '+')
 747                                         other->trust++;
 748                                 else
 749                                         other->trust--;
 750
 751                                 newkeys.insert(other);
 752                         }
 753                 }
 754
 755                 tocheck = newkeys;
 756         }
 757 }
 758
 759 /// Merges a public key into the database.
 760 //
 761 /// @param key The public key to merge.
 762 void fides::merge(publickey *key) {
 763         if(keys.find(key->fingerprint()) != keys.end()) {
 764                 debug cerr << "Key already known\n";
 765                 return;
 766         }
 767
 768         keys[key->fingerprint()] = key;
 769         key->save(keydir + hexencode(key->fingerprint()));
 770 }
 771
 772 /// Merges a certificate into the database.
 773 //
 774 /// The database is searched to find if there are certificates from the same signer
 775 /// with similar statements.
 776 /// If the given certificate is similar to another one in our database,
 777 /// then the certificate with the newer timestamp wins and will be allowed in the database,
 778 /// the older certificate will be removed.
 779 ///
 780 /// @param cert The certificate to merge.
 781 void fides::merge(certificate *cert) {
 782         // TODO: check if cert is already in database
 783         // TODO: check if cert obsoletes other certs
 784
 785         // If we already know this certificate, drop it.
 786         if(certs.find(cert->fingerprint()) != certs.end()) {
 787                 debug cerr << "Certificate already known\n";
 788                 return;
 789         }
 790
 791         // If the certificate does not validate, drop it.
 792         if(!cert->validate()) {
 793                 // TODO: this should not happen, be wary of DoS attacks
 794                 cerr << "Trying to merge invalid certificate: " << cert->to_string() << '\n';
 795                 return;
 796         }
 797
 798         // TODO: move these regexps to the class?
 799         regexp authexp("^a[+0-] ");
 800         regexp trustexp("^t[+0-] ");
 801         vector<const certificate *> others;
 802
 803         // Is this an authorisation cert?
 804         if(authexp.match(cert->statement)) {
 805                 // Find certs identical except for the +/-/0
 806                 // TODO: escape statement in regexp
 807                 others = find_certificates(cert->signer, string("^a[+0-] ") + cert->statement.substr(3) + '$');
 808                 if(others.size()) {
 809                         if(timercmp(&others[0]->timestamp, &cert->timestamp, >)) {
 810                                 debug cerr << "Certificate is overruled by a newer certificate\n";
 811                                 return;
 812                         }
 813                         if(timercmp(&others[0]->timestamp, &cert->timestamp, ==)) {
 814                                 // TODO: this should not happen, be wary of DoS attacks
 815                                 debug cerr << "Certificate has same timestamp as another timestamp!\n";
 816                                 return;
 817                         }
 818                         debug cerr << "Certificate overrules an older certificate!\n";
 819                         // save new cert first
 820                         certificate_save(cert, certdir + hexencode(cert->fingerprint()));
 821                         certs[cert->fingerprint()] = cert;
 822
 823                         // delete old one
 824                         rename((certdir + hexencode(others[0]->fingerprint())).c_str(), (obsoletedir + hexencode(others[0]->fingerprint())).c_str());
 825                         certs.erase(others[0]->fingerprint());
 826                         delete others[0];
 827                         return;
 828                 }
 829         }
 830
 831         // Is this a trust cert?
 832         // TODO: it's just the same as above!
 833         if(trustexp.match(cert->statement)) {
 834                 // Find certs identical except for the +/-/0
 835                 // TODO: escape statement in regexp
 836                 others = find_certificates(cert->signer, string("^t[+0-] ") + cert->statement.substr(3) + '$');
 837                 if(others.size()) {
 838                         if(timercmp(&others[0]->timestamp, &cert->timestamp, >)) {
 839                                 debug cerr << "Certificate is overruled by a newer certificate\n";
 840                                 return;
 841                         }
 842                         if(timercmp(&others[0]->timestamp, &cert->timestamp, ==)) {
 843                                 // TODO: this should not happen, be wary of DoS attacks
 844                                 debug cerr << "Certificate has same timestamp as another timestamp!\n";
 845                                 return;
 846                         }
 847                         debug cerr << "Certificate overrules an older certificate!\n";
 848                         // delete old one
 849                         rename((certdir + hexencode(others[0]->fingerprint())).c_str(), (obsoletedir + hexencode(others[0]->fingerprint())).c_str());
 850                         certs.erase(others[0]->fingerprint());
 851                         delete others[0];
 852                         certs[cert->fingerprint()] = cert;
 853                         certificate_save(cert, certdir + hexencode(cert->fingerprint()));
 854                         return;
 855                 }
 856         }
 857
 858         // Did somebody sign the exact same statement twice?
 859         // Could happen if there is a different, conflicting statement between this new and the corresponding old one.
 860         others = find_certificates(cert->signer, string("^") + cert->statement + '$');
 861         if(others.size()) {
 862                 if(timercmp(&others[0]->timestamp, &cert->timestamp, >)) {
 863                         debug cerr << "Certificate is overruled by a newer certificate\n";
 864                         return;
 865                 }
 866                 if(timercmp(&others[0]->timestamp, &cert->timestamp, ==)) {
 867                         // TODO: this should not happen, be wary of DoS attacks
 868                         debug cerr << "Certificate has same timestamp as another timestamp!\n";
 869                         return;
 870                 }
 871                 debug cerr << "Certificate overrules an older certificate!\n";
 872                 // delete old one
 873                 rename((certdir + hexencode(others[0]->fingerprint())).c_str(), (obsoletedir + hexencode(others[0]->fingerprint())).c_str());
 874                 certs.erase(others[0]->fingerprint());
 875                 delete others[0];
 876                 certs[cert->fingerprint()] = cert;
 877                 certificate_save(cert, certdir + hexencode(cert->fingerprint()));
 878                 return;
 879         }
 880
 881         debug cerr << "Certificate is new\n";
 882         certs[cert->fingerprint()] = cert;
 883         certificate_save(cert, certdir + hexencode(cert->fingerprint()));
 884 }
 885
 886 /// Calculates whether a statement is allowed or denied.
 887 //
 888 /// @param statement The statement to calculate the authorisation values for.
 889 /// @param self      Will be set to 1 if we allow the statement,
 890 ///                  0 if we neither allowed nor denied it,
 891 ///                  or -1 if we denied it.
 892 /// @param trusted   Will be positive if the majority of the trusted public keys
 893 ///                  gave a positive authorisation, 0 if there is a tie,
 894 ///                  or negative if the majority gave a negative authorisation.
 895 /// @param all       Same as trusted but for all public keys.
 896 void fides::auth_stats(const std::string &statement, int &self, int &trusted, int &all) const {
 897         self = trusted = all = 0;
 898         vector<const certificate *> matches = find_certificates(string("^a[+0-] ") + statement + '$');
 899         for(size_t i = 0; i < matches.size(); ++i) {
 900                 char code = matches[i]->statement[1];
 901                 int diff = 0;
 902                 if(code == '+')
 903                         diff = 1;
 904                 else if(code == '-')
 905                         diff = -1;
 906                 if(matches[i]->signer == &mykey)
 907                         self += diff;
 908                 if(matches[i]->signer->trust > 0)
 909                         trusted += diff;
 910                 all += diff;
 911         }
 912 }
 913
 914 /// Tests whether the given public key is trusted.
 915 //
 916 /// @param key The public key to test.
 917 /// @return True if the key is explicitly trusted, false otherwise.
 918 bool fides::is_trusted(const publickey *key) const {
 919         return key->trust > 0;
 920 }
 921
 922 /// Tests whether the given public key is distrusted.
 923 //
 924 /// @param key The public key to test.
 925 /// @return True if the key is explicitly distrusted, false otherwise.
 926 bool fides::is_distrusted(const publickey *key) const {
 927         return key->trust < 0;
 928 }
 929
 930 /// Tests whether the given statement is allowed.
 931 //
 932 /// @param statement The statement to test.
 933 /// @param key       The public key to test.
 934 /// @return True if the statement is allowed for the given key, false otherwise.
 935 bool fides::is_allowed(const std::string &statement, const publickey *key) const {
 936         int self, trusted, all;
 937
 938         if(key)
 939                 auth_stats(hexencode(key->fingerprint()) + " " + statement, self, trusted, all);
 940         else
 941                 auth_stats(statement, self, trusted, all);
 942
 943         if(self)
 944                 return self > 0;
 945         else if(trusted)
 946                 return trusted > 0;
 947         else
 948                 return false;
 949 }
 950
 951 /// Tests whether the given statement is denied.
 952 //
 953 /// @param statement The statement to test.
 954 /// @param key       The public key to test.
 955 /// @return True if the statement is denied for the given key, false otherwise.
 956 bool fides::is_denied(const std::string &statement, const publickey *key) const {
 957         int self, trusted, all;
 958
 959         if(key)
 960                 auth_stats(hexencode(key->fingerprint()) + " " + statement, self, trusted, all);
 961         else
 962                 auth_stats(statement, self, trusted, all);
 963
 964         if(self)
 965                 return self < 0;
 966         else if(trusted)
 967                 return trusted < 0;
 968         else
 969                 return false;
 970 }
 971
 972 /// Creates a certificate for the given statement.
 973 //
 974 /// @param statement The statement to create a certificate for.
 975 void fides::sign(const std::string &statement) {
 976         // Try to set "latest" to now, but ensure monoticity
 977         struct timeval now;
 978         gettimeofday(&now, 0);
 979         if(timercmp(&latest, &now, >=)) {
 980                 latest.tv_usec++;
 981                 if(latest.tv_usec >= 1000000) {
 982                         latest.tv_sec++;
 983                         latest.tv_usec -= 1000000;
 984                 }
 985         } else {
 986                 latest = now;
 987         }
 988
 989         // Create a new certificate and merge it with our database
 990         merge(new certificate(&mykey, latest, statement));
 991 }
 992
 993 void fides::allow(const std::string &statement, const publickey *key) {
 994         string full = "a+ ";
 995         if(key)
 996                 full += hexencode(key->fingerprint()) + ' ';
 997         full += statement;
 998         sign(full);
 999 }
1000
1001 void fides::dontcare(const std::string &statement, const publickey *key) {
1002         string full = "a0 ";
1003         if(key)
1004                 full += hexencode(key->fingerprint()) + ' ';
1005         full += statement;
1006         sign(full);
1007 }
1008
1009 void fides::deny(const std::string &statement, const publickey *key) {
1010         string full = "a- ";
1011         if(key)
1012                 full += hexencode(key->fingerprint()) + ' ';
1013         full += statement;
1014         sign(full);
1015 }
1016