design.mdwn

   1 Assumptions
   2 ===========
   3
   4 Let us consider an individual's public keyring as an unordered set of
   5 public OpenPGP keys.
   6
   7 We assume there probably exists at least one subset of public keys in
   8 this keyring that identifies it, i.e. no other individual's keyring
   9 contain the same subset of public keys. This unproven assumption is
  10 the basis for any subsequent design thought about parcimonie.
  11
  12 It is generally considered good practice to refresh such public keys
  13 from public keyservers on a regular basis, notably since public
  14 OpenPGP keys can be compromised and thus revoked.
  15
  16 The usual way to refresh a public keyring is to run the `gpg
  17 --refresh-keys` command that queries the configured keyserver for
  18 updates of every public key stored in the to-be-refreshed keyring.
  19
  20 Combined with the identifying subset assumption, this "query all keys
  21 at a time" way of refreshing a keyring might disclose private
  22 information to an adversary.
  23
  24 The adversary
  25 =============
  26
  27 Network-wise we assume the same type of threat that Tor does: an
  28 non-global adversary who has full control over the network traffic of
  29 some fractions of the Internet.
  30
  31 OpenPGP keyservers administrators are in a privileged position to
  32 observe public keys requests.
  33
  34 To put it short, the rest of this document will call "the adversary"
  35 anyone able to monitor a given individual's connections to her
  36 configured OpenPGP keyserver(s) on a regular basis.
  37
  38 The adversary is able to establish the identifying subset <->
  39 individual.
  40 XXX: explain why/how the adversary may be able to do so.
  41
  42 Threats
  43 =======
  44
  45 Using Tor
  46 ---------
  47
  48 (application-level leakage)
  49
  50 The adversary gains knowledge of the rest of the keyring.
  51
  52 Not using Tor
  53 -------------
  54
  55 (IP-level + application-level leakage)
  56
  57 The adversary gains knowledge of the rest of the keyring + user location.
  58
  59 Possible workarounds
  60 ====================
  61
  62 Greatly increase the cost of correlating every key update.
  63
  64 parcimonie refreshes one key at a time, over Tor; between every key
  65 update it sleeps a random amount of time, long enough for the
  66 previously used Tor circuit to expire.
  67
  68 Refresh rate
  69 ============
  70
  71 parcimonie sleeps a random amount of time between every key fetch;
  72
  73 - the longer the delay is, the longer it takes for a published key
  74   update (e.g. revocation certificate) to become locally available
  75 - the shorter the delay is, the cheaper a correlation attack is
  76
  77 this lapse time is computed in function of the number of public keys
  78 in the keyring:
  79
  80    if rand(2 * (seconds in a week / number of pubkeys)) >= MaxCircuitDirtiness:
  81        rand(2 * (seconds in a week / number of pubkeys))
  82    else:
  83        MaxCircuitDirtiness + rand(MaxCircuitDirtiness)
  84
  85 Note that the MaxCircuitDirtiness value is 10 minutes in current Tor.
  86
  87 Examples:
  88   - 50  public keys -> average lapse time =~ 200 min.
  89   - 500 public keys -> average lapse time =~ 20 min.
  90   - 5000 public keys -> lapse time = 10 min. + rand(10 min.)
  91   - 50000 public keys -> lapse time = 10 min. + rand(10 min.)
  92
  93 Feedback to the user
  94 ====================
  95
  96 The parcimonie daemon sends a D-Bus signal before and after every key
  97 fetch attempt. The applet registers to this signal and displays status
  98 information accordingly.