Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Time Is Money, Friend! Timing Side-Channel Attack Against Garbled Circuit Constructions

  • Conference paper
  • First Online:
Applied Cryptography and Network Security (ACNS 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14585))

Included in the following conference series:

  • 360 Accesses

Abstract

With the advent of secure function evaluation (SFE), distrustful parties can jointly compute on their private inputs without disclosing anything besides the results. Yao’s garbled circuit protocol has become an integral part of secure computation thanks to considerable efforts made to make it feasible, practical, and more efficient. For decades, the security of protocols offered in general-purpose compilers has been assured with regard to sound proofs and the promise that during the computation, no information on parties’ input would be leaking. In a parallel effort, timing side-channel attacks have proven themselves effective in retrieving secrets from implementations, even through remote access to them. Nevertheless, the vulnerability of garbled circuit frameworks to timing attacks has, surprisingly, never been discussed in the literature. This paper introduces Goblin, the first timing attack against commonly employed garbled circuit frameworks. Goblin is a machine learning-assisted, non-profiling, single-trace timing side-channel attack (SCA), which successfully recovers the garbler’s input during the computation under different scenarios, including various garbling frameworks, benchmark functions, and the number of garbler’s input bits. In doing so, Goblin hopefully paves the way for further research in this matter.

Code is available at  https://github.com/vernamlab/Goblin.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 99.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 129.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    For specifics of the encryption function in the free-XOR protocol, see [13, 34].

