brute force physics Was: cleversafe...

[Alexander Klimov]

On Sun, 9 Aug 2009, Jerry Leichter wrote:
> Since people do keep bringing up Moore's Law in an attempt to justify
> larger keys our systems "stronger than cryptography," it's worth
> keeping in mind that we are approaching fairly deep physical limits.
> I wrote about this on this list quite a while back.  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.

A problem with this reasoning is that the physical world and the usual
digital computers have exponential simulation gap (it is known at
least in one direction: to simulate N entangled particles on a digital
computer one needs computations exponential in N). This can be
considered as a reason to suspect that physical world is
non-polynomially faster than the usual computers (probably even to an
extent that all NP computations can be simulated).

While it is possible to use physical world to simulate usual computers
in the straightforward way (namely by using voltage levels of a
circuit to represent separate bits), it is not clear that doing
computations in this way is the best way to do computations, for
example, if the meaning of our computations are simulation of the
physical world, then it can be better to use direct
physical-to-physical mapping instead of physical-to-usual followed by
usual-to-physical: analog computers, such as wind tunnels, are still
in use.

I am not aware of any plausible argument why a brute force search in
general (a quintessence of NP class, by the way) or a key search
against any particular algorithm cannot be implemented in a direct way
significantly faster than in the indirect way, that is NP-to-physical
instead of NP-to-usual followed by usual-to-physical. All the fuss
about quantum computing is exactly because people believe that a
different mapping (not thru usual computers) can be more efficient (if
I understand correctly, right now neither the class of algorithms that
can be sped up this way is understood, nor the quantum computers of
practical capacity exist).

> 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.

Of course, if AES-256 was used (say for hashing) with input as
the key, then nobody should be surprised that the version that
takes 256 bits at a time is weaker than the version that spends
comparable time for processing only 128 bits.

-- 
Regards,
ASK

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