| Re: How to generate cryptographically-secure random big-integers? [message #170986 is a reply to message #170217] |
Mon, 13 December 2010 20:09   |
seeWebInstead
Messages: 14
Registered: October 2010
Karma:
|
Junior Member |
|
|
> From: Erwin Moller <Since_humans_read_this_I_am_spammed_too_m...@spamyourself.com>
>> I need to generate a random integer uniformly distributed from 0 to
>> 165704257009980305087908956205223296585688096305918417966291411066008093135 190411324365527113804568013399264982255120906812142560021321323875432044092 494966970218269418334085525290028472777766273110227504712320
Note: This is used to covertly bootstrap confidential public-key
parameters (i.e. the private exponent) across an insecure link to a
remote PHP/MySQL hosting service. All subsequent public-key
activity by my scripts there *depend* on that random number *not*
being discernable by anyone whatsoever. Any "random" number
generator not well enough documented as to where the information
comes from and who can possibly view it, is unacceptable for this
purpose.
(Regarding an idea I rejected a priori:)
> I noticed you used:
> srand(time());
> But the manual says:
> ===================================================================
> Note: As of PHP 4.2.0, there is no need to seed the random number
> generator with srand() or mt_srand() as this is now done automatically.
> ===================================================================
> But the manual is not very clear on the exact implementation it uses
> when you do not call srand().
Indeed, not documented that it's *really* random and unobservable
by anyone else. In fact typically such system-provided random
number generates are really pseudo-random, and if somebody knows
the algorithm they can repeatedly sample it and notice any gap, and
deduce that some other user got in there to take the gap-value, and
thus this user can *know* which pseudo-random value the *other*
user got.
> But there are a few other approaches you could consider:
> 1) /dev/random
Not generally available on free PHP/MySQL hosting sites, and not
documented as absolutely secure in any case.
> And in case you are on Linux, have a look at /dev/random/
> http://en.wikipedia.org/wiki//dev/random
> It says: "It allows access to environmental noise collected from device
> drivers and other sources.", which sounds promising, as in impossible
> for the man-in-the-middle to predict.
Ditto, not available, not documented as secure.
> 2) Use one of these online random generators, based on nuclear fission.
> But this is probably a bad idea since that communication can be heard by
> the man-in-the-middle.
I have no access to the PHP/MySQL hosting services I'm using,
except via FTP and my own PHP scripts. Definitely no way to attach
a hardware device to their server located unknown location. Let me
check with ARIN:
nslookup blackapplehost.com => 69.162.86.3 => Limestone Networks (Dallas, TX)
nslookup netii.net => 208.43.151.204 => SoftLayer Technologies (Dallas, TX)
Wow, both of them in the same city!! All other PHP/MySQL hosting
services in other places have ceased working, including
freeweb7.com which was working a month ago off-and-on but has been
off the past couple weeks, but seems to have come back online today:
nslookup freeweb7.com => 75.126.176.160 => SoftLayer Technologies (Dallas, TX)
Weird!!
> 3) If you are really serious about randomness, you could buy one
> of these cards that generate true random numbers.
What good would that do? I have no physical access to any of the
PHP/MySQL hosting services in Dallas.
> Another approach (I don't like) that was mentioned in the user
> contributions on the PHP manual was: request some webpage and measure
> the time needed (micros) to fetch it. And use that number as the seed.
Not possible because the PHP/MySQL hosting services don't allow
external network connections from PHP scripts. Also, that's too
slow. Sampling microsecond time a few hundred times takes only
about 5 microseconds per call, total just a few milliseconds, and
gives me all the entropy I need to shrink the inverval down by 210
orders of magnitude (676 bits of entropy).
> One last thing: Why not use mt_rand()? It seems to be better:
> http://nl2.php.net/manual/en/function.mt-rand.php
"It uses a random number generator with known characteristics using
the ; Mersenne Twister, which will produce random numbers four
times faster than what the average libc rand() provides."
which begs the question where it gets the starting seed from. No
guarantee the seed is truly random and secure. Most likely it uses
the system clock (just once or twice) as the seed, which has only a
narrow range of possible seed values at one time when hostile
forces might be observing my activities and trying to deduce what
seed value I used via mt_rand. By comparison, no way they can guess
(within reasonable time, like a million years) what exact sequence
of hundreds of system-microsecond-time sample-differences I'm using
per the algorithm I described earlier.
Anyway, I've finished covertly bootstrapping private exponents for
public-key cryptosystems onto all the PHP/MySQL servers I'm
currently using for NewEco, and using these installed cryptosystems
I've uploaded additional parameters to some of the servers, and I'm
now implementing public-key server-to-server SOAP RPC over HTTP as
a way to pass signed+encrypted messages from one server to another
as part of my distributed NewEco application. For a high-level
description of the PK-SS-SOAP-RPC process, see:
http://www.rawbw.com/~rem/Pub/EcoWeb/newInterNetCooperative.php?see=pksat
which is part of http://TinyURL.Com/NewEco
I haven't yet written a spec for the details of how it will work,
but basically:
- User selects task and amount of funds to put into escrow (done for test).
- Escrow account is created, and that amount of funds moved from
user's main accout to escrow account.
- XML messages is created, containing voucher for funds and service
request, and is signed by originating host (#1) and encrypted for
destination host (#2), and written to local file (done)
- HTTP redirection from sending host#1 to receiving host#2, with
query string telling name of local (host#1) file (next to implement)
To implement later:
- Receiving host (#2) issues call-back to retrieve the message, decrypt
it, verify signature, parse XML.
- Host#2 executes request, keeping track of time consumed.
- Host#2 generates XML message containing receipt and results, signs#2,
encrypts#1.
- Host#2 issues call-forward to deposit the return-message on host#1.
- HTTP redirection from host#2 to host#1, with query string telling
name of local (host#1) return-message file.
- Host#1 fetches message, decrypts, verifies signature, parses XML,
refunds "change" to user and credits "charge" to master account
or other service provider, delivers results to user.
Note: Call-back is needed because host#1 can't initiate any
non-local InterNet connections, so host#1 can't act as HTTP client
talking directly to host#2 as with traditional SOAP over HTTP, and
HTTP redirection works only for GET method, so the message can't be
transmitted via redirection, and bandwidth is costly on cellphones,
so POST form can't be used to transmit the entire message from
host#1 via client to host#2.
By the way, does anybody reading this thread know of anyone other
than myself who is implementing, or who might like to implement,
public-key server-to-server SOAP RPC over HTTP?
|
|
|
|
Calendar
Search
Help
Members
Register
Login
Home
]