Dirty Elligator for better hiding of the ephemeral key

[covert-encryption]

Three bits of information per file were still leaked in ephemeral keys, weakening the deniability property. This is fixed by implementing dirty keys that use all eight of Curve25519 subgroups rather than only the prime group.

Also implements and uses Signal's XEdDSA (XEd25519) for signatures as is written in Covert specification. Previous versions used EdDSA instead, making it impossible to sign with Age and Wireguard keys. Now all key types are good for both signatures and encryption.

Fixes #55 Fixes #2

[codecov[bot]]

Codecov Report

Merging #61 (bcbe222) into main (ae1ce19) will increase coverage by 4.34%. The diff coverage is 89.47%.

@@            Coverage Diff             @@
##             main      #61      +/-   ##
==========================================
+ Coverage   63.43%   67.78%   +4.34%     
==========================================
  Files          17       22       +5     
  Lines        1991     2086      +95     
  Branches      448      487      +39     
==========================================
+ Hits         1263     1414     +151     
+ Misses        593      531      -62     
- Partials      135      141       +6     

Impacted Files	Coverage Δ
covert/pubkey.py	67.72% <63.63%> (-0.16%)	:arrow_down:
covert/elliptic/eddsa.py	72.41% <72.41%> (ø)
covert/elliptic/elligator.py	82.60% <82.60%> (ø)
covert/elliptic/ed.py	93.75% <93.75%> (ø)
covert/elliptic/scalar.py	94.20% <94.20%> (ø)
covert/elliptic/xeddsa.py	94.59% <94.59%> (ø)
covert/elliptic/util.py	95.00% <95.00%> (ø)
covert/blockstream.py	79.79% <100.00%> (+0.20%)	:arrow_up:
covert/cli.py	57.91% <100.00%> (ø)
covert/elliptic/__init__.py	100.00% <100.00%> (ø)
... and 1 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update ae1ce19...bcbe222. Read the comment docs.

[covert-encryption]

@LoupVaillant Would you mind having a look at this?

[covert-encryption]

Now that there is a largely independent implementation in plain Python, I should try making bindings to Monocypher and see if it can be produce identical Elligator mapping (using deterministic tweak values as used here). Ideally also XEdDSA would be available from that library, as the Python implementation is fairly slow (circa 30 ms for each of signatures and dirty elligator), which is not long enough to matter much for Covert but still could be much faster, and is also less secure than a C implementation could be (because Python is not constant time and cannot zero out buffers after use).

[LoupVaillant]

Almost perfect as far as I can tell. I noticed no misconception in the comments, it seems you've got a good grasp of the problem.

I only found one error, which may or may not be serious: the fully deterministic dirty point generation. To have perfect randomness, you don't want to use the sign of P (P.is_negative), you need a random sign.

Reason is, regular public key generation cover only half of the prime order subgroup. Quite naturally, adding a random low order point will generate only half of the curve. More details here.

If we count, the order of the prime order subgroup is about 2^252, but the clamped scalar has 256-2-3=251 bits only. So we're one bit short. In practice it doesn't matter at all for X25519, because if we consider not the points themselves, but pairs of points (P, -P), then we cover all pairs almost perfectly (some pairs are missing, and there's some overlap, but the bias is undetectable in practice).

So to cover all points, you need to select the sign of your point randomly. You don't, and as a result you're covering only half of all possible representatives, instead of almost all of them.

This time though, this bias, as huge as it is, is not easily detected. Not by current method anyway. Mike Hamburg himself conjectured to me 2 years ago that there's probably no fast method to detect this bias. So you are probably okay.

Me, I made a different choice for Monocypher. I wanted a provably undetectable bias, but for this I needed a total of 257 bits. That's why I ultimately opted to have an additional input for the tweak & point sign.

Now I won't strongly oppose your approach if you feel if the API convenience is worth it. That's a judgement call. It just need to be a conscious choice.

[covert-encryption]

EDIT: After many quick edits...

Ah, got it. Since the clamped scalar is (roughly) 4q...8q and with low three bits cleared, only half of the points are created (using of each eight adjacent prime group points a pattern that includes four and misses the other four, with the same pattern repeating over the whole group). But assuming that the DLP holds, this is not a problem as the points that are created are still random by any inspection, offering 50/50 % of each sign and no useful relation between the sign and the y coordinate.

So yes, there is definitely a bit of entropy missing like you mention but doubling the number of keys on Ed25519 (as well as the convenience of the preserving signs by itself) might indeed outweigh that even when this is typically only used for X25519.

It would be nice if you'd click the approve button so that we can get this merged properly, even though #63 is in the plans.

[LoupVaillant]

You got it correct. Just make sure you encode that understanding of the comments, so future reviewers can be aware of the tradeoff.

[burdges]

Elligator is already fairly dirty if you go by the sketch in the paper. ;)