access icon free Randomised multi-modulo residue number system architecture for double-and-add to prevent power analysis side channel attacks

© The Institution of Engineering and Technology
Received 25/11/2012, Accepted 12/03/2013, Revised 12/03/2013, Published

Security in embedded systems is of critical importance since most of our secure transactions are currently made via credit cards or mobile phones. Power analysis-based side channel attacks have been proved as the most successful attacks on embedded systems to retrieve secret keys, allowing impersonation and theft. State-of-the-art solutions for such attacks on public key cryptographic algorithms, such as elliptic curve cryptography, mostly in software, hinder performance and repeatedly attacked using improved techniques. To protect these public key ciphers from both simple power analysis and differential power analysis, as a hardware solution, we propose to take advantage of the inherent parallelisation capability in multi-modulo residue number systems (RNS) architectures to obfuscate the secure information. Random selection of moduli is proposed to randomly choose the moduli sets for each key bit operation. This solution allows us to prevent power analysis, although still providing all the benefits of RNS. In this study, the authors show that differential power analysis, cross correlation analysis and correlation power analysis for a simple binary double-and-add operation are thwarted using their solution.

Inspec keywords: data privacy; correlation methods; randomised algorithms; embedded systems; public key cryptography; residue number systems

Other keywords: binary double-and-add operation; mobile phone; secret key retrieval; cross correlation power analysis; randomised multimodulo residue number system architecture; public key cipher; credit card; public key cryptographic algorithm; power analysis side channel attack prevention; embedded security system; elliptic curve cryptography; RNS; differential power analysis

Subjects: Data security; Digital arithmetic methods; Cryptography theory; Cryptography

