Implementation of signatures

[covert-encryption]

Our goal is to primarily use only X25519 keys (i.e. encryption keys, Montegomery Curve), and for signatures to convert them to corresponding Ed25519 keys (signing, Edwards Curve). Such a practice is commonplace and is considered safe in this scheme. The key conversion from Ed25519 to X25519 is implemented in libsodium and thus is commonly available. Covert already implements to opposite conversion, as specified by Whisper Systems / Signal in their XEd25519 (XEdDSA) scheme.

The sign problem

One problem with the opposite conversion is that X25519 keys lack a sign bit that is present on Ed keys, meaning that a single key can produce two different public keys, and thus incompatible signatures. Signal's specification suggests forcing the sign bit zero, and by modifying the secret key so that it matches. We believe that this approach is bad, and it would appear that Signal have also abandoned it for another approach that actually stores the sign bit in an unused bit within the signature itself.

Rather than forcing or storing the sign, one can easily try verifying the signature with the bit flipped both ways. One will fail, but if the other passes, the signature is good. Therefore, this is not really an issue.

The hashing problem

In principle the secret keys of both schemes are identical, and only the public key needs conversion. However, it is a common practice to take sha512 of an Ed "secret key" (i.e. what is stored in the keyfile) to obtain the actual secret key used by the algorithms. Thus, a secret key converted back won't work, because this extra round of hashing breaks it. Unfortunately this hash operation is built deep inside libsodium/ref10, and cannot be disabled.

X25519 operations do not use such hashing but instead use the given secret key directly. The libsodium ed25519_sk_to_curve25519 conversion function does just this hashing.

Signal solves this by their own XEd25519 signing algorithm that omits the hashing. This is almost perfect for our intentions as well, except for the fact that there are no commonly available implementations of this signing algorithm, and maintaining our own Python implementation of it does not seem optimal. Also, the algorithm opts for simplicity and does not require the public keys to be entirely unique (fully reduced).

Choices

Thus, as for implementation, we have two main options:

1. Signal's XEd25519, which allows us to use any Ed25519 or X25519 keys, and stores the sign bit in signatures
2. Standard Ed25519 which can only work with Ed25519 keys

Option 1 seems more sensible for the future, where XEdDSA is expected to be implemented in crypto libraries, and if so, it would simplify Covert implementation.

Option 2 might be reasonable because nearly all keys that we might want to use come in Ed25519 format. SSH and minisign keys would work for encryption and signing but Age keys could only encrypt. We would need to handle keys differently depending on which format they were sourced from.

Leaving the issue open for discussion.

[covert-encryption]

For simplicity of usage, we have only messages with an anonymous sender and messages that are signed by the sender, and in the latter case the sender public key is included within the encrypted and authenticated content, that is finally signed by it.

Also, plain text signatures where the message can be read in clear text and is followed by an encoded signature (PGP style) are not going to be supported, for two reasons. Any changes in whitespace or other innocent transformation of the signed message causes such signatures to fail. A bigger problem is that malicious people attach some random signature to a message they forged, assuming (quite correctly) that most readers won't bother to actually verify that signature, and instead believe that it was a signed message from someone else. Such scams are already very common with PGP.

The wide-open encrypted format is used instead, such that the message itself is also protected from both sorts of modification, even if it can be opened by anyone. Since it can only be read by using Covert, no-one can skip the signature verification, and readers will be alerted of any attempted forgery.

Further usability concern is that since the signature is only verified at the end of file, some might be tricked to extract malicious data before doing the verification. While Covert does not force doing two passes, it is expected both in our CLI and GUI workflows that typically one would first open a message, and immediately have the signature verified, prior to extracting any files. E.g. on CLI:

# Read/verify a message from clipboard (-A), listing its contents and signature
covert dec -A -i .ssh/id_ed25519

# Once seen that the content is OK, extract files
covert dec -A -i .ssh/id_ed25519 -o verified_files/

Since Covert can decrypt and verify about 4 GB/s, and even very large files are likely then entirely cached in RAM, the two steps do not make this much slower like they would with PGP.

[LoupVaillant]

I have an opinion on this: you are considering the wrong conversion.

Instead of starting from the X25519 private key, you should start from the EdD25519 private key: converting it to X25519 just means hashing it with SHA-512 an taking the first 32 bytes. Gone is the sign bit problem, and library support is back.

