Anelok: using NaCl

Werner Almesberger werner at almesberger.net
Tue Apr 28 16:59:02 UTC 2015


I implemented a first proof of concept prototype of encryption, based
on NaCl's crypto_box [1] using the TweetNaCl implementation [2].

The this proof-of-concept is quite crude: there is only one reader,
keys and encrypted data and kept in memory forever, the account
database is linked into the code, and the only way to create or edit
accounts is by running a scary collection of programs on the Linux
host.


Code size
---------

Nevertheless, this exercises more than half of the crypto system and
provides a realistic workload. Code size comparison:

	   text    data     bss     dec     hex filename
Base	  24676    1416    4200   30292    7654 anelok-2014.elf
Dynamic	  25484    1200    4200   30884    78a4 anelok-2014.elf
Decrypt	  29180    1200    4200   34580    8714 anelok-2014.elf

"Base" is the version before all the crypto work, where the account
database was not encrypted and just hard-coded.

"Dynamic" changes various APIs to work with account information that
is not available at build time. As a consequence of one of the API
changes, the account database could now be "const" and thus moved
from "data" to "text".

"Decrypt" then adds TweetNaCl and decryption. The code size increase
is quite moderate, which means that we still have a lot of room for
fun things.

I don't quite trust the BSS figure, though. It should at least change,
and it should be larger in the decrypting version since it adds a few
buffers.


Run time
--------

When I had it all running with Anelok using crypto_box_open, it was
disappointingly slow. Even the simulator running on my PC was
extremely sluggish.

The reason for this is that the whole decryption had to be performed
for every access to a record, i.e., each time the list of accounts
is redrawn (which happens a lot when sliding) and also for moving up
and down in the list (there should be some room for optimization).

Fortunately, NaCl can divide the decryption task into two parts: the
computationally expensive key agreement and then the much lighter
decryption of the actual data. The key agreement is needed only once,
when beginning to access a set of encrypted records while the
decryption is needed each time a record is accessed.

This markedly improved performance. In the simulator, the delay is
imperceptible and on the real device there is a short wait of about
1-2 seconds when entering the account selection list, but response
is smooth afterwards.


Improvements
------------

First of all, there are a few small optimizations I can make that
should somewhat reduce the overhead when scrolling in lists. There
is less I can do about the key agreement.

However, there is muNaCl [3], a version of NaCl optimized for small
MCUs, with work for the Cortex M0 under way. That should bring down
the number of CPU cycles by a fair bit.

In any case, the speed is already quite acceptable. But the idea of
just trying various keys until one fits (see part 2 of the crypto
discussion [4]) probably doesn't make sense given how expensive key
agreement is.

The security of my implementation is abysmal, with far too much
sensitive information sitting around in memory for too long. But
fixing that can wait until Anelok sees more widespread use.


Changes to the build process
----------------------------

The build process in fw/ now depends on some tools from crypter/.
And the simulator in sim/ needs generated files from fw/. So the
entire sequence is now:

% make -C anelok/crypter
% make -C anelok/fw
% make -C anelok/sim

If you have compiled these things before, a "make clean" may be
needed because account.c has moved and old dependencies may confuse
vpath.

- Werner

[1] http://nacl.cr.yp.to/box.html
[2] http://tweetnacl.cr.yp.to/
[3] http://munacl.cryptojedi.org/index.shtml
[4] http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010851.html



More information about the discussion mailing list


interactive