On Sep 7, 2013, at 11:45 PM, John Kelsey wrote:

> Let's suppose I design a block cipher such that, with a randomly generated 
> key and 10,000 known plaintexts, I can recover that key.... At this point, 
> what I have is a trapdoor one-way function.  You generate a random key K and 
> then compute E(K,i) for i = 1 to 10000.  The output of the one-way function 
> is the ciphertext.  The input is K.  If nobody can break the cipher, then 
> this is a one-way funciton.  If only I, who designed it, can break it, then 
> it's a trapdoor one-way function.... At this point, I have a perfectly fine 
> public key encryption system.  To send me a message, choose a random K, use 
> it to encrypt 1 through 10000, and then send me the actual message encrypted 
> after that in K.  If nobody but me can break the system, then this cipher 
> works as my public key.
OK, let's look at this another way.  The broader argument being made here 
breaks down into three propositions:

1.  If you have a way to "spike" a block cipher based on embedding a secret in 
it, you can a way to create something with the formal properties of a public 
key cryptosystem - i.e., there is a function E(P) which anyone can compute on 
any plaintext P, but given E(P), only you can invert to recover P.

2.  Something with the formal properties of a public key cryptosystem can be 
used as a *practical* public key cryptosystem.

3.  A practical public-key cryptosystem is much more valuable than a way to 
embed a secret in a block cipher, so if anyone came up with the latter, they 
would certainly use it to create the former, as it's been "the holy grail" of 
cryptography for many years to come up with a public key system that didn't 
depend on complex mathematics with uncertain properties.

If we assume these three propositions, and looks around us and observe the lack 
of the appropriate kinds of public key systems, we can certainly conclude that 
no one knows how to embed a secret in a block cipher.

Proposition 1, which is all you specifically address, is certainly true.  I 
claim that Propositions 2 and 3 are clearly false.

In fact, Proposition 3 isn't even vaguely mathematical - it's some kind of 
statement about the values that cryptographers assign to different kinds of 
primitives and to publication.  It's quite true that if anyone in the academic 
world were to come up with a way to create a practical public key cryptosystem 
without a dependence on factoring or DLP, they would publish to much acclaim.  
(Of course, there *are* a couple of such systems known - they were published 
years ago - but no one uses them for various reasons.  So "acclaim" ... well, 
maybe.)  Then again, an academic cryptographer who discovered a way to hide a 
secret in a block cipher would certainly publish - it would be really 
significant work.  So we never needed this whole chain of propositions to begin 
with:  It's self-evidently true that no one in the public community knows how 
to embed a secret in a block cipher.

But ... since we're talking *values*, what are NSA's values?  Would *they* have 
any reason to publish if they found a way to embed a secret in a block cipher? 
Hell, no!  Why would they want to give away such valuable knowledge?  Would 
they produce a private-key system based on their breakthrough?  Maybe, for 
internal use.  How would we ever know?

But let's talk mathematics, not psychology and politics.  You've given a 
description of a kind of back door that *would* produce a practical public key 
system.  But I've elsewhere pointed out that there are all kinds of back doors. 
 Suppose that my back door reduces the effective key size of AES to 40 bits.  
Even 20+ years ago, NSA was willing to export 40-bit crypto; presumably they 
were willing to do the brute-force computation to break it.  Today, it would be 
a piece of cake.  But would a public-key system that requires around 2^40 
operations to encrypt be *practical*?  Even today, I doubt it.  And if you're 
willing to do 2^40 operations, are you willing to do 2^56?  With specialized 
hardware, that, too, has been easy for years.  NSA can certainly have that 
specialized hardware for code breaking - will you buy it for encryption?

> The assumption that matters here is that you know enough cryptanalysis that 
> it would be hard to hide a practical attack from you.  If you don't know 
> about differential cryptanalysis, I can do the master key cryptosystem, but 
> only until you learn about it, at which point you will break my cipher.
In fact, this is an example I was going to give:  In a world in which 
differential crypto isn't known, it *is* a secret that's a back door.  Before 
DC was published, people seriously proposed strengthening DES by using a 
448-bit (I think that's the number) key - just toss the round key computation 
mechanism and provide all the keying for all the rounds.  If that had been 
widely used, NSA would have been able to break it use DC.

Of course we know about DC.  But the only reason RSA is safe is that we don't 
know how to factor quickly!  (Actually, even that's not quite true - after all 
these years, as far as I know, we *still* haven't managed to show that RSA is 
as hard as factoring - only the obvious fact that it's no harder.  It would be 
an incredible and unexpected result to separate the problems, but it *could* 
happen.)  It happens that in the case of RSA, we can point to *a particular 
easy to state problem* that, if solved, would break the system.  Things are 
much more nebulous for block ciphers, but that shouldn't be surprising:  They 
don't have simple, clean mathematical structures.  (In fact, when Rijndael was 
first proposed, there was some concern that it was "too clean" - that its 
relatively simple structure would provide traction for mathematical attacks.  
It doesn't seem to have worked out that way.)

There are, in fact, even closer analogues between potential RSA weaknesses and 
DC weaknesses.  What DC tells us is that certain S boxes lead to weak ciphers, 
even if the general structure is otherwise sound.  Well ... over the years, 
we've learned that certain choices of primes lead to weak RSA, so we've 
restricted the choices we make to the "good" primes.  This is a much more 
pronounced effect with discrete log-based algorithms - and yet more so with 
elliptic curve algorithms.  Anyone who knows about such weaknesses before they 
are known to the public, and is in a position to influence how primes or curves 
are chosen, can embed a back door - a back door that will be closed as soon as 
the potential weakness becomes known.  How is this different in the public-key 
and block cipher cases?

In the case of elliptic curve algorithms, we *know* that in some cases its 
possible to embed a secret, but we don't know of any way to tell if a secret 
*actually was embedded*.  DC happens to have the property that once you know 
about it, you can check if your S-boxes are bad - but where's the proof that a 
different attack will necessarily have this property?  If such an attack were 
to emerge against AES, *mathematically*, we'd have to say, well, maybe someone 
put a back door into AES - we really don't know one way or another, just as we 
don't know, one way or the other, about the NSA-suggested elliptic curves and 
points.  In either case, we should probably come up with something new.

                                                        -- Jerry

The cryptography mailing list

Reply via email to