I also note that if you want to support SSH keys you don’t even have a choice: you have Ed25519 keys, that you must convert to X25519 before using them.

---

Besides, except for the wide open format, you could get rid of signatures entirely.

Most of the time, the reason we sign encrypted messages is to authenticate ourselves to the recipient. By doing so however, we give them a cryptographic proof they can show to everyone, that you sent a message to them. If you signed the entire message instead of an intermediate key, they can even prove what you said.

I personally don’t like this. Trusting a recipient with the contents of a message is one thing. Trusting them with the proof of what you said is quite another. So I prefer a fully deniable approach based on key exchange. Something like Whisper System’s X3DH, or Noise’s X pattern.

The idea is simple: instead of doing only one key exchange between your ephemeral key and the recipient’s identity key, you add another exchange, between your own identity key and the recipient’s. Hash them together, and voilà, you get a shared secret you can use to encrypt the rest of the message. The kicker here is that the recipient is able to forge messages from you to them. This has two consequences:

• If an attacker steals the recipient’s keys, they’ll be able to forge any message they want to the recipient. This is called Key Compromise Impersonation. That’s pretty bad.
• The recipient themselves won’t be able to show a cryptographic proof that you sent anything: they might have forged the message, so the whole thing devolves into "he said, she said". That’s pretty good.

So there’s a compromise here: either you give up on key compromise impersonation resistance, or you put more trust on recipients. My personal preference is that recipients are responsible for their own key. If they lose it, that’s on them. I don’t want to sacrifice my security for that of the recipient. Especially if the recipient is not a close acquaintance of mine. And of course, I’ll do my best to secure my own keys.

Other people may have a different preference. It’s a judgement call.

Edit: if you go the deniability route, it would be nice to add a "forge message to myself" easy to use option. That way deniability is not theoretical, users have an easy to use option that makes forgeries a real possibility.

[covert-encryption]

@LoupVaillant I'll get back to you later on key types, but a brief comment on signcryption, which you propose instead of signatures.

We have considered that, and have read Signal's reasoning for what they call deniability.

I believe the only case where anyone would believe the claim that you did not actually send the message is if the content says something beneficial to the recipient who releases it (for instance that you promised to pay a million dollars to that person), and even then it would still prove that you sent some message to him. If the message said something not directly beneficial to the recipient or if it was discovered by any other means than intentional release by him, it would be extremely difficult to convince anyone of the message not being written by you. It certainly would not protect against the more totalitarian governments.

However, signatures allow the recipient to prove that whoever holds the signature's secret key actually did write or approve the message. So, it allows making precisely this sort of agreements where you can assure that you are actually paying the recipient for something. A recipient wishing to prove that will only have to present the encrypted file and the file encryption key to a third party, while keeping his own keys secure.

The security model offered by signcryption is extremely difficult to understand, whereas signatures are pretty straight-forward, and because of this we only plan to implement (1) anonymous sender with no signature and (2) sender public key and signature included in message. These respond to two clear use cases where either the sender wishes to remain anonymous or wishes to prove message origin, avoiding forgeries, and still allows pseudonymity by using a custom or temporary identity as the sender of the signed message.

Notably, we do not implement messages that include the sender's public key but are not signed by it, as this easily leads to identity forgeries (the sender or any other recipient can put in a false public key without being noticed).

The wide-open format is used to force signature verification, avoiding the problems with plain text messages with signatures. Scammers already often take any signed message (PGP or Minisign) and modify the plain text to say something different. This passes because most people only read the plain text and won't verify the signature.

[covert-encryption]

On keys: the problem is that some of our source keys are in X25519 format, namely Age and WireGuard of the key types currently supported. We have conversions implemented both ways (and yes, Ed25519 to X25519 is easier because it is already implemented in Sodium and avoids the hashing issue).

The current implementation in version 0.5 is actually just that, what you propose (option 2 in the original post), allowing signing only with keys originally in SSH or Minisign format. But the specification says XEd25519 (i.e option 1) and there is Python code to support it, and I am slightly leaning towards it because of wider key support and because of some likelyhood of the Signal algorithm eventually getting picked up by cryptography libraries too (and if any of them did, this option would instantly win).

That being said, the signature algorithm, as well as many other details regarding signatures remain very much an open question. Your input on this will definitely be taken into account before finalising the specification.