References

  1. Acıiçmez, O., Koç, Ç.K.: Trace-driven cache attacks on AES (Short Paper). In: Ning, P., Qing, S., Li, N. (eds.) ICICS 2006. LNCS, vol. 4307, pp. 112–121. Springer, Heidelberg (2006). https://doi.org/10.1007/11935308_9

    Chapter  Google Scholar 

  2. Applebaum, B.: Key-dependent message security: generic amplification and completeness. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 527–546. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_29

    Chapter  Google Scholar 

  3. Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded key-dependent message security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 423–444. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_22

    Chapter  Google Scholar 

  4. Bellare, M., Hoang, V.T., Keelveedhi, S., Rogaway, P.: Efficient garbling from a fixed-key blockcipher. In: 2013 IEEE Symposium on Security and Privacy, pp. 478–492. IEEE (2013)

    Google Scholar 

  5. Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Proceedings of the 2012 ACM Conference on Computer and Communication Security, pp. 784–796 (2012)

    Google Scholar 

  6. Benhamouda, F., Lin, H.: k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 500–532. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_17

    Chapter  Google Scholar 

  7. Bernstein, D.J.: Cache-timing attacks on AES (2005)

    Google Scholar 

  8. Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03549-4_20

    Chapter  Google Scholar 

  9. Brakerski, Z., Yuen, H.: Quantum garbled circuits. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 804–817 (2022)

    Google Scholar 

  10. Carter, H., Lever, C., Traynor, P.: Whitewash: outsourcing garbled circuit generation for mobile devices. In: Proceedings of the 30th Annual Computer Security Applications Conference, pp. 266–275 (2014)

    Google Scholar 

  11. Carter, H., Mood, B., Traynor, P., Butler, K.: Outsourcing secure two-party computation as a black box. Secur. Commun. Netw. 9(14), 2261–2275 (2016)

    Article  Google Scholar 

  12. Chen, D., Chen, W., Chen, J., Zheng, P., Huang, J.: Edge detection and image segmentation on encrypted image with homomorphic encryption and garbled circuit. In: 2018 IEEE International Conference on Multimedia and Expo (ICME), pp. 1–6. IEEE (2018)

    Google Scholar 

  13. Choi, S.G., Katz, J., Kumaresan, R., Zhou, H.-S.: On the security of the free-XOR technique. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 39–53. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_3

    Chapter  Google Scholar 

  14. Cock, M.d., Dowsley, R., Nascimento, A.C., Newman, S.C.: Fast, privacy preserving linear regression over distributed datasets based on pre-distributed data. In: Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security, pp. 3–14 (2015)

    Google Scholar 

  15. Conti, M., et al.: Losing Control: on the effectiveness of control-flow integrity under stack attacks. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 952–963 (2015)

    Google Scholar 

  16. Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_23

    Chapter  Google Scholar 

  17. Damgård, I., Ishai, Y., Krøigaard, M., Nielsen, J.B., Smith, A.: Scalable multiparty computation with nearly optimal work and resilience. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 241–261. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_14

    Chapter  Google Scholar 

  18. Demmler, D., Schneider, T., Zohner, M.: Aby-a framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015)

    Google Scholar 

  19. Doerner, J., Evans, D., Shelat, A.: Secure stable matching at scale. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1602–1613 (2016)

    Google Scholar 

  20. Easdon, C., Schwarz, M., Schwarzl, M., Gruss, D.: Rapid prototyping for microarchitectural attacks. In: USENIX Security Symposium (2022)

    Google Scholar 

  21. Feige, U., Killian, J., Naor, M.: A minimal model for secure computation. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 554–563 (1994)

    Google Scholar 

  22. Garg, S., Srinivasan, A.: Garbled protocols and two-round MPC from bilinear maps. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 588–599. IEEE (2017)

    Google Scholar 

  23. Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_16

    Chapter  Google Scholar 

  24. Gascón, A., et al.: Privacy-preserving distributed linear regression on high-dimensional data. Proc. Priv. Enhancing Technol. 2017(4), 345–364 (2017)

    Article  Google Scholar 

  25. Ge, Q., Yarom, Y., Cock, D., Heiser, G.: A survey of microarchitectural timing attacks and countermeasures on contemporary hardware. J. Cryptogr. Eng. 8, 1–27 (2018)

    Article  Google Scholar 

  26. Gentry, C., Halevi, S., Vaikuntanathan, V.: i-hop homomorphic encryption and rerandomizable Yao circuits. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 155–172. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_9

    Chapter  Google Scholar 

  27. Goldwasser, S., Kalai, Y., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 555–564 (2013)

    Google Scholar 

  28. Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 162–179. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_11

    Chapter  Google Scholar 

  29. Gras, B., Razavi, K., Bos, H., Giuffrida, C.: Translation leak-aside buffer: defeating cache side-channel protections with \(\{\)TLB\(\}\) attacks. In: 27th USENIX Security Symposium (USENIX Security 18), pp. 955–972 (2018)

    Google Scholar 

  30. Groce, A., Ledger, A., Malozemoff, A.J., Yerukhimovich, A.: CompGC: efficient offline/online semi-honest two-party computation. Cryptology ePrint Archive (2016)

    Google Scholar 

  31. Gruss, D., Maurice, C., Mangard, S.: Rowhammer.js: a remote software-induced fault attack in JavaScript. In: Caballero, J., Zurutuza, U., Rodríguez, R.J. (eds.) DIMVA 2016. LNCS, vol. 9721, pp. 300–321. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40667-1_15

    Chapter  Google Scholar 

  32. Gruss, D., Maurice, C., Wagner, K., Mangard, S.: Flush+Flush: a fast and stealthy cache attack. In: Caballero, J., Zurutuza, U., Rodríguez, R.J. (eds.) DIMVA 2016. LNCS, vol. 9721, pp. 279–299. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40667-1_14

    Chapter  Google Scholar 

  33. Gueron, S., Lindell, Y., Nof, A., Pinkas, B.: Fast garbling of circuits under standard assumptions. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 567–578 (2015)

    Google Scholar 

  34. Guo, C., Katz, J., Wang, X., Weng, C., Yu, Yu.: Better concrete security for half-gates garbling (in the multi-instance setting). In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 793–822. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_28

    Chapter  Google Scholar 

  35. Guo, C., Katz, J., Wang, X., Yu, Y.: Efficient and secure multiparty computation from fixed-key block ciphers. In: 2020 IEEE Symposium on Security and Privacy (SP), pp. 825–841. IEEE (2020)

    Google Scholar 

  36. Gupta, T., Fingler, H., Alvisi, L., Walfish, M.: Pretzel: email encryption and provider-supplied functions are compatible. In: Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pp. 169–182 (2017)

    Google Scholar 

  37. Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. SSS, Springer, New York (2009). https://doi.org/10.1007/978-0-387-84858-7

    Book  Google Scholar 

  38. Hastings, M., Hemenway, B., Noble, D., Zdancewic, S.: SoK: General purpose compilers for secure multi-party computation. In: 2019 IEEE Symposium on Security and Privacy (SP), pp. 1220–1237. IEEE (2019)

    Google Scholar 

  39. Hettwer, B., Gehrer, S., Güneysu, T.: Applications of machine learning techniques in side-channel attacks: a survey. J. Cryptogr. Eng. 10(2), 135–162 (2020)

    Article  Google Scholar 

  40. Intel Corporation: Intel Core i7 Processors. https://www.intel.com/content/www/us/en/products/details/processors/core/i7.html. Accessed 30 Jan 2023 (2017)

  41. Irazoqui, G., Inci, M.S., Eisenbarth, T., Sunar, B.: Wait a minute! a fast, cross-VM attack on AES. In: Stavrou, A., Bos, H., Portokalidis, G. (eds.) RAID 2014. LNCS, vol. 8688, pp. 299–319. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11379-1_15

    Chapter  Google Scholar 

  42. irdan: JustGarble framework. https://github.com/irdan/justGarble. Accessed 30 Jan 2023 (2014)

  43. Jagadeesh, K.A., Wu, D.J., Birgmeier, J.A., Boneh, D., Bejerano, G.: Deriving genomic diagnoses without revealing patient genomes. Science 357(6352), 692–695 (2017)

    Article  Google Scholar 

  44. Jancar, J.: The state of tooling for verifying constant-timeness of cryptographic implementations. https://neuromancer.sk/article/26. Accessed 7 Feb 2023 (2021)

  45. Jancar, J., et al.: They’re not that hard to mitigate: what cryptographic library developers think about timing attacks. In: 2022 IEEE Symposium on Security and Privacy (SP), pp. 632–649. IEEE (2022)

    Google Scholar 

  46. Jayaraman, B., Li, H., Evans, D.: Decentralized certificate authorities. arXiv preprint arXiv:1706.03370 (2017)

  47. Juvekar, C., Vaikuntanathan, V., Chandrakasan, A.: \(\{\)GAZELLE\(\}\): a low latency framework for secure neural network inference. In: 27th USENIX Security Symposium (USENIX Security 18), pp. 1651–1669 (2018)

    Google Scholar 

  48. Kamara, S., Mohassel, P., Raykova, M.: Outsourcing multi-party computation. Cryptology ePrint Archive (2011)

    Google Scholar 

  49. Kamara, S., Mohassel, P., Raykova, M., Sadeghian, S.: Scaling private set intersection to billion-element sets. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 195–215. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_13

    Chapter  Google Scholar 

  50. Kamara, S., Mohassel, P., Riva, B.: Salus: a system for server-aided secure function evaluation. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 797–808 (2012)

    Google Scholar 

  51. Kamara, S., Mohassel, P., Riva, B.: Salus: a system for server-aided secure function evaluation. Cryptology ePrint Archive (2012)

    Google Scholar 

  52. Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9

    Chapter  Google Scholar 

  53. Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_40

    Chapter  Google Scholar 

  54. Lai, C.H., Zhao, J., Yang, C.L.: Leave the cache hierarchy operation as it is: a new persistent memory accelerating approach. In: Proceedings of the 54th Annual Design Automation Conference 2017, pp. 1–6 (2017)

    Google Scholar 

  55. Levi, I., Hazay, C.: Garbled-circuits from an SCA perspective: free XOR can be quite expensive... Cryptology ePrint Archive (2022)

    Google Scholar 

  56. Lindell, Y., Pinkas, B.: A proof of Yao’s protocol for secure two-party computation. ECCC report TR04-063. In: Electronic Colloquium on Computational Complexity (ECCC) (2004)

    Google Scholar 

  57. Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72540-4_4

    Chapter  Google Scholar 

  58. Lindell, Y., Pinkas, B.: A proof of security of Yao’s protocol for two-party computation. J. Cryptol. 22(2), 161–188 (2009)

    Article  MathSciNet  Google Scholar 

  59. Lipp, M., Gruss, D., Schwarz, M.: AMD prefetch attacks through power and time. In: USENIX Security Symposium (2022)

    Google Scholar 

  60. Lipp, M., Gruss, D., Spreitzer, R., Maurice, C., Mangard, S.: \(\{\)ARMageddon\(\}\): cache attacks on mobile devices. In: 25th USENIX Security Symposium (USENIX Security 16), pp. 549–564 (2016)

    Google Scholar 

  61. Lipp, M., Hadžić, V., Schwarz, M., Perais, A., Maurice, C., Gruss, D.: Take a way: exploring the security implications of AMD’s cache way predictors. In: Proceedings of the 15th ACM Asia Conference on Computer and Communications Security, pp. 813–825 (2020)

    Google Scholar 

  62. Lipp, M., et al.: PLATYPUS: software-based power side-channel attacks on x86. In: 2021 IEEE Symposium on Security and Privacy (SP), pp. 355–371. IEEE (2021)

    Google Scholar 

  63. Liu, F., et al.: CATalyst: defeating last-level cache side channel attacks in cloud computing. In: 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 406–418. IEEE (2016)

    Google Scholar 

  64. Liu, F., Yarom, Y., Ge, Q., Heiser, G., Lee, R.B.: Last-level cache side-channel attacks are practical. In: 2015 IEEE Symposium on Security and Privacy, pp. 605–622. IEEE (2015)

    Google Scholar 

  65. Lou, X., Zhang, T., Jiang, J., Zhang, Y.: A survey of microarchitectural side-channel vulnerabilities, attacks, and defenses in cryptography. ACM Comput. Surv. (CSUR) 54(6), 1–37 (2021)

    Article  Google Scholar 

  66. Lyu, Y., Mishra, P.: A survey of side-channel attacks on caches and countermeasures. J. Hardware Syst. Secur. 2(1), 33–50 (2018)

    Article  Google Scholar 

  67. Malozemoff, A., Wang, X., Katz, J.: EMP-toolkit framework. https://github.com/emp-toolkit. Accessed 30 Jan 2023 (2022)

  68. Martin, R., Demme, J., Sethumadhavan, S.: TimeWarp: rethinking timekeeping and performance monitoring mechanisms to mitigate side-channel attacks. In: 2012 39th Annual International Symposium on Computer Architecture (ISCA), pp. 118–129. IEEE (2012)

    Google Scholar 

  69. Moghimi, A., Irazoqui, G., Eisenbarth, T.: CacheZoom: how SGX amplifies the power of cache attacks. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 69–90. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_4

    Chapter  Google Scholar 

  70. Mohassel, P., Rosulek, M., Zhang, Y.: Fast and secure three-party computation: the garbled circuit approach. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 591–602 (2015)

    Google Scholar 

  71. Mohassel, P., Zhang, Y.: SecureML: a system for scalable privacy-preserving machine learning. In: 2017 IEEE Symposium on Security and Privacy (SP), pp. 19–38. IEEE (2017)

    Google Scholar 

  72. Mowery, K., Keelveedhi, S., Shacham, H.: Are AES x86 cache timing attacks still feasible? In: Proceedings of the 2012 ACM Workshop on Cloud Computing Security Workshop, pp. 19–24 (2012)

    Google Scholar 

  73. Mushtaq, M., Mukhtar, M.A., Lapotre, V., Bhatti, M.K., Gogniat, G.: Winter is here! a decade of cache-based side-channel attacks, detection & mitigation for RSA. Inf. Syst. 92, 101524 (2020)

    Article  Google Scholar 

  74. Nakamoto, A.: W-shield: protection against cryptocurrency wallet credential stealing. In: Workshop on Security and Privacy in E-Commerce 2018, pp. 71–107 (2018)

    Google Scholar 

  75. Nikolaenko, V., Weinsberg, U., Ioannidis, S., Joye, M., Boneh, D., Taft, N.: Privacy-preserving ridge regression on hundreds of millions of records. In: 2013 IEEE Symposium on Security and Privacy, pp. 334–348. IEEE (2013)

    Google Scholar 

  76. Ostrovsky, R., Paskin-Cherniavsky, A., Paskin-Cherniavsky, B.: Maliciously circuit-private FHE. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 536–553. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_30

    Chapter  Google Scholar 

  77. Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 1–20. Springer, Heidelberg (2006). https://doi.org/10.1007/11605805_1

    Chapter  Google Scholar 

  78. Page, D.: Theoretical use of cache memory as a cryptanalytic side-channel. Cryptology ePrint Archive (2002)

    Google Scholar 

  79. Percival, C.: Cache missing for fun and profit (2005)

    Google Scholar 

  80. Sahai, A., Seyalioglu, H.: Worry-free encryption: functional encryption with public keys. In: Proceedings of the 17th ACM Conference on Computer and Communications Security, pp. 463–472 (2010)

    Google Scholar 

  81. Saxena, A., Panda, B.: DABANGG: a case for noise resilient flush-based cache attacks. In: 2022 IEEE Security and Privacy Workshops (SPW), pp. 323–334. IEEE (2022)

    Google Scholar 

  82. Schneider, T.: Practical secure function evaluation. In: Informatiktage, pp. 37–40 (2008)

    Google Scholar 

  83. Schwarz, M., et al.: Automated detection, exploitation, and elimination of double-fetch bugs using modern CPU features. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security, pp. 587–600 (2018)

    Google Scholar 

  84. Schwarz, M., Weiser, S., Gruss, D., Maurice, C., Mangard, S.: Malware guard extension: using SGX to conceal cache attacks. In: Polychronakis, M., Meier, M. (eds.) DIMVA 2017. LNCS, vol. 10327, pp. 3–24. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60876-1_1

    Chapter  Google Scholar 

  85. Sherali, H.D., Tuncbilek, C.H.: A squared-Euclidean distance location-allocation problem. Naval Res. Logist. (NRL) 39(4), 447–469 (1992)

    Article  MathSciNet  Google Scholar 

  86. Songhori, E., Siam, H., Riazi, S.: Tinygarble framework. https://github.com/esonghori/TinyGarble. Accessed 30 Jan 2023 (2019)

  87. Songhori, E.M., Hussain, S.U., Sadeghi, A.R., Schneider, T., Koushanfar, F.: TinyGarble: highly compressed and scalable sequential garbled circuits. In: 2015 IEEE Symposium on Security and Privacy, pp. 411–428. IEEE (2015)

    Google Scholar 

  88. Standaert, F.-X., Malkin, T.G., Yung, M.: A unified framework for the analysis of side-channel key recovery attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 443–461. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_26

    Chapter  Google Scholar 

  89. Tian, L., Jayaraman, B., Gu, Q., Evans, D.: Aggregating private sparse learning models using multi-party computation. In: NIPS Workshop on Private Multi-Party Machine Learning (2016)

    Google Scholar 

  90. Vattikonda, B.C., Das, S., Shacham, H.: Eliminating fine grained timers in XEN. In: Proceedings of the 3rd ACM workshop on Cloud Computing Security Workshop, pp. 41–46 (2011)

    Google Scholar 

  91. Whitnall, C., Oswald, E.: Robust profiling for DPA-style attacks. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 3–21. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48324-4_1

    Chapter  Google Scholar 

  92. Wu, M., Guo, S., Schaumont, P., Wang, C.: Eliminating timing side-channel leaks using program repair. In: Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 15–26 (2018)

    Google Scholar 

  93. Yao, A.C.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science (SFCS 1986), pp. 162–167. IEEE (1986)

    Google Scholar 

  94. Yarom, Y., Falkner, K.: Flush+ reload: a high resolution, low noise, l3 cache side-channel attack. In: 23rd \(\{\)USENIX\(\}\) Security Symposium (\(\{\)USENIX\(\}\) Security 14), pp. 719–732 (2014)

    Google Scholar 

  95. Zahur, S., Kerneis, G., Necula, G.: Obliv-C secure computation compiler. https://github.com/samee/obliv-c. Accessed 2 Feb 2023 (2018)

  96. Zahur, S., Evans, D.: Obliv-C: A language for extensible data-oblivious computation. Cryptology ePrint Archive (2015)

    Google Scholar 

  97. Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 220–250. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_8

    Chapter  Google Scholar 

  98. Zhao, L., Iyer, R., Makineni, S., Newell, D., Cheng, L.: NCID: a non-inclusive cache, inclusive directory architecture for flexible and efficient cache hierarchies. In: Proceedings of the 7th ACM International Conference on Computing Frontiers, pp. 121–130 (2010)

    Google Scholar 

Download references

Acknowledgments

This work has been supported partially by Semiconductor Research Corporation (SRC) under Task IDs 2991.001 and 2992.001 and NSF under award number 2138420. We also thank Mr. Saleh Khalaj Monfared and Mr. Caner Tol for their support.

Author information

Authors and Affiliations

  1. Worcester Polytechnic Institute, Worcester, MA, 01609, USA

    Mohammad Hashemi & Fatemeh Ganji

  2. University of Florida, Gainesville, FL, 32611, USA

    Domenic Forte

Authors
  1. Mohammad Hashemi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Domenic Forte
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fatemeh Ganji
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Mohammad Hashemi or Fatemeh Ganji .

Editor information

Editors and Affiliations

  1. New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

    Christina Pöpper

  2. Radboud University Nijmegen, Nijmegen, The Netherlands

    Lejla Batina

Appendices

Appendix A

Table 3 contains details of leaky IF conditions in each function of TinyGarble [86], EMP-toolkit [67], Obliv-C [96], and ABY [18].

Fig. 6.
figure 6

SR of Goblin for 1000 randomly chosen inputs given to GC garbled by TinyGarble [87] when (a) only free-XOR or (b) half-gate optimization is enabled and JG is disabled.

Full size image
Fig. 7.
figure 7

SR of Goblin against MULT, SUM, and Hamming benchmark functions for a range of inputs garbled by TinyGarble [86] when (a) only free-XOR optimization, (b) half-gate protocol is enabled, and JG is disabled.

