Skip to main content
Erschienen in: Journal of Cryptographic Engineering 1/2020

12.01.2019 | Regular Paper

Improved parallel mask refreshing algorithms: generic solutions with parametrized non-interference and automated optimizations

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Refreshing algorithms are a critical ingredient for secure masking. They are instrumental in enabling sound composability properties for complex circuits, and their randomness requirements dominate the performance overheads in (very) high-order masking. In this paper, we improve a proposal of mask refreshing algorithms from EUROCRYPT 2017 that has excellent implementation properties in software and hardware, in two main directions. First, we provide a generic proof that this algorithm is secure at arbitrary orders—a problem that was left open so far. We introduce parametrized non-interference as a new technical ingredient for this purpose that may be of independent interest. Second, we use automated tools to further explore the design space of such algorithms and provide the best known parallel mask refreshing gadgets for concretely relevant security orders. Incidentally, we also prove the security of a recent proposal of mask refreshing with improved resistance against horizontal attacks from CHES 2017.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
In our notations, \({{\mathbf {x}}}^{{i}}\) always has to be interpreted modulo \(t+1\), i.e., \({{\mathbf {x}}}^{{i}} \mathrel {\triangleq }{{\mathbf {x}}}^{{i \bmod t+1}}\).
 
2
We note that another algorithm can be obtained by producing multiple encodings of 0 via \(\mathsf {ZeroBlock}\) and adding them together after they are produced. This algorithm has a marginally higher memory complexity, and we believe this makes no difference to security—which we leave as a scope for further investigations.
 
