[Cryptography] Opening Discussion: Speculation on "BULLRUN"

Eugen Leitl eugen at leitl.org
Sat Sep 7 01:43:10 PDT 2013


----- Forwarded message from Jon Callas <jon at callas.org> -----

Date: Fri, 6 Sep 2013 17:58:33 -0700
From: Jon Callas <jon at callas.org>
To: Jerry Leichter <leichter at lrw.com>
Cc: cryptography at metzdowd.com, Jon Callas <jon at callas.org>, "Perry E. Metzger" <perry at piermont.com>
Subject: Re: [Cryptography] Opening Discussion: Speculation on "BULLRUN"
X-Mailer: Apple Mail (2.1508)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sep 6, 2013, at 6:23 AM, Jerry Leichter <leichter at lrw.com> wrote:

> Is such an attack against AES *plausible*?  I'd have to say no.  But if you were on the stand as an expert witness and were asked under cross-examination "Is this *possible*?", I contend the only answer you could give is "I suppose so" (with tone and body language trying to signal to the jury that you're being forced to give an answer that's true but you don't in your gut believe it).

I'd be happy to give a different answer, like -- almost certainly not.

> 
> Could an encryption algorithm be explicitly designed to have properties like this?  I don't know of any, but it seems possible.  I've long suspected that NSA might want this kind of property for some of its own systems:  In some cases, it completely controls key generation and distribution, so can make sure the system as fielded only uses "good" keys.  If the algorithm leaks without the key generation tricks leaking, it's not just useless to whoever grabs onto it - it's positively hazardous.  The gun that always blows up when the bad guy tries to shoot it....

We know as a mathematical theorem that a block cipher with a back door *is* a public-key system. It is a very, very, very valuable thing, and suggests other mathematical secrets about hitherto unknown ways to make fast, secure public key systems. 

To me, it's like getting a cheap supply of gold and then deciding you'll make bullets out of it instead of lead. To riff on that analogy, it feels like you're suggesting that they would shoot themselves in the foot because they know that the bullet fragments will hurt their opponent.

That's why I say almost certainly not. It suggests irrationality beyond my personal ken. It's something I classify colloquially as "too stupid to live."

My assumptions about the NSA are that they're smart, clever, and practical. Conjectures about their behavior that deviate from any of those axes ring false to the degree that they deviate from that.

My conjectures start with assuming they're at least as smart as me, and I start with "what would I do if I were them?" I think they're smart enough not to attack the strong points of the system, but the weak points. I think they're smart enough to prefer operating in stealth.

Yeah, yeah, sure, if with those resources I stumbled into a fundamental mathematical advantage, I'd use it. But I would use it to maximize my gain, not to be gratuitously sneaky.

The math we know about block ciphers suggests (not proves, suggests) that a back door in a cipher is impractical, because it would imply the holy grail of public key systems -- fast, secure, public key crypto. It suggests secure trapdoor functions that can be made out of very simple components.

If I found one, it would be great, but I'd devote my resources to places where I technology is on my side. Those include network security and software security, along with traffic analysis.

If I wanted to devote research resources, I'd be looking closely at language-theoretic security. I'd be paying close attention to the fantastic things that have come out of there.

The stuff that Bangert, Bratus, Shapiro, and Smith did on turning an MMU into a Turing machine is where I'd devote research, as well as their related work on "weird machines."

I apologize for repeating myself, but I'd fight the next war, not the last one.

	Jon


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii

wj8DBQFSKno7sTedWZOD3gYRAjMUAJ9qDQcQZVr/1580qZStlu/7fFgLIwCg2U5r
WFth65Vi4GIDF1wu5oVukYs=
=M/f+
-----END PGP SIGNATURE-----
_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5



More information about the cypherpunks mailing list