×

On bounded distance decoding with predicate: breaking the “lattice barrier” for the hidden number problem. (English) Zbl 1479.94108

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2021. 40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12696, 528-558 (2021).
Summary: Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short.
We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.
For the entire collection see [Zbl 1475.94010].

MSC:

94A60 Cryptography

Software:

fpLLL; G6K; fpylll
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: 33rd ACM STOC, pp. 601-610. ACM Press, July 2001 · Zbl 1323.68561
[2] Albrecht, M.R., Bai, S., Fouque, P.A., Kirchner, P., Stehlé, D., Wen, W.: Faster enumeration-based lattice reduction: Root hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\). In: Micciancio and Ristenpart [5], pp. 186-212 · Zbl 1501.94023
[3] Albrecht, MR; Cid, C.; Faugère, J.; Fitzpatrick, R.; Perret, L., On the complexity of the BKW algorithm on LWE, Des. Codes Cryptogr., 74, 2, 325-354 (2015) · Zbl 1331.94051 · doi:10.1007/s10623-013-9864-x
[4] Albrecht, M.R., Deo, A., Paterson, K.G.: Cold boot attacks on ring and module LWE keys under the NTT. IACR TCHES 2018(3), 173-213 (2018). https://tches.iacr.org/index.php/TCHES/article/view/7273
[5] Albrecht, MR; Ducas, L.; Herold, G.; Kirshanova, E.; Postlethwaite, EW; Stevens, M.; Ishai, Y.; Rijmen, V., The general sieve kernel and new records in lattice reduction, Advances in Cryptology - EUROCRYPT 2019, 717-746 (2019), Cham: Springer, Cham · Zbl 1509.94054 · doi:10.1007/978-3-030-17656-3_25
[6] Albrecht, MR; Göpfert, F.; Virdia, F.; Wunderer, T.; Takagi, T.; Peyrin, T., Revisiting the expected cost of solving uSVP and applications to LWE, Advances in Cryptology - ASIACRYPT 2017, 297-322 (2017), Cham: Springer, Cham · Zbl 1420.94034 · doi:10.1007/978-3-319-70694-8_11
[7] Albrecht, M.R., Heninger, N.: Bounded distance decoding with predicate source code, December 2020. https://github.com/malb/bdd-predicate/
[8] Albrecht, MR; Player, R.; Scott, S., On the concrete hardness of Learning with Errors, J. Math. Cryptol., 9, 3, 169-203 (2015) · Zbl 1352.94023 · doi:10.1515/jmc-2015-0016
[9] Aldaya, A.C., Brumley, B.B., ul Hassan, S., García, C.P., Tuveri, N.: Port contention for fun and profit. In: 2019 IEEE Symposium on Security and Privacy, pp. 870-887. IEEE Computer Society Press, May 2019
[10] Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) USENIX Security 2016, pp. 327-343. USENIX Association, August 2016
[11] Applebaum, B.; Cash, D.; Peikert, C.; Sahai, A.; Halevi, S., Fast cryptographic primitives and circular-secure encryption based on hard learning problems, Advances in Cryptology - CRYPTO 2009, 595-618 (2009), Heidelberg: Springer, Heidelberg · Zbl 1252.94044 · doi:10.1007/978-3-642-03356-8_35
[12] Aranha, DF; Fouque, P-A; Gérard, B.; Kammerer, J-G; Tibouchi, M.; Zapalowicz, J-C; Sarkar, P.; Iwata, T., GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias, Advances in Cryptology - ASIACRYPT 2014, 262-281 (2014), Heidelberg: Springer, Heidelberg · Zbl 1306.94023 · doi:10.1007/978-3-662-45611-8_14
[13] Aranha, D.F., Novaes, F.R., Takahashi, A., Tibouchi, M., Yarom, Y.: LadderLeak: reaking ECDSA with less than one bit of nonce leakage. Cryptology ePrint Archive, Report 2020/615 (2020). https://eprint.iacr.org/2020/615
[14] Bai, S., Stehlé, D., Wen, W.: Improved reduction from the bounded distance decoding problem to the unique shortest vector problem in lattices. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) ICALP 2016. LIPIcs, vol. 55, pp. 76:1-76:12. Schloss Dagstuhl, July 2016 · Zbl 1391.94869
[15] Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA, pp. 10-24. ACM-SIAM, January 2016 · Zbl 1410.68093
[16] Becker, A., Gama, N., Joux, A.: Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. Cryptology ePrint Archive, Report 2015/522 (2015). http://eprint.iacr.org/2015/522
[17] Benger, N.; van de Pol, J.; Smart, NP; Yarom, Y.; Batina, L.; Robshaw, M., “Ooh Aah... just a little bit” : a small amount of side channel can go a long way, Cryptographic Hardware and Embedded Systems - CHES 2014, 75-92 (2014), Heidelberg: Springer, Heidelberg · Zbl 1332.94057 · doi:10.1007/978-3-662-44709-3_5
[18] Bleichenbacher, D.: On the generation of one-time keys in DL signature schemes. In: Presentation at IEEE P1363 working Group Meeting, p. 81 (2000)
[19] Bleichenbacher, D.: Experiments with DSA. CRYPTO 2005-Rump Session (2005)
[20] Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435-440. ACM Press, May 2000 · Zbl 1296.68122
[21] Boneh, D.; Venkatesan, R.; Koblitz, N., Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Advances in Cryptology — CRYPTO ’96, 129-142 (1996), Heidelberg: Springer, Heidelberg · Zbl 1329.94054 · doi:10.1007/3-540-68697-5_11
[22] Breitner, J.; Heninger, N.; Goldberg, I.; Moore, T., Biased nonce sense: lattice attacks against weak ECDSA signatures in cryptocurrencies, Financial Cryptography and Data Security, 3-20 (2019), Cham: Springer, Cham · Zbl 1460.94039 · doi:10.1007/978-3-030-32101-7_1
[23] Brumley, BB; Tuveri, N.; Atluri, V.; Diaz, C., Remote timing attacks are still practical, Computer Security - ESORICS 2011, 355-371 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-23822-2_20
[24] Cabrera Aldaya, A., Pereida García, C., Brumley, B.B.: From A to Z: projective coordinates leakage in the wild. IACR TCHES 2020(3), 428-453 (2020). https://tches.iacr.org/index.php/TCHES/article/view/8596
[25] Capkun, S., Roesner, F. (eds.): USENIX Security 2020. USENIX Association, August 2020
[26] Coppersmith, D.; Maurer, U., Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in Cryptology — EUROCRYPT ’96, 178-189 (1996), Heidelberg: Springer, Heidelberg · Zbl 1304.94043 · doi:10.1007/3-540-68339-9_16
[27] Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio and Ristenpart [56], pp. 329-358 · Zbl 1504.94128
[28] Dagdelen, Ö.; Schneider, M.; D’Ambra, P.; Guarracino, M.; Talia, D., Parallel enumeration of shortest lattice vectors, Euro-Par 2010 - Parallel Processing, 211-222 (2010), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-15291-7_21
[29] Dall, F., et al.: CacheQuote: efficiently recovering long-term secrets of SGX EPID via cache attacks. IACR TCHES 2018(2), 171-191 (2018). https://tches.iacr.org/index.php/TCHES/article/view/879
[30] De Mulder, E.; Hutter, M.; Marson, ME; Pearson, P.; Bertoni, G.; Coron, J-S, Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-Bit ECDSA, Cryptographic Hardware and Embedded Systems - CHES 2013, 435-452 (2013), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-40349-1_25
[31] Doulgerakis, E.; Laarhoven, T.; de Weger, B.; Ding, J.; Steinwandt, R., Finding closest lattice vectors using approximate Voronoi cells, Post-Quantum Cryptography, 3-22 (2019), Cham: Springer, Cham · Zbl 1447.94033 · doi:10.1007/978-3-030-25510-7_1
[32] Ducas, L.; Nielsen, JB; Rijmen, V., Shortest vector from lattice sieving: a few dimensions for free, Advances in Cryptology - EUROCRYPT 2018, 125-145 (2018), Cham: Springer, Cham · Zbl 1423.94069 · doi:10.1007/978-3-319-78381-9_5
[33] Fincke, U.; Pohst, M., Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comput., 44, 170, 463-471 (1985) · Zbl 0556.10022 · doi:10.1090/S0025-5718-1985-0777278-8
[34] Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 207-216. ACM Press, May 2008 · Zbl 1230.11153
[35] Gama, N.; Nguyen, PQ; Regev, O.; Gilbert, H., Lattice enumeration using extreme pruning, Advances in Cryptology - EUROCRYPT 2010, 257-278 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94056 · doi:10.1007/978-3-642-13190-5_13
[36] García, C.P., Brumley, B.B.: Constant-time callees with variable-time callers. In: Kirda, E., Ristenpart, T. (eds.) USENIX Security 2017, pp. 83-98. USENIX Association, August 2017
[37] 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 2016, pp. 1626-1638. ACM Press (Oct 2016)
[38] Gennaro, R., Robshaw, M.J.B. (eds.): CRYPTO 2015, Part I, LNCS, vol. 9215. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7 · Zbl 1319.94002
[39] Guo, Q., Johansson, T., Stankovski, P.: Coded-BKW: Solving LWE using lattice codes. In: Gennaro and Robshaw [38], pp. 23-42 · Zbl 1336.94051
[40] Hanrot, G.; Stehlé, D.; Menezes, A., Improved analysis of Kannan’s shortest lattice vector algorithm, Advances in Cryptology - CRYPTO 2007, 170-186 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94050 · doi:10.1007/978-3-540-74143-5_10
[41] Herold, G.; Kirshanova, E.; Fehr, S., Improved algorithms for the approximate k-list problem in Euclidean Norm, Public-Key Cryptography - PKC 2017, 16-40 (2017), Heidelberg: Springer, Heidelberg · Zbl 1404.11144 · doi:10.1007/978-3-662-54365-8_2
[42] Herold, G.; Kirshanova, E.; May, A., On the asymptotic complexity of solving LWE, Des. Codes Cryptogr., 86, 1, 55-83 (2018) · Zbl 1381.94071 · doi:10.1007/s10623-016-0326-0
[43] Howgrave-Graham, N.; Smart, NP, Lattice attacks on digital signature schemes, Des. Codes Cryptogr., 23, 3, 283-290 (2001) · Zbl 1006.94022 · doi:10.1023/A:1011214926272
[44] Jancar, J., Sedlacek, V., Svenda, P., Sys, M.: Minerva: he curse of ECDSA nonces. IACR TCHES 2020(4), 281-308 (2020). https://tches.iacr.org/index.php/TCHES/article/view/8684
[45] Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: 15th ACM STOC, pp. 193-206. ACM Press, April 1983
[46] Kannan, R., Minkowski’s convex body theorem and integer programming, Math. Oper. Res., 12, 3, 415-440 (1987) · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[47] Kirchner, P., Fouque, P.A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro and Robshaw [38], pp. 43-62 · Zbl 1336.94058
[48] Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: Shmoys, D.B. (ed.) 11th SODA. pp. 937-941. ACM-SIAM, January 2000 · Zbl 0953.65043
[49] Laarhoven, T.: Search problems in cryptography: from fingerprinting to lattice sieving. Ph.D. thesis, Eindhoven University of Technology (2015)
[50] Laarhoven, T.; Mariano, A.; Lange, T.; Steinwandt, R., Progressive lattice sieving, Post-Quantum Cryptography, 292-311 (2018), Cham: Springer, Cham · Zbl 1425.94066 · doi:10.1007/978-3-319-79063-3_14
[51] Lenstra, AK; Lenstra, HW Jr; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 366-389 (1982) · Zbl 0488.12001 · doi:10.1007/BF01457454
[52] Liu, M.; Chen, J.; Li, H.; Lin, D.; Xu, S.; Yung, M., Partially known nonces and fault injection attacks on SM2 signature algorithm, Information Security and Cryptology, 343-358 (2014), Cham: Springer, Cham · Zbl 1347.94047 · doi:10.1007/978-3-319-12087-4_22
[53] Liu, M.; Nguyen, PQ; Dawson, E., Solving BDD by enumeration: an update, Topics in Cryptology - CT-RSA 2013, 293-309 (2013), Heidelberg: Springer, Heidelberg · Zbl 1312.94070 · doi:10.1007/978-3-642-36095-4_19
[54] Merget, R., Brinkmann, M., Aviram, N., Somorovsky, J., Mittmann, J., Schwenk, J.: Raccoon attack: finding and exploiting most-significant-bit-oracles in TLS-DH(E), September 2020. https://raccoon-attack.com/RacoonAttack.pdf. Accessed 11 Sept 2020
[55] Micciancio, D.; Regev, O.; Bernstein, DJ; Buchmann, J.; Dahmen, E., Lattice-based cryptography, Post-Quantum Cryptography, 147-191 (2009), Heidelberg: Springer, Heidelberg · Zbl 1161.81324 · doi:10.1007/978-3-540-88702-7_5
[56] Micciancio, D., Ristenpart, T. (eds.): CRYPTO 2020, Part II, LNCS, vol. 12171. Springer, Heidelberg (2020). doi:10.1007/978-3-030-56880-1
[57] Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Charika, M. (ed.) 21st SODA,pp. 1468-1480. ACM-SIAM (2010) · Zbl 1288.94076
[58] Micciancio, D., Walter, M.: Fast lattice point enumeration with minimal overhead. In: Indyk, P. (ed.) 26th SODA, pp. 276-294. ACM-SIAM, January 2015 · Zbl 1372.68140
[59] Micciancio, D.; Walter, M.; Fischlin, M.; Coron, J-S, Practical, predictable lattice basis reduction, Advances in Cryptology - EUROCRYPT 2016, 820-849 (2016), Heidelberg: Springer, Heidelberg · Zbl 1385.94062 · doi:10.1007/978-3-662-49890-3_31
[60] Moghimi, D., Lipp, M., Sunar, B., Schwarz, M.: Medusa: Microarchitectural data leakage via automated attack synthesis. In: Capkun and Roesner [25], pp. 1427-1444
[61] Moghimi, D., Sunar, B., Eisenbarth, T., Heninger, N.: TPM-FAIL: TPM meets timing and lattice attacks. In: Capkun and Roesner [25], pp. 2057-2073
[62] Nemec, M., Sýs, M., Svenda, P., Klinec, D., Matyas, V.: The return of coppersmith’s attack: practical factorization of widely used RSA moduli. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1631-1648. ACM Press (2017)
[63] Nguyen, PQ; Shparlinski, I., The insecurity of the digital signature algorithm with partially known nonces, J. Cryptol., 15, 3, 151-176 (2002) · Zbl 1009.94011 · doi:10.1007/s00145-002-0021-3
[64] Nguyen, PQ; Tibouchi, M.; Joye, M.; Tunstall, M., Lattice-based fault attacks on signatures, Fault Analysis in Cryptography, 201-220 (2012), Heidelberg: Springer, Heidelberg · Zbl 1267.94087 · doi:10.1007/978-3-642-29656-7_12
[65] Nguyen, PQ; Vidick, T., Sieve algorithms for the shortest vector problem are practical, J. Math. Cryptol., 2, 2, 181-207 (2008) · Zbl 1193.11117 · doi:10.1515/JMC.2008.009
[66] Phost, M., On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications, SIGSAM Bull., 15, 37-44 (1981) · Zbl 0467.10022 · doi:10.1145/1089242.1089247
[67] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84-93. ACM Press, May 2005 · Zbl 1192.94106
[68] Ryan, K.: Return of the hidden number problem. IACR TCHES 2019(1), 146-168 (2018).https://tches.iacr.org/index.php/TCHES/article/view/7337
[69] Ryan, K.: Hardware-backed heist: extracting ECDSA keys from qualcomm’s TrustZone. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 181-194. ACM Press, November 2019
[70] Schnorr, CP, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., 53, 201-224 (1987) · Zbl 0642.10030 · doi:10.1016/0304-3975(87)90064-8
[71] Schnorr, C.; Euchner, M., Lattice basis reduction: improved practical algorithms and solving subset sum problems, Math. Program., 66, 181-199 (1994) · Zbl 0829.90099 · doi:10.1007/BF01581144
[72] Stein, W., et al.: Sage Mathematics Software Version 9.0. The Sage Development Team (2019). http://www.sagemath.org
[73] Takahashi, A., Tibouchi, M., Abe, M.: New Bleichenbacher records: fault attacks on qDSA signatures. IACR TCHES 2018(3), 331-371 (2018). https://tches.iacr.org/index.php/TCHES/article/view/7278
[74] The FPLLL development team: FPLLL, a lattice reduction library (2020). https://github.com/fplll/fplll
[75] The FPLLL development team: FPyLLL, a Python interface to FPLLL (2020). https://github.com/fplll/fpylll
[76] The G6K development team: G6K (2020). https://github.com/fplll/g6k
[77] Tibouchi, M.: Attacks on (ec)dsa with biased nonces (2017). https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf, elliptic Curve Cryptography Workshop
[78] Weiser, S., Schrammel, D., Bodner, L., Spreitzer, R.: Big numbers - big troubles: Systematically analyzing nonce leakage in (EC)DSA implementations. In: Capkun and Roesner [25], pp. 1767-1784
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.