Opened 5 years ago

Closed 4 years ago

#13538 closed defect (fixed)

Stop signed left shift overflows in curve25519-donna (non-64-bit)

Reported by: teor Owned by:
Priority: Medium Milestone: Tor: 0.2.9.x-final
Component: Core Tor/Tor Version: Tor: unspecified
Severity: Normal Keywords: tor-router, integer-safety, lorax, intro
Cc: nickm Actual Points:
Parent ID: #17983 Points: small
Reviewer: Sponsor:

Description

Similarly to #13280, the curve25519-donna.c code contains some signed left shifts of negative numbers, which clang identifies as runtime errors. (This is only an issue with the generic code, not the 64-bit code.)

Under -ftrapv, this causes a trap/crash.

I've used a similar strategy to the one in #13280, where we automate the entire SHL32/SHL64 conversion using a perl script. The first commit sets up the macros.

The safe SHL32/SHL64 macros perform potentially overflowing left shifts in unsigned arithmetic.

I'll post a branch as soon as I've set up a change entry (for which I need the bug number).

Version: tor 2.6.?-alpha
git: fc5cab44724e8328e2186f22114625388f1c8f0d (Thu Oct 16 13:29:14 2014 -0400)

Child Tickets

Change History (18)

comment:1 Changed 5 years ago by nickm

Milestone: Tor: 0.2.6.x-final

Could you also submit this upstream for review? I don't want to get out of synch with Adam's code. (https://github.com/agl/curve25519-donna)

comment:2 Changed 5 years ago by teor

Branch: bug13538-donna-signed-shift
Repository: ​​​​https://github.com/teor2345/tor.git

I've committed the manual changes in one commit, and the automated change in the next.
The first commit adds the required macros, refactors common code into torint.h, and keeps the expanded perl script in scripts/maint in case we need to do this again.

I'll send a note upstream - what's the best way to do this on GitHub?

comment:3 Changed 5 years ago by nickm

I'll send a note upstream - what's the best way to do this on GitHub?

Replicate your changes in a fork of the curve25519-donna repository, then send a pull request?

comment:4 Changed 5 years ago by teor

Status: newneeds_review

I've just updated this branch with an entry in scripts/README and corrected the location of safe_shl.pl

comment:5 Changed 5 years ago by nickm

Looks plausible to me, though I need to stare at the perl a little longer. Please add a link here when you've posted this upstream to agl's repository?

comment:6 Changed 5 years ago by nickm

comment:7 Changed 5 years ago by teor

Thanks, Nick, and thanks for committing the trunnel code on the other task.
I expect to get back to coding tor mid-week, or next weekend. (Busy times.)

comment:8 Changed 5 years ago by teor

Owner: set to teor
Status: needs_reviewassigned

comment:9 Changed 5 years ago by nickm

Hm. Adam thought that the first patch was too messy for him. I just asked whether he might accept some other fix, or whether he's committed to invoking undefined behavior.

comment:10 Changed 5 years ago by teor

I agree it looks ugly, but I can't imagine a less messy patch.

We could duplicate all the signed variables (needed for multiplication and carry) as unsigned variables (needed for shifts), and somehow keep then in sync. But that could be just as ugly.

Or we could access the array as unsigned, but that is just as undefined, isn't it?

What C really needs is an unsigned-left-shift-cast-back-to-signed operator... or something!

comment:11 Changed 5 years ago by nickm

Milestone: Tor: 0.2.6.x-finalTor: 0.2.???

comment:12 Changed 4 years ago by teor

Keywords: lorax added
Owner: teor deleted
Severity: Normal

Building curve-25519 with -fwrapv would also resolve this issue.
If it becomes an issue with some compiler, let's resolve it that way.

(Note that --enable-gcc-hardening adds -fwrapv to CFLAGS, but it's not on by default.)

comment:13 Changed 4 years ago by teor

See #17983.

comment:14 Changed 4 years ago by teor

Parent ID: #17983

comment:15 Changed 4 years ago by nickm

Keywords: intro added

comment:16 Changed 4 years ago by nickm

Points: small

comment:17 Changed 4 years ago by nickm

Milestone: Tor: 0.2.???Tor: 0.2.9.x-final

Merged parent.

comment:18 Changed 4 years ago by nickm

Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.