SLIP-0010 : change to derive 1...n-1 integers without needing retries about slips HOT 4 CLOSED

(ping authors @jhoenicke @prusnak )

from slips.

Where exactly we use d = x mod n?

I only see parse_256(I_L) + k_par (mod n) = 0 which is different and cannot be replaced.

from slips.

With bip32, the goal was to have no bias at all. They wanted to even avoid the tiny bias of the modulo operation that ca. 2^128 numbers are twice as likely as the others.

BTW, the 0 is no problem, the problem is if I_L would exactly equal -k_par, which the modulo n-1 trick cannot avoid (you could of course use modulo (n-1) and add 1 if I_L is >= -k_par, but that just makes it more complicated and it would be hard to make an implementation side-channel resistant).

I'm not sure if the bias that modulo would give is security relevant for secp256k. Let's face it, even though some numbers are twice as likely (the ones between 0 and 2^256 - n), it is still very unlikely that one of these numbers will ever be taken in the next hundred years. It's not even feasible to brute force a test case for this.

from slips.

Ah, ok, I have misinterpreted what's going on. I can see now why the logic needs to be the way it is. (Interestingly, if the ultra-rare case does happen that parse_256(I_L) == -k_par then not only is that key position useless, but in fact k_par has been accidentally compromised to anyone who knows the xpub.)

If child keys had been derived via multiplication rather than addition, then the solution I suggested would have been helpful. I.e., calculate 0 < d < n from x = parse_256(I_L) but then use k_i = d * k_par mod n and K_i = d * K_par, which always yields a good key without needing retries. That said, I am unsure whether multiplicative derivation is as secure as additive derivation.

from slips.