Garbled Circuits from an SCA Perspective
Garbling schemes, invented in the 80’s by Yao (FOCS’86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, which led to a long line of study of this object, where one of the most influential...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/10277 |
| _version_ | 1811158051290349568 |
|---|---|
| author | Itamar Levi Carmit Hazay |
| author_facet | Itamar Levi Carmit Hazay |
| author_sort | Itamar Levi |
| collection | DOAJ |
| description |
Garbling schemes, invented in the 80’s by Yao (FOCS’86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, which led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP’08), introducing a global offset Δ for all garbled wire values where XOR gates are computed locally without garbling them. To date, garbling schemes were not studied per their side-channel attacks (SCA) security characteristics, even though SCA pose a significant security threat to cryptographic devices. In this research we, demonstrate that adversaries utilizing advanced SCA tools such as horizontal attacks, mixed with advanced hypothesis building and standard (vertical) SCA tools, can jeopardize garbling implementations.
Our main observation is that garbling schemes utilizing a global secret Δ open a door to quite trivial side-channel attacks. We model our side-channel attacks on the garbler’s device and discuss the asymmetric setting where various computations are not performed on the evaluator side. This enables dangerous leakage extraction on the garbler and renders our attack impossible on the evaluator’s side.
Theoretically, we first demonstrate on a simulated environment, that such attacks are quite devastating. Concretely, our attack is capable of extracting Δ when the circuit embeds only 8 input non-linear gates with fifth/first-order attack Success-Rates of 0.65/0.7. With as little as 3 such gates, our attack reduces the first-order Guessing Entropy of Δ from 128 to ∼ 48-bits. We further demonstrate our attack via an implementation and power measurements data over an STM 32-bit processor software implementing circuit garbling, and discuss their limitations and mitigation tactics on logical, protocol and implementation layers.
|
| first_indexed | 2024-04-10T05:16:40Z |
| format | Article |
| id | doaj.art-120b79a971804b3a9dd32cb4515f7ea6 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-10T05:16:40Z |
| publishDate | 2023-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-120b79a971804b3a9dd32cb4515f7ea62023-03-08T15:37:34ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-03-012023210.46586/tches.v2023.i2.54-79Garbled Circuits from an SCA PerspectiveItamar Levi0Carmit Hazay1Bar-Ilan University, Ramat-Gan, IsraelBar-Ilan University, Ramat-Gan, Israel Garbling schemes, invented in the 80’s by Yao (FOCS’86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, which led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP’08), introducing a global offset Δ for all garbled wire values where XOR gates are computed locally without garbling them. To date, garbling schemes were not studied per their side-channel attacks (SCA) security characteristics, even though SCA pose a significant security threat to cryptographic devices. In this research we, demonstrate that adversaries utilizing advanced SCA tools such as horizontal attacks, mixed with advanced hypothesis building and standard (vertical) SCA tools, can jeopardize garbling implementations. Our main observation is that garbling schemes utilizing a global secret Δ open a door to quite trivial side-channel attacks. We model our side-channel attacks on the garbler’s device and discuss the asymmetric setting where various computations are not performed on the evaluator side. This enables dangerous leakage extraction on the garbler and renders our attack impossible on the evaluator’s side. Theoretically, we first demonstrate on a simulated environment, that such attacks are quite devastating. Concretely, our attack is capable of extracting Δ when the circuit embeds only 8 input non-linear gates with fifth/first-order attack Success-Rates of 0.65/0.7. With as little as 3 such gates, our attack reduces the first-order Guessing Entropy of Δ from 128 to ∼ 48-bits. We further demonstrate our attack via an implementation and power measurements data over an STM 32-bit processor software implementing circuit garbling, and discuss their limitations and mitigation tactics on logical, protocol and implementation layers. https://tches.iacr.org/index.php/TCHES/article/view/10277Secure ComputationGarbled CircuitsFree-XORSide-channel analysisHorizontal AttacksSingle Trace |
| spellingShingle | Itamar Levi Carmit Hazay Garbled Circuits from an SCA Perspective Transactions on Cryptographic Hardware and Embedded Systems Secure Computation Garbled Circuits Free-XOR Side-channel analysis Horizontal Attacks Single Trace |
| title | Garbled Circuits from an SCA Perspective |
| title_full | Garbled Circuits from an SCA Perspective |
| title_fullStr | Garbled Circuits from an SCA Perspective |
| title_full_unstemmed | Garbled Circuits from an SCA Perspective |
| title_short | Garbled Circuits from an SCA Perspective |
| title_sort | garbled circuits from an sca perspective |
| topic | Secure Computation Garbled Circuits Free-XOR Side-channel analysis Horizontal Attacks Single Trace |
| url | https://tches.iacr.org/index.php/TCHES/article/view/10277 |
| work_keys_str_mv | AT itamarlevi garbledcircuitsfromanscaperspective AT carmithazay garbledcircuitsfromanscaperspective |