b524e55a011c969e5347bfb485311ba2 information_a2021v12n11p462.pdf f1db513337314f5b226569e6913fd9a2cc40186a information_a2021v12n11p462.pdf 374504967558571c4227877ff4e32716fd2a1aa38a74d76f5f1fdbe57df43fca information_a2021v12n11p462.pdf Title: Profiling Attack against RSA Key Generation Based on a Euclidean Algorithm Subject: A profiling attack is a powerful variant among the noninvasive side channel attacks. In this work, we target RSA key generation relying on the binary version of the extended Euclidean algorithm for modular inverse and GCD computations. To date, this algorithm has only been exploited by simple power analysis; therefore, the countermeasures described in the literature are focused on mitigating only this kind of attack. We demonstrate that one of those countermeasures is not effective in preventing profiling attacks. The feasibility of our approach relies on the extraction of several leakage vectors from a single power trace. Moreover, because there are known relationships between the secrets and the public modulo in RSA, the uncertainty in some of the guessed secrets can be reduced by simple tests. This increases the effectiveness of the proposed attack. Keywords: Euclidean algorithm; GCD; RSA key generation; side channel attack; profiling attack; machine learning-based attack Author: Sadiel de la Fe, Han-Byeol Park, Bo-Yeon Sim, Dong-Guk Han and Carles Ferrer Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Tue Nov 9 04:57:11 2021 CET ModDate: Tue Nov 9 05:01:13 2021 CET Tagged: no UserProperties: no Suspects: no Form: none JavaScript: no Pages: 12 Encrypted: no Page size: 595.276 x 841.89 pts (A4) Page rot: 0 File size: 541125 bytes Optimized: no PDF version: 1.7 name type encoding emb sub uni object ID ------------------------------------ ----------------- ---------------- --- --- --- --------- JNTBWN+URWPalladioL-Ital Type 1 Custom yes yes no 10 0 GOCCMP+URWPalladioL-Bold Type 1 Custom yes yes no 15 0 QTDFKP+URWPalladioL-Roma Type 1 Custom yes yes no 19 0 MOGGYH+CMSY10 Type 1 Builtin yes yes no 23 0 IREHDW+TimesNewRomanPSMT Type 1C WinAnsi yes yes no 31 0 TNTENQ+TimesNewRomanPS-BoldItalicMT Type 1C WinAnsi yes yes no 34 0 MCBCCI+SourceSansRoman-Regular Type 1C Custom yes yes no 51 0 MCBCCM+SourceSansRoman.613wght Type 1C Custom yes yes no 55 0 MCBCCO+SourceSansRoman-Bold Type 1C Custom yes yes no 59 0 GIGFZE+CMR10 Type 1 Builtin yes yes no 71 0 MFNKKH+PazoMath-Italic Type 1 Builtin yes yes no 78 0 Jhove (Rel. 1.22.1, 2019-04-17) Date: 2023-05-27 03:27:49 CEST RepresentationInformation: information_a2021v12n11p462.pdf ReportingModule: PDF-hul, Rel. 1.12.1 (2019-04-17) LastModified: 2023-03-31 11:58:32 CEST Size: 541125 Format: PDF Version: 1.7 Status: Well-Formed and valid SignatureMatches: PDF-hul MIMEtype: application/pdf PDFMetadata: Objects: 232 FreeObjects: 1 IncrementalUpdates: 0 DocumentCatalog: PageLayout: SinglePage PageMode: UseNone Outlines: Item: Title: Introduction Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@12f41634 Item: Title: RSA Key Generation Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@13c27452 Children: Item: Title: The Binary Extended Euclidean Algorithm Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@262b2c86 Item: Title: Countermeasures against SCA on BEEA Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@371a67ec Item: Title: Profiling Attacks Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@5ed828d Item: Title: Profiling Attack on the Euclidean Algorithm Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@50d0686 Children: Item: Title: Attack Points on Private Key Generation Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@7a3d45bd Item: Title: Attack Points on the Coprimality Tests Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@1e7c7811 Item: Title: Profiles and Guesses Verification Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@77ec78b9 Item: Title: Experimental Results Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@1a3869f4 Children: Item: Title: Experiment Environment Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@a38d7a3 Item: Title: Attack Model Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@77f99a05 Item: Title: Experiment Results Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@63440df3 Item: Title: Conclusions Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@3aeaafa6 Item: Title: References Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@76a3e297 Info: Title: Profiling Attack against RSA Key Generation Based on a Euclidean Algorithm Author: Sadiel de la Fe, Han-Byeol Park, Bo-Yeon Sim, Dong-Guk Han and Carles Ferrer Subject: A profiling attack is a powerful variant among the noninvasive side channel attacks. In this work, we target RSA key generation relying on the binary version of the extended Euclidean algorithm for modular inverse and GCD computations. To date, this algorithm has only been exploited by simple power analysis; therefore, the countermeasures described in the literature are focused on mitigating only this kind of attack. We demonstrate that one of those countermeasures is not effective in preventing profiling attacks. The feasibility of our approach relies on the extraction of several leakage vectors from a single power trace. Moreover, because there are known relationships between the secrets and the public modulo in RSA, the uncertainty in some of the guessed secrets can be reduced by simple tests. This increases the effectiveness of the proposed attack. Keywords: Euclidean algorithm; GCD; RSA key generation; side channel attack; profiling attack; machine learning-based attack Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Tue Nov 09 04:57:11 CET 2021 ModDate: Tue Nov 09 05:01:13 CET 2021 ID: 0x510c6dc6332dfa83d181fba7c19fa7d0, 0x510c6dc6332dfa83d181fba7c19fa7d0 Filters: FilterPipeline: FlateDecode Images: Image: NisoImageMetadata: FormatName: image/png ImageWidth: 1915 ImageHeight: 319 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Image: NisoImageMetadata: FormatName: image/png ImageWidth: 1364 ImageHeight: 959 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Fonts: Type1: Font: BaseFont: QTDFKP+URWPalladioL-Roma FontSubset: true FirstChar: 2 LastChar: 242 FontDescriptor: FontName: QTDFKP+URWPalladioL-Roma Flags: Symbolic FontBBox: -166, -283, 1021, 943 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: MOGGYH+CMSY10 FontSubset: true FirstChar: 0 LastChar: 54 FontDescriptor: FontName: MOGGYH+CMSY10 Flags: Symbolic FontBBox: -29, -960, 1116, 775 FontFile: true Font: BaseFont: GIGFZE+CMR10 FontSubset: true FirstChar: 40 LastChar: 61 FontDescriptor: FontName: GIGFZE+CMR10 Flags: Symbolic FontBBox: -40, -250, 1009, 750 FontFile: true Font: BaseFont: JNTBWN+URWPalladioL-Ital FontSubset: true FirstChar: 2 LastChar: 151 FontDescriptor: FontName: JNTBWN+URWPalladioL-Ital Flags: Symbolic FontBBox: -170, -305, 1010, 941 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: MFNKKH+PazoMath-Italic FontSubset: true FirstChar: 102 LastChar: 102 FontDescriptor: FontName: MFNKKH+PazoMath-Italic Flags: Symbolic FontBBox: -70, -277, 902, 733 FontFile: true Font: BaseFont: GOCCMP+URWPalladioL-Bold FontSubset: true FirstChar: 2 LastChar: 122 FontDescriptor: FontName: GOCCMP+URWPalladioL-Bold Flags: Symbolic FontBBox: -152, -301, 1000, 935 FontFile: true EncodingDictionary: Differences: true Pages: Page: Sequence: 1 Annotations: Annotation: Subtype: Link Rect: 35, 759, 169, 795 Annotation: Subtype: Link Rect: 515, 759, 560, 795 Annotation: Subtype: Link Rect: 150, 358, 154, 367 Annotation: Subtype: Link Rect: 35, 346, 156, 355 Annotation: Subtype: Link Rect: 35, 162, 97, 184 Annotation: Subtype: Link Rect: 153, 89, 154, 98 Annotation: Subtype: Link Rect: 35, 77, 147, 86 Annotation: Subtype: Link Rect: 467, 236, 474, 245 ActionDest: 108 Annotation: Subtype: Link Rect: 369, 211, 376, 220 ActionDest: 108 Annotation: Subtype: Link Rect: 539, 199, 546, 208 ActionDest: 108 Annotation: Subtype: Link Rect: 549, 199, 556, 208 ActionDest: 108 Annotation: Subtype: Link Rect: 449, 161, 456, 170 ActionDest: 108 Annotation: Subtype: Link Rect: 549, 136, 556, 145 ActionDest: 108 Annotation: Subtype: Link Rect: 123, 17, 262, 28 Annotation: Subtype: Link Rect: 392, 17, 558, 28 Annotation: Subtype: Link Rect: 35, 423, 87, 442 Page: Sequence: 2 Annotations: Annotation: Subtype: Link Rect: 283, 686, 290, 695 ActionDest: 112 Annotation: Subtype: Link Rect: 369, 674, 381, 683 ActionDest: 112 Annotation: Subtype: Link Rect: 380, 661, 392, 670 ActionDest: 112 Annotation: Subtype: Link Rect: 442, 624, 454, 633 ActionDest: 112 Annotation: Subtype: Link Rect: 447, 611, 459, 620 ActionDest: 112 Annotation: Subtype: Link Rect: 259, 573, 271, 582 ActionDest: 112 Annotation: Subtype: Link Rect: 449, 523, 461, 532 ActionDest: 112 Annotation: Subtype: Link Rect: 342, 448, 354, 457 ActionDest: 112 Annotation: Subtype: Link Rect: 383, 194, 390, 206 ActionDest: 68 Annotation: Subtype: Link Rect: 466, 182, 474, 194 ActionDest: 85 Annotation: Subtype: Link Rect: 199, 156, 206, 168 ActionDest: 88 Annotation: Subtype: Link Rect: 410, 156, 417, 168 ActionDest: 97 Annotation: Subtype: Link Rect: 200, 147, 207, 156 ActionDest: 108 Annotation: Subtype: Link Rect: 518, 96, 530, 105 ActionDest: 112 Page: Sequence: 3 Annotations: Annotation: Subtype: Link Rect: 522, 260, 534, 269 ActionDest: 112 Annotation: Subtype: Link Rect: 323, 160, 335, 169 ActionDest: 112 Annotation: Subtype: Link Rect: 336, 160, 348, 169 ActionDest: 112 Annotation: Subtype: Link Rect: 552, 132, 559, 144 ActionDest: 82 Annotation: Subtype: Link Rect: 301, 122, 308, 131 ActionDest: 108 Annotation: Subtype: Link Rect: 421, 57, 428, 69 ActionDest: 85 Page: Sequence: 4 Annotations: Annotation: Subtype: Link Rect: 320, 707, 327, 719 ActionDest: 82 Annotation: Subtype: Link Rect: 202, 137, 214, 146 ActionDest: 112 Page: Sequence: 5 Annotations: Annotation: Subtype: Link Rect: 394, 634, 406, 643 ActionDest: 112 Annotation: Subtype: Link Rect: 202, 588, 214, 597 ActionDest: 112 Annotation: Subtype: Link Rect: 215, 588, 227, 597 ActionDest: 112 Annotation: Subtype: Link Rect: 213, 574, 220, 585 ActionDest: 85 Annotation: Subtype: Link Rect: 364, 563, 376, 572 ActionDest: 112 Annotation: Subtype: Link Rect: 340, 513, 352, 522 ActionDest: 112 Annotation: Subtype: Link Rect: 246, 386, 253, 397 ActionDest: 82 Annotation: Subtype: Link Rect: 461, 373, 468, 385 ActionDest: 85 Annotation: Subtype: Link Rect: 463, 250, 475, 259 ActionDest: 112 Page: Sequence: 6 Annotations: Annotation: Subtype: Link Rect: 444, 722, 456, 731 ActionDest: 112 Annotation: Subtype: Link Rect: 459, 722, 471, 731 ActionDest: 112 Annotation: Subtype: Link Rect: 393, 685, 405, 694 ActionDest: 112 Annotation: Subtype: Link Rect: 457, 374, 469, 383 ActionDest: 112 Annotation: Subtype: Link Rect: 469, 374, 481, 383 ActionDest: 112 Annotation: Subtype: Link Rect: 516, 231, 523, 242 ActionDest: 85 Annotation: Subtype: Link Rect: 392, 129, 404, 138 ActionDest: 112 Page: Sequence: 7 Annotations: Annotation: Subtype: Link Rect: 382, 707, 397, 719 ActionDest: 91 Annotation: Subtype: Link Rect: 395, 466, 402, 478 ActionDest: 91 Annotation: Subtype: Link Rect: 382, 275, 389, 287 ActionDest: 91 Annotation: Subtype: Link Rect: 550, 174, 557, 186 ActionDest: 91 Annotation: Subtype: Link Rect: 180, 89, 192, 98 ActionDest: 112 Page: Sequence: 8 Annotations: Annotation: Subtype: Link Rect: 339, 732, 346, 744 ActionDest: 94 Annotation: Subtype: Link Rect: 539, 529, 546, 540 ActionDest: 85 Annotation: Subtype: Link Rect: 348, 491, 355, 503 ActionDest: 94 Annotation: Subtype: Link Rect: 191, 378, 198, 390 ActionDest: 91 Annotation: Subtype: Link Rect: 406, 340, 420, 352 ActionDest: 91 Page: Sequence: 9 Annotations: Annotation: Subtype: Link Rect: 212, 733, 219, 744 ActionDest: 94 Annotation: Subtype: Link Rect: 458, 557, 465, 568 ActionDest: 85 Annotation: Subtype: Link Rect: 214, 518, 221, 530 ActionDest: 82 Annotation: Subtype: Link Rect: 358, 521, 365, 530 ActionDest: 108 Annotation: Subtype: Link Rect: 528, 506, 535, 518 ActionDest: 91 Annotation: Subtype: Link Rect: 440, 443, 447, 455 ActionDest: 97 Annotation: Subtype: Link Rect: 342, 256, 349, 268 ActionDest: 97 Annotation: Subtype: Link Rect: 203, 193, 210, 206 ActionDest: 103 Page: Sequence: 10 Annotations: Annotation: Subtype: Link Rect: 254, 720, 261, 732 ActionDest: 97 Annotation: Subtype: Link Rect: 200, 710, 215, 719 ActionDest: 91 Annotation: Subtype: Link Rect: 329, 694, 336, 706 ActionDest: 97 Annotation: Subtype: Link Rect: 430, 682, 437, 694 ActionDest: 103 Annotation: Subtype: Link Rect: 240, 370, 247, 382 ActionDest: 103 Annotation: Subtype: Link Rect: 376, 372, 388, 382 ActionDest: 112 Annotation: Subtype: Link Rect: 452, 320, 459, 332 ActionDest: 108 Annotation: Subtype: Link Rect: 376, 307, 383, 319 ActionDest: 108 Page: Sequence: 11 Annotations: Annotation: Subtype: Link Rect: 275, 456, 282, 467 ActionDest: 85 Annotation: Subtype: Link Rect: 488, 443, 495, 454 ActionDest: 82 Annotation: Subtype: Link Rect: 267, 418, 274, 429 ActionDest: 82 Annotation: Subtype: Link Rect: 490, 420, 502, 429 ActionDest: 112 Annotation: Subtype: Link Rect: 456, 169, 493, 180 Annotation: Subtype: Link Rect: 490, 134, 527, 145 Annotation: Subtype: Link Rect: 424, 111, 462, 124 Annotation: Subtype: Link Rect: 449, 100, 487, 111 Page: Sequence: 12 Annotations: Annotation: Subtype: Link Rect: 192, 686, 229, 697 Annotation: Subtype: Link Rect: 442, 629, 479, 640 Annotation: Subtype: Link Rect: 380, 594, 417, 605 Annotation: Subtype: Link Rect: 131, 572, 168, 582 Annotation: Subtype: Link Rect: 505, 537, 543, 548 Annotation: Subtype: Link Rect: 242, 491, 280, 502 Annotation: Subtype: Link Rect: 412, 479, 504, 490 Annotation: Subtype: Link Rect: 236, 341, 274, 352 Annotation: Subtype: Link Rect: 56, 318, 205, 329 Checksum: 6c329134 Type: CRC32 Checksum: b524e55a011c969e5347bfb485311ba2 Type: MD5 Checksum: f1db513337314f5b226569e6913fd9a2cc40186a Type: SHA-1