Menu

DM Verity Algorithm Change

October 16th, 2019

One of the foundational security features of Chromebooks is Verified Boot, which protects our users from potentially malicious software being run on their devices. The last chain of verification in this process is to validate the integrity of the root file system (rootfs). This blog post describes a recent enhancement to this rootfs validation to increase the cryptographic strength against attackers. This enhancement was carefully implemented to ensure that it didn’t negatively impact the startup time of Chromebooks.

Chrome OS uses DM Verity [1] to verify the rootfs authenticity. This is to protect against malicious software such as rootkits [2], as well as accidental corruptions. The underlying structure leverages a cryptographic hash tree approach along with a kernel crypto API. With the hash tree approach, individual hashes of small blocks constituting the rootfs are computed first. Then the hash tree is built up to compute and verify a final hash value [3]. This incremental approach makes the verification process less resource-intensive, and consequently faster.

Until recently, the underlying hash algorithm used by DM Verity in Chrome OS has been SHA1. However, SHA1 has been found to be vulnerable to attacks a few years ago [4] and more recently research by Google and the larger security community has demonstrated that SHA1 collisions are not just theory anymore but can happen in practice [5, 6, 7]. This necessitates the replacement of SHA1 with SHA2 or SHA3 when the use scenarios make the attacks defined in the research studies feasible.

On the other hand, the risks to DM Verity due to collision attacks are arguably low. This is because DM Verity uses a hash tree structure with disk data blocks as leaves to obtain the final hash. And to turn the collision attack into an exploit for DM Verity, the attacker would need to develop malware that would fit into a single and specific block and produce the same hash value as the original block using a chosen prefix attack. This would be computationally expensive.
We decided to proactively upgrade DM Verity in Chrome OS to use SHA256 instead. Moving to SHA256 was difficult because it is computationally more expensive than SHA1 and potentially would have increased Chromebook boot time. This is why we spent significant time tuning our implementation and measuring its performance impact on a wide range of Chromebooks to ensure that you will get very similar performance with SHA256 that you had with SHA1 when you boot your Chromebook as shown here:

DM Verity Algorithm Change
Kernel boot time comparison in ms for (1)Veyron-minnie, (2)Cyan, (3)Octopus, (4)Sarien, (5)Samus, (6)Clapper, (7)Eve, (8)Bob

With this change in place, your Chromebook will be safer and remain blazing fast. This migration from SHA1 to SHA256 in DM Verity is ready to go and will be on Chromebooks starting with M77.

Posted by Betul Soysal, Chrome OS security software engineer

References:

  1. https://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot
  2. https://en.wikipedia.org/wiki/Rootkit
  3. https://source.android.com/security/verifiedboot/dm-verity
  4. https://en.wikipedia.org/wiki/SHA-1
  5. Stevens, Marc, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. “The first collision for full SHA-1.(2017).” URL http://shattered. it/static/shattered. pdf 167 (2017): 169-177.
  6. Mezher, Monique, and Ahmed Ibrahim. “Introducing Practical SHA-1 Collisions to the Classroom.” Proceedings of the 50th ACM Technical Symposium on Computer Science Education. ACM, 2019.
  7. Leurent, Gaëtan, and Thomas Peyrin. “From Collisions to Chosen-Prefix Collisions Application to Full SHA-1.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 527-555. Springer, Cham, 2019.