Re: (eternity) Eternity as a secure filesystem/backup medium

-----BEGIN PGP SIGNED MESSAGE-----

[ To: cypherpunks ## Date: 01/21/98 ##
  Subject: Re: (eternity) Eternity as a secure filesystem/backup
medium ]

>Subject:      Re: (eternity) Eternity as a secure filesystem/backup
medium
>From:         Adam Back <aba@dcs.ex.ac.uk>
>Date:         1998/01/18

>1. communications crypto used by the author in submitting
>   the document is broken

This is only a threat if the authorities have a good idea
who submitted the data, and want to prove it.  Otherwise,
you end up with billions of encrypted documents, each
encrypted with a moderately weak cipher.  (Even assuming
that the cipher turns out to have only 40 bits of strength,
this is too expensive to do for more than a handful of
documents.)

>2. the eternity architecture contains encrypted documents to
>   frustrate attempts to locate documents, and to hide the
>   contents of documents from individual servers

Again, this won't be too economical unless the eternity
service is rarely used.

>3. communications crypto used to request and deliver
>   documents is broken thus revealing the readers identity


>So it is useful to design upgrade paths for ciphers into the
>protocols where possible.

Definitely--this is always a good idea, right?

>Other approaches we could take are to use very conservative
>cipher key sizes and protocols combining multiple ciphers in
>ways which gives us the security of the best of the ciphers.

>For example:

>	R = random, C = 5DES( R ) || blowfish-484( M xor R )

>Where 5DES is say E-D-E-D-E with 5 independent DES keys.

>Constructs to combine in strong ways hash functions, macs,
>symmetric and asymmetric ciphers would be useful.  Is there
>much research in this area?

Yes.  Massey and Maurer did a Journal of Cryptography paper
titled ``The Importance of Being First,'' which says that
in any chain of encryptions with different ciphers and
independent keys, such as E_1(E_2(E_3(data))), the whole
thing is provably as strong as the first cipher used on the
data (E_3, in my example above).  This is really obvious,
when you reflect that an attacker can always try to break
data encrypted with E_3 by superencrypting it with E_1 and
E_2, and then mounting his attack on E_1(E_2(E_3(data))).
Of course, if keys aren't independent among the three
ciphers, then you don't get any guarantee of this kind.

The other thing to note is that if you're just generating
keystream sequences, as you would with RC4 or SEAL, then all
ciphers are ``first.''

Rivest and Sherman also did some work on randomized
encryption, of the kind you discuss, in the Crypto '82
proceedings.  Your construction is very similar to one of
theirs.  Let M = message and R = a message-sized random
number, then in

E_1(R), E_2(R XOR M)

both E_1 and E_2 must be broken to learn M.  (Imagine this
isn't the case, then either E_1 or E_2 wasn't broken.  If
you didn't break E_2 but broke E_1, then you only learn R,
which is useless to you--it's random and uncorrelated with
M.  If you broke E_2 but not E_1, you would have a message
encrypted with a one-time pad.)

This generalizes nicely to

E_1(R1), E_2(R2), ..., E_N(RN), E_{N+1}(R1 XOR R2 XOR ... XOR M).

If those random numbers are really random, then if any one
of those ciphers resists your attacks, the message can't be
recovered.

Now, you can also do this with things that approximate
random functions, which they also discuss.  Thus, you might
use:

f_1(),f_2(), ..., f_n() are N independently-keyed different
cryptographic functions that approximate random functions.

The funny thing is, if you instantiate this intelligently,
you get a message encrypted by N different stream ciphers,
perhaps with a random parameter per message thrown in during
keying of those ciphers.  Thus, suppose

s_1(K1) = RC4(K1)
s_2(K2) = 3DES-OFB(K2)
s_3(K3) = SHA1-Counter-Mode(K3)
s_4(K4) = Blowfish-OFB(K4)
s_5(K5) = SAFER-SK128(K5).

and that these keys are different per message and are all
independent.  Then, you get the result that

M XOR s_1(K1) XOR S_2(k2) XOR ... XOR s_5(k5).

leaves no way to recover M unless all five s_i() can be
guessed.

Note that, in practice, this isn't likely to be useful
unless you've done the same kind of thing for symmetric key
distribution, random number generation, etc.  Otherwise,
your attacker in 2050 will bypass the symmetric encryption
entirely and factor your RSA modulus, or guess all the
entropy sources used for your PRNG, or whatever else you can
think of.

