I'm still trying to decipher this Schnorr presentation entitled "Average Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time". Presumably, if this led to a practical attack, Schnorr would have presented it differently, but I'd be interested to see an analysis of the impact of it, if any, from a real cryptographer.

# COMSEC: April 2009 Archives

## April 30, 2009

## April 26, 2009

- To a first order, the strength of symmetric encryption algorithms against the best known attacks is the length of the key itself.
- Currently the strength of our standard digest algorithms (SHA-x) against preimage attacks is roughly that of the output length, and against collision attacks it's something less than half the output length (this is a topic of active research on SHA-1, which currently stands at 63 bits as opposed to the theoretically optimal 80 bits).
- The situation is somewhat less clear for asymmetric algorithms: again, you can see keylength.com for details, but a 1024-bit RSA key is very approximately equivalent to an 80-bit symmetric key, a 2048-bit RSA key to 100 bits or so. Elliptic curve keys of size 2n are approximately equivalent to symmetric keys of size n.

There is also some consensus on the near-term lifespan of any set of parameter: keylength.com has a good summary here. Whats a lot less clear is the long term. For instance, ECRYPT's recommendation is that 128-bit symmetric keys are fine for "Long term protection: Generic application-independent recommendation, protection from 2009 to 2038." NIST's recommendations aren't that different, though they recommend 192 bits for >> 2030 and 256 bits for >>> 2030, whatever that means. In general, guidelines for keys > 128 bits are somewhat vague. The basic problem is that it's very hard to imagine any circumstances in which a 128-bit symmetric key will become susceptible by brute force attack with conventional computers. Hopefully Dan Simon will chime in here, but as I understand the situation if we got quantum computers working they would potentially offer a significant improvement against the main public key algorithms and a potential square root improvement against symmetric algorithms. Of course, we're nowhere near having a working quantum computer anything like this good.

Absent working quantum computers, the only plausible avenue of attack on any system with an effective key strength of 128 bits is an analytic attack of some kind. Each asymmetric algorithm is basically the same at any key length (the keys are just bigger) so you would expect any analytic attack at (e.g., 1024 bits) to also be useful at another key size (e.g., 2048 bits). The relationship between AES-128, AES-192, and and AES-256 is more complicated, but the underlying structure is the same, so you would expect an attack on AES-128 to have an impact on AES-256 as well. Beyond that, it's very hard to predict what form such attacks would take; otherwise those doing the predicting would be hard at work on their CRYPTO submissions. In particular, it's hard to predict what the relative strength of the algorithms would be after such an attack.

This isn't to say that AES-256 isn't
likely to be stronger than AES-128—most likely it is, even if
there are better analytic attacks, if for no other reason
than it uses more rounds—but
it's not really 2^{128} bits stronger in any
meaningful way. Either we don't have any attacks better than
those we have now, in which case there's no practical
attack and AES-256 is just super-duper secure (but infinity * 2^{128} = infinity), or there are better attacks, in which case all bets are off.
Much the same is true for the asymmetric algorithms.

A related issue is "matching" the strength of the symmetric algorithms to the asymmetric algorithms. In protocols such as TLS, one usually uses an asymmetric algorithm (e.g., RSA) for key establishment and a symmetric algorithm (e.g., AES) for encryption. Some communities (the NSA especially) are very hot on choosing a set of algorithms with roughly equivalent nominal strengths (within the assumptions listed above). This can be quite problematic, however, because of the quantization of the symmetric algorithms. For instance, it's very natural to use AES-128, but if you really only care about having 80 bits of equivalent security, it's not at all clear why the fact that you're using AES-128 should drive you to use 3000 bit RSA keys; it's just that the minimum standard symmetric algorithm is AES-128. Similarly, if you're worried about cryptanalysis of AES so you've decided to use AES-256 it's not clear that that implies that you ought to be using an equivalent RSA key size (15000 bits!). Flipping things around, if you're worried about quantum computers, then the improvement for symmetric algorithms isn't the same as for asymmetric algorithms, so it's not clear why it would make sense to just dial up the strengths in parallel under either theory.

## April 11, 2009

