Solution
Format the EFI system partition as FAT16.
- Partitions up to 16 MiB should be formatted as FAT12.
- Partitions in the range of 16-32 MiB (inclusive) should be formatted as FAT16.
- For anything larger than 32 MiB — FAT32 is recommended. Although, technically, FAT16 supports volume sizes up to 2 GB (or even more, on specific OS'es).
Note, that since of all the three flavors of FAT the UEFI specification only requires FAT32 for system partitions, some tools choose not to support FAT12 partitions (<16 MiB). So things might not work with a partition that's smaller than 16 MiB, and you may not be able to, for example, install GRUB (the version of Calamares used by Parrot at the time of writing has this exact problem).
Script
Of the following only the archive creation and the partition inspection (lsblk and partprobe) operations can be performed by an unprivileged user, so you'd be better off if you could just run all of this in a root shell.
#!/bin/sh
ESP=/dev/sda1 ## EFI system partition (ESP).
ROOT=/dev/sda2 ## The partition of the root file system.
MNT=$(mktemp -d --suffix=-mnt) ## Mount point path.
TGZ=$(mktemp --suffix=-eps.tgz) ## ESP backup archive.
FSTAB=$MNT/etc/fstab ## The`fstab` of the root file system.
(
set -e ## Abort on error.
mount $ESP "$MNT" ## (2.1)
(cd "$MNT" && tar -czf "$TGZ" *) ## (2.2)
umount "$MNT" ## (2.3)
OLD=$(lsblk -no UUID $ESP) ## (3.1)
mkfs.vfat -F 16 $ESP ## (3.2)
partprobe $ESP ## (3.3)
NEW=$(lsblk -no UUID $ESP) ## (3.4)
mount $ROOT "$MNT" ## (4.1)
sed -Ei'' "s/^(UUID)=$OLD/\1=$NEW/" "$FSTAB" ## (4.2)
umount "$MNT" ## (4.3)
mount $ESP "$MNT" ## (5.1)
tar -C "$MNT" -xf "$TGZ" ## (5.2)
umount "$MNT" ## (5.3)
TYPE=$(lsblk -no PARTTYPENAME $ESP) ## Partition type name.
if [ "$TYPE" != "EFI System" ]; then ## (6.1)
DEV=${ESP%%[0-9]*}
parted $DEV set ${ESP#$DEV} esp on ## (6.2)
fi
)
Unlike the other variables that we can be sure are safe, MNT, TGZ and FSTAB have been quoted here because there is a chance, however slim, that the generated temporary names could contain characters that could break command invocations.
Steps in detail
Boot the system from a Live CD/DVD/USB that has the mkfs.vfat utility (the one you installed from should do).
Back up the contents of the EFI system partition.
Mount the partition.
We're using a temporary directory here, but you could use, e.g., /mnt (unless it is already being used by something else — check first).
Archive its contents to a gzipped TAR archive.
You could just as well copy all of it to some local directory, but archiving is safer.
Unmount the partition.
Format the file system of ESP as FAT16.
Back up the current file system UUID of the ESP.
You can skip this if you intend to perform the upcoming step 4.2 manually.
Use mkfs.vfat to format the partition.
If your ESP is smaller than 16 MiB, you should format it as FAT12 by passing 12 as the -F parameter instead.
This changes the file system UUID for the partition.
Ensure the operating system registers the above changes.
Get the new file system UUID for ESP.
To simplify the upcoming step 4.2, we're assigning it to a shell variable here, but you can also view the value by executing
lsblk -o UUID $ESP
Update /etc/fstab in the root partition with the new UUID
Mount the root partition.
Replace the old UUID in the root partition's /etc/fstab with the new value.
Alternatively, you could edit the fstab file and replace the value manually.
Unmount the partition.
Restore the backed-up ESP contents.
Mount the ESP again.
Extract the archived contents.
Unmount the partition.
Ensure that the ESP actually has the correct partition type.
Check if the partition type name matches EFI System.
Alternatively, you could compare c12a7328-f81f-11d2-ba4b-00a0c93ec93b with what is returned by
lsblk -no PARTTYPE $ESP
Either way, the next step is not necessary if we get a match here.
Use parted to set the partition type (if necessary).
We're using crude shell pattern matching to separate the device name (e.g. /dev/sda) and the partition number (e.g. 1) when calling parted, since that is the argument format it requires.
Verify
You could (and probably, should) verify that the partition has the valid format and type now by running lsblk:
$ lsblk -o PATH,FSTYPE,FSVER,PARTTYPE,PARTTYPENAME $ESP
PATH FSTYPE FSVER PARTTYPE PARTTYPENAME
/dev/sda1 vfat FAT16 c12a7328-f81f-11d2-ba4b-00a0c93ec93b EFI System
You should be seeing FAT12 in that output, if that is what you were aiming for instead of FAT16.
Reboot
UEFI should be able to recognize the partition and successfully boot the system now.
