Anelok: first try at crypto: something-nymity (2/3)

Werner Almesberger werner at almesberger.net
Sat Apr 18 22:40:40 UTC 2015


Sometimes, one may want a bit more privacy. Let's see what options we
have for this.


Pseudonymity
------------

One possible feature that occurred to me is to hide the information of
who has written a record from anyone who is not an authorized reader.
This could be accomplished by introducing an "author" who is the real
source of the information in the record, and letting the "writer" just
be a pseudonym.

This pseudonym could be a completely random private key (*) used only
once, or anything more durable than that.

(*) For Curve25519, all it takes to build a valid private key from a
    random bit string is to clear or set five bits at fixed locations.
    ("Computing secret keys" in [1].)

The only changes needed in the system would be:

- we replace the checksum with a cryptographic signature [2, 3], which
  certifies that the writer did indeed what the author intended it to
  do,

- for identification, include the author's public key in the encrypted
  record,

- make the reader look up the author's public key in the list of
  authorized writers and validate the signed hash after decrypting.

Now, would this be worth the effort and the added complexity ? Costs
this produces include:

- code size (we only have a few kB),
- possibly RAM size (we have even fewer kB of that),
- CPU cycles (we only have a few MHz),
- since we're moving more/different information around, this may create
  unexpected side channels,
- possibly addition of bugs that can be used to compromise the system.


Anonymity for writers
---------------------

We could also omit any hint about the writer's identity completely.
A reader would then have to try to decrypt the record for each
possible writer until one produces a valid output.

Good:

- simple,
- reduces the information available to attackers,
- accomplishes the same and more than introducing an author,

Bad:

- if the number of possible writers is large, this may get expensive
  in terms of CPU time.


Pseudonymity for readers
------------------------

We could "scramble" the public keys used for identifying which encrypted
key belongs to which reader, for example by replacing them with a hash of
the secret reader and writer share through ECDH.

Salting [4] the hash would further obscure who the readers are.

Risks and side effects:

- more code, more cycles, more complexity,
- if salting, this will consume entropy,
- a weak hash function could reveal information about the shared secret,
- we can no longer tell whether a record is accessible to us without
  first performing the key agreement, (*)
- especially expensive if combined with anonymous writers.

(*) Whether this would be much of an issue depends on how data is used
    and structured.

    If each record has its own self-contained cryptographic information
    and there is a high probability that some records will not be
    accessible to us, then generating a list of accounts ("directory
    listing") would require checking accessibility of each entry before
    adding it to the list.

    If we can expect to be able to read everything - which is what I'd
    consider the normal use case, with this mechanism used to protect
    information shared among a small group of equals from outsiders,
    and not as a means to differentiate access levels inside this
    group - then we could just list everything we have and produce an
    error in the rare case when we find out later that we can't read it
    after all.

    Note: if also the information that goes into the directory listing
    is encrypted, then we have no choice but to decrypt the record in
    any case.

    Last but not least, multiple records may share the same encryption
    key. (*) In this case, the number of operations may be much lower
    than if each record had its own crypto.

    (*) Note that I've drawn the record content and the encryption keys
	in separate boxes. I'm not sure yet how to best arrange these
	things.


Anonymity for readers
---------------------

Like for anonymous writers, we could omit reader's identities completely
and just provide the encrypted keys. A reader would then have to try
key after key until one produces a valid output.

Good:

- simple,
- reduces the information available to attackers,

Bad:

- we can no longer tell whether a record is accessible to us without
  first decrypting it,
- if the number of possible readers is large, this may get expensive
  in terms of CPU time,
- especially expensive if combined with anonymous writers.


Is any of this worth the effort ? Are there plausible attacks or
inconveniences such *-nymity would effectively protect from ? And could
we afford the approaches that keep things simple but require more
computation ? How many authorized readers and writers should we expect
to have ? One or two ? A dozen ? Hundreds ?

Next mail: randomness.

- Werner

[1] http://cr.yp.to/ecdh.html#use
[2] http://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
[3] http://en.wikipedia.org/wiki/EdDSA
[4] http://en.wikipedia.org/wiki/Salt_(cryptography)



More information about the discussion mailing list


interactive