[Cryptography] [RNG] on RNGs, VM state, rollback, etc.

[Jerry Leichter]

On Oct 21, 2013, at 6:24 PM, Bill Stewart wrote:
>> Real-world cryptanalysis [can] break OTP.
> 
> Real-world cryptanalysis can't break mathematical-cryptography OTP.
> But real-world cryptography can use sometimes-more-than-One-Time Pads, and not-independent-identically-distributed random pads, and not-destroyed-after-use pads, and real-world cryptanalysis can sometimes break those.
No, you're missing the point.

Mathematical cryptanalysis is about breaking highly specific idealized models using a particular set of techniques - usually formalized as something along the lines of "a probabilistic Turing machine receiving X, Y and Z on its input tape and running for no more than T seconds has a probability of less then epsilon of producing a result of a particular kind."

Real-world cryptanalysis includes the possibility that someone planted a camera in the ceiling above the desk where you do the paper-and-pencil computation of your perfect OTP cipher.

Mathematical cryptanalysis gives you an upper bound on the difficulty of the problem.  There's not much point in using a system if the upper bound you get is small relative to the value of what you're protecting.  But once it becomes large enough, measuring the mathematical difficulty becomes much less useful, as the vulnerabilities are elsewhere.

A true one-time-pad is completely secure against mathematical cryptanalysis, but that fact tells you almost nothing of interest about the security of a real-world system that uses a one-time-pad.  Remember how we got here:  From the initial claim that any system can be attacked given enough resources, to the counterclaim that a one-time-pad could *not* be attacked, to my counter-counter claim, just repeated here, that any real-world implementation *can* be attacked, given sufficient resources.  It's not a claim about the particular weaknesses of particular realizations of one-time-pads; it's a claim that *some* weakness will always be present.  The best you can do is make the cost of attacking that weakness exceed the value of whatever you're protecting.  *That* is the real-world analogue of the "perfect (mathematical) security" of a one-time-pad.
                                                        -- Jerry