Closed Bug 596056 Opened 14 years ago Closed 14 years ago

nanojit: random number generator needed for many hardening algorithms

Categories

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect, P1)

defect

Tracking

(Not tracked)

RESOLVED FIXED
flash10.1.x-Salt

People

(Reporter: rreitmai, Assigned: rreitmai)

References

Details

(Whiteboard: fixed-in-salt, fixed-in-nanojit, fixed-in-tracemonkey, fixed-in-tamarin)

Attachments

(2 files, 1 obsolete file)

      No description provided.
Blocks: 593517
Blocks: 595033
Blocks: 595034
Group: tamarin-security
Attached patch VMPI mac only changes (obsolete) — Splinter Review
Sample mac implementation of random number generator used for hardening.
Code cribbed from player Random.cpp class.

If this is an acceptable approach will provide code for other platforms.
Assignee: nobody → rreitmai
Attachment #475349 - Flags: feedback?(edwsmith)
Attachment #475349 - Flags: feedback?(lhansen)
Attachment #475349 - Flags: review?(puhley)
Attachment #475349 - Flags: review?(puhley) → feedback?(puhley)
Comment on attachment 475349 [details] [diff] [review]
VMPI mac only changes

Why is a good pseudorandom number generator that we know we can trust, rather than a platform layer that may not always be trustworthy, not the right choice here?  Given that we can seed an rng off the clock (we already have performance counter interfaces and time-of-day interfaces) we should be able to reduce the size of the porting interface, which seems like a good in itself.
Attachment #475349 - Flags: feedback?(lhansen) → feedback-
Comment on attachment 475349 [details] [diff] [review]
VMPI mac only changes