The good news, though, is that active attacks (like chosen
input attacks) and many side-channel attacks (e.g., timing
attacks) turn out not to be possible if you are trying to
mount them after the encryption has been carried out.

>Adam

- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print =  5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNMeCqSZv+/Ry/LrBAQGxpgQAloxNjdZMf6l/7U520ZSIVuk7lFZcu0+J
5tUyQgHtS4EAplC1OBnYc8B3pzCir6VCXinmNbClgalXhrRFfmV7vTQLZySaVv/+
0T44TFkJ0Ldu4cTsA2ertL0jcCXiBp38mhVK2IFbPtN+04B+een8jrUYtzx/qIj5
ztBpBb4yil8=
=wBTR
-----END PGP SIGNATURE-----

John Kelsey <kelsey@plnet.net> writes on cpunks:
> >1. communications crypto used by the author in submitting
> >   the document is broken
> 
> This is only a threat if the authorities have a good idea
> who submitted the data, and want to prove it.  

If we assume that the document was submitted by mixmaster remailer,
and that there is another leap forward in factoring algorithms such
that 1024 bit isn't enough any more.  (Not like it hasn't happened
before cf Rivest & friend's original predictions of hardness of
RSA-129).

Now threat model is that NSA is archiving mail between mixmaster
nodes.  They observe which exit mail corresponds to the target
document.  They look at the set of mixmaster mails going into that
node which could plausibly have corresponded to that message as
determined by the pool size.

Repeat to get back to originator.  If we assume 100 message pool size
(probably generous) and chain of length 10, that is 1000 decryptions
which adds equivalent to 10 bits worth of symmetric key size.

Paranoid stuff yes, but the NSA mixmaster traffic archive doesn't seem
that unlikely.

It is interesting to note that Tim May's recent suggestion of LAM
(Local Area Mixes) would help here because if 5 of those mixmaster
nodes where part of a LAM, it is unlikely that the NSA would be able
to archive inter remailer traffic, thus increasing effective pool size
to 100^5.  So one advantage of the LAM approach is that it provides
links which are protected by physical security.

A user might like to amuse himself trying to use channels he suspects
will not be archived as the entry point.  Perhaps a disposable account
at a high volume free mail account like hot mail might be nice.  We
would like to push NSA's problem towards having to archive the entire
net traffic.

> >2. the eternity architecture contains encrypted documents to
> >   frustrate attempts to locate documents, and to hide the
> >   contents of documents from individual servers
> 
> Again, this won't be too economical unless the eternity
> service is rarely used.

The design criteria of efficiency and robustness are conflicting.  Our
problem is to design something with useful tradeoffs.  Probably a
system offering a range of trade offs so that low risk documents can
make use of more efficient but less secure services, etc.

> M XOR s_1(K1) XOR S_2(k2) XOR ... XOR s_5(k5).
> 
> leaves no way to recover M unless all five s_i() can be
> guessed.
> 
> Note that, in practice, this isn't likely to be useful
> unless you've done the same kind of thing for symmetric key
> distribution, random number generation, etc.  Otherwise,
> your attacker in 2050 will bypass the symmetric encryption
> entirely and factor your RSA modulus, or guess all the
> entropy sources used for your PRNG, or whatever else you can
> think of.

Yes.  We need to build constructs for all areas.  A mega hash would be
nice, with a large output size even in the face of birthday attack,
preferably as secure as a collection of hash functions.

That gives us something to wash our pseudo random number input entropy
with, and then we can go on to combine public key systems.

A problem with public key systems however is that there isn't a lot of
choice -- basically all based on discrete log or factoring.  So
perhaps RSA and DH combined in a construct with an optimistically
proportioned key size would be near all that could be done.

> The good news, though, is that active attacks (like chosen
> input attacks) and many side-channel attacks (e.g., timing
> attacks) turn out not to be possible if you are trying to
> mount them after the encryption has been carried out.

A variation of this is that if we can get widely deployed blanket
encryption (IPSEC), we have largely won because we can mix all sorts
of things below that envelope, and the NSA is reduced to archiving
some large proportion of network traffic.  Our task is then to design
protocols which aggresively rekey (earliest opportunity) and which
maximise the number of nodes which the NSA would need to archive
traffic between to recover traffic with future cryptanalysis.