Sometimes, of course, the arguments are such that the specialists can develop and summarize them to the point that an intelligent layman can evaluate them. But often--and I feel pretty sure here--that's just not the case. Give me a topic I know fairly intimately, and I can often make a convincing case for absolute horseshit. Convincing, at any rate, to an ordinary educated person with only passing acquaintance with the topic. A specialist would surely see through it, but in an argument between us, the lay observer wouldn't necessarily be able to tell which of us really had the better case on the basis of the arguments alone--at least not without putting in the time to become something of a specialist himself. Actually, I have a possible advantage here as a peddler of horseshit: I need only worry about what sounds plausible. If my opponent is trying to explain what's true, he may be constrained to introduce concepts that take a while to explain and are hard to follow, trying the patience (and perhaps wounding the ego) of the audience.Come to think of it, there's a certain class of rhetoric I'm going to call the "one way hash" argument. Most modern cryptographic systems in wide use are based on a certain mathematical asymmetry: You can multiply a couple of large prime numbers much (much, much, much, much) more quickly than you can factor the product back into primes. A one-way hash is a kind of "fingerprint" for messages based on the same mathematical idea: It's really easy to run the algorithm in one direction, but much harder and more time consuming to undo. Certain bad arguments work the same way--skim online debates between biologists and earnest ID afficionados armed with talking points if you want a few examples: The talking point on one side is just complex enough that it's both intelligible--even somewhat intuitive--to the layman and sounds as though it might qualify as some kind of insight. (If it seems too obvious, perhaps paradoxically, we'll tend to assume everyone on the other side thought of it themselves and had some good reason to reject it.) The rebuttal, by contrast, may require explaining a whole series of preliminary concepts before it's really possible to explain why the talking point is wrong. So the setup is "snappy, intuitively appealing argument without obvious problems" vs. "rebuttal I probably don't have time to read, let alone analyze closely."

Unfortunately, Sanchez has the cryptography pretty much wrong.
He's confused two totally separate
cryptographic concepts: public key cryptography, and one-way
hashes. Some PKC (but not all) involves multiplying large
prime numbers. Hash functions (with the exception of VSH,
which is impractically slow and not in wide use), don't
involve prime numbers at all. Neither does symmetric
encryption, which is what you actually use to encrypt data
(PKC is used primarily for key exchange and authentication/signature). Now, it's
true that prime multiplication is indeed a one-way function
(or at least we hope it is) and hash functions are
intended to be as well, but other than that, there's not
much of a connection.^{1}
That said, however, I've seen this post referenced
several places, and with the exception of Paul Hoffman,
who pointed it out to me, few seem to have noticed, that,
well, it's horseshit. I suppose this is an argument in
favor of Sanchez's thesis.

^{1.}Hash functions are actually one-way in
an important sense that prime number multiplication is not:
any given integer only has one unique factorization, whereas
there are many messages that hash to a single value,
so it's always possible with enough computational effort
to reconstruct the original primes. However, given
a hash value and no other information, it's not possible
to determine which of the possible input messages was
fed in.

## April 8, 2009

The spies came from China, Russia and other countries, these officials said, and were believed to be on a mission to navigate the U.S. electrical system and its controls. The intruders haven't sought to damage the power grid or other key infrastructure, but officials warned they could try during a crisis or war."The Chinese have attempted to map our infrastructure, such as the electrical grid," said a senior intelligence official. "So have the Russians."

...

The U.S. electrical grid comprises three separate electric networks, covering the East, the West and Texas. Each includes many thousands of miles of transmission lines, power plants and substations. The flow of power is controlled by local utilities or regional transmission organizations. The growing reliance of utilities on Internet-based communication has increased the vulnerability of control systems to spies and hackers, according to government reports.

So, obviously this is bad.

The first question you should be asking at this point is why these infrastructure systems are connected to the Internet at all. Protecting a computer in an environment where the attacker is allowed to transmit arbitrary traffic is an extremely difficult problem. I'm not sure that anyone I know would feel comfortable guaranteeing that they could secure a computer under conditions of concerted attack by a dedicated attacker. This doesn't mean that nobody should ever connect their computer to the Internet. After all, it's not like the entire reources of some national intelligence agency are going to be trained on the server where your blog is hosted. But the situation is different with things like the electrical grid which are attractive national-scale attack targets. [And rumor in the system security community is that these targets are not that well secured.]

It's natural to set up a totally closed network with separate cables, fiber, etc., but I'm not sure how much that actually helps. If you're going to connect geographically distributed sites, then that's a lot of cable to protect, so you need to worry about attackers cutting into the cable at some point in the middle of nowhere and injecting traffic at that point. The next step is to use crypto: if you have point to point links then you can use simple key management between them and it's relatively simple to build hardware-based link encryptors which reject any traffic which wasn't protected with the correct key. Obviously you still need to worry about subversion of the encryptors, but it's a much harder attack target than subversion of a general purpose computer running some cort of crypto or firewall or whatever.

Unfortunately, this is only a partial answer because you still have to worry about what happens if one end of the link gets compromised. At that point, the attacker can direct traffic to the other end of the link, so we're back to the same problem of securing the end systems, but at least the attack surface is a lot smaller because someone first has to get into one of the systems. So, you need some kind of defense in depth where the end systems are hardened behind the link devices.

Ideally, of course, you wouldn't network these systems at all, but I suspect that's pretty much a nonstarter: the grid is pretty interdependent and the control networks probably need to be as well. Most likely the best we can do here is try to have as many airgaps and choke points as possible to try to make it hard to get into the system in the first place and then make it hard for malware to spread.

P.S. It's not a *computer* security issue per se, but it's
worth observing that the electrical grids have non-computational
cascading failure modes. See, for instance, the Wikipedia article
on the
2003 blackout.
This implies that even if you have excellent informational isolation,
you still need to worry about localized informational attacks
leading to large scale failures by propagation through the
grid rather than propagation through the computer network.