[OTR-dev] Socialist millionaire efficiency on J2ME platforms

[Vladimir]

On 02/03/2010 18:46, Ian Goldberg wrote:
> 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?
>    
B's private key will not exist once the application is shut down/restarted.
>    
>> 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.
>    
If MITM replaces the hash, then A and B will know about it during the 
fingerprint (hash) verification.
>    
>> 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.  :-)
>    
Yes that is why I am so interested in SMP. :-)
>    
>>> 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)?
>    
I always thought D-H is more computationally expensive. I need to check 
my sources :) thanks for pointing this out.

Regards,
Vladimir