jonathanKingston
commented
3 years ago Hey @austinhartzheim thanks for the detailed analysis and explanations. I just want to follow up and say I've looked at the code and we're deciding the right path forward.
Due to breakage we have actually already disabled this feature anyway. As we use JavaScript we have a trade off on how much randomisation we can do as you can imagine. You mentioned that we aren't applying more when the clip is longer, again this was a trade off I took due to the performance aspect.
I'd like in an ideal world to run this code in WASM so we can use much more tried and tested crypto algorithms for this.
Anyway we're working through internally on the next best steps here.
Discovered Weaknesses
Insufficient entropy
In the following code snippet,
itemis set to the character code of the first character inkey. As used for the protection of the audio API,keyis a hexadecimal string. Therefore, the first character is in the range[0-9a-f], which offers only four bits of entropy.https://github.com/duckduckgo/duckduckgo-privacy-extension/blob/918c48c6db17f09135d375c5d2fa91280f019777/shared/js/content-scope/utils.js#L62-L77
Recommendation 1: Seed the PRNG with sufficient entropy. For example, a 64-bit LFSR should be seeded with 64-bits of entropy.
Choice of PRNG
The current PRNG is a LFSR which appears to operate on a 64-bit register. Even when seeded with additional entropy, the outputs quickly regress to a predictable sequence.
https://github.com/duckduckgo/duckduckgo-privacy-extension/blob/918c48c6db17f09135d375c5d2fa91280f019777/shared/js/content-scope/utils.js#L11-L13
JavaScript integers are represented in IEEE 754 format, which can only accurately represent integers up to 53-bits. This may explain why the outputs begin to repeat faster than expected.
Recommendation 2: Change the PRNG implementation. For example, a 32-bit LFSR would have similar performance characteristics but, but better randomness given the limitation on JavaScript's integers.
Samples of modified indexes
The PRNG quickly regresses into repeated sequences, and often outputs the same index (modulo length) consecutively. ``` length=64 seed=97 sequence=[33, 48, 24, 12, 58, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31, 15, 7, 3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 31, 47, 55, 59, 3, 63, 31] length=128 seed=57 sequence=[57, 28, 114, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15, 7, 3, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 63, 95, 111, 119, 123, 67, 31, 15] length=200 seed=98 sequence=[98, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87, 43, 127, 163, 167, 183, 191, 95, 47, 23, 111, 55, 127, 63, 31, 15, 7, 103, 151, 175, 87, 143, 71, 135, 167, 183, 191, 195, 151, 175, 87] length=200 seed=99 sequence=[99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199, 99, 199, 99, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, 99, 199, 199] ```Perturbation ratio
The implementation of
iterateDataKey(linked above) does not scale the number of perturbed elements with the length of the audio buffer. Instead, at most8 * key.lengthelements are perturbed. In practice, the actual number is lower due to 1) duplicate elements chosen by the PRNG, and 2)bytehaving at most seven ASCII bits (see note at end).As the length of the audio buffer grows, the ratio of perturbed to unperturbed elements falls. This makes it easier to extract unprotected fingerprint data from longer audio buffers.
Recommendation 3: Scale perturbation with the length of the buffer so that longer buffers do not yield a greater chance of selecting unperturbed items. If performance constraints allow, perturbing all elements in the buffer is preferable.
Practical Attacks
Due to the issues outlined above, the several practical attacks become possible. Fixing these issues should significantly mitigate the following attacks.
As a general theme, the following attacks allow reversing or bypassing the anti-fingerprinting techniques applied by the extension. At least some fingerprinting tools have expressed interest in reversing anti-fingerprinting protections (see section "Reverting Brave standard farbling").
Pre-computed perturbation set
If the fingerprinting software relies on an
AudioBufferof known length, it is possible to pre-compute the set of indexes which may be perturbed over all PRNG seeds. (In fact, the computation is fast enough to be computed dynamically if variable buffer lengths are used.) Once the set is computed, the fingerprinting software may choose to ignore those indexes when generating the fingerprint, regardless of the extension's presence. This makes the fingerprints comparable across all browsers.The limited entropy in the seed means there are only sixteen possible sequences of indexes to ignore. And due to the poor performance of the PRNG, those sequences share significant overlap.
Possible perturbation percentages by length
The following table shows the percent of items that *could* be perturbed without a priori knowledge of the PRNG seed. ``` length=64 percent=0.515625 length=128 percent=0.335938 length=192 percent=0.333333 length=256 percent=0.218750 length=320 percent=0.246875 length=384 percent=0.205729 length=448 percent=0.194196 length=512 percent=0.132812 length=576 percent=0.166667 length=640 percent=0.151562 length=704 percent=0.144886 length=768 percent=0.119792 length=832 percent=0.123798 length=896 percent=0.116071 length=960 percent=0.111458 length=1024 percent=0.076172 length=1088 percent=0.103860 length=1152 percent=0.096354 length=1216 percent=0.092928 length=1280 percent=0.089063 length=1344 percent=0.087798 length=1408 percent=0.081676 length=1472 percent=0.081522 length=1536 percent=0.066406 length=1600 percent=0.076875 length=1664 percent=0.069712 length=1728 percent=0.076968 length=1792 percent=0.066964 length=1856 percent=0.068427 length=1920 percent=0.063542 length=1984 percent=0.064516 length=2048 percent=0.042480 ```Sample pre-computed perturbation set
By seed, `length=64`: ```json // {seed: [indexes]} { "48": [3, 7, 12, 15, 24, 31, 48, 58, 63], "49": [3, 7, 12, 15, 24, 31, 47, 49, 55, 58, 59, 63], "50": [3, 7, 15, 31, 35, 39, 50, 51, 63], "51": [3, 7, 15, 31, 39, 51, 63], "52": [3, 7, 27, 31, 38, 47, 51, 52, 55, 63], "53": [3, 7, 11, 23, 27, 31, 38, 43, 47, 51, 53, 63], "54": [3, 7, 11, 23, 27, 31, 43, 47, 51, 54, 63], "55": [3, 7, 27, 31, 47, 51, 55, 63], "56": [3, 7, 15, 28, 31, 50, 56, 63], "57": [3, 7, 15, 28, 31, 47, 50, 55, 57, 59, 63], "97": [3, 7, 12, 15, 24, 31, 33, 47, 48, 55, 58, 59, 63], "98": [3, 7, 15, 31, 34, 39, 51, 63], "99": [3, 7, 15, 31, 35, 39, 51, 63], "100": [3, 7, 14, 15, 31, 36, 39, 51, 63], "101": [3, 7, 11, 14, 23, 27, 31, 37, 39, 47, 51, 63], "102": [3, 7, 11, 23, 27, 31, 38, 39, 47, 51, 63] } ``` Full set over all seeds, `length=64`: ```json /// [indexes] [3, 7, 11, 12, 14, 15, 23, 24, 27, 28, 31, 33, 34, 35, 36, 37, 38, 39, 43, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 63] ```Recovery of PRNG state
Using the "Sample pre-computed perturbation set" table above, it is possible to reverse the set of perturbed elements to the seed used by the PRNG. The following code snippet recovers the seed by observing the perturbations in the audio buffer. (Note, while this example initializes the buffer to a known state, this attack can be performed on any buffer where the sum of all elements is not zero).
Sample code
```js extractAudioKey() { // Reverse table for length=64 const revtable = { "3,7,12,15,24,31,48,58,63": 48, "3,7,12,15,24,31,47,49,55,58,59,63": 49, "3,7,15,31,35,39,50,51,63": 50, "3,7,15,31,39,51,63": 51, "3,7,27,31,38,47,51,52,55,63": 52, "3,7,11,23,27,31,38,43,47,51,53,63": 53, "3,7,11,23,27,31,43,47,51,54,63": 54, "3,7,27,31,47,51,55,63": 55, "3,7,15,28,31,50,56,63": 56, "3,7,15,28,31,47,50,55,57,59,63": 57, "3,7,12,15,24,31,33,47,48,55,58,59,63": 97, "3,7,15,31,34,39,51,63": 98, "3,7,15,31,35,39,51,63": 99, "3,7,14,15,31,36,39,51,63": 100, "3,7,11,14,23,27,31,37,39,47,51,63": 101, "3,7,11,23,27,31,38,39,47,51,63": 102 }; var ab = new AudioBuffer({length: 64, numberOfChannels: 1, sampleRate: 48000}); var abb = ab.getChannelData(0); // Initialize the buffer to a known value for (var i = 0; i < abb.length; i++) { abb[i] = 1; } // Read back the data, which will be perturbed by DDG var abb = ab.getChannelData(0); // Find perturbed elements. var perturbed = []; for (var i =In pra 0; i < abb.length; i++) { if (abb[i] != 1) { console.log(i, abb[i], abb[i] != 1) perturbed.push(i); } } // Lookup the perturbation set in `revtable` var lookup = perturbed.join(','); return revtable[lookup]; } ```Due to how the cache is linked with the
AudioBufferinstance, it is possible to discover the seed after having read the perturbed data.https://github.com/duckduckgo/duckduckgo-privacy-extension/blob/918c48c6db17f09135d375c5d2fa91280f019777/shared/js/content-scope/fingerprintingAudio-protection.js#L59-L70
Once the seed is known, there are a few possible uses:
audioKey) fully determines the perturbation applied to several indexes in the buffer. Knowing the seed may allow the perturbation to be reversed. The remainder of this section is dedicated to this case.Knowing the seed allows determination of the perturbation applied to several indexes within the buffer. The amount of perturbation is determined by a byte (hex digit) of the key and the iteration of the perturbation process. Because the first byte of the key is used eight times (bit-shifted once each time), it is possible to compute the perturbation that was applied. In this instance, the non-random PRNG output provides a degree of protection by perturbing most values many, many times with a different portion of the key. However, the first few PRNG outputs are sufficiently unique to only appear once for several seeds.
This green cells in this table show the indexes perturbed only once, depending on the seed. All such indexes are perturbed using the first byte of the key - which is known during this attack. Therefore, the perturbations are reversible (to the degree allowed by floating point precision).
In practice, I believe there are simpler methods to approximate the original values. However, they are not related to the PRNG and are therefore not discussed here.
Other Notes
byte ^ 0x1is alwaystrueexcept whenbyteis zero, in which case, the index is perturbed by adding zero (i.e., not perturbed). Perhapsbyte & 0x1was intended instead. Currently, this has the effect that all perturbations are subtractions.