FWIW, the covert.pubkey.Key structure always keeps the source format and generates keys in Ed25519, but also converts everything to X25519, We don't intend to add our own key format to the mess, so Covert-generated keys are only used as ephemeral keys. At least unless some significant extension such as X3DH is implemented, justifying our own format to support that rather than plain simple keys.

[LoupVaillant]

a brief comment on signcryption, which you propose instead of signatures.

I’m not proposing signcryption. I’m proposing the equivalent of the Noise protocol X pattern. With this pattern, there is no signature, and there’s not even the equivalent of signatures. Messages are still authenticated, but only to the recipient.

The point of this pattern, compared to an actual signature, is that the recipient is unable to cryptographically prove to anyone else that the message came from the sender. I’ll go even further, it doesn’t even prove that the sender ever sent anything: the only thing Bob needs to forge a message from Alice to himself, is Alice’s public key.

If Alice’s plaintext messages leak anyway, all people will have is circumstantial evidence, including Alice’s and Bob’s words. I agree that depending on context, circumstantial evidence can be more than enough, but I would insist that it’s not always the case.

However, signatures allow the recipient to prove that whoever holds the signature's secret key actually did write or approve the message.

This is a legitimate, but separate, use case: If the goal is for Bob to show Eve that Alice approved something, signatures is the way to do it. But then I’d rather sign the plaintext, and then encrypt both message and signature if I still need to keep it secret.

The wide-open format is used to force signature verification, avoiding the problems with plain text messages with signatures.

Yeah, about that: wide open formats are by their very nature easily distinguished from random (just test for wide open, if it works you win). The only thing you want here is making them unreadable by default to avoid user error. For this use case, any encoding would do, including just flipping all bits. I understand the temptation to reuse other parts of the specs to make the wide open format, but personally I’d rather consider making it an entirely separate file format, that could be just as easily implemented by a separate, much smaller application or library.

On keys: the problem is that some of our source keys are in X25519 format, namely Age and WireGuard of the key types currently supported.

If you have to support existing keys, that’s a bit of a problem. It would be much easier if you could just tell people to generate their Age and WireGuard keys from say an SSH key. If at all possible, I’d try to provide an SSH to Age conversion tool and encourage people to use it.

If you can’t, well… library support is possible, and I’d even say it would be easy to modify Monocypher to expose the intermediate step to the user. But then you have another problem: Ed25519 needs two private keys: the secret scalar (same as X25519), and some random secret that can be used to generate one random number per message. That random secret is a problem:

• It could be an actual random number. Heck, we could even pick a new one for each signature. But if we fail to make it actually unpredictable to the attacker, then they could deduce another secret number that ultimately reveals the secret scalar.
• It could be hashed from the secret scalar, but it wouldn’t be independent from it the same way it was when both where generated from the same seed. While it probably works, the data dependency triggers my spidey senses, and suspect it would trigger the spidey senses of most cryptographers.

Thus, I’m reluctant to add such support to my own library: it’s either not cryptographically sound enough, or it would add yet another death trap for the unwary user — I have enough of those already.

[covert-encryption]

What we really wish to have as a library implementation is XEd25519, not just any hack of Ed25519/ECDSA.

High quality random numbers are taken for granted, as without those all parts of the security fall apart anyway (no unique nonces or ephemeral keys, then ChaCha20 and Poly1305 won't work, etc). Fortunately random numbers are much less of a problem than they used to be just a few years back (barring smallest embedded systems and such where Covert cannot run anyway due to its hardware requirements).

While it is possible to scan for wide-open when you know to look for it, it does still avoid all typical searches such as plain text scans of disk images by forensic tools (I have seen plain text found from deleted temporary files of a PGP application this way, by a keyword search hitting some text within the message still on disk). If Covert became popular, possibly those tools would implement wide-open scans as well. But in any case, the wide-open format is not designed to protect data from being accessed, just of casual viewing, and providing safety against data corruption, and file attachments in addition to plain text. With an open source implementation available for all major programming languages, there is little reason to devise another custom format just for signatures, especially when Minisign already handles that well if you prefer maximal simplicity.

Signing all of the encrypted file, in particular all the recipient fields, was deemed most useful. Consider Alice sending a signed message to Bob saying "I will pay you". If the auth header was not signed as well, Mallory could take that message and change herself as the recipient, claiming that Alice had promised to pay her as the signature would still be valid. More generally, not authenticating and signing every byte allows for all sorts of potentially dangerous malleability. Covert attempts to prevent all malleability and does not allow anything to be modified even by message recipients, without immediately changing the file hash and breaking any signatures.

[LoupVaillant]

What we really wish to have as a library implementation is XEd25519, not just any hack of Ed25519/ECDSA.

Well, I agree there are legitimate use cases for XEdDSA. I need to study it in more depth, see whether I want to support it, and how many lines of code I’d have to pay for that (one hard limit I’ve set for Monocypher is 2K SLOC, and we don’t have that many left).

High quality random numbers are taken for granted, […]

Fair enough.

[wide open]

Makes sense.

---

If the auth header was not signed as well, Mallory could take that message and change herself as the recipient, claiming that Alice had promised to pay her as the signature would still be valid.

Actually, Mallory cannot do that, because she can’t decrypt the message, and there’s no ciphertext malleability to take advantage of. All Mallory can do is forge some arbitrary message from Alice to her, saying whatever Mallory is able to write.

More generally, not authenticating and signing every byte allows for all sorts of potentially dangerous malleability.

My proposal (Noise protocol, X pattern) does authenticate the message, and there is no malleability. When Bob receives a message from Alice, there are only two possible scenarios:

• Bob forged the message, hit himself on the head, and forgot about it.
• Alice actually wrote the message.

[burdges]

I believe deniability winds up typically being useless or worse harmful:

As a rule, anytime we've parties with dramatically unequal power, then only the powerful party benefits from deniability because exploiting the deniability works by exercising their power, usually established reputation, situational biases, media connection, or paid public relations personnel, but perhaps legal representation or political connections.

Afaik, the famous non-deniability cases were mostly where some powerful party gets exposed taking a malicious action, and then denies the action expecting their power and media connections shall sell their lie effectively, but then finally some signature proves they took the malicious action.

It's seemingly only cases of all primary parties having relatively equal power where deniability becomes useful, but here stakes wind up way lower.

It's basically the cutesy adversaries problem highlighted by Rogaway: We envision equal power parties when discussing abstractions like Alice v Eve, but afaik typical deniability cases really involve vastly unequal power.

---

I've an unrelated dumber question: You've placed these signatures inside the envelope I presume? Isn't this format meant to be anonymous?

[covert-encryption]

@burdges The attached signatures list signature public keys in the index header at the beginning of the encrypted stream and have the signature itself in a separate encrypted block after the end of the main stream. So yes, signatures are fully encrypted and can only be seen by recipients of the file. Signature block missing or any mismatch with index header causes signature verification error.

Detached signatures are similar but have no mention in the file itself, and only consist of a signature block as a separate file -- still always encrypted. To decrypt the signature block, one first needs to decrypt the signed file, and also needs to have the public key of the signature, otherwise it remains an opaque block of 80 random-looking bytes. The application does not currently implement detached signatures, and as with all signatures, details are subject to change.

Anonymous (in our terminology) means that the sender does not identify herself at all, the sender does not need any keypair, and there can also be no attached signatures (but a third party could create a detached signature). Senders can also choose to be pseudonymous and sign with a temporary identity that they use for nothing else, or if they do wish to identify, just use a publicly known identity in their sender signatures (as is customary in PGP messaging).

People who are not recipients of the message see nothing (other than the encrypted file size), while recipients see any sender public keys included, can verify the corresponding signatures and obviously can read the message contents. However, when there are multiple recipients, they cannot find out who the other recipients are.

@LoupVaillant The idea was that Mallory can already read the message, either by hacking Bob or because Bob released it to her for signature verification or other reason. I'll look more precisely at that scheme you proposed, some other time, and will get back to you then.

[LoupVaillant]

@burdges, with respect to the power asymmetry, I’m not sure how relevant that really is:

• My instinct tells me that when some powerful entity communicates with some nobody, the choice of the communication medium is largely determined by the powerful party. At the extreme end of this, you get good old paperwork: some entity (taxes, insurance, bank) make some mutual authentication, but once you’ve sent your paper or pay check or accident report, they are the sole arbiter of all your past interactions with them. Only exception being physical paper trail. Those entities won’t suddenly chose modern replacements of PGP, they’ll stick to whatever makes their lives easier.
• It would seem to me that Covert is more likely to be used among peers, or mostly peers, thus voiding the problem of power differences. No justification here, just my feeling.
• Covert is for asynchronous communication. I’d expect people will make a conscious decision to send each message, especially if it’s not as convenient as sending an email.

---

More generally, my point was to get around the fact that more and more informal communication is happening by text messages. Often to the point of being just as informal as unrecorded private oral conversations. We remember almost none of it, we have low expectations of people ever remembering it, and we easily resent people from digging up old conversations that may have derailed at the time.

It’s even harder with authenticated encryption, because the other party knows what you sent (unless you got hacked). And that’s a problem, because there’s a mismatch between how informal conversations are, and our ability to forget them. Take away deniability, and the mismatch becomes even greater.

In the end though, it’s a judgement call, and I’m honestly not certain what is the right one.

[burdges]

I do not know the right choice either. I base my biases upon the stakes being low among equals, but yes message ages enters the picture too. It's a messy topic for sure..

We've far too many people who breathlessly champion deniability in absolute terms, even asking Google to publish it's old DKIM secret keys, so it seemed worth raising my concerns. :)

