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