I'v been asked this question a few times over the last year or so, so I thought I would explain some of why you might see some issues on a Fedora or Red Hat Enterprise Linux system (or any other Linux distribution that uses prelinked binaries) when trying to track down strange MD5/SHA1 changes to binaries.
By default, and for nearly a decade now, prelink has shipped with Red Hat Enterprise Linux and Fedora. What it does is modify the ELF code in binaries and libraries to speed up load times, so that fewer relocations need to be resolved when executing a program. I can't explain all the details and technicalities of it because, quite frankly, they are above my limited brainpower to explain. Suffice it to say, prelinking is a good thing. Unless you are using AIDE or Tripwire. These programs determine whether or not a file has changed based on their MD5SUM or SHA1SUM (or any other *SUM of the binary). So when you install a program, AIDE sees a certain MD5SUM of the binary. Later, when prelink runs, that binary might be modified to do the aforementioned relocations. This will result in a different MD5SUM of the binary, and AIDE will most certainly tell you about the change. What does not inform you of the change, however, is rpm -V (or rpm --verify).
The verification command in RPM tells it to compare the MD5SUM of the files in certain package to what is on the filesystem. It's a poor man's AIDE, and can also tell you what has changed on your system (from what RPM expects according to when it was installed). In theory, you would expect rpm -V to report the same discrepancy that AIDE does. The fact that it doesn't is what's led to a few questions regarding this.
The "problem" (if you can call it that) is that rpm knows about prelink, and knows how to deal with it. As is succinctly explained in this mailing list email, "rpm when --verify will prelink --verify, which is essentially --undo followed by prelinking again and comparing." So the reason that rpm doesn't fail the verification is that it is basically turning off prelink for the file(s) to check, running the verification, then turning prelink back on. This is why rpm won't report on a MD5SUM change, but AIDE will.
So for those of us who use AIDE, we know that we need to do things like daily runs to make sure nothing has changed. The problem is that if you do this and run a yum update, X number of hours later you'll get an email telling you that files have changed. You might, at that point, update AIDE but there is a window of opportunity there where you may miss things. We can minimize this by doing an AIDE check, then yum update, then force a prelink run, then update AIDE. I've been doing this for a few years on Red Hat Enterprise Linux 5 and it essentially gets rid of all false positives. It's a little script called do-update that I execute as root and it runs this:
#!/bin/sh aidecheck && yum update -y && /etc/cron.daily/prelink && aideupdate
This doesn't eliminate the window of opportunity completely, but it does lessen it considerably. This uses my AIDE_gpg scripts (aidecheck and aideupdate). The rest is pretty self-explanatory.
Hopefully this information will be useful to someone. It took me a bit to dig up the mailing list message I link to above; I knew that prelink was had some special relationship with rpm, but I didn't know the particulars. Now I do, and so do you. =)