I suspect archiving world Network traffic would pose something of a
operational and financial strain :-)

Adam
-- 
Now officially an EAR violation...
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

At 5:18 PM -0800 1/25/98, Adam Back wrote:

>Repeat to get back to originator.  If we assume 100 message pool size
>(probably generous) and chain of length 10, that is 1000 decryptions
>which adds equivalent to 10 bits worth of symmetric key size.
>
>Paranoid stuff yes, but the NSA mixmaster traffic archive doesn't seem
>that unlikely.
>
>It is interesting to note that Tim May's recent suggestion of LAM
>(Local Area Mixes) would help here because if 5 of those mixmaster
>nodes where part of a LAM, it is unlikely that the NSA would be able
>to archive inter remailer traffic, thus increasing effective pool size
>to 100^5.  So one advantage of the LAM approach is that it provides
>links which are protected by physical security.

This is a big part of the LAM motivation: to grossly complicate the task of
observers watching the traffic. If SWAN or PipeNet is adopted, this
obviates this point, but neither seems likely anytime soon.

A LAM approach is low tech, and can be implemented easily enough. (And
PipeNet becomes much more feasible...)

Even an adventurous company, with many machines on various networks, could
deploy a LAM on their network.

(Though the laws about corporate culpability are written in ways that a
Silicon Graphics or Sun or C2Net would have much to fear in having their
corporate network associated with a LAM of any sort. Hence my point about
many and varied residential users in a physical building being the LAM
nodes.)

Another point about LAMs is that they are useful as "concentrators" for
PipeNet connections. To wit,

Suppose someone has deployed a PipeNet connection to another node. Fine,
but the NSA and Mossad and GCHQ and other enemies of freedom may watch the
traffic flowing into the node feeding that PipeNet connection.

So why not do a better job of "loading" this PipeNet connection by having a
LAM at the site? Then, watchers see the stuff flowing into the LAM, and
have less idea (correlation-wise) of what's then making use of the PipeNet
connection.

(There are arguments that PipeNet would be immune to this type of
correlation, in that a single node feeding a PipeNet connection is as good
as N nodes. The devil's in the details. I argue that a LAM feeding a
PipeNet connection is at least as secure against monitoring as a single
node feeding a PipeNet, and possibly more secure, practically speaking.)

--Tim May

The Feds have shown their hand: they want a ban on domestic cryptography
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
ComSec 3DES:   408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^2,976,221   | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."

On Tue, 27 Jan 1998, Tim May wrote:
> A LAM approach is low tech, and can be implemented easily enough. (And
> PipeNet becomes much more feasible...)

I agree.

> Even an adventurous company, with many machines on various networks, could
> deploy a LAM on their network.

There are several such companies outside the US that I can think of.

> (Though the laws about corporate culpability are written in ways that a
> Silicon Graphics or Sun or C2Net would have much to fear in having their
> corporate network associated with a LAM of any sort. Hence my point about
> many and varied residential users in a physical building being the LAM
> nodes.)

Sure. A LAM would not happen at any of the above companies. But there are
several non-US ISP's and other outfits with triple fiber to the backbone
that could set this up. [You know who I am talking about, lurkers. :-) How
about it]?

> Another point about LAMs is that they are useful as "concentrators" for
> PipeNet connections. To wit,
> 
> Suppose someone has deployed a PipeNet connection to another node. Fine,
> but the NSA and Mossad and GCHQ and other enemies of freedom may watch the
> traffic flowing into the node feeding that PipeNet connection.
> 
> So why not do a better job of "loading" this PipeNet connection by having a
> LAM at the site? Then, watchers see the stuff flowing into the LAM, and
> have less idea (correlation-wise) of what's then making use of the PipeNet
> connection.

That setup would work even better if operated by a major ISP. If you run
10% of a country's (and be it a small country) IP traffic through a LAM,
the computations an attacker has to perform become complex to the point of
being intractable. Especially if the ISP runs dial-up. [Lurkers, your
thoughs please]?

Of course we won't see such sites until somebody writes the
software.

Cypherpunks write code,
-- Lucky Green <shamrock@cypherpunks.to> PGP v5 encrypted email preferred.
   "Tonga? Where the hell is Tonga? They have Cypherpunks there?"