Stop signed left shift overflows in ed25519

The new ed25519 code contains some signed left shifts of negative numbers, which clang identifies as runtime errors.

Under -ftrapv, this causes a trap/crash.

Without -ftrapv, this causes about 100 warnings during the tests like: crypto/ed25519_simple: src/ext/ed25519/ref10/ge_scalarmult_base.c:42:48: runtime error: left shift of negative value -2 (log attached)

A patch is attached that performs potentially overflowing left shifts in unsigned arithmetic. Macros SHL64 and SHL32 are defined for convenience.

This is my first patch using git format-patch with a changes entry - let me know if it needs revising.

Version: tor 2.6.?-alpha git: 5190ec0bc4c22d7bab756e21db6e357ba07379c4

changed milestone to %Tor: 0.2.6.x-final

added component::core tor/tor ed25519 milestone::Tor: 0.2.6.x-final priority::high resolution::fixed status::closed tor-router type::defect version::tor unspecified labels

Trac:
ed25519-left-shift-overflow-test-warnings.log

Log of warnings generated by ed25519 tests under clang without -ftrapv

did you forget to attach a patch?

Just give me 30 seconds more - this is my first time, and I needed the bug number for the name of the changes file :-)

Trac:
0001-Stop-signed-left-shifts-overflowing-in-ed25519.patch

Perform all left shifts on potentially negative values using unsigned types

Sebastian, I've attached the patch - thanks for the quick response.

Trac:
Status: new to needs_review

Trac:
Priority: normal to major
Milestone: N/A to Tor: 0.2.6.x-final

This seems like a good idea to do. One question we'll need to think about:

Since this is a pretty mechanical transformation, can we verify its correctness mechanically? I'm thinking about diffing the assembly output of the two cases, or writing a script (with coccinelle? with perl?) to replicate the transformation, or something like that. Otherwise, verifying all 200 changed lines by eye seems like the kind of thing I might make a mistake with.

Trac:
transform.pl

I've attached a probably-not-quite-right perl script that tries to reproduce this patch. Does it? If not, is it the script's fault, or the patch's fault?

(Known bugs in the script: it only matches at most one shift per line. It doesn't match variables declared in arguments. It doesn't match variables declared in unexpected ways, such as if more than one is declared in a line.)

(I'd check it myself, but today is a family day, and we need to go to the aquarium)

Trac:
0002-Allow-unsafe-left-shifts-in-ed25519-using-DUNSAFE_SI.patch

Add -DUNSAFE_SIGNED_LSHIFT to revert to old behaviour and code

Trac:
bug13280_all_preprocessed_files.patch

Not for application! A patch containing the full preprocessed source of old, new-unsafe, and new-safe

Trac:
bug13280_comparison.diff

Not to be applied! A diff of the old and new-unsafe sources. Behaviour is identical apart from cast to unsigned char in ed25519_ref10_select

The attached patch 0002-Allow-unsafe-left-shifts-in-ed25519-using-DUNSAFE_SI.patch reverts to the previous behaviour on -DUNSAFE_SIGNED_LSHIFT.

We can verify the ed25519 changes by diffing: cpp -E -DUNSAFE_SIGNED_LSHIFT new_file.c cpp -E old_file.c

Results:

• 28 non-significant bracket changes, as order of operations (<< before |) preserves semantics;
• preprocessor line number/header order changes; and
• whitespace changes.

The diff also shows one intentional cast to unsigned char in ed25519_ref10_select(). This cast resolves an 8-bit signed shift overflow (there's no macro for 8-bit shifts).

The 28 bracket and 1 unsigned char cast changes are much easier to verify by hand than the original ~400 changes.

Alternately, the unsigned char cast could be removed, and then the assembler/object/executable code should compare and behave identical. (But I like the preprocessor method.)

Nick, your script looks like it does the opposite of cpp -E -DUNSAFE_SIGNED_LSHIFT (which is handy).

The only existing (relevant) left shifts that it misses are two performed on signed char types in ge_scalarmult_base.c. I had also missed one of these. (I've attached a patch which standardises both of these shifts using new SHL8().)

All other left shifts are performed on (signed) constants or unsigned types.

Trac:
0003-Stop-ed25519-8-bit-signed-left-shift-overflowing.patch

Fix an 8-bit signed left shift, standardise existinf 8-bit fix to SHL8()

Should I squash 0003 into 0001, or are 3 patches OK?

Trac:
transform.2.pl

I've attached a new version of my script... did your old patch miss fe_frombytes.c ? My script added some shifts there, but I didn't seem them in your patches. That and the hand-written change in ge_scalarmult_base.c were the only differences I detected.

I've tried to split the patches up into human-generated and machine-generated portions in a new branch. It's called "bug13280" in my public repository. (info at https://gitweb.torproject.org/nickm/tor.git )

Additionally, I've run 'gcc -O2 -S' on master before and after applying this patch series, and found no changes in the generated assembly. This is looking pretty safe to me now. If it still looks okay to you, I'll merge it.

Yes, I missed the carry shifts in fe_frombytes.c (why send a person to do a machine's job?)

Looks great - we have the single manual change in ge_scalarmult_base.c, and the rest are automatic. I'd only expect to see changes in the assembly under -ftrapv.

Sounds good to me. Merged this to master. Thanks!

Trac:
Status: needs_review to closed
Resolution: N/A to fixed

closed

mentioned in issue #13284 (moved)

mentioned in issue #13538 (moved)

moved to tpo/core/tor#13280 (closed)

mentioned in issue tpo/core/tor#13284 (closed)

mentioned in issue tpo/core/tor#13538 (closed)