diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index 6b8bf15..adbd32d 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -990,7 +990,8 @@
   return cert
 
 
-def MakeRecoveryPatch(input_dir, output_sink, recovery_img, boot_img):
+def MakeRecoveryPatch(input_dir, output_sink, recovery_img, boot_img,
+                      info_dict=None):
   """Generate a binary patch that creates the recovery image starting
   with the boot image.  (Most of the space in these images is just the
   kernel, which is identical for the two, so the resulting patch
@@ -1003,6 +1004,9 @@
   common.LoadInfoDict() on the input target_files.
   """
 
+  if info_dict is None:
+    info_dict = OPTIONS.info_dict
+
   diff_program = ["imgdiff"]
   path = os.path.join(input_dir, "SYSTEM", "etc", "recovery-resource.dat")
   if os.path.exists(path):
@@ -1016,8 +1020,8 @@
   _, _, patch = d.ComputePatch()
   output_sink("recovery-from-boot.p", patch)
 
-  boot_type, boot_device = GetTypeAndDevice("/boot", OPTIONS.info_dict)
-  recovery_type, recovery_device = GetTypeAndDevice("/recovery", OPTIONS.info_dict)
+  boot_type, boot_device = GetTypeAndDevice("/boot", info_dict)
+  recovery_type, recovery_device = GetTypeAndDevice("/recovery", info_dict)
 
   sh = """#!/system/bin/sh
 if ! applypatch -c %(recovery_type)s:%(recovery_device)s:%(recovery_size)d:%(recovery_sha1)s; then
diff --git a/tools/releasetools/sign_target_files_apks b/tools/releasetools/sign_target_files_apks
index ab24706..bf16436 100755
--- a/tools/releasetools/sign_target_files_apks
+++ b/tools/releasetools/sign_target_files_apks
@@ -77,6 +77,7 @@
 import errno
 import os
 import re
+import shutil
 import subprocess
 import tempfile
 import zipfile
@@ -139,14 +140,40 @@
   return data
 
 
-def SignApks(input_tf_zip, output_tf_zip, apk_key_map, key_passwords):
+def ProcessTargetFiles(input_tf_zip, output_tf_zip, misc_info,
+                       apk_key_map, key_passwords):
   maxsize = max([len(os.path.basename(i.filename))
                  for i in input_tf_zip.infolist()
                  if i.filename.endswith('.apk')])
+  rebuild_recovery = False
+
+  tmpdir = tempfile.mkdtemp()
+  def write_to_temp(fn, attr, data):
+    fn = os.path.join(tmpdir, fn)
+    if fn.endswith("/"):
+      fn = os.path.join(tmpdir, fn)
+      os.mkdir(fn)
+    else:
+      d = os.path.dirname(fn)
+      if d and not os.path.exists(d):
+        os.makedirs(d)
+
+      if attr >> 16 == 0xa1ff:
+        os.symlink(data, fn)
+      else:
+        with open(fn, "wb") as f:
+          f.write(data)
 
   for info in input_tf_zip.infolist():
     data = input_tf_zip.read(info.filename)
     out_info = copy.copy(info)
+
+    if (info.filename.startswith("BOOT/") or
+        info.filename.startswith("RECOVERY/") or
+        info.filename.startswith("META/") or
+        info.filename == "SYSTEM/etc/recovery-resource.dat"):
+      write_to_temp(info.filename, info.external_attr, data)
+
     if info.filename.endswith(".apk"):
       name = os.path.basename(info.filename)
       key = apk_key_map[name]
@@ -163,14 +190,43 @@
       print "rewriting %s:" % (info.filename,)
       new_data = RewriteProps(data)
       output_tf_zip.writestr(out_info, new_data)
+      if info.filename == "RECOVERY/RAMDISK/default.prop":
+        write_to_temp(info.filename, info.external_attr, new_data)
     elif info.filename.endswith("mac_permissions.xml"):
       print "rewriting %s with new keys." % (info.filename,)
       new_data = ReplaceCerts(data)
       output_tf_zip.writestr(out_info, new_data)
+    elif info.filename in ("SYSTEM/recovery-from-boot.p",
+                           "SYSTEM/bin/install-recovery.sh"):
+      rebuild_recovery = True
+    elif (OPTIONS.replace_ota_keys and
+          info.filename in ("RECOVERY/RAMDISK/res/keys",
+                            "SYSTEM/etc/security/otacerts.zip")):
+      # don't copy these files if we're regenerating them below
+      pass
     else:
       # a non-APK file; copy it verbatim
       output_tf_zip.writestr(out_info, data)
 
+  if OPTIONS.replace_ota_keys:
+    new_recovery_keys = ReplaceOtaKeys(input_tf_zip, output_tf_zip, misc_info)
+    if new_recovery_keys:
+      write_to_temp("RECOVERY/RAMDISK/res/keys", 0755 << 16, new_recovery_keys)
+
+  if rebuild_recovery:
+    recovery_img = common.GetBootableImage(
+        "recovery.img", "recovery.img", tmpdir, "RECOVERY", info_dict=misc_info)
+    boot_img = common.GetBootableImage(
+        "boot.img", "boot.img", tmpdir, "BOOT", info_dict=misc_info)
+
+    def output_sink(fn, data):
+      output_tf_zip.writestr("SYSTEM/"+fn, data)
+
+    common.MakeRecoveryPatch(tmpdir, output_sink, recovery_img, boot_img,
+                             info_dict=misc_info)
+
+  shutil.rmtree(tmpdir)
+
 
 def ReplaceCerts(data):
   """Given a string of data, replace all occurences of a set
@@ -265,7 +321,8 @@
   for k in keylist:
     m = re.match(r"^(.*)\.x509\.pem$", k)
     if not m:
-      raise common.ExternalError("can't parse \"%s\" from META/otakeys.txt" % (k,))
+      raise common.ExternalError(
+          "can't parse \"%s\" from META/otakeys.txt" % (k,))
     k = m.group(1)
     mapped_keys.append(OPTIONS.key_map.get(k, k) + ".x509.pem")
 
@@ -287,10 +344,11 @@
                   os.path.join(OPTIONS.search_path, "framework", "dumpkey.jar")]
                  + mapped_keys + extra_recovery_keys,
                  stdout=subprocess.PIPE)
-  data, _ = p.communicate()
+  new_recovery_keys, _ = p.communicate()
   if p.returncode != 0:
     raise common.ExternalError("failed to run dumpkeys")
-  common.ZipWriteStr(output_tf_zip, "RECOVERY/RAMDISK/res/keys", data)
+  common.ZipWriteStr(output_tf_zip, "RECOVERY/RAMDISK/res/keys",
+                     new_recovery_keys)
 
   # SystemUpdateActivity uses the x509.pem version of the keys, but
   # put into a zipfile system/etc/security/otacerts.zip.
@@ -304,6 +362,8 @@
   common.ZipWriteStr(output_tf_zip, "SYSTEM/etc/security/otacerts.zip",
                      tempfile.getvalue())
 
+  return new_recovery_keys
+
 
 def BuildKeyMap(misc_info, key_mapping_options):
   for s, d in key_mapping_options:
@@ -375,10 +435,8 @@
   CheckAllApksSigned(input_zip, apk_key_map)
 
   key_passwords = common.GetKeyPasswords(set(apk_key_map.values()))
-  SignApks(input_zip, output_zip, apk_key_map, key_passwords)
-
-  if OPTIONS.replace_ota_keys:
-    ReplaceOtaKeys(input_zip, output_zip, misc_info)
+  ProcessTargetFiles(input_zip, output_zip, misc_info,
+                     apk_key_map, key_passwords)
 
   input_zip.close()
   output_zip.close()