DUAL EC attack theory, in quantum mechanical terms

Lets take a look at https://onedrive.live.com/redir?resid=5061D4609325B60!5824&authkey=!AJaVvdDixpapUgA&ithint=file%2c.pdf




2014-0521.pdf listed by Cryptome


In short, the paper discusses several implementations of TLS and the means by which one can exploit implementation features, in the manner by which cryptomodules are used by ciphersuites of the TLS handshake. The exploit class delivers to the supposed attacker sufficient public data about a random stream, generated from a PRNG seed, that allows one with a backdoor on the PRNG process to predict the next set of generated values. The point is that said set may contain secrets that the ciphersuite protects – that the trapdoor reveals by a mixture of knowing the pool from which the secrets are taken and by search. Some of the secrets compromise other mechanisms (and the security services that derive from them); including DSA signing keys. A compromised signing key compromises the authenticity of the DH keys used in the key agreement mechanism, which compromises the generation of the pre-master secret used in key derivation elements of the SSL handshake.

However, the above is not my concern (since Id like to stay unshot – having been trusted by folks in NSA not to undermine their mission). Our concern is to simplify understanding of how DUAL EC works – so lots of folks can understand its processes. They seem hard! But they are not if you think in terms of physics and computer science.

Recall from quantum mechanics that there is the unknowable notion of quantum state – that bucket of bit-like things from which all measurements in the real world derive. We cannot know that state, being an pure math combinatorical object, but we can measure it – providing we learn to do quantum mechanical measurements. For that, we need some math – the math of measuring states.

For the purposes of this article, the PRNG seed is the quantum state – supposedly unknown and unknowable (until we understand the math theory of trapdooring).

Its best to start out with a math refresher taught by an expert

In this lecture you get a solid grounding. But you don’t get the kind of math that shows how to more easily understand Ps and Qs and elliptic curves. For that we need a little more of his teaching:

What we now need is the ability to compute in two spaces at once – the space and its dual. So there , we are starting to get towards P (this space) and Q (its dual). Other examples of this duality include the frequency space and the space of  amplitudes – where one converts between the two using the fourier transform.

Look at the part of the video, at link, where SUsskind introduces a summing variable (j). And, then, understand the notion of “scripty M” and the general concept of hermitian conjugation (of operators, rather than values). Now recall the notion of wave/particle duality – and just consider how the very FORM of the equation captures that notion. Both aspects are modeled, with the stuff on the right being the amplitude space (perhaps known as kets) and the stuff on the left being the periodic or frequency space (perhaps known as bras). One models both the particle like and its wave like features at the same time, knowing that they are conjugate. The domain and its frequency representation (via fourier transforms) are conjugates. You can be a particule and and a wave at the same time, once the math enables you to state facts about both simultaneously. And that’s the key (without getting into locality, centrality, or any other physics ideas).

I want you, now,  to think of P and Q in the sense of hermitian conjugates (don’t take this literally!). They act on the mythical and unknowable “crypto”-quantum state denoted as A (on the right and on the left, in dual form). We have to be reasoning with both components always, simultaneously, to be seeing the crypto notion of trapdooring.

Now, the point of elliptic curves is that the relationship between particular points P and Q, as hermitian conjugates, is not computable – without knowing the value d (in the language of the paper). (One should think of RSA math, at this point!) Only then can one start to compute “averages” as a cryptanalyst– that special kind of computation that comes about from “duality” expressions of this form. It’s allows one to work with predictions about average cases, found when performing a measurement lots of times. One wishes to know the bias, over 50%, of which outcome value predominates. This is the key to cryptanalytical techniques and knowhow.

Now, you might object to this characterization of curves and points P and Q (since the duality concept is not consistent with “how you do the calculation”). But calculating is not the point of this memo. We are programming, here, creating algebras that allow us to reason about calculation spaces, types of expressions, and the GENERATION of expressions (that then calculate).

To use Susskind’s metaphors, you perform your particle-like machine process ‘M’ on an input state and then project the intermediate result (which should be reminding you of a DES sbox output) onto the machine.dagger – that conjugate machine that allows you now to act on the crypto-space in a wave like manner.  IN so doing one statements are those that now act on *any* possible input (complex conjugated); one is doing algebra of
“crypto” search spaces and formulating algebras thereof.  One has captures the “art” of cryptanalysis, realizing that its that class of math that “characterizes” searching and constraining. Of course, being math, one wants math that searches out math that duly searches…out such mundane things as needle keys in haystacks of cipher.


About home_pw

Computer Programmer who often does network administration with focus on security servers. Sometimes plays at slot machine programming.
This entry was posted in coding theory. Bookmark the permalink.