Farag, Abdel Alim, Kamal (2012) Cryptanalysis and Secure Implementation of Modern Cryptographic Algorithms. PhD thesis, Concordia University.
Preview |
Text (application/pdf)
1MBFarag_PhD_F2012.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
Cryptanalytic attacks can be divided into two classes: pure mathematical attacks and Side Channel Attacks (SCAs). Pure mathematical attacks are traditional cryptanalytic techniques that rely on known or chosen input-output pairs of the cryptographic function and exploit the inner structure of the cipher to reveal the secret key information. On the other hand, in SCAs, it is assumed that attackers have some access to the cryptographic device and can gain some information from its physical implementation.
Cold-boot attack is a SCA which exploits the data remanence property of Random Access Memory (RAM) to retrieve its content which remains readable shortly after its power has been removed. Fault analysis is another example of SCAs in which the attacker is assumed to be able to induce faults in the cryptographic device and observe the faulty output. Then, by careful inspection of faulty outputs, the attacker recovers the secret information, such as secret inner state or secret key. Scan-based Design-For-Test (DFT) is a widely deployed technique for testing hardware chips. Scan-based SCAs exploit the information obtained by analyzing the scanned data in order to retrieve secret information from cryptographic hardware devices that are designed with this testability feature.
In the first part of this work, we investigate the use of an off-the-shelf SAT solver, CryptoMinSat, to improve the key recovery of the Advance Encryption Standard (AES-128) key schedules from its corresponding decayed memory images which can be obtained using cold-boot attacks.
We also present a fault analysis on both NTRUEncrypt and NTRUSign cryptosystems. For this specific original instantiation of the NTRU encryption system with parameters $(N,p,q)$, our attack succeeds with probability $\approx 1-\frac{1}{p}$ and when the number of faulted coefficients is upper bounded by $t$, it requires $O((pN)^t)$ polynomial inversions in $\mathbb Z/p\mathbb Z[x]/(x^{N}-1)$. We also investigate several techniques to strengthen hardware implementations of NTRUEncrypt against this class of attacks. For NTRUSign with parameters ($N$, $q=p^l$, $\mathcal{B}$, \emph{standard}, $\mathcal{N}$), when the attacker is able to skip the norm-bound signature checking step, our attack needs one fault to succeed with probability $\approx 1-\frac{1}{p}$ and requires $O((qN)^t)$ steps when the number of faulted polynomial coefficients is upper bounded by $t$. The attack is also applicable to NTRUSign utilizing the \emph{transpose} NTRU lattice but it requires double the number of fault injections. Different countermeasures against the proposed attack are also investigated.
Furthermore, we present a scan-based SCA on NTRUEncrypt hardware implementations that employ scan-based DFT techniques. Our attack determines the scan chain structure of the polynomial multiplication circuits used in the decryption algorithm which allows the cryptanalyst to efficiently retrieve the secret key.
Several key agreement schemes based on matrices were recently proposed. For example, \'{A}lvarez \emph{et al.} proposed a scheme in which the secret key is obtained by multiplying powers of block upper triangular matrices whose elements are defined over $\mathbb{Z}_p$. Climent \emph{et al.} identified the elements of the endomorphisms ring $End(\mathbb{Z}_p \times \mathbb{Z}_{p^2})$ with elements in a set, $E_p$, of matrices of size $2\times 2$, whose elements in the first row belong to $\mathbb{Z}_{p}$ and the elements in the second row belong to $\mathbb{Z}_{p^2}$. Keith Salvin presented a key exchange protocol using matrices in the general linear group, $GL(r,\mathbb{Z}_n)$, where $n$ is the product of two distinct large primes. The system is fully specified in the US patent number 7346162 issued in 2008. In the second part of this work, we present mathematical cryptanalytic attacks against these three schemes and show that they can be easily broken for all practical choices of their security parameters.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Electrical and Computer Engineering |
|---|---|
| Item Type: | Thesis (PhD) |
| Authors: | Farag, Abdel Alim, Kamal |
| Institution: | Concordia University |
| Degree Name: | Ph. D. |
| Program: | Electrical and Computer Engineering |
| Date: | July 2012 |
| Thesis Supervisor(s): | Youssef, Amr |
| Keywords: | Side channel attacks, Cryptography, Cryptanalaysis, Key exchange schemes, Cold-boot attack, Fault attacks, Scan-based attack, Hardware implementation, CUDA framework, Graphic processing units (GPU). |
| ID Code: | 974675 |
| Deposited By: | ABDEL ALIM KAMA FARAG |
| Deposited On: | 30 Oct 2012 18:52 |
| Last Modified: | 18 Jan 2018 17:38 |
References:
[1] M. Agrawal, S. Karmakar, D. Saha, and D. Mukhopadhyay. Scan based side channel attacks on stream ciphers and their counter-measures. In Proceedings of the International Conference on Cryptology in India (INDOCRYPT’08), volume 5365 of Lecture Notes in Computer Science, pages 226–238, Kharagpur, India, 2008. Springer.[2] A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In Proceedings of Theory of Cryptography Conference(TCC’09), volume 5444 of Lecture Notes in Computer Science, pages 474–495, SanFrancisco, CA, USA, 2009. Springer.
[3] M.-L. Akkar, R. Bevan, P. Dischamp, and D. Moyart. Power analysis, what is now possible... In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’00), volume 1976 of Lecture Notes in Computer Science, pages 489–502, Kyoto, Japan, 2000. Springer.
[4] M.-L. Akkar and C. Giraud. An implementation of DES and AES, secure against some attacks. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems (CHES’01), volume 2162 of Lecture Notes in Computer Science, pages 309–318, Paris, France, 2001. Springer.
[5] R. Álvarez, F. Ferrández, J.-F. Vicent, and A. Zamora. Applying quick exponentiation for block upper triangular matrices. Applied Mathematics and Computation, 183(2):729–737, 2006.
[6] R. Álvarez, F. Mart´ınez, J.-F. Vicent, and A. Zamora. Cryptographic applications of3x3 block upper triangular matrices. In Proceedings of the International Conference on Hybrid Artificial Intelligent Systems (HAIS’12), volume 7209 of Lecture Notes in Computer Science, pages 97–104, Salamanca, Spain, 2012. Springer.
[7] R. Álvarez, L. Tortosa, J. Vicent, and A. Zamora. A non-abelian group based on block upper triangular matrices with cryptographic applications. In Proceedings of the International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC’09), volume 5527 of Lecture Notes in Computer Science, pages 117–126,Tarragona, Catalonia, Spain, 2009. Springer.
[8] R. Álvarez, L. Tortosa, J.-F. Vicent, and A. Zamora. Analysis and design of a secure key exchange scheme. Information Sciences, 179(12):2014–2021, 2009.
[9] J. Alwen, Y. Dodis, and D. Wichs. Leakage-resilient public-key cryptography in the bounded-retrieval model. In Proceedings of the International Cryptology Conference(CRYPTO’09), volume 5677 of Lecture Notes in Computer Science, pages 36–54, Santa Barbara, CA, USA, 2009. Springer.
[10] R. J. Anderson, M. Bond, J. Clulow, and S. P. Skorobogatov. Cryptographic processors–a survey. Proceedings of the IEEE, 94(2):357–369, 2006.
[11] R. J. Anderson and M. G. Kuhn. Low cost attacks on tamper resistant devices. In Proceedings of the International Workshop on Security Protocols, volume 1361 of Lecture Notes in Computer Science, pages 125–136, Paris, France, 1997. Springer.
[12] A. C. Atici, L. Batina, J. Fan, I. Verbauwhede, and S. B. Örs. Low-cost implementations of NTRU for pervasive security. In Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors (ASAP’08), pages 79–84,Leuven, Belgium, 2008. IEEE Computer Society.
[13] A. C. Atici, L. Batina, B. Gierlichs, and I. Verbauwhede. Power analysis on NTRU implementation for RFIDs: First results. In Proceedings of the Workshop on RFID Security(RFIDSec’08), pages 128–139, Budapest, Hungary, 2008.
[14] M. F. Atiyah and I. G. MacDonald. Introduction to commutative algebra. Westview Press, New York, NY, USA, 1969.
[15] D. V. Bailey, D. Coffin, A. J. Elbirt, J. H. Silverman, and A. D. Woodbury. NTRU in constrained devices. In Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems (CHES’01), volume 2162 of Lecture Notes inComputer Science, pages 262–272, Paris, France, 2001. Springer.
[16] H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, and C. Whelan. The sorcerers apprentice guide to fault attacks. Proceedings of the IEEE, 94(2):370–382, 2006.
[17] G. M. Bergman. Some examples in PI ring theory. Israel Journal of Mathematics, 18(3):257–277, 1974.
[18] D. L. Berre and A. Parrain. The SAT4J library, release 2.2. Satisfiability, Boolean Modeling and Computation, 7:59–64, 2010.
[19] D. L. Berre and O. Roussel. The international SAT competitions.http://www.satcompetition.org/, 2009.
[20] G. Bertoni, L. Breveglieri, I. Koren, P. Maistri, and V. Piuri. Error analysis and detection procedures for a hardware implementation of the advanced encryption standard. IEEE Transactions on Computers, 52(4):492–505, 2003.
[21] A. Berzati, C. Canovas, J.-G. Dumas, and L. Goubin. Fault attacks on RSA public keys: Left-to-right implementations are also vulnerable. In Proceedings of the Cryptographers’Track at the RSA Conference (CT-RSA’09), volume 5473 of Lecture Notes in ComputerScience, pages 414–428, San Francisco, CA, USA, 2009. Springer.
[22] A. Berzati, C. Canovas, and L. Goubin. Perturbating RSA public keys: An improved attack. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems (CHES’08), volume 5154 of Lecture Notes in Computer Science, pages 380–395, Washington, DC, USA, 2008. Springer.
[23] I. Biehl, B. Meyer, and V. Müller. Differential fault attacks on elliptic curve cryptosystems .In Proceedings of the International Cryptology Conference (CRYPTO’00), volume1880 of Lecture Notes in Computer Science, pages 131–146, Santa Barbara, CA, USA,2000. Springer.
[24] J. Biernat and M. Nikodem. Fault cryptanalysis of ElGamal signature scheme. In Proceedings of the International Conference on Computer Aided Systems Theory (EUROCAST’05), volume 3643 of Lecture Notes in Computer Science, pages 327–336, Las Palmas de Gran Canaria, Spain, 2005. Springer.
[25] E. Biham and A. Shamir. Differential fault analysis of secret key cryptosystems. In Proceedings of the International Cryptology Conference (CRYPTO’97), volume 1294 of Lecture Notes in Computer Science, pages 513–525, Santa Barbara, CA, USA, 1997.Springer.
[26] I. F. Blake, G. Seroussi, and N. P. Smart. Elliptic curves in cryptography. London Mathematical Society Lecture Notes in Computer Science. Cambridge University Press, Cambridge, UK, 1999.
[27] J. Blömer and M. Otto. Wagner’s attack on a secure CRT-RSA algorithm reconsidered. In Proceedings of the International Workshop on Fault Diagnosis and Tolerance in Cryptography(FDTC’06), volume 4236 of Lecture Notes in Computer Science, pages 13–23,Yokohama, Japan, 2006. Springer.
[28] J. Blömer, M. Otto, and J.-P. Seifert. A new CRT-RSA algorithm secure against Bellcore attacks. In Proceedings of the Conference on Computer and Communications Security(CCS’03), pages 311–320, Washington, DC, USA, 2003. ACM.
[29] D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of checking cryptographic protocols for faults (extended abstract). In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT’97), volume1233 of Lecture Notes in Computer Science, pages 37–51, Konstanz, Germany, 1997.Springer.
[30] D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of eliminating errors in cryptographic computations. Cryptology, 14(2):101–119, 2001.
[31] E. Brier, B. Chevallier-Mames, M. Ciet, and C. Clavier. Why one should also secure RSA public key elements. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems (CHES’06), volume 4249 of Lecture Notes in Computer Science, pages 324–338, Yokohama, Japan, 2006. Springer.
[32] B. Buchberger. Gröbner bases: An algorithmic method in polynomial ideal theory. InN. K. Bose and J. P. Guiver, editors, Multidimensional systems theory: Progress, directions and open problems in multidimensional systems, pages 184–232. Reidel Publishing Company, 1985.
[33] I. Buck, T. Foley, D. R. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan. Brook for GPUs: Stream computing on graphics hardware. ACM Transactions on Graphics, 23(3):777–786, 2004.
[34] M. L. Bushnell and V. D. Agrawal. Essentials of electronic testing for digital, memory, and mixed-signal VLSI circuits. Kluwer Academic, Boston, MA, USA, 2000.
[35] R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-resilient functions and all-or-nothing transforms. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT’00), volume 1807of Lecture Notes in Computer Science, pages 453–469, Bruges, Belgium, 2000. Springer.
[36] D. Cash, Y. Z. Ding, Y. Dodis, W. Lee, R. J. Lipton, and S. Walfish. Intrusion-resilient key exchange in the bounded retrieval model. In Proceedings of Theory of Cryptography Conference (TCC’07), volume 4392 of Lecture Notes in Computer Science, pages 479–498, Amsterdam, Netherlands, 2007. Springer.
[37] J. C. Cha, K. H. Ko, S. Lee, J. W. Han, and J. H. Cheon. An efficient implementation ofbraid groups. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’01), volume 2248 of Lecture Notes in Computer Science, pages 144–156, Gold Coast, Australia, 2001. Springer.
[38] S. Chari, C. S. Jutla, J. R. Rao, and P. Rohatgi. Towards sound approaches to counteract power-analysis attacks. In Proceedings of the International Cryptology Conference(CRYPTO’99), volume 1666 of Lecture Notes in Computer Science, pages 398–412,Santa Barbara, CA, USA, 1999. Springer.
[39] J. H. Cheon and B. Jun. A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem. In Proceedings of the International Cryptology Conference (CRYPTO’03),volume 2729 of Lecture Notes in Computer Science, pages 212–225, Santa Barbara, CA,USA, 2003. Springer.
[40] J.-J. Climent, P. R. Navarro, and L. Tortosa. On the arithmetic of the endomorphisms ring End(Zp×Zp2). Applicable Algebra in Engineering, Communication and Computing, 22(2):91–108, 2011.
[41] Close to Metal. Technology unleashes the power of stream computing. http://www.amd.com/us/press-releases/Pages/Press Release 114147.aspx, 2006.
[42] Consortium for Efficient Embedded Security. Efficient embedded security standard (EESS) #1: Implementation aspects of NTRUEncrypt and NTRUSign.http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf, 2003.
[43] D. L. Cook, J. Ioannidis, A. D. Keromytis, and J. Luck. CryptoGraphics: Secret key cryptography using graphics cards. In Proceedings of the Cryptographers’ Track at the RSA Conference (CT-RSA’05), volume 3376 of Lecture Notes in Computer Science, pages334–350, San Francisco, CA, USA, 2005. Springer.
[44] S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Symposium on Theory of Computing (STOC’71), pages 151–158, Shaker Heights, Ohio, USA, 1971. ACM.
[45] N. Courtois and G. V. Bard. Algebraic cryptanalysis of the data encryption standard. In Proceedings of the International Conference on Cryptography and Coding, volume 4887of Lecture Notes in Computer Science, pages 152–169, Cirencester, UK, 2007. Springer.
[46] N. Courtois, G. V. Bard, and D. Wagner. Algebraic and slide attacks on KeeLoq. In Proceedings of the International Workshop on Fast Software Encryption (FSE’08), volume5086 of Lecture Notes in Computer Science, pages 97–115, Lausanne, Switzerland,2008. Springer.
[47] N. Courtois, S. O’Neil, and J.-J. Quisquater. Practical algebraic attacks on the Hitag2stream cipher. In Proceedings of the International Conference on Information Security(ISC’09), volume 5735 of Lecture Notes in Computer Science, pages 167–176, Pisa, Italy,2009. Springer.
[48] N. T. Courtois, K. Nohl, and S. O’Neil. Algebraic attacks on the Crypto-1 stream cipherin MiFare classic and Oyster cards. International Association for Cryptologic Research(IACR), 166, 2008.
[49] J. Daemen and V. Rijmen. The design of Rijndael: AES–The advanced encryption standard. Springer, New York, NY, USA, 2002.
[50] M. Davis and H. Putnam. A computing procedure for quantification theory. ACM, 7(3):201–215, 1960.
[51] D. De, A. Kumarasubramanian, and R. Venkatesan. Inversion attacks on secure hash functions using SAT solvers. In Proceedings of the International Conference on Theory and applications of satisfiability testing (SAT’07), volume 4501 of Lecture Notes in Computer Science, pages 377–382, Lisbon, Portugal, 2007. Springer.
[52] J.-F. Dhem, F. Koeune, P.-A. Leroux, P. Mestré, J.-J. Quisquater, and J.-L. Willems.A practical implementation of the timing attack. In Proceedings of the International Conference on Smart Card Research and Applications (CARDIS’98), volume 1820 of Lecture Notes in Computer Science, pages 167–182, Louvain-la-Neuve, Belgium, 1998.Springer.
[53] B. Driessen, A. Poschmann, and C. Paar. Comparison of innovative signature algorithms for WSNs. In Proceedings of the Conference on Wireless Network Security (WISEC’08),pages 30–35, Alexandria, VA, USA, 2008. ACM.
[54] P. Dusart, G. Letourneux, and O. Vivolo. Differential fault analysis on AES. In Proceedings of the International Conference on Applied Cryptography and Network Security(ACNS’03), volume 2846 of Lecture Notes in Computer Science, pages 293–306,Kunming, China, 2003. Springer.
[55] N. Eén and N. Sörensson. An extensible SAT-solver. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT’03), volume 2919of Lecture Notes in Computer Science, pages 502–518, Santa Margherita Ligure, Italy,2003. Springer.
[56] T. Eibach, E. Pilz, and G. Völkel. Attacking Bivium using SAT solvers. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing(SAT’08), volume 4996 of Lecture Notes in Computer Science, pages 63–76, Guangzhou, China, 2008. Springer.
[57] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469–472, 1985.
[58] J. Erickson, J. Ding, and C. Christensen. Algebraic cryptanalysis of SMS4: Gröbner basis attack and SAT attack compared. In Proceedings of the International Conference on Information, Security and Cryptology (ICISC’09), volume 5984 of Lecture Notes in Computer Science, pages 73–86, Seoul, Korea, 2009. Springer.
[59] Federal Information Processing Standards Publication (FIPS). Announcing the advanced encryption standard (AES). National Institute of Standards and Technology (NIST), 197,2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.
[60] Federal Information Processing Standards Publication (FIPS). Security requirements for cryptographic modules. National Institute of Standards and Technology (NIST), 140(2),2001. http://http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf.
[61] K. Gandolfi, C. Mourtel, and F. Olivier. Electromagnetic analysis: Concrete results. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems (CHES’01), volume 2162 of Lecture Notes in Computer Science, pages 251–261,Paris, France, 2001. Springer.
[62] C. H. Gebotys and R. J. Gebotys. Secure elliptic curve implementations: An analysis of resistance to power-attacks in a DSP processor. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems (CHES’02), volume 2523of Lecture Notes in Computer Science, pages 114–128, Redwood Shores, CA, USA,2002. Springer.
[63] L. Genelle, E. Prouff, and M. Quisquater. Thwarting higher-order side channel analysis with additive and multiplicative maskings. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems (CHES’11), volume 6917 of Lecture Notes in Computer Science, pages 240–255, Nara, Japan, 2011. Springer.
[64] C. Gentry, J. Jonsson, J. Stern, and M. Szydlo. Cryptanalysis of the NTRU signature scheme (NSS) from Eurocrypt 2001. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’01),volume 2248 of Lecture Notes in Computer Science, pages 1–20, Gold Coast, Australia,2001. Springer.
[65] C. Gentry and M. Szydlo. Cryptanalysis of the revised
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics