Anelok: first try at crypto: randomness (3/3)

Werner Almesberger werner at almesberger.net
Sun Apr 19 04:19:40 UTC 2015


Now we get to the fun part: randomness.


Entropy users
-------------

An obvious place where Anelok requires randomness is for the generation
of record keys.

We may also want to provide an initialization vector (IV [1]) for the
payload encryption, but I haven't worked out an attack scenario yet
where not having an IV would significantly help the attacker to
accomplish anything meaningful. Suggestions ?

Note that the IV doesn't necessarily require randomness. Maybe we could
generate it deterministically from, say, the encrypted keys. This may
be somewhat similar to what NaCl's crypto_box [2] does with the help of
a nonce [3] (haven't looked at the details yet).

Last but not least, public keys used by devices (i.e., readers and
writers) require an excellent entropy source.

Anelok also needs random numbers for a few other things, but these are
not directly related to the encryption of account records.


Random number generation
------------------------

The problem with randomness is that it is an expensive good, especially
in small embedded systems like Anelok. And it is also a fragile thing.
Therefore, we should try to use randomness as sparingly and efficiently
as possible.

The fragility comes from the risk of operating entropy (randomness)
sources in a way that makes them become a lot less random than they
should be.

Anelok has the following general sources of randomness:

- a true random number generator (TRNG [4]) in the radio chip
  (not available when rfkill is applied),

- any entropy we can obtain by measuring noise in the MCU,

- any entropy we can extract from user input (touch sensor), and

- we may have an "entropy assist" file full of hopefully good random
  bits.

By mixing entropy from multiples independent sources, one can improve
the quality of the resulting randomness. This is especially true if
some sources fail to provide the expected amount of entropy, be it by
accident or due to manipulation.


Entropy of content
------------------

A very nice approach for obtaining entropy "for free" is mentioned on
page 8 of [5]: since the item we are encrypting also contains some
entropy (if there was no entropy in there, the attacker could already
predict the content), why not put it to good use ?

However, we have to be careful with this. E.g., if the secret we're
trying to protect is an ATM PIN and we just use a hash of the plaintext
for our IV without adding _any_ randomness from another source, then an
attacker who can gain access to the encrypted record and who has a bit
of additional knowledge of (or is good at guessing) what else is in
that record could just try to brute-force the PIN as follows:

	for (i = 0; i != 1000000; i++) {
		sprintf(buf, "Name: FooCard\nPW: %06d\n", i);
		if (hash(buf) == IV)
			gotcha(i);
	}

The trick here is that brute forcing an ATM PIN is usually difficult
because ATMs limit the number and/or rate of attempts. But exposing
the information trough a hash would remove the penalty on failed
attempts, and thus make brute-forcing extremely easy.

For the record key, the situation would be similar. Just instead of
simply  (hash(buf) == IV)  the comparison would be
(Esym(hash(buf), buf) == Encrypted)

Still way too easy for anything as weak as an ATM key.


Reuse of entropy
----------------

Another delicate topic. Attacks against reused keys that should have
been one-time-pads are legion, and there are plenty of more subtle
variations of the theme.

However, when editing a record, we could certainly mix any entropy the
old record had in its IV and its record key into our entropy pool.

Also, record key reuse seems to be safe as long as the authorized
readership stays the same.


Hmm, we're at part 3 of 3 now, but I think the "for further study" part
deserves another mail, even though it won't be very long.

- Werner

[1] http://en.wikipedia.org/wiki/Initialization_vector
[2] http://nacl.cr.yp.to/box.html
[3] http://en.wikipedia.org/wiki/Cryptographic_nonce
[4] http://en.wikipedia.org/wiki/Random_number_generation#.22True.22_random_numbers_vs._pseudo-random_numbers
[5] http://ed25519.cr.yp.to/ed25519-20110926.pdf



More information about the discussion mailing list


interactive