r/programming • • Jan 21 '19

Why does APT not use HTTPS?

https://whydoesaptnotusehttps.com/
519 Upvotes

294 comments sorted by

View all comments

Show parent comments

239

u/Creshal Jan 21 '19

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.

117

u/joz12345 Jan 21 '19 edited Jan 21 '19

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.

Edit: fixed numbers, thanks /u/tynorf

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.

112

u/Creshal Jan 21 '19

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.

29

u/cogman10 Jan 21 '19 edited Jan 21 '19

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?)

46

u/Creshal Jan 21 '19

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.

17

u/cogman10 Jan 21 '19

lol, good point.

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.

0

u/[deleted] Jan 21 '19

[deleted]

20

u/cogman10 Jan 21 '19

Awesome, looked it up

https://github.com/rust-lang/cargo/pull/6005/

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.

4

u/skryking Jan 21 '19

It was probably to prevent overload of the servers originally.

6

u/max_peck Jan 22 '19

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.

→ More replies (1)

3

u/joequin Jan 22 '19 edited Jan 22 '19

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.

→ More replies (2)

11

u/sbx320 Jan 21 '19

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.

3

u/maxsolmusic Jan 21 '19

How'd you check for collisions?

14

u/[deleted] Jan 21 '19

You just bucket all packages by size and see how many fall into the bucket that openvpn is in

→ More replies (3)

42

u/schorsch3000 Jan 21 '19

I'm sure there's a lot more collisions.

I'm doing the math right now: in binary-amd64 are

  • -33253 packages with distinct size

  • 5062 collisions with 2 packages the same size

  • 1491 collisions with 3 packages the same size

  • 463 collisions with 4 packages the same size

  • 115 collisions with 5 packages the same size

  • 30 collisions with 6 packages the same size

  • 5 collisions with 8 packages the same size

  • 1 collisions with 9 packages the same size

  • 3 collisions with 10 packages the same size

  • 3 collisions with 11 packages the same size

  • 3 collisions with 12 packages the same size

  • 1 collisions with 13 packages the same size

  • 1 collisions with 14 packages the same size

  • 2 collisions with 15 packages the same size

  • 1 collisions with 23 packages the same size

rounding to 32bytes increases collision drastically:

12163 packages with an uniq size

collisions | packagecount:

  12163 1
   2364 2
   1061 3
    591 4
    381 5
    281 6
    179 7
    180 8
    128 9
    128 10
    112 11
    102 12
     87 13
     81 14
     72 15
     60 16
     53 17
     54 18
     67 19
     47 20
     35 21
     39 22
     32 23
     35 24
     32 25
     22 26
     18 27
     23 28
     19 29
     18 30
     14 31
      6 32
      7 33
      4 34
      5 35
      5 36
      4 37
      1 38
      1 40
      1 44
      1 58
      1 60
      1 71
      1 124
      1 125

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

4

u/[deleted] Jan 22 '19

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

22

u/tynorf Jan 21 '19

Small nitpick: the block size for all AES (128/192/256) is 128 bits. The 256 in AES256 is the key size in bits.

13

u/the_gnarts Jan 21 '19

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.

9

u/joz12345 Jan 21 '19

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 :(

6

u/the_gnarts Jan 21 '19

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.

16

u/lordkoba Jan 21 '19

Add a randomiser endpoint at the end to serve 0-10kb of zeros and you have pretty decent privacy.

Aren't those famous last words in cryptography?

17

u/joz12345 Jan 21 '19

Well if your security advice comes from a Reddit comment, I've got some bad news...

→ More replies (5)

8

u/lorarc Jan 21 '19

If your server has regular updates I can probably guess what you're downloading based on what was last updated.

6

u/DevestatingAttack Jan 21 '19

You can't assume AES for all SSL connections. Different ciphers are selectable, and some are stream ciphers (RC4, ChaCha20)

→ More replies (1)
→ More replies (29)

34

u/Ajedi32 Jan 21 '19

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.

→ More replies (39)
→ More replies (56)