Recently we have added a so-called All-or-nothing transform to our encryption module.
All-Or-Nothing transform (AONT) was introduced by Rivest back in 1997. It is used to increase a cost of brute force attack without changing a key length. Generally speaking, AONT is not a cryptography since there is no secret key. We take a random key, mix a message with that key to get a new message that can be read only if we have all of its parts. With just a single missing block we cannot recover the original message. That makes a brute force attack harder since an adversary needs to decrypt a whole message to check if the key guess was right. The longer a message is, the harder it is to brute force a key.
For example, for AES encryption in CBC mode, an adversary can take an encrypted block, then take the next block and try to brute-force a password on that block. There is enough data to check if a password is correct. With AONT, an adversary needs to get all the blocks of the message and try the key on all of these blocks to be able to tell that the key is OK. That slows down the whole process by the multiple of total blocks count. It is good on large data blocks that are more than 1 MB in size.
Why do we use AONT if a size of a typical email message is less than a page? Our primary goal is to provide maximum security of your data. Although AES itself is an industry standard for encryption and is considered safe enough to use it for business, there are plenty of options, such as bad passwords, for example, that may weaken it. SenseMail uses low-entropy passwords to protect data. That is not a weakness of the application, this is our reality – all the passwords, shorter than 40 symbols are weak. So we use every possible solution that may strengthen the encryption. Despite some experts who claim that AONT has no strong mathematical proofs and is virtually useless on small pieces of data we decided to give it a chance since it, anyway, narrows the set of attacks available to crackers and requires more time to process. Who knows, perhaps it may save your data. At least, it will not decrease security in any aspect.
We derive an encryption key using 88K rounds of PBKDF2-SHA512. In the most cases, then a message is a typical e-mail message (1-2048 characters), with AONT an adversary will require up to 64 more AES operation. Compared to the key derivation this is nothing. But if you use a 256-bit certificate to protect your message, there is no need to derive a key, then an adversary will require up to x64 more time to crack the message. This is really much, taking into account that brute-forcing a 256-bit key is an insane idea itself.
One drawback of this method is definitely time. AONT will take its time to process the data and a user will have to wait. Hopefully, our tests showed that this delay is just a fraction of a second, so we found that price acceptable.