Replace/substitute adversarial substring variables

I have three unescaped adversarial shell variables.

$mystring
$old
$new

Remember, all three strings are adversarial. They will contain special characters. They will contain everything possible to mess up the replace. If there is a loophole in your replace, the strings will exploit it.

What is the simplest function to replace $old with $new in $mystring? (I couldn't find any solution in stack overflow for a generic substitution that will work in all cases).

There's nothing fancy here -- the only thing you need to do to ensure that your values are treated as literals in a parameter expansion is to ensure that you're quoting the search value, as described in the relevant section of BashFAQ #21:

result=${mystring/"$old"/$new}

Without the double quotes on the inside, $old would be interpreted as a fnmatch-style glob expression; with them, it's literal.

To operate on streams instead, consider gsub_literal, also described in BashFAQ #21:

# usage: gsub_literal STR REP
# replaces all instances of STR with REP. reads from stdin and writes to stdout.
gsub_literal() {
  # STR cannot be empty
  [[ $1 ]] || return

  # string manip needed to escape '\'s, so awk doesn't expand '\n' and such
  awk -v str="${1//\\/\\\\}" -v rep="${2//\\/\\\\}" '
    # get the length of the search string
    BEGIN {
      len = length(str);
    }

    {
      # empty the output string
      out = "";

      # continue looping while the search string is in the line
      while (i = index($0, str)) {
        # append everything up to the search string, and the replacement string
        out = out substr($0, 1, i-1) rep;

        # remove everything up to and including the first instance of the
        # search string from the line
        $0 = substr($0, i + len);
      }

      # append whatever is left
      out = out $0;

      print out;
    }
  '
}

some_command | gsub_literal "$search" "$rep"

...which can also be used for in-place replacement on files using techniques from the following (yet again taken from the previously-linked FAQ):

# Using GNU tools to preseve ownership/group/permissions
gsub_literal "$search" "$rep" < "$file" > tmp &&
  chown --reference="$file" tmp &&
  chmod --reference="$file" tmp &&
  mv -- tmp "$file"