I typically think deniable communications aligns best with a collaborative editor-like interface, so anyone could modify or delete or even rename the sender of old messages at any time, which perhaps makes the channel distasteful for more official use cases, and more useful among real equals. This has no relevance to covert however.

[covert-encryption]

A bit of practical aspect to the power discussion. Imagine a tor messaging board as the transfer medium, so IP addresses and such are not revealed, but the service gains access to all messages and may end up leaking them. Additionally, a search of a user's laptop can reveal Tor Browser's cache files as well as any messages saved by the user on local disk, and typically all keys are leaked at this point as well.

I am arguing that we need forward secrecy and to prevent messages being identified at all to have any chance against a more powerful adversary.

Making the data random blobs (binary or even plain base64) makes them extremely difficult to find on hard drives, which contain plenty of unencrypted random files (and space that may have previously contained files now deleted) that would look similarly random to statistical analysis tools. Many cryptographers tend to overlook this difficulty and assume that any random blob would immediately be found and considered an encrypted archive, making deniable encryption not useful against powerful adversaries. The file ctime/mtime/atime fields might in many cases be the most revealing and are hard to avoid in a file-based storage, and obviously a badly chosen filename could reveal the file to investigators. Still, even the user's home folder contains thousands of frequently updated application files that are hard to inspect and that a user cannot be expected to explain the meaning and use of. One having applications like the Tor Browser or Covert installed does not change this, unless the regime makes having such software installed a criminal act by itself.

If a ciphertext was found and decrypted, with an apparent message from Alice to Bob, repudiating message contents (i.e. deniable authentication) remains very "theoretical" (quoting @LoupVaillant from an earlier message). In practical terms, the judge and the jury would not understand nor believe the defence on the message being forged when the prosecutor presents a message in plain text saying that it was securely encrypted from Alice to Bob. Due to this, I don't see repudiability being a very useful property despite all of OTR, Signal and others' marketing claims (which would of course be useful material on building that defence).

[LoupVaillant]

In practical terms, the judge and the jury would not understand nor believe the defence on the message being forged when the prosecutor presents a message in plain text saying that it was securely encrypted from Alice to Bob.

Indeed they wouldn’t, and they’d be right: today, tampering with messages on most chat applications require serious technical literacy, and few would go to these lengths to do it.

To make forgery believable, it must be easy. Not just easy to do, easy to discover as well.

• Chat apps like WhatsApp and Signal should have unlimited editing facilities: delete messages, add messages, change messages… and most importantly don’t record the fact that such edits happened.
• Encryption software like Covert and Age should have a big "forge message to myself" button somewhere close to the main "encrypt message for someone else" button.

At this point, all you need to show the judge and jury, is how to click on the "forge message to myself" button.

[LoupVaillant]

Another reason I love those deniable schemes has nothing to do with deniability: it requires less code.

I hate dependencies. The less I have, the happier I am. The same goes for file formats, I want them to require as little code as possible. With a deniable scheme like Noise, all you need is key exchanges, hashing, and AEAD. With a signature based scheme, you need all that and signatures.

Signatures require quite a bit of code, even if you don’t count the code you already need for key exchange. Getting rid of them just simplify everything. (Now you may still need signatures for actual signing, but users who don’t need it could use a lighter implementation with less features.)

[covert-encryption]

Indeed, it certainly has use in many protocols, especially if Ed25519 can be avoided entirely. That is of course not a benefit that Covert has, although savings on code size would certainly be welcome especially on the Javascript implementation. Worse, all the secret key formats require their own password hashing and cipher algorithms, which are not even supported by common cipher libraries and require additional dependencies.

