Date: Fri, 14 Nov 2014 14:45:02 -0800
I was recently pointed to
https://trac.torproject.org/projects/tor/ticket/13538 and the patch to fix
it, at
https://github.com/teor2345/tor/commit/ced74e0144e967f838416e6af92cba65c007d89b
.
The underlying algorithm stores 26-bit signed numbers in int64s, and tries
to guarantee that its operations never overflow. However, because the
numbers are signed and possibly negative, C++ insists that they never be
left-shifted, even if the arithmetic result would fit in the range of the
type, and so the programmers can't get undefined behavior (and the
resulting -ftrapv errors) in the cases they want.
We could suggest that the programmers explicitly multiply by a power of 2
instead, but they're using the <<s at least partly to get constant-time
operation, and relying on multiplication for this would depend even more on
implementation details than they already are.
Separately, a related piece of code uses a signed right-shift to repeat the
sign bit across all the bits of a number:
https://boringssl.googlesource.com/boringssl/+/e18d821dfcc32532caeeb1a2d15090672f592ce3/crypto/internal.h#157.
This is implementation-defined rather than undefined, so the programmers
can probably use #if to check for the behavior they expect, as at
https://github.com/teor2345/tor/blob/ced74e0144e967f838416e6af92cba65c007d89b/src/ext/curve25519_donna/curve25519-donna.c#L466
Is there space to improve the situation here?
I've pasted the entire contents of [expr.shift] from N4140 below, for
context:
5.8 Shift operators [expr.shift]
1 The shift operators << and >> group left-to-right.
*shift-expression:*
*additive-expression*
*shift-expression << additive-expression*
*shift-expression >> additive-expression*
The operands shall be of integral or unscoped enumeration type and integral
promotions are performed. The type of the result is that of the promoted
left operand. The behavior is undefined if the right operand is negative,
or greater than or equal to the length in bits of the promoted left operand.
2 The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits
are zero-filled. If E1 has an unsigned type, the value of the result is E1
× 2^E2, reduced modulo one more than the maximum value representable in the
result type. Otherwise, if E1 has a signed type and non-negative value, and
E1 × 2^E2 is representable in the corresponding unsigned type of the result
type, then that value, converted to the result type, is the resulting
value; otherwise, the behavior is undefined.
3 The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an
unsigned type or if E1 has a signed type and a non-negative value, the
value of the result is the integral part of the quotient of E1/2^E2. If E1
has a signed type and a negative value, the resulting value is
implementation-defined.
https://trac.torproject.org/projects/tor/ticket/13538 and the patch to fix
it, at
https://github.com/teor2345/tor/commit/ced74e0144e967f838416e6af92cba65c007d89b
.
The underlying algorithm stores 26-bit signed numbers in int64s, and tries
to guarantee that its operations never overflow. However, because the
numbers are signed and possibly negative, C++ insists that they never be
left-shifted, even if the arithmetic result would fit in the range of the
type, and so the programmers can't get undefined behavior (and the
resulting -ftrapv errors) in the cases they want.
We could suggest that the programmers explicitly multiply by a power of 2
instead, but they're using the <<s at least partly to get constant-time
operation, and relying on multiplication for this would depend even more on
implementation details than they already are.
Separately, a related piece of code uses a signed right-shift to repeat the
sign bit across all the bits of a number:
https://boringssl.googlesource.com/boringssl/+/e18d821dfcc32532caeeb1a2d15090672f592ce3/crypto/internal.h#157.
This is implementation-defined rather than undefined, so the programmers
can probably use #if to check for the behavior they expect, as at
https://github.com/teor2345/tor/blob/ced74e0144e967f838416e6af92cba65c007d89b/src/ext/curve25519_donna/curve25519-donna.c#L466
Is there space to improve the situation here?
I've pasted the entire contents of [expr.shift] from N4140 below, for
context:
5.8 Shift operators [expr.shift]
1 The shift operators << and >> group left-to-right.
*shift-expression:*
*additive-expression*
*shift-expression << additive-expression*
*shift-expression >> additive-expression*
The operands shall be of integral or unscoped enumeration type and integral
promotions are performed. The type of the result is that of the promoted
left operand. The behavior is undefined if the right operand is negative,
or greater than or equal to the length in bits of the promoted left operand.
2 The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits
are zero-filled. If E1 has an unsigned type, the value of the result is E1
× 2^E2, reduced modulo one more than the maximum value representable in the
result type. Otherwise, if E1 has a signed type and non-negative value, and
E1 × 2^E2 is representable in the corresponding unsigned type of the result
type, then that value, converted to the result type, is the resulting
value; otherwise, the behavior is undefined.
3 The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an
unsigned type or if E1 has a signed type and a non-negative value, the
value of the result is the integral part of the quotient of E1/2^E2. If E1
has a signed type and a negative value, the resulting value is
implementation-defined.
Received on 2014-11-14 23:45:23