Hello,
I've noticed the following typical code sequence:
ecc_modp_mul(ecc, t, x, y); cy = mpn_sub_n(dest, t, ecc->p.m, ecc->p.size); cnd_copy(cy, dest, t, ecc->p.size);
What is the benefit of this piece of code over the following one?
ecc_modp_mul(ecc, t, x, y); memcpy(dest, t, ecc->p.size * sizeof(mp_limb_t));
Does mpn_sun_n/cnd_copy add any form of side channel attach protection?
On Thu, 2019-10-31 at 15:07 +0300, Dmitry Eremin-Solenikov wrote:
Hello,
I've noticed the following typical code sequence:
ecc_modp_mul(ecc, t, x, y); cy = mpn_sub_n(dest, t, ecc->p.m, ecc->p.size); cnd_copy(cy, dest, t, ecc->p.size);
What is the benefit of this piece of code over the following one?
ecc_modp_mul(ecc, t, x, y); memcpy(dest, t, ecc->p.size * sizeof(mp_limb_t));
Does mpn_sun_n/cnd_copy add any form of side channel attach protection?
cnd_copy provides side-channel protection when you want to make the copy conditional.
In this case the copy is conditional to the carry being returned from the subtraction, your code does not look equivalent.
Simo.
чт, 31 окт. 2019 г. в 17:00, Simo Sorce simo@redhat.com:
On Thu, 2019-10-31 at 15:07 +0300, Dmitry Eremin-Solenikov wrote:
Hello,
I've noticed the following typical code sequence:
ecc_modp_mul(ecc, t, x, y); cy = mpn_sub_n(dest, t, ecc->p.m, ecc->p.size); cnd_copy(cy, dest, t, ecc->p.size);
What is the benefit of this piece of code over the following one?
ecc_modp_mul(ecc, t, x, y); memcpy(dest, t, ecc->p.size * sizeof(mp_limb_t));
Does mpn_sun_n/cnd_copy add any form of side channel attach protection?
cnd_copy provides side-channel protection when you want to make the copy conditional.
In this case the copy is conditional to the carry being returned from the subtraction, your code does not look equivalent.
After ecc_modp_mul() call value of `t` should be already lower than `ecc->p.m`. So subtract will always return a carry.
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
After ecc_modp_mul() call value of `t` should be already lower than `ecc->p.m`. So subtract will always return a carry.
No, the reduction after mul and sqr doesn't produce canonical results. They only ensure that than t < 2*m. The pattern you see is needed in places where a canonical representation, t < m, is required.
Result is the same as with if (mpn_cmp(...)) mpn_sub_n(...), but an unconditional subtraction + cnd_cpy makes that logic side-channel silent.
Regards, /Niels
Hello,
чт, 31 окт. 2019 г. в 17:55, Niels Möller nisse@lysator.liu.se:
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
After ecc_modp_mul() call value of `t` should be already lower than `ecc->p.m`. So subtract will always return a carry.
No, the reduction after mul and sqr doesn't produce canonical results. They only ensure that than t < 2*m. The pattern you see is needed in places where a canonical representation, t < m, is required.
Ok, thanks for the clarification. Is it only the case for 521-bit curve and for redc-based reduce? Because for all other cases 2 * p > B, so mul (and sqr) can not return value greater or equal to 2*m (= 2 * p).
Result is the same as with if (mpn_cmp(...)) mpn_sub_n(...), but an unconditional subtraction + cnd_cpy makes that logic side-channel silent.
Yes, this part is understandable. I was concerned about not copying the result straight ahead.
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Ok, thanks for the clarification. Is it only the case for 521-bit curve and for redc-based reduce? Because for all other cases 2 * p > B, so mul (and sqr) can not return value greater or equal to 2*m (= 2 * p).
Not sure I understand the question. For a reduced value t (output of ecc->mod or ecc->reduce), we always have both r < B (fits in ecc->size limbs) and r < 2 m.
Now, it's true that for many of the ecc-related moduli, we have 2 m > B, so that r < B ==> r < 2 m, but that makes little difference in this context. In either case, to reduce r to the canonical range 0 <= r < m, one conditional subtraction is needed.
One complication is that ecc_mod_add and ecc_mod_sub do *not* ensure r < 2 m, only r < B. So for moduli where 2 m < B, it's possible to get outputs t >= 2m.
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
Dmitry Eremin-Solenikov -
nisse＠lysator.liu.se -
Simo Sorce