RFC: Proposal for estimating unique Julia clients without tracking

General Usage
, , ,
21

Just a quick note on this, if you don’t trust the operators of the Julia package servers, there’s an even bigger existing risk than this proposal creates in what is already available server-side by IP and TLS fingerprinting.

Collecting information client-side makes it much easier to precisely get the minimum amount of user data required to infer useful information (the kind that helps get grant funding for academic work on packages, for example) and no more. To me, this seems like a good thing to do.

22

I know this is just a turn of phrase, but there’s no “business value” here. The estimates will be public and the beneficiaries are open source projects, not businesses. Any benefit to businesses is to businesses that have made a significant bet on Julia and want to be able to show that’s not a crazy thing to do.

This is a good point. I’ll have to think about the timed secret rotation thing a bit.

That’s a good idea. The VM example is compelling, but I do also kind of think that sort of thing is bound to happen and doesn’t matter that much — we know unique client count is still a rough proxy and the number of cases of things like VMs is going to be tiny relative to the number of normal users just installing on their laptops. The thing that can create huge request counts and really mess up the data is automated systems like CI.

I’ve updated the code and the comment about it. I put the client hash length assertion in there and I changed the hashing order so the client hash — which is secret and controlled solely by the client — is hashed second, which blocks length extension. It is also the case that truncated SHA256 is not vulnerable to length extension, and the client does not send this hash value, it sends y = w (x_0 g^h)^t where w, x_0, t and h are all unknown to the server. The server provably learns no information about h because for any h' there is a x_0' such that x_0 g^h = x_0' g^{h'}. We don’t even need a cryptographically strong hash here, we just need a decent hash with enough output bits. The main purpose of this hash is to turn a resource class string into an exponent in a nice uniform way that is highly client-specific.

If we had them as stdlibs I would.

Again, not for business; if we did change it, I don’t think it would be with any regularity.

Point well taken—I think this is the real reason; get it right because we probably won’t change it. One of the many reasons to ask for feedback now!

23

