[OTR-dev] Socialist millionaire efficiency on J2ME platforms

[Ian Goldberg]

On Tue, Mar 02, 2010 at 06:08:25PM +0000, Vladimir wrote:
> On 02/03/2010 17:11, Ian Goldberg wrote:
>> On Tue, Mar 02, 2010 at 01:44:05PM +0000, Vladimir wrote:
>>> Hello,
>>>
>>> I'm currently using fingerprints to identify clients using my
>>> application on their mobile phones. The application uses J2ME.
>> Cool; which application is this?
>>
>>> I am  interested in using SMP but I doubt it will be possible because
>>> of the  computationally intense calculations (power in particular).
>>> The example  in the documentation talks about its uses on a
>>> BlackBerry, but the aim  of my software is to be used on less powerful
>>> devices too. What effects  on performance will SMP have on a less
>>> powerful processor?
>> In regular OTR conversation, 2 modexps (the expensive operation) are
>> done every time one of the parties creates a new temporary encryption
>> key, which is generally done approximately every message.
> My protocol is different from OTR in that respect. It uses public key  
> encryption to exchange a symmetric key, which is used for the duration  
> of the conversation. Both clients (A and B) have to generate a pair for  
> every application startup. If A wants to speak to B, then A encrypts a  
> freshly generated symmetric key using B's public key.

So no forward secrecy, then?  If B's private key is compromised at any
time in the future, all past messages to B are retroactively revealed?

> Along with the  encrypted symmetric key, A sends a hash fingerprint of
> both public keys  to B.

Why send the hash, if you're going to compare it offline anyway?  The
MITM can easily replace the hash with a hash of his own key and Bob's.

> Then A and B have to contact each other to confirm the  
> fingerprint. By confirming the fingerprint, we know that no MITM attack  
> has taken place, since the keys used for encrypting them are the correct  
> ones. In a way A says "I encrypted the symmetric key using this public  
> key, is that ok?".

Right.  If only you could get users to actually contact each other
out-of-band to confirm hashes.  :-)

>> In SMP, each side does about 9 modexps, but only once per person you
>> talk to.  So I'd say SMP should take way less power than the rest of the
>> conversation.
> I'm not familiar with the modexps measurements but it seems to me that  
> using 1536-bit primes is still more than generating a single RSA  
> key-pair, which is enough of a burden right now. Please correct me if  
> I'm wrong.

Hmm?  Generating an RSA key pair is much more expensive than a modexp.
I just did a quick timing test on my desktop machine.  A 1536-bit RSA
key generation takes between 300 and 900 ms.  A 1536-bit modexp takes
less than 4 ms.

If RSA key gen is a burden, why aren't you using a DH-based system,
where the keygen is super-cheap (one modexp)?

   - Ian