Building a fully immutable Linux OS image, fully verified with your own Secure Boot key

Today, QubesOS does not offer any protection against malware persistence, not even at dom0 or hypervisor level, as QubesOS completely lack boot verification. QubesOS does not even offer boot verification as an optional addition. The few desktop operating system that does implement some kind of verified boot, such as Ubuntu, only verifies kernel space, and fail to lock trust to only their own signing key, thus providing little to no security benefit in practice.

A few months back I set out on a mission to see if it is viable today for an OS vendor to implement full protection against malware persistence, relying only on functionality present in regular hardware and BIOS firmware, such as Secure Boot and TPM support. I decided to try to protect a custom built “live” version of a regular Linux distribution in this sense, so that all of user space including configuration is fully verified at boot, and below is a write-up of my findings, for anyone interesting in learning how it is done, or how to replicate it. Not only is it possible to do, but since at least a year back, all tooling exists to do so easily.

Every Linux distribution that is serious about security should implement this now, as it improves system security in very tangible ways. To the best of my knowledge, no Linux distribution at all implements full boot verification today, not even security focused ones like SecureBlue. What follows is how to turn it into a reality.

At the end is some reflections about how to also turn QubesOS hypervisor, dom0, sys-usb, sys-net, sys-firewall and sys-whonix into being fully immutable and fully verified at boot, in a secure way fully preventing malware persistence.

Overview:

Legacy boot will be disabled, and Secure Boot will be enabled in BIOS settings, with Deny Execution as default policy on violations for OpROMs and bootloaders alike. All default provisioned Secure Boot certificates will be deleted, and your own will be provisioned instead, plus hashes for all OpROMs logged to tpm2_eventlog during regular system startup. The latter is needed to ensure BIOS can load and execute the graphic driver from your GPU PCI-e slot, so you have visuals in early boot and still can access BIOS settings. This provides the foundation for ensuring only your own authentic OS images can be booted, nothing else.

The only step the user installing the operating system needs to do themselves is enabling Secure Boot and putting Secure Boot in Setup Mode by deleting all existing certificates through BIOS settings. The actual provisioning of your own OS signing key can be done by the installation program for your own OS. Once installed, the user never have to do anything again, everything will be transparent to them, as new OS images are signed by the same already enrolled Secure Boot key.

Secure Boot will now validate the EFI bootloader, and refuse to execute it unless it is signed by you. The EFI bootloader will be a Unified Kernel Image (UKI), containing the Linux kernel, the initrd, and the boot parameters. This ensures an attacker can not modify or replace the kernel nor initrd, nor modify the boot parameters in any way, as all of that is signed as a unit and verified at boot.

The whole of user space, including all apps and configuration, will be an immutable file system image (a single squashfs or erofs image file). A dm-verity file for the immutable image, containing all block hashes for the immutable image, will also be stored next to the image. Boot parameters will include the partition UUID and file path to the immutable image to boot. Boot parameters will also include a dm-verity root hash for the immutable image. The already verified authentic and unmodified initrd will read the already verified and authentic boot parameters. It will setup dm-verity in “reboot-on-corruption” mode, using the immutable image and its dm-verity file. Since the root hash is already verified authentic and unmodified, any modifications done to either the immutable image or dm-verity file will be detected when the corresponding block is being read, since dm-verity verifies all reads. The system will refuse to continue execution if this happens, making sure an attacker can not affect system execution in any way, not even by causing targetted I/O errors (dm-verity default mode). Since verification happens on each block read rather than full scan at boot, there is negligable boot time overhead, and any modifications happening post boot will also be detected. All persistence of malicious code is prevented.

To support writes, initrd will mount an overlay as “/”, with the dm-verity protected file system mount as lower layer, and a tmpfs (RAM backed) file system as upper writable layer. This ensures Linux functions as it should, without any support for persistence. If the user wants to save files or app data, they can create a separate LUKS encrypted partition, and store those files there.

An OS vendor would atomically replace the UKI image, file system image, and dm-verity file upon system update. This whole setup is very similar to the setup on Android devices, which also uses dm-verity in this manner. The OS vendor would likely also allow persisting user files and app data, for example by mounting the encrypted user data volume at a certain path at login, like in Tails, or as the home folder, like on Android.

Rollback protection to guard against downgrade attacks should also be possible to implement. One can apparently setup UEFI variables such that only a verified bootloader can update the value, making it possible to write a counter that way, and making all UKIs ever signed by the same Secure Boot key check what the counter is and refuse to boot if counter is higher than their built-in value, preventing downgrade attacks. This solution is apparently implemented by Secure Version Number (SVN, Windows) and Secure Boot Advanced Targeting (SBAT, Linux). An OS vendor would want to do this. I haven’t made a proof-of-concept of this. If you are just making your own OS images for yourself, you can just enroll a new Secure Boot key each time. But an OS vendor would want to implement rollback protection, so a malware cannot rollback to earlier more vulnerable versions.

In addition to preventing malware persistence, one might want to protect against attackers with physical access to your device, or allow for attesting system security post-install. Setting a BIOS boot and setup password raises the bar a little against a physical attacker (Evil Maid) trying to disable Secure Boot or replace the enrolled keys with their own. You would notice any fool play even if they jumper reset your BIOS, as long as the attacker doesn’t know your BIOS password and thus cannot set the right one again. This should lower the risk you leak your disk encryption passphrase to them. The attacker cannot replace the BIOS, since it is verified by keys burned into fuses on your device. But they might be able to change specific BIOS settings by reflashing the chip holding them, and they definitely can get your disk encryption passphrase using a pinhole camera or hardware keylogger anyway.

As for attestation, no BIOS today prints the hash of the enrolled Secure Boot key during boot, making it impossible to inspect from a verified environment whether the next step that will be loaded is also secure. Theoretically, values written to TPM PCR registers can be used for attestation, but it is unclear if they are adequately protected. At least one BIOS vendor (MSI) is also adding that Secure Boot is enabled to the PCR registers, despite it being effectively disabled by execution policies being set to “Always execute”. Ideally, the BIOS would print the full hash of the enrolled signing key at boot, for you to verify, or at least not outright lie to the TPM about system state.

Detailed how-to instructions:

Step 1 - Install and setup Linux distribution exactly like you want it

Start by installing a regular Linux distribution in the usual way. I used Linux Mint, so this should work just fine on any Debian based distribution. Install any software you might want, and make any configuration changes you might want. If installing proprietary NVidia drivers, make sure to install the version with properly signed kernel modules, or they won’t load. On Linux Mint, do this by install linux-modules-nvidia-VER-generic before nvidia-driver-VER. To reduce image size, remove unnecessary application, all kernels except the latest, and clear package manager cache and similar. Do not access any privacy sensitive files nor enter any personal passwords at all during this step. The image you build must be made in such a way you could distribute it to anyone.

Step 2 - Prepare initrd to support booting dm-verity protected immutable image

Add support for dm-verity in the initrd image. This will be used to allow initrd to mount the user space image in such a way that system can detect any modification made and prevent further execution of the system. Create “/usr/share/initramfs-tools/hooks/veritysetup” with the following content:

#!/bin/sh
. /usr/share/initramfs-tools/hook-functions
copy_exec /sbin/veritysetup /sbin
manual_add_modules dm_verity

Edit “/usr/share/initramfs-tools/init”. Add the following two code snippets in the respective correct list in that file, to allow passing in our custom boot parameters.

export SQUASHFILE=
export VERITYHASH=
squashfile=*)
    SQUASHFILE=${x#squashfile=}
    ;;
verityhash=*)
    VERITYHASH=${x#verityhash=}
    ;;

Finally also edit “/usr/share/initramfs-tools/scripts/local” to add support for mounting dm-verity protected immutable file system images, replacing the support for the regular root file system mounting.

Replace this:

# Mount root
# shellcheck disable=SC2086
mount ${roflag} ${FSTYPE:+-t "${FSTYPE}"} ${ROOTFLAGS} "${ROOT}" "${rootmnt?}"

With this:

# Mount read-only file system image
modprobe ext4
modprobe squashfs
modprobe dm_verity
mkdir -p /fsimage
mkdir -p /medium
mount -t ext4 -o ro,noatime "$ROOT" /medium
veritysetup open --reboot-on-corruption "/medium/${SQUASHFILE#/}" verityimg "/medium/${SQUASHFILE#/}.verity" "$VERITYHASH"
mount -t squashfs -o ro,noatime /dev/mapper/verityimg /fsimage

# Mount writable upper layer
mkdir -p /cow
mount -t tmpfs -o rw,noatime,mode=0755 tmpfs /cow

# Mount the combination of both as the root
modprobe overlayfs
mkdir -p /cow/upper
mkdir -p /cow/work
mount -t overlay -o noatime,lowerdir=/fsimage,upperdir=/cow/upper,workdir=/cow/work overlay "$rootmnt"

# Make the underlying filesystems visible inside
mkdir -p "$rootmnt/livemnt/medium"
mkdir -p "$rootmnt/livemnt/fsimage"
mkdir -p "$rootmnt/livemnt/cow"
mount -o bind /medium "$rootmnt/livemnt/medium"
mount -o bind /fsimage "$rootmnt/livemnt/fsimage"
mount -o bind /cow "$rootmnt/livemnt/cow"

Now run the below as root to regenerate the “initrd.img” file. Run this from within the installation itself.

chmod +x /usr/share/initramfs-tools/hooks/veritysetup
update-initramfs -u

Edit /etc/fstab so it does not mount and even mention any file systems. The user space must not auto-mount any file systems ever.

Step 3 - Convert into a dm-verity protected immutable OS image

Create an ext4 partition to hold the immutable file system images, and nothing else. Place your terminal in that partition, and execute the below as root. Here I use squashfs, but erofs is recommended today because of better file system attribute support. Execute this from another Linux installation to ensure no files are updated while the image generation progresses.

mksquashfs /path/to/filesystem-root filesystem.squashfs -noappend
veritysetup format filesystem.squashfs filesystem.squashfs.verity

Take note of the root hash mentioned in that last command. This is the one we will need to add to our boot parameters in the UKI image. Now create the UKI image as root. Replace ${UUID} with the UUID of the ext4 partition holding the squashfs image and dm-verity file, and ${ROOTHASH} with the actual root hash value.

ukify build --linux /path/to/filesystem-root/boot/vmlinuz --initrd /path/to/filesystem-root/boot/initrd.img --cmdline "root=UUID=${UUID} squashfile=/filesystem.squashfs verityhash=${ROOTHASH} ro quiet splash"

It is advisable to add more security hardening boot options, including zero-on-free support to prevent cold boot attacks, and disabling of EFI pstore and ERST to prevent persisting system logs to EFI or ACPI variables, which can leak information about files in encrypted volumes. I would add this after the “splash” option: “slab_nomerge slub_debug=FZ mce=0 vsyscall=none init_on_free=1 mds=full,nosmt page_alloc.shuffle=1 randomize_kstack_offset=on efi_pstore.pstore_disable=1 erst_disable spec_store_bypass_disable=on”, which is the boot parameters Tails is using. I have not verified whether they work on Ubuntu kernels though.

Delete any data already existing on the EFI system partition, and then place the generated UKI as “/EFI/BOOT/BOOTX64.EFI”. This should be enough, but just to be certain, use “efibootmgr” to delete all existing configurations, and then register the new one:

efibootmgr --create --disk /dev/sda --part 1 --label "My operating system" --loader '\EFI\BOOT\BOOTX64.EFI'

Step 4 - Sign UKI image and enroll keys to Secure Boot.

Make sure Secure Boot is in Setup Mode by deleting all enrolled certificates from the BIOS settings before booting. Secure Boot should be enabled in BIOS settings, but will present as disabled during boot since in Setup Mode.

Now generate a new signing key and sign the UKI image. Make sure you do not save the generated keys anywhere where an attacker can later access them. If you are an OS vendor, you should adequately protect them on some hardware security module on some offline system. If you are just creating this OS images for yourself, you can just write the keys to a RAM backed file system while offline on a trusted system, so they aren’t persisted at all. You won’t need to sign anything more in the future, as you can just put Secure Boot back in Setup Mode and enroll new keys each time.

openssl req -newkey rsa:4096 -nodes -keyout sign.key -new -x509 -sha256 -days 3650 -subj "/CN=My EFI Signing Key/" -out sign.crt
sbsign --key sign.key --cert sign.crt --output /EFI/BOOT/BOOTX64.EFI /EFI/BOOT/BOOTX64.EFI

Now, fetch all hash values for OpROM images loaded at boot. On some systems, like laptops, there will be none. If you have a desktop computer with a discrete GPU, there will usually be one OpROM hash for the GPU. If you have a RAID controller, there might be one more. Take note of each SHA256 hash for the EV_EFI_BOOT_SERVICES_DRIVER entries that was measured to the TPM2 PCR registers at boot.

tpm2_eventlog /sys/kernel/security/tpm0/binary_bios_measurements

An OS vendor might want to fetch all OpROM hashes for systems they want to support, and add them to a machine specific db, signed by the OS vendors PK and KEK keys. It might be tempting to just fetch the OpROM hashes during the installation program, but that would mean the PK and KEK keys needs to be generated by the installation program, and there is no way to attest they were generated securily and destroyed securely, so that would break the ability to attest system authencity. The OS vendor needs to take care to only sign OpROM hashes they themselves have verified authentic.

Now, create and sign the PK, KEK and db EFI variable data.

GUID=$(uuidgen --random)
cert-to-efi-sig-list -g $GUID sign.crt sign.esl
echo ${OPROM_HASH} | xxd -r -p > hash
sbsiglist --owner $GUID --type sha256 --output oprom.esl hash
cat sign.esl oprom.esl > db.esl
openssl req -newkey rsa:4096 -nodes -keyout pk.key -new -x509 -sha256 -days 3650 -subj "/CN=My Platform Key/" -out pk.crt
openssl req -newkey rsa:4096 -nodes -keyout kek.key -new -x509 -sha256 -days 3650 -subj "/CN=My Key Exchange Key/" -out kek.crt
cert-to-efi-sig-list -g $GUID pk.crt pk.esl
cert-to-efi-sig-list -g $GUID kek.crt kek.esl
sign-efi-sig-list -g $GUID -k pk.key -c pk.crt PK pk.esl pk.auth
sign-efi-sig-list -g $GUID -k pk.key -c pk.crt KEK kek.esl kek.auth
sign-efi-sig-list -g $GUID -k kek.key -c kek.crt db db.esl db.auth

Upload it to the EFI variable storage as root. The last command below uploads the PK variable, which will cause Secure Boot to be enabled, and Setup Mode to be exited. The next reboot, Secure Boot will be enforced.

mkdir a
mkdir a/PK
mkdir a/KEK
mkdir a/db
mv pk.auth a/PK/PK.auth
mv kek.auth a/KEK/KEK.auth
mv db.auth a/db/db.auth
sbkeysync --keystore a --verbose
sbkeysync --keystore a --verbose --pk

That is all. An OS vendor would create and sign all EFI variable data in their own secure environment, distribute the signed data (.auth files) in their installation program, which uploads them to the EFI variable storage on the user’s machine.

A fully installed system will have uploaded the PK, KEK and db EFI variables to EFI variable storage, will have a EFI system partition holding a single file “/EFI/BOOT/BOOTX64.EFI”, and will have an ext4 partition holding two files “filesystem.squashfs” and “filesystem.squashfs.verity”. That is all. The remaining disk space can be allocated to one or more user data partition, all preferably LUKS encrypted. On top of that, the user is supposed to have enabled Secure Boot, set default violation policy to Deny Execution for everything, and have deleted all pre-provisioned certificates to set Secure Boot in Setup Mode, prior to running the installation program.

Future:

For the future, a quick internet search reveals that Xen has full support for being bundled in a UKI like EFI image, together with all Xen configuration, dom0 kernel and dom0 initrd. This alone should be enough to implement full boot verification in QubesOS in a secure way, that is easy to use, and works on almost all hardware. This would remove the possibility for the user to modify dom0 configuration, but the user is not supposed to do that anyway, and if the user can, so might an attacker. It’s better to be certain the OS including all of dom0 is in an authentic and secure state.

Individual template qubes and app qubes will not be protected this way though, but the isolation between them will. QubesOS design is fundamentally incompatible with extending verification further in, as apps would need to be immutable and signed images too for that to work. Maybe Flatpaks are one possible avenue for the future, to allow verifying the full system authencity.

Any criticism or thoughts are welcome!

5 Likes

I would change SHA256 to SHA384, if the boot process supported that.

I might also think about the pros/cons of generating those keys within a YubiKey/NitroKey etc.

But thanks for sharing, it is an interesting guide.

1 Like

I studied and wrote about immutability, it’s rarely truly immutable (between boots) except when using a livecd as the medium is immutable itself.

But how do you are productive with a truly immutable system that won’t change after a reboot? (this can work if the user do not require mutable states, like files)

How do you keep it up to date? How to make the squashfs update transactional?

3 Likes

QubesOS does not offer any protection against malware persistence

I think everyone would appreciate it if the post did not start with sensational and even false statements. QubesOS does not offer the level of protection described in this post by default but it does offer protection in the form of Disposable VMs (of course with there maybe being ways to bypass that by very advanced malware), so your statment is just false and designed to farm attention.

I would change it to mention that it does not offer protection against malware in dom0/the bootloader, as this is not clear from your post. To me it reads as if “QubesOS did not offer any protection against malware AT ALL” which is false.

Sorry if I sound needlessly combative, but with so many clickbait articles (and more now, written by LLMs), I’ve been trying to work against sensationalism.

7 Likes

Thank you for the nice guide! Perhaps it should be moved to Community Guides from General Discussion. (I’ve just moved.)

Qubes can be used with TPM, Heads and a hardware key for verified boot and with /boot and /root verification. Works for me. Restricted boot is possible too. All is FLOSS.

Related: Verified boot on Qubes -- a lofty dream?

5 Likes

It’s not related to Qubes OS to me, why should it be a community guide?

2 Likes

In my opinion, if it’s compatible and can improve your security according to some threat model (can it?), it should be good enough. I definitely can be wrong here though.

2 Likes

AFAIK this can’t be used by dom0, and I don’t think Xen expose the features required for this guide to work. So I don’t think it’s useful for Qubes OS users, apart for literature.

3 Likes

Nope, the hash must be SHA256. Since the hashes are used for verification (second pre-image, see Preimage attack - Wikipedia), SHA256 should provide about 128-bits of security against a quantum computer and 256-bit security against regular computers. So that should be fine.

Yeah, some kind of hardware security module would be recommended, I think I mentioned that. Not any specific brand though.

I would be interesting in reading that. Do you have any links?

Actually, I have been running my immutable version of Linux Mint since about 2015 or something. I just create separate LUKS partitions where I store any file I want to keep, or any app data that I want to keep (symlinking from /home). This ensures no persistent state is loaded until I have unlocked a LUKS partition, and either executed something from there or symlinked in something from there. Before 2015 I used Tails, which works in the same way.

The only new thing I did now was protecting the immutable image with Secure Boot. Before, it could have been compromised by an attacker having gained root.

Yeah, that is not very practical if rolling your own, as you need to build a new immutable image each time. It would have to be scripted/automated in some sense. But for an OS vendor they could easily do that and ensure security updates are released in a timely manner.

ln filesystem.squashfs filesystem.squashfs.old
mv filesystem.squashfs.new filesystem.squashfs

Android have two separate partitions I believe, they write the immutable image to the one that is not currently booted, and then just flip a flag about which to boot next time.

2 Likes
3 Likes

I thought the way I phrased it would be clear I am talking about the boot, sorry if it lead to any confusion or made it feel I made a false or sensational statement. That was not my intention. You could run a virtual machine on top of any host OS and run potentially malicious things in there, and claim you have some protection against malware persistence, but when we are talking about protecting against malware persistence at OS level, we usually always talk about it in terms of preventing malware that has infected the system from reinfecting the system at next boot.

I was under the impression Heads only attempts to protect against a physical attacker, by making it harder to unlock the disk encryption unless the correct boot sequence was measured to TPM PCR registers? And did not attempt to protect against malware persistence at all? Am I mistaken?

From the description I read just now, it sounds like Linux kernel and initrd are measured, and then initrd unlocks the disk encryption using your passphrase and a value only released if right PCR value in PCR register. And that nothing inside the disk encryption is verified.

If all you want to do is protecting against a physical attacker, you can assume they cannot access the encrypted data and thus not change it. But if we want to protect against malware persistence, eg if a driver or the hypervisor has been compromised by a remote attacker, we need to verify far further in than initrd, at least all of dom0 too.

My focus was orthogonal to what I believe Heads do. I tried protecting against malware persistence, but not a physical attacker. For a boot secure against both, we would likely need to combine the two approaches.

Yeah, I put it in General Discussion because I felt it was more a step towards protecting QubesOS in a similar way, than a guide actually useful to QubesOS setups today. So more discussion than guide. But I am fine either way.

Internet searches suggests that Xen does, and there is a ticket on the bug tracker about implementing a similar Secure Boot verification process in QubesOS that also suggests it should be possible.

I focused on a regular Linux distribution as a first step, since I anticipated it will be harder to implement this over Xen and in QubesOS, so that will be a next future step now when I know the basics of how to do things.

2 Likes

Thank you for your post. I would like to implement this because it’s part of threat model but I’m a non technical user. What happens if I follow your guide? Is this ready for implementation?

1 Like

I am trying to understand this statement better, are you saying that at a technical level, the process cannot use SHA384? Or are you saying you choose not to use SHA384 in favor of SHA256? They are different statements.

I think I understand your intent behind this statement, however the comes close to confusing cryptography’s perfect security (in bits) vs. actual algorithmic security (in bits). Those two are very different.

1 Like

The guide was written for someone with technical expertise, I left out everything that would be “obvious” to someone with deep experience about how Linux works at a technical level. I imagine the guide can be hard to follow for a regular user, especially to make sure and understand the end result is actually secure and done correctly.

But I have been thinking about maybe making a script that “distro morph” a clean Linux Mint installation into this kind of setup. I have some ideas there to make it easy to use and practical for a regular user. But I would not have anything ready for several months yet, even if I go ahead with the idea.

If you decide to go ahead and follow my instructions above now, just post here in this forum thread any issues you run into, and I can clarify. I am certain others that attempt to replicate what I did would appreciate that too.

SHA256 is used in two places as far as I know, for the signing certificates, and for the whitelist of OpROMs. Both are written to the BIOS settings (more specifically, to the EFI variables). Secure Boot will then use them to validate any EFI image loaded. Secure Boot only supports SHA256 hashes for the whitelist according to the UEFI standard, so this would be true for any actual BIOS implementation too. I guess this is also true for the certificates. I know only RSA keys are supported, for example. The UEFI standard is kept simple on purpose, to reduce risks of vulnerable implementations. It is basically Authenticode, but simplied to remove everything not strictly needed.

So, I am saying SHA256 is the only hash algorithm supported at a technical level, by the BIOS / Secure Boot.

To the best of my knowledge, there are no known attacks against the SHA-2 family of hash algorithms, such as SHA256, which means there is no known practical attack that breaks the hash algorithm faster than the theoretical security I mentioned. However, no lower bound of the security of SHA-2 is mathematically proven as far as I know, so future attacks might be found.

Edit: Wikipedia says there are no known attacks that break the full SHA-2 algorithm.

1 Like

Thanks for this explanation of it.

I agree, that would be a logical assumption, given the previous point.

Hmm… but if they don’t keep the standard up to date when more modern standards come about, simplicity becomes its weakness. Thanks, I’ll read more in to UEFI specifications when I have time.

That is interesting to me, thanks.

Got it now. Thanks for all of this.


My point here was that all algorithms have inefficiencies and/or non-fatal flaws, which means you cannot take algorithmic security (in bits) as a true measure of perfect security (in bits).

For instance rather than this:

It’s more accurate to say “SHA256 provides the equivalent security of SHA128 against a quantum computer”, not that it provides 128-bits of security (as 128-bits of security is perfect security).


This statement here:

Is much different from this statement here:

The key difference between those two statements is “known attacks” versus the latter statement of “break the full SHA-2 algorithm”.

Though the latter statement is true, the former statement is incorrect - as there is the category of attacks known as length extension attacks on MD5, and SHA-0 through to SHA-2.

Which why I suggested SHA384.

As to if these kinds of attacks are theoretically/practically relevant to just SHA-2, or to SHA-2 as well as the UEFI Secure Boot process, is probably an academic debate.

But as you’ve pointed out here:

Any academic debate is probably pointless, if this statement is true.

If the UEFI specification only supports signing using SHA256, then SHA256 is the hashing algorithm one should use if using this process.

Until at least the UEFI Secure Boot specification changes. And/or one might need to acknowledge that if the Secure Boot specification never changes, Secure Boot may not be considered a secure boot forever (if it is at all).


Thanks for your technical explanations on these points, the process was an interesting read.

1 Like

SHA384 is also vulnerable to length-extension attacks, but those attacks should not be relevant in this use-case for any hash algorithm, as we do not rely on the hashed and signed data being secret.

Both RSA-4096 and SHA-256 (for second pre-image resistance) are still considered secure for all user-cases, including into the near future. There are no recommendations to switch to anything newer at this point in time, even if newer and better constructed algorithms do exist. RSA is the weakest of the two, due to lacking resistance against quantum computers, and no good alternatives exist yet, as in, no quantum resistant signing algorithm is battle tested yet.

If RSA-4096 or SHA-256 starts showing its age, and there are worries they might not remain secure that much longer, I guess the Secure Boot specification will be updated to use new modern algorithms instead. But updating it is probably not easy to do, and roll out to everyone. So they will probably hold off with that, at least until we have a well-recognized and well-received quantum resistant signing algorithm.

1 Like

And this is where I’m trying to make sense of this, because whilst I know the broad concepts of what UEFI Secure Boot tries to achieve, but I’ve never gone deeper into technical implementation details.

Mostly because Secure Boot has never been useful for my purposes when it was pitched by industry as commercial OS vendor controlled & requires a TPM to function.

Pitched as, an open-source OS user controlled & not requiring TPMs (e.g. your above process) - that is much more useful.

This is unfortunately not true. Both RSA and SHA lack quantum-resistance.

If one is to fixate on quantum-resistance alone, then the only point of difference between them is that they are attacked by different quantum-computing algorithms.

Grovers algorithm could be improved upon tomorrow, or the next day, or the next day after that, and SHA2 still has no internal defense against large enough quantum computers. SHA2 still needs to be replaced, in the context of quantum-resistance.

The the same can be said of every cryptographic algorithm when it is newly released, regardless of if it has quantum-resistant properties or not, though.

“Battle-testing” any algorithm can take decades.

I assume here, you mean no recommendation from you personally, or from the UEFI specification team.

Because there is current advice on the timeline to moving towards quantum-resistant algorithms (from cryptographic academia, government agencies, and big tech). Arguably that advice has been in place since at least 2022.

The timeline is shorter than decades away from now. The most conservative estimates, are by the early-to-mid 2030s.

I see where you’re coming from here in defense of the RSA and SHA2 algorithms (which I agree with some of). But I’m not sure its not as relevant, as you seem to.

More relevant (from my perspective) is that government authorities, industry bodies, big tech companies, and the compliance frameworks for which corporations use for information security governance - are all now starting to move towards hard dates in requiring quantum resistance algorithms.

That in turn will become sales problem for computer manufacturers (and by extension BIOS manufacturers) trying to sell to these organisations, regardless of the perceived strength of RSA/SHA2.

That is more likely to have influence on a timeline to change the Secure Boot specification, rather than the strength of the existing algorithms.

All of this is hard - its why they should start now.

I suspect what will happen though (based on hardware manufacturer trends of the past), is they wont roll out to everyone.

They’ll roll out to new devices, and claim that old devices cannot support new algorithms (which is not always true, but it makes more sales).

This is why they should start now.

5 years years to get technical consensus on what the new specification will be. And a couple of extra years to swap out out their internal software toolsets to comply to the new specification.

By the time they achieve all that, it will be the early-to-mid 2030s, and the conservative deadline will be there.


I’ve taken on board your other points not addressed here.

1 Like

Oh really. I thought it was proven that more than halving of the number of bits in security compared to traditional computing isn’t possible on typical designs of symmetric encryption and hashing algorithms.

Is it possible to design hash algorithms in a way that is provably secure against further advances in quantum-computing algorithms? All research that I know of is only focusing on asymmetric algorithms, and at least early designs redesigned the asymmetric algorithms to be based on the symmetric counterparts, and all follow up research was merely to improve speed and storage requirements, as the early algorithms ended up being highly inefficient, especially with regard to storage requirements.

Yeah.

I meant in general from the security community. Do you mean there is recommendations to switch to a specific quantum-resistant algorithm, or you just mean recommendations to research and standardize quantum-resistant algorithms in general? Because if the former, I certainly have missed that communication.

It cannot become a problem until we actually have quantum-resistant algorithms, at which point I assume they will start considering an update to the UEFI specification.

1 Like

I’m going to have to correct my own self here (note to self, don’t be in a rush when writing about cryptography).

I’ve not communicated well here, regarding Grovers. It makes it seem like I’m putting more faith in Grovers than I meant to. That is my error.

The point I was trying to make here, is there is nothing specific within the SHA2 algorithm itself to counter Grovers (or any other quantum-computing algorithm).

And I should have been more specific when saying “SHA2 still needs to be replaced”.

Specifically, its SHA128 & SHA256 which needs to be replaced (with either SHA384 and/or SHA512, or in limited cases with SHA3).

Yes and no, depending on whose language you use when using the word “prove”.

If you’re a mathematician, you might say yes (as in a mathematical proof).

In the epistomological sense, no. There’s no way in hard science to prove you are secure. You can only prove you are reasonably secure, having migitated all the known flaws.

I assume this is why Qubes OS makes claims that it is a “reasonably secure OS” - not that it is a “secure OS”.

It is the unknown flaws that may one day still threaten you, and there is no way to prove there are zero flaws left.

There’s a lot of improvements relating to Shor’s algorithm right now because after 30 years people are finding ways to optimise on the original algorithm. But my wider point from above (which was communicated poorly), was that it is still plausible one day there will be improvements in the symmetric attacks too. Attacks only get better.

The former. It is a slow shift but it has started. Not everyone in the security community has fully embraced it yet, but enough big players have - so everyone else eventually have to follow.

NSA, NIST, Google/Chrome, Apple/Safari, Cloudflare and many others have also started on the path of moving towards quantum-resistant algorithms (Apple being the most recent).

Once Microsoft, Google and Apple embrace a change, you have three of the largest hardware/browser manufacturers on board at that point - and then you have a defacto standard regardless of if you wanted it or not.

And once NIST changes their recommendations for algorithms (which they are), every governance framework will also change. That forces governments and corporations to move towards NISTs recommendations.

Yes, but it’s also more than just a technical challenge. Its also a governance challenge too. A team of stakeholder representatives needs to be assembled to meet regularly, to discuss goals of any and all new UEFI specifications, including moving to quantum-resistant algorithms.

This doesn’t happen overnight, it takes time (people to bring in, meetings to be scheduled and funded etc.). Without changing the algorithms immediately, this process can be started this year (and it should be, because the changes are not trivial and will take time to fully implement).

1 Like

Ah, yes, that makes sense. Because of halving of bits of security when/if quantum computers become a reality.

Oh, but cryptographic algorithms can actually be analyzed and proven to provide at least a certain number of bits of security against all differential cryptographic attack in classic computing. If that is 128 bits of security or more proven, that means a lot. True, those proofs don’t mean anything against a quantum computer, and we would need new proofs, but similar proofs could likely be made.

But when QubesOS says it is a “reasonable secure OS”, that is for a totally different reason: There are no mathematical/formal/logical proofs of any part of QubesOS providing any kind of security against any kind of broad class of attacks. I think there exist hypervisors who provide some level of formal proof of their security, but Xen that QubesOS uses does not.

If you have a formal proof of some level of security, you can actually claim that level of security, and many cryptographic algorithms does that, without being called out as frauds. But if QubesOS would claim to actually be secure in any absolute sense, it would be without any formal proofs, and thus QubesOS would have (rightfully) been called out as fraud. Which is why they make no such claim.

I am actually uncertain of this. My understanding is that most symmetric algorithms are inherently secure against quantum computing. Just that number of bits of security is halved again compared to classical computing, (it is already halved once because of birthday paradox in classic computing), meaning we need SHA512 for 128-bits of security.

The asymmetric algorithms on the other hand are based on a class of mathematical problems that are believed to lose exponentially much security in face of quantum algorithms. Those algorithms may not yet have been invented, or may not yet have reached their full theoretical potential. But that is why the focus on developing quantum-resistant cryptographic algorithms are solely focusing on asymmetric algorithms.

Okay. Hopefully we will start seeing quantum-resistant algorithms soon, in TLS and Microsoft’s Authenticode (that Secure Boot uses) and everything.