Werner Almesberger
2016-05-20 13:48:13 UTC
So far, the account database format only supported one reader per
record and the tools for creating the database used only a single
key pair, which kinda defeats the purpose of public-key cryptography.
After some hands-on experience with NaCl
https://nacl.cr.yp.to/index.html
and studying Dan Bernstein's paper on how it all works under the hood
http://cr.yp.to/highspeed/naclcrypto-20090310.pdf
I felt confident to take the next step and to implement multi-reader
encryption.
This required a change of the database format and the introduction of
encrypted per-record keys. You may remember this diagram
http://downloads.qi-hardware.com/people/werner/anelok/tmp/crypto-accreg-20150420.pdf
from these threads:
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010850.html
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010851.html
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010852.html
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010854.html
The updated version is quite similar:
http://downloads.qi-hardware.com/people/werner/anelok/tmp/crypto-accreg-20160520.pdf
https://gitlab.com/anelok/anelok/blob/master/doc/crypto/accrec.fig
The main changes are that I removed the key derivation function (KDF),
the initialization vector (IV) is now a nonce, and involving hashes
in the generation of random numbers is less encouraged than before.
The KDF simply wasn't necessary: the Curve25519 key agreement produces
a 32 byte key, which is exactly the size of the secret key for the
symmetric encryption used later on.
The nonce has specific requirements: it must be unique for each message
that uses the same secret key. The reason for this is that messages are
encrypted and decrypted by generating a stream of pseudo-random bits
defined by nonce and secret key, and xor-ing the message with that
stream. E.g., with S = stream(nonce, key)
Encrypt message M: C = M xor S
Decrypt C: M = C xor S
Now, if a given key and nonce are used to encrypt a message M1 and
the same key and nonce were used again to encrypt a message M2, the
result would be
C1 = M1 xor S
C2 = M2 xor S
and someone who notices that we've reused the nonce (which is trivial
to detect) could thus calculate
C1 xor C2 = (M1 xor S) xor (M2 xor S) = M1 xor M2
The effect is nicely illustrated here:
http://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse/108#108
(In our case, we have much less redundancy than in an image, so it
would be less bad, but still crazily insecure.)
However, the nonce only has to be unique per key, not entirely random.
So we can use the same nonce with different keys and we can recycle a
nonce by making a simple change to it, such as considering it as one
big number and incrementing it.
The diagram shows safe reuse of the nonce: once for encrypting the
record key, and then for encrypting the actual content.
Last but not least, I've reduced the use of hash values for assisting
random number generation. The reason is that records may have low
entropy, and exposing the hash would allow for efficient attacks.
The entropy in a record comes mainly from the passwords. Systems that
rate-limit attacks (e.g., bank card PINs where the card is blocked
after three failed attempts) don't need passwords with a lot of
randomness to be reasonably secure.
But if someone could get such a record from an Anelok account database
and run a "fast" attack against it, such "weak" passwords could be
broken easily, which is why we have to avoid doing anything that would
enable such "fast" attacks.
I'm not sure yet if hashes should be mixed into "random" numbers at
all.
Pro: if the random number generator (RNG) is weak, we get better
entropy.
Contra: especially where the nonce is concerned, we don't need a lot
of entropy anyway, and mixing a hash with a weak random number could
result in "fast" attacks against the hash becoming feasible.
Next: record format and encryption algorithm.
- Werner
_______________________________________________
Qi Hardware Discussion List
Mail to list (members only): ***@lists.en.qi-hardware.com
Subscribe or Unsubscribe: http://lists.en.qi-hardware.com/mailma
record and the tools for creating the database used only a single
key pair, which kinda defeats the purpose of public-key cryptography.
After some hands-on experience with NaCl
https://nacl.cr.yp.to/index.html
and studying Dan Bernstein's paper on how it all works under the hood
http://cr.yp.to/highspeed/naclcrypto-20090310.pdf
I felt confident to take the next step and to implement multi-reader
encryption.
This required a change of the database format and the introduction of
encrypted per-record keys. You may remember this diagram
http://downloads.qi-hardware.com/people/werner/anelok/tmp/crypto-accreg-20150420.pdf
from these threads:
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010850.html
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010851.html
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010852.html
http://lists.en.qi-hardware.com/pipermail/discussion/2015-April/010854.html
The updated version is quite similar:
http://downloads.qi-hardware.com/people/werner/anelok/tmp/crypto-accreg-20160520.pdf
https://gitlab.com/anelok/anelok/blob/master/doc/crypto/accrec.fig
The main changes are that I removed the key derivation function (KDF),
the initialization vector (IV) is now a nonce, and involving hashes
in the generation of random numbers is less encouraged than before.
The KDF simply wasn't necessary: the Curve25519 key agreement produces
a 32 byte key, which is exactly the size of the secret key for the
symmetric encryption used later on.
The nonce has specific requirements: it must be unique for each message
that uses the same secret key. The reason for this is that messages are
encrypted and decrypted by generating a stream of pseudo-random bits
defined by nonce and secret key, and xor-ing the message with that
stream. E.g., with S = stream(nonce, key)
Encrypt message M: C = M xor S
Decrypt C: M = C xor S
Now, if a given key and nonce are used to encrypt a message M1 and
the same key and nonce were used again to encrypt a message M2, the
result would be
C1 = M1 xor S
C2 = M2 xor S
and someone who notices that we've reused the nonce (which is trivial
to detect) could thus calculate
C1 xor C2 = (M1 xor S) xor (M2 xor S) = M1 xor M2
The effect is nicely illustrated here:
http://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse/108#108
(In our case, we have much less redundancy than in an image, so it
would be less bad, but still crazily insecure.)
However, the nonce only has to be unique per key, not entirely random.
So we can use the same nonce with different keys and we can recycle a
nonce by making a simple change to it, such as considering it as one
big number and incrementing it.
The diagram shows safe reuse of the nonce: once for encrypting the
record key, and then for encrypting the actual content.
Last but not least, I've reduced the use of hash values for assisting
random number generation. The reason is that records may have low
entropy, and exposing the hash would allow for efficient attacks.
The entropy in a record comes mainly from the passwords. Systems that
rate-limit attacks (e.g., bank card PINs where the card is blocked
after three failed attempts) don't need passwords with a lot of
randomness to be reasonably secure.
But if someone could get such a record from an Anelok account database
and run a "fast" attack against it, such "weak" passwords could be
broken easily, which is why we have to avoid doing anything that would
enable such "fast" attacks.
I'm not sure yet if hashes should be mixed into "random" numbers at
all.
Pro: if the random number generator (RNG) is weak, we get better
entropy.
Contra: especially where the nonce is concerned, we don't need a lot
of entropy anyway, and mixing a hash with a weak random number could
result in "fast" attacks against the hash becoming feasible.
Next: record format and encryption algorithm.
- Werner
_______________________________________________
Qi Hardware Discussion List
Mail to list (members only): ***@lists.en.qi-hardware.com
Subscribe or Unsubscribe: http://lists.en.qi-hardware.com/mailma