Literatur
1.
Zurück zum Zitat Albrecht, M.R., Paterson, K.G.: Lucky microseconds: a timing attack on Amazon’s s2n implementation of TLS. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I, Volume 9665 of LNCS, pp. 622–643. Springer, Heidelberg (2016) Albrecht, M.R., Paterson, K.G.: Lucky microseconds: a timing attack on Amazon’s s2n implementation of TLS. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I, Volume 9665 of LNCS, pp. 622–643. Springer, Heidelberg (2016)
2.
Zurück zum Zitat Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B.: Compositional verification of higher-order masking: application to a verifying masking compiler. Cryptology ePrint Archive, Report 2015/506. http://eprint.iacr.org/2015/506 Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B.: Compositional verification of higher-order masking: application to a verifying masking compiler. Cryptology ePrint Archive, Report 2015/506. http://​eprint.​iacr.​org/​2015/​506
3.
Zurück zum Zitat Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B., Strub, P.-Y.: Verified proofs of higher-order masking. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I, Volume 9056 of LNCS, pp. 457–485. Springer, Heidelberg (2015)MATH Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B., Strub, P.-Y.: Verified proofs of higher-order masking. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I, Volume 9056 of LNCS, pp. 457–485. Springer, Heidelberg (2015)MATH
4.
Zurück zum Zitat Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B., Strub, P.-Y., Zucchini, R.: Strong non-interference and type-directed higher-order masking. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16, pp. 116–129. ACM Press, New York (2016)CrossRef Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B., Strub, P.-Y., Zucchini, R.: Strong non-interference and type-directed higher-order masking. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16, pp. 116–129. ACM Press, New York (2016)CrossRef
5.
Zurück zum Zitat Barthe, G., Dupressoir, F., Faust, S., Grégoire, B., Standaert, F.-X., Strub, P.-Y.: Parallel implementations of masking schemes and the bounded moment leakage model. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I, Volume 10210 of LNCS, pp. 535–566. Springer, Heidelberg (2017)MATH Barthe, G., Dupressoir, F., Faust, S., Grégoire, B., Standaert, F.-X., Strub, P.-Y.: Parallel implementations of masking schemes and the bounded moment leakage model. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I, Volume 10210 of LNCS, pp. 535–566. Springer, Heidelberg (2017)MATH
6.
Zurück zum Zitat Battistello, A., Coron, J.-S., Prouff, E., Zeitoun, R.: Horizontal side-channel attacks and countermeasures on the ISW masking scheme. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016, Volume 9813 of LNCS, pp. 23–39. Springer, Heidelberg (2016) Battistello, A., Coron, J.-S., Prouff, E., Zeitoun, R.: Horizontal side-channel attacks and countermeasures on the ISW masking scheme. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016, Volume 9813 of LNCS, pp. 23–39. Springer, Heidelberg (2016)
7.
Zurück zum Zitat Belaïd, S., Benhamouda, F., Passelègue, A., Prouff, E., Thillard, A., Vergnaud, D.: Randomness complexity of private circuits for multiplication. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II, Volume 9666 of LNCS, pp. 616–648. Springer, Heidelberg (2016)MATH Belaïd, S., Benhamouda, F., Passelègue, A., Prouff, E., Thillard, A., Vergnaud, D.: Randomness complexity of private circuits for multiplication. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II, Volume 9666 of LNCS, pp. 616–648. Springer, Heidelberg (2016)MATH
8.
Zurück zum Zitat Carlet, C., Prouff, E., Rivain, M., Roche, T.: Algebraic decomposition for probing security. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I, Volume 9215 of LNCS, pp. 742–763. Springer, Heidelberg (2015) Carlet, C., Prouff, E., Rivain, M., Roche, T.: Algebraic decomposition for probing security. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I, Volume 9215 of LNCS, pp. 742–763. Springer, Heidelberg (2015)
9.
Zurück zum Zitat Cassiers, G., Standaert, F.-X.: Improved bitslice masking: from optimized non-interference to probe isolation. IACR Cryptol. ePrint Arch. 2018, 438 (2018) Cassiers, G., Standaert, F.-X.: Improved bitslice masking: from optimized non-interference to probe isolation. IACR Cryptol. ePrint Arch. 2018, 438 (2018)
10.
Zurück zum Zitat Coron, J.-S.: Higher order masking of look-up tables. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014, Volume 8441 of LNCS, pp. 441–458. Springer, Heidelberg (2014) Coron, J.-S.: Higher order masking of look-up tables. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014, Volume 8441 of LNCS, pp. 441–458. Springer, Heidelberg (2014)
11.
Zurück zum Zitat Coron, J.-S., Prouff, E., Rivain, M.: Side channel cryptanalysis of a higher order masking scheme. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007, Volume 4727 of LNCS, pp. 28–44. Springer, Heidelberg (2007)MATH Coron, J.-S., Prouff, E., Rivain, M.: Side channel cryptanalysis of a higher order masking scheme. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007, Volume 4727 of LNCS, pp. 28–44. Springer, Heidelberg (2007)MATH
12.
Zurück zum Zitat Coron, J.-S., Prouff, E., Rivain, M., Roche, T.: Higher-order side channel security and mask refreshing. In: Moriai, S. (ed.) FSE 2013, Volume 8424 of LNCS, pp. 410–424. Springer, Heidelberg (2014) Coron, J.-S., Prouff, E., Rivain, M., Roche, T.: Higher-order side channel security and mask refreshing. In: Moriai, S. (ed.) FSE 2013, Volume 8424 of LNCS, pp. 410–424. Springer, Heidelberg (2014)
13.
Zurück zum Zitat Duc, A., Dziembowski, S., Faust, S.: Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014, Volume 8441 of LNCS, pp. 423–440. Springer, Heidelberg (2014) Duc, A., Dziembowski, S., Faust, S.: Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014, Volume 8441 of LNCS, pp. 423–440. Springer, Heidelberg (2014)
14.
Zurück zum Zitat Duc, A., Faust, S., Standaert, F.-X.: Making masking security proofs concrete—or how to evaluate the security of any leaking device. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I, Volume 9056 of LNCS, pp. 401–429. Springer, Heidelberg (2015) Duc, A., Faust, S., Standaert, F.-X.: Making masking security proofs concrete—or how to evaluate the security of any leaking device. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I, Volume 9056 of LNCS, pp. 401–429. Springer, Heidelberg (2015)
15.
Zurück zum Zitat Faust, S., Rabin, T., Reyzin, L., Tromer, E., Vaikuntanathan, V.: Protecting circuits from leakage: the computationally-bounded and noisy cases. In: Gilbert, H. (ed.) EUROCRYPT 2010, Volume 6110 of LNCS, pp. 135–156. Springer, Heidelberg (2010) Faust, S., Rabin, T., Reyzin, L., Tromer, E., Vaikuntanathan, V.: Protecting circuits from leakage: the computationally-bounded and noisy cases. In: Gilbert, H. (ed.) EUROCRYPT 2010, Volume 6110 of LNCS, pp. 135–156. Springer, Heidelberg (2010)
16.
Zurück zum Zitat Fischer, W., Homma, N. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, Volume 10529 of Lecture Notes in Computer Science. Springer (2017) Fischer, W., Homma, N. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, Volume 10529 of Lecture Notes in Computer Science. Springer (2017)
17.
Zurück zum Zitat Genkin, D., Pachmanov, L., Pipman, I., Tromer, E., Yarom, Y.: ECDSA key extraction from mobile devices via nonintrusive physical side channels. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16, pp. 1626–1638. ACM Press, New York (2016)CrossRef Genkin, D., Pachmanov, L., Pipman, I., Tromer, E., Yarom, Y.: ECDSA key extraction from mobile devices via nonintrusive physical side channels. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16, pp. 1626–1638. ACM Press, New York (2016)CrossRef
18.
Zurück zum Zitat Goudarzi, D., Rivain, M.: How fast can higher-order masking be in software? In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I, Volume 10210 of LNCS, pp. 567–597. Springer, Heidelberg (2017) Goudarzi, D., Rivain, M.: How fast can higher-order masking be in software? In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I, Volume 10210 of LNCS, pp. 567–597. Springer, Heidelberg (2017)
19.
Zurück zum Zitat Groß, H., Mangard, S.: Reconciling d+1 masking in hardware and software. In: Fischer, W., Homma, N. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, Volume 10529 of Lecture Notes in Computer Science, pp. 115–136. Springer (2017) Groß, H., Mangard, S.: Reconciling d+1 masking in hardware and software. In: Fischer, W., Homma, N. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, Volume 10529 of Lecture Notes in Computer Science, pp. 115–136. Springer (2017)
20.
Zurück zum Zitat Gruss, D., Spreitzer, R., Mangard, S.: Cache template attacks: automating attacks on inclusive last-level caches. In: 24th USENIX Security Symposium, USENIX Security 15, Washington, DC, USA, August 12–14, 2015, pp. 897–912 (2015) Gruss, D., Spreitzer, R., Mangard, S.: Cache template attacks: automating attacks on inclusive last-level caches. In: 24th USENIX Security Symposium, USENIX Security 15, Washington, DC, USA, August 12–14, 2015, pp. 897–912 (2015)
21.
Zurück zum Zitat Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003, Volume 2729 of LNCS, pp. 463–481. Springer, Heidelberg (2003) Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003, Volume 2729 of LNCS, pp. 463–481. Springer, Heidelberg (2003)
22.
Zurück zum Zitat Journault, A., Standaert, F.-X.: Very high order masking: efficient implementation and security evaluation. In: Fischer, W., Homma, N. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, Volume 10529 of Lecture Notes in Computer Science, pp. 623–643. Springer (2017) Journault, A., Standaert, F.-X.: Very high order masking: efficient implementation and security evaluation. In: Fischer, W., Homma, N. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, Volume 10529 of Lecture Notes in Computer Science, pp. 623–643. Springer (2017)
23.
Zurück zum Zitat Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) CRYPTO’99, Volume 1666 of LNCS, pp. 388–397. Springer, Heidelberg (1999) Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) CRYPTO’99, Volume 1666 of LNCS, pp. 388–397. Springer, Heidelberg (1999)
24.
Zurück zum Zitat Prouff, E., Rivain, M.: Masking against side-channel attacks: a formal security proof. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013, Volume 7881 of LNCS, pp. 142–159. Springer, Heidelberg (2013) Prouff, E., Rivain, M.: Masking against side-channel attacks: a formal security proof. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013, Volume 7881 of LNCS, pp. 142–159. Springer, Heidelberg (2013)
25.
Zurück zum Zitat Rivain, M., Prouff, E.: Provably secure higher-order masking of AES. In: CHES, Volume 6225 of Lecture Notes in Computer Science, pp. 413–427. Springer (2010) Rivain, M., Prouff, E.: Provably secure higher-order masking of AES. In: CHES, Volume 6225 of Lecture Notes in Computer Science, pp. 413–427. Springer (2010)
26.
Zurück zum Zitat Schramm, K., Paar, C.: Higher order masking of the AES. In: Pointcheval, D. (ed.) CT-RSA 2006, Volume 3860 of LNCS, pp. 208–225. Springer, Heidelberg (2006) Schramm, K., Paar, C.: Higher order masking of the AES. In: Pointcheval, D. (ed.) CT-RSA 2006, Volume 3860 of LNCS, pp. 208–225. Springer, Heidelberg (2006)
27.
Zurück zum Zitat Tromer, E., Osvik, D.A., Shamir, A.: Efficient cache attacks on AES, and countermeasures. J. Cryptol. 23(1), 62–74 (2010)MathSciNetCrossRef Tromer, E., Osvik, D.A., Shamir, A.: Efficient cache attacks on AES, and countermeasures. J. Cryptol. 23(1), 62–74 (2010)MathSciNetCrossRef
Metadaten
Titel
Improved parallel mask refreshing algorithms: generic solutions with parametrized non-interference and automated optimizations
Publikationsdatum
12.01.2019
Erschienen in
Journal of Cryptographic Engineering / Ausgabe 1/2020
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-018-00202-2

Weitere Artikel der Ausgabe 1/2020

Journal of Cryptographic Engineering 1/2020 Zur Ausgabe