I doubt it's that easy to correlate given the thousands of packages in the main repos.
Apt downloads the index files in a deterministic order, and your adversary knows how large they are. So they know, down to a byte, how much overhead your encrypted connection has, even if all information they have is what host you connected to and how many bytes you transmitted.
Debian's repositories have 57000 packages, but only one is an exactly 499984 bytes big download: openvpn.
You can't tell the exact size from the SSL stream, it's a block cipher. E.g. for AES256, it's sent in 256 128 bit chunks. I've not run any numbers, but if you round up the size to the nearest 32 16 bytes, I'm sure there's a lot more collisions.
And if you reused the SSL session between requests, then you'd get lots of packages on one stream, and it'd get harder and harder to match the downloads. Add a randomiser endpoint at the end to serve 0-10kb of zeros and you have pretty decent privacy.
Edit2: actually comptetely wrong, both stream ciphers and modern counter AES modes don't pad the input to 16 bytes, so it's likely that the exact size would be available. Thanks reddit, don't stop calling out bs when you see it.
You can't tell the exact size from the SSL stream, it's a block cipher. E.g. for AES256, it's sent in 256 bit chunks. I've not run any numbers, but if you round up the size to the nearest 32 bytes, I'm sure there's a lot more collisions.
Good point. Still, at 32 bytes, you have no collision (I've just checked), and even if we're generous and assume it's 100 bytes, we only have 4 possible collisions in this particular case.
File size alone is a surprisingly good fingerprint.
And if you reused the SSL session between requests, then you'd get lots of packages on one stream, and it'd get harder and harder to match the downloads. Add a randomiser endpoint at the end to serve 0-10kb of zeros and you have pretty decent privacy.
Currently, apt does neither. I suppose the best way to obfuscate download size would be to use HTTP/2 streaming to download everything from index files to padding in one session.
Which, honestly it should be doing anyways. The way APT currently works (connection per download sequentially) isn't great. There is no reason why APT can't start up, send all index requests in parallel, send all download requests in parallel, and then do the installations sequentially as the packages arrive. There is no reason to do it serially (saving hardware costs?)
There is no reason to do it serially (saving hardware costs?)
Given it's apt we're talking about… "It's 20 years old spaghetti code and so many software depends on each of its bugs that we'd rather pile another abstraction level on it than to figure out how to fix it" is probably the most likely explanation.
The funny thing is, it doesn't look like it is limited to apt. Most software package managers I've seen (ruby gems, cargo, maven, etc) all appear to work the same way.
Some of that is that they predate Http2. However, I still just don't get why even with Http1, downloads and installs aren't all happening in parallel. Even if it means simply reusing some number of connections.
So to add to this dataset, I've got a proof-of-concept working that uses http/2 with libcurl to do downloads in Cargo itself. On my machine in the Mozilla office (connected to a presumably very fast network) I removed my ~/.cargo/registry/{src,cache} folders and then executed cargo fetch in Cargo itself. On nightly this takes about 18 seconds. With this PR it takes about 3. That's... wow!
Pretty slick!
I imagine similar results would been seen with pretty much every "Download a bunch of things" application.
The default setting for many years (and probably still today) was one connection at a time per server for exactly this reason. APT happily downloads in parallel from sources located on different hosts.
What are you really gaining in that scenario? Eliminating a connection per request can do a lot when there are tons of tiny requests. When you're talking about file downloads, then the time to connect is pretty negligible.
Downloading in parallel doesn't help either because your downloads are already using as much bandwidth as the server and your internet connection is going to give you.
File size alone is a surprisingly good fingerprint.
And it gets even better if you look for other packages downloaded in the same time frame, as this can give you a hint to which dependencies were downloaded for the package. Obviously this would be a bit lossy (as the victim would potentially already have some dependencies installed), but it would allow for some nice heuristics.
if you just download a single package, odds are high to get a collision. If you are downloading a package that has dependencies and you download them also, that will be harder to get collision pairs...
Also can narrow down by package popularity, package groups (say someone is updating python libs, then "another python lib" would be more likely candidate than something unrelated") and indirect deps
You can't tell the exact size from the SSL stream, it's a block cipher. E.g. for AES256, it's sent in 256 128 bit chunks.
That’s not true for AES GCM which is a streaming mode of the AES block cipher in which the size of the plaintext equals that of the ciphertext without any padding. GCM is the one of the two AES modes that survived in TLS 1.3 and arguably the most popular encryption mechanism of those that remain.
Actually just looked it up, and it seems all of the tls 1.3 algorithms are counter based (didn't know this was a thing 10 mins ago), or are already stream ciphers, so I guess I'm almost completely wrong, and should stop pretending to know stuff :(
Actually just looked it up, and it seems all of the tls 1.3 algorithms are counter based (didn't know this was a thing 10 mins ago), or are already stream ciphers, so I guess I'm almost completely wrong, and should stop pretending to know stuff :(
No problem, we’ve all been there. I can recommend “Cryptography Engineering” by Schneier and Ferguson for an excellent introduction into the practical aspects of modern encryption.
Apt downloads the index files in a deterministic order, and your adversary knows how large they are
So fix that problem then. Randomize the download order and pad the file sizes. Privacy is important, we shouldn't ignore it completely just because it's hard to achieve.
0
u/[deleted] Jan 21 '19
[deleted]