Actually, sorry, this is false (only works if g^{h'} is a semi-generator, which has a probably of around 50%). But we do know that the server only learns the client’s 18-bit HLL value, which can be viewed as a very truncated hash of x_0 with h, so length extension is definitely not a concern.

24

I’d even say “for zero direct gain to the average user”.

The gain is indirect and difficult to measure: It is the influence (again, the indirect one) onto the very existence and further development of the packages available to that average user.

On a general note, that “average user” has typically other concerns than concealing their usage data from the “greedy corporations”. The “transparent opt-in choice” in >99.99…% of cases means clicking away that intrusive dialog. Or how often do you carefully study some linked information about cookie usage?

Generally I don’t like data collection too much, but somehow I realize that Googles and Mictrosofts, and Juliahubs too, need to pay salaries and taxes, and these salaries and taxes go - directly or indirectly - into schools, health institutions, and armies in our countries.

25

While I appreciate what seems intended as support, this is very much the wrong take, imo. Google and Facebook’s businesses are literally collecting data on you so that ads can be targeted more accurately. JuliaHub, which again, has nothing to do with this proposal, sells simulation and modeling software and an HPC compute platform. Nowhere in JuliaHub’s business model does knowing anything about Julia users (even at a demographic level) factor in. The company doesn’t get or need access to any data that isn’t available to everyone else, whether this protocol gets deployed or not. So lumping JuliaHub in with Google, Microsoft, Facebook, etc. is really not right. JuliaHub paying its employees does not depend in any way on this proposal.

26

Last I looked, they are part of the SHA stdlib?

We even have hmac available SHA · The Julia Language since probably 8 years.

But the resource-sharding hash discussion is growing way out of hand for a minor nitpick.

What I was saying: The desired properties are exactly resource_key = MAC(client_master_secret, resource_class). A boring workman-like implementation should not try to be clever, and just use a well-known standard MAC. Anything else looks weird and amateurish to the trained eye, wastes review-time, and is a red flag, even if it doesn’t cause security issues.

It also looks weird and amateurish to AI (google “sha2 as mac” or “sha3 as mac”, and google will explain to you that you shouldn’t do this). Even naked sha3 is cutting it close (google AI and more nitpicky reviewers would say: Use KMAC, you’re not qualified to figure out how to make a MAC out of a hash, that’s the job of NIST / FIPS-xyz; and even if you are qualified, that’s wasting review-time that should go to your very clever RSA construction!).

You can chose to not act on this specific feedback, and nothing will blow up; and I won’t be offended either.

I think the RSA-for-hyperloglog is a really cool construction. But the resource-sharding deanonymization is a little scary: It means that, in certain scenarios, people actually lose anonymity compared to a more naive “no resource sharding” variant. It makes me feel that coarser resource-sharding could be better. It also means that raw logs can never be released (toxic sludge, in terms of privacy).

Regarding general privacy and process concerns that a bunch of other people raised… I think that should be a separate discussion (and should probably come after the first round of technical discussion is finished).

I don’t envy the communication task of making the community happy with this kind of tracking – there is a lot of well-earned distrust for any kind of tracking, even though I think your proposal is reasonable and privacy conserving (and good for julia open-source projects, which in turn is good for all of us who maintain or rely on these projects!).

27

Looking at the other side of the equation, I think it is reasonable to ask that people who oppose this proposal demonstrate direct, practical, and specific concerns.

“I don’t like data collection in general, no matter how much effort went into anonymization” may not be of those.

28

Hah, TIL :man_facepalming: Guess I’ll switch to one of these options then.

Do you have a specific recommendation using the SHA package?

I do think that we could do something where we do daily aggregation a few ways and remember that (eg "What hours of the day are hot, sliced by some useful rollup dimensions like region), and then forget everything but the date of each log record, dropping the time part. That should more than address this since a) it would prevent easily temporally associating a burst of requests from a single client, and b) it’s more anonymization than we’re doing now. If we have client HLL values, I also think we can and probably should drop IP HLL hashes, which could help with burst linking and have not turned out to be useful in practice since they don’t map effectively to unique clients. I think those measures combined would put us in a better rather than worse position in terms of privacy or “toxic sludge”.

29

I went with hmac_sha3_256 and yes, it’s much cleaner and simpler:

Do you think I should be using an HMAC construction for hll_hash_into_ring as well? Or does that not trigger the same concerns since the arguments are fully determined by the protocol with no leeway for either party to mess with them?

30

It might be helpful to just have a direct comparison of the privacy and data considerations between the status quo and this new proposal. My rough understanding is that replacing the server-side HLL-hashed-IP with this would make the private long-term stored logs less deanonymizable while making the public aggregations more meaningful. Is that accurate?

With the old system, you can meaningfully correlate between packages with the private logs. This actually destroys that capability. Even the most privacy-conscious client wouldn’t hop through the hundreds of exit nodes that’d be required just to instantiate a Manifest with the same level of anonymity that resource sharding gives them here.

With the old system, it’s possible for a particular IP to encrypt/hash into an unlucky rare bin, allowing longitudinal tracking of a very small (perhaps single user) cohort across all packages with the private logs. This “spreads the joy” and everyone has a chance to be a little special for a small corner of the dataset — but nobody is uniquely and universally special.

Is that accurate? Are there other scenarios that are worth exploring?

31

Not really. Since you use sha2 in other places, hmac-sha256, I guess? Mixing different cryptosystems is not a problem per-se, but it is a tiny little weirdness flag, and there is no reason to do that.

I don’t see a good reason for that. The hashing looks good enough for me.

No, it makes the thing worse, if the server is misbehaving with private logs.

The attack is the following (what I wrote upstairs as the “correlation of (k,d) pairs”):

Server logs all accesses, with IP address, time, requested package, and the (k,d)-value. For simplicity, the evil server will even discard the geometric distributed d value from hyperlolog; but it will keep the k-value.

The k-value is a uniform random 12 bit number generated and stored by the client. It is stable over years. Each package gets its own k value, for each client (the client doesn’t know its k-value, though – it’s masked by the clever cryptographic RSA construction).

Now, when Joe User decides to update his DifferentialEquations install, Pkg will download a bunch of packages. All these downloads happen from the same IP address, in very short sequence.

From this, the malicious log-reader learns: There is a user from Pakistan who did an update in july 26, and has

DifferentialEquationsBase: k=1337
DifferentialEquations: k=1234
StaticArrays: k=1678
DataStructures: k=2012
...

Each single of these k-values is not enough to uniquely identify Joe. But any pair is probably enough (one in 16 million users).

So when somebody installs or updates CentrifugeSimulations.jl in 2030, from an IP in North Korea, which has in its dependency lists StaticArrays.jl [k=2012] and DataStructures.jl [k=1678], then – bingo!

This is what I meant by: The resource sharding turns the raw server logs into privacy-toxic sludge.

32

Ah, I was thinking of the long-term stored data, not the raw nginx logs. The former do not keep raw IP addresses currently and definitely won’t in the future — doing so would be in violation of the GDPR. We document that we rotate the raw logs every 31 days, but I think it’s much shorter these days.

Yes, a misbehaving server could break this, that’s true.

33

If you’re going with SHA3, I’d specifically advocate for KMAC over HMAC: the HMAC algorithm is a workaround for for Merkle–Damgård constructions (like SHA2) that suffer from length-extension attacks, which is a problem that sponge-based approaches like SHA3 simply don’t have. In this way, SHA3-HMAC seems a bit cryptographically messy.

KMAC is more straighforward, has strong crypto analysis, and is specified in NIST SP 800-185.

It’s pretty easy to impement on top of SHA.jl, using SHAKE_128_CTX (might as well if you just want a UInt128 out, KMAC128 has a comprable security margin to HMAC-SHA256).

using SHA

function kmac128(key::AbstractVector{UInt8}, msg::AbstractVector{UInt8}, customization::AbstractString="")
    function length_encode(len, left::Bool)
        if len == 0
            UInt8[left, !left]
        else
            big_endian_bytes = map(UInt8, reverse(digits(len, base=256)))
            (if left pushfirst! else push! end)(big_endian_bytes, length(big_endian_bytes))
            big_endian_bytes
        end
    end
    function bytepad(data, block_size)
        padded = [length_encode(block_size, true); data]
        vcat(padded, zeros(UInt8, block_size - rem(length(padded), block_size)))
    end
    encode_string(data) = [length_encode(length(data) * 8, true); data]
    # Injest the data
    sponge = SHAKE_128_CTX()
    update!(sponge, bytepad([encode_string(codeunits("KMAC")); encode_string(codeunits(customization))], 168))
    update!(sponge, bytepad(encode_string(key), 168))
    update!(sponge, msg)
    update!(sponge, length_encode(128, false))
    # cSHAKE suffix 0x04 (not SHAKE's 0x1F)
    usedspace = Int(sponge.bytecount % 168)
    sponge.buffer[usedspace + 1] = 0x04
    sponge.buffer[(usedspace+2):167] .= 0x00
    sponge.buffer[168] = ifelse(usedspace == 167, 0x84, 0x80)
    SHA.transform!(sponge)
    # Donezo
    bswap(first(reinterpret(UInt128, view(sponge.state, 1:2))))
end

Edit: Changed recommendation/example to KMAC128 instead of KMAC256

34

Yes, this is accurate modulo a few additional facts. One is that IP addresses are a very bad proxy for individual clients. The mapping is neither one-to-one nor onto due to NATs (many clients, one public IP address) and dynamic IP assignment (one client, many public IP addresses over time), which provides some level of “privacy”, but that’s a very poor form of privacy.

Right now if some client has a rare IP HLL hash, that cuts across all resource classes — they aren’t sharded. If we replace unsharded IP HLLs with sharded client HLLs and do the thing that @foobar_lv2 suggested with coarsening timestamps, then I think the overall privacy situation would be substantially better and we’d be getting much better information about unique client counts. (I also think there should be some rotation mechanism for HLLs; still have to think on exactly how it should work though.)

The only thing, imo, causing a negative reaction in a few people seems to be that HLL over RSA does involve the client participating actively by sending something, instead of the collection being strictly passive.

We don’t store raw server logs more than 31 days (and they’re stored in a completely separate operational system that never feeds into log analysis). We do currently, however, keep timestamps on the analysis logs, which is what allows @foobar_lv2’s request bundle analysis. The having a client HLL value per request does make that worse — but there’s already a good amount of information in logs to work with, so this would already be a problem. If we only keep the date and then roll that up into weekly aggregate date after a month or so and monthly aggregate data after a year, then this data is fine since there’s no way to correlate requests that happened in a batch from time-aggregated data.

35

Switch to hmac_sha2_256 now.

Perhaps, but I’d rather not get into implementing this kind of algorithm as part of this. I’ll just stick with SHA256 for the whole thing and use hmac_sha2_256.

36

Only if someone (you @tecosaur ?) adds KMAC to Sha.jl first. sha3-hmac is a little silly, but it has no problems, and I understand why people end up using it. (same as here: library offers hmac-sha3, but not kmac)

If you switch from sha2 to sha3 cryptosystem, then the SHAKE extendable output functions are exactly what the doctor ordered for hll_hash_into_ring : You want to turn a key into a lot of randomish bits. Current implementation has a little loop using multiple sha512 invocations. Getting rid of such kludges is exactly why NIST specified extendible output functions. But such kludges are commonly used in the before-sha3-age, and not a problem or red flag.

This goes into log-retention and statistics publication policy.

I’d like to see (or do) a real statistical analysis before I believe it; and that analysis should compare to the “no resource sharding” approach, and take the “request bundle attack” (nice name!) into account. To me, it is extremely non-obvious that “resource sharding” is ultimately superior to “no resource sharding”, privacy-wise. Even better would be prior art, i.e. series of papers that discuss that tradeoff at length.

My feeling is that the request bundle attack forces something like: No sketches are published unless they contain more than estimated 2^16 unique users (otherwise, keep secret and continue aggregating). That’s unfortunate! It basically means: raw HLL (k,d)-sketch-aggregates must be treated as toxic privacy sludge, viewable only by few trusted members / scripts who create various “harmless” summary statistics for public consumption / consumption by package maintainers.

37

I have a hard time seeing how it’s not strictly better. In the unsharded case, you have extra bits (albeit not many) to directly connect requests. In the sharded case, you can’t connect them, you have to infer a connection by some other circumstantial evidence like temporal proximity. If you aggregate the logs enough that circumstantial evidence becomes useless, then with sharding there’s nothing left to tie requests together.

Perhaps we’ve been talking past each other here. Sketches would never be published at all:

Maybe I need to promote that section at the end of the long Protocol Summary page to its own page because it is quite important. You only report aggregate count estimates for slices with at least ~1024 unique clients; everything else gets rolled up into an “other” row. After a delay, we could also discard everything besides rolled up aggregates, deleting individual logs entirely.

38

Yes, but in the unsharded case, connecting requests gives you a connected request – it doesn’t allow you to infer connected requests years in the future.

In the sharded case, once you have connected some requests through side-channels, you have obtained a unique fingerprint.

IOW, the unsharded case will have gracefully deteriorating privacy as the side-channel becomes stronger; while the sharded case will see some kind of nonlinear and complete collapse of privacy.

39

Out of my depth here, but is there a way to have the sharded case rotate out information to preserve privacy on the client side?

The concern I’d see is that if long-term privacy relies on trusting the server following it’s claimed data-retention policy and doing aggregation, then I can understand why some particularly sensitive users would be quite uncomfortable with that.

If the client-side itself can periodically shake up its salts so that the sharded information can’t be correlated over time, that seems better and more verifiable.

40

Yes, doing it yearly was what I proposed; @foobar_lv2 was suggesting something more stochastic. Probably a good idea. Have to think through the exact mechanism though.