The VMPI api should only abstract the details of a platform-specific source of random entropy.  Building a pseudorandom generator seeded from that entropy doesn't need to be underneath the platform specific VMPI layer.
Attachment #475349 - Flags: feedback?(edwsmith) → feedback-
(In reply to comment #2)
> Comment on attachment 475349 [details] [diff] [review]
> VMPI mac only changes
> 
> Why is a good pseudorandom number generator that we know we can trust, rather
> than a platform layer that may not always be trustworthy, not the right choice
> here?  

I'm not sure that a good pseudorandom number generator is out of the question, but its not clear to me why we'd want to take that approach considering that the OS has support for what we need already.   And if it doesn't, then probably the benefit of these measures is questionable.

Also, when discussing this part of the feature with our security team I was directed to internal documentation that cited this approach.
(In reply to comment #3)
> Comment on attachment 475349 [details] [diff] [review]
> VMPI mac only changes
> 
> The VMPI api should only abstract the details of a platform-specific source of
> random entropy.  Building a pseudorandom generator seeded from that entropy
> doesn't need to be underneath the platform specific VMPI layer.

If I'm not mistaken, I think this relates to what Lars mentions above and yes, agreed that if we do take the approach of pRNG then we can shrink the VMPI interface to a single call that seeds the rng.    The remaining code will be platform independent.
Adding requirements sifted from email conversation with Ed:

"I'd like for the JIT to call some api that's specifically written for the purpose of generating random #s for jit-hardening.  the implementation of this jit-specific api can be portable, and needs to support being turned off, or put into a deterministic mode, for testing.

sketching it out:

// several JIT call sites need a source of random #s, for hardening.
... int noise = get_jit_noise(range);

// portable, JIT-specific code:
int get_jit_noise(int range) {
   /* i dont care if this is pRNG or RNG */
   /* implement code here, or call some pRNG that calls VMPI_entropy */
   return noise % range;
}

Lets assume the JIT calls get_jit_noise() 100 times per method, and 1000 methods per second, during startup.  If the range is 0..255, then the JIT needs 8*100*1000 = almost 1M random bits, per second, while it's running.  If all platforms can be expected to provide this, then get_jit_noise() could use VMPI_entropy directly.  If not, then we probably need a pRNG, called from, or implemented in, get_jit_noise().  

VMPI_entropy probably needs to be designed to handle the least-good platform.  I think the VMPI api could still use some API-crafting, but my main point was that it be as small as possible, and There needs to be an intermediary between the jit and whatever source of random bits we use.  And that source of random bits probably hides the call to VMPI_entropy."

Ok, will break the work apart into 2 pieces; a jit specific API call getJitNoise() which wraps the 2nd part which is whatever rng / VMPI interface we decide on. 

This is also nice in that it (somewhat) decouples the other bugs from this work.
Flags: flashplayer-qrb+
Priority: -- → P1
Target Milestone: --- → flash10.1.x-Salt
Status: NEW → ASSIGNED
Assembler to use a noise object in which the actual mechanics of how noise is being produced in abstracted by the client.

The noise object will often need to contain state so its convenient to derive from this class and build an object containing all the necessary state.

Also adding another patch which shows how clients of nanojit (e.g. CodegenLIR) are to interact with this interface.
Attachment #475349 - Attachment is obsolete: true
Attachment #476147 - Flags: review?(edwsmith)
Attachment #476147 - Flags: feedback?(nnethercote)
Attachment #475349 - Flags: feedback?(puhley)
I believe using the MathUtils randomness is sufficient for hardening purposes.
Attachment #476147 - Attachment is obsolete: true
Attachment #476148 - Flags: review?(edwsmith)
Attachment #476147 - Flags: review?(edwsmith)
Attachment #476147 - Flags: feedback?(nnethercote)
Attachment #476147 - Attachment is obsolete: false
Attachment #476147 - Flags: review?(edwsmith)
Attachment #476147 - Flags: review?(nnethercote)
One issue to consider is that using an arbitrary integer upper bound (i.e., the 'range' argument to getValue()) is that it requires taking an integer remainder to do the scaling.  I gather this is more expensive on ARM than one might suppose due to the lack of an integer divide instruction.  It is cheaper to mask off bits from a larger value in order to obtain powers-of-two ranges, or test single bit for a simple coin-toss when that would be sufficient.  Perhaps this doesn't really matter, but I'm just suggesting that we make the simplest and most easily statisfied demands on the platform service provider that will serve our purpose.
Do you mean for getValue(range) to return a value in the interval [0,range] or [0,range) ?  The code comments suggest the former, but the implementation in terms of MathUtils::Random() will yield the latter.  This absolutely critical for the binary coin-toss case.
Comment on attachment 476147 [details] [diff] [review]
introduce noise object

Seems fine.  In another patch you had this randomization stuff all within a #ifdef, should you do that here too?
Attachment #476147 - Flags: review?(nnethercote) → review+
(In reply to comment #11)
> In another patch you had this randomization stuff all within a
> #ifdef, should you do that here too?

They should have all been switched over to use the runtime config flag.  I'll make sure before landing.
Attachment #476147 - Flags: review?(edwsmith) → review+
Comment on attachment 476148 [details] [diff] [review]
codegenlir changes to support Noise

Make sure to fix tags in CodegenLIR.h before submitting.  (the new "JITNoise noise" field is indented too far)
Attachment #476148 - Flags: review?(edwsmith) → review+
Comment on attachment 476148 [details] [diff] [review]
codegenlir changes to support Noise

It looks like JITNoise never initializes its randomSeed field.  Am I missing something from another patch?

Testing with valgrind would catch this.

Does the int-modulo in MathUtils::Random() rank anywhere near the top of jit self+callee time?  if so, I second Bill's suggestion, to use power-of-two values and mask with & instead of %.
Comment on attachment 476148 [details] [diff] [review]
codegenlir changes to support Noise

Setting R- because the "randomSeed" field isn't initialized; Since valgrind would have caught this, please run the fix through valgrind to be sure.
Attachment #476148 - Flags: review+ → review-
Comment on attachment 476148 [details] [diff] [review]
codegenlir changes to support Noise

aha, it is initialized by MathUtils::initRandom() which calls VMPI_getTime().  so we just need a review that gettimeofday is indeed enough entropy.
Attachment #476148 - Flags: review- → review+
Please add a comment in the JITNoise constructor that we're assuming MathUtils::initRandom will provide enough entropy for our requirements.  Note that since we can jit several methods per millisecond, its possible for several methods to be jit-compiled with the same seed value.  (not sure if this is bad, just noting).  and that assumes VMPI_getTime() has 1-ms accuracy, which it may not.  e.g. on windows it might be 10ms, and its possible for a whole SWF to be compiled in that amount of time.
an attacker could call new Date() or getTimer() and wait for time to reach a special value, then trigger jit-compilation; this could enable them to control the initial seed.
Rick is this still open and is there anyway that it can be tested via test media or is this something that would be "verified" by verifying that code has been checked in?
Yes it is open and the code has *not* landed.

The discussion over alternatives to MathUtils pRNG has not been resolved.
Looks like this was checked into Salt in P4 CL 721542...still more to do?
Whiteboard: fixed-in-salt
http://hg.mozilla.org/tracemonkey/rev/afb8a2b88e56
Whiteboard: fixed-in-salt → fixed-in-salt, fixed-in-nanojit, fixed-in-tracemonkey
http://hg.mozilla.org/mozilla-central/rev/afb8a2b88e56
Status: ASSIGNED → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
Whiteboard: fixed-in-salt, fixed-in-nanojit, fixed-in-tracemonkey → fixed-in-salt, fixed-in-nanojit, fixed-in-tracemonkey, fixed-in-tamarin
Blocks: 608798
How should this be tested in Tamarin?
You need to log in before you can comment on or make changes to this bug.