8
$\begingroup$

The ATmega2560 is slow - it's a single core, 16MHz 8-bit AVR. Despite that, I need to use some encryption on it, and since it is limited to a few blocks, AES-256 can be used.

However, the key derivation is a problem. A computer can easily do a PBKDF2-HMAC-SHA256 with a million iterations in less than a few seconds. The Arduino struggles to perform 100 iterations in 4 seconds (to be exact, the time required with the implementation I use is 4.37s); that also applies when optimizations are enabled.

The current NIST recommendation is to use at least 10,000 iterations, in which case PBKDF2 may not be a good fit for my case.

When it comes to Key Derivation Functions, are there any solutions that are cryptographically safe for low power devices, and more generally IoT devices?

Since I cannot add comments I'll edit to answer them:

  • I'm not sure what is meant by "if the key derivation is performed only once", so to be more precise: the key derivation is performed only once, yes, but the devices shouldn't block for more than a few seconds before it can actually be used. 4 seconds is not a lot, but I sure don't want to go over that.
  • The key can - and will - be created beforehand, but it still needs to be computed each time the device is powered on. It would make absolutely no sense to store a key in plaintext.
  • The device is safe from attackers while it is being used, however it may not be safe while powered off (it is meant to be plugged in, unlocked, have one or two interactions with it and powered off). I guess a similar device would be the "Mooltipass Hardware Password Keeper", except that I don't have access to smart cards nor do I intend to use it as a keyboard while an operating system is up and running. Unless I missed something though, smart cards aren't easily accessible (the SLE4442 is NOT read protected).
Improve this question
$\endgroup$
7
  • $\begingroup$ Re. " It would make absolutely no sense to store a key in plaintext." Why? That's common in embedded. It's not plain text per se, it's a semi-opaque HEX file that <<0.1% of Arduino programmers will be able to read back (if any at all) when you set the lock bits and remove the bootloader. $\endgroup$
    – Paul Uszak
    Sep 10, 2019 at 0:51
  • 2
    $\begingroup$ The lockbits are far from being a good protection, many Chinese companies have processes to extract the data from the microcontrollers, and while you may argue that "do you really think people are going to care enough to do that?" I'd say that security is never well done if you begin by leaving holes everywhere. $\endgroup$
    – Dash
    Sep 10, 2019 at 1:29
  • 1
    $\begingroup$ @PaulUszak Seriously? Please do not suggest that anyone store passwords in plaintext. Just because it's common does not mean that it's good. Lots of people don't sanitize parameters either and SQLi is common, but that doesn't mean it's good or that any web dev worth their salt would recommend allowing it. $\endgroup$
    – forest ♦
    Sep 10, 2019 at 7:24
  • $\begingroup$ It could be the very last option in case all other options have been crossed out. Using a key that is not well protected can be better than having no encryption whatsoever. Of course, you'd at least try and use a per-device key in that case, e.g. deriving that same key from a master key using the ID of the device. Recommending it without mentioning that this is a last resort is probably not a good idea, I certainly agree with that. $\endgroup$
    – Maarten Bodewes ♦
    Sep 10, 2019 at 10:30
  • 1
    $\begingroup$ @forest Probably. We've been described the system, but not the use cases or threat model, so in the end what's best is still guesswork. $\endgroup$
    – Maarten Bodewes ♦
    Sep 10, 2019 at 11:37

2 Answers 2

Reset to default
5
$\begingroup$

Generally you should try and avoid deriving keys from passwords on embedded devices or passwords. There are a few strategies that could be used.

First of all, you can try and design a system that doesn't use a password. Passwords are very tricky to secure, and password hashing algorithms (or, in this case, rather Password Based Key Derivation Function or PBKDF - need to be constantly updates / reconfigured to deal with the advance in computing power. Yes, that's not easy, but opting out would be preferable to haphazard solutions. For instance, you could input a key from an external device instead.

Second, you can try and use a password that's so strong that it doesn't require any PBKDF. Basically, you can encode a fully randomized key in such a way that you can enter it as if it is a password. The key would be 80 bits or higher of random data. The key can then be stored in e.g. a password manager on your phone so that the user doesn't have to remember it. The "password" is now protected by a more capable device. Instead of performing a PBKDF over the password you could now perform a Key Based Key Derivation Function - that doesn't require a work factor - such as HKDF or a decode function followed by a KBKDF that uses AES in counter mode. Users will probably have to store the password in a password manager, as it would be too complex to remember.

Thirdly you can require an external device to perform most of the work of a PBKDF, and then finish the work on the device. In that case your device may have to do only one step of hashing. Instead of the password the device will receive the intermediate result and then proceeds by performing a single one-way function (such as a hash) over it. You could for instance perform PBKDF2 on a smart phone and then continue with a hash on the embedded device. Some password hash functions such as Catena in the password hashing competition deliberately contained ways of performing such a split between client (the phone in this story) and the server (the embedded device). This solution requires that the device and connection to the embedded device is secure; it shifts the burden largely from the device to the surrounding entities.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Sorry about method #1 but it needs to be in there for future readers. And sorry to CodesInChaos for stealing his thunder in method #3. $\endgroup$
    – Maarten Bodewes ♦
    Sep 10, 2019 at 10:21
  • $\begingroup$ Don't worry, I perfectly agree with method #1, it's just that getting read-protected smartcards or similar devices is pretty hard. Second method is great as it answers my other question, on the same topic, I would, however, rather remember it (it's not that hard anyway). Third method implies that the phone is safe though, as a man-in-the-middle on it could easily replay the computed hash. $\endgroup$
    – Dash
    Sep 10, 2019 at 10:35
  • $\begingroup$ Usually passwords only have an entropy of about 47 bits on average. Remembering a password with 80 bits of entropy is exceedingly hard. And usually it is not the only password that needs to be remembered. $\endgroup$
    – Maarten Bodewes ♦
    Sep 10, 2019 at 11:34
  • $\begingroup$ Though, in the current case, I will be the sole user of the device. If the following calculation is correct, that is, log2(14^24) (charset of 14 characters, length of 24), then it makes at best an entropy of 91 bits (one could argue that it would be lower since the password isn't entirely random). Remembering a 24 character password with the charset "123456789ABCD" isn't too difficult. $\endgroup$
    – Dash
    Sep 10, 2019 at 12:37
  • $\begingroup$ As sole user you can do what you want, but I would like to point out that humans are rather incapable of choosing ones that have high entropy, and most human minds are really more failure prone than yours. $\endgroup$
    – Maarten Bodewes ♦
    Sep 10, 2019 at 13:05
4
$\begingroup$

There aren't many KDFs that will be faster on an AVR than PBKDF2. In your case, it's likely that the only thing you can do is find a hash which can be implemented efficiently on an ATmega2560, and implement it with as many optimizations as possible. A highly-optimized implementation of a hash algorithm is likely to improve speed significantly. That's really all you can do: Find/write a very fast AVR implementation.

If you find that PBKDF2-HMAC isn't giving you optimal performance, you could try to use a similar KDF such as S2K of the OpenPGP standard. It works by concatenating the password and salt and feeding that data into some chosen hash function. It is fed, repeating, until the configured number of bytes have been processed. See RFC 4880 § 3.7.1.3 for the specifications. It does not require any optimizations beyond optimizing the hash itself, unlike PBKDF2-HMAC. Benchmark it and see if it's good for you.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.