[Standards-JIG] Re: The Great Encryption Debate

David Chisnall theraven at sucs.org
Wed Aug 10 11:20:55 UTC 2005

On 9 Aug 2005, at 20:54, Ian Paterson wrote:

> Yes. But if Alice wanted to know if Charlie was in Bob's roster  
> then she
> could simply propose a chat and send him the hash of Charlie's JID
> (whether Charlie is really on her roster or not doesn't matter).

True, but this isn't much of an invasion of privacy - Alice needs to  
already know Charlie's JID and needs to be friendly enough with Bob  
to set up a secure chat session (I would suggest that encrypted chat  
be default for people in your roster, not for random people).  Also,  
this would not work at all if we allowed each user to specify trusted  
third parties - all this would allow Alice to do is determine that  
Bob and Charlie had exchanged keys at some point in the past - it  
might also be worth speculatively establishing trust relationships  
with people not on your roster, in case you want to use them later as  
intermediaries (although this is probably only useful on a client you  
use often, and should be an option so it can be disabled on low- or  
expensive-bandwidth links).

> I really like your idea... but, as you hinted, the scheme could  
> consume
> a frightening amount of bandwidth. If the TTL allowed 4 hops and an
> average roster includes 32 people, then up to one million requests  
> would
> be made!
> If all Alice's contacts asked all their contacts (and it stopped  
> there),
> then up to 1000 requests would still be required.

Well, it wouldn't be quite that bad.  For one thing, you would only  
be asking people you already had a trust-relationship with.  If you  
are lucky, and this is everyone on your roster, then this means that  
you are more likely to find a match in the first hop.  It could also  
be mitigated by using an adaptive TTL - start with TTL 1, increase to  
TTL 2 on failure, increase to TTL 3 with certain other restrictions  
(only query people on the same server as Bob).  Caching could also  
speed up the process.

A server could possibly be used as an intermediary in this,  
maintaining an internal list of trust relationships and finding the  
shortest path - if there were a crypto intermediate on each server,  
then it could find a path from Alice to someone on Bob's server to  
Bob's server, and then Bob's server could find a path from that user  
to Bob.  Additionally, a server could note when two webs of trust  
become joined by a single person and suggest that other users might  
like to start trusting people in the other web - this would have then  
have then benefit that it would eliminate the ability for to discover  
if Charlie was in Bob's roster - there would be no difference between  
Charlie being in Bob's roster and Charlie's key having been signed by  
one of Bob's friends as a result of a server-initiated signing.

Note that this does not require the server to be trusted, since it  
has no part in signing keys.  The worst a compromised server could do  
would be to claim that no web of trust existed containing both  
people, in which case they would fall back to not using the server.

Note also that the key-signing is (or, at least, should be) a one-off  
occurrence.  It will produce network spikes, rather than increases in  
total usage.  Additionally, the total number of key-signings /  
discoveries should drop over time as larger webs of trust are built,  
requiring less searching to find a trusted person.

> Again there is a privacy issue. Alice would have to disclose the fact
> that she was starting a trust relationship with Bob to all her  
> contacts.

Is this a problem?  If so, then a client could prompt to ask which  
people Alice is happy with knowing - if it's no one then that's a  
problem.  It would also be possible for Alice and Bob to agree on a  
trusted third party (TTP) out-of-band (e.g. during an unencrypted  
chat session) and use this person.  As a fall-back, it might be nice  
if a TTP could be a key-signing organisation such as CA Cert which  
verifies the individual's identity in person.

I think it is important for us all to remember that cryptography is  
hard.  It is an axiom that anyone can design a cryptography scheme  
that they can not break themselves, and it would be very easy for a  
crypto JEP to be rushed through without proper analysis - only to  
have holes poked in it after it has been implemented.

More information about the Standards mailing list