Another concern with signatures is that 64 bytes for a signature is a bit larger than we'd like, especially when coupled with the 16 byte authentication tag and the public key (total 112+ bytes, two lines base64 armored). It would be nice to reduce the size of this to keep short messages short. The authentication tag could be omitted by using AES-CTR or plain ChaCha20, or storing the signature in plain, but the related problems are not worth saving only 16 bytes. The public key is needed for good UX, as it is likely not known by the recipient on the first message, and we wish to establish key exchange with messages.

[covert-encryption]

And yes, such key exchange is vulnerable to MitM but active attacks are rare because they are hard to implement and can be easily exposed by additional verification (such as key comparison over some alternative transport), and no-one really has a better solution anyway (it is not like signing parties, web of trust and keyservers ever really worked).

[covert-encryption]

@LoupVaillant A quick signature-related question if you don't mind: how are the signs in Ed25519 and X25519 related? Given that there is an unused bit on the standard X25519 32-byte public key, wouldn't it be quite trivial to use bit this to encode the sign such that the original Ed25519 public key can be recovered exactly as it was?

[covert-encryption]

A related question, inspired by your earlier post: if a sub group has 2**252 + e points, aren't there 2**255 + 8*e points in the whole group? Now, how do all of these fit in 255 bits, is that because we only use the prime group, or is the highest bit actually sometimes but just very rarely used to encode a point? EDIT: Since we ignore the sign, I guess half of the points disappear, allowing all to fit (with almost half of the 255 bit values then corresponding to non points).

[LoupVaillant]

Worse, all the secret key formats require their own password hashing and cipher algorithms, which are not even supported by common cipher libraries and require additional dependencies.

Is there a compelling backward compatibility reason to do so? Otherwise I’d just stick to one format for password hashing, and another for high-entropy secret hashing.

It would be nice to reduce the size of this to keep short messages short.

A Noise-like X-pattern with its message needs the following:

• A public ephemeral key of the sender: 32 bytes, hidden with Elligator2.
• The public static key of the sender: 32 bytes, encrypted.
• An authentication tag for the encrypted static key: 16 or 32 bytes.
• The message itself, encrypted.
• An authentication tag for the message, 16 bytes.

I count a minimum of 96 bytes of overhead, or 112 if you want key commitment (making sure the authentication tag is not valid with any other public key). Well, I guess the 64 byte signature would still net you 32 bytes more than that.

---

A quick signature-related question if you don't mind: how are the signs in Ed25519 and X25519 related?

As far as I know there is no obvious relation. Even less so because the "sign" is kind of arbitrary to begin with: in Ed25519 for instance what we call "sign" is actually the parity of the X coordinate (whether it is odd or even, once reduced modulo 2^255 - 19).

However, this likely does not matter: see, public Ed25519 keys store only the Y coordinate, plus a single bit that is 1 if the X coordinate is odd, and 0 if it is even. The public key is decompressed into the full (X, Y) point before the actual verification algorithm starts. X25519 on the other hand utterly ignores the sign of the V coordinate, and only stores the U coordinate. The Montgomery ladder does not even decompress the point into (U, V), it uses the U coordinate directly (the resulting code is surprisingly simple).

To be tested, but many libraries, including Monocypher and Libsodium, ignore the most significant bit when parsing an X25519 public key. You could use it to store the parity of Ed25519’s X coordinate if you so wish.

---

A related question, inspired by your earlier post: if a sub group has 2**252 + e points, aren't there 2**255 + 8*e points in the whole group?

Yup, that’s exactly right.

As for the rest, your edit is correct: we ignore parity, that’s what makes encoding the point in 255 bits possible. Now to be more precise, X25519 points have two coordinates, (U, V), each between 0 and 2^255 - 20. Thus, the U coordinate trivially fits in 255 bits. But we do need an additional bit to encode the sign of the V coordinate (though X25519 does not even use it). No subgroup magic here, this works with the whole curve.

[covert-encryption]

Is there a compelling backward compatibility reason to do so? Otherwise I’d just stick to one format for password hashing, and another for high-entropy secret hashing.

