Types of Cryptography for a 4-8 bit microcontroller

Question

This is more of a research question.

I was wondering what types of crypto algorithms would work best on a small 4-8 bit micro controller. I recently read a paper called Security Considerations for 802.15.4 Networks and was wondering if anyone out there can think of any other papers or has knowledge about what types of things to consider when implementing cryptography on a low-power, low-memory system.

I read a 2009 ieee paper on implementing RFID on a 4-bit micro controller, but I am looking for papers that will generally apply towards 802.11 or 802.15 standards. I will propablly be trying to hook a bunch of these controllers together, so I am looking for more of asymmetric encryption.

Answer 1

Public-key encryption on microcontrollers

Erik-oliver Blaß , Martina Zitterbart. "Towards Acceptable Public-Key Encryption in Sensor Networks". 2005.

"dsPIC DSC Asymmetric Key Embedded Encryption Library" an implementation of RSA, Diffie-Hellman, DSA, SHA-1, MD5. (Are such 16-bit microcontrollers in your range of interest?)

"Links to Embedded Crypto Implementations" lists a few implementations of RSA on 8 bit microcontrollers.

"full size" symmetric ciphers on microcontrollers

Many people implement cryptography on a microcontroller very similarly to cryptography on any other CPU -- write a program to do encryption or decryption using the same ciphers we use on any other CPU. Quite a few modern 8-bit microcontrollers have enough program memory (often called "ROM" for historical reasons, although today it's usually Flash memory) and RAM and processing speed to handle the full Advanced Encryption Standard (AES)(a)(b)(c)(d), Triple Data Encryption Standard (3DES)(a)(b), Enigma(a), RC4(a), as well as less-known algorithms such as Alexander Pukall’s PC1 (a).

symmetric ciphers designed for low RAM

Quite a few microcontrollers have 256 bytes of RAM or less. A few full-size ciphers work just fine, but ciphers like RC4 seem impossible to implement in this environment. A few symmetric ciphers seem specifically designed for this environment -- KeeLoq, TEA, XXTEA, etc.

Other cryptographic techniques for microcontrollers

A few bootloaders for embedded systems use encryption.( "USB PIC Bootloader with XTEA encryption" )

Rather than doing the encryption in the CPU itself, a few systems have an external chip that does crypto stuff. ( CryptoAuthentication, CryptoMemory, Trusted Platform Module, etc. ) Such dedicated circuitry, hard-wired to perform some calculation, often requires significantly less power than a more general-purpose CPU programmed to perform the same calculation. This way newly-introduced bugs in the software on the main CPU can't possibly leak the secret keys stored in that external chip, or introduce new flaws (new timing attacks, etc.) in the algorithm implemented in that external chip.

Answer 2

Very small platforms usually have very little RAM, because RAM uses quite a lot of space (SRAM is 6 transistors per bit, i.e. 12 gates per byte -- counting 4 transistors for a "gate"). Among asymmetric algorithms, your best bet for software with very strict memory constraints is elliptic curves (ECDH for key exchange, ECDSA for signatures -- for asymmetric encryption, you combine ECDH with a symmetric encryption algorithm; the X.93:2001 ANSI standard describe that under the name "ECIES") using Koblitz curves -- namely the K-163 curve specified in the DSA/ECDSA standard. Usually, "prime field" curves (e.g. P-256) are considered faster for software, but this is true mostly on big architectures which have an efficient multiplier (e.g. 32x32→64 bits multiplications in a single opcode). On very small architectures, binary curves are competitive, and Koblitz curves in particular are amenable to many optimizations which reduce the number of needed operations and the used RAM as well. See TinyECCK for some details, and the Guide to Elliptic Curve Cryptography.

As @fgrieu points out, this kind of embedded platform is highly susceptible to side-channel leakage, especially since power is drawn from the outside quite directly. Making an efficient implementation protected against such leakage is a very difficult challenge. A dedicated hardware circuit is somewhat easier to protect, and it turns out that ECC with binary curves is a very good fit for hardware accelerators as well.

Answer 3

Not quite on topic, but closely related: 8 bit microcontrollers with ISO 14443 "RFID" communication hardware from e.g. Infineon, NXP, STM (in alphabetical order), and several others, now abound. Some of these ICs cost $1 within a binary order of magnitude, when ordered in 6-decimal-figures quantities. They come with efficient hardware for TRNG, TDES, and sometime modexp for RSA/DSA, with AES and sometime ECC/ECDSA increasingly available. Their security against intrusion, side-channel and fault attacks is state-of-the-art, certified for some area including the crypto libraries, and rivals that of HSMs costing thousands times more. It's hard to beat these chips, the field has matured for the last 10++ years.

Back on topic: if you are really willing to start from scratch doing the crypto in software, again you'll face an uphill battle against side-channel and fault attacks. It follows that two of the safest things are hashes like SHA-1 and similar, and RSA with low public exponent or Rabin signature verification: nothing is secret, and that can be plausibly fast (with really tight coding and preferably at least an 8x8 hardware multiplier). Notice that this does not let the tag authenticate itself, only the opposite; and that moving from hash to HMAC potentially brings back the security issues.

My last link will be to some leading-edge stream ciphers at ecrypt. Gook luck.

Update: on a straight 8051 @4 Mcycles/s (that's 1 µs for 8x8 multiplication, which lasts 4 NOPs), Rabin signature verification for public modulus of b=2048 bits can be done in about 0.8 seconds [scaling as O(b^2)] with 256 bytes of XRAM [2*b bits], about 20 other internal RAM bytes, and well under 1.5 kbytes code. That includes input, output, but not the public modulus n. That's nice for authentication of another party, certificate verification (using message recovery, e.g. ISO/IEC 9796-2:2002) but any attempt to do RSA private key on similar hardware with even much smaller modulus size is doomed to be too slow to be practical, even leaving aside the issue of countermeasures. Other Public Key schemes must be researched.

Answer 4

You asked only about the choice of cryptographic algorithm, and the choice of primitives is indeed important, but the design of the surrounding protocol can also have a significant impact on performance. I recommend that you take a look at TinySec and MiniSec to see two carefully designed schemes for secure communication on 8-bit microprocessors.

Mark Luk, Ghita Mezzour, Adrian Perrig, Virgil Gligor. MiniSec: A Secure Sensor Network Communication Architecture. IPSN 2007. MiniSec project web page.

Chris Karlof, Naveen Sastry, David Wagner. TinySec: A Link Layer Security Architecture for Wireless Sensor Networks. ACM SenSys 2004.

Answer 5

For symmetric-key cryptography: Skipjack turns out to be great for these applications. It requires very little RAM (it has no complex key schedule, and no key expansion process), it can be made efficient on 8-bit platforms, and it is unpatented. Give it a try.

Public-key cryptography is tougher. Take a look at elliptic curve cryptography. See also recent research on LWE cryptosystems for another contender that is within the capabilities of a RFID tag (though I don't know how it will meet your particular needs).

In general, I recommend you implement a few candidate ciphers, benchmark them, and see what works best on your platform.

Answer 6

8-bit designs typically are VERY cost sensitive and regular encryption/decryption techniques are often not cost sensitive enough...e.g. could double the cost of the product. The question you should ask yourself, is how much encryption is enough for your application. I came up with an algorithm with this in mind. First, consider this random number generator algorithm.

Starts with 2 random variables, x and y, with s (start seed) and this per byte algorithm...

y1 = y + s
x1 = x + y

y starts off as 0 and x starts off as an odd integer. x is the random byte output.

If you have 2 such random number generators and encrypt a byte using:

e = b^r1 + r2

Decryption is done on the other side by using the same random numbe generators and using:

d = (b - r2) ^ r1

The initial s and y values (32 bits total) can be done using a simple diffie helman type algorithm.

Note that this algorithm will get you 255 unique encryption values. After this, y is set to zero again, the x and s values have to be set to new values. This could be done by carefully picking unique starting values at the end of the 255 generation, or you could use another random number generator.

The diffie-helman initialization is slow, but the per byte calculations after that is only 6 operations per byte transmitted/received if you only use the 2 random number generators.....which is very fast for an encryption algorithm and it doesn't require a multiply.

I'd probably give this more thought, but it's got a good idea at it's heart. You could also do the diffie-helman step again once every 5 minutes to increase security.

I call this algorithm the Small Device Embedded Security algorithm or SDES.