Pileus Git - ~andy/sunrise/blob - www-client/torbrowser/files/12.0/0012-Randomize-HTTP-request-order-and-pipeline-depth.patch

   1 From 6147cea4de151dade922b3c2787016f70c222458 Mon Sep 17 00:00:00 2001
   2 From: Mike Perry <mikeperry-git@torproject.org>
   3 Date: Tue, 24 Apr 2012 17:21:45 -0700
   4 Subject: [PATCH 12/16] Randomize HTTP request order and pipeline depth.
   5
   6 This is an experimental defense against
   7 http://lorre.uni.lu/~andriy/papers/acmccs-wpes11-fingerprinting.pdf
   8
   9 See:
  10 https://blog.torproject.org/blog/experimental-defense-website-traffic-fingerprinting
  11
  12 This defense has been improved since that blog post to additionally randomize
  13 the order and concurrency of non-pipelined HTTP requests.
  14 ---
  15  netwerk/protocol/http/nsHttpConnectionMgr.cpp |  133 ++++++++++++++++++++++++-
  16  netwerk/protocol/http/nsHttpConnectionMgr.h   |    5 +
  17  2 files changed, 133 insertions(+), 5 deletions(-)
  18
  19 diff --git a/netwerk/protocol/http/nsHttpConnectionMgr.cpp b/netwerk/protocol/http/nsHttpConnectionMgr.cpp
  20 index 6e1099d..3eec5b3 100644
  21 --- a/netwerk/protocol/http/nsHttpConnectionMgr.cpp
  22 +++ b/netwerk/protocol/http/nsHttpConnectionMgr.cpp
  23 @@ -100,6 +100,12 @@ nsHttpConnectionMgr::nsHttpConnectionMgr()
  24      mCT.Init();
  25      mAlternateProtocolHash.Init(16);
  26      mSpdyPreferredHash.Init();
  27 +
  28 +    nsresult rv;
  29 +    mRandomGenerator = do_GetService("@mozilla.org/security/random-generator;1", &rv);
  30 +    if (NS_FAILED(rv)) {
  31 +        mRandomGenerator = nsnull;
  32 +    }
  33  }
  34
  35  nsHttpConnectionMgr::~nsHttpConnectionMgr()
  36 @@ -353,8 +359,12 @@ nsHttpConnectionMgr::AddTransactionToPipeline(nsHttpPipeline *pipeline)
  37          nsConnectionEntry *ent = mCT.Get(ci->HashKey());
  38          if (ent) {
  39              // search for another request to pipeline...
  40 -            PRInt32 i, count = ent->mPendingQ.Length();
  41 -            for (i=0; i<count; ++i) {
  42 +            PRInt32 i, h, count = ent->mPendingQ.Length();
  43 +            PRInt32* ind = new PRInt32[count];
  44 +            ShuffleRequestOrder((PRUint32*)ind, (PRUint32)count);
  45 +
  46 +            for (h=0; h<count; ++h) {
  47 +                i = ind[h]; // random request sequence
  48                  nsHttpTransaction *trans = ent->mPendingQ[i];
  49                  if (trans->Caps() & NS_HTTP_ALLOW_PIPELINING) {
  50                      pipeline->AddTransaction(trans);
  51 @@ -365,6 +375,8 @@
  52                      break;
  53                  }
  54              }
  55 +
  56 +            delete [] ind;
  57          }
  58      }
  59  }
  60 @@ -898,12 +908,17 @@ nsHttpConnectionMgr::ProcessPendingQForEntry(nsConnectionEntry *ent)
  61
  62      ProcessSpdyPendingQ(ent);
  63
  64 -    PRUint32 i, count = ent->mPendingQ.Length();
  65 +    PRUint32 h, i = 0, count = ent->mPendingQ.Length();
  66      if (count > 0) {
  67          LOG(("  pending-count=%u\n", count));
  68          nsHttpTransaction *trans = nsnull;
  69          nsHttpConnection *conn = nsnull;
  70 -        for (i = 0; i < count; ++i) {
  71 +
  72 +        PRUint32* ind = new PRUint32[count];
  73 +        ShuffleRequestOrder(ind, count);
  74 +
  75 +        for (h=0; h<count; ++h) {
  76 +            i = ind[h]; // random request sequence
  77              trans = ent->mPendingQ[i];
  78
  79              // When this transaction has already established a half-open
  80 @@ -927,6 +944,7 @@
  81                                "something mutated pending queue from "
  82                                "GetConnection()");
  83          }
  84 +        delete [] ind;
  85          if (conn) {
  86              LOG(("  dispatching pending transaction...\n"));
  87
  88 @@ -1011,6 +1026,19 @@ nsHttpConnectionMgr::AtActiveConnectionLimit(nsConnectionEntry *ent, PRUint8 cap
  89          maxPersistConns = mMaxPersistConnsPerHost;
  90      }
  91
  92 +    // Fuzz maxConns for website fingerprinting attack
  93 +    // We create a range of maxConns/5 up to 6*maxConns/5
  94 +    // because this function is called repeatedly, and we'll
  95 +    // end up converging on a the high side of concurrent connections
  96 +    // after a short while.
  97 +    PRUint8 *bytes = nsnull;
  98 +    nsresult rv = mRandomGenerator->GenerateRandomBytes(1, &bytes);
  99 +    NS_ENSURE_SUCCESS(rv, rv);
 100 +
 101 +    bytes[0] = bytes[0] % (maxConns + 1);
 102 +    maxConns = (maxConns/5) + bytes[0];
 103 +    NS_Free(bytes);
 104 +
 105      // use >= just to be safe
 106      return (totalCount >= maxConns) || ( (caps & NS_HTTP_ALLOW_KEEPALIVE) &&
 107                                           (persistCount >= maxPersistConns) );
 108 @@ -1227,7 +1255,7 @@ nsHttpConnectionMgr::DispatchTransaction(nsConnectionEntry *ent,
 109
 110      if (conn->SupportsPipelining() && (caps & NS_HTTP_ALLOW_PIPELINING)) {
 111          LOG(("  looking to build pipeline...\n"));
 112 -        if (BuildPipeline(ent, trans, &pipeline))
 113 +        if (BuildRandomizedPipeline(ent, trans, &pipeline))
 114              trans = pipeline;
 115      }
 116
 117 @@ -1300,6 +1328,101 @@ nsHttpConnectionMgr::BuildPipeline(nsConnectionEntry *ent,
 118      return true;
 119  }
 120
 121 +
 122 +// Generate a shuffled request ordering sequence
 123 +void
 124 +nsHttpConnectionMgr::ShuffleRequestOrder(PRUint32 *ind, PRUint32 count)
 125 +{
 126 +   PRUint32 i;
 127 +   PRUint32 *rints;
 128 +
 129 +   for (i=0; i<count; ++i) {
 130 +       ind[i] = i;
 131 +   }
 132 +   nsresult rv = mRandomGenerator->GenerateRandomBytes(sizeof(PRUint32)*count,
 133 +                                                       (PRUint8**)&rints);
 134 +   if (NS_FAILED(rv))
 135 +       return; // Leave unshuffled if error
 136 +
 137 +   for (i=0; i < count; ++i) {
 138 +       PRInt32 temp = ind[i];
 139 +       ind[i] = ind[rints[i]%count];
 140 +       ind[rints[i]%count] = temp;
 141 +   }
 142 +   NS_Free(rints);
 143 +}
 144 +
 145 +bool
 146 +nsHttpConnectionMgr::BuildRandomizedPipeline(nsConnectionEntry *ent,
 147 +                                   nsAHttpTransaction *firstTrans,
 148 +                                   nsHttpPipeline **result)
 149 +{
 150 +    if (mRandomGenerator == nsnull)
 151 +        return BuildPipeline(ent, firstTrans, result);
 152 +    if (mMaxPipelinedRequests < 2)
 153 +        return PR_FALSE;
 154 +
 155 +    nsresult rv;
 156 +    PRUint8 *bytes = nsnull;
 157 +
 158 +    nsHttpPipeline *pipeline = nsnull;
 159 +    nsHttpTransaction *trans;
 160 +
 161 +    PRUint32 i = 0, numAdded = 0, numAllowed = 0;
 162 +    PRUint32 max = 0;
 163 +
 164 +    while (i < ent->mPendingQ.Length()) {
 165 +        if (ent->mPendingQ[i]->Caps() & NS_HTTP_ALLOW_PIPELINING)
 166 +            numAllowed++;
 167 +        i++;
 168 +    }
 169 +
 170 +    rv = mRandomGenerator->GenerateRandomBytes(1, &bytes);
 171 +    NS_ENSURE_SUCCESS(rv, rv);
 172 +    // 4...12
 173 +    max = 4 + (bytes[0] % (mMaxPipelinedRequests + 1));
 174 +    NS_Free(bytes);
 175 +
 176 +    while (numAllowed > 0) {
 177 +        rv = mRandomGenerator->GenerateRandomBytes(1, &bytes);
 178 +        NS_ENSURE_SUCCESS(rv, rv);
 179 +        i = bytes[0] % ent->mPendingQ.Length();
 180 +        NS_Free(bytes);
 181 +
 182 +        trans = ent->mPendingQ[i];
 183 +
 184 +        if (!(ent->mPendingQ[i]->Caps() & NS_HTTP_ALLOW_PIPELINING))
 185 +            continue;
 186 +
 187 +        if (numAdded == 0) {
 188 +            pipeline = new nsHttpPipeline;
 189 +            if (!pipeline)
 190 +                return PR_FALSE;
 191 +            pipeline->AddTransaction(firstTrans);
 192 +            numAdded = 1;
 193 +        }
 194 +        pipeline->AddTransaction(trans);
 195 +
 196 +        // remove transaction from pending queue
 197 +        ent->mPendingQ.RemoveElementAt(i);
 198 +        NS_RELEASE(trans);
 199 +
 200 +        numAllowed--;
 201 +
 202 +        if (++numAdded == max)
 203 +            break;
 204 +    }
 205 +
 206 +    //fprintf(stderr, "Yay!!! pipelined %u/%u transactions\n", numAdded, max);
 207 +    LOG(("  pipelined %u/%u transactions\n", numAdded, max));
 208 +
 209 +    if (numAdded == 0)
 210 +        return PR_FALSE;
 211 +
 212 +    NS_ADDREF(*result = pipeline);
 213 +    return PR_TRUE;
 214 +}
 215 +
 216  nsresult
 217  nsHttpConnectionMgr::ProcessNewTransaction(nsHttpTransaction *trans)
 218  {
 219 diff --git a/netwerk/protocol/http/nsHttpConnectionMgr.h b/netwerk/protocol/http/nsHttpConnectionMgr.h
 220 index a13da0f..59ee9b9 100644
 221 --- a/netwerk/protocol/http/nsHttpConnectionMgr.h
 222 +++ b/netwerk/protocol/http/nsHttpConnectionMgr.h
 223 @@ -54,6 +54,7 @@
 224  #include "nsIObserver.h"
 225  #include "nsITimer.h"
 226  #include "nsIX509Cert3.h"
 227 +#include "nsIRandomGenerator.h"
 228
 229  class nsHttpPipeline;
 230
 231 @@ -317,6 +318,8 @@ private:
 232      nsresult DispatchTransaction(nsConnectionEntry *, nsHttpTransaction *,
 233                                   PRUint8 caps, nsHttpConnection *);
 234      bool     BuildPipeline(nsConnectionEntry *, nsAHttpTransaction *, nsHttpPipeline **);
 235 +    bool     BuildRandomizedPipeline(nsConnectionEntry *, nsAHttpTransaction *, nsHttpPipeline **);
 236 +    void     ShuffleRequestOrder(PRUint32 *, PRUint32);
 237      nsresult ProcessNewTransaction(nsHttpTransaction *);
 238      nsresult EnsureSocketThreadTargetIfOnline();
 239      void     ClosePersistentConnections(nsConnectionEntry *ent);
 240 @@ -409,6 +412,8 @@ private:
 241      PRUint64 mTimeOfNextWakeUp;
 242      // Timer for next pruning of dead connections.
 243      nsCOMPtr<nsITimer> mTimer;
 244 +    // Random number generator for reordering HTTP pipeline
 245 +    nsCOMPtr<nsIRandomGenerator>             mRandomGenerator;
 246
 247      //
 248      // the connection table
 249 --
 250 1.7.5.4
 251