# Cryptanalysis of Nonlinear Table Lookup

I am trying to derive a symmetric key based on a master key, combined with a simple string. Based on my limited knowledge, it seems that something like PBKDF2 would do that for me in a well-defined way:

DK = PBKDF2(PRF, Password, Salt, c, 256)

• Password = master key
• Salt = simple string
• c = number of iterations
• DK is the 256 bit derived key

However, I am working in a very constrained embedded environment, so a high number for 'c' is not an option. Now for my question:

Would I improve security if I used a low value for 'c', but I did some kind of table lookup as a final step, such that

DK_final = table[F(DK,i) MOD size]

• Assume DK is twice is large as DF_final, so 256 bits and 128 bits respectively
• table = a large table of randomly chosen bytes (more than 4000 elements)
• F(DK,i) = a simple function that takes the i'th 2 byte pair from the string DK
• size = the number of elements in the table
• DK_final = the final derived key, 128 bits in this example

I could not find any published material on such a method, besides a vague reference here. However, no indication of cryptanalysis was given.

Any help on such a scheme would be appreciated, if only to warn against it: It seems that the general rule of thumb is never invent you own clever idea with it comes to cryptography.

1. If the master key is strong (e.g. random 256-bit key), $c=1$ is fine, or you can use HKDF. A high number of iterations is only needed when you derive the key from a password or other low entropy string.

2. If you can store a 4000 element table securely, you could just use random keys instead of derived ones.

3. If you need the derived key to depend on a low entropy master key, you could use a randomly generated salt you keep secure. In that case leaking the salt will allow a brute force or dictionary attack on the master key, but without knowing the salt an attacker cannot attack it.

Optimally, your situation is 1. and you don't need to do anything special. 2. is also a secure alternative, but requires you to store more keys. You should only use 3. if you have no other options, and in that case you should use as high a $c$ as you can.

Now the actual question, is such a table secure?

If you have a large enough table that is only used for one key, it will not hurt the quality of the derived key. However, if that isn't the case, it may, since the keys will share the nonuniform probability distribution defined by the table.

An attacker who has the table could of course derive the key just as easily as when no table was used, so it is no better than using a random secret salt like I suggested in 3. above. So I wouldn't recommend using it.

• Thanks. I believe my master key to be very strong. However, I must derive a key since the 'salt' in my example above is a simple string supplied by the user. I think the implication is that I my derived keys will be based on a strong master key, but they will be closely related due to the weak salt? – Fanus Aug 18 '14 at 9:45
• @Fanus, salts only need to be unique, their weakness does not matter – they can even be assumed to be known by the adversary. If they are not unique, any number of iterations will not prevent keys from colliding. – otus Aug 18 '14 at 12:55