Lightweight Crypto, Heavyweight Protection

Logic puzzles, brain teasers and mathematical riddles fascinated me throughout my childhood, so I feel lucky that I ended up with a career that never lacks for mathematical challenges. Part of my job at the National Institute of Standards and Technology (NIST) involves reviewing the cryptographic algorithms developed to protect our information and identifying possible weaknesses that make them less secure. Searching for these weaknesses reminds me of the process of solving hard mathematical riddles. Although it can sometimes be frustrating, I find it very rewarding.

Over the last couple of years, my focus has been on cryptographic algorithms that are designed to increase the security of small devices like embedded microcontrollers, radio-frequency identification (RFID) tags or sensors. These now ubiquitous devices, found in home automation, smart city technologies, digital assistants and health-care applications, are constrained in terms of their processing power and storage capabilities. Since these devices usually collect, store and process so much important information, users are concerned about their privacy and security. Moreover, due to the lack of suitable cryptographic solutions that perform well in these devices, most of these products do not offer sufficient protection or use proprietary, nonstandard security algorithms that can be reverse-engineered and broken in practice.

New Cryptographic Algorithms Needed

Over the last decade there has been significant research on designing new encryption algorithms optimized for constrained devices. These algorithms are commonly referred to as “lightweight” cryptography algorithms. “Lightweight” does not mean that the algorithms are not secure, but rather that they are efficient to implement and perform well in constrained devices. When we think about the weight of an algorithm, we look at the properties of its implementation in hardware or software. For hardware implementations where the encryption is hardwired into the device, the properties are the physical area needed for a circuit to implement the algorithm, the amount of time it takes to obtain the circuit’s output, and the amount of power needed. For software implementations, the properties are the amount of memory used during evaluation of the algorithm, the size of the compiled code, and the amount of input processed per time unit.

The target metrics and the optimal tradeoff between performance, cost and security usually depend on the technology and applications. In anti-counterfeiting applications, RFID tags with a small amount of memory are commonly used to identify and track retail products. Here, hardware-oriented algorithms that can be implemented in a small area are desired. In smart home appliances with low-end processing units, software-oriented algorithms that consume a small amount of memory are preferred.

After analyzing the performance of current NIST standards on constrained devices, the institute’s Cryptographic Technology Group (CTG) has decided that there is indeed a need for a new lightweight cryptography standard that simultaneously protects the confidentiality and proves the authenticity of the message. To select the new lightweight cryptography standard, CTG decided to organize an international cryptographic competition.

Cryptography Competitions

International cryptography competitions provide an open and transparent process to standardize algorithms. The competitions, especially the ones organized by NIST, are highly visible and bring the cryptography research community, industry stakeholders and other standards-developing organizations together to evaluate and select widely accepted, state-of-the-art algorithms. Cryptographic competitions also attract many graduate students searching for interesting research problems to work on. Due to this interest, the competitions are believed to help the research community gain broader understanding of the field, as numerous research papers and even Ph.D. theses are published as the result of the process.

In 1997, NIST initiated a public competition to develop a replacement for the Data Encryption Standard, which was initially adopted in 1977, and received 15 international submissions. In 2000, the submission Rijndael, designed by Joan Daemen and Vincent Rijmen, was selected as the winner of the competition and dubbed the Advanced Encryption Standard (AES). According to a study commissioned by NIST, the economic impact of the development of AES has been more than $250 billion since its selection. In 2007, NIST announced another competition to select a new hash function standard named SHA-3. This competition received 64 submissions, and in 2012, NIST selected Keccak as the new hash function standard.

Setting the Standard for Lightweight Cryptography

In 2018, NIST announced the lightweight cryptography competition to solicit, evaluate and standardize algorithms that are suitable for constrained environments. The announcement in the Federal Register specified the technical requirements for the target cryptographic algorithm and explained the evaluation criteria and a tentative timeline.

The competition received 57 submission packages from 25 different countries, where each package included algorithm specifications, intellectual property statements and portable reference software implementations. We were happy and surprised to receive such a large number of submissions. Similar to other competitions, we planned for having multiple rounds, where in each round the field is narrowed to focus on the most promising candidates. We advanced 32 of these candidates to the second round based on their security properties. As the next step, we plan to select around eight finalists that perform significantly better than current NIST standards in software and hardware. After one more year of extensive analysis and performance benchmarking, we plan to select the winner and add a new crypto standard to NIST’s portfolio.

Although being in the review committee of these competitions is challenging, it also provides an amazing opportunity to learn and exchange new ideas, work as a team with the cryptographic research community with the goal of selecting a secure algorithm. I look forward to working on more of these mathematical challenges and helping to improve cryptographic standards in the future.