Full size image

Appendix B

To study the impact of an implementation in which not all timing side-channel vulnerabilities are considered, we have launched Goblin against TinyGarble when the JG has been disabled.

Fig. 8.
figure 8

SR of Goblin against 128-bit (a) SUM, (b) Hamming, and (c) MULT. CPU cycle traces captured from 10-100, 000 randomly chosen inputs when JG is disabled. (Top: TinyGarble [86] with only free-XOR, Bottom: with half-gate optimization).

Full size image
Table 2. Type of the gates in the input layer of the AES and 256-bit MULT modules.
Full size table

Fig. 6 illustrates the results of Goblin against TinyGarble when JG is disabled. It is observable in Fig. 6 that even without JG, Goblin can reveal the garbler’s input with an average SR average of \(95\%\) or higher, slightly lower than the case when JG is enabled. To further investigate this, we launched Goblin against MULT, SUM, and Hamming benchmarks with input ranges between 128 and 1024 bits when JG was disabled. Figure 7 shows the results of launching Goblin against MULT, SUM, and Hamming benchmark functions for a range of inputs garbled by TinyGarble when (a) only free-XOR optimization, (b) half-gate protocol is enabled, and JG is disabled. Same as results in Sect. 5.2, one can observe a similar pattern of increasing SR of Goblin according to the increased size of benchmarks input. As another part of our investigations, we have launched Goblin against MULT, SUM, and Hamming modules without JG. Figure 8 illustrates SR of Goblin against 128-bit (a) SUM, (b) Hamming, and (b) MULT benchmarks for a range of CPU cycle traces captured from \(10-100,000\) randomly chosen inputs when JG is disabled. These results prove that Goblin can reveal garbler information from an insecurely implemented framework even without the help of JG.

Appendix C

The JG, as in Algorithm 1, works as follows. The iteration’s parameter n determines how many cell indexes in the array are summed and updates another array cell. This procedure repeats until it reaches the index of (Size-1). At this point, JG produces new random numbers and repeats the process indefinitely, resulting in cache disruption and potentially evicting critical data, like the global parameter R used for free-XOR [53]/Half-gates [97] optimizations.

Algorithm 1
figure c

. Junk Generator pseudo code

Full size image

Appendix D

To investigate the effects of the gate types in the input layer on the SR, we counted the number of XOR and AND gates in the input layer of the AES and 256-bit MULT since the results for these two benchmark functions vary largely as shown in Fig. 3. Table 2 contains the detail about the type of the gates in the AES and 256-bit MULT benchmark functions. Moreover, the category of AND gate contains AND/NAND, OR/NOR, ANDN, ORN, NANDN, and NORN gates, and the category of XOR gate includes NV, XOR, and XNOR gates as described in Sect. 4.3. It is observable that the AND gates are dominant in the AES input layer (\(75\%\) input layer gates) while the portions of XOR and AND gates are equal in the input layer of 256-bit MULT. This can explain why the results for these two benchmark functions are different. In fact, it is because of the fact that it is more challenging to determine the inputs given to XOR gates.

