Hello,

I have one question regarding the importance of salt in encryption.

As I understand, the salt is used to prevent dictionary attacks. Also,
it is recommended that the salt isn't always the same, and that it
should be randomly generated for each message. This random salt should
then be stored in the encrypted message, as a prefix for example, so
that it could  be retrieved during the decryption.

Now, I don't understand how this helps with dictionary attacks? For
example, if the attacker knows that the first 8 bytes for example are
salt, can't he simply modify his attacking program to include that salt
for each word he retrieves from the dictionary? The assumption here is
that the attacker gets access to the original encryption software as
well as the message.

Secondly, can someone explain how do the increased interations in
PasswordDeriveBytes help?

Thanks for your help,

V.

Hello vla***@gmail.com,

first of all - you are mixing some terms here

Encryption - the term salt isn't commonly used here, you may think of an
IV (initialization vector) which is used to start a feedback chain when using
CBC.

but i think you really mean hashing (e.g. for passwords) -

salted hashes are : H(salt+password)

reasons for salting

a) you are not leaking information, e.g. if alice and bob have the same password
- the resulting hash would be the same - not with salted hashes
b) there a tables of pre-computed hashes, so e.g. you encounter a hashed
password of "HJK)((bbnmm" - all you have to do is, look up that table for
the hash and retrieve the clear text value. If you use salted hashes, you
cannot use pre-computed tables, but have to calculate the hash on each try.
this takes time.

By using PasswordDeriveBytes with a high iteration count, you even raise
the bar

a) the attacked does not know the iteration count from looking at the hash
b) it takes even longer now to mount brute force/dictionary attacks - say
a simple hash needs 1 ms - and a iterated hash 1 s to calculate - this makes
password guessing really infeasible

this all depends of course on the password complexity and the computing power
the attackers has at his disposal.

you are basically buying time.

That said - go for salted, iterated hashes by using PasswordDeriveBytes -
or even better the new .NET 2.0 Rfc2898DeriveBytes class.


---------------------------------------
Dominick Baier - DevelopMentor
http://www.leastprivilege.com

Show quoteHide quote

Hello,

Maybe I wasn't clear enough. Let me try to explain a bit more... I
mentioned salting because I am reffering to a key generation based on a
password (PasswordDeriveBytes class). So, users use plain passwords to
generate a key which is then used for encryption. The salt is used on
that password, which should help prevent the attacker trying to get the
key by using the dictionary.

Now, I understand how this could be helpfull if I use a static salt and
then just transmit the message. The attacker really couldn't use his
dictionary, because he doesn't know the salt. But, what if the attacker
has access to the application that encrypts the messages? He can then
see the static/hardcoded salt and simply use it with his dictionary
when trying out the passwords.

If I want to avoid static salt, I have to generate it somehow, and then
store it so I can use it when decrypting, right? If I store it in a
message, again, whats the point? The attacker can again retrieve the
salt and use it with his dictionary.

I repeat, the assumption is that we are using an publicly available
software for encryption, so the attacker can decompile it or do
whatever he wants with it.

As for the iteration count... if I understood you correctly, all this
does is increase the time that it takes to generate the key from the
password? In other words, if I use 10 iterations to generate the
key/hash for the password, that key can ONLY be generated with the same
password and exactly 10 iterations? The attacker would have to run 10
iterations for each word in his dictionary to get the key, assuming he
even knows the correct iteration count used.

Thanks again for your help,

V.




Dominick Baier [ DevelopMentor ] wrote:
Show quoteHide quote

Hello vla***@gmail.com,

inline

again, the salt helps against precomputed tables

thats always the assumption in crypto. Only the key is secret - nothing else.

yes exactly, but we are talking 50.000 iterations or more - it is really
there to slow down the attacker

That all said - this is not the usual approach for encryption. To minimize
risk when using password based keys:

a) enforce strong, non dictionary passwords
b) encrypt the data using a randomly created key
c) encrypt the random key with the password generated key (add salt if you
like, but does not improve security dramatically IMO)
d) store the encrypted key

now an attacker has 2 choices

a) mount an attack against the encrypted data. infeasible as a full entropy
random key was used
b) mount an attack against the encrypted key. Also hard because it will not
be easy to distinguish between valid and invalid data when trying to decrypt.

makes sense?



Show quoteHide quote

Precomputed tables... now this really sheds some light. :) I didn't
think about the hashed dictionaries. Okay, I see now how any kind of
salting helps against that kind of dictionaries. On the other hand, if
the attacker uses plain dictionaries and computes the hash at runtime
(with my salt), then I can use high number of iterations to slow him
down a bit. Thanks for the explanation... :)

As for your suggestions... this means that the attacker will first have
to try to decrypt a key by lets say dictionary attack, and for each
attempt (each retrieved key) he has to try to decrypt the entire
message with that key. I'm not sure that this is dramatically better
than the original situation where the attacker tries to generate a key
and use that key to decrypt the message. The only advantage that I see
is that in your case, he will spend a bit more time, since he has to
decypt twice. At least thats my understanding, please correct me if i'm
wrong... :)

V.

Hello vla***@gmail.com,

yes - again that slows him down - and give the number of computations necessary
for these kind of attacks, this is an important factor

in general, try to keep the amount of data encrypted with a long term secret
as small as possible.

so what would be a practical solution

0) enforce password complexity (this is the most important step)
1) generate a key from the password, use salting and hashing and iterations
if you like
2) generate a random key
3) encrypt using random key
4) encrypt key using key from password

you should get a copy of "Schneier, Ferguson: Practical Cryptography"

---------------------------------------
Dominick Baier - DevelopMentor
http://www.leastprivilege.com

Show quoteHide quote

Okay, I will consider your approach. Just to be sure that I completely
understand, the increase in time comes from the first computation where
he retrieves a key based on his dictionary. Trying to decrypt with that
retrieved key is the same as if he immediately tried the key he got
based on his dictionary.

Is there a risk in generation of random key? As I understand, the
Random class from the .NET Framework generates pseudo-random numbers
and shouldn't be used in encryption.

Oh, one more thing I see as an advantage of random salt... with it the
resulting encrypted text will always be different even for the same
plain text.

Thanks for the book recommendation as well.

V.

Hello vla***@gmail.com,


don't use Random!

IIRC - the SymmetricAlgorithm class has built in key generation. For general
purpose random numbers use the RNGCryptoServiceProvider class.

as i said - there is another golden rule - never use a long term secret (=password)
directly to encrypt bulkloads of data.

---------------------------------------
Dominick Baier - DevelopMentor
http://www.leastprivilege.com

Show quoteHide quote

Can you explain a little bit this golder rule of never using a password
derived key on bulkloads of data?

Thanks again.

V.

Hello vla***@gmail.com,

there are cryptanalysis methods, which take a different approach than brute
forcing.

By looking at data (and the bigger data the better) you can get the key,
this is especially true if you reuse the key (=password) for different encrypted
data and if the key (=password) is weak.

get the schneier book :)

---------------------------------------
Dominick Baier - DevelopMentor
http://www.leastprivilege.com

Show quoteHide quote

Okay, thanks, I will try the method you suggested, and I'll get the
book. ;)

V.



Dominick wrote:
Show quoteHide quote

V, that is all correct.  That is the problem with using one-way hash
function for sending passwords.  The strength is still based on the strength
of the password.  If the password is easy, it will be crack fast via a
dictionary attack.  Once it is captured, they can process offline for as
long as it takes.  The other issue is your basically creating a password
equivilent.  Depending on the what is going on, I can do reply attacks or
maybe even other stuff.   What transport tech are you using?  WSE, sockets,
Web services, etc.?  If you want real security, I would take the next step
into real encryption and key exchange protocol of some kind.  WSE, for
example, has a few options built in.  I have some other stuff too, but need
to know more about your app as far as what the transport is.

Show quoteHide quote

Well, at the moment, I'm just gathering information and clearing few
unclear things... :) But, for our discussion, lets say the application
stores documents and there is a feature to store those documents
securely by encrypting them. The encryption or key storage shoudn't be
machine specific, so we can't use DPAPI or something like that to store
the key. So, we use passwords to generate a key. Users must also be
able to share those documents, provided they share the password as well
(lets ignore the transport of the password at the moment).

This is a basic scenarion. I am aware that the strength of the password
determines the strength of the entire process, and thats why I was
curious how much does the salting help. Not much, as I see... :)

You mentioned key exchange... I thought about asymetric encryption, but
this would mean that a document can be shared only by two people,
right? Also, there is the issue of private key storage. Lets assume
that the machine gets compromised, or that the application resides on
the server, shared computer, or something like that... I would be much
more comfortable knowing that there are no explicit trails of the key
on the machine and that the only way to retrieve it is by a dictionary
attack or by user torture ;)...

V.

So user A has a document and wants to put doc on Server.  Doc is encrypted
and sent to server.  User B, if allowed access, can download document.  Does
the document need to stay encrypted on the server?  Does it need to stay
encrypted on the client?  Is this the general idea, or something else?  Need
a bit more information.

Show quoteHide quote

OK, here is a simple use case... You are working on a document, on a
computer that's shared among different users. Doesn't have to be a
server, it can be a laptop, but it doesn't matter, as long as we have
in mind that other people have access to those documents. Upon save,
you are asked for a password, you specify it and the document is
encrypted and then saved. Each time you want to work on it, you
retrieve it in encrypted form to the application, decrypt it, make
changes, encrypt it and save it again... Now you email this document to
5-6 of your friends who know the password. They can open it, decrypt
it, make changes, encrypt it and return it to you. Ignore the usability
aspect of such poor document collaboration :), i'm just illustrating an
example what I would want from the encryption side of it... The
document should always be encrypted, except the time it's open in the
application (for simplicity, let's ignore the fact that the plain text
remains in the memory, or in swap file).

V.

Gotya now.  In this case, you don't need to store the password anyway, but
in your head.  Use PasswordDeriveBytes (or others) to gen your key and iv.
Then use Rijndael/AES to encrypt/decrypt the file.  If the wrong pw is
given, the decryption throws an exception.  If you forget the pw, your out
of luck.  Public knowledge of the source code, does not help them.  You can
use the CryptoStream class to help here.  Something like:

        private static void EncryptFile(string inPath, string outPath,
string password)
        {
            int blockSize = 4096;
            PasswordDeriveBytes pdb = new PasswordDeriveBytes(password,
Encoding.UTF8.GetBytes("salt"));
            RNGCryptoServiceProvider rng = new
RNGCryptoServiceProvider(password);
            byte[] key = pdb.GetBytes(16);
            byte[] iv = pdb.GetBytes(16);
            RijndaelManaged rm = new RijndaelManaged();
            ICryptoTransform encryptor = rm.CreateEncryptor(key, iv);

            using ( FileStream iFs = File.OpenRead(inPath) )
            using ( FileStream oFs = File.OpenWrite(outPath))
            using ( CryptoStream cs = new CryptoStream(oFs, encryptor,
CryptoStreamMode.Write))
            {
                byte[] buf = new byte[blockSize];
                int read = 0;
                while((read = iFs.Read(buf, 0, blockSize)) > 0 )
                {
                    cs.Write(buf, 0, read);
                }

                cs.FlushFinalBlock();
            }
        }

        private static void DecryptFile(string inPath, string outPath,
string password)
        {
            int blockSize = 4096;
            PasswordDeriveBytes pdb = new PasswordDeriveBytes(password,
Encoding.UTF8.GetBytes("salt"));
            byte[] key = pdb.GetBytes(16);
            byte[] iv = pdb.GetBytes(16);
            RijndaelManaged rm = new RijndaelManaged();
            ICryptoTransform decryptor = rm.CreateDecryptor(key, iv);

            using ( FileStream iFs = File.OpenRead(inPath) )
            using ( FileStream oFs = File.OpenWrite(outPath) )
            using ( CryptoStream cs = new CryptoStream(iFs, decryptor,
CryptoStreamMode.Read) )
            {
                byte[] buf = new byte[blockSize];
                int read = 0;
                while ( (read = cs.Read(buf, 0, blockSize)) > 0 )
                {
                    oFs.Write(buf, 0, read);
                }
            }
        }
Show quoteHide quote

Thank you William, I'm already using a similiar code based on this
article: http://www.obviex.com/Samples/EncryptionWithSalt.aspx but I
will look into your example.

V.

Cool.  Basically all he is doing there is prepending X random salt bytes to
the data and stripping it off after the decrypt.  That was a lot of code to
show a simple idea.  The same thing could be done just "using" Rijndael
instead of deriving another class from it:

        /// <summary>
        /// Encrypt data bytes using AES encryption.  Decrypt using Decrypt
and supply the same password and options.
        /// Set useRandomSalt to true to add random salt the beginning of
the data before encryption.  The Decrypt method will remove the same
        /// amount of bytes before returning the data.  If saltSize is set
to 0 and useRandomSalt is true, the actual saltSized used will be
        /// selected at random.  If saltSize is greater then 0, saltSize
number of random bytes will be prepended to the data.
        /// Call Decrypt to decrypt the results of this method.  You must
use the same password, paddingMode, useRandomSalt and saltSize that was
        /// used in the call to this method.
        /// </summary>
        /// <param name="data">Clear data to encrypt.</param>
        /// <param name="password">Password used to derive a key to encrypt
the data.</param>
        /// <param name="paddingMode">Encryption padding mode.</param>
        /// <param name="useRandomSalt">Set to true to add random salt to
the beginning of data.</param>
        /// <param name="saltSize">Number of salt bytes to include in data.
