Opened 4 years ago

Closed 2 years ago

#17815 closed defect (wontfix)

[PATCH] eliminate modulo bias in OpenBSD's malloc

Reported by: logan Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-03-unspecified-201612
Cc: logan@… Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

Currently, there is a modulo bias introduced by using:

i = rand() % bp->free;

Is there a reason not to import arc4random_uniform() which takes care of modulo bias ?

In the mean time, attached is a small patch that reduces the modulo bias.

Child Tickets

Attachments (2)

tor_rand.diff (458 bytes) - added by logan 4 years ago.
tor_rand_reduce_modulo_bias
tor_rand_2.diff (608 bytes) - added by logan 4 years ago.

Download all attachments as: .zip

Change History (13)

Changed 4 years ago by logan

Attachment: tor_rand.diff added

tor_rand_reduce_modulo_bias

comment:1 Changed 4 years ago by logan

Wrong patch uploaded. Re-uploading.

comment:2 Changed 4 years ago by logan

Sorry, it's the correct patch, from the right branch.

I got the formula from here:
http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx

comment:3 Changed 4 years ago by teor

Milestone: Tor: 0.2.8.x-final
Status: newneeds_revision
Type: enhancementdefect

Isn't the correct approach to do what Tor's crypto_rand_int() function does, and discard biased inputs until you get a result?

That's the only way I know to ensure you don't get a biased result.

comment:4 Changed 4 years ago by logan

Cc: logan@… added

Uploading my latest patch. I am hitting a build issue. I don't have any of the "warning: implicit declaration", as I'm using "crypto.h", but at link time, it has issues:

src/common/libor.a(OpenBSD_malloc_Linux.o): In function `malloc_bytes':
/home/logan/tor/src/ext/OpenBSD_malloc_Linux.c:1191: undefined reference to `crypto_rand_int_range'
collect2: error: ld returned 1 exit status
Makefile:2880: recipe for target 'src/tools/tor-resolve' failed
make[1]: * [src/tools/tor-resolve] Error 1
make[1]: Leaving directory '/home/logan/tor'
Makefile:1868: recipe for target 'all' failed
make:
* [all] Error 2

Changed 4 years ago by logan

Attachment: tor_rand_2.diff added

comment:5 Changed 4 years ago by nickm

(Haven't had a hard look at the patch here, but the openbsd malloc isn't "hardened" -- it's just meant to give improved memory usage under some loads.)

comment:6 Changed 4 years ago by logan

Summary: [PATCH] eliminate modulo bias in OpenBSD's hardened malloc[PATCH] eliminate modulo bias in OpenBSD's malloc

comment:7 in reply to:  4 Changed 4 years ago by teor

Status: needs_revisionneeds_information

Replying to logan:

Uploading my latest patch. I am hitting a build issue. I don't have any of the "warning: implicit declaration", as I'm using "crypto.h", but at link time, it has issues:

src/common/libor.a(OpenBSD_malloc_Linux.o): In function `malloc_bytes':
/home/logan/tor/src/ext/OpenBSD_malloc_Linux.c:1191: undefined reference to `crypto_rand_int_range'
collect2: error: ld returned 1 exit status
Makefile:2880: recipe for target 'src/tools/tor-resolve' failed
make[1]: * [src/tools/tor-resolve] Error 1
make[1]: Leaving directory '/home/logan/tor'
Makefile:1868: recipe for target 'all' failed
make:
* [all] Error 2

tor-resolve doesn't link in crypto.o.

I'm not sure how to proceed with this patch:

  • I am concerned that calling crypto_rand_int() every time we allocate bytes might slow down performance dramatically. Are there malloc() tests in src/test/bench you could use to verify this?
  • I don't think we want to make every tor tool depend on OpenSSL (crypto.o depends on OpenSSL).

Alternately:

  • If we simply call rand(), there's no point in removing modulo bias, because many rand() implementations have significant biases.

I think we need to answer these questions before proceeding:

Does tor operate with guarded memory allocations by default (or is it a commonly used feature)?

Do we need the random locations of guard pages (and guarded allocations) to be cryptographically random and/or unbiased?

comment:8 Changed 3 years ago by nickm

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

It is impossible that we will fix all 261 currently open 028 tickets before 028 releases. Time to move some out. This is my first pass through the "needs_revision" and "needs_information" tickets, looking for things to move to ???.

Note that in most cases, if these tickets get the requested revisions done in time for the 0.2.8 merge window, they could get considered for review and merge in 0.2.8.

comment:9 Changed 3 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:10 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:11 Changed 2 years ago by nickm

Resolution: wontfix
Status: needs_informationclosed

I'm not planning to take unnecessary changes to openbsd_malloc. The bias in this case does not appear to be harmful.

Note: See TracTickets for help on using tickets.