PGP Keypair, Seeds and Speed Improvement

Its been a while since we introduced some new features - almost a month to be precise. Such a delay was caused by major system improvements which we will discuss in this post.

As you may know, we offer a one-of-a-kind feature to encrypt metadata of the email (i.e we encrypt who is the actual recipient and sender). As a result, if our database is ever compromised, it will give the attacker absolutely zero information of who talks to whom. We call this process the ‘Seed To E-Mail’ technique. You can learn more about it.

In short we create a tiny message with every new email that holds a reference to the actual email. It is encrypted with the public key of the recipient and each person has to retrieve this seed in order to receive new email.

This process obfuscates the recipient and allows us to be the only email service that not only truly encrypts email but also keeps communication between two parties private.

Unfortunately, due to huge overhead of retrieving every seed, we designed our system to have a second PGP keypair. It is deliberately weaker than the key we use to encrypt actual email. This particular solution seemed reasonable at the time and offers better speed performance (~6 times).

Aaron and I had a theoretical discussion recently in which we came up with the following 'what ifs...':

  • ... we have 10,000 seeds generated per hour
  • ... a person has not been logged in for a few weeks
  • ... some third party or spam server decides to spam us and force everyone to load a huge list of fake seeds
  • ... we grow like crazy and the amount of messages skyrockets Considering a 4 core desktop (at least that's what I have :) ), on average, it takes about 3 minutes to go through 10,000 seeds. It will require approximately 30 minutes of wait time for person who just visits their account after 10 hours. If you use a smartphone or missed a few days, it will take even longer. In case of just one week, we will risk losing a user. That outcome is a dire consequence we want to avoid.

We spent a good amount of time brainstorming on how to combat that problem.

Using a new approach, we dramatically increased performance. Recipients don't have to fetch all seeds in the database, but only have to retrieve those that belong to them. This eliminates that spam problem as malicious servers cannot spam all of our users just by generating a bunch of invalid seeds. At the same time, we still protect users from disclosing communication in between.

First of all, let's show how we had our seed and email records before:
seed

Each seed consists of 3 fields:

  1. seed Id - integer ID which corresponded with email ID
  2. metaData - actual string that contained public key encrypted text. There were thousands of seeds in our database that your account tried to decrypt, and if successful, it pulled the email having the same ID as the seed. Our initial seed keypair was only 512 bits long, which was not long enough to encrypt any meaningful data.
  3. modKey -hash of random string that allowed user to delete seed by providing correct string in order to prove ownership

Email:
email

  1. email Id - integer Id which equals the seed Id
  2. email Body - actual encrypted email that contained communication and other technical parts
  3. email Meta - short encrypted version of email to represent it in Inbox
  4. fileObj - if email had an attachment
  5. mod Key - same as seed to prove user ownership of this email

In our new design, we add more fields to the seed:
new seed

  1. seed Id - integer Id, not corresponding to email Id anymore
  2. metaData - AES encoded JSON string that stores email ID, and email and seed Mod key
  3. AES KEY - encrypted with recipient public key
  4. modKey - hash of random string
  5. email Recipient - SHA512 of recipient public key (first 10 characters)

Email changes includes only email Id and everything else stays the same:

  1. email Id - now 64 randomly generated long hex

Adding a Recipient hash solves problems with speed and spam.

If our database is ever compromised, an attacker can learn that there are a messages that can belong to their target since we use only 10 first hex. However, they won't know which email is related to this seed.
But the attacker can try to bruteforce this seed in order to decrypt it and find out the email Id. To handle this type of problem, we got rid of the seed key since it is weaker, and let our users use a single public key to encrypt both seed and email, which is much stronger and now can be 2048 bit for even a basic account.

We also want to emphasize that nobody can retrieve new email without knowing the actual email Id and modKey of it, and both the seed and email get removed from our database when you fetch your email. This way gives two main benefits:

  • If RSA encryption becomes compromised, we can seamlessly increase key strength requirements without your old emails getting compromised
  • An attacker cannot record emails that have been sent before an attack, since emails and seeds get deleted when a recipient opens his or her email and moves it to their inbox. All emails in inbox are encrypted with AES, which is even stronger than RSA. If an attacker has physical access to our database, all previous messages still will be protected because they are stored in personal folders and encrypted with AES.

The one most important thing you should remember is to regularly login into your SCRYPTmail account to check for new emails.