• SSH keys use bcrypt and aes-ctr (n/a in sodium and the bcrypt uses so weak parameters that libraries won't accept them anymore).
• Minisign uses scrypt (with secure settings) and blake2b, even when the password is empty.
• Wireguard not encrypted
• Age uses Age-encrypted archive (scrypt, chacha20), their encrypted keys are not supported by us at this time.
• Covert will use Covert-encrypted archive (argon2, chacha20) when identity store is implemented.

Given that SSH is the most common key format used with Covert, we cannot really drop it. In addition to the old ciphers, also the implementation is quite odd with both SSH and Minisign (from the dark ages prior to AEADs). I suppose that not all Covert implementations absolutely have to support all of the formats if there is a tool to import them into Covert-native identity store.

A Noise-like X-pattern with its message needs the following:

That seems significantly less than the signature scheme, since only the authentication tag for the key would be something that we don't already have even in normal (anonymous sender) messages. I will look closer at this like I said earlier, too. However, a true signature still remains a requirement for purposes where you, well, need a signature.

... the most significant bit when parsing an X25519 public key. You could use it to store the parity of Ed25519’s X coordinate if you so wish.

Or should that rather be the sign of the V coordinate, or will whichever do? I have seen code for flipping the sign of converted keys, but am not exactly certain which sign/parity exactly needs storing for the montogomery-to-edwards conversions to work properly, and I suppose the V coordinate is not used in those conversions either, so cannot easily use its sign anyway.

[LoupVaillant]

Ah, you were talking about the format of stored keys, makes sense. I would do this in steps:

1. Fuck the other formats.
2. Have separate tools to convert those keys to Covert-native.
3. Give access to those tools from the Covert GUI.
4. Support the other formats natively.

Even step 4 can be cheated. Say you want to support Age’s format. Then Use Age itself. Call a subprocess that will decrypt the key, use the output to decrypt the archive you’re set to decrypt, then discard the key. Users will have the illusion of native support, while in fact it will work only when Age is installed and accessible from Covert.

... the most significant bit when parsing an X25519 public key. You could use it to store the parity of Ed25519’s X coordinate if you so wish.

Or should that rather be the sign of the V coordinate, or will whichever do?

Whichever will do, it will just affect the conversion process. If you store the sign/parity of the Edwards point, you must:

• Convert the U coordinate into an Edwards Y coordinate.
• Recover the Edwards X coordinate
• Adjust the sign of X with the sign bit.

You may be able to merge those two steps for better performance, but otherwise the conversion is easy to code, and all Ed25519 libraries have what you need to decompress the Edwards point. In fact, since they do so automatically when verifying a signature, what you actually have to do is even simpler:

• Convert the U coordinate into an Edwards Y coordinate.
• Replace bit 255 (which has value 0) by your Edwards sign bit.

Now if you want a Montgomery sign bit instead, here are the steps:

• Recover the Montgomery V coordinate
• Adjust the sign of V witsh the sign bit.
• Convert (U, V) into Edwards (X, Y)

And for this one, you won’t find many libraries doing it this way. You’ll likely need to derive the formulas yourself (not too hard if you’ve studied the subject, near impossible before you do). Moreover, since all Ed25519 libraries decompress the X coordinate automatically, what you actually need to do is the following:

• Recover the Montgomery V coordinate
• Adjust the sign of V witsh the sign bit.
• Convert (U, V) into Edwards (X, Y)
• Replace bit 255 (which has value 0) of Y by the sign of X, then discard X.

Use the Edwards sign bit directly, it’s much simpler. When you generate the key, you can use one of the padded bits of the secret key to select the sign. X25519 will ignore it, and your conversion scheme will be able to use it.

Now about doing it in constant time…

[covert-encryption]

4. Support the other formats natively.

We accidentally started here. We may have been able to read SSH and Age keys (that had no password) prior to generating any random keypairs.

1. Fuck the other formats.

But I am sure we can aim towards this and keep only one format in our own keystore. For public keys we could then just store sign+U that directly works with all libraries (without even having to mask that bit first) and that can be converted back to the original Ed25519 and then even to a line for ~/.ssh/authorized_keys still matching the original key (if it even was SSH to start with). Or maybe more conventionally, always store the Y with embedded sign, and convert any X25519-originated keys to that with a randomised sign (or rather always zero sign).

Secret keys still cannot be converted back for standard EdDSA once hashed and clamped. But XEd25519 would avoid that problem too. As would the signatureless scheme you are proposing.

Now about doing it in constant time…

Certainly an interesting challenge. Do the sign both ways and then constant time select?

Happy Friday evening to you too :)