Exploit (and Fix) Android "Master Key"

(I really wish people would respond instead of just downvote; I spent a long time putting together both the argument in my article, as well as the argument in this comment, and as I'm the person who wrote the article in question that people seem to have liked enough to have held on the home page all day, I feel like there's probably some merit to my thoughts: the least someone could do is explain why they think I'm wrong. Personally, I think this is an interesting philosophical discussion.)

I disagree (with you, not with Schneier, whom I do not believe was making quite the same point you are): even though the jar verification algorithm is quite arguably horribly complex (in a way that is likely to lead to implementation skew), if Android used one or the other algorithm for managing the contents of a zip file, there would not have a been a problem: there was nothing intrinsically wrong with their signature checker, it simply didn't work identically the same to the code that later extracted files.

To demonstrate why I believe this, I actually have another story to tell about signature verification vulnerabilities on this platform: Android also uses zip files for OTA system software image updates, and they actually do whole-file signatures for those archives; yet, they also managed to do it wrong, and there was a similar signature vulnerability issue that targeted the recovery system. This is the exploit used in 2009 to root the Motorola Droid.

http://evancharlton.com/thoughts/how-droid-was-rooted

The cause? Once again, multiple implementations: in this case, of the system for finding the signature itself, which was attached to the end of the zip file (conceptually a zip file "comment", as they wanted to use a separate off-the-shelf implementation of unzip); the implementation of unzip was using the normal "scan backwards" algorithm, while the verification code took the length of the signature and subtracted it from the length of the file. This caused the unzip code to use a different whole-file than the signature verification did.

You really can't implement a signature system and feel safe that you did it right if the code that is using the file is different than the code that is verifying the file: that's the core issue that is behind this kind of vulnerability. It's a sloppy kind of mistake, and these "multiple implementation" situations are always the first place to look for bugs as you attack a system: maybe the bootloader has a one-off read-only implementation of the filesystem parser, or maybe the kernel has a different implementation of XML (such as to parse Apple plist files) than userland.

You might argue that it is easier to have multiple implementations that are more likely to be implemented in the same way if the specification is simpler, but that is a mitigation, not a solution: at some point, the file is always going to be in some kind of container (such as on the filesystem, or in a flash memory partition, or in a MIME-encoded e-mail message, or yes: inside of a zip file) and if the implementation of the code that works with that content is different in one place than in the other place, that is how this kind of mistake is made.

While complex, jarsign has been around a long time and is fairly battle-hardened: attackers have had well over a decade to find holes in its specification, and it has been used in some rather security-critical deployed-over-insecure-Internet situations; the only reason we'd expect to find a mistake today is because the implementation was wrong. As an example, we might expect to find "extra files are allowed in the zip file that were not signed" (the kind of mistake that at least was, if not still is, made by Apple's codesign implementation).

To be clear: yes, you should strive to use as whole-file verification techniques as possible. (I am not disagreeing with Scheier's point: in fact, I agree with him whole-heartedly, I just believe that "whole-file" is not the root cause of this particular mistake that Google made with jarsign.) I was, truly, very disappointed that the APK algorihthm was not a whole-file signature verification, especially given that the tool that does the whole-file OTA update signatures is "SignApk" (like, I thought they were using the same signature in both places).

However, in this case, the signature mechanism was implemented correctly on top of the Java ZipFile abstraction: the problem is that that underlying abstraction was incompatible with Dalvik's, and that kind of problem can happen even to "whole-file" solutions. The underlying philosophical issue is that, much like "you can't not choose partition tolerance", you can't not have a container: we aren't signing the whole filesystem, we are signing one file on the filesystem, and somewhere there will be code that decides which file is being signed by what signature.

(I'd even argue that we are in "screaming agreement" at some level: in essence, I feel that the only way to truly know you have "signed the thing you meant, not the thing you said"--which requires feeling comfortable that the interpretation of the meaning in all of the places that you attempt to understand that meaning is the same--is to have one single implementation in charge of meaning extraction. In real-world encryption systems, you will always have a container: to be responsible, you have to not subject that container to sloppy implementation skew.)