Partial Key Exposure Attacks on BIKE, Rainbow, and NTRU

Explore the vulnerability of PQC candidates to partial key exposure attacks in schemes like BIKE, Rainbow, and NTRU. Learn about leakage resistance, modeling leakage, practical bounds, and secret key decoding methods. Dive into the erasure and error models, analyzing the security of secret keys in varying scenarios.

• Key Exposure
• BIKE
• Rainbow
• NTRU
• Security

kuchar_d Follow

Uploaded on Nov 20, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Partial Key Exposure Attacks on BIKE, Rainbow and NTRU Andre Esser Alexander May Javier Verbel Weiqiang Wen @ CRYPTO 2022, Santa Barbara

2. Motivation Are PQC candidates leakage resistant? ?-bit key, -bit leaked security of (? ) -bit key? Best known: Enumeration attacks No use of key-redundancy / structure New attacks and bounds on required leakage 2

3. Methodology How to model leakage? Errors / Erasures Asymptotic leakage bounds (poly-time) Practical leakage bounds 3

4. Rainbow, BIKE and NTRU 4

5. Secret Keys Rainbow BIKE NTRU ? ?/2 Vector ? ?3 Vector ?,? ?2 ?2 with few 1 s Matrices over ??: ?/2 ? 0 0 ?1 ? 0 ?2 ?3 ? ? 1=? ? ? , ? 1= 0 Satisfies: ?? = ? Satisfies: ?? = ? ? or ? suffice no intrinsic shortcut Row of ? and constant columns of ?1 suffice for full recovery but stores some extra information for efficiency 5

6. Information Set Decoding [Prange 62] BIKE Secret key ?,? ?2 Satisfies: ?? = ? and has ? entries equal to 1 (??/2 ?) (?,?) = 0?/2 ?/2 ?2 ?/2 ??/2 ? 0 = e s 6

7. Information Set Decoding [Prange 62] BIKE Secret key ?,? ?2 Satisfies: ?? = ? and has ? entries equal to 1 ?/2 ?2 ?/2 ??/2 ? 0 = 0 0 0 0 0 0 0 0 0 0 0 0 ? 2 6

8. Information Set Decoding [Prange 62] BIKE Secret key ?,? ?2 Satisfies: ?? = ? and has ? entries equal to 1 ?/2 ?2 ?/2 0 = ? 0 0 0 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 0 0 0 0 s ? 2 weight ? 6

9. The Erasure Model 7

10. The Error Model Secret key (?-bits) 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0 Erased key 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Erasure-probability: Pr[ ] = Pr[ ] = p 0 ? 1 ? 8

11. Asymptotic Bounds Number of Erasures Setting first layer ? ?(?) ? 0 0 ?1 ? 0 ?2 ?3 ? ? 1=? ? ? , ? 1= linear / quadratic Rainbow 0 full key ? ? 2 ? 11 standard 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 systems due to key relations BIKE compact 0, 11, 14 NTRU (un) packed unpacked: 0 1 -1 -1 0 0 1 0 0 1 0 0 3? packed: 9

12. Asymptotic - BIKE BIKE secret key satisfies n/2 known linear equations: As = e standard ? ? ? ? 1 0 ? 0 0 0 ? 0 0 0 0 ? 1 0 0 0 0 ? 0 0 0 ? 0 1 ? ? 0 0 0 0 ? ? ? ? 2 Less than n/2 : solve linear system ? ? 11 compact 1 0 1 ? 1 0 0 ? 0 ? 1 0 ? 0 ? 1 1 0 1 ? 0 1 0 1 ? 1 ? ? ? ? log ? ? 42, 46, 2, 6, 18, 22 1. Enumerate all ? 2. If less than ?/2 candidates ?/2 zeros known : solve linear system 10

13. Practical Bounds Category I Parameters Setting 60-bit complexity linear / quadratic system Rainbow full key 0.81 standard 0.65 ISD (accelerated) BIKE compact 0.43 unpacked 0.30 lattice reduction NTRU packed 0.09 11

14. The Error Model 12

15. Leakage models Secret key 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0 Erroneous Key 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 01 1 1 1 1 0 0 Error-probability: Pr[ ] = Pr[ ] = p 0 1 (symmetric) (asymmetric) 1 0 Pr[ ] =0.001, Pr[ ] = p 0 1 1 0 13

16. Asymptotic Bounds Number of Errors Setting first layer log2? Rainbow full key log ? Information Set Decoding standard ? log ? ? log2? BIKE compact NTRU (un) packed log ? 14

17. Asymptotic - BIKE standard 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 solve via ISD but sample zeros only from (and ) 0 0 compact 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1 1 log ? ? 1. Enumerate small-weight errors list of candidates 2. but sample zeros only from non-candidates solve via ISD 15

18. Practical Bounds 60-bit complexity sym Category I Parameters Setting asym ISD + quadratic system Rainbow full key 0.19 0.38 standard 0.12 0.15 ISD (accelerated) BIKE compact 0.06 0.24 unpacked lattice reduction / meet-in-the-middle 0.01 0.10 NTRU packed 0.01 0.02 16

19. Conclusion Non-trivial polynomial time recovery Even higher practical bounds Comparable to non-post-quantum systems PQC does not per se enjoy leakage resistance 17