diff --git a/recovery/Android.mk b/recovery/Android.mk
index 585db84..0034dc8 100644
--- a/recovery/Android.mk
+++ b/recovery/Android.mk
@@ -17,7 +17,7 @@
 # Edify extension functions for doing bootloader updates on Tuna devices.
 
 LOCAL_MODULE_TAGS := optional
-LOCAL_C_INCLUDES += bootable/recovery
+LOCAL_C_INCLUDES += bootable/recovery system/vold
 LOCAL_SRC_FILES := recovery_updater.c bootloader.c
 
 # should match TARGET_RECOVERY_UPDATER_LIBS set in BoardConfig.mk
diff --git a/recovery/recovery_updater.c b/recovery/recovery_updater.c
index 02963f5..0c49f9a 100644
--- a/recovery/recovery_updater.c
+++ b/recovery/recovery_updater.c
@@ -19,6 +19,11 @@
 #include <stdarg.h>
 #include <stdlib.h>
 #include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <cryptfs.h>
 
 #include "edify/expr.h"
 #include "bootloader.h"
@@ -55,8 +60,68 @@
     return StringValue(strdup(result == 0 ? "t" : ""));
 }
 
+/*
+ * The size of the userdata partition for HSPA Galaxy Nexus devices is incorrect
+ * in the partition as it comes from the factory.  Updating the bootloader fixes
+ * the partition table, and makes the size of the userdata partition 1 sector
+ * smaller.  However, if the user had encrypted their device with the original
+ * incorrect size of the partition table, the crypto footer has saved that
+ * size, and tries to map that much data when decrypting.  However, with the
+ * new partition table, that size is too big to be mapped, and the kernel
+ * throws an error, and the user can't decrypt and boot the device after the
+ * OTA is installed.  Oops!
+ *
+ * The fix here is to recognize a crypto footer that has the wrong size, and
+ * update it to the new correct size.  This program should be run as part of
+ * the recovery script for HSPA Galaxy Nexus devices.
+ */
+
+#define BAD_SIZE  0x01b14fdfULL
+#define GOOD_SIZE 0x01b14fdeULL
+
+#define HSPA_PRIME_KEY_PARTITION "/dev/block/platform/omap/omap_hsmmc.0/by-name/metadata"
+
+Value* FsSizeFixFn(const char* name, State* state, int argc, Expr* argv[])
+{
+    struct crypt_mnt_ftr ftr;
+    int fd;
+
+    if (argc != 0) {
+        return ErrorAbort(state, "%s() expects 0 args, got %d", name, argc);
+    }
+
+    if ((fd = open(HSPA_PRIME_KEY_PARTITION, O_RDWR)) == -1) {
+        return ErrorAbort(state, "%s() Cannot open %s\n", name, HSPA_PRIME_KEY_PARTITION);
+    }
+
+    if (read(fd, &ftr, sizeof(ftr)) != sizeof(ftr)) {
+        close(fd);
+        return ErrorAbort(state, "%s() Cannot read crypto footer %s\n", name, HSPA_PRIME_KEY_PARTITION);
+    }
+
+   if ((ftr.magic == CRYPT_MNT_MAGIC) && (ftr.fs_size == BAD_SIZE)) {
+        ftr.fs_size = GOOD_SIZE;
+        if (lseek(fd, 0, SEEK_SET) == 0) {
+            if (write(fd, &ftr, sizeof(ftr)) == sizeof(ftr)) {
+                fsync(fd); /* Make sure it gets to the disk */
+                fprintf(stderr, "Footer updated\n");
+                close(fd);
+                return StringValue(strdup("t"));
+            }
+        }
+        close(fd);
+        return ErrorAbort(state, "%s() Cannot seek or write crypto footer %s\n", name, HSPA_PRIME_KEY_PARTITION);
+    }
+
+    /* Nothing to do */
+    fprintf(stderr, "Footer doesn't need updating\n");
+    close(fd);
+    return StringValue(strdup("t"));
+}
+
 void Register_librecovery_updater_tuna() {
     fprintf(stderr, "installing samsung updater extensions\n");
 
     RegisterFunction("samsung.write_bootloader", WriteBootloaderFn);
+    RegisterFunction("samsung.fs_size_fix", FsSizeFixFn);
 }
diff --git a/releasetools.py b/releasetools.py
index 23581d6..056c7dc 100644
--- a/releasetools.py
+++ b/releasetools.py
@@ -32,6 +32,8 @@
   else:
     WriteRadio(info, radio_img)
 
+  FsSizeFix(info)
+
 def IncrementalOTA_VerifyEnd(info):
   try:
     target_radio_img = info.target_zip.read("RADIO/radio.img")
@@ -74,6 +76,12 @@
   except KeyError:
     print "no radio.img in target target_files; skipping install"
 
+  FsSizeFix(info)
+
+def FsSizeFix(info):
+  info.script.Print("Fixing fs_size in crypto footer...")
+  info.script.AppendExtra('''assert(samsung.fs_size_fix());''')
+
 def WriteBootloader(info, bootloader_img):
   common.ZipWriteStr(info.output_zip, "bootloader.img", bootloader_img)
   fstab = info.info_dict["fstab"]