News for hackers. Stuff that matters.
Re:Saving Data: Reducing the Size of App Updates by 65% by legulere on Wednesday December 07, 2016 @03:23AM (#13121235)
So they are recompressing the files after applying the patches and hope that it's the same? Wouldn't it make more sense to work on having the signature work on uncompressed files?

Also it's kind of shocking that almost everyone is using deflate in with compression level 6 or 9. Why is 6 even used? Why does almost nobody use zopfli which achieves 3–8% higher compression rates. Why aren't other compression formats supported like lzma, brotli, etc.?

Re:Saving Data: Reducing the Size of App Updates by 65% by vog on Wednesday December 07, 2016 @04:55AM (#13121516)
> Wouldn't it make more sense to work on having the signature work on uncompressed files?

No! That would create an additional security risk, in addition to potential performance issues.

Ideally, unchecked data should only ever hit the signature check and nothing else. Otherwise, it could also attack the decompression, not just through security holes, but also through denial of service (by injecting something that explodes in size on decompression).

This is a general principle! You should neither decompress, nor decrypt, nor unpack/untar, nor parse (XML/JSON/...), nor anything else before the signature check. See also:

"Preauthenticated decryption considered harmful"

http://www.tedunangst.com/flak/post/preauthenticated-decrypt...

However, I agree that it makes sense to have an additional check after decompression. However, that check usually happens in most decompression tools anyway, and usually through fast, lightweight checksums. Because, again, the point here is to detect bugs in the decompressor, not to protect from malicious tampering, which should always happen before complex stuff like decompression.

Re:Saving Data: Reducing the Size of App Updates by 65% by Benjamin_Dobell on Wednesday December 07, 2016 @05:57AM (#13121715)
> Otherwise, it could also attack the decompression, not just through security holes, but also through denial of service (by injecting something that explodes in size on decompression).

> This is a general principle! You should neither decompress, nor decrypt, nor unpack/untar, nor parse (XML/JSON/...), nor anything else before the signature check.

Google have stated that they're going to be decompressing, patching and recompressing data in an attempt to recreate the original data stream - simply to perform a signature check.

So, whilst minimising the attack surface is a great goal in general, your advice is not relevant here. They're already vulnerable to having their decompression, patching and compression software attacked.

Re:Saving Data: Reducing the Size of App Updates by 65% by leni536 on Wednesday December 07, 2016 @09:08AM (#13122579)
Your old apk is already signed. I guess it would make sense to sign the patch too (if they don't do it already).
Re:Saving Data: Reducing the Size of App Updates by 65% by rakoo on Wednesday December 07, 2016 @07:57AM (#13122171)
Yes, but the payload to check here is the diff, not the full APK.

What happens today is that the diff is verified, then applied, then the full APK checksum is verified. So the diff is checked before being applied; whether the checksum is verified at APK level or at file level, we have passed the signature checking.

Re:Saving Data: Reducing the Size of App Updates by 65% by vog on Wednesday December 07, 2016 @08:31AM (#13122346)
But the original question was whether the signature check should happen after applying the patch instead of before, and the answer is clearly "No!". You can and should clearly do both, but if you'd have to decide either-or, always verify first, as early as possible.
Re:Saving Data: Reducing the Size of App Updates by 65% by cesarb on Wednesday December 07, 2016 @05:12AM (#13121576)
> Why is 6 even used?

The zlib default is 6. The "maximum compression" is 9. Most people would either use the default, or request maximum compression.

> Why does almost nobody use zopfli which achieves 3–8% higher compression rates.

Most people are probably using Google's tools to create the APK, and these tools probably use zlib.

> Why aren't other compression formats supported like lzma, brotli, etc.?

Most compression formats with higher compression ratios (like lzma) need more power and memory to uncompress. As for brotli, not only IIRC it's newer than the APK format, but also most of its gains come from a predefined dictionary, which works only for text files.

Also, the APK format is AFAIK based on Java's JAR format, which uses Deflate exclusively. Many other recent formats also use a JAR-like container, like OpenDocument and EPUB.

Re:Saving Data: Reducing the Size of App Updates by 65% by user5994461 on Wednesday December 07, 2016 @05:47AM (#13121692)
I'd add that lzma memory usage is accounted in [multiple?] GB per core for the highest compression levels. That amount of memory is a big no-no for mobile devices.
Re:Saving Data: Reducing the Size of App Updates by 65% by pja on Wednesday December 07, 2016 @07:22AM (#13122025)
That’s for compression only isn’t it? I think lzma decompression requires a max of ~64Mb.

(Checks manpage) Yup:

  Preset   DictSize   CompCPU   CompMem   DecMem
  -0     256 KiB       0        3 MiB    1 MiB
  -1       1 MiB       1        9 MiB    2 MiB
  -2       2 MiB       2       17 MiB    3 MiB
  -3       4 MiB       3       32 MiB    5 MiB
  -4       4 MiB       4       48 MiB    5 MiB
  -5       8 MiB       5       94 MiB    9 MiB
  -6       8 MiB       6       94 MiB    9 MiB
  -7      16 MiB       6      186 MiB   17 MiB
  -8      32 MiB       6      370 MiB   33 MiB
  -9      64 MiB       6      674 MiB   65 MiB
Default of -6, so 8Mb. Doesn’t seem too unreasonable on a modern device.
Re:Saving Data: Reducing the Size of App Updates by 65% by vanderZwan on Wednesday December 07, 2016 @07:19AM (#13122015)
Isn't it usually just the compression stage that's very demanding with these algorithms?
Re:Saving Data: Reducing the Size of App Updates by 65% by user5994461 on Wednesday December 07, 2016 @10:10AM (#13123030)
Yes for the most common algorithms. The compression takes a lot more memory than the decompression.

But... you still have to be careful with the decompression if you intend to support small devices. Be it a tiny embedded device (obvious issue) or an old generation $500 android phone where the JVM processes are limited to xx MB (less obvious issue).

Re:Saving Data: Reducing the Size of App Updates by 65% by Benjamin_Dobell on Wednesday December 07, 2016 @03:34AM (#13121274)
> So they are recompressing the files after applying the patches and hope that it's the same? Wouldn't it make more sense to work on having the signature work on uncompressed files?

I was thinking the exact same thing when I read that portion of the article. Trying to recreate the exact APK seems entirely irrelevant.

All the user (and developer) cares about is that the installed product is identical to the one the developer submitted via the Google Play developer console. This is much more easily achieved by generating a signature on the decompressed content. It also gives Google greater freedom to change compression algorithms etc.

Re:Saving Data: Reducing the Size of App Updates by 65% by orf on Wednesday December 07, 2016 @04:04AM (#13121357)
Because then to check the signature you'd have to decompress the app. Android runs on lots of hardware, much of which is not very powerful. I would imagine this is also why they use deflate, perhaps others achieve x% better compression if it'd a lot slower on certain hardware then maybe it's not worth it.
Re:Saving Data: Reducing the Size of App Updates by 65% by pja on Wednesday December 07, 2016 @06:16AM (#13121767)
Two signatures: one on the compressed APK which is used on the initial install & one for the concatenation of the uncompressed data which is used to check in-place upgrades.

Obviously the diffs themselves also need to be signed in some way to prevent bad actors injecting data into the decompression system, but that’s a separate issue to checking that the updated App matches the data originally delivered to Google by the App developer.