Uri_Yandex
With the current "unofficial" ECDH patches out there for OpenVPN, is the compromised PRNG ever called to generate the curves?
I know the PRNG is present in OpenSSL. My question is, how is it enabled/implemented/called within OpenSSL. Are there any concerns with using elliptic curves + OpenSSL + OpenVPN?
Pattern_Juggled
DUAL_EC_DRBG is a standalone PRNG that isn't (directly) related to EC-based key exchange algorithms. Rather, it makes use of EC characteristics as seed values for it's pseudorandom generator.
(for complex political reasons, the NIST at the time wanted a PRNG that was built on a different mathematical foundation than the standard, well-tested PRNGs already in use - and there's some sort of bizarre mistrust of "real" random IV entropy sources like radio emissions or other physical phenomena at NIST so these PRNGs end up being really crucial more so than in most non-NIST-centric implementations where we're more likely to grab entropy from the environment than to lean so heavily on an algorithmic generator of any kind)
ECDH doesn't make use of any PRNG in curve generation. Rather, it has a set of default curve "families" which are then fed IVs (random-ish, one hopes) to produce the concomitant "points on the curve" that are the conceptual equivalent of the prime factors used in RSA key exchange (or the logarithms used in "normal" DH). There's some concerns that the "default" curves are maybe "special" in that someone <cough>NSA<cough> might know more about how those curves work than the rest of us and thus be able to deduce matching points (not actually points, as this is discrete maths, but functionally equivalent) with relatively little effort. The solution to this is, as I see it anyhow, simply to choose one's own curve families by one's own selection criteria, and seed then with one's own IV sources. ECDH is perfectly happy with this. The challenge is that selecting curves - or curve families - is nontrivial as there's lots of curves that are considered "degenerate" or at least not robust enough for use in this kind of unidirectional transform. There's statistical tests that can be run on proposed curve metrics to see if it passes muster, but they're quite complex and unless one is a specialist in this branch of mathematics, it's probably unreasonable to assume running such tests is practical.
Alternatively, there's published literature with lists of non-degenerate curve parameters for the various flavours of ECDH and one can pick from those lists. Downside being: maybe the people who made those lists were secretly in the pocket of the NSA... but some lists are quite long, made by folks who seem pretty unlikely to be stooges for the secret police state regime. That's my $0.02, anyhow.
OpenVPN, being quite happy to offload crypto mechanics to OpenSSL, knows nothing of such shenanigans under the covers, as it were, and will simply trust that OpenSSL is doing its job. Thus, administrators of such systems must dig into the guts of the OpenSSL parameters - which are supremely flexible, to the point that one's imagination is the only limit to what sort of tweaks are possible.
The downside is that 99% of folks won't bother, and thus will end up using the default EC parameters for ECDH (and, even more worrisome perhaps, ECDHE). Which is a problem if those curves are "special" and thus functionally reversible by someone with that special knowledge. Which is, at present, unproven... but Schneier has hinted at it being quite likely. Or that's my read, anyhow.
Is ECC itself broken? There's no hard data to show that, nor even to really hang a suggestion on. We can speculate, but it seems that's a low probability. Much more likely is the fiddling of curve selection & curve family preference so that many ECC implementations default to those "special" curves without many folks knowing. I consider that, personally, to be all but certain at this point in time. If you use the default curves, you're handing a key to the NSA - that's overstating it a bit, but it's my read of the literature and the advice given by lots of really smart folks thus far.
Again, you'd never want to generate "random" curves for use with ECC; it's too likely the curve you get would be boring/simple/degenerate. You have to hunt for those nice, meaty curves - not random. You do use "random" IVs for curve/point mapping in actual deployment... but in that case the random-ness of the IV is more or less irrelevant. It's more of a nonce, I guess - so long as it's not static over time, it does the job. You won't go wrong by getting obsessive about ensuring your curve/point IVs are high-entropy via temporal metrics... but I don't know that it's actually necessary for good security in practice.
Standard caveat: cryptographers are really smart. I hope one of those folks shows up here and mercilessly corrects any and all errors or shortcomings in my efforts to discuss these topics. My work is with cryptographic implementations - not "real" crypto research at the fundamental level - and I defer on matters of underlying maths to the real cryptographic experts... of which I am not one. I just try my best to use the tools properly, without error or improper implementation.
Cheers,
~ pj
