# Types of Cryptography for a 4-8 bit microcontroller

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.

-
Is it this paper? No, it is from 2009. Could you link your 2005 paper, if it is available online? –  Paŭlo Ebermann Sep 1 '11 at 0:37
You are correct, that is the one I was mentioning, I was getting it confused with this paper: cosic.esat.kuleuven.be/publications/article-614.pdf –  Jim Sep 1 '11 at 0:53
Perhaps, a direct link for Security Considerations for 802.15.4 Networks –  fgrieu Sep 1 '11 at 5:29
I recommend you start by telling us what kind of cryptographic primitives you need. Public-key or symmetric key? A MAC? A PRF? Encryption? Digital signature? Key exchange? SOmething else? –  D.W. Sep 1 '11 at 20:18
Public Key, the nodes in the network need to communicate with other nodes, and will have to do an adhoc network topology, so I would assume that public key would be best for this atmosphere. –  Jim Sep 1 '11 at 20:35

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.

-
The first paper that you linked was exceptionally good and is more of what I was leaning towards. Thank you! Very helpful and constructive. It will take me some time to read through all of your links. –  Jim Sep 1 '11 at 17:38
I definitely would not recommend Enigma, RC4, PC1, or Keeloq. I'm a bit skeptical about whether TEA or XXTEA will be efficient on a 4-bit or 8-bit processor; they were designed for a 32-bit processor. –  D.W. Sep 1 '11 at 20:28
I don't plan on it. I think that ECC is going to be the way that I am going, and the first paper and some of those posted by Thomas are the best way to go. –  Jim Sep 1 '11 at 20:33

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.

-
So ECC's are the way to go for small systems, I was reading a paper that state that bit for bit it is better than RSA, I will have to read into them more. Thank you for the links! –  Jim Sep 1 '11 at 17:36

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.

-
I don't think I will be re-inventing the wheel, but I was looking for good encryptions that have been proven for small systems, while maintaining security, how I do like your notes on side-channel and fault attacks, as I had no idea about those prior. –  Jim Sep 1 '11 at 17:45

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.

-
Wow, these look relevant, let me read through and let you know. –  Jim Sep 1 '11 at 20:37
+1: these look useful and relevant. Thank you. –  David Cary Sep 2 '11 at 3:51

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.

-

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.

-
Hey, an algorithm I hadn't heard of. Where is peer-reviewed literature about that algorithm? –  Gilles Aug 16 '13 at 13:57
Why do you mention diffie-hellman? Your code doesn't have anything in common with DH. DH takes at least million cycles. If you can afford DH, you can afford a sane symmetric algo. There is also the whole field of lightweight crypto that attempts to construct cheap but secure crypto. Unlike your system which seems about as secure as caesar encryption. –  CodesInChaos Aug 16 '13 at 14:37
Well, I call this algorithm "Pseudo Random Number Generator" because that's what it is. –  e-sushi Nov 8 '13 at 21:00
Two statements "The initial s and y values (32 bits total) can be done using a simple diffie helman type algorithm." and "y starts off as 0" conflict with each other. In either case, the seed is either 16 bits or 32 bits, which is not sufficient, even with otherwise secure algorithm. This algorithm, however, is broken with a few known plaintext and ciphertext bytes (resulting in simple linear equations which can be solved by hand in matter of minutes). Thus, the algorithm is not a good idea. –  user4982 Jan 6 at 10:57