-
Notifications
You must be signed in to change notification settings - Fork 792
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[aes, prim_lfsr, sca] Verification of the masked AES with PRNG #19091
Comments
As an additional issue, the state of the LFSRs is only 32-bits, therefore it can be brute-forced. |
CC'ing LowRISC people who might be interested: @vogelpi @moidx @johannheyszl |
Thanks @AeinRezaeiShahmirzadi for reaching out. For visibility, Aein and I have been communicating about this. I will prepare a testbench that will allow Aein to kick off the verification process. Edit by @vogelpi - Jan 26, 2024: Summary of what has been done as part of this issue:
|
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
@AeinRezaeiShahmirzadi , I've pushed the testbench to this PR here: #19216. |
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This is mainly useful to perform some basic verification of, e.g., a synthesized version of the AES cipher core and/or to get an understanding of how to interface the core, e.g., for verifying security properties. This is related to #19091. Signed-off-by: Pirmin Vogel <[email protected]>
Hi @AeinRezaeiShahmirzadi , Related to the original question about brute-forcing 32-bit LFSRs: I think we could switch to 64-bit LFSRs. If we do in a smart way we can avoid massively inflating area. Do you think this would be advisable? |
@vogelpi About brute-forcing the LFSRs: moving from 4x 32-bit to 2x 64-bit (or even 1x 128-bit) should avoid that attack, and should not lead to significantly increased costs (you may even want shift a bit faster the LFSR to get more fresh bits per clock cycle). This will however not solve the non-uniformity issues pointed out by @AeinRezaeiShahmirzadi. Your might be interested in our recent paper on the topic https://eprint.iacr.org/2023/1134, although our proposition is likely more expensive than your current solution. |
A good alternative might be to replace the PRNG with XoShiRo256++ PRNG. It has a 256 bit state and we already have the implementation. It passes NIST 800-22 statistical tests, so it is not likely to cause non-uniformity issues. |
Update: We did have a good and constructive discussion today and agreed on the following: @AeinRezaeiShahmirzadi will share the PROLEAD configuration file with us allowing us to reproduce the discussed experiments. Our plan is to do an investigation on whether we can work out some relatively minor changes to the current PRNG design to avoid potential non-uniformity issues or whether it would be better to redesign the PRNG using a different approach. Personally, I think it will be challenging to come up with an efficient reseeding mechanism, to do the DV integration and the actual SCA evaluation - independent on the approach we take. If we decide to go through that, I am more in favor of a doing a PRNG redesign. |
Update: we came together last TUE to discuss the results of the investigation I have been doing over the last couple of weeks. The main discussion points were:
On my end, I will now do more experiments with Bivium/Trivium and check if we can definitely integrate them into AES on the master branch. |
This commit adds a couple of support files and a how to for evaluating the masking employed inside AES together with the instantiated PRNG using the PROLEAD tool. The library file as well as the PROLEAD config file have been derived from files based on variants in the PROLEAD repository and kindly shared by @AeinRezaeiShahmirzadi. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This commit adds a couple of support files and a how to for evaluating the masking employed inside AES together with the instantiated PRNG using the PROLEAD tool. The library file as well as the PROLEAD config file have been derived from files based on variants in the PROLEAD repository and kindly shared by @AeinRezaeiShahmirzadi. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
Happy New Year! The PR adding the Trivium/Bivium primitives has been merged and I've now done a PR adding the support files for evaluating the AES cipher core using PROLEAD here #20765. This allows repeating the analysis and reproducing the results mentioned above. Thanks again @AeinRezaeiShahmirzadi for the collaboration on this. Next up is to kick off some more experiments (FPGA) and take a look at DV. |
This commit adds a couple of support files and a how to for evaluating the masking employed inside AES together with the instantiated PRNG using the PROLEAD tool. The library file as well as the PROLEAD config file have been derived from files based on variants in the PROLEAD repository and kindly shared by @AeinRezaeiShahmirzadi. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This commit adds a couple of support files and a how to for evaluating the masking employed inside AES together with the instantiated PRNG using the PROLEAD tool. The library file as well as the PROLEAD config file have been derived from files based on variants in the PROLEAD repository and kindly shared by @AeinRezaeiShahmirzadi. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
This commit adds a couple of support files and a how to for evaluating the masking employed inside AES together with the instantiated PRNG using the PROLEAD tool. The library file as well as the PROLEAD config file have been derived from files based on variants in the PROLEAD repository and kindly shared by @AeinRezaeiShahmirzadi. This is related to #19091. Signed-off-by: Pirmin Vogel <[email protected]>
This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC#19091. Signed-off-by: Pirmin Vogel <[email protected]>
FYI the PR changing the PRNG implementation in OpenTitan AES is finally here: #20852 In the meantime, we've done additional experiments (including FPGA evaluation) and everything looked good so far. :-) The PR is currently under review but I hope to merge this soon. |
While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to #19091. Signed-off-by: Pirmin Vogel <[email protected]>
Update: the PRNG implementation on master has now been switched to an unrolled Bivium implementation. I am now updating my first comment in this thread to summarize what has been done and what the findings were. Afterwards, I will close this issue, feel free to re-open in case further questions / inputs related to this come up. Thanks again @AeinRezaeiShahmirzadi and @cassiersg for all your input on this! |
And here is the summary: #19091 (comment) |
Upstream OpenTitan commit b9afd40c3e9d9a8a852c7b8372b1744645ffa15e While the LFSR-based masking PRNG seems to be able to produce randomness of sufficient quality for the masking implementation in the AES cipher core (as indicated both by our FPGA-based side-channel analysis and by the PROLEAD tool) it may be vulnerable to brute-forcing attacks on the LFSR states. Therefore, this commit replaces the LFSR-based masking PRNG implementation inside AES with an implementation based on an unrolled Bivium stream cipher primitive as suggested in the paper: Cassiers, "Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue" available at https://eprint.iacr.org/2023/1134 Thanks to bigger individual state chunks - the smallest non-linear feedback shift register (NFSR) has a width of 84 bits - brute-forcing attacks are rendered infeasible. The overall PRNG state width increases from 160 to 177 bits, meaning the randomness consumption for reseeding increases by one 32-bit word per reseed. Thanks to the strong diffusion properties of Bivium, fresh entropy received from EDN can still be injected directly into the PRNG without additional buffering. From an area perspective, the overall AES area increases slightly (+1.81 kGE or +1.1% based on Yosys + nangate45). Thanks again @cassiersg and @AeinRezaeiShahmirzadi for reporting the issue in the first place and for the constructive conversations. This is related to lowRISC/opentitan#19091. Signed-off-by: Pirmin Vogel <[email protected]> Co-authored-by: Gary Guo <[email protected]> Signed-off-by: Gary Guo <[email protected]>
Description
The high bandwidth random number generator for the masked AES core seems highly unconventional as it uses a single 32-bit LFSR (with nonlinear filter function) to re-mask four masked S-box which is calculated over five cycles. Moreover, the entire state of LFSRs is used as fresh randomness every cycle. This might result in non-uniform distributions of the masks in later cycles of the AES S-box operation and potentially cause side-channel leakage. It would be beneficial if the entire masked AES is verified by verification tools (such as PROLEAD which is able to verify the entire design) together with the PRNG to make sure that there is no vulnerability in the design.
The text was updated successfully, but these errors were encountered: