Re: [openpgp] 4880bis: Update S2K

In summary, I would be more concerned with users getting wrong 
impression that somehow their low-entropy password will get "upgraded" 
by a new S2K scheme. There is a cost of change, and I think if the 
OpenPGP does change the S2K, the choice should bring concrete additional 
benefits.
Here is why:

1. One should keep in mind what value the iterative methods like S2K or 
PDKDF actually provide. Assuming that the number of iterations is c and 
the password space has 2^n entries, the work factor for legitimate users 
is c*2^n, as opposed to 2^n without iterated calculations. Doubling the 
c slows the computation time in half for the attacker as well as for the 
the password holder; this is equivalent to adding 1 bit of extra entropy 
to password space. This offers one of the worst cost-benefits to 
legitimate users. Just compare this with any other computational 
security schemes, such as public key crypto (exponential v.s. polynomial 
complexity).
2. The Iterated S2K is essentially a

   M = M1 || M2 || M2 || M2 || ... || M2, where M1 includes the salt.
   S2K = Hash( M )

(assuming that hash output is no smaller than the number of bits 
required for the key).
In many respects, this construction is easier to analyze. There is no 
attempt to "fix" the hash function as in some other schemes. Imagine a 
sponge construction like SHA3 Keccak or many other hash functions with 
sufficient internal state (probably including SHA-256), which should be 
fine to handle the above task.
3. The max number of iterations that the S2K counter encodes is c = 
16+15^(15) + 6 > 2^58
For SHA1 S2K this is over 2^53 invocations and about the same for 
SHA-256. SHA-256 can only hash 2^64 bytes. Likewise, AES-256, as any 
16-byte block cipher, is considered insecure after about the same number 
of invocations due to the birthday bounds limitation.
This is plenty of iterations for the foreseeable future.

4. One can argue that the S2K construction is one of the strongest in 
active use today. If we assume that it's possible to recover M given the 
S2K as defined the above, i.e. to invert a hash function (even assuming 
somehow that S2K value is known, which it is not) then many existing 
schemes will be broken. For example, an attacker that is able to get M 
from S2K can use the same method to recover the authentication key K 
from an HMAC MAC value, leading to the forgery of MAC.
The proof is easy: use the "oracle" that returns M from S2K = Hash( M )  
to recover the HMAC key as follows: get M' = K ^ opad | H( K ^ ipad | m 
), which reveals the K as M' ^ opad with appropriate truncation.
The other problem one might try to solve with S2K construction is how 
the scheme behaves with non-uniform hash functions. ( Imagine that a 
hypotherical Hash() often returns all-zero output for random M). 
However, we don't intend to use these hash functions, will quickly 
replace them if we discover that we do.
It's hard to see that S2K and PBKDF are materially different. ( In less 
formal language: PBKDF2 should have the same resulting weakness, but 
long before this the collision resistance will likely be broken ).
Both schemes have the same problems. For example, both have an 
unfortunate property that if the two invocations of PBKDF (or S2K) use 
the same salt and password but different counters c1, c2, the S2K or 
PBKDF can be calculated from the previous values with just |c2-c1| 
iterations. I.e. it seems like an oversight that c was not hashed. As 
was noted by others, it may be desirable to increase memory footprint 
requirements.
HKDF is not designed to handle S2K. (It's main target are things like 
derivation of an AES key from a DH shared secret). At least it needs the 
stretching step defined.
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp