The funny thing is, you don't actually need to replace a package that's part of the base distribution. Every package format we have (RPM, DEB, etc.) runs its install- and upgrade-scripts as root, so every package can potentially do anything on install, including patching the installed files of other packages (or cleverer things, like adding SSL trust roots.)
So, since they don't specifically need to patch your openssl package to compromise your openssl library, they could just as well suborn the signing key of (presuming Ubuntu) some PPA author, as long as the user they're trying to bug has that PPA in their sources.list.