[cryptography] Unbreakable crypto?

Seth David Schoen schoen at eff.org
Sun Mar 22 00:17:52 EDT 2015


Lee writes:

> On 3/21/15, Jeffrey Goldberg <jeffrey at goldmark.org> wrote:
> > [Apologies for quoting badly]
> >
> > No!  A thousand times no.
> >
> > (1) the file isn't secret
> 
> But the fact that I'm using it as my one-time pad is.  Why isn't that
> good enough?

If an attacker has access to the same web sites and databases that you
do, the attacker could just try all of them the files in them.  There
shouldn't be more than 2⁵⁰ publicly-accessible files out there, right?

Or maybe each file in a copy of the Internet Archive, say.  One of them
is actually going to be that ISO file!

There are other conceptual problems that are much worse than this
practical problem.  The biggest conceptual problem is that, for the
one-time pad setting that has been mathematically proven secure, the
shortest description of the pad you are using should normally be the pad
itself.  If there is a shorter description, the attacker first of all has
a smaller work factor (set of things to try), but what's really _much much
much_ worse conceptually, the attacker has a probability of being able
to usefully distinguish one possible decryption as more likely than others.

In the ideal one-time pad, there is no basis on which an attacker (even
an attacker with completely unbounded resources) can usefully say that
one proposed decryption is more likely to be right than another, at
least compared to the attacker's prior beliefs about what the plaintext
was likely to be.  But if there is a meaningfully shorter description of
what you used as the pad, then an attacker with vast resources who
correctly guesses what that was will know that it's likely to be right,
which is a kind of success that the attacker couldn't have achieved with
a truly random pad.

*True random pad*: Attacker doesn't know whether pad k₁ is actually more
likely than pad k₂, if (c ⊕ k₁) and (c ⊕ k₂) both appear to be equally
plausible plaintexts.

*Choosing a meaningful file but keeping secret which one you used*: An
attacker who tries your file f₁ as the pad notices that both (c ⊕ f₁)
and f₁ itself appear "meaningful", so it's more likely that f₁ is
correct compared to some other f₂ which is not "meaningful".


This is the great thing about the classical one-time pad: the attacker
_literally doesn't know when the attack was successful_, a fact which
has nothing to do with how powerful the attacker is (how many keys the
attacker is able to try guessing).  In the classical one-time pad with
a true random pad, even an attacker who can try _every single_ pad
literally doesn't have any evidence which could reveal which one was
right, or which could reveal any new fact or property about the
plaintext.  Relaxing the randomness assumption, in turn, undermines this
conclusion because the attacker can now have some conceivable indication
about "being on the right track" (even if that's merely statistical),
which could simply never happen with a true random pad.

-- 
Seth Schoen  <schoen at eff.org>
Senior Staff Technologist                       https://www.eff.org/
Electronic Frontier Foundation                  https://www.eff.org/join
815 Eddy Street, San Francisco, CA  94109       +1 415 436 9333 x107


More information about the cryptography mailing list