[Cryptography] Opening Discussion: Speculation on "BULLRUN"

Jerry Leichter leichter at lrw.com
Thu Sep 5 23:24:54 EDT 2013


>> Another interesting goal:  "Shape worldwide commercial cryptography marketplace to make it more tractable to advanced cryptanalytic capabilities being developed by NSA/CSS." ... This makes any NSA recommendation *extremely* suspect.  As far as I can see, the bit push NSA is making these days is toward ECC with some particular curves.  Makes you wonder.
> Yes, but. The reason we are using those curves is because they want them for products they buy. 
They want to buy COTS because it's much cheap, and COTS is based on standards.  So they have two contradictory constraints:  They want the stuff they buy secure, but they want to be able to break in to exactly the same stuff when anyone else buys it.  The time-honored way to do that is to embed some secret in the design of the system.  NSA, knowing the secret, can break in; no one else can.  There have been claims in this direction since NSA changed the S-boxes in DES.  For DES, we now know that was to protect against differential cryptanalysis.  No one's ever shown a really convincing case of such an embedded secret hack being done ... but now if you claim it can't happen, you have to explain how the goal in NSA's budget could be carried out in a way consistent with the two constraints.  Damned if I know....

>> (I know for a fact that NSA has been interested in this area of mathematics for a *very* long time:  A mathematician I knew working in the area of algebraic curves (of which elliptic curves are an example) was recruited by - and went to - NSA in about 1975....
> I think it might even go deeper than that. ECC was invented in the civilian world by Victor Miller and Neal Koblitz (independently) in 1985, so they've been planning for breaking it even a decade before its invention. 
I'm not sure exactly what you're trying to say.  Yes, Miller and Koblitz are the inventors of publicly known ECC, and a number of people (Diffie, Hellman, Merkle, Rivest, Shamir, Adelman) are the inventors of publicly known public-key cryptography.  But in fact we now know that Ellis, Cocks, and Williamson at GCHQ anticipated their public key cryptography work by several years - but in secret.

I think the odds are extremely high that NSA was looking at cryptography based on algebraic curves well before Miller and Koblitz.  Exactly what they had developed, there's no way to know.  But of course if you want to do good cryptography, you also have to do cryptanalysis.  So, yes, it's quite possible that NSA was breaking ECC a decade before its (public) invention.  :-)

                                                        -- Jerry



More information about the cryptography mailing list