14

Introductory Background to the question below

(so the question is more usable to more people)

Inside of an Ubuntu/debian-style package (*.deb file) there is a file named /DEBIAN/md5sums which has a content of this form:

212ee8d0856605eb4546c3cff6aa6d35  usr/bin/file1
4131b66dc3913fcbf795159df912809f  path/to/file2
8c21de23b7c25c9d1a093607fc27656a  path/to/file3
c6d010a475366e0644f3bf77d7f922fd  path/to/place/of/file4

As I assume this file will be used to check that the files which come with the package have not been corrupted somehow. Since the file is called `/DEBIAN/md5sums" I assume the hexnumber before the path+filename is the MD5 Message-Digest Algorithm Hash of the package's files.

Now everybody interested knows that the MD5 Hash has been broken already long time ago. Therefore it is totally possible to change the content of a file in the package (e.g maliciously) and still have the file having the same MD5-Hash (see for instance Prove of concept "Predicting the winner....").

Question

Bearing in mind the information above I want to know the following:

Assuming I install a package in my Ubuntu system. Is the DEBIAN/md5sums the only means to make sure the data has not been tampered with?

Answering the question I think it could help to figure out the following:

  • Are the deb packages as a whole also hashed(Hashvalues made for) so that there is another way to make safe the files received are "safe"/"untampered"
  • If there are other ways then the DEBIAN/md5sums file to ensure integrity, what is the file included in the *.deb packages anyhow?
  • Does Ubuntu use hashes for repository/package-system that are "less broken" than SHA-1 and MD5?

which unfortunately I do not know either.

Any reponse which can shed light on the question (or even only a subquestion) is very welcome

update

(1) https://help.ubuntu.com/community/Repositories/Ubuntu#Authentication_Tab seems to indicate that there is (as I hoped for) some public/private gpg key going on (to keep the repos and package systems) safe from attacks. The information at the linked location is not very much though. It tells almost nothing about the security aspect of the Package-system. Anyhow I assume the link already indicates that the answer for the question will be "NO -at least the deb packages from the repo - are also secured by .... ". Hope somebody has some insights to use for an answer here.

(2) This question seems to be also about the topic of "security" in Ubuntu package system. So I just add it here so its ad hand if somebody strives to figure the question out: Why are the proposed BADSIG (on apt-get update) fixes secure?

Bruce Becker
  • 189
humanityANDpeace
  • 1,579
  • 1
    http://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Checksums indicates support for SHA-1 and SHA256 per-file checksums, however I do not know what apt's checksum policy is. – chronitis Jan 10 '13 at 14:26
  • 1
    @chronitis thanks for the link there. Indeed the SHA-* hashes are mentioined there I still have to figure out how they appear in the packages (which I did not see yet) or the packages system.Do you know more? Well the indication is already a good step – humanityANDpeace Jan 10 '13 at 14:33

3 Answers3

22

Ubuntu publishes a manifest that is signed with an RSA key. The manifest lists individual Packages index files, each with MD5, SHA-1 and SHA-256 hashes. Each Packages file lists individual .deb files with MD5, SHA-1 and SHA-256 hashes.

For verification, apt uses the best hash that it supports and is published by the archive it is downloading from. In the case of the Ubuntu archive, this is SHA-256.

So the entire chain of installing packages on your Ubuntu system is protected by RSA and SHA-256.

The MD5 protection that exists in dpkg is really only useful for accidental corruption, and not necessary to protect the installation path.

You might be interested in the debsums package, but since it uses MD5s, it also is only useful for checking for accidental corruption.

If you want to check for malicious system modification, then these are not the appropriate tools for you. You will need to take the system offline and check against either a previous record, the original package files, or secure hashes generated from these.

Note that since a successful malicious modification might be to simply downgrade a package to the one prior to a security update, checking that all installed package files match against their originals may not be sufficient either.

Robie Basak
  • 15,670
  • 1
    I have gained some clearer insight. Where did you get all this information, which I have such a dificulty in finding? Do you have some docus/links you used? Also I appreciate the mentioning of the "downgrade-danger" you mentioned, so I do not yet understand how excatly this might be exploited. Great! thank you – humanityANDpeace Jan 10 '13 at 14:50
  • I don't believe that the apt repository format is properly specified or documented anywhere. This is bad, but it is how it is. The best (and to my knowledge only) true documentation is the source. I know the details because I've worked in the source.

    On the other hand, the dpkg format is very well specified in Debian policy. It covers what happens after packages end up on your system, but not how they get there. The latter part is done by apt.

     – Robie Basak Jan 11 '13 at 09:34
  • Downgrade risk: this is an aside and isn't really directly connected to your original question.

    If exploit X is discovered in version A, you get a security update to version B, where the vulnerability is fixed. If an attacker can exploit X in version A then you are safe, since you upgraded to B. But if the attacker can also downgrade you to A, then you are vulnerable again. You won't notice this even if all your secure hashes match the packages you have installed, since your package database will say that you are supposed to have A installed and not B.

     – Robie Basak Jan 11 '13 at 09:35
  • 2
    @RobieBasak "I don't believe that the apt repository format is properly specified or documented anywhere." Obviously this is not true. You just have to look for it. Debian Wiki: RepositoryFormat – gertvdijk Jan 11 '13 at 21:52
6

I wanted this to be a comment, but I couldn't fit it in the box so I'm placing it here.

Yes, md5 has been broken cryptologically, but that doesn't mean it's a bad general purpose hashing algorithm. Modifying a file so it has the same hash is incredibly difficult, and doing so with a particular malicious change is nigh on impossible. From looking at the example you referenced, (Predicting The Winner) see this:

"The documents were first carefully prepared as valid PDF documents, with a hidden image object incorporated, containing a sufficient amount of random bits. Then, according to the diamond structure shown above, eleven chosen-prefix collisions were computed, and placed inside the hidden image objects at precisely the proper spots. In this way the twelve documents were turned into an MD5 multi-collision."

What was done was filling the files with random data to make the hashes match. The technology isn't anywhere near capable of adding particular malicious code to a file and having the hashes line up without breaking it or making it obvious that the file has been changed (I don't know if apt does, but many file hashes are accompanied by their file sizes to increase the difficulty of an undetectable hash collision).

jackweirdy
  • 3,440
  • 3
    thank you for the answer. I think it is a good reply, in the sense that it gives more light to the whole background :) Unfortunatelly "Stack...Ask Ubuntu" is sometimes hard with "strictly reply to the question only" and so its great you took courage to elaborate on the topic. – humanityANDpeace Jan 10 '13 at 14:41
  • The prepared PDf files have random data and are only 104kb with all this effort. Why would you say this is impossible then? There must be tons of files in deb packages being >200kb where it must be possible to do such a thing. I feel not so safe after having seen the proof of concept , that amazed and shocked me – humanityANDpeace Jan 10 '13 at 14:42
  • There are lots of places in legitimate files where a subtle change would not appear odd, for example minor whitespace differences in a text file. You only need to find around 128 of these places to have sufficient scope to create a malicious file that both appears legitimate and also matches your desired target MD5. I'm not sure whether this particular attack could be applied to this situation though. – Robie Basak Jan 10 '13 at 14:50
  • @RobieBasak, you misunderstand the attack. You can not just go change 128 bytes in a file and preserve the md5sum. You have to insert a chunk of what otherwise appears to be two sets of random data into two copies of a file, and they will have the same md5sum as one another, despite the fact that the two chunks of "random" data are different. – psusi Jan 10 '13 at 15:40
2

md5 was not "broken". What they found was a way to carefully craft an original message, and a modified message that had the same hash. It is not possible to take an original message not specially crafted for the purpose of tampering with ( the correct file ), and modify it in such a way as to preserve its md5sum.

psusi
  • 37,551
  • ok. But what would be the good way to refer to the current state of MD5 security now, if not "broken"? I can understand what you say and I thanks for pointing that out. I still wonder how to evaluate the current safety by MD5 etc. – humanityANDpeace Jan 10 '13 at 14:53
  • @humanityANDpeace, "just fine". – psusi Jan 10 '13 at 14:53
  • I like the optimistic attitude. I was still amazed by the proof of concept afterall. thanks! – humanityANDpeace Jan 10 '13 at 14:54
  • @humanityANDpeace, it was in interesting experiment, and does point out a minor weakness in the algorithm, but tends to get blown out of proportion. The actual security implications are virtually nil. – psusi Jan 10 '13 at 14:56
  • I disagree. Unless you're one of the handful of people in the world who really understand this stuff, you should consider MD5 broken. There are various citations here: http://crypto.stackexchange.com/questions/3360/should-i-use-md5-for-my-new-application - who are we to say otherwise? – Robie Basak Jan 10 '13 at 15:01
  • @RobieBasak, don't see anything there that contradicts me, and I do understand this stuff. – psusi Jan 10 '13 at 15:06
  • @psusi from that page: US-CERT says MD5 "should be considered cryptographically broken and unsuitable for further use."

    It doesn't matter whether you think you understand this stuff or not. When it comes to crypto, either you have a worldwide reputation or you are a nobody who should not be trusted to provide advice (and note that I am a nobody here, too).

     – Robie Basak Jan 10 '13 at 15:10
  • "It is not possible to take an original message not specially crafted for the purpose of tampering with ( the correct file ), and modify it in such a way as to preserve its md5sum."

    You cannot prove such a negative in cryptography. If nobody has found a way, is this because crypto experts stopped looking further when they decided MD5 was broken?

     – Robie Basak Jan 10 '13 at 15:12
  • @RobieBasak, so you are saying you can not prove any hash is secure, which is a pointless statement. People looked for years and years and the best attack they could find requires control of both messages. That is a weakness and good reason to move away from the algorithm, but practically it can not be exploited. Hand waving about some magical undiscovered exploit that may exist is also a nonsense argument. – psusi Jan 10 '13 at 15:32
  • Crypto experts consider MD5 broken. Therefore it should be considered broken. QED. Disputing this in a question about what should be used for cryptographic security is not productive. – Robie Basak Jan 10 '13 at 15:38
  • @RobieBasak, an appeal to authority is a logical fallacy, and clarifying exactly what is wrong instead of applying the overly broad and misleading term "broken" is entirely productive. – psusi Jan 10 '13 at 15:43
  • 1
    "Crypto experts consider MD5 broken. Therefore it should be considered broken." that's not the way the world works @RobieBasak As a crypto enthousist (cant call myself an "expert" but I had to dig into it a few years back) myself I would not state MD5 is broken. Merely that there is an interesting case worth checking out but it seems theoratical atm. But it won't break Ubuntu's packaging ;) Back to 0 psusi ;) – Rinzwind Jan 10 '13 at 15:50
  • The black and white here is don't use MD5. It seems none of us are Crypto experts, so we can only follow their advice, which is use something else. @Rinzwind MD5 clearly is broken, as the question contains a working exploit... – jackweirdy Jan 10 '13 at 17:04
  • @jackweirdy, no, isn't black and white. The question does not contain a working exploit. A working exploit would be to modify a file in such a way as to preserve its md5sum. That is not what they do. – psusi Jan 10 '13 at 20:14
  • @psusi I see what you're saying now - but it's synonymous - they've crafted a file such that it's MD5sum matches with an arbitrary sum. There's no reason this exploit can't do the same thing where the "arbitrary sum" is the initial MD5sum of the file before any changes. – jackweirdy Jan 10 '13 at 22:28
  • 1
    @jackweirdy, actually, there is, and that's why they didn't do that. Their method relies on both sets of data having very specific properties. It is much like a public keypair. You can generate a pair of keys that match each other, but given only one, you can not figure out the other. – psusi Jan 11 '13 at 01:54
  • I see your point, but are you trying to argue that MD5 isn't broken? – jackweirdy Jan 11 '13 at 12:31