8.1 Low-level functions for cryptography

The functions prefixed with mpn_sec_ and mpn_cnd_ are designed to perform the exact same low-level operations and have the same cache access patterns for any two same-size arguments, assuming that function arguments are placed at the same position and that the machine state is identical upon function entry. These functions are intended for cryptographic purposes, where resilience to side-channel attacks is desired.

These functions are less efficient than their “leaky” counterparts; their performance for operands of the sizes typically used for cryptographic applications is between 15% and 100% worse. For larger operands, these functions might be inadequate, since they rely on asymptotically elementary algorithms.

These functions do not make any explicit allocations. Those of these functions that need scratch space accept a scratch space operand. This convention allows callers to keep sensitive data in designated memory areas. Note however that compilers may choose to spill scalar values used within these functions to their stack frame and that such scalars may contain sensitive data.

In addition to these specially crafted functions, the following mpn functions are naturally side-channel resistant: mpn_add_n, mpn_sub_n, mpn_lshift, mpn_rshift, mpn_zero, mpn_copyi, mpn_copyd, mpn_com, and the logical function (mpn_and_n, etc).

There are some exceptions from the side-channel resilience: (1) Some assembly implementations of mpn_lshift identify shift-by-one as a special case. This is a problem iff the shift count is a function of sensitive data. (2) Alpha ev6 and Pentium4 using 64-bit limbs have leaky mpn_add_n and mpn_sub_n. (3) Alpha ev6 has a leaky mpn_mul_1 which also makes mpn_sec_mul on those systems unsafe.

Function: mp_limb_t mpn_cnd_add_n (mp_limb_t cnd, mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

Function: mp_limb_t mpn_cnd_sub_n (mp_limb_t cnd, mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

These functions do conditional addition and subtraction. If cnd is non-zero, they produce the same result as a regular mpn_add_n or mpn_sub_n, and if cnd is zero, they copy {s1p,n} to the result area and return zero. The functions are designed to have timing and memory access patterns depending only on size and location of the data areas, but independent of the condition cnd. Like for mpn_add_n and mpn_sub_n, on most machines, the timing will also be independent of the actual limb values.

Function: mp_limb_t mpn_sec_add_1 (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n, mp_limb_t b, mp_limb_t *tp)

Function: mp_limb_t mpn_sec_sub_1 (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n, mp_limb_t b, mp_limb_t *tp)

Set R to A + b or A - b, respectively, where R = {rp,n}, A = {ap,n}, and b is a single limb. Returns carry.

These functions take O(N) time, unlike the leaky functions mpn_add_1 which are O(1) on average. They require scratch space of mpn_sec_add_1_itch(n) and mpn_sec_sub_1_itch(n) limbs, respectively, to be passed in the tp parameter. The scratch space requirements are guaranteed to increase monotonously in the operand size.

Function: void mpn_sec_mul (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t an, const mp_limb_t *bp, mp_size_t bn, mp_limb_t *tp)

Function: mp_size_t mpn_sec_mul_itch (mp_size_t an, mp_size_t bn)

Set R to A * B, where A = {ap,an}, B = {bp,bn}, and R = {rp,an+bn}.

It is required that an >= bn > 0.

No overlapping between R and the input operands is allowed. For A = B, use mpn_sec_sqr for optimal performance.

This function requires scratch space of mpn_sec_mul_itch(an, bn) limbs to be passed in the tp parameter. The scratch space requirements are guaranteed to increase monotonously in the operand sizes.

Function: void mpn_sec_sqr (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t an, mp_limb_t *tp)

Function: mp_size_t mpn_sec_sqr_itch (mp_size_t an)

Set R to A^2, where A = {ap,an}, and R = {rp,2an}.

It is required that an > 0.

No overlapping between R and the input operands is allowed.

This function requires scratch space of mpn_sec_sqr_itch(an) limbs to be passed in the tp parameter. The scratch space requirements are guaranteed to increase monotonously in the operand size.

Function: void mpn_sec_powm (mp_limb_t *rp, const mp_limb_t *bp, mp_size_t bn, const mp_limb_t *ep, mp_bitcnt_t enb, const mp_limb_t *mp, mp_size_t n, mp_limb_t *tp)

Function: mp_size_t mpn_sec_powm_itch (mp_size_t bn, mp_bitcnt_t enb, size_t n)

Set R to (B raised to E) modulo M, where R = {rp,n}, M = {mp,n}, and E = {ep,ceil(enb / GMP_NUMB_BITS)}.

It is required that B > 0, that M > 0 is odd, and that E < 2^enb.

No overlapping between R and the input operands is allowed.

This function requires scratch space of mpn_sec_powm_itch(bn, enb, n) limbs to be passed in the tp parameter. The scratch space requirements are guaranteed to increase monotonously in the operand sizes.

Function: void mpn_sec_tabselect (mp_limb_t *rp, const mp_limb_t *tab, mp_size_t n, mp_size_t nents, mp_size_t which)

Select entry which from table tab, which has nents entries, each n limbs. Store the selected entry at rp.

This function reads the entire table to avoid side-channel information leaks.

Function: mp_limb_t mpn_sec_div_qr (mp_limb_t *qp, mp_limb_t *np, mp_size_t nn, const mp_limb_t *dp, mp_size_t dn, mp_limb_t *tp)

Function: mp_size_t mpn_sec_div_qr_itch (mp_size_t nn, mp_size_t dn)

Set Q to the truncated quotient N / D and R to N modulo D, where N = {np,nn}, D = {dp,dn}, Q’s most significant limb is the function return value and the remaining limbs are {qp,nn-dn}, and R = {np,dn}.

It is required that nn >= dn >= 1, and that dp[dn-1] != 0. This does not imply that N >= D since N might be zero-padded.

Note the overlapping between N and R. No other operand overlapping is allowed. The entire space occupied by N is overwritten.

This function requires scratch space of mpn_sec_div_qr_itch(nn, dn) limbs to be passed in the tp parameter.

Function: void mpn_sec_div_r (mp_limb_t *np, mp_size_t nn, const mp_limb_t *dp, mp_size_t dn, mp_limb_t *tp)

Function: mp_size_t mpn_sec_div_r_itch (mp_size_t nn, mp_size_t dn)

Set R to N modulo D, where N = {np,nn}, D = {dp,dn}, and R = {np,dn}.

It is required that nn >= dn >= 1, and that dp[dn-1] != 0. This does not imply that N >= D since N might be zero-padded.

Note the overlapping between N and R. No other operand overlapping is allowed. The entire space occupied by N is overwritten.

This function requires scratch space of mpn_sec_div_r_itch(nn, dn) limbs to be passed in the tp parameter.

Function: int mpn_sec_invert (mp_limb_t *rp, mp_limb_t *ap, const mp_limb_t *mp, mp_size_t n, mp_bitcnt_t nbcnt, mp_limb_t *tp)

Function: mp_size_t mpn_sec_invert_itch (mp_size_t n)

Set R to the inverse of A modulo M, where R = {rp,n}, A = {ap,n}, and M = {mp,n}. This function’s interface is preliminary.

If an inverse exists, return 1, otherwise return 0 and leave R undefined. In either case, the input A is destroyed.

It is required that M is odd, and that nbcnt >= ceil(log(A+1)) + ceil(log(M+1)). A safe choice is nbcnt = 2 * n * GMP_NUMB_BITS, but a smaller value might improve performance if M or A are known to have leading zero bits.

This function requires scratch space of mpn_sec_invert_itch(n) limbs to be passed in the tp parameter.

This document was generated on March 31, 2014 using texi2html 5.0.