Half a croissant, on a plate, with a sign in front of it saying '50c'
h a l f b a k e r y
Tip your server.

idea: add, search, annotate, link, view, overview, recent, by name, random

meta: news, help, about, links, report a problem

account: browse anonymously, or get an account and write.

user:
pass:
register,


                                                 

Please log in.
Before you can vote, you need to register. Please log in or create an account.

Certified random data

System for explicitly dealing with randomness in the eyes of the law
  (+5, -2)
(+5, -2)
  [vote for,
against]

So the "Regulation of Investigatory Powers Act 2000" is a set of laws in the UK which, among other things:

//... requires persons to supply decrypted information (which had been previously encrypted by the owner) and/or the cryptographic key to government representatives. Failure to disclose these items is a criminal offence, with a maximum penalty of two years in jail.//
(wikipedia, see link)

Obviously this effectively makes storing files of random bits on your computer a liability - since it's not possible to directly prove that random data isn't encrypted data. Which is an annoyance to those who want to store random bits for whatever legitimate reason.

I propose a solution involving a trusted service providing authenticated random bits for those who wish to remain beyond reproach (and the long, random arm of the law).

The system is actually quite simple. 'True', high-quality random bits are generated using one of the variety of approaches (radioactive isotope decay (as at 'hotbits'), atmospheric radio noise (as at 'random.org'), a computer randomness generator addon or whatever. The bits are routinely analysed using a suite of statistical techniques to ensure that they do appear to be random, and suspected failures are conservatively discarded. The remaining bits are stored until required.

Random bits are supplied in a number of formats, including one-off files of arbitrary size over the internet, and batches of files from a set of specified sizes on CD, or hard disk. Each format can be supplied as a matching pair for a reasonable surcharge.
Each supplied unit includes a text manifest which specifies the file ID codes (which are also their filenames) and a cryptographic hash function of its contents, plus software for verifying the hash of any file (and various other housekeeping cryptographic functions) in unix, windows and mac, and GPL sourcecode. Each unit also has an integral token which corroborates its destruction - supplied CDs, for example could have a serial number printed radially across the disc in an area which does not hold random data (this may require a straightforward modification of the storage format), or a peelable strip which initiates destruction of the data layer.

The service-provider discards the random bits immediately after media production (or online file transfer) but retains a copy of the manifest which they undertake to serve and certify on request.

For example, suppose Alice wishes to communicate securely with Bob. Alice purchases a pair of CDs containing 5,000 100kb files, and gives one to Bob, and agree how they will use the data.
The random files are copied to their hard-disks, and the supplied software immediately verifies that each file is uncorrupted. Any corrupted files (which don't match the recorded hash) are immediately and completely deleted by overwriting with patterned data (0xff, 0x00, 0x55, 0x99, etc).
Both Alice and Bob cut out and store the serial number slice of the CD, but destroy the remainder securely.
When Alice wishes to talk to Bob privately, she can use a file as a one time pad, then securely delete the encrypted message, as described above. On receipt, Bob can decrypt and read the message, and subsequently delete it. Deleting the random data-file improves the security of the message, but isn't essential to remain verifiable by law.
If either Alice or Bob's computer is seized, they can prove that the random data-files really are random by referring the demand to the randomness generator service, who will corroborate the hash code, proving that the data is truely random.

Loris, Dec 06 2011

RIPA http://en.wikipedia...ory_Powers_Act_2000
[Loris, Dec 06 2011]

Decrypt anything ... to anything Decrypt_20anything_..._2e_20to_20anything
Another option, which I believe fits the letter of the law. [Loris, Dec 08 2011]

http://en.wikipedia...iki/Benford%27s_law [not_morrison_rm, Dec 08 2011]

A Million Random Digits http://www.amazon.c...-reviews/0833030477
I didn't read the whole idea, so this might not be what you're looking for. [Worldgineer, Dec 09 2011]

'Predictably random' public keys can be cracked http://www.theregis...16/crypto_security/
-> true randomness important for most people in modern society [Loris, Feb 16 2012]

[link]






       Respectfully nominate this idea for most boring of the week.
rcarty, Dec 07 2011
  

       Hey, thanks for not saying 'year'. At least it's only Wednesday.   

       Sorry if it's rather dry, I do generally try to write with more humour. However, I've found that you need to be explicit and precise on the technical details in this specific area.
Loris, Dec 07 2011
  

       heheh [+]
FlyingToaster, Dec 07 2011
  

       //for most boring of the week.//   

       Hey, this is HB, that just sounds like a challenge...   

       Actually, that's sadly like a steganography project of mine, but turned out to need 128 Gb of files, so bit of a no-no USB memory stick wise...
not_morrison_rm, Dec 07 2011
  

       Careful: If the government intercepts the one-time pad encrypted file sent between Bob and Alice, can't they demand to have it decrypted? If Bob and Alice did delete the original message and the one-time pad, would they be able to avoid the 2-year prison term by summarizing what they remember of the message, or does the fact that they are unable to produce either the original or the key guarantee a prison term?   

       If someone uses TrueCrypt to store encrypted data in unused areas of the hard drive, it is not possible to prove that there is not encypted data stored there. Therefore the government should be able to demand the password for any random data on the hard drive, not just files. Even if the user gives one password, unless that accounts for all random data on the hard drive there could be additional encrypted files, so the governemtn can choose to jail any such person for 2 years. Therefore, to stay above reproach, all unused portions of your hard drive should be initialized with non-random data, and any random data should be certified by [Loris] Inc. If you really want to store encypted data, show up in the alley behind Loris' diner at 4:57am. For a small fee, your CD of "random" data will be fed into the "random" number generator at Loris Inc. and certified for you.
scad mientist, Dec 07 2011
  

       Another thought: if the government demands the decryption key under RIPA, what stops someone from writing a benign but private sounding message of the same length, XORing it with the message that was intercepted, and providing that XORed copy as a one-time pad decryption key? Since you can't PROVE that this is not what you did, are you still on the hook? That means that either this portion of RIPA is unenforcable for anyone who knows how to make a fake one-time pad, or else one-time pads are illegal. Maybe they could be legal if you use certified random data for your key, since it proves that you didn't make up the key after the fact, but like I pointed out in the last annotation: how do you trust the certification process?   

       By the way, [+] for an interesting concept.
scad mientist, Dec 07 2011
  

       //Careful: If the government intercepts the one-time pad encrypted file sent between Bob and Alice, can't they demand to have it decrypted? If Bob and Alice did delete the original message and the one-time pad, would they be able to avoid the 2-year prison term by summarizing what they remember of the message, or does the fact that they are unable to produce either the original or the key guarantee a prison term?//
I don't know. If they demand it after you've deleted the random file, I guess you're relying on them accepting that the fact that the file is missing from the appropriate directory, plus the evidence that you've destroyed the original medium. Given how OTPs work, that's a plausible explanation (and it would also be true).
However,assuming that the message is innocuous - just private (commercially sensitive, personal communication etc) rather than actually a terrorist plot), it might be better to retain the random-datafile and just destroy the encrypted message. That does however mean that any intercepted messages are readable if your hard disc can be read by the attacker. You could of course encrypt the files - and be willing to 'decrypt' them (back to the original randomness) if you receive a legal order.
  

       //If someone uses TrueCrypt to store encrypted data in unused areas of the hard drive, it is not possible to prove that there is not encypted data stored there.//
Indeed. My interpretation is that this means that unless you have used up all space in the volume and can supply decryption codes, you are still open to the risk.
  

       //Therefore the government should be able to demand the password for any random data on the hard drive, not just files.//
I don't know. It's not like politicians understand the technology.
  

       //Therefore, to stay above reproach, all unused portions of your hard drive should be initialized with non-random data.//
That's probably a good idea to be on the safe side.
  

       //if the government demands the decryption key under RIPA, what stops someone from writing a benign but private sounding message of the same length, XORing it with the message that was intercepted, and providing that XORed copy as a one-time pad decryption key?//
Apparently nothing.
I've actually covered that before - it's one of the proposals I alluded to in my first comment. see link.
Loris, Dec 08 2011
  

       Is there an application other than cryptography for truly random data? (For Monte Carlo simulations, one uses -- by preference, in fact, for reproducibility -- pseudorandom.)   

       In what I take to be the spirit of this idea, I propose the Government issue entropy licenses, akin to USAan federal DEA licenses for controlled substances. Only registered, trusted individuals and organization would be allowed to have randomness, and only as much as they needed, and they would be required to keep strict records of where it went.
mouseposture, Dec 08 2011
  

       //Is there an application other than cryptography for truly random data? (For Monte Carlo simulations, one uses -- by preference, in fact, for reproducibility -- pseudorandom.)//   

       Yes.   

       Monte Carlo simulations can need *excellent* pseudorandom numbers, so you might still need a little random data to seed them somewhere.
"True randomness is still preferred where unpredictability is paramount." (wikipedia - "Random number generation")
  

       Apart from that : gambling, statistical sampling, selection, various security processes (eg, secure passwords), analysis (eg pattern detection testing) and many other minor uses (art, divination ...). Perhaps surprisingly many uses, in fact.
Loris, Dec 08 2011
  

       //"True randomness is still preferred where unpredictability is paramount." //   

       Erm, I was a bit surprised to find out that even in genuinely random number there is a preponderance of numbers that start with 1.   

       To me, that looks less random than genuinely random should be, but obviously I'm in the wrong there somewhere? See Benford's law link
not_morrison_rm, Dec 08 2011
  

       Benford's law give "the distribution expected if the logarithms of the numbers (but not the numbers themselves) are uniformly and randomly distributed." (Wikipedia).   

       It doesn't apply to uniformly randomly distributed numbers.   

       "Random number" is a concept (like white noise) that needs to be qualified a bit. "Genuinely" random numbers are infinitely big; "genuine" white noise is infinitely loud. What is usually (such as in the context of this idea) meant by a random number is a number drawn from a theoretical population having a uniform distribution over a finite range.
spidermother, Dec 08 2011
  

       //"Genuinely" random numbers are infinitely big...//   

       (pedant mode activated) That's not really correct. A number can be considered random only within specified parameters. For example, a fairly rolled die[1] gives a genuine random number in the set (1,2,3,4,5,6), a tossed coin gives a genuine one-bit number (if you assign values of zero and one to the sides) and so on.   

       Consider the alternative. There are infinite natural numbers, and obviously adding a digit yields 10 times more numbers. Therefore an 'unspecified' random number would be expected to have infinitely many. Of course, half of them would be negative. There are infinitely many numbers between adjacent integers, so obviously a random number would be expected to be irrational.
However, there are also infinitely many complex numbers at each real number position, so any number without an imaginary part is infinitely unlikely to be "genuinely" random. Now, it's possible to extend complex numbers into higher dimensions...
I hope you see where I'm going.
  

       [1] a dice.
Loris, Dec 09 2011
  

       //That's not really correct// Fair enough; but we agree that "random number" needs qualification, right? For example, it's only a particular type of random distribution, with a sufficiently wide range, that exhibits Benford's law.   

       It's not so important for the idea, because //random bits// clearly specifies the distribution; I was just trying to help [not_morrison_rm].
spidermother, Dec 09 2011
  

       I think you were right with what you said about Benson's law. My interpretation is that not_morrison_rm had read somewhere that if you went into the real world and picked numbers from 'things' at random, the distribution would follow Benson's law. That's actually a subtly different question. I think that's actually kind of intuitive when you consider how things have to be numbered; here's my explanation.
Suppose you sampled 'random' GPS coordinates in an area and record the houses number along the street if it happens to unambigously hit a house, or the pavement outside. Roads vary widely in length, having zero or more houses on them, and typically house numbers typically start at one and increment. In the UK house counting alternates sides of the road, which probably doesn't affect things much.
Anyway, some roads will only have a few houses on, ending in the low tens. If a street has 20 houses on, 55 percent of them start with the digit '1' (1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19). If a house has 200 houses on, 55.5% start with '1', and so on. Obviously, the result from counting many house 'hits' around the country would depend on how street lengths were distributed, but the only way to get an even spread 1..9 would be to make sure each street only went up to one of 9, 99, 999 or so on.
Loris, Dec 09 2011
  

       //That's not really correct// Darn, I was hoping it was.   

       "Guess the genuinely random number I just generated."
"Infinity?"
"Got it in one!"
  

       ('course, the sophisticated player would ask its cardinality before guessing).
mouseposture, Dec 09 2011
  

       [Loris] Which is much the same as saying that roughly logarithmic distributions are fairly common; the length of randomly selected organisms would probably also follow Benson's law. The height of humans, though, would not - the distribution is closer to normal.   

       An important distinction here is between things selected at random (from a population with some distribution or other) and things that exhibit a uniform random distribution - which would be rare in the real world.
spidermother, Dec 09 2011
  

       Just for fun, I took a small sample of first digits of street numbers from the White Pages directory, and got:   

       1 - 31
2 - 19
3 - 6
4 - 7
5 - 7
6 - 5
7 - 6
8 - 4
9 - 2
spidermother, Dec 09 2011
  

       //Is there an application other than cryptography for truly random data?//   

       As an addendum to my above reply, I should point out that cryptography is used in many places you may not expect. When buying something online you will be relying on cryptography for security, for example.
I mention this now because I saw an article today (link) that poor random-number generation has afflicted a small fraction of keys (for a widely used system), making them insecure.
  

       This doesn't directly affect the idea - however, if you were thinking "I don't use cryptography" then you're probably wrong.
Loris, Feb 16 2012
  

       //is there an application other than cryptography for truly random data ?//   

       trying to emulate a random event: card games for instance, or trying to emulate noise.
FlyingToaster, Feb 16 2012
  
      
[annotate]
  


 

back: main index

business  computer  culture  fashion  food  halfbakery  home  other  product  public  science  sport  vehicle