References

    1. 1)
      • 10. Schinianakis, D., Kakarountas, A., Stouraitis, T.: ‘A new approach to elliptic curve cryptography: an RNS architecture’. MELECON, 2006.
    2. 2)
      • 17. Lim, Z., Phillips, B., Liebelt, M.: ‘Elliptic curve digital signature algorithm over GF(p) on a residue number system enabled microprocessor’. TENCON, 2009.
    3. 3)
      • 14. Izumi, M., Ikegami, J., Sakiyama, K., Ohta, K.: ‘Improved countermeasure against address-bit DPA for ECC scalar multiplication’. DATE, March 2010, pp. 981–984.
    4. 4)
      • 25. Jun, B., Kocher, P.: ‘The Intel random number generator’ (White Paper Prepared for Intel Corporation, Cryptography Research Inc., 1999). Available at http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf.
    5. 5)
      • 13. Zhou, Y., Feng, D.: ‘Side-channel attacks: ten years after its publication and the impacts on cryptographic module security testing’. 2005.
    6. 6)
      • 2. Messerges, T.S., Dabbish, E.A., Sloan, R.H.: ‘Investigations of power analysis attacks on smartcards’. WOST, 1999, pp. 17–30.
    7. 7)
      • 15. Itoh, K., Izu, T., Takenaka, M.: ‘A practical countermeasure against address-bit differential power analysis’. CHES, 2003, pp. 382–396.
    8. 8)
      • 27. Ambrose, J.A., Ragel, R.G., Parameswaran, S.: ‘RIJID: random code injection to mask power analysis based side channel attacks’. DAC, 2007, pp. 489–492.
    9. 9)
      • 28. Brier, E., Clavier, C., Olivier, F.: ‘Correlation power analysis with a leakage model’. CHES, 2004, pp. 16–29.
    10. 10)
      • 12. Paliouras, V., Stouraitis, T.: ‘Systematic design of multi-modulus/multi-function residue number system processors’. ISCAS, 1994.
    11. 11)
      • 9. Koschuch, M., Lechner, J., Weitzer, A., et al: ‘Hardware/software co-design of elliptic curve cryptography on an 8051 microcontroller’. CHES, 2006.
    12. 12)
      • 19. Ambrose, J.A., Pettenghi, H., Sousa, L.: ‘DARNS: a randomized multi-modulo RNS architecture for double-and-add in ECC to prevent power analysis side channel attacks’. ASP-DAC, 2013(accepted to be published).
    13. 13)
      • 18. Oswald, E., Aigner, M.: ‘Randomized addition-subtraction chains as a countermeasure against power attacks’. CHES, 2001.
    14. 14)
      • 5. Coron, J.-S.: ‘Resistance against differential power analysis for elliptic curve cryptosystems’. CHES, 1999.
    15. 15)
      • 23. Szabo, N.S., Tanaka, R.I.: ‘Residue arithmetic and its applications to computer technology’ (McGraw-Hill, New York, USA, 1967).
    16. 16)
      • 3. Afreen, R., Mehrotra, S.C.: ‘A review on elliptic curve cryptography for embedded systems’. CoRR, 2011.
    17. 17)
      • 24. Kelsey, J., Schneier, B., Wagner, D., Hall, C.: ‘Cryptanalytic attacks on pseudorandom number generators’. Fifth International Workshop Proc. Fast Software Encryption, 1998, pp. 168–188.
    18. 18)
      • 1. Kocher, P., Jaffe, J., Jun, B.: ‘Differential power analysis’. CRYPTO, 1999, pp. 388–397.
    19. 19)
      • 11. Pettenghi, H., Sousa, L., Ambrose, J.: ‘Efficient implementation of multi-moduli architectures for binary-to-rns conversion’. 2012 17th Asia and South Pacific Design Automation Conf. (ASP-DAC), 2012, pp. 819–824.
    20. 20)
      • 30. Alia, G., Martinelli, E.: ‘Designing multioperand modular adders’, Electron. Lett., 1996, 32, (1), pp. 22–23 (doi: 10.1049/el:19960026).
    21. 21)
      • 21. Gierlichs, B., Batina, L., Tuyls, P.: ‘Mutual information analysis – a universal differential side-channel attack’. 2007.
    22. 22)
      • 20. Gebotys, C.H., White, B.A.: ‘Methodology for attack on a Java-based PDA’. CODES + ISSS, 2006.
    23. 23)
      • 6. Okeya, K., Sakurai, K.: ‘Power analysis breaks elliptic curve cryptosystems even secure against the timing attack’. INDOCRYPT, 2000.
    24. 24)
      • 8. Sakai, Y., Sakurai, K.: ‘Simple power analysis on fast modular reduction with generalized Mersenne prime for elliptic curve cryptosystems’, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2006, 89-A, pp. 231–237 (doi: 10.1093/ietfec/e89-a.1.231).
    25. 25)
      • 31. Parhami, B.: ‘Computer arithmetic: algorithms and hardware designs’ ser The Oxford Series in Electrical and Computer Engineering Series. (Oxford University Press, 2009). Available at http://books.google.pt/books?id=tEo_AQAAIAAJ.
    26. 26)
      • 26. Rechberger, C., Oswald, E.: ‘Practical template attacks’. WISA, 2004, vol. 3325, pp. 443–457.
    27. 27)
      • 7. Miyaji, A., Ono, T., Cohen, H.: ‘Efficient elliptic curve exponentiation’. IICSC, 1997, pp. 282–290.
    28. 28)
      • 4. Oswald, E.: ‘Enhancing simple power-analysis attacks on elliptic curve cryptosystems’. CHES, 2002.
    29. 29)
      • 22. Itoh, K., Izu, T., Takenaka, M.: ‘Address-bit differential power analysis of cryptographic schemes OK-ECDH and OK-ECDSA’. CHES, 2003, pp. 129–143.
    30. 30)
      • 29. Pettenghi, H., Chaves, R., Sousa, L.: ‘RNS reverse converters for moduli sets with dynamic ranges up to (8n + 1)-bit’, IEEE Trans. Circuits Syst. I, Regul. Pap., 99, pp. 1–14.
    31. 31)
      • 16. Bajard, J., Duquesne, S., Ercegovac, M.: ‘Combining leak resistant arithmetic for elliptic curves defined over Fp and RNS representation’. IACR Eprint archive, 2010.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2012.0367
Loading

Related content

content/journals/10.1049/iet-cds.2012.0367
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading