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 majord...@metzdowd.com