Subject: [Cfrg] Forward symmetric encryption

From: ngaga Gisse <[email-masked]>
Date: Fri, 11 May 2007 05:14:05 -0700 (PDT)

Hi, 
  I have the following question;
  Is it possible to have a forward   secure symmetric  encryption scheme that generated  different  encryption  keys (evolves) but   allows to decrypt the messages with one key (master key)?. Such a scheme must also allow dcryption using  individual keys. 
  I will highly appreciate if anyone over there knows the url to such information or has such information. 
  Ngaga 

---------------------------------
Need a vacation? Get great deals to amazing places on Yahoo! Travel. 

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "Hugo Krawczyk" <[email-masked]>
Date: Fri, 11 May 2007 15:26:46 -0400

If* *I understand your question correctly then the following is a solution.

You use a PRF (HMAC, CBC, etc) and choose a master key MK. Then each time
period t (I guess a notion of "time period" is implicit in your idea of
"evolving key") you compute a key Kt =F(MK,T). Whoever finds (or is
given) Kt does not learn anything about previous or later period keys. The
owner of MK can generate keys for all periods and then decrypt under all
period keys. Of course, if MK is disclosed all keys are revealed (but that
is unavoidable with your requirments).

On 5/11/07, ngaga Gisse <[email-masked]> wrote:
> Is it possible to have a forward   secure symmetric  encryption scheme
> that generated  different  encryption  keys (evolves) but   allows to
> decrypt the messages with one key (master key)?. Such a scheme must
> also allow dcryption using  individual keys.
> ------------------------------
> Need a vacation? Get great deals to amazing places
> <http://us.rd.yahoo.com/evt=48256/*http://travel.yahoo.com/;_ylc=X3oDMTFhN2hucjlpBF9TAzk3NDA3NTg5BHBvcwM1BHNlYwNncm91cHMEc2xrA2VtYWlsLW5jbQ-->on
> Yahoo! Travel.
>
>

---

From: Adam Back <[email-masked]>
Date: Sat, 12 May 2007 19:14:31 -0400

I think the forward-secrecy term is a bit ambiguous, so I will use
Anderson's forward and backward secure terminology.

If you use Anderson's definition of forward secure (recover from key
compromise), then I think you cant acheive forward security with
symmetric-key techniques (where the model is the attacker gained
temporary access all your keying material, then lost access to your
computer; and is able to eavesdrop on all your communications).  Also
assume you have a random number generator, with some continuous
re-seeding (and sufficient ability to recover in away that cant be
incrementally matched by the attacker -- one of the design goals of
Yarrow).  But still without a fresh ephemeral-key exchange (like EDH)
you have no means to communicate the fresh-keys.

The reverse "backward secure" is can be done with symmetric
techniques, eg with a hash chain.  The Cebolla anonymous IP tunnel
uses both (infrequent) forward secure (public key based) security, and
(frequent) backward secure (symmetric key based) security.  (Of course
without the "master key" aspect.

Apart from the crypto aspects, one could argue that forward security
is a bit dubious in practice, because with your key material the
attacker and ability to hijack TCP the attacker can impersonate you.
Also if he has sufficient power on your machine to take key material,
perhaps he can modify your software, install a root-kit etc.

Now the common counter-argument is that the attacker gained access to
an unprivileged account, and so could read some of the users key
material, but not modify software.

However in practice most common operating systems have multiple
unfixed privilege escalation attacks available at any given time.

So then it comes down to your presumed attacker capabilities -- is he
a sophisticated hacker, or does he have the money to subscribe to one
of the corporate intrusion testing tools that comes with updates for
many exploits, ready to "test" with.

But still I think forward security is useful as a defense in depth, in
case your protocol turns out not to be as secure as you thought it was
(eg leaks randomness over time, making keys gradually obtainable, like
bliechenbacher's attack applying to some SSL implementations), there
is some chance that moderately frequent forward secret rekeying might
ameliorate the defect.

Adam

---

From: [email-masked]
Date: Thu, 17 May 2007 09:07:32 -0600

Hello Adam Back and cfrg:

Thanks for your thoughts about forward security.  I've been contributing to the
design of ZRTP [1], and in that context I've regarded forward security and
related properties as valuable, so I was interested in this:

> perhaps he can modify your software, install a root-kit etc.

That's a good argument, but also consider that installing a root-kit etc.
increases the chance that the attack will subsequently be discovered.  In the
context of ZRTP, I think forward security offers a pretty good improvement in
making the prospect of launching an attack less appealing.  Consider laptops,
handhelds, and cell-phones, which might occasionally be left unattended, and
which I think are more vulnerable to having their secrets read out than to
having their software modified.

There is a related property that I like in ZRTP which I don't recall seeing in
the crypto literature.  I call it "self-healing".  Suppose an attacker learns
both Alice's and Bob's secrets, but then if he does *not* intercept the next
connection between Alice and Bob, then they use that connection to generate and
exchange new secrets, rendering the stolen secrets moot.

You can see that "self-healing" is very like forward security, but not quite.
For one thing, you can have self-healing without using asymmetric cryptography,
and by the same token, self-healing can work even if the attacker is using
strong Man-in-the-Middle Attacks (as long as he fails to intercept one of your
connections).

If anyone has pointers to related ideas in the crypto literature, I would
appreciate it.

Regards,

Zooko O'Whielacronx

[1] http://zfoneproject.org

---

From: Adam Back <[email-masked]>
Date: Thu, 17 May 2007 15:54:48 -0400

On Thu, May 17, 2007 at 09:07:32AM -0600, [email-masked] wrote:
> You can see that "self-healing" is very like forward security, but
> not quite.  For one thing, you can have self-healing without using
> asymmetric cryptography

Are you sure about that?  How would that work?  There are shared keys
between the two parties, all those keys are compromised, you have a
good PRNG with fresh entropy, but how do you communicate any new
randomly generated keys to the other party without using asymmetric
keys?

> and by the same token, self-healing can work even if the attacker is
> using strong Man-in-the-Middle Attacks (as long as he fails to
> intercept one of your connections).

Thats a good feature.

About other literature you could look at cebolla, it defines a related
concept of forward-anonymity, for multi-hop connections.

Adam

http://www.cypherspace.org/cebolla/

---

From: Ken Raeburn <[email-masked]>
Date: Thu, 17 May 2007 16:51:06 -0400

> randomly generated keys to the other party without using asymmetric

The critical part is that an exchange is missed by the attacker.  The  
new-key exchange protected by another key is compromised only if an  
attacker gets both the old key and the traffic.  If no one listens to  
an exchange (or if anyone does, the exchanged data and the  
compromised key can't ever get put together), then that exchange is  
in a sense secure.  There's no way to guarantee it, or determine if  
an exchange was secure, without additional factors (like an  
additional key or communications channel known to be safe), but such  
a protocol could still reduce damage from a compromise if you get  
lucky.  Which is nothing to base a security proof on, but it helps  
with the "mitigating the damage" aspect of security work.

On the flip side, though, if a MITM attacker can negotiate new and  
different keys with each party, it might make for an easy denial of  
service attack, if the attacker can make each legitimate  
correspondent think that the other is in fact the attacker once the  
MITM stops interfering.  I'm not sure if that's going to be an  
inherent vulnerability of "self-healing" protocols with only  
symmetric keys.

Ken

---

From: "Mihir Bellare" <[email-masked]>
Date: Fri, 18 May 2007 09:42:15 +0700

> > information or has such information.
A general pointer for forward security in the symmetric setting is:

http://www-cse.ucsd.edu/users/mihir/papers/fspkc.html

-Mihir