Strengthening Crypto-1 Cipher Against Algebraic Attacks

Farah Afianti, Ari M. Barmawi


In the last few years, several studies addressed the problem of data security in Mifare Classic. One of its weaknesses is the low random number quality. This causes SAT solver attacks to have lower complexity. In order to strengthen Crypto-1 against SAT solver attacks, a modification of the feedback function with better cryptographic properties is proposed. It applies a primitive polynomial companion matrix. SAT solvers cannot directly attack the feedback shift register that uses the modified Boolean feedback function, the register has to be split into smaller groups. Experimental testing showed that the amount of memory and CPU time needed were highest when attacking the modified Crypto-1 using the modified feedback function and the original filter function. In addition, another modified Crypto-1, using the modified feedback function and a modified filter function, had the lowest percentage of revealed variables. It can be concluded that the security strength and performance of the modified Crypto-1 using the modified feedback function and the modified filter function are better than those of the original Crypto-1.

Full Text:



Garcia, F.D.,van Rossum, P., Verdult, R. & Schreur, R.W., Wirelessly Pickpocketing a Mifare Classic Card, Proceedings of the 30th IEEE Symposium on Security and Privacy, pp. 3-15, Washington, DC, USA, 2009.

Courtois, N.T. & Nohl, K., Algebraic Attacks on the Crypto-1 Stream Cipher in Mifare Classic and Oyster Cards, Cryptology ePrint Archive, Report 2008/166,2008.

Garcia, F.D.,Gans, G.K., Muijrers, R., Rossum, P., Verdult, R., Schreur, R.W. & Jacobs, B., Dismantling Mifare Classic, Proceedings of the 13th European Symposium on Research in Computer Security: Computer Security, ESORICS ’08, pp. 97-114, Berlin, Heidelberg, 2008.

Nohl, K., Cryptanalysis of Crypto-1, Computer Science Department University of Virginia, White Paper, 2008.

Soos, M., Privacy-preserving Security Protocols for RFIDs. Master’s thesis, Institut Polytechnique de Grenoble, Grenoble, France, 6 October 2009.

Liu, M., Zhang, Y.& Lin,D., Perfect Algebraic Immune Functions, Advances in Cryptology–ASIACRYPT 2012, pp. 172-189, Springer, 2012.

Courtois, N.T. & Meier, W., Algebraic Attacks on Stream Ciphers with Linear Feedback, Proceedings of the 22nd International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT’03, pp. 345-359, Berlin, Heidelberg, 2003.

Eén, N.& Sorensson, N., An Extensible Sat-Solvers, Theory and Applications of Satisfiability Testing, 2919, pp. 502-518, Springer Berlin Heidelberg, 2004.

Bard, G.V., Courtois, N.T.,& Jefferson,C.,Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials Over Gf(2) Via Sat-Solvers, Cryptology ePrint Archive, Report 2007/024, 2007.

Nohl, K.,Disclosing Secret Algorithms from Hardware, Black Hat Japan, 2008.

Courtois, N.T., O’Neil, S.& Quisquater, J.-J., Practical Algebraic Attacks on the Hitag2 Stream Cipher, Proceedings of the 12th International Conference, ISC 2009, 5735, pp.167-176,Pisa, Italy, September 7-9, 2009.

Soos, M., Nohl, K. & Castelluccia, C., Extending Sat Solvers to Cryptographic Problems, Proceedings of the 12th International Conference, SAT 2009, pp. 244-257,Swansea, UK, June 30 - July 3, 2009.

Wang, Q., Peng, J., Kan, H., & Xue, X., Constructions of Cryptographically Significant Boolean Functions Using Primitive Polynomials, Information Theory, IEEE Transactions on, 56(6), pp.3048-3053, 2010.

Carlet, C., Comments on “Constructions Of Cryptographically Significant Boolean Functions Using Primitive Polynomials”. Information Theory, IEEE Transactions on Information Theory, 57(7), pp.4852-4853, 2011.

Fischer, S., Analysis of Lightweight Stream Ciphers, Master’s thesis, Ecole Polytechnique Federale De Lausanne, Lausanne, Switzerland, April 2008.

Cormen, T.H., Leiserson, C.E., Rivest, R.L. & Stein, C.,Introduction to algorithms (3rd ed.), MIT press Cambridge, 2009.

Bard, G.V.,Algebraic Cryptanalysis, Springer Publishing Company, United States, 2009.

Soos, M., Grain of salt – an automated way to test stream ciphers through SAT solvers, Workshop on Tools for Cryptanalysis, June, 2010.

Carlet, C., Boolean Functions for Cryptography and Error Correcting Codes, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, 2:257, 2010.

Townsend,W.J.& Thornton, M.A., Walsh Spectrum Computations using Cayley Graphs, Spectrum, 15(11), p.5, 2001.



  • There are currently no refbacks.

Contact Information:

ITB Journal Publisher, LPPM – ITB, 

Center for Research and Community Services (CRCS) Building Floor 7th, 
Jl. Ganesha No. 10 Bandung 40132, Indonesia,

Tel. +62-22-86010080,

Fax.: +62-22-86010051;