On Tue, Jun 20, 2000 at 07:50:11PM +0200, Niels Möller wrote:
[...]
> On the other hand, if you don't care about making the hashing
> artificially slow, but have a reasonable amount of entropy to start
> with and just want to stretch it, you may want to look at the way ssh2
> does that. (Say you have a 100+ bit shared secret and need to get two
> 256 bit twofish keys and 2 iv:s, 768 bits in all). That is specified
> in draft-ietf-secsh-transport-07.txt, the relevant section is
>
> : If the key length in longer than the output
> : of the HASH, the key is extended by computing HASH of the concatenation
> : of K and H and the entire key so far, and appending the resulting bytes
> : (as many as HASH generates) to the key. This process is repeated until
> : enough key material is available; the key is taken from the beginning of
> : this value. In other words,
> :
> : K1 = HASH(K || H || X || session_id) (X is e.g. "A")
> : K2 = HASH(K || H || K1)
> : K3 = HASH(K || H || K1 || K2)
> : ...
> : key = K1 || K2 || K3 || ...
>
> Here, K is the secret being stretched, and H is an "exchange hash"
> that can probably be ignored in this context. The X is different for
> the keys that are generated from the same secret.
>
> I haven't tried to analyze this. Of course, I'm interested in any
> weaknesses in it.
With usual hash functions (Merkle/Damgård construction), you're
wasting entropy if there are more than 2^B possible values for K
where B is the size of the output of the compression function.
The reason is that the hash construct always has the same internal
state when K is hashed in. (Actually, if K is a random B-bit
value, you still have to expect to lose 0.5 bits or so due to
collisions, but that's a minor issue.)
This problem would be avoided by setting
K1 = HASH(K || H || X || session_id) (X is e.g. "A")
K2 = HASH(K1 || H || K)
K3 = HASH(K2 || H || K)
...
key = K1 || K2 || K3 || ...
because in this variant K is applied at different states of the hash
construct.
