Opened 5 years ago

Closed 5 years ago

#13280 closed defect (fixed)

Stop signed left shift overflows in ed25519

Reported by: teor Owned by:
Priority: High Milestone: Tor: 0.2.6.x-final
Component: Core Tor/Tor Version: Tor: unspecified
Severity: Keywords: tor-router ed25519
Cc: nickm Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

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

Child Tickets

Attachments (8)

ed25519-left-shift-overflow-test-warnings.log (19.9 KB) - added by teor 5 years ago.
Log of warnings generated by ed25519 tests under clang without -ftrapv
0001-Stop-signed-left-shifts-overflowing-in-ed25519.patch (33.2 KB) - added by teor 5 years ago.
Perform all left shifts on potentially negative values using unsigned types
transform.pl (311 bytes) - added by nickm 5 years ago.
0002-Allow-unsafe-left-shifts-in-ed25519-using-DUNSAFE_SI.patch (2.9 KB) - added by teor 5 years ago.
Add -DUNSAFE_SIGNED_LSHIFT to revert to old behaviour and code
bug13280_all_preprocessed_files.patch (445.5 KB) - added by teor 5 years ago.
Not for application! A patch containing the full preprocessed source of old, new-unsafe, and new-safe
bug13280_comparison.diff (15.2 KB) - added by teor 5 years ago.
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
0003-Stop-ed25519-8-bit-signed-left-shift-overflowing.patch (2.0 KB) - added by teor 5 years ago.
Fix an 8-bit signed left shift, standardise existinf 8-bit fix to SHL8()
transform.2.pl (499 bytes) - added by nickm 5 years ago.

Download all attachments as: .zip

Change History (21)

Changed 5 years ago by teor

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

comment:1 Changed 5 years ago by Sebastian

did you forget to attach a patch?

comment:2 Changed 5 years ago by teor

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

Changed 5 years ago by teor

Perform all left shifts on potentially negative values using unsigned types

comment:3 Changed 5 years ago by teor

Status: newneeds_review

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

comment:4 Changed 5 years ago by nickm

Milestone: Tor: 0.2.6.x-final
Priority: normalmajor

comment:5 Changed 5 years ago by nickm

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.

Changed 5 years ago by nickm

Attachment: transform.pl added

comment:6 Changed 5 years ago by nickm

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.)

comment:7 Changed 5 years ago by nickm

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

Changed 5 years ago by teor

Add -DUNSAFE_SIGNED_LSHIFT to revert to old behaviour and code

Changed 5 years ago by teor

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

Changed 5 years ago by teor

Attachment: bug13280_comparison.diff added

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

comment:8 Changed 5 years ago by teor

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.)

comment:9 Changed 5 years ago by teor

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.

Changed 5 years ago by teor

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

comment:10 Changed 5 years ago by teor

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

Changed 5 years ago by nickm

Attachment: transform.2.pl added

comment:11 Changed 5 years ago by nickm

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.

comment:12 Changed 5 years ago by teor

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.

comment:13 Changed 5 years ago by nickm

Resolution: fixed
Status: needs_reviewclosed

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

Note: See TracTickets for help on using tickets.