[ILUG] serious Debian/Ubuntu security hole found

[Brian Foster]

  | Date: Sat, 17 May 2008 18:25:19 +0100
  | From: Michael Watterson <watty at eircom.net>
  | 
  | Brian Foster wrote:
  | >   |[ ... ]
  | >   | (Pi  and e you can always calculate (predict) more digits. They are
  | >   | irrational, not random).
  | >
  | >  careful here.  if I told you I'm using the base 10
  | >  expansion of π and my current “random” digit is 7,
  | >  you wouldn't be able to tell me what the next digit
  | >  is.  (you'd be able to guess with an c.10% chance
  | >  of being right.)  and if I asked you for the next
  | >  sequence of, say, 10 digits, your search space is
  | >  larger.  what we don't know is just how large.
  | 
  | If you told me your last ten* "random" digits though, you might be in
  | trouble.

 agreed.  (note there's no real difference between
 knowing the last 10  1-digit sequences, and knowing
 the last 1  10-digit (or the last 2  5-digit)
 sequences, provided of course you know the order of
 the sequences and also know they are consecutive.)

  | You can't know anything from a single input. My suggestion was that with
  | suitable amount of history, that if you have calculated the irrational
  | number to more places than was used, you could deduce which irrational
  | number was used and thus what part of it might be used next. Hypothetically.

 yes, if you're know you have calculated to more
 places then were used.  that's a string matching
 problem, ableit there still may be more than one hit.
 even so, you get a much smaller candidate list.

 without that key constraint then it (seems) much harder.
 this is where normalness, or the lack thereof, comes in.
 if you know the last Q sequences of D digit "random"
 values, and your irrational number is normal, that QxD
 sequence will appear with equal probability to every
 other QxD sequence.  this means (given there are an
 infinite number of sequences of length QxD in an normal
 irrational (since an irrational expansion is of infinite
 length)) you don't know which particular instance was
 used, and hence what the next sequence will be.

 of course, there are flies in the ointment here.
 for instance, in computing/engineering sequences are
 necessarily finite (not infinite) in length, and so
 even if the irrational is normal, eventually what you
 propose might work:  no finite expansion can ever be
 normal (indeed, no rational is normal).

 furthermore, irrational numbers are not necessary
 normal, albeit it is known most numbers are normal.
 (most numbers are also irrational.)  to the best of
 my knowledge, there are relatively few normal numbers
 whose value is known; most of them have, as far as I
 know, been deliberately constructed.


  |[ ... ]
  | The only 100% secure for ever system is a One Time Pad using
  | a true random key the same size at least as the message.  [ ... ]

 yes, something like that (I'm unsure of the details
 of the "OTP is secure" proof, but the above sounds
 about correct (maybe with a few minor corrections
 or clarifications?)).

  |[ ... ]
  | Messages to spies from 1950s to now probably uses OTP. Famous of these
  | may be the Short Wave Number Stations. I first heard them in the 1970s
  | and they are still on the go

 they are still going?  I have vague recollections of
 stumbling across one back in my ham radio / shortwave
 days (that and the fecking russian woodpecker (probably
 an OTH radar (has that ever been confirmed ? ))), but I
 never really paid any attention.

cheers!
	-blf-
-- 
“How many surrealists does it take to    |  Brian Foster
 change a lightbulb?  Three.  One calms  |  somewhere in south of France
 the warthog, and two fill the bathtub   |     Stop E$$o (ExxonMobil)!
 with brightly-coloured machine tools.”  |       http://www.stopesso.com