Qtox: Suspected security vulnerability in qtox chat history

[initramfs]

Whilst snooping through the code I found the routine for generating/deriving a symmetric encryption key for the chat history data (in rawdatabase.cpp) was using a static salt.

As seen in this line and this line, the code to derive a encryption key comes from the encoded form of the string:

L'ignorance est le pire des maux

or

4c 27 69 67 6e 6f 72 61 6e 63 65 20 65 73 74 20 6c 65 20 70 69 72 65 20 64 65 73 20 6d 61 75 78

on my machine (ASCII).

Not sure if that's meant as a joke or something but since this singular byte array is set during compile time, all users who use pre-compiled binary versions or did not change this salt would have the same salt, effectively negating the password salt.

An attacker can simply generate a rainbow table with this specific salt, and given access to the database file, attempt a brute-force attack that's amortized by his/her pre-generated table.

---

Brief Description

qTox's database key derivation routine uses a static salt, this is incredibly dangerous and detrimental to the security of the chat database file.

Reproducible: Always

Expected Behavior

The concept of a salt, especially in this case is such that it changes the way a hashing function or PBKDF works, preventing a single pre-generated rainbow table from being used against the chat history database. As such, during initial generation, the salt should be randomly generated from a TRNG or a CSPRNG source and then stored with the database file. Such use of the salt guarantees that everyone's db file will have a different salt (and thus lookup/rainbow tables become ineffective).

---

Edit: The static-salted key is being saved as a PRAGMA within the DB, but doesn't seem to be otherwise used, I'm continuing to investigate...

The PRAGMA directive apparently causes sqlite to perform it's own encryption operation using the given key.

[initramfs]

@zetok Well, I might have jumped the gun a bit, the static-salted key doesn't seem to be used... Not sure why it exists, but something's definitely weird with the way the chat history is being encrypted. I guess you can remove the "P-very-high" flag for now. I'll investigate further...

[zetok]

Even if it's just suspected, it's still very important. And any existing ambiguity when it comes to code that ensures security needs to be cleared up.

[initramfs]

@zetok Okay, I think I just verified it, the actual encryption is being done by sqlite, using the static-salted key. The PRAGMA directive causes sqlite to perform encryption using the affected key.

[linux-modder]

so the static is being used as a primitive essentially for the sqlite encryption?

[initramfs]

@linux-modder toxcore provides us with a library named toxencryptsave (ToxES for short) that provides a PBKDF (Password-Based Key Derivation Function) for us. For initial generation of the encryption key, this PBKDF requires your tox password and a secure random salt in order to ensure security. The problem here is that a static salt (which is definitely not secure) is being used.

In short, the encryption key isn't static as it still depends on your tox password. The problem is that an attacker can generate a lookup table of passwords to encryption keys that'll work for every qTox client out there. Arguably worse, compromise of your database file and an attacker could very likely get access to what your original password is as well (provided he/she has the resources).

[linux-modder]

@initramfs that much I get I was just not sure the naming of the bits as they pertained to qtox thanks.

[initramfs]

@linux-modder And to everyone else interested (just for the sake of clarity), the PBKDF that ToxES provides us is called tox_derive_key_with_salt, the documentation from ToxES being:

/* Generates a secret symmetric key from the given passphrase. out_key must be at least
 * TOX_PASS_KEY_LENGTH bytes long.
 * Be sure to not compromise the key! Only keep it in memory, do not write to disk.
 * The password is zeroed after key derivation.
 * The key should only be used with the other functions in this module, as it
 * includes a salt.
 * 
 * Note that this function is not deterministic; to derive the same key from a
 * password, you also must know the random salt that was used. See below.
 *
 * returns true on success
 */
bool tox_derive_key_from_pass(const uint8_t *passphrase, size_t pplength, TOX_PASS_KEY *out_key,
TOX_ERR_KEY_DERIVATION *error);

/* Same as above, except use the given salt for deterministic key derivation.
 * The salt must be TOX_PASS_SALT_LENGTH bytes in length.
 */
bool tox_derive_key_with_salt(const uint8_t *passphrase, size_t pplength, const uint8_t *salt, TOX_PASS_KEY *out_key,
TOX_ERR_KEY_DERIVATION *error);

Though not explictly stated, it does mention that tox_derive_key_from_pass (which should be used for initial key derivation) uses a random salt.

[tux3]

Hi, I wrote this code so I'll try to clear things up a little!

This static salt is used to derive a key for the history database when the qTox profile has a password set, we currently don't use a random salt mainly because the PBKDF that we use is strong enough to make rainbow tables impractical by itself, and second because there's no obvious place to store that random salt (as it can't easily be written in the database file itself without confusing SQLite).

We absolutely could find a way to use a random salt, but first let's see how practical rainbow tables are in this case to check whether there is a security issue.

---

The key-derivation function that we use internally is libsodium's scrypt with slightly stronger than default parameters.

Let's do a quick back-of-the-envelope calculation. It's not that easy to get numbers for a typical scrypt hashrate nowadays since the custom scrypt parameters make it hard to compare. On my laptop each call to the KDF takes a bit over 100ms, that's 10^-5 Mhash/s.
Since we use scrypt, there are high memory requirements which makes it a major pain to parallelize key-derivation or implement custom hardware for it, but let's assume an attacker with 10,000 times more computing power than my machine, that's a 0.1 Mhash/s hash rate.

Now say we want to generate a rainbow table, we know that qTox profile passwords have a minimum length of 6 characters.
So let's generate a table for 6 to 8 characters passwords, with a simple Alphanum charset (no symbols, nothing fancy). Let's say we want a run of the mill 10,000 links per chain in 4 tables at a 99.9% success rate.

Now let's plug the number in a handy calculator available here.

We get 4 rainbow tables of 900GB each, and a generation time hovering around 770 years.

---

Now that we have some order-of-magnitude numbers, let's discuss whether this is a security issue or not.
Note that I tried to assume some sensible default for the parameters of the rainbow table, but this is of course very debatable. Perhaps the attacker is only interested in 6 characters passwords with only ascii letters and no symbols, in this case the rainbow table is doable in a matter of weeks.
However as much as we want to strive for security we have to remember than there is nothing we can do to protect from exceptionally weak passwords (except forbidding them). If a bruteforce will do or if your password is in rockyou.txt, salting will not save you.

Furthermore, all of the above discussion assumes that the attacker has access to your qTox database file, this is a questionable situation in and of itself.
Now of course, rainbow tables are not magical, they trade some precomputation time for a faster attack later, but they are only useful if the attacker plans to crack a large amount of passwords (otherwise the precomputation is a clear waste of time), so we might imagine an attacker in control of a botnet or equivalent as part of our threat model.
But clearly if the attacker has access to your computer, then it is easier to install a keylogger than to crack the cold hashed password, so this scenario is only valid in the case of an attacker who can read your qTox profile but _not_ compromise your system. So there is a question of whether such an attacker is realistic or not.

---

So to sum it up the threat model considered here would be an attacker interested in cracking large amount of qTox profile passwords, who has a access to a copy of many people's qTox history database (but _without_ compromising their computer), and who is only interested in cracking weak 6 character passwords (otherwise the rainbow tables take >10 years), but still willing to dedicate the money to running a hash-cracking server farm for months.

I considered that all of this at once was not a realistic threat model, and that's why we only use a static salt (instead of for example implementing a system to store a random salt in a different file).

If I made a mistake above, or if people care about this threat model regardless, I'll be happy to discuss what we should do here, more security is always welcome :)

[initramfs]

@tux3 I completely understand the threat model you've suggested, in fact, that's the only reason why I'm not scrambling to write a PR to fix it right away. The issue here isn't that the security model is realistically compromised (though admittedly I guess realistic software security is really all that matters...) it's that the algorithm is applied inappropriately where it can most certainly be fixed.

This issue is mainly here to shed light on the particular issue and motivate action towards a fix since who knows how long that snippet of code could be there before someone else finds it. Better to have this as a lingering open issue such that people are aware that this needs to be fixed than having this issue rediscovered only when someone actually has an idea how to fix it. Though this seems unlikely, we must not exclude the possibility that advances in hardware allow more practical attacks against Scrypt (and by practical, I mean in the cryptoanalytic sense, when the attacker is some multi-million dollar organization with botnets and stuff). Just as a trivial example (I'll admit this is not at all realistic), imagine the whole litecoin mining pool is turned against you, their combined hashrate is indeed in the GH/s region (that's actually pretty bismal, good job Scrypt!)

Just a small detail, regarding your threat model, you stated that obtaining the chat history database is equivilent to full access to a computer:

But clearly if the attacker has access to your computer

This is not at all true. It's often easier to obtain file access to a computer (more so, read file access) to a computer/device than to get full root privileges. Besides, we must not exclude social engineering attacks (e.g. some website that claims to "organize chat history" or provide services to your chat history that cause users to willingly submit their chat history file).

Whilst I'm not suggestingly that we somehow provide means to completely shield the user from bad passwords, qTox's masthead does promote "ease of use" as one of it's design goals. Even if the user inadvertently submits their history db to some phishing service, we need to at least make a best-effort attempt to stop secrets from being leaked. Using a password salt (whether this helps at all with _practical_ security right now or not), in my opinion, is very necessary. To me it's akin to deciding to stick to MD5 using like a billion iterations (or some ridiculously high number) and saying that's good enough since no current technology exists to crack it in reasonable times (yes, yes, I know MD5 has low memory cost and can be easily parallelized by GPUs, it's just an example).

[tux3]

@tux3 I completely understand the threat model you've suggested, in fact, that's the only reason why I'm not scrambling to write a PR to fix it right away. The issue here isn't that the security model is realistically compromised (though admittedly I guess realistic software security is really all that matters...) it's that the algorithm is applied inappropriately where it can most certainly be fixed.

This issue is mainly here to shed light on the particular issue and motivate action towards a fix since who knows how long that snippet of code could be there before someone else finds it. Better to have this as a lingering open issue such that people are aware that this needs to be fixed than having this issue rediscovered only when someone actually has an idea how to fix it. Though this seems unlikely, we must not exclude the possibility that advances in hardware allow more practical attacks against Scrypt (and by practical, I mean in the cryptoanalytic sense, when the attacker is some multi-million dollar organization with botnets and stuff). Just as a trivial example (I'll admit this is not at all realistic), imagine the whole litecoin mining pool is turned against you, their combined hashrate is indeed in the GH/s region (that's actually pretty bismal, good job Scrypt!)

That's entirely fair, and you make a good point that what is not a problem now may be a problem ten years from now. The only thing to be careful of is that when changing the password of the database, we have to be careful to not lose the qTox chat history even if the computer crashes at any point (this is trickier if we need to save two files in lockstep!)

Just a small detail, regarding your threat model, you stated that obtaining the chat history database is equivilent to full access to a computer:

But clearly if the attacker has access to your computer

This is not at all true. It's often easier to obtain file access to a computer (more so, read file access) to a computer/device than to get full root privileges. Besides, we must not exclude social engineering attacks (e.g. some website that claims to "organize chat history" or provide services to your chat history that cause users to willingly submit their chat history file).

Absolutely, what I meant to say, and I must not have been very clear, is only that the threat model is _not_ valid in the case where an attacker has access to your computer (because then a keylogger renders all security useless), so you should probably be _more_ scared by botnets, malware and exploits than this as a user.
It's entirely possible that the attacker will get access to a copy of your profile (maybe you lost a USB key, maybe you forgot to erase the hard drive, maybe you uploaded it somewhere unsafe), the only thing to keep in mind is that this particular threat model is only interesting for the attacker if this can be done at large scale, otherwise it's not worth spending the money to compute rainbow tables, and even then it only works for very weak passwords.

Whilst I'm not suggestingly that we somehow provide means to completely shield the user from bad passwords, qTox's masthead does promote "ease of use" as one of it's design goals. Even if the user inadvertently submits their history db to some phishing service, we need to at least make a best-effort attempt to stop secrets from being leaked. Using a password salt (whether this helps at all with practical security right now or not), in my opinion, is very necessary. To me it's akin to deciding to stick to MD5 using like a billion iterations (or some ridiculously high number) and saying that's good enough since no current technology exists to crack it in reasonable times (yes, yes, I know MD5 has low memory cost and can be easily parallelized by GPUs, it's just an example).

I completely agree that we should strive towards perfect security, even if we can't necessarily attain it. It's certainly possible to fix this, and although I don't currently see it as a security issue, I see no reason why we shouldn't improve the situation.

[zetok]

We absolutely could find a way to use a random salt

I considered that all of this at once was not a realistic threat model, and that's why we only use a static salt (instead of for example implementing a system to store a random salt in a different file).

Just gonna leave a note here: TES (toxcore encrypted save) does use random salt, and it does save it with the file.

qTox used it before custom stuff for DB.

[initramfs]

@zetok Yeah... Though I'm not certain, I believe the new DBMS-based encryption system (as opposed to the old custom DB code) allows for transactional atomicity, allowing the system to crash at any point without risk of data loss. ToxES' encryption functions are very primitive in nature and only work when committing a whole file from memory to file, unsuited for DB needs (in fact I opened an issue on it).

The main issue with implementing a system that saves a random salt is where and how to store the salt and upon rekeying, how to update the salt atomically with the new key.

[zetok]

Yep, atomicity was main reason why the change happened. Too many users lost their data because of slight corruption.

[sudden6]

I spent a few thoughts on where to get better salt value than the static one and I think I might have a solution or at least an improvement for it. My idea is to just use our own public key as salt for the database.

I think it works, because the:

• public key is semi random
• public key is stored inside of *.tox file and thus encrypted, if it can be decrypted we already have lost
• public key is unique for every qTox user, no more rainbowtables for all users
• public key is easily available before the need to decrypt the database arises

So far the only drawbacks I can think of are:

• if the *.tox file is lost, the database is also lost without help from others (giving back your public key)
• I don't know if this is secure from a security standpoint, but I think since a Salt is uncritical and a PK is also uncritical it should be no problem

[initramfs]

@sudden6 Seems like a viable solution, though I was hoping that something as trivial as storing a small random string wouldn't be such a remote possibility. I heard there was a proposal for the tox file to store custom key-value pairs in the save file, that would definitely be useful in this case. If that was ever implemented on password changes we could:

1. Generate the salt.
2. Store the salt in the tox save file
3. Save the tox save file (note we keep the old salt at this point)
4. Derive the new key
5. Use the new key with the DB
6. Delete the old salt
7. Save the tox save file again

Corruption/crash at any point results in a consistent state for the system (either both salts are present or only the old or the new). And we can simply try them both and see which works on login during crash recovery.

But yeah, anything short of that the PK itself is a good candidate.