Re: [Cryptography] Can you backdoor a symmetric cipher (was Re: Opening Discussion: Speculation on "BULLRUN")

2013-09-06 Thread Jerry Leichter
>> 
>> It is probably very difficult, possibly impossible in practice, to
>> backdoor a symmetric cipher. For evidence, I direct you to this old
>> paper by Blaze, Feigenbaum and Leighton:
>> 
>> http://www.crypto.com/papers/mkcs.pdf
>> 
> 
> There is also a theorem somewhere (I am forgetting where) that says that if 
> you have a block cipher with a back door, then it is also a public key 
> cipher  The real question there is whether someone who had such a thing 
> would want to be remembered by history as the inventor of the most 
> significant PK system the world has ever seen, or a backdoored cipher.
Well, if that "someone" were the NSA, they might well be very happy to be 
remembered as the guy who made it possible break in to much of the world's 
communication!

However, I find this argument unconvincing.  It has the feel of a standard 
reduction, but isn't, because the reduction is to a known problem that's widely 
thought to be difficult - it's to a vaguely defined, broad class of problems, 
"designing a much faster public key system".  Just because the construction 
gives you something like a public key system, doesn't mean if gives you 
anything practical for use that way.  For example, suppose the master key works 
- but only for 1/2^k possible cleartext blocks, or even 1/2^k possible keys.  
This makes it useless as a public-key system even for very small k, but quite 
useful to an attacker even for larger k.

Or suppose the master key works on all messages and keys, but is inefficient, 
requiring large amounts of time or memory, or the pre-computation of large 
lookup tables.  Here's a thought experiment:  Suppose differential 
cryptanalysis were known only to you, and you were in a position to influence 
the choice of S-boxes for a cryptosystem.  Your "master key" would be the 
knowledge that DC would work very effectively against the system - but it would 
still require a lot of time and memory to do so.  You'd even have a leg up on 
everyone else because you'd know the differentials to use up front - though 
that's a trivial advantage, since once you know to look for them, finding them 
is easy enough.  In fact, as far as I know, no one has had any reason to pose 
questions like:  Could you choose S-boxes that allow some kind of 
pre-computation step to make application of DC to messages much faster?  DC 
requires gathering up a large number of plaintext/cyphertext pairs; eventually, 
you f
 ind examples of you can use.  But could there be some way of producing pairs 
so that success is more likely to come earlier?  Could it be that there's some 
pre-secret that allows computation both of those tables and and of the S-boxes, 
such that given only the S-boxes, finding the pre-secret and the tables isn't 
practical?  Once DC was known and it was found the NSA had actually 
strengthened DES's S-boxes to protect against it, no one really looked into 
such issues - basically, who cared?

If you really want to think in tin-hat terms, consider linear cryptanalysis.  
While DES was strong against DC, it was quite weak against LC.  People 
interpreted this as meaning that NSA didn't know about LC.  But ... maybe out 
in Area 51, or wherever Langley does work with alien technologies, they knew 
about LC *all along*, and *deliberately* made DES weak against it!  (Why LC and 
not DC?  Because as we subsequently learned from Don Coppersmith, DC was 
already known in the non-NSA community, and the NSA knew that it was known.)

Please keep in mind that I'm not proposing that NSA actually did anything like 
this for any widely-used cryptosystem.  I don't even see how they could have 
with respect to, say, AES, since they had no hand in the design of the 
algorithm or the choice of constants.  The only thing I'm arguing here is that 
the "theorems" that say such a thing could never happen prove nothing of the 
sort.
-- Jerry

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] Can you backdoor a symmetric cipher (was Re: Opening Discussion: Speculation on "BULLRUN")

2013-09-05 Thread Jon Callas
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On Sep 5, 2013, at 9:33 PM, "Perry E. Metzger"  wrote:

> 
> It is probably very difficult, possibly impossible in practice, to
> backdoor a symmetric cipher. For evidence, I direct you to this old
> paper by Blaze, Feigenbaum and Leighton:
> 
> http://www.crypto.com/papers/mkcs.pdf
> 

There is also a theorem somewhere (I am forgetting where) that says that if you 
have a block cipher with a back door, then it is also a public key cipher. The 
proof is easy to imagine -- whatever trap door lets you unravel the cipher is 
the secret key, and the block cipher proper is a PRF that covers the secret 
key. I remember the light bulb going on over my head when I saw it presented.

So if you have a backdoored symmetric cipher, you also have a public key 
algorithm that runs five orders of magnitude faster than any existing public 
key algorithm.

This suggests that such a thing does not exist. We have a devil of a time 
making public key systems that actually work. Look at all we've talked about 
with brittleness of the existing ones, and how none of the alternatives 
(Lattice, McElice, etc.) are really any better and most of those are really 
only useful in a post-quantum world. It doesn't prove it, but it suggests it.

The real question there is whether someone who had such a thing would want to 
be remembered by history as the inventor of the most significant PK system the 
world has ever seen, or a backdoored cipher.

Jon



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

wj8DBQFSKV02sTedWZOD3gYRAnK5AJ9aB8I0csP1ryW6aaXEqMPOyL31PwCfZuUs
swH73+Zqwqy4ZFeD7QjWoyM=
=BnW3
-END PGP SIGNATURE-
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


[Cryptography] Can you backdoor a symmetric cipher (was Re: Opening Discussion: Speculation on "BULLRUN")

2013-09-05 Thread Perry E. Metzger
On Thu, 5 Sep 2013 23:24:54 -0400 Jerry Leichter 
wrote:
> 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,

It is probably very difficult, possibly impossible in practice, to
backdoor a symmetric cipher. For evidence, I direct you to this old
paper by Blaze, Feigenbaum and Leighton:

http://www.crypto.com/papers/mkcs.pdf

Perry
-- 
Perry E. Metzgerpe...@piermont.com
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography