brute force physics Was: cleversafe...

[Alexander Klimov]

Jerry Leichter wrote:

>> If current physical theories are even approximately correct,
>> there are limits to how many "bit flips" (which would
>> encompass all possible binary operations) can occur in
>> a fixed volume of space-time.

> The physical arguments to which I was referring say *nothing*
> about how the computation is done.  It can be a QM computation
> as well.

"Obvious" assumptions are hardest to trace: they assume that the
computation is done by bit flips which flip only constant number of
bits. QM computation is done with the whole state, that is a flip in
an N-qbit state simultaneously flips 2^N numbers describing this
state (if it were simulated by a classical computer).

I hope we agree that an exponential speed-up by QM computation *is*
possible (unless factoring is in P). That is why if we hear that (1) a
"physical limit" says that 2^N bit-flips cannot be done in a
one-light-year computer in a year, and we know that (2) the best
classical M-bit factoring requires 2^N bit-flips, and we know that (3)
this factoring can be done in few minutes on a QM computer, then we
must conclude that such "physical limits" are misleading.

David Wagner wrote:
> for a more nuanced and deep treatment of these issues,
> http://www.scottaaronson.com/papers/npcomplete.pdf

Thanks, it is great reading!

Whether NP is physically computable is an interesting topic, but its
applicability to our subject is quite limited: for cryptography it is
important to know that none of the puzzles created by a user can be
solved in some particular time given reasonable investment in
hardware, and thus the fact that hard instances exist as size tends to
infinity cannot console a practitioner.

Jerry Leichter wrote:
> >> All the protocols and standards out there calling for AES-256 - it's
> >> obviously "better" than AES-128 because after all 256 is *twice as
> >> large* as 128! - were just a bunch of nonsense.  And, perhaps,
> >> dangerous nonsense.
> >
> > I see the situation in the positive way: the recent AES attacks
> > stress the fact that the key management should be done
> > correctly, in particular, keys should be derived thru KDF (not
> > a simple xor) and must be authenticated. With this attack in
> > hand it is much easier for us now to say why one should not use
> > K to encrypt messages of one type and K+1 for another type, or
> > why it is a bad idea to encrypt a key in CTR mode and store the
> > result without a MAC. I doubt it is possible to find any
> > professionally designed protocol or standard that becomes weak
> > due to the recent discovery.
>
> That's a ... bizarre point of view.  :-)  Should freedom from
> related- key attacks be part of the definition of a "secure"
> encryption algorithm?  We should decide that on some rational basis,
> not on whether, with care, we can avoid such attacks.  Clearly, a
> system that *is* secure against such attacks is more robust.  Do we
> know how to build such a thing?  What's the cost of doing so?  But
> to say it's an *advantage* to have a weakness seems like some kind
> of odd moral argument:  If you're hurt by this it's because you
> *deserve* to be.

There is a set of rules in cryptographic design that are well
known to practitioners and are ignored by kibitzers. In many
cases it is much easier to do a normal design than to explain
why some proposed "improvements" are bad.

Consider a situation where some "smart" person comes to you and
say that for some reason (say, to save space) they want to use
CBC encryption, but keep IV constant; or they want to do CBC
encryption and CBC-MAC with the same key (as a bonus they get
encryption for free). What options you have once you manage to
stop the laughter?  In some cases it is enough to say: "No,
SP800-38a in Appendix C requires IV for CBC to be
unpredictable," but in other cases you also need to show
a plausible-looking attack against the "improvement". In this
situation it is clearly an advantage to have a known weakness of
ignoring rules of sane key management.

-- 
Regards,
ASK

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com