search

cfrg / draft-irtf-cfrg-bls-signature

32 stars 16 forks source link

Backwards compatability of KeyGen #28

Closed CarlBeek closed 4 years ago

CarlBeek commented 4 years ago

In #26, KeyGen was updated to never return SK=0. This is achieved by repeatedly hashing the seed until a non-zero SK is found. This change was made in a non-backwards compatible way. Specifically, eth2 has tooling that uses the same methods for converting IKM into a SK in addition to this change requiring changes to BLS test vectors.

For all real world use cases, the new KeyGen could have been made backwards compatible by hashing the seed only if the SK happens to be 0. This also has the benefit of saving one hash per key derived.

This would be possible if the seed hashing that occurs in line 4 below occurred after line 7.

1. salt = "BLS-SIG-KEYGEN-SALT-"
2. SK = 0
3. while SK == 0:
4.     salt = H(salt)
5.     PRK = HKDF-Extract(salt, IKM || I2OSP(0, 1))
6.     OKM = HKDF-Expand(PRK, key_info || I2OSP(L, 2), L)
7.     SK = OS2IP(OKM) mod r
8. return SK
JustinDrake commented 4 years ago

This would be possible if the seed hashing that occurs in line 4 below occurred after line 7.

Or even after line 5?

@kwantam: Could the extraneous round of hashing (which I guess is also a minor performance hit) be rolled back in a v5?

kwantam commented 4 years ago

The issue is that, from a security perspective, the extra hash is not extraneous. Per Hugo and the HKDF paper, using a structured salt string with HKDF violates its security analysis. So, for the sake of being conservative, we hash the structured string before using it as a salt.

As discussed in the KeyGen section, it is completely fine if you want to use an alternative KeyGen function, including one that assumes that using a structured salt is OK, but making this more aggressive assumption doesn't seem appropriate for an IETF document when avoiding it is relatively simple.

Regarding performance: there should be no hit, other than maybe 12 bytes of extra static storage: you can always precompute H("BLS-SIG-KEYGEN-SALT-").

JustinDrake commented 4 years ago

the extra hash is not extraneous. Per Hugo and the HKDF paper, using a structured salt string with HKDF violates its security analysis. So, for the sake of being conservative, we hash the structured string before using it as a salt.

Gotcha, thanks for the explanation :)

Regarding performance: there should be no hit

Right 👍

CarlBeek commented 4 years ago

Or even after line 5?

I didn't propose this as then the hash would be calculated and never used.

Per Hugo and the HKDF paper, using a structured salt string with HKDF violates its security analysis.

Thanks for clarifying, @kwantam, I was unaware of this.

Regarding performance: there should be no hit

Not really worried about this, it just felt like an extra reason to put the hash after the SK calcs.