tar will add files in the order of the filesystem. This can vary from one build to the next.

Solution

Instead of solely using tar, use find+sort+tar.

Before:

tar -cf archive.tar src

After for Tar version 1.28+:

tar --sort=name -cf archive.tar src

After for older versions of Tar:

find src -print0 | LC_ALL=C sort -z | tar --no-recursion --null -T - -cf archive.tar

ReproducibleBuildsFileOrderInTarballs