Technical Analysis of DuckDuckGo Privacy Essentials (part 2)

20 minute read

Analysis of the DuckDuckGo extension’s protection of the Audio API. A broader look at the extension’s privacy protections is in part 1.

The following writeup is adapted from my bug report to DuckDuckGo in issue #736 and partial patch proposed in PR #737.

Intended Protection

One technique for device fingerprinting involves observation of minor variations in mathematical operations. For example, the result of floating point operations may differ depending on the underlying implementation. These differences may be introduced by software or hardware and will often affect the least significant bits of the floating point representation.

To expose these implementation differences, fingerprinting software executes floating point operations that are likely produce disparate results when executed on different hardware or software stacks. In particular, the Web Audio API defines an AudioBuffer object consisting of 32-bit floats. The API also provides numerous operations for modifying the audio data - each of which is a potential source for implementation differences.

To prevent fingerprinting software from using these differences to fingerprint a browser, the DuckDuckGo Privacy Essentials (DPE) browser extension adds random noise when reading the contents of an AudioBuffer. The extension generates this random noise by using a pseudo-random number generator (PRNG) to modify calls to the AudioBuffer API.

PRNG Analysis

Analysis of the PRNG used in DPE yields two weaknesses which lessen the effectiveness of the protection. First, the PRNG is seeded with low-entropy input. Second, due to an implementation flaw, the chosen PRNG results in low quality randomness.

Low-Entropy Seed

The following code snippet demonstrates how the seed is selected for the PRNG. Notice that key.charCodeAt(0) selects the first character from key, where key is a hexadecimal string. Consequently, item takes a value in the range [0-9a-f], which has only four bits of entropy.

// Iterate through the key, passing an item index and a byte to be modified 
export function iterateDataKey (key, callback) { 
    let item = key.charCodeAt(0) 
    for (const i in key) { 
        let byte = key.charCodeAt(i) 
        for (let j = 8; j >= 0; j--) { 
            callback(item, byte) 
 
            // find next item to perturb 
            item = nextRandom(item) 
 
            // Right shift as we use the least significant bit of it 
            byte = byte >> 1 
        } 
    } 
} 

Source

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

DPE uses a Linear Feedback Shift Register (LFSR) PRNG. LFSRs have the benefit of being quite fast, which might be beneficial for low-latency audio applications. However, the chosen LFSR implementation operates on a 64-bit register. Normally, this would be fine, however JavaScript uses IEEE 754 format to represent numbers internally. This format only allows lossless representation of up to 53-bit integers. The result is that the PRNG output (ignoring the low-entropy seed discussed above) quickly decays into a predictable sequence of outputs.

The PRNG implementation is as follows:

export function nextRandom (v) { 
    return Math.abs((v >> 1) | (((v << 62) ^ (v << 61)) & (~(~0 << 63) << 62))) 
} 

Source

The PRNG selects which indexes in the AudioBuffer output are modified. Because the PRNG decays into a predictable state, the result is that far fewer than the desired numbered of outputs are modified. The following displays a simulation of the PRNG output for several seeds, demonstrating the high number of repeated indexes. Note that the output values of the PRNG are taken modulo the length of the AudioBuffer:

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]

Recommendation 2: Change the PRNG implementation. For example, a 32-bit LFSR would have similar performance characteristics but, better randomness given the limitation on JavaScript’s integers.

Implementation Choices

Beyond the PRNG, an additional design choice limits DPE’s ability to limit fingerprinting via the AudioBuffer API due to the amount of unprotected data.

Perturbation ratio

As an implementation choice, the iterateDataKey function (linked above) does not increase the number of perturbed elements with the length of the AudioBuffer. Instead, at most 8 * key.length elements are perturbed. In practice, the actual number is lower due to 1) duplicate elements chosen by the PRNG (discussed above), and 2) byte having at most seven ASCII bits1.

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.

Boolean Logic

In the following code, byte ^ 0x1 is always true except when byte is zero, in which case, the index is perturbed by adding zero (i.e., not perturbed). Perhaps byte & 0x1 was intended instead. Currently, this has the effect that all perturbations are subtractions which further limits the randomness of perturbations applied.

iterateDataKey(audioKey, (item, byte) => {
    const itemAudioIndex = item % channelData.length

    let factor = byte * 0.0000001
    if (byte ^ 0x1) {
        factor = 0 - factor
    }
    channelData[itemAudioIndex] = channelData[itemAudioIndex] + factor
})

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 AudioBuffer of 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.

The following table shows the percent of items that could be perturbed without a priori knowledge of the PRNG seed. The listed percentage represents the amount of data in the AudioBuffer that is perturbed by at least one of the 16 possible seed values. Even with a short buffer length (such as n=64), approximately 50% of the buffer’s indexes are unperturbed under all seed values, giving plenty of unprotected values from which a fingerprint might be extracted. Modestly longer buffer lengths have even less protection.

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

To give a specific example, a buffer of length n=64 will have the following indexes perturbed by the extension depending on the input key:

// {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]
}

Taking the union of indexes for each key, the following list of indexes could be ignored when generating a fingerprint to avoid accessing data modified by DPE:

// [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).

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 AudioBuffer instance, it is possible to discover the seed after having read the perturbed data.

Source

function getCachedResponse (thisArg, args) { 
    const data = cacheData.get(thisArg) 
    const timeNow = Date.now() 
    if (data && 
        data.args === JSON.stringify(args) && 
        data.expires > timeNow) { 
        data.expires = timeNow + cacheExpiry 
        cacheData.set(thisArg, data) 
        return data 
    } 
    return { audioKey: null } 
} 

Once the seed is known, there are a few possible uses:

  • The seed is four bits of entropy which can be used to fingerprint a DuckDuckGo extension user’s session. This value is derived from the user’s session key and therefore cannot be used to track a user across sessions, but could track the user within a given session even if other data (such as cookies) have been cleared.
  • The seed determines which indexes are perturbed and can be used to target specific indexes for exclusion from a fingerprint. This is more targeted than the “pre-computed perturbation set” described above, allowing for recovery of additional unperturbed data from a smaller buffer.
  • The seed (which is also the first four bits of the 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).

PRNG state recovery allows determination of value shift. Diagram displays a table of AudioBuffer offsets by PRNG seeds. It indicates which values are perturbed only once for a given seed.

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.

Footnotes

  1. It may be preferable to access raw bytes from the hash or to parse hex digits into longer integers. Direct operation on the hex ASCII codes provides at most 4-bits of entropy encoded in 7-bit ASCII. This results in potential weakness here