Fig. 9.
figure 9

SR of Goblin computed separately for AND and XOR input gates of 128-AES, 256-bit MULT, 128-bit Hamming, 128-bit SUM, and 288-bit SHA modules with (a) free-XOR and (b) half-gate optimization.

Full size image
Table 3. A detailed report of leaky IF conditions (IF) of every function call in JustGarble [4], TinyGarble [86] with half-gate and free-XOR optimization, EMP-toolkit [67], Obliv-C [96], and ABY [18].
Full size table

To further analyze the reason behind this, we have separately calculated the SR of Goblin against applied against AND and XOR gates. Figure 9 illustrates the results for launching Goblin against 128-AES, 256-bit MULT, 128-bit Hamming, 128-bit SUM, and 288-bit SHA modules, similar to Fig. 3, where the results for AND and XOR gates are combined. As observable in Fig. 9, Goblin’s average SR when launching against AND gates are always close to \(100\%\) while its average SR has a range between \(100\%\) and \(65\%\) when launching against XOR gates for the benchmark functions. This is aligned with the results presented in Fig. 3. In that figure, the difference between the mean values of CPU cycles collected for inputs “0” and “1” is larger for AND gates in comparison to XOR gates.

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hashemi, M., Forte, D., Ganji, F. (2024). Time Is Money, Friend! Timing Side-Channel Attack Against Garbled Circuit Constructions. In: Pöpper, C., Batina, L. (eds) Applied Cryptography and Network Security. ACNS 2024. Lecture Notes in Computer Science, vol 14585. Springer, Cham. https://doi.org/10.1007/978-3-031-54776-8_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-54776-8_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-54775-1

  • Online ISBN: 978-3-031-54776-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation