On gpg2's symmetric decryption

Question

According to an answer and comments in a earlier question of mine, when one uses gpg2 to symmetrically encrypt a message, gpg2 randomly generates a one-time encryption key for that message, as well as some random salt, and uses this key and salt to encrypt the message. Furthermore, the passpharse and the resulting encrypted message comprise all the information that gpg2 needs in order to decode the message.

I am still unclear on some of this.

First, could someone walk me through how gpg2 uses the passphrase to decrypt a message symmetrically encrypted under that passphrase?

I imagine that the passphrase is used to decrypt the one-time randomly-generated encryption key K that was used to encrypt the main message, and then this K is used to decrypt the rest of the encrypted content to produce the original message.

If this is true, it means that, however strong the one-time encryption key may be, this strength is irrelevant; the only cryptographic strength that matters here is the strength of the passphrase. Is this correct?

Second, what is the point of using a salt here, if the symmetric encryption key is a one-time randomly generated one, used to encrypt only one message? In other words, what kind of attack could be mounted against a one-time random encryption key that a salt would thwart?

Answer 1

Salts for passwords effectively exclude the possibility of a rainbow table attack or even a simple reverse lookup. Rainbow tables allow to pre-compute hashes of passwords and store them in a way that allows to find them in minutes (if contained in the tables) instead of years or longer. When a salt is used, the whole data structure of these rainbow tables has to use that salt, too. So you basically need n times the computational amount when generating the tables and n times the amount of data to store the tables, where n is the number of possible salt values.

Answer 2

TL;DR Skip to the last paragraph

Not quite. To encrypt the file, the passphrase and the one-time random salt are combined to encrypt the one-time random key. The salt must then be stored unencrypted along with the encrypted file data. Then, to decrypt the file, the passphrase and the salt (obtained from the encrypted file) are combined again to decrypt the one-time random key which is then used to decrypt the file.

According to an answer to your previous question, the purpose of the salt is to fix the problem that most passphrases will be rubbish (low entropy) and adding salt will help to improve them. This might sound unlikely to really work since the salt is available to an adversary but presumably it must increase the computational task of decrypting the one-time random key (i.e. similar to the situation with password hashing where salt means that there's no possibility of using rainbow tables to speed things up).

An answer to your previous question claimed that adding salt does help and there was a link to more information on the use of salt in cryptography: https://en.wikipedia.org/wiki/Salt_(cryptography) but that page only refers to the use of salt in password hashing, not key encryption. It doesn't sound convincing based on that statement alone. I'm sure that the authors of gpg must have good reasons for adding salt but I don't know what those reasons are (IANAC = I am not a cryptograper). This isn't the same situation as password hashing where the hash is stored and might become available to an adversary.

Having said that, strong passphrases definitely are essential. They are usually the weakest part of cryptography. Even with salted password hashing, a bad, short, well-known password will still be cracked quickly even without rainbow tables (unless bcrypt/scrypt/argon2 is used).

If you don't trust this salt technique (and I'm not suggesting that you should or shouldn't), use a great passphrase. A six-word Diceware passphrase should take the NSA 3,500 years to crack (even if they know it's a Diceware passphrase). Although it's only 77 bits of entropy. To get 128 bits of entropy, you need a ten-word Diceware password. A good place to get Diceware passwords is https://www.rempe.us/diceware/#eff but there are others.

Actually, forget the above. I think whoever told you that symmetric encryption involves a one-time random key was wrong. Having read the links thoughtfully provided by RubberStamp, it seems that the passphrase and the salt are the inputs to the s2k (string2key) key derivation function to create the symmetric key that is then used to encrypt the data. So there is no random key for symmetric encryption. I think whoever said that there was was confusing gpg's asymmetric encryption with its symmetric encryption. With asymmetric encryption, there's a random symmetric key which is encrypted using the public key and decrypted using the private key. With symmetric encryption, there is only the passphrase and the salt. So, yes, the strength is entirely dependant on the strength of the passphrase (see above). The purpose of the salt is not to strengthen the passphrase. It's to ensure that the actual key used to encrypt a file is unique to that file so that, even if you use the same passphrase to encrypt every file, and you are compelled by the authorities (or other threat actors) to hand over the key to an encrypted file, instead of giving them the passphrase which could decrypt all of your files, you can just give them the session key obtained with the --show-session-key option, and then they can use the --override-session-key option to decrypt the one file that they are interested in without automatically having access to all of your other files that may have been encrypted using the same passphrase. This makes much more sense. Actually, it was RubberStamp who said that symmetric encryption uses a random key but I didn't get that impression from reading the section of the RFC that was linked to. And if there was a random key, there would be no compelling need (that I can see) for a salt. The per-file uniqueness of the symmetric encryption key can be achieved either by a random key or by salt. It wouldn't require both.