Feedback on my similar tool

[covert-encryption]

You should be aware of our effort at finally getting encryption right (and killing PGP). First and foremost, our files have no identifiable header bytes: without correct keys it looks like random data. Yes, it was a little hard to design, but we got it done.

GPG, Age, Kryptor and yes, everybody else reveal the exact size of the plaintext because the encrypted file only adds its headers. While random padding is not a new idea, we implement it correctly while others don't support it at all. We can also put a message and a bunch of files into a single archive (not possible with most other tools, Krypton included as I understand), which hides the sizes and count of individual files, and allows for easier transport of the whole package.

Even with the padding included, our messages are super short, only one line of Base64 where GPG and Age use about six lines, and the gap only widens once you switch to public keys or perhaps have many recipients and signatures.

Within weeks, I claim, we have implemented more features and for a large part better than any of our competition. The console UI is already pretty good. The encryption runs faster than any other program that we know of (around 3 GB/s).

Covert Encryption is still in early development, but we want people to test it and give feedback, especially on the specification because all changes are still possible. For Windows we plan to do a GUI soon and thus won't bother to fix operation in legacy terminals, so use Windows Terminal or other modern options if you wish to try it at this point. Other platforms have no such issues.

https://github.com/covert-encryption/covert

[samuel-lucas6]

This is a very advertisey comment, and from a quick look, I can already see some questionable things and comments going on. For example, password hashing for dozens of seconds is completely impractical, forward secrecy isn't possible using a non-interactive key exchange, the same nonce is being used for various things, you're XORing keys, and you've said that using numbers and symbols weakens a passphrase. I'm afraid I don't currently have the time to look into your tool properly.

I'm going to investigate implementing an indistinguishable from random format in v4 because minimising metadata is a goal of mine. However, it's a lot harder to do. One of the main issues would be applying Elligator to ephemeral public keys and padding messages in a way to limit leakage.

As for the current version of Kryptor, it does not reveal the exact size of the plaintext because it encrypts in 16 KiB chunks. Even if you encrypt a 0 byte file, it will be padded to 16 KiB. Age also performs chunking but only for larger file sizes. Directory encryption does not currently result in one file, but that's another thing I'm considering for v4. It does have various disadvantages though, like not being able to decrypt or back up individual files in the directory. A corruption could prevent decryption of the entire directory, whereas encrypting files individually means a corruption is less of a problem. It's also again more difficult to implement.

[samuel-lucas6]

Thank you for the clarification. I've only heard good things about PADME, so I'll look into that.

[covert-encryption]

Thanks for the motivation, I just implemented Elligator2. Meanwhile someone made a GUI which is looking pretty cool, hoping to see that PR finished and merged soon. I was expecting it to be until early next year that work on GUI should be started but I definitely don't mind having one now.

Regarding padding, since everyone seems so hyped about Padme, I did have a closer look. It turns out that the overhead is actually very low, and that the 12 % figure was only the maximal peak value. As for other features, here are a few diagrams to illustrate.

Data shown in gray, padding on top of it in orange, and in case of Covert the fading shades of orange represent randomness. For each output size, we should have many possible input sizes that could have produced it.

If only clearly distinct known output sizes are produced, an adversary can find out which padding scheme was used. We do not want those spikes. Even a single larger file can be revealing. E.g. 1114112 bytes is almost certainly padme padding because it is one of the 33 sizes that padme uses within the 1-2 MiB range, where you would expect a million different sizes if they were random.

[samuel-lucas6]

Yes, the minimal overhead seems to be the main selling point. Nice graphs thanks. I do agree that deterministic padding is more problematic.

When padding with chunked encryption, you can either:

1. Pad each input chunk.
2. Pad each output chunk.
3. Pad based on the entire input size.
4. Pad based on the entire output size.

The first two require storing more information about the padding and complicate decryption. The bottom two result in having to store less padding information, and the padding can be easily skipped or removed. Which would you recommend? I presume you're calculating the amount of padding based on the input file size rather than the output size.

[covert-encryption]

Covert indices all the input files and reads their names and sizes (if available) before starting, writing an index at the beginning. If all sizes are known, the padding size can be calculated before starting encryption, but if there are any streaming inputs (e.g. from a pipe), we do that after all the files have been written so that the total content size is known. It is also possible to add padding in the middle of streaming, which may be necessary to fill a block when less data is available than the current block size, and real time operation is needed.

The padding size is calculated on content only to allow short messages to be protected while keeping the output size under 100 bytes. An adversary who knows that a short file is a covert message can discover that it can only have one recipient and no signatures (as having any more data would make it larger than the actual size found), just as she can deduce the maximum size of content that there may possibly be. However, randomness makes it far less likely that anything of importance could be extracted unless the adversary can have the same message encrypted many times, allowing statistical analysis, or if she gets lucky and gets a random size that matches only one of the known possible plain text lengths. Any deterministic padding that still allows the output size adapt to content still reveals more. I also attempted combining Padme with randomness either before or after it but either way it was worse than our current system.

Padding is best added at the end, after all the content. To keep every byte authenticated and to avoid having to generate random bytes we put the padding inside ChaCha20-Poly1305 and always read all of it (another implementation can choose to stop early of course, just as they can seek to skip to a specific file while decrypting). If you don't care about full file authentication, you can simply add random bytes after your format has already indicated that the data has ended.

Full authentication is relevant when an adversary can try altering some of the bytes and then test with a decoding oracle whether that causes an error. If your padding is not authenticated, any modification to those bytes goes undetected, allowing Malice to learn the amount of padding there is in that file. A similar problem with the auth header bytes, where altering any bytes actually used just causes a decryption failure, so you might think you need no authentication. However, if altering some of the bytes causes no error, Malice learns that those bytes are part of the auth header and that they contain a recipient other than the one she is testing on. Thus, you really should have every byte authenticated, which of course is very easy to do with AEAD ciphers, no reason to use HMACs anymore.

[samuel-lucas6]

Pad-then-Encrypt seems sensible. I agree that every byte of the file should be authenticated. Prepending or appending would work for Encrypt-then-Pad though if you authenticated those bytes by using them as additional data. That's what I was getting at. The official PURBs implementation switched from Pad-then-Encrypt to Encrypt-then-Pad.

I'm afraid I don't agree with you about HMAC though. Encrypt-then-MAC provides better security than an AEAD when implemented correctly. The main disadvantage is of course speed, especially compared to newer algorithms like AEGIS and ROCCA.