Key derivation on Arduino 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).
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.