[GNUnet-developers] 1024 vs. 2048 bit RSA

[Christian Grothoff]

Hi all!

I've just made a semi-important change to the system, and I wanted to document 
the rationale here (so that you can object or hold your peace).  Basically, I 
changed the length of the RSA key for KBlocks from 2048 bits to 1024 bits.
This does NOT affect the size of the RSA keys for hostkeys or pseudonyms.

Why?

Well, obviously performance.  Inserting svn/doodle on a PIII-800 with 2048 
bits took 53m (with standard LE options).  After changing to 1024 bits (and 
everything else being the same), the insertion took only 6m.  I consider 53 
minutes unacceptably long.

What is the disadvantage?  Surprisingly, the disadvantage is extremely small.  
Clearly 1024 are easier to factor (though still today totally impractical).  
Not to mention that for KBlocks, an adversary would probably rather try to 
guess the keyword than to factor a 1024 bit RSA key.  If the adversary 
guesses the keyword, he is able to do MORE than he could do with factoring 
alone. The change to 1024 bit only makes the guessing attack as much faster 
as it speeds up the insertion -- but the guessing of the right words is still 
equally difficult.  

Now, suppose the adversary is only able to factor the 1024 bit key (but was 
still not able to guess it).  What can he do now?  Well, he can construct an 
invalid KBlock which will pass verification by intermediaries (but not the 
final recipient since the decryption will still not result in valid data).  
So the adversary can trick the network into possibly replicating an invalid 
KBlock and possibly gain a little bit of trust for sending an invalid reply.  
That's it.  And the expense was factoring a 1024 bit RSA key.  A rather 
extremely uneconomical attack that the network and its users would barely 
notice (high cost, minimal effect).

So in conclusion I believe picking a 1024 bit key is the better choice here.

Happy hacking

Christian