Use 0 to select a random number of bytes between 5 and 30.</param>
        /// <returns>The encrypted data.</returns>
        public static byte[] EncryptData(byte[] data, string password,
PaddingMode paddingMode, bool useRandomSalt, int saltSize)
        {
            if ( data == null || data.Length == 0 )
                throw new ArgumentNullException("data");
            if ( password == null )
                throw new ArgumentNullException("password");

            byte[] keySalt =
SHA1.Create().ComputeHash(Encoding.UTF8.GetBytes(password +
password.Length));
            Rfc2898DeriveBytes pdb = new Rfc2898DeriveBytes(password,
keySalt);

            RijndaelManaged rm = new RijndaelManaged();
            rm.Padding = paddingMode;
            ICryptoTransform encryptor =
rm.CreateEncryptor(pdb.GetBytes(16), pdb.GetBytes(16));

            if ( useRandomSalt )
            {
                if ( saltSize < 0 )
                    throw new ArgumentOutOfRangeException("saltSize must be
                bool dynamicSize = false;
                if ( saltSize == 0 )
                {
                    dynamicSize = true;
                    saltSize = Utils.GenerateRandomNumber(5, 30);
                }

                RNGCryptoServiceProvider rng = new
RNGCryptoServiceProvider();
                byte[] dynamicSalt = new byte[saltSize];
                rng.GetNonZeroBytes(dynamicSalt);

                if ( dynamicSize )
                {
                    data = Utils.JoinArrays(new byte[] {
(byte)dynamicSalt.Length }, dynamicSalt, data);
                }
                else
                {
                    data = Utils.JoinArrays(dynamicSalt, data);
                }
            }

            using ( MemoryStream msEncrypt = new MemoryStream() )
            using ( CryptoStream encStream = new CryptoStream(msEncrypt,
encryptor, CryptoStreamMode.Write) )
            {
                encStream.Write(data, 0, data.Length);
                encStream.FlushFinalBlock();
                return msEncrypt.ToArray();
            }
        }

        /// <summary>
        /// Decrypt data bytes using AES encryption.  This decrypts a byte[]
that was encrypted with the Encrypt method.
        /// If useRandomSalt is true, this method will remove the required
amount of salt bytes before returning the decrypted byte[].
        /// If saltSize is set to 0 and useRandomSalt is true, the actual
saltSized used will be
        /// determined from the data. If saltSize is greater then 0,
saltSize number of random bytes will be removed from the data after
decryption.
        ///
        /// This method is intended to be used in pair with EncryptData.
Call DecryptData with the same password, paddingMode, useRandomSalt and
saltSize
        /// that was used in the EncryptData method.
        /// </summary>
        /// <param name="data">Encrypted data to decrypt.</param>
        /// <param name="password">Password used to encrypt data.</param>
        /// <param name="paddingMode">Padding mode used to encrypt
data.</param>
        /// <param name="useRandomSalt">Use same value passed to
EncryptData.</param>
        /// <param name="saltSize">Use same value passed to
EncryptData.</param>
        /// <returns></returns>
        public static byte[] DecryptData(byte[] data, string password,
PaddingMode paddingMode, bool useRandomSalt, int saltSize)
        {
            if ( data == null || data.Length == 0 )
                throw new ArgumentNullException("data");
            if ( password == null )
                throw new ArgumentNullException("password");

            byte[] keySalt =
SHA1.Create().ComputeHash(Encoding.UTF8.GetBytes(password +
password.Length));
            Rfc2898DeriveBytes pdb = new Rfc2898DeriveBytes(password,
keySalt);

            RijndaelManaged rm = new RijndaelManaged();
            rm.Padding = paddingMode;
            ICryptoTransform decryptor =
rm.CreateDecryptor(pdb.GetBytes(16), pdb.GetBytes(16));

            using ( MemoryStream ms = new MemoryStream(data) )
            using ( CryptoStream cs = new CryptoStream(ms, decryptor,
CryptoStreamMode.Read) )
            {
                // Decrypted bytes will always be less then encrypted bytes,
so len of encrypted data will be big enouph for buffer.
                byte[] dec = new byte[data.Length];
                byte[] clearBuf;

                // Read as many bytes as possible.
                int read = cs.Read(dec, 0, dec.Length);
                if ( read < dec.Length )
                {
                    // Return a byte array of proper size.
                    clearBuf = new byte[read];
                    Buffer.BlockCopy(dec, 0, clearBuf, 0, read);
                }
                else
                    clearBuf = dec;

                if ( useRandomSalt )
                {
                    if ( saltSize < 0 )
                        throw new ArgumentOutOfRangeException("saltSize must
be >= 0.");
                    if ( saltSize == 0 )
                    {
                        saltSize = clearBuf[0];
                        saltSize = saltSize + 1;
                    }
                    return Utils.TrimStartBytes(clearBuf, saltSize);
                }
                else
                {
                    return clearBuf;
                }
            }
        }

This does add salt and could save a trip to the DB just to lookup salt.
However, I am unclear how must actual protection (if any) it adds to the
encrypted data.  If you have the source or know what is doing, this still
does not protect against brute force, but would only make it a bit more
work.  The strength still remains in the key.  Valery can probably comment
on this more.

Show quoteHide quote

I think he prepends the salt to the original plain text just to make
the final encrypted text always different, even for the same plain
text. What I learned from this discussion is that salt just slows
things down (and helps against basic dictionary attacks). Like you
said, the strength always remains in the key, or in the strength of the
password from which the key is derived.

I will use the salt combined with the larger number of password
iterations, but the emphasis will be on stronger passwords, although
I'm not sure will this be possible to enforce, since the app must be
very easy to use.

I'm curious, what do you, or Valery (or anyone else :) ), think about
the Dominic's proposal to encrypt everything with a random key, then
encrypt the random key with the key derived from the password, and then
simply combine the encrypted key with the encrypted message?

V.

Agree.

Yes.

I have used that before.  I encrypted the key with DPAPI so only the windows
user could decrypt the key.  In your case, however, I don't see the reason
you need to store any key.  Why not just prompt for the password and then
generate the key and try to decrypt.  Is there a reason you need to store
the key?

As stated in the scenario described, users should be able to exchange
documents across machines and across larger number of users. Thats the
reason why the key should travel with the message, asuming the random
key is used.

V.


William Stacey [MVP] wrote:
Show quoteHide quote

Hi,
Dominick and William have already gave you some answers, so here is just
some additional info for you.
you can check my older blog post:
http://www.harper.no/valery/PermaLink,guid,ea26f2f0-31f7-4707-89eb-191940d5bf63.aspx
where I discuss differences and relations and between salts and IV.

About passwords in cryptography - there are tons of resources, you can start
with http://www.google.com/search?hl=en&q=passwords+site%3Arsasecurity.com

and if you want latest and best mathematical treatment of passwords - here
some recent papers on subject from several best experts in the field:

Passwords and Offline Guessing Attacks.
O. Goldreich and Y. Lindell, "Session Key Generation using Human
Passwords Only."  Extended abstract in Proc. of Crypto 2001,
pp. 408-32, 2001.
J. Katz, R. Ostrovsky, and M. Yung, "Efficient and Secure
Authenticated Key Exchange Using Weak Passwords."  Extended abstract
in Proc. of Eurocrypt 2001, pp. 475-94, 2001.
R. Gennaro and Y. Lindell, "A Framework for Password-Based
Authenticated Key Exchange."  Extended abstract in Proc. of Eurocrypt
2003, pp. 524-43, 2003.
The full online versions are:
    http://www.wisdom.weizmann.ac.il/~oded/PS/passwd3.ps
    http://www.cs.umd.edu/~jkatz/papers/password.pdf
    http://www.cs.biu.ac.il/~lindell/PAPERS/hash-password.ps


-Valery.
http://www.harper.no/valery

<vla***@gmail.com> wrote in message
Show quoteHide quote

Hello Valery,

i just wanted to say "where is valery when you need him" :)


---------------------------------------
Dominick Baier - DevelopMentor
http://www.leastprivilege.com

Show quoteHide quote

Hi Dominick,
I had no time to follow newgroups during last two weeks - got literally
over-jammed by the work lately.
I have promised to deliver on project before global summit (don't want to
miss global summit for third time), so I was working something like 14+
hours/day. The good news is - looks that I'm going to summit after all :D.

-Valery.
http://www.harper.no/valery

Hello Valery,

cool. then see you there :)

---------------------------------------
Dominick Baier - DevelopMentor
http://www.leastprivilege.com

Show quoteHide quote

Valery, thank you for the excellent links and resources!

Blog... subscribed! ;)

V.

Anonymous access + Windows Authentication
Custom Security Permission & Security Attribute troubles
X.509 "Bad Key" error - EnvelopedCms.Decrypt()
RSACryptoServiceProvider
Strong Names Secure???
Windows authentication only
Sending raw sockets without administrative privileges?
Are .NET Caches Secure from Memory Dumps etc?
.NET 2.0: code access security / authentication
Windows Security pops up